2. Boolean circuits 19

(negation, disjunction, conjunction). Here are the value tables for these

functions:

x ¬x x1 x2 x1 ∨ x2 x1 x2 x1 ∧ x2

0 1 0 0 0 0 0 0

1 0 0 1 1 0 1 0

1 0 1 1 0 0

1 1 1 1 1 1

Theorem 2.1. The basis {NOT, OR, AND} = {¬, ∨, ∧} is complete.

Proof. Any Boolean function of n arguments is determined by its value

table, which contains

2n

rows. Each row contains the values of the arguments

and the corresponding value of the function.

If the function takes value 1 only once, it can be computed by a conjunc-

tion of literals; each literal is either a variable or the negation of a variable.

For example, if f(x1,x2,x3) is true (equals 1) only for x1 = 1,x2 = 0,x3 = 1,

then

f(x1,x2,x3) = x1 ∧ ¬x2 ∧ x3

(the conjunction is associative, so we omit parentheses; the order of literals

is also unimportant).

In the general case, a function f can be represented in the form

f(x) =

{u: f(u)=1}

χu(x), (2.1)

where u = (u1,...,un), and χu is the function such that χu(x) = 1 if x = u,

and χu(x) = 0 otherwise.

A representation of type (2.1) is called a disjunctive normal form (DNF).

By definition, a DNF is a disjunction of conjunctions of literals. Later

we will also need the conjunctive normal form (CNF) — a conjunction of

disjunctions of literals. Any Boolean function can be represented by a CNF.

This fact is dual to Theorem 2.1 and can be proved in a dual way (we start

with functions that have only one zero in the table). Or we can represent

¬f by a DNF and then get a CNF for f by negation using De Morgan’s

identities

x ∧ y = ¬(¬x ∨ ¬y), x ∨ y = ¬(¬x ∧ ¬y).

These identities show that the basis {¬, ∨, ∧} is redundant: the subsets

{¬, ∨} and {¬, ∧} also constitute complete bases. Another useful example

of a complete basis is {∧, ⊕}.

The number of assignments in a circuit is called its size. The minimal

size of a circuit over A that computes a given function f is called the circuit

http://dx.doi.org/10.1090/gsm/047/04