80-310/610 Logic and Computation Fall 2001

Homework #8

Due Wednesday, October 24

1. Study for the in-class exam on Wednesday, October 17. In particular:

a. Make sure you are comfortable with the definitions and the statements of theorems given in the book and in lectures, as well as proofs I have gone over in class.

b. Review past homework assignments and “unstarred” homework problems.

The exam will cover material discussed in class through Monday, October 15. This homework assignment is due the following Wednesday, but some of the material that it covers will be on the exam, so you may want to do some or all of the starred problems before then.

2. Read through Section 2.4 in Chapter 2 of van Dalen.

3. Say that a set of formulas Γ is finitely satisfiable if every finite subset of Γ is satisfiable. Note that the compactness theorem states

For every set of formulas Γ, if Γ is finitely satisfiable then Γ is satisfiable.

Prove (directly) that if Γ is a finitely satisfiable set of formulas and φ is any formula, then either Γ ∪ φ or Γ ∪ {¬φ} is finitely satisfiable.

4. Do problems 8 and 9 on page 48.

5. Do problem 11 on page 48.

6. ∘ Prove the compactness theorem directly, in a manner similar to the way we proved the completeness theorem in class. (Hint: start with a finitely satisfiable set Γ, and extend it to a maximally finitely satisfiable set Γ′.)

7. ∘ Do problems 2 and 3 on page 54.

8. Using the new proof rules, do problem 5 on page 55 of van Dalen. The backwards direction is tricky. Note that ¬(φ ∨ ψ) implies ¬φ, which in turn implies φ → ψ.

9. ⋆ Do problem 7 on page 55.

10. ∘ Using the proof of Theorem 1.3.8 in van Dalen, describe an algorithm that converts any formula φ to formulas φ^{∨} and φ^{∧}, in disjunctive and conjunctive normal form, respectively.

11. ⋆

a. Say that a formula φ is satisfiable if there is a truth assignment v such that v satisfies φ (in other words, v ⊧ φ, or [[φ]]_{v} = 1). φ is unsatisfiable if it is not satisfiable. Show that for any formula φ, φ is unsatisfiable if and only if ¬φ is valid.

b. Now suppose φ is of the form

φ_{1} ∨ φ_{2} ∨ … ∨ φ_{k}

in disjunctive normal form, so that each formula φ_{i} is a conjunction of atomic formulas and their negations. Show that φ is satisfiable if and only if one of the conjunctions φ_{i} does not contain an atomic formula p_{j} together with its negation ¬p_{j}.

c. Use this, together with the previous problem, to give an algorithm to determine whether or not a formula φ is valid.

12. ∘ This problem outlines a more constructive approach to the following special case of the completeness theorem: if ⊧ φ, then ⊢ φ.

a. Modify the algorithm of problem 5 so that given φ, it outputs not only a formula φ^{∧}, but also a proof of φ ↔ φ^{∧}.

b. Show that if φ^{∧} is valid, it is easy to prove. (The previous problem is relevant.)

13. ∘ If φ is any formula, show that

length(φ^{∨}) ≤ 2^{length(φ)+3}.

(Use the definition of φ^{∨} implicit in Theorem 1.3.9 on page 26.)

14. ∘

a. Assuming φ has length n, what is the worst-case running time of the algorithm in part (c) of the problem 6?

b. Another way to determine if a formula φ is a tautology is to compute its value on every truth assignment (the “truth table” method). What is the worst-case running time of this algorithm? c. Come up with a polynomial-time algorithm for determining if a

propositional formula φ is a tautology or not, or prove that no such algorithm exists. (Note: a successful solution to this problem amounts to settling the famous open question, P = NP?.)

15. Do problem 1 on page 60.

16. ⋆ Consider a first-order language, with relation symbols < and =. The intended interpretation is the natural numbers, with “less-than” and “equality.” Formalize the following statements:

a. “x is less than or equal to y”

b. “0 is the smallest number”

c. “there is a smallest number”

d. “there is no largest number”

e. “every number has an immediate successor” (in other words, for every number, there is another one that is the “next largest”)

17. ⋆ Do problem 4 on page 68. For each one, just indicate whether the term is “free” or “not free,” and carry out the substitution either way.