152
CHAPTER 2 Formal Logic
(b) Find a formula equivalent to a -* (b A C A d) using only the connectives NAND
(and not the constants TRUE and FALSE). Find the shortest such formula; does
it have more or fewer symbols than the formula a -- + (b A C A d)?
(c) NOR has the truth table
p q
NOR(p, q)
T T
F
T F
F
F T
F
F F
T
Show that the set {NOR} of operators is complete.
(d) Find a formula equivalent to a -+ (b A C A d) using only the connectives NOR
(and not the constants TRUE and FALSE). Find the shortest such formula; does
it have more or fewer symbols than the formula a -- + (b A C A d)?
The NAND operator is often called the Sheffer stroke and is denoted as plq.
The NOR operator is often called the Pierce arrow and is denoted as p 4 q.
3. The connective if-then-else is defined by the following truth table:
p q r ifp thenq else r
T T T
T
T T F
T
T F T
F
T F F
F
F T T
T
F T F
F
F F T
T
F F F
F
This connective is key in binary decision diagrams (BDDs), which provide one standard way for manipulation of propositional formulas in computer programs. For example, BDDs have been widely used by computer-chip designers in showing that the
circuits in the chips they design match the specifications for those chips. (In BDD
language, the connective is often called just ITE.)
(a) Find a formula equivalent to
if a
then
if b then c else d
else
if e then d else c
using only the connective A, v, and -.