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
Previous Page Next Page