132 CHAPTER 2 Formal Logic
(e) p q r s Truth Value (f) p q r s Truth Value
T T T T F T T T F T
T T F T T T T F F F
T F T F T T F F F T
F T F T F F T T F T
F T F F T F T F T F
F F T F F F F T F F
F F F F F- Find formulas in DNF equivalent to each of the following formulas:
(a) -(p A T)
(b) ((p - q) -+ r) - F
(c) ((p q) r)- T
(d) (p q) +-). r
(e) --(p <+- q) +-* r
(f) ((p v q) --> r) A (r -- '(p v q))
(g) (-,r) -- (((p v q) --+ r) -+ -q)
- Which of the following DNF formulas are satisfiable? If the formula is satisfiable, give
an interpretation that satisfies it. If it is not satisfiable, explain why not.
(a) (aAbAc)v(cA-,cAb)
(b) (aAbAcAdA-,b)V(cAdA-.CAeAf)
(c) (aAbAc)V(-aA-,bA-,c)
- Find formulas in DNF equivalent to each of the following formulas, and find at least
two interpretations that make each formula satisfiable:
(a) ((p -- q) -- r) -+ F
(b) -- (p -- q) + r
(c) (-"r) -+ (((p v q) - r) -- -q) - Find formulas in CNF equivalent to each of the following formulas:
(a) -(p A T)
(b) ((p -- q) -- r) - F
(c) ((p q) r)- T
(d) (p -q) +-+ r
(e) --(p +-+ q) +-+ r
(f) ((p v q) --+ r) A (r -- (p v q))
(g) (-r) - (((p v q) -+ r) -* -q) - For the following formulas find equivalent formulas in CNF and DNF form. Draw
combinatorial networks corresponding to the original formulas and their equivalent
CNF forms.
(a) (pAq) +* (pAr)
(b) ((p - q) -+ r) -- p - Which of the following formulas in CNF are tautologies? Explain, as in Example 6.
(a) (avbVc)A(cv--cvb)
(b) (avbvcvdv-'b)A(cvdv-'cvevf)
(c) (avbvc)A(-'aV-bv-c)