80-310/610 Logic and Computation Fall 2001

Homework #7

Due Wednesday, October 10

1. Finish reading Section 1.5 in van Dalen. Then read Sections 1.6, 2.1, and 2.2. Note that the midterm exam is in class on Wednesday, October 17.

2. Do problem 3 on page 39 of van Dalen.

3. ⋆ Do problem 4 on page 39. Hints: For 4a, remember that if α and β are any formulas, from β you can conclude α → β. 4b is tricky, because it is not classically valid; you will need to use RAA. Note that from ¬α you can conclude α → β using ex falso (show how).

4. Do problems 5, 7, and 8 on pages 39–40.

5. Do problem 1 on page 47. If you claim the set is inconsistent, show that you can prove a contradiction from those assumptions. If you claim the set is consistent, demonstrate this by providing a valuation under which all the formulas are true. (Note that the completeness theorem implies that if a set of formulas is consistent, there will always be such a valuation.)

6. ⋆ Do problem 2 on page 47.

7. ⋆ Do problem 3 on page 47.

8. ⋆ A formula φ is said to be independent of a set of formulas Γ if Γ ⊬ φ and Γ ⊬ ¬φ. Suppose Γ is a consistent set of formulas, φ is independent of Γ, and ψ is independent of Γ ∪ {φ}. Show that there are at least three different maximally consistent sets containing Γ.

9. Find a consistent set Γ that is not maximally consistent, but has the property that there is only one maximally consistent set containing it. In fact, show that there is a fixed natural number k, such that we can assume that every formula in Γ has length at most k.

10. ∘ Do problem 4 on page 47 of van Dalen.

11. ∘ Do problem 5 on page 48. In effect, you will be describing a computer program that prints out propositional formulas ad infinitum, in such a way that every propositional formula is printed sooner or later.

12. ⋆ Do problem 6 on page 48. Van Dalen’s wording is awkward. What you need to prove is this: Suppose Γ is a consistent set of formulas with the property that for every formula φ, either φ ∈ Γ or ¬φ ∈ Γ. Then Γ is maximally consistent.

13. ⋆ Show that if Γ is any consistent set, and φ is any formula, then either Γ ∪ {φ} or Γ ∪ {¬φ} is consistent. (Hint: suppose they are both inconsistent…)