Results 1 to 4 of 4
Like Tree1Thanks
  • 1 Post By emakarov

Math Help - Natural Deduction - Approaching problems and deciding on assumptions

  1. #1
    Junior Member
    Joined
    Nov 2012
    From
    Manchester
    Posts
    30

    Natural Deduction - Approaching problems and deciding on assumptions

    I have been trying to understand how to use natural deduction rules to solve problems in logic. I understand the different rules, per se. However, I find it the most difficult to determine what can be set as assumptions, in order to solve the problems. For instance, I have understood the simple problems, such as the following: Where it is clear what ought to be the assumption and how to work from there.
    Yet, when it comes to other problems, I get really confused as to what I am allowed to state as assumptions and what not to state as assumptions. Following is an example, in which I have stated R as an assumption, without knowing if that is "legal".

    Is there a simple rule for proving formulas through natural deduction, with regards to problem solving techniques? For instance, when given problems such as:

    How can I know which assumptions to make, etc.?
    Any help is highly appreciated!
    Last edited by aprilrocks92; December 8th 2013 at 02:44 PM.
    Follow Math Help Forum on Facebook and Google+

  2. #2
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Natural Deduction - Approaching problems and deciding on assumptions

    In your second derivation, there is no need for an assumption R to derive P ∨ R from P. Also, you don't cancel R in the ->I rule because the premise of the newly formed implication is P ∧ Q. You are only allowed to cancel the premise.

    Formally, there are only two requirements: each node in the derivation must conform to one of the inference rules and all open assumptions must be eventually closed (or some may be kept open if the problem statement stipulates so). This does not say how to build a derivation, though.

    If you don't use the rule of double-negation elimination, then each branch in the shortest derivation starts with eliminations and ends with introductions (all inference rules are divided into introduction and elimination rules). Note that this is the structure of the two derivations in your post. From this, one can prove the so-called subformula property: in the shortest derivation each formula is a subformula of either an open assumption or the conclusion. So when you need to construct a derivation, break the formula apart by going bottom-up and using introduction rules: to prove an implication, assume the premise, to prove a conjunction, prove both conjuncts and so on. When you arrive at atomic formulas, use open assumption you introduced to derive them.

    It may also help to think about formulas as functions or factories that take premises and produce conclusions. Under this view, conjunctions correspond to pairs (elements of Cartesian product) and disjunctions to elements of disjoint unions. In your third formula, suppose you are given two functions that turn P and R into Q. Then if you have a pair of P and R, it is clear how to produce a Q: just take any element of that pair and apply the corresponding function. It is even enough to have not a pair of P and R, but either P or R.

    Hope this helps, and feel free to ask further questions.
    Thanks from Plato
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Junior Member
    Joined
    Nov 2012
    From
    Manchester
    Posts
    30

    Re: Natural Deduction - Approaching problems and deciding on assumptions

    I'm still a bit confused as to what I can set as the assumption(s).

    The below example confuses me. In line (I), both the first conjunction [(P->Q)&(R->Q)] of the expression, as well as the second conjunction, [P & R], which is actually the conclusion of the left-most implication, is also set as an assumption.

    Natural Deduction - Approaching problems and deciding on assumptions-photo-1-.jpg

    I expected to end this proof with two stacked →Is, because of the ->(P & R)->Q.

    The problem is how to know what expressions to use as assumptions? I keep seeing worked examples, all of them which make sense. However, when I am to solve problems myself, I get confused with the assumptions that can be made. Any advice on this particular matter?

    For instance, I thought one could not assume an expression that is also the conclusion of an implication (P & R), as an assumption? Or is this just the case of the right-most conclusion, in this case Q?

    Evidently, the choice of assumptions confuses me!.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718

    Re: Natural Deduction - Approaching problems and deciding on assumptions

    Your derivation is correct except that it uses P → R instead of P ∧ R two times. I was also at first confused by the first line, which I thought was a part of the derivation rather than the header.

    Quote Originally Posted by aprilrocks92 View Post
    The below example confuses me. In line (I), both the first conjunction [(P->Q)&(R->Q)] of the expression, as well as the second conjunction, [P & R], which is actually the conclusion of the left-most implication, is also set as an assumption.
    P ∧ R is not the conclusion of anything here. Implication associates to the right, so the final formula is

    [(P\to Q)\land (R\to Q)]\to[(P\land R)\to Q]

    It's an implication whose premise is (P\to Q)\land (R\to Q) and whose conclusion is another implication with premise P\land R and conclusion Q.

    Quote Originally Posted by aprilrocks92 View Post
    I expected to end this proof with two stacked →Is, because of the ->(P & R)->Q.
    That's correct.

    Quote Originally Posted by aprilrocks92 View Post
    The problem is how to know what expressions to use as assumptions?
    I can interpret this question in two ways, and I am not sure which of them you mean. When you are constructing a derivation bottom up and have an implication A → B, there is no choice (at least in the shortest derivation without double-negation elimination) other than to use →I, to introduce A and to add it to the list of open assumptions. Every well-formed formula is uniquely parsed, so if it's an implication, the premise A and the conclusion B are uniquely determined. The second possible meaning of your question is which of the existing open assumptions to use in the top part of the derivation, which consists of eliminations (in this case, the part above →E with conclusion Q). Here there is no definite answer; you need to see in which order to combine open assumptions to produce the required formula. For example, when you are proving (P → (Q → R)) → ((P → Q) → (P → R)), you assume (1) P → (Q → R)), (2) P → Q and (3) P and have to prove R. It requires some experimenting to see that you need to apply (1) to (3) to get (4) Q → R, then (2) to (3) to get Q and finally (4) to Q to get R.

    Quote Originally Posted by aprilrocks92 View Post
    For instance, I thought one could not assume an expression that is also the conclusion of an implication (P & R), as an assumption? Or is this just the case of the right-most conclusion, in this case Q?
    Yes, the rightmost conclusion is Q, and P ∧ R is not a conclusion, but the premise of a nested implication. That's why you can assume it.
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. simple natural deduction problems
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: August 7th 2012, 07:20 AM
  2. natural deduction
    Posted in the Discrete Math Forum
    Replies: 3
    Last Post: December 12th 2011, 08:31 AM
  3. Natural Deduction
    Posted in the Discrete Math Forum
    Replies: 9
    Last Post: June 9th 2011, 03:15 AM
  4. natural deduction
    Posted in the Discrete Math Forum
    Replies: 5
    Last Post: April 24th 2010, 11:47 AM
  5. Help with Logic (Natural Deduction)
    Posted in the Discrete Math Forum
    Replies: 7
    Last Post: January 12th 2010, 02:07 PM

Search Tags


/mathhelpforum @mathhelpforum