NATURAL DEDUCTION IN PROPOSITIONAL LOGIC

[Pages:10]7 NATURAL DEDUCTION IN PROPOSITIONAL LOGIC

7.1 RULES OF IMPLICATION I

Every substitution instance of a valid argument form is valid. This fact is the key to understanding natural deduction, a method of demonstrating the validity of arguments in propositional logic. In natural deduction, certain valid argument forms (and eventually certain forms of logical equivalences) are used as rules for deducing a proposition from one or more others. For example, since p q / p // q is a valid argument form, then from, say A B and A, B can be validly deduced. A proof or derivation of an argument is a sequence of propositions that leads from the premises of the argument to its conclusion in the following way: each proposition in the sequence is either itself one of the premises of the argument or else can be deduced from one or more previous members of the sequence by means of one of the rules of deduction.

It can be shown in detail--and it is more or less intuitively clear--that any argument for which a proof exists is a valid argument.

As a matter of fact, any valid argument form (or any form of logical equivalence) can be used as a rule of deduction. For the purpose of simplicity, most systems of natural deduction employ only a small number of forms as rules of inference. In this test there are eighteen such rules. The first four are

1. p q p q

2. p q ~q ~p

3. p q q r p r

4. p q ~p q

modus ponens (MP) modus tollens (MT) hypothetical syllogism (HS) disjunctive syllogism (DS)

The basic task in mastering natural deduction is to learn to construct proofs. This task is not always simple and straightforward. The text gives a number of rules of thumb for constructing derivations, but there is no substitute for practice. In some ways natural deduction is like the game of chess; in order to play it well, one must first learn the permitted moves by heart and then, with practice, acquire a "feel" for the strategy of the activity.

91

Sample Exercises from Exercise 7.1. Part II

(1) 1. (D E) (B P) 2. ~(D E) 3. B P

(2) 1. (K ? O) (N T) 2. K ? O 3. N T

(3) 1. (M P) ~K 2. D (M P) 3. D ~K

(4) 1. ~~(R W) 2. S ~(R W) 3. ~S

(5) 1. ~C (A C) 2. ~C 3. A C 4. ~A

(6) 1. F (D T) 2. ~F 3. D 4. D T 5. T

(7) 1. (K ? B) (L E) 2. ~(K ? B) 3. ~E 4. L E 5. ~L

(8) 1. P (G T) 2. Q (T E) 3. P 4. Q 5. G T 6. T E 7. G E

(9) 1. ~W [ ~W (X W)] 2. ~W 3. ~W (X W) 4. X W 5. ~X

1, 2, DS

/ N T 1, 2, MP

/ D ~K 1, 2, HS

/ ~S 1, 2, MT

/ ~A 1, 2, MP 2, 3, MT

/ T 1, 2, DS 3, 4, MP

/ ~L 1, 2, DS 3, 4, MT

/ G E 1, 3, MP 2, 4, MP 5, 6, HS

/ ~X 1, 2, MP 2, 3, MP 2, 4, MT

Untitled-10

92

92

11/6/00, 4:46 PM

(10) 1. ~S D 2. ~S (~D K) 3. ~D

4. ~(~S) 5. ~D K 6. K

1, 3, MT 2, 4, DS 3,5, MP

Additional Exercises for Section 7.1

Using the first four rules of inference, construct proofs of the following arguments.

(1) 1. X (Y Z)

2. X

3. Y

/ Z

(6) 1. X Y

2. Y Z

3. ~Z

/ ~X

(2) 1. X (Y Z)

2. ~X

3. ~Y

/Z

(3) 1. X ~Y

2. ~X

3. Z Y

/ ~Z

(4) 1. X (Y Z)

2. W X

3. W

4. ~Y

/ Z

(5) 1. X (~Y ~Z)

2. ~Y

3. Y X

/ ~Z

(7) 1. X (Y Z) 2. X (Z W) 3. T X 4. ~T

(8) 1. X (Y ? Z) 2. (Y ? Z) W 3. X T 4. ~T

(9) 1. ~X ~Y 2. ~X Z 3. ~Z 4. Y W

(10) 1. X (X ~Y) 2. Y ~T 3. X 4. W T

/Y W /W / W / ~W

7.2 RULES OF IMPLICATION II

In this section four additional rules of derivation are presented. As with the first four, they are valid argument forms.

5. (p q) ? (r s) p r q s

constructive dilemma (CD)

6. p ? q p

simplification (Simp)

7. p q p ? q

conjunction (Conj)

93

Untitled-10

93

11/6/00, 4:46 PM

8. p p q

addition (Add)

These rules may be used in connection with the first four rules. The first eight rules have the common characteristic that they must be applied to whole lines in proofs, and not merely to parts of lines. Without this restriction, the erroneous deduction

(p ? q) r p r

might be thought to be justified by simplification, just to take one example. (The rules introduced later in this chapter, called rules of replacement, are not covered by this restriction.)

Sample Exercises from Exercise 7.2. Part II

(1) 1. ~M Q 2. R ~T 3. ~M R 4. (~M Q) ? (R ~T) 5. Q ~T

/ Q ~T 1, 2, Conj 3, 4, CD

(2) 1. E (A ? C) 2. A (F ? E) 3. E 4. A ? C 5. A 6. F ? E 7. F

/ F 1, 3, MP 4, Simp 2, 5, MP 6, Simp

(3) 1. G (S ? T) 2. (S T) J 3. G 4. S ? T 5. S 6. S T 7. J

/ J 1, 3, MP 4, Simp 5, Add 2, 6, MP

(4) 1. (L T) (B ? G) 2. L ? (K R) 3. L 4. L T 5. B ? G 6. B 7. L ? B

/ L ? B 2, Simp 3, Add 1, 4, MP 5, Simp 3, 6, Conj

(5) 1. (~F X) (P T) 2. F P 3. ~P

4. ~F 5. ~F X 6. P T 7. T

2, 3, MT 4, Add 1, 5, MP 3, 6, DS

94

Untitled-10

94

11/6/00, 4:46 PM

Additional Exercises for Section 7.2

Use the first eight rules of inference to construct proofs for the following arguments.

(1) 1. (X Y) Z

2. (Z T) W

3. X

/ W

(2) 1. X (Y ? Z) 2. Y K 3. W 4. W X

(3) 1. X (Y Z) 2. Y W 3. Z K 4. X

/ K / W K

(4) 1. X Y 2. (~X W) K 3. ~Y ? Z

(5) 1. X (Y Z) 2. ~Y ? W 3. ~X ? T

(6) 1. (X Y) ? (Z W) 2. (K ? L) ? M 3. K (X Z)

/ K T / Z T / Y W

(7) 1. (X Y) ? L 2. (Y Z) ? M 3. (X Z) [(X Y) W]

(8) 1. (X ? Y) (Z ? W) 2. (X ? Y) L 3. ~L ? M 4. Z (N ? O)

(9) 1. (X Y) ? Z 2. X ? L 3. (X Y) M 4. (Y ? M) (Z ? K)

/ W / N / Z W

(10) 1. X P 2. X ? R 3. P (Q ? S) 4. (P ? Q) (P Q)

/ P Q

(11) 1. A (B C) 2. A ? X 3. B ? (Y ?Z)

/ C ? A

95

Untitled-10

95

11/6/00, 4:46 PM

(12) 1. (B C) A 2. A X 3. ~X ? Y 4. D (B C)

(13) 1. (A B) ? (C D) 2. (B E) ? (F G) 3. (A E) (H ? I) 4. H J

(14) 1. (A ? B) (C D) 2. C E 3. A B 4. A ? F 5. (D G) ? H

(15) 1. A B 2. C A 3. C D 4. ~D

/ ~A ? ~D / H ? J / (A ? B) ? (E G) / (B ? ~C) E

7.3 RULES OF REPLACEMENT I

We saw in Sections 7.1 and 7.2 how valid argument forms may be used as rules of inference in natural deduction. Forms of logical equivalences may also be used as rules of inference. Every substitution instance of a form of logical equivalence is a logical equivalence; moreover, either one of a pair of logically equivalent expressions may be substituted for the other in a proof without loss of validity.

Five forms of logical equivalence are given in this section: 9. ~(p ? q) is logically equivalent to (~p ~q).

~(p q) is logically equivalent to (~p ? ~q). These two statements are known as DeMorgan's Rule (DM). 10. (p q) is logically equivalent to (q p). (p ? q) is logically equivalent to (q ? p). These two rules are known as commutativity (Com). 11. [p (q r)] is logically equivalent to [(p q) r]. [p ? (q ? r)] is logically equivalent to [(p ? q) ? r]. These two rules are known as associativity (Assoc). 12. [p ? (q r)] is logically equivalent to [(p ? q) (p ? r)]. [p (q ? r)] is logically equivalent to [(p q) ? (p r)]. These two rules are known as distribution (Dist).

13. p is logically equivalent to ~~p.

This is known as double negation (DN).

96

Untitled-10

96

11/6/00, 4:46 PM

These and the remaining rules of replacement may be applied not only to whole lines in proofs--as the rules of implication must be--but to parts of lines as well. Thus, going from

(p ? q) r to

(q ? p) r

by the rule of commutativity is quite proper.

Sample Exercises from Exercise 7.3. Part II

(1) 1. (~M P) ? (~N Q) 2. ~(M ? N) 3. ~M ~N 4. P Q

(2) 1. J (K ? L) 2. ~K 3. ~K ~L 4. ~(K ? L) 5. (K ? L) J 6. J

(3) 1. R ~B 2. D R 3. B 4. ~~B 5. ~R 6. R D 7. D

(4) 1. (O M) S 2. ~S 3. ~(O M) 4. ~O ? ~M 5. ~M ? ~O 6. ~M

(5) 1. Q (L C) 2. ~C 3. (Q L) C 4. (L Q) C 5. C (L Q) 6. L Q

/P Q 2, DM 1, 3, CD

/J 2, Add 3, DM 1, Com 4, 5, DS

/D 3, DN 1, 4, MT 2, Com 5, 6, DS

/ ~M 1, 2, MT 3, DM 4, Com 5, Simp

1, Assoc 3, Com 4, Com 2, 5, DS

Untitled-10

97

97

11/6/00, 4:46 PM

Additional Exercises for Section 7.3

(1) 1. ~(X ? Y) 2. X 3. Y Z

(2) 1. X ? (Y Z) 2. ~(X ? Y) 3. (Z ? X) K

(3) 1. ~X Y 2. ~Y Z 3. X ? W

(4) 1. (X Y) Z 2. ~(Z W)

(5) 1. X ? (Y ? Z) 2. (Y ? X) (W ? T) 3. (T ? Z) L

(6) 1. ~X T 2. W ? ~T 3. (X Y) Z

(7) 1. ~X 2. ~(X ? Y) ~W

(8) 1. ~(X ~X)

(9) 1. X 2. (~Y X) Z 3. ~ (X ? Z) W

(10) 1. X ? ~Z 2. (Y X) ~W

/Z

/K

/(X ? Y) ? Z /~Y

/(Y ? W) ? Z

/W ? Z /~(W ? Z) /Y

/(W ? X) ? Z /~(Z W)

7.4 RULES OF REPLACEMENT II

The remaining five rules of replacement are: 14. (p q) is logically equivalent to (~q ~p).

This rule is called transposition (Trans). 15. (p q) is logically equivalent to (~p q).

This rule is called material implication (Impl). 16. (p q) is logically equivalent to [(p q) ? (q p)].

(p q) is logically equivalent to [(p ? q) (~p ? ~q)]. These two rules together are known as material equivalence (Equiv).

98

Untitled-10

98

11/6/00, 4:46 PM

 ................
................

In order to avoid copyright disputes, this page is only a partial summary.

Google Online Preview   Download