Introductory Logic Exercises

Solutions are available by request for course instructors and the self-taught.

These documents are intended for the spring 2024 version of PHI 201, Introductory Logic. However, they will be fine-tuned on an ongoing basis.

Chapter 2

The proofs in Chapter 2 should not use dependency numbers, as they are only introduced in Chapter 3. Thus, a correctly written proof will consist of two columns: the first column contains a line number (n) and a formula, the second column contains a justification. For example:

Exercise 2.1

1. Prove that Q ∧ P follows from P ∧ Q. That is, write P ∧ Q on line (1), then use the rules (∧ introduction and elimination) repeatedly until you obtain Q ∧ P.

2. Prove that P ∧ (Q∧R) follows from (P∧Q) ∧ R.

Exercise 2.2 Prove the following sequents.

1. P ∧ Q ⊢ Q ∨ R

2. P ∧ Q  ⊢ (P∨R) ∧ (Q∨R)

3. P ⊢ Q ∨ (P∨Q)

4. P ⊢ (P∨R) ∧ (P∨Q)

Exercise 2.3 Prove that the following argument forms are valid. You may use the rules ∧E, ∧I, ∨I, and MP.

1. P → (Q→R), P → Q, P ⊢ R

2. (A∨B) → T, Z → A, T → W, Z ⊢ W

3. (A→B) ∧ (C→A), (C∧(W→Z)) ∧ W ⊢ (B∨D) ∧ (Z∨E)

4. P → (P→Q), P ⊢ Q

5. P ∧ (P→Q) ⊢ P ∧ Q

6. P → (Q→R), P ∧ Q ⊢ R

Exercise 2.4 Prove that Q → (P→R), ¬R ∧ Q ⊢ ¬P.

Exercise 2.5 Prove the following sequents. Here the double turnstile means that you should prove the sequents in both directions.

1. P ∧ (Q∧R)  ⊣ ⊢ (P∧Q) ∧ R

2. P  ⊣ ⊢ P ∧ P

Exercise 2.6 As we mentioned before, there is only an approximate match between symbolic logic and arguments in the wild. Nonetheless, to develop your intuitions, it helps sometimes to look at an argument in the wild, and to try to represent it symbolically. To that end, let’s try our hand at representing the logical form of some sentences. Here’s how we do it. First of all, identify the overall logical structure of the sentence. Ask yourself: what does the sentence assert? Is it an atomic sentence in the sense that there is no internal logical complexity? Does it assert the conjunction of two other sentences? Does it assert the disjunction of two other sentences? Etc.

For example, the sentence, “The cat is on the mat,” is atomic. In this case, the best we can do is to represent it with a single letter such as P. On the other hand, “The cat is on the mat, and the dog is in the kennel,” asserts a conjunction of two atomic sentences. Thus, it’s best represented as something like P ∧ Q.

For the following sentences, give the most perspicuous representation you can of their inner logical form. First identify the component atomic sentences, and abbreviate each with a (distinct) letter. Then translate the original sentence using the symbols ∨,∧,¬,→ for the logical words “or”, “and”, “not”, “if…then…”. (We have suggested letters for the atomic sentences at the end of each sentence.)

1. It’s not true that if Ron doesn’t do his homework then Hermione will finish it for him. R, H

2. Harry will be singed unless he evades the dragon’s fiery breath. S, E

3. Aristotle was neither a great philosopher nor a great scientist. P, S

4. Mark will get an A in logic only if he does the homework or bribes the professor. A, H, B

5. Dumbledore will be killed, and either McGonagal will become headmistress and Hogwarts will flourish, or else it won’t flourish. K, M, F

6. Harry and Dumbledore are not both right about the moral status of Professor Snape. H, D

7. The spell will work only if Hermione concentrates and Ron doesn’t interrupt. (W, C, I)

8. Draco will apologize or not get dessert, but he won’t do both. (A, D)

9. The Quidditch match will be canceled if it rains, unless the field can be magically dried. (C, R, M)

10. If Taylor Swift expresses support for environmental policies, then she will also advocate for renewable energy, unless she prioritizes economic concerns. (E, A, P)

11. If Elon Musk innovates in electric car technology or develops new space exploration methods, then he will be recognized as a pioneer in technology. However, if he fails to achieve progress in either field, he will not be recognized as such. (I, D, R)

12. If it is not sunny then we will not go to the beach. (S, B)

13. Either it’s sunny or we will not go to the beach. (S, B)

14. We will not go to the beach if it’s not sunny. (S, B)

15. We will go to the beach only if it’s sunny. (S, B)

16. It’s being sunny is a necessary but not sufficient condition for our going to the beach. (S, B)

17. A society does not have free speech unless it allows peaceful protests. (F, P)

18. Professor Plum is the murderer unless the weapon was a candlestick or the crime occurred in the library. (P, C, L)

19. Professor Plum is the murderer only if the weapon was the candlestick and the crime occurred in the library, or the weapon was the dagger and the crime didn’t occur in the library. (P, C, L, D)

20. Provided, but only provided, that the French Fleet is sailed forthwith for British harbors, His Majesty’s Government give their full consent to an armistice for France. (S, C)

21. For the tenability of the thesis that mathematics is logic it is not only sufficient but also necessary that all mathematical expressions be capable of definition on the basis solely of logical ones.

Exercise 2.6.1 Display the propositional form of the following argument. Does it seem valid to you? Does it convince you that God does not exist?

Premise 1: If God exists then he is all good and all powerful.

Premise 2: If God is all good and all powerful then there would be no suffering.

Premise 3: There is suffering.

Conclusion: Therefore, God does not exist.

Exercise 2.6.2 Display the propositional form of the following argument. Does it seem valid to you?

Premise 1: If the murder happened in the kitchen, then the weapon was either a knife or a revolver.

Premise 2: The murder did not happen in the kitchen.

Conclusion: Therefore, the weapon was neither a knife nor a revolver.

Exercise 2.6.3 Display the propositional structure of the following argument.

Premise 1: The greatest genius of our time must have made groundbreaking contributions in multiple advanced fields.

Premise 2: Elon Musk has made groundbreaking contributions in multiple advanced fields, such as space exploration with SpaceX, electric vehicles with Tesla, and neural technology with Neuralink.

Conclusion: Therefore, Elon Musk is the greatest genius of our time.

Exercise 2.7 Prove that the following argument forms are valid. Each line of your proof must either be one of the premises given, or it must be justified from previous lines by one of our rules of inference: MP, MT, DN, ∧I, ∧E, or ∨I.

1. ¬¬Q → P, ¬P ⊢ ¬Q

2. P → (P→Q), P ⊢ Q

3. (P∧P) → Q, P ⊢ Q

4. P ⊢ Q ∨ (¬¬P∨R)

5. ¬P → ¬Q, Q ⊢ P ∧ Q

6. P → ¬(Q∨R), Q ⊢ ¬P

Exercise 2.8 Demonstrate that the following argument forms are invalid by providing a counterexample, i.e. give English sentences for P, Q, R such that the premises are obviously true but the conclusion is obviously false.

1. P → ¬Q, ¬P ⊢ Q

2. P → R ⊢ (P∨Q) → R

3. P → Q ⊢ Q → P

4. P → Q ⊢ P → (Q∧R)

Chapter 3

The proofs in this chapter require the use of dependency numbers. Thus, a correctly written proof consists of three columns with a list of dependency numbers in the first column, a line number and a formula in the second column, and a justification in the third column. For example:

Exercise 3.1 Prove the following sequents. (You should not use reductio ad absurdum in any of these problems, although you might be tempted to do so in 3.1.8, 3.1.9, and 3.1.10. The hints explain how the other rules can be used to derive the same things as RA, albeit in a much more roundabout way. For the philosophically minded: MT is an “impure” rule since its application requires the presence of different connectives.)

1. P ⊢ Q → (P∧Q)

2. (P→Q) ∧ (P→R) ⊢ P → (Q∧R)

3. P → (Q→R) ⊢ Q → (P→R)

4. P → Q ⊢ (Q→R) → (P→R)

5. P → (P→Q) ⊢ P → Q

6. P → (Q→R) ⊢ (P∧Q) → R

7. (P∨Q) → R ⊢ P → R

8. ¬P ⊢ ¬(P∧Q) (Hint: For any sentences ϕ and ψ, if you can derive ψ ⊢ ϕ then you can derive ¬ϕ ⊢ ¬ψ. Indeed, apply CP to ψ ⊢ ϕ to derive  ⊢ ψ → ϕ. Now assume ¬ϕ and apply MT.)

9. ¬(P∨Q) ⊢ ¬P ∧ ¬Q (Hint: If you can prove ¬(P∨Q) ⊢ ¬P and ¬(P∨Q) ⊢ ¬Q individually, then you can use ∧I and you’re done. )

10. P → ¬P ⊢ ¬P (Hint: First prove that P ⊢ (P→¬P) → ¬P, resulting in a proof with first line “1 (1) P A” and last line “1 (n) (P→¬P) → ¬P”. Now use line 1 again to derive ¬¬P and apply MT.)

11. P → (Q→R), P → Q ⊢ P → R

12. P → (Q→R) ⊢ (P→Q) → (P→R)

13. P → Q ⊢ ¬Q → ¬P

14. (P∧Q) → R ⊢ P → (Q→R)

15. P → (Q→R) ⊢ P → (¬R→¬Q)

16. P → (Q→R) ⊢ ¬R → (Q→¬P)

17. (P→Q) → P ⊢ (P→Q) → Q (Hint: Not as difficult as it looks. Assume (P→Q) → P and P → Q. The latter can be used both as the antecedent of a conditional, and as a conditional itself.)

Exercise 3.2 Prove the following sequents. (Do not use reductio ad absurdum, which is only introduced in a subsequent section.)

1. ⊢ (P∧Q) → (Q∧P)

2. ⊢ (P∧Q) → P

3. ⊢ Q → (P→Q)

4. ⊢ Q → (P→P)

5. ⊢ P ∨ ¬P (Hint: This can be proven with the rules we have so far! One possibility is to use 3.1.10, but replace P with P ∨ ¬P. In particular, use the fact that ¬(P∨¬P) ⊢ P to derive  ⊢ ¬(P∨¬P) → ¬¬(P∨¬P).)

6. ¬P ⊢ P → Q (Hint: Prove ¬P ⊢ ¬Q → ¬P and then use the contrapositive maneuver.)

7. ⊢ (P→Q) → (¬Q→¬P)

8. (P→Q) → P, Q ⊢ P

9. (P→Q) → P ⊢ ¬P → P

Exercise 3.3 Prove the following sequents. (Still do not use RA. It is good to learn to prove directly when you can!)

1. (P→R) ∧ (Q→R) ⊢ (P∨Q) → R

2. P ∨ (Q∨R)  ⊣ ⊢ (P∨Q) ∨ R

3. P ∨ Q, ¬P ⊢ Q (Hint: Recall that ¬P ⊢ P → Q.)

4. P ∧ (Q∨R)  ⊣ ⊢ (P∧Q) ∨ (P∧R)

5. P ∨ (Q∧R)  ⊣ ⊢ (P∨Q) ∧ (P∨R)

6. ¬P ∨ Q  ⊣ ⊢ P → Q

7. ¬P ∨ ¬Q ⊢ ¬(P∧Q)

Exercise 3.4 Prove the following sequents.

1. P → Q ⊢ ¬(P∧¬Q)

2. ¬(P∧Q) ⊢ ¬P ∨ ¬Q

3. ¬(P→Q) ⊢ P ∧ ¬Q

4.  ⊢ (P→Q) ∨ (Q→P)

5. P → (Q∨R) ⊢ (P→Q) ∨ (P→R)

6. (P∧Q) → ¬Q ⊢ P → ¬Q

7. P ∧ ¬Q ⊢ ¬(P→Q)

8. ⊢ ((P→Q)→P) → P (Hint: One possibility is to first prove  ⊢ P ∨ ¬P, and then argue by cases. The first case is easy if you remember “positive paradox”. For the second case, remember “negative paradox”, i.e. that ¬P implies P → Q.)

9. P → (Q∨R) ⊢ ¬R → (¬Q→¬P)

10. P → ¬Q ⊢ (P∧Q) → R

11. P → ¬Q ⊢ P → (Q→R)

12. ¬(P→Q) ⊢ P → ¬Q

13. P  ⊣ ⊢ (P∧Q) ∨ (P∧¬Q)

14. P → (Q→R)  ⊣ ⊢ (P→Q) → (P→R)

15. P → ¬P  ⊣ ⊢ ¬P

16. P → (Q→¬Q)  ⊣ ⊢ P → ¬Q

17. (P→Q) → (P→¬Q)  ⊣ ⊢ P → ¬Q

18. P  ⊣ ⊢ P ∧ (Q∨¬Q)

19. P  ⊣ ⊢ P ∨ (Q∧¬Q)

20. (P→Q) → Q ⊢ (Q→P) → P

21. (P→Q) → R ⊢ (P→R) → R

22. (P→R) → R  ⊣ ⊢ P ∨ R (Hint for ⊢: it’s easy to derive ¬P → R from the sentence on the left.)

23. (P→Q) → P  ⊣ ⊢ P (Hint for ⊢: assume ¬P and derive P → Q.)

Exercise 3.5 People who reject DN elimination also tend to reject the law of excluded middle.¹ This exercise explains why. Use the law of excluded middle and EFQ to re-derive DN elimination. That is, show that ¬¬P ⊢ P, without using DN, but where you’re allowed to insert P ∨ ¬P, and where you’re allowed to infer anything from a contradiction.

For discussion: is the law of excluded middle more obviously correct than the DN rule?

Exercise 3.6 An earlier exercise shows that the following sequent is provable:  ⊢ (P→Q) ∨ (Q→P). Give an example of English sentences P and Q where it does not seem correct to say that either P → Q or Q → P is true. Discuss what this means about the relationship of propositional logic to rational thinking.

Exercise 3.7 Show that Γ ⊢ ¬(¬ϕ∧¬ψ) can be derived from Γ ⊢ ϕ without using the ∨ rules at any step.

Exercise 3.8 Consider the following scenario:

If a is at home then so is b.

Either d or e, or both are at home.

Either b or c, but not both are home.

d and c are either both at home or both not at home.

If e is at home then a and d are also at home.

Using the letter X for the sentence “x is at home”, write these conditions in propositional logic notation. Then prove that there is a unique scenario that satisfies these conditions. (Hint: Assume E for RA.)

Exercise 3.9 Show that the rule MT can be derived from the other rules.

Exercise 3.10 Show that the rule of DN introduction can be derived from the other rules.

Exercise 3.11 We say that a proof is intuitionist if it does not use DN elimination — but it can use the derived rule EFQ. Show that the following two schema are intuitionistically equivalent:

1. ⊢ ψ ∨ ¬ψ

2.  ⊢ ((ϕ→¬ϕ)→ϕ) → ϕ

By calling them “schema”, we mean that one is allowed to replace the Greek letters with any sentence whatsoever (not just atomic sentences). So a schema is an infinite collection of axioms with the same form. (All of our inference rules are actually schematic in this sense.)

Exercise 3.12 Show that there is a formula χ such that for every formula ϕ,  ⊢ ϕ ↔︎ (χ→ϕ).

Exercise 3.13 Show that there is an intuitionistic derivation of  ⊢ P ∨ ¬P from the schema ϕ → (ψ∨θ) ⊢ (ϕ→ψ) ∨ (ϕ→θ). Hint: use Q ∨ ¬Q for ϕ. Supposing that there is no intuitionist proof of  ⊢ P ∨ ¬P, argue that there is no intuitionist proof of P → (Q∨R) ⊢ (P→Q) ∨ (P→R).

Glossary

Atomic sentence

In propositional logic, an atomic sentence is simple in the sense that it is not the result of composition from simpler sentences using the propositional connectives.

DN

Double negation introduction and elimination are basic rules of our system. The intro rule says that if Γ implies ϕ, then Γ also implies ¬¬ϕ. The elimination rule says that if Γ implies ¬¬ϕ, then Γ also implies ϕ.

EFQ

Ex Falso Quodlibet is a derived rule of our system which can be stated as follows: if sentences Γ imply ϕ ∧ ¬ϕ for some other sentence ϕ, then Γ implies any sentence ψ. This derived rule is sometimes called “explosion”.

Valid

An argument is valid just in case its premises would, if true, provide decisive support for its conclusion. In other words, in a valid argument, the conclusion follows logically from the premises.