80-310/610 Logic and Computation Fall 2001

Homework #6

Due Wednesday, October 3

1. Read Section 1.4 in van Dalen, and start reading Section 1.5.

2. ⋆ Use our semantic definitions to prove or find a counterexample to each of the following:

a. For every set of formulas Γ, every formula φ, and every formula ψ, if

Γ ⊧ φ ∧ ψ, then Γ ⊧ φ and Γ ⊧ ψ. b. For every set of formulas Γ, every formula φ, and every formula ψ, if

Γ ⊧ φ ∨ ψ, then Γ ⊧ φ or Γ ⊧ ψ.

3. ⋆ Do problems 4 and 5 on page 28 of van Dalen. In other words, if φ | ψ, read “φ nand ψ,” means that φ and ψ are not both true, and φ ↓ ψ, read “φ nor ψ,” means that neither φ nor ψ is true, show that {|} and {↓} are complete sets of connectives.

4. Do problem 6 on page 28. In other words, show that these are the only two binary connectives that have this property.

5. Show that {→, ⊥} is a complete set of connectives.

6. ⋆

a. Show that {→, ∨, ∧} is not a complete set of connectives. (Hint: show that any formula involving only these connectives is true when all the variables are true.)

b. Conclude that {→, ∨, ∧, ↔, ⊤} is not a complete set of connectives. (Hint: define the last two in terms of the others.)

7. a. Show that {⊥, ↔} is not a complete set of connectives. (Hint: show that any formula involving only these connectives and the variables p_{0} and p_{1} is equivalent to one of the following: ⊥, ⊤, p_{0}, p_{1}, ¬p_{0}, ¬p_{1}, p_{0} ↔ p_{1}, or p_{0} ⊕ p_{1}.)

b. Conclude that {⊥, ⊤, ¬, ↔, ⊕} is not complete. (Hint: see the previous problem.)

8. ∘ How many ternary (3-ary) complete connectives are there?

9. ∘ Do problem 7 on page 28.

10. ⋆ Do problem 8 on page 28. (Hint: it might help to read problem 7.)

11. Make up a truth table for a ternary connective, and then find a formula that represents it.

12. Do problems 9 and 10 on page 28.

13. Using the property φ∨(ψ∧θ) ≈ (φ∨ψ)∧(φ∨θ), and the dual statement with ∧ and ∨ switched, put

(p_{1} ∧ p_{2}) ∨ (q_{1} ∧ q_{2}) ∨ (r_{1} ∧ r_{2})

in conjunctive normal form. (Hint: try it with (p_{1} ∧ p_{2}) ∨ (q_{1} ∧ q_{2}) first.)

14. ⋆ Do problem 1 on page 39 of van Dalen. Remember that we are taking φ ↔ ψ to abbreviate (φ → ψ) ∧ (ψ → φ).

Note that a parenthesis is missing at the end of part (f). The ← directions of parts (d) and (e) are a little tricky, because they require the classical rule RAA.

15. Do problem 2 on page 39.

There is a parenthesis missing in part (b); it should read [φ → (ψ → σ)] ↔ [ψ → (φ → σ)]. Here the square brackets are only used to make the formula more readable; they are no different from parentheses.