Proof

For arguments that involve complex statements, or more than a few premises, even the short version of the truth-table method can be cumbersome. It is often easier and more natural to look for a proof by which the conclusion can be derived from the premises. Proof in logic is like proof in geometry. It is a series of small steps, each of which is itself a valid inference. If we can get from premises to conclusion by valid steps, then the argument as a whole is valid. Constructing a proof often takes some ingenuity, so the fact that you haven't found a proof in a given case does not establish that the argument is invalid. Perhaps you haven't looked hard enough.

Unlike the truth-table method, the method of proof won't establish that an argument is invalid. If an argument is valid, however, a proof will often reveal the connection between premises and conclusion more clearly than the truth-table method does.

Described below are several inference forms commonly used in propositional logic as building blocks from which proofs can be constructed. They can all be proven valid by the truth-table method, and you are already familiar with most of them. These inference rules can be grouped into three general categories:


Comprehension Questions

1 Which of the following is the inference form simplification?
a) p. Therefore, p v q.
b) p v q, ~p. Therefore, q
c) p > q, p. Therefore, q.
d) p . q. Therefore, p.
e) (p > q) . (r > s), p v q. Therefore, q v s.
2 Which of the following is the inference form conjunction?
a) (p > q) . (r > s), p v q. Therefore, q v s.
b) p > q, q > r. Therefore, p > r.
c) p, q. Therefore, p . q.
d) (p > q) . (r > s), ~q v ~s. Therefore, ~p v ~r.
e) p > q, ~q. Therefore, ~p.
3 Which of the following is the inference form addition?
a) p. Therefore, p v q.
b) p v q, ~p. Therefore, q
c) p > q, p. Therefore, q.
d) p . q. Therefore, p.
e) (p > q) . (r > s), p v q. Therefore, q v s.
4 Which of the following is the inference form disjunctive syllogism?
a) p. Therefore, p v q.
b) p v q, ~p. Therefore, q
c) p > q, p. Therefore, q.
d) p . q. Therefore, p.
e) (p > q) . (r > s), p v q. Therefore, q v s.
5 Which of the following is the inference form hypothetical syllogism?
a) (p > q) . (r > s), p v q. Therefore, q v s.
b) p > q, q > r. Therefore, p > r.
c) p, q. Therefore, p . q.
d) (p > q) . (r > s), ~q v ~s. Therefore, ~p v ~r.
e) p > q, ~q. Therefore, ~p.
6 Which of the following is the inference form modus ponens?
a) p. Therefore, p v q.
b) p v q, ~p. Therefore, q
c) p > q, p. Therefore, q.
d) p . q. Therefore, p.
e) (p > q) . (r > s), p v q. Therefore, q v s.
7 Which of the following is the inference form modus tollens?
a) (p > q) . (r > s), p v q. Therefore, q v s.
b) p > q, q > r. Therefore, p > r.
c) p, q. Therefore, p . q.
d) (p > q) . (r > s), ~q v ~s. Therefore, ~p v ~r.
e) p > q, ~q. Therefore, ~p.
8 Which of the following is the inference form constructive dilemma?
a) (p > q).(r > s),(pvr). Therefore, qvs.
b) p > q, q > r. Therefore, p > r.
c) p, q. Therefore, p . q.
d) (p > q) . (r > s), ~q v ~s. Therefore, ~p v ~r.
e) p > q, ~q. Therefore, ~p.
9 Which of the following is the inference form destructive dilemma?
a) (p > q).(r > s),(pvr). Therefore, qvs.
b) p > q, q > r. Therefore, p > r.
c) p, q. Therefore, p . q.
d) (p > q) . (r > s), ~q v ~s. Therefore, ~p v ~r.
e) p > q, ~q. Therefore, ~p.
10 Supply the justification for the fourth step in the following proof.

1. J > (K > L) Premise
2. L v J Premise
3. ~L /~K Premise/Conclusion
4. J
5. K > L
6. ~K

a) 1,2 hypothetical syllogism
b) 1,4 modus pollens
c) 2,3 disjunctive syllogism
d) 3,5 modus tollens
11 Supply the justification for the fifth step in the following proof.

1. J > (K > L) Premise
2. L v J Premise
3. ~L /~K Premise/Conclusion
4. J
5. K > L
6. ~K

a) 1,2 hypothetical syllogism
b) 1,4 modus pollens
c) 2,3 disjunctive syllogism
d) 3,5 modus tollens
12 Supply the justification for the sixth step in the following proof.

1. J > (K > L) Premise
2. L v J Premise
3. ~L /~K Premise/Conclusion
4. J
5. K > L
6. ~K

a) 1,2 hypothetical syllogism
b) 1,4 modus pollens
c) 2,3 disjunctive syllogism
d) 3,5 modus tollens
13 Supply the justification for the fourth step in the following proof.

1. ~S > D Premise
2. ~S v (~D > K) Premise
3. ~D / K Premise/Conclusion
4. ~~S
5. ~D > K
6. K

a) 1,3 modus tollens
b) 2,4 disjunctive syllogism
c) 3,5 modus pollens
d) 3,4 hypothetical syllogism
14 Supply the justification for the fifth step in the following proof.

1. ~S > D Premise
2. ~S v (~D > K) Premise
3. ~D / K Premise/Conclusion
4. ~~S
5. ~D > K
6. K

a) 1,3 modus tollens
b) 2,4 disjunctive syllogism
c) 3,5 modus pollens
d) 3,4 hypothetical syllogism
15 Supply the justification for the sixth step in the following proof.

1. ~S > D Premise
2. ~S v (~D > K) Premise
3. ~D / K Premise/Conclusion
4. ~~S
5. ~D > K
6. K

a) 1,3 modus tollens
b) 2,4 disjunctive syllogism
c) 3,5 modus pollens
d) 3,4 hypothetical syllogism


Constructing a Proof

Equivalence

Q Copyright 310, W.W. Norton & Co.