Discrete Mathematics for Computer Science

Normal Forms 125

Example 4. Let x, y be elements of a boolean algebra. Use the DNF for the boolean

expression (x A y) V (-x A -'y) to design a combinatorial circuit.

Solution. The boolean expression is in DNF. Therefore, the combinatorial circuit is

y ~

X • "X ý"• A "•y

Y

2.5.3 Conjunctive Normal Form

Consider again the formula used as a motivating example for DNFs:

(p -). (q V r)) ++ (q -- p)

The formula is logically equivalent to the formula

(p V -q) A (-'p V q V r)

This logically equivalent formula is in conjunctive normal form (CNF). It consists of

a conjunction of two formulas that are disjunctions of literals. In this example, it is the

conjunct of (p v --q) and (-,p v q v r). Each disjunction of zero or more literals can be

thought of as a restriction on when the formula can be T. The first restriction is that at least

one of p and -q must be T. The second is that at least one of -'p, q, and r must be T.

This can be thought of as a list of rules that must all be met for the formula to be satisfied.

Thus, CNF formulas are often easy to understand.

Definition 3. Let O 1 , - 2 ..... m be a set of m literals with m E N. A clause is a disjunc-

tion

Xl1VX2 V ... V -m

of m literals. A formula 0 is in CNF if it is a conjunction

01A 02 A'..A Ok

of k clauses 01, 2,.. Ok where k E N.