In Sept. 22's class, we sorta-proved that for any set of sentences Γ and any sentence S, if there's a proof of S from premises Γ, then S is a tautological consequence of Γ. There were actually eleven cases, of which we did five or six. Complete the ∨-elimination case, the last rule in the handout. That is, assume that you have a shortest possible proof in our proof system whose conclusion is not a tautological consequence of its premises, and that the last step in this proof is ∨-elimination. Show that this is impossible.
Consider the class of wffs whose only operator is ↔. Make up several examples and write down their truth tables. Find a property that all such Boolean functions have, and prove (by induction on the size of the wff) that they all have it. Then find a Boolean function (presumably using connectives other than ↔) that doesn't have this property. You have now proven that ↔ alone is not sufficient to express all Boolean functions.
Do problem 1.5.1 on p. 52: find a wff using only ∨, ∧, and ¬ that has the specified truth table. Then find such a wff with only five occurrences of connectives.
Do problem 1.5.9 on p. 53: find a wff in conjunctive normal form equivalent to the specified wff. Then prove that every wff has an equivalent conjunctive normal form (we already proved this for disjunctive normal form).
Do problems 1.6.2 and 1.6.3 on p. 59: find the prime implicants of a formula, and identify which disjunctions of prime implicants would be equivalent to that formula (as opposed to just implying it). Hint: The technique of Example 4 will help.
Construct a Boolean circuit (using 1-input ¬ gates and 2-input ∧ and ∨ gates) with two inputs X and Y, and two outputs Z1 and Z0, such that Z1Z0, interpreted as a two-bit binary number, is the sum of the one-bit binary numbers X and Y. Test your circuit on paper by trying all four possible combinations of X and Y values.
Then build a similar circuit to add two 2-bit binary numbers X1X0 and Y1Y0 , producing the three-bit binary number Z2Z1Z0. Test your circuit on paper by trying a good selection of the possible combinations of X and Y values (not all sixteen).
What are the size (number of gates) and depth or delay of your circuits?
Predict the size and depth of a circuit to add two 3-bit numbers. How about 4-bit numbers? n-bit numbers?
Extra credit: Suppose you had unbounded-input ∧ and ∨ gates: that is, you could AND or OR together as many bits as you wanted, counting it as only one gate and one unit of delay. How much can you improve on the size and depth of the circuits in problem 6 above?
Do problem 1.7.1 on p. 65: prove that if Σ is finitely satisfiable and α is a wff, then either Σ ∪ {α} or Σ ∪ {(¬α)} is finitely satisfiable.
Do problem 1.7.2 on p. 65: suppose Δ is finitely satisfiable and, for every wff, contains either it or its negation. Define a truth assignment by assigning T to exactly those sentence symbols that are in Δ, and extend this truth assignment to all wffs in the usual way. Prove that the extended truth assignment assigns T to exactly those wffs that are in Δ.
Do problem 1.7.4 on p. 65: by using the theorem that every finite planar map can be colored with only four colors, prove that every infinite planar map can also be colored with only four colors.
Prove that if a set S is decidable, then so is its complement. (This is easy, but worth pointing out.)
Do problem 1.7.8 on p. 66: prove that a set [of expressions] is decidable if and only if both it and its complement are effectively enumerable.
Hint: I would ignore the "of expressions"; this should apply to any set.
Another hint: One direction of the "if and only if" is outlined in the paragraph just before Theorem 17F, starting with "Clearly". The other direction takes more work.
Do problem 1.7.11 on p. 66: given algorithms to effectively enumerate sets V and W, build an algorithm to effectively enumerate the set V ∪ W, and another algorithm to effectively enumerate the set V ∩ W.
Do problem 1.7.12 on p. 66: find an unsatisfiable set of wffs such that all its subsets of a particular size are satisfiable. (Compactness would say that if all its finite subsets are satisfiable, it must be satisfiable.)