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
2. 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)
3. 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)
4. 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)
5. 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)
6. 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
7. 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)