2. Boolean circuits 19
(negation, disjunction, conjunction). Here are the value tables for these
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
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,
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
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
Previous Page Next Page