MATH 1090.03D Fall 2000

Date: Sep. 20, 2000 Due: Sep. 27, 2000—▶At the beginning of class◀ Problem Set No. 1—On Chapter 2 of “GS”.

NOTE. Whenever needed, BE-operator precedences must be as given in class. In particular, all associativities are right.

(0) Suppose that, for some given formula A, you want to find out whether or not ¬A ∨ A is a tautology, and you are going to use a truth table. Suppose that A has 11 Boolean variables. How many rows will your truth table have? Why?

(1) In each row below compare all formulas for pairwise tautological equivalence: ((p ∨ q) ∨ r), (p ∨ (q ∨ r))

((p ∧ q) ∧ r), (p ∧ (q ∧ r))

(((p ≡ q) ≡ r) ≡ p′), (p ≡ (q ≡ (r ≡ p′))), ((p ≡ (q ≡ r)) ≡ p′), (p ≡ ((q ≡ r) ≡ p′))

(2) (Meta)prove that a formula A is a tautology iff ¬A is unsatisfiable (a contradiction). NOTE. Recall that “iff” means that there are two directions to do.

(3) (Meta)prove that for any two formulas P and Q, ⊧ (((P ⇒ Q) ⇒ P) ⇒ P).

(4) Express the following Boolean expression A(p, q, r)—given by a truth table—in each of:

(i) Conjunctive Normal Form, and (ii) Disjunctive Normal Form. NOTE. You may use “engineering notation”, if you wish.

\begin{matrix}p & q & r & A(p, q, r) \\ t & t & t & f \\ t & t & f & f \\ t & f & t & f \\ t & f & f & f \\ f & t & t & f \\ f & t & f & t \\ f & f & t & t \\ f & f & f & f \end{matrix}

(5) (Meta)prove that for any formulas A, B, C and D, A, B, C ⊧ D iff ⊧ A ⇒ B ⇒ C ⇒ D