Discrete Mathematics for Computer Science

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 stan-

dard way for manipulation of propositional formulas in computer programs. For ex-

ample, 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 -.