Proofs with the Rules of Inference

This post and video begin to explain how to do proofs in symbolic logic using the rules of inference. At the end, it includes some proofs to try on your own.

There are an infinite number of deductively valid argument forms. Consider hypothetical syllogism, for example.

P ⊃ Q
Q ⊃ R
 P ⊃ R

From two conditionals, we can infer a new conditional with the antecedent of the first and the consequent of the second so long as the consequent of the first matches the antecedent of the second. We can link a series of conditionals in the same way, such that the antecedent of one matches the consequent of the next, allowing us to infer a conditional with the antecedent of the first and the consequent of the last. Since there is no limit on how many conditionals we can link together in this way, that right there gives us an infinite number of deductively valid argument forms.

Or consider constructive dilemma.

(P ⊃ Q) & (R ⊃ S)
P ∨ R
 Q ∨ S

With any number of conditionals and a disjunctive premise of every antecedent of every one of these conditionals, we can infer the disjunction of all their consequents. This gives us another infinite set of valid argument forms that doesn’t even overlap with the first set.

(P ⊃ Q) & (R ⊃ S)
~Q ∨ ~S
 ~P ∨ ~R

Similar to the infinite set in the constructive dilemma model, there is another infinite set in the pattern of destructive dilemma. And even without counting any of these, there will still be an infinite number of valid argument forms.

Of course, it would not be practical, much less even possible, to memorize them all as individual rules. As the number of statements expressed in the premises grew, it would become more and more unwieldy to prove them with truth tables, eventually reaching a size only computers could handle, and eventually surpassing that size too. So, to show that long arguments are deductively valid, we normally rely on proofs.

A proof consists of the application of various rules that are simple enough to be easily recognized as valid and small enough in number to be easily remembered. The rules of inference and the rules of replacement are part of the set commonly used in proofs. If you have viewed my previous videos on symbolic logic, you are now ready to begin learning how to do proofs. In this video, we will begin with proofs that use the rules of inference. Proofs that use the rules of replacement will wait until another video. Before we begin looking at proofs, let’s review the rules of inference.

1. P & Q
∴ P

1. P & Q
∴ Q

1. P
2. Q
∴ P & Q

1. P ∨ Q
2. ~P
∴ Q

1. P ∨ Q
2. ~Q
∴ P

1. P
∴ P ∨ Q

1. P ⊃ Q
2. P
∴ Q

1. P ⊃ Q
2. ~Q
∴ ~P

P ⊃ Q
Q ⊃ R
 P ⊃ R

(P ⊃ Q) & (R ⊃ S)
P ∨ R
 Q ∨ S

(P ⊃ Q) & (R ⊃ S)
~Q ∨ ~S
 ~P ∨ ~R

1. P ⊃ Q // Premise
2. Q ⊃ R // Premise
3. R ⊃ S // Premise
Prove: P ⊃ S
4. P ⊃ R // 1, 2 Hypothetical Syllogism
5. P ⊃ S // 3, 4 Hypothetical Syllogism

1. P & Q // Premise
2. R & S // Premise
Prove: Q & S
3. Q // 1 Simplification
4. S // 2 Simplification
5. Q & S // 3, 4 Conjunction

1. P // Premise
2. Q // Premise
3. (P & Q) ⊃ R
Prove: R
4. P & Q // 1, 2 Conjunction
5. R // 3, 4 Modus Ponens

1. P ∨ Q // Premise
2. Q ⊃ R // Premise
3. S & ~R // Premise
Prove: P
4. ~R // 3 Simplification
5. ~Q // 2, 4 Modus Tollens
6. P // 1, 5 Disjunctive Syllogism

1. P ⊃ Q // Premise
2. ~P ⊃ R // Premise
3. S ⊃ T // Premise
4. ~S ⊃ U // Premise
5. ~Q ∨ ~T // Premise
Prove: (R ∨ U) ∨ S
6. (P ⊃ Q) & (S ⊃ T) // 1, 3 Conjunction
7. ~P ∨ ~S // 5, 6 Destructive Dilemma
8. (~P ⊃ R) & (~S ⊃ U) // 2, 4 Conjunction
9. R ∨ U // 7, 8 Constructive Dilemma
10. (R ∨ U) ∨ S // 9 Addition

Homework

1. P // Premise
2. P ⊃ Q // Premise
3. Q ⊃ R // Premise
Prove: R

1. P & ~Q // Premise
2. P ⊃ Q // Premise
Prove: R

1. P ⊃ R // Premise
2. R ⊃ Q // Premise
3. P ∨ T // Premise
4. (P ∨ T) ⊃ (T ⊃ S) // Premise
Prove: Q ∨ S

1. P ⊃ (Q ∨ S) // Premise
2. ~Q ⊃ P // Premise
3. Q ⊃ R // Premise
4. ~R ∨ T // Premise
5. ~T // Premise
Prove: Q ∨ S

1. P ∨ (T ∨ R) // Premise
2. U ⊃ ~P // Premise
3. (T ⊃ Q) & (R ⊃ S) // Premise
4. W & (U & V) // Premise
Prove: Q ∨ S

1. P ⊃ Q // Premise
2. Q ⊃ R // Premise
3. S ⊃ T // Premise
4. T ⊃ U // Premise
5. ~U ∨ ~R // Premise
Prove ~S ∨ ~P

To use the same symbols I have used in writing these proofs, use

⊃ for ⊃

∨ for ∨

& for &

~ for ~

I have let my experience with computer programming influence the conventions I follow in doing proofs. I have followed the convention of using C++ style inline comments to separate the justification for a line from its content. This same style of commenting is used in PHP and my own programming language GAME Code. Taking another cue from programming, I am using only parentheses instead of brackets and braces.