Chapter Review 153
(b) Find a formula equivalent to
if a
then
if b then c else d
else
if e then d else c
in CNF.
(c) Find a formula equivalent to -'a using only the if-then-else connective and con-
stants T and F.
(d) Find a formula equivalent to (a V b V c) A (-a v -,b v d) A (-c V -d) using
only the if-then-else connective and constants T and F.
4. Find a DNF for the condition that there are an even number of l's in the three binary
strings p, q, and r. Draw a combinatorial network to represent the DNF. Can you
simplify the combinatorial circuit using the properties of a boolean algebra?
5. Find a DNF for the condition that there are an odd number of l's in the three binary
strings p, q, and r. Draw a combinatorial network to represent the disjunctive normal
form. Can you simplify the combinatorial circuit using the properties of a boolean
algebra?
- An especially simple class of CNF formulas are those built from Horn clauses. A
Horn clause is a clause containing, at most, one positive literal. (A pure Horn clause
is a clause containing exactly one positive literal.) Horn clauses form the basis for the
computer language Prolog, which allows the programmer to input a set of requirements
(specified in formal logic) and to ask the computer to find how to satisfy them all (if
possible)-as opposed to the user's having to write out the case analysis.
(a) Using the atomic formulas
a = "Tweety is a penguin."
b = "Opus is a penguin."
c = "Phoenix is a penguin."
d = "Elvis lives!"
express "If Tweety is a penguin and Opus is a penguin, and Phoenix is a penguin,
then Elvis lives" as a Horn clause.
(b) Find a set of Horn clauses logically equivalent to (a A b A c -+ d v e) A (-a v
-e). Find the shortest such set of clauses.
(c) Find all satisfying truth assignments for the following set of Horn clauses:
{PI, -PI V P2, -Pi V -1'P2 V P3, -'P V -1P2 V P4, -P3 V -174 V P51
Now, show that the following set of Horn clauses is not satisfiable:
{Pl, -'p1 V P2, -'p1 V -P2 V P3, -P V -'p2 V P4, -P3 V -P4 V P5, -113 V -"p5}
(d) Find all satisfying truth assignments for the following set of Horn clauses:
{PI, - P1 V P2, -PI V -P2 V P3, -PI V -1P2 V P4, -P3 V -'P4 V P5,
- P6 V P7, -P1 V -PP7 V P6)
