80-310/610 Logic and Computation Fall 2001

Homework #11

Due Wednesday, November 14

1. Read section 3.1 in van Dalen. Start reading Section 3.2, using the class notes to determine which parts we will focus on.

2. Do problem 1 on page 96.

3. ⋆ Do the following.

a. Prove ¬(p ↔ ¬p) in propositional logic.

b. Use this to prove ¬∃y ∀x (S(y, x) ↔ ¬S(x, x)) in first-order logic.

You can take ↔ to be a defined in terms of ∧ and →, or to be a new symbol with the rules introduced in class, as you prefer. Hint for part (b): if suffices to show that ∀x (S(y, x) ↔ ¬S(x, x)) leads to a contradiction. This is a formalization of the Barber paradox: in a given town there is a (male) barber who shaves every man that does not shave himself. Who shaves the barber?

4. ⋆ Do problem 1 on page 99 of van Dalen.

5. Do problems 2 and 3 on page 99.

6. ∘ Do problem 4 on page 99. The → direction is difficult. (Because the implication is not intuitionistically valid, you will need to use RAA.)

7. ⋆ Do problem 5 on page 99.

8. Do other problems on page 99 of van Dalen, for practice.

9. ⋆ An old song goes, “Everybody loves my baby, but my baby don’t love nobody but me.” Prove that if this is true, I am my baby.

More precisely: Let L(x, y) stand for “x loves y,” let b be a constant denoting “my baby,” and m be a constant denoting me. From assumptions ∀x L(x, b) and ∀x (L(b, x) → x = m), prove b = m.

10. ⋆ Do problem 1 on page 103. Here, I_{2} is the axiom

∀x ∀y (x = y → y = x)

and I_{3} is the axiom

∀x ∀y ∀z (x = y ∧ y = z → x = z).

Do not use the equality rules! The point of the exercise is to show that you can replace the three basic axioms of equality (reflexivity, symmetry, and transitivity) by two axioms.

11. Do problem 3 on page 103.

12. Do other problems on page 103 for practice.

13. ⋆ Assuming φ is any formula, prove φ ∨ ¬φ, using the ∨-rules on page 50 in van Dalen. (Hint: use a proof by contradiction.)