It is well known that AND, NOT and OR form a universal set of gates.
Consider for example the case n = 1. We have four distinct functions imple-
mented as in Table 6.2.
TABLE 6.2: The four 1-bit functions.
Function Action Form Gate
f
1
: 0 → 0
1 → 0 f(x) = x ∧ 0 AND
f
2
: 0 → 0
1 → 1 f (x) = x Identity
f
3
: 0 → 1
1 → 0 f (x) = ¯x NOT
f
4
: 0 → 1
1 → 1 f(x) = x ∨ 1 OR
For n > 1, the functions fall into two classes: those giving output 0 and
those giving output 1. Suppose for a given function that the output is 1 for
the set of inputs {x
a
}. The function can then be constructed in terms of what
are called the minterms of f , defined as:
f
a
(x) =
(
1, x ∈ {x
a
}
0 otherwise.
(6.8)
The minterms are easily constructed from the bits in the input by the product
(AND) of the bits or their complements. For instance, say x
k
= 10110 ∈ {x
a
}.
Then
f
k
(x) = x
5
∧ ¯x
4
∧ x
3
∧ x
2
∧ ¯x
1
. (6.9)
We can then construct f (x) as the sum (OR), of the minterms. Then we have
the so-called disjunctive normal form of f (x):
f(x) = f
1
(x) ∨ f
2
(x) ∨ . . . (6.10)
Thus we need OR, AND, and NOT operations to construct this function.
Since we will need more than one copy of the bits in the input to construct
the minterms, we require COPY as well.
There is an alternative inductive proof for this. Assume that we have a
circuit built only of AND, NOT, and OR gates to construct f (x) for some
n. Then to construct an n + 1 → 1 function, we define two n → 1 functions,
Computation Models and Computational Complexity 109
whose values are given by the output of f(x), as the (n + 1)
th
bit is set to 0
or 1:
f
0
(x
n
x
n−1
. . . x
1
) = f
n+1
(0x
n
x
n−1
. . . x
1
), (6.11a)
f
1
(x
n
x
n−1
. . . x
1
) = f
n+1
(1x
n
x
n−1
. . . x
1
). (6.11b)
Then,
f(x) = (f
0
∧ ¯x
n+1
) ⊕ (f
1
∧ x
n+1
). (6.12)
Thus f
n+1
can be implemented by the circuit of Figure 6.2.
FIGURE 6.2: Classical circuit for function evaluation
Leave a Reply