12.2 Representing Boolean Functions

Question 1

Literals

Answer 1

A literal is a Boolean variable or its complement.

Question 2

Minterm

Answer 2

Hence, a minterm is a product of n literals, with one literal for each variable.

Question 3

Disjunctive Normal Form (DNF)

Answer 3

The disjunctive normal form (DNF) of a degree-n Boolean function f is the unique sum of minterms
of the variables x1, . . . , xn that represents f.

Question 4

Maxterm

Answer 4

A maxterm of the Boolean variables x1, x2, . . . , xn is a Boolean sum y1 + y2 + . . . + yn, where
yi = xi or yi = ¯xi
. Hence, a maxterm is a sum of n literals, with one literal for each variable.

Question 5

Maxterm

Answer 5

Hence, a maxterm is a sum of n literals, with one literal for each variable.

Question 6

Maxterm

Answer 6

Hence, a maxterm is a sum of n literals, with one literal for each variable.

Question 7

Conjunctive Normal Form (CNF)

Answer 7

The conjunctive normal form (CNF) of a degree-n Boolean function f is the unique product of
maxterms of the variables x1, . . . , xn that represents f.

Question 8

Functional Completeness

Answer 8

Functional Completeness
Since every Boolean function can be expressed in terms of ·, +,¯, we say that the set of operators
{·, +,¯} is functionally complete.