Natural Deduction Homework #1

Use the following six rules to do Natural Deductions:

Modus Ponens Modus Tollens Hypothetical Syllogism

A → B A → B A → B

A ~ B B → C

\ B \ ~ A \ A → C

Disjunctive Syllogism Conjunction Simplification

A v B or A v B A A & B

~ A ~ B B \ A

\ B \ A \ A & B

The relation between the components of the rules stated in ordinary language:

Modus Ponens Modus Tollens

A → B (Conditional) A → B (Conditional)

A (Antecedent) ~ B (Negation of Consequent)

\ B (Consequent) \ ~ A (Negation of Antecedent)

Hypothetical Syllogism

A → B (Conditional, Antecedent same as the Antecedent in the Conclusion, Consequent same as the Antecedent of the other Premise)

B → C (Conditional, Consequent same as the Consequent in the Conclusion, Antecedent same as the Consequent of the other Premise)

\ A → C (Conditional, Antecedent same as the Antecedent in one Premise, Consequent same as the Consequent in the other Premise)

Disjunctive Syllogism

A v B or A v B (Disjunction)

~ A ~ B (Negation of one Disjunct)

\ B \ A (The other Disjunct)

Conjunction Simplification

A (Conjunct) A & B or A & B (Conjunction)

B (Conjunct) \ A \ B (Either of the Conjuncts)

\ A & B (Conjunction)

Identify the rule used in the following 1-step arguments:

(1) (D v E) & (F v G) (2) (S → T) v [(U & V) v (U & V)]

\ D v E ~ (S → T)

\ (U & V) v (U & V)

(3) (F v G) → ~ (G & ~ F) (4) (A → B) → (C v D)

~ (G & ~ F) → (G → F) A → B

\ (F v G) → (G → F) \ C v D

(5) N → (O v P) (6) (C v D) → [(J v K) → ~ E]

Q → (O v R) ~ [(J v K) → ~ E]

\ [N → (O v P)] & [Q → (O v R)] \ ~ (C v D)

Identify the line numbers and rules used to justify each step in the following deductions:

(7) 1. (E v F) & (G v H) (8) 1. I → J

2. (E → G) & (F → H) 2. J → K

3. ~ G 3. ~ L

\ H 4. I v L

4. E v F \ K

5. G v H 5. I → K

6. H 6. I

7. K