![\"\"](\"https:\/\/learning.oreilly.com\/api\/v2\/epubs\/urn:orm:book:9781482238129\/files\/bg86.png\")
<\/p>\n\n\n\nIt is well known that AND, NOT and OR form a universal set of gates.<\/p>\n\n\n\n
Consider for example the case n = 1. We have four distinct functions imple-<\/p>\n\n\n\n
mented as in Table 6.2.<\/p>\n\n\n\n
TABLE 6.2: The four 1-bit functions.<\/p>\n\n\n\n
Function Action Form Gate<\/p>\n\n\n\n
f<\/p>\n\n\n\n
1<\/p>\n\n\n\n
: 0 \u2192 0<\/p>\n\n\n\n
1 \u2192 0 f(x) = x \u2227 0 AND<\/p>\n\n\n\n
f<\/p>\n\n\n\n
2<\/p>\n\n\n\n
: 0 \u2192 0<\/p>\n\n\n\n
1 \u2192 1 f (x) = x Identity<\/p>\n\n\n\n
f<\/p>\n\n\n\n
3<\/p>\n\n\n\n
: 0 \u2192 1<\/p>\n\n\n\n
1 \u2192 0 f (x) = \u00afx NOT<\/p>\n\n\n\n
f<\/p>\n\n\n\n
4<\/p>\n\n\n\n
: 0 \u2192 1<\/p>\n\n\n\n
1 \u2192 1 f(x) = x \u2228 1 OR<\/p>\n\n\n\n
For n > 1, the functions fall into two classes: those giving output 0 and<\/p>\n\n\n\n
those giving output 1. Suppose for a given function that the output is 1 for<\/p>\n\n\n\n
the set of inputs {x<\/p>\n\n\n\n
a<\/p>\n\n\n\n
}. The function can then be constructed in terms of what<\/p>\n\n\n\n
are called the minterms of f , de\ufb01ned as:<\/p>\n\n\n\n
f<\/p>\n\n\n\n
a<\/p>\n\n\n\n
(x) =<\/p>\n\n\n\n
(<\/p>\n\n\n\n
1, x \u2208 {x<\/p>\n\n\n\n
a<\/p>\n\n\n\n
}<\/p>\n\n\n\n
0 otherwise.<\/p>\n\n\n\n
(6.8)<\/p>\n\n\n\n
The minterms are easily constructed from the bits in the input by the product<\/p>\n\n\n\n
(AND) of the bits or their complements. For instance, say x<\/p>\n\n\n\n
k<\/p>\n\n\n\n
= 10110 \u2208 {x<\/p>\n\n\n\n
a<\/p>\n\n\n\n
}.<\/p>\n\n\n\n
Then<\/p>\n\n\n\n
f<\/p>\n\n\n\n
k<\/p>\n\n\n\n
(x) = x<\/p>\n\n\n\n
5<\/p>\n\n\n\n
\u2227 \u00afx<\/p>\n\n\n\n
4<\/p>\n\n\n\n
\u2227 x<\/p>\n\n\n\n
3<\/p>\n\n\n\n
\u2227 x<\/p>\n\n\n\n
2<\/p>\n\n\n\n
\u2227 \u00afx<\/p>\n\n\n\n
1<\/p>\n\n\n\n
. (6.9)<\/p>\n\n\n\n
We can then construct f (x) as the sum (OR), of the minterms. Then we have<\/p>\n\n\n\n
the so-called disjunctive normal form of f (x):<\/p>\n\n\n\n
f(x) = f<\/p>\n\n\n\n
1<\/p>\n\n\n\n
(x) \u2228 f<\/p>\n\n\n\n
2<\/p>\n\n\n\n
(x) \u2228 . . . (6.10)<\/p>\n\n\n\n
Thus we need OR, AND, and NOT operations to construct this function.<\/p>\n\n\n\n
Since we will need more than one copy of the bits in the input to construct<\/p>\n\n\n\n
the minterms, we require COPY as well.<\/p>\n\n\n\n
There is an alternative inductive proof for this. Assume that we have a<\/p>\n\n\n\n
circuit built only of AND, NOT, and OR gates to construct f (x) for some<\/p>\n\n\n\n
n. Then to construct an n + 1 \u2192 1 function, we de\ufb01ne two n \u2192 1 functions,<\/p>\n\n\n\n
<\/p>\n\n\n\n
Computation Models and Computational Complexity 109<\/p>\n\n\n\n
whose values are given by the output of f(x), as the (n + 1)<\/p>\n\n\n\n
th<\/p>\n\n\n\n
bit is set to 0<\/p>\n\n\n\n
or 1:<\/p>\n\n\n\n
f<\/p>\n\n\n\n
0<\/p>\n\n\n\n
(x<\/p>\n\n\n\n
n<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
. . . x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
) = f<\/p>\n\n\n\n
n+1<\/p>\n\n\n\n
(0x<\/p>\n\n\n\n
n<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
. . . x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
), (6.11a)<\/p>\n\n\n\n
f<\/p>\n\n\n\n
1<\/p>\n\n\n\n
(x<\/p>\n\n\n\n
n<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
. . . x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
) = f<\/p>\n\n\n\n
n+1<\/p>\n\n\n\n
(1x<\/p>\n\n\n\n
n<\/p>\n\n\n\n
x<\/p>\n\n\n\n
n\u22121<\/p>\n\n\n\n
. . . x<\/p>\n\n\n\n
1<\/p>\n\n\n\n
). (6.11b)<\/p>\n\n\n\n
Then,<\/p>\n\n\n\n
f(x) = (f<\/p>\n\n\n\n
0<\/p>\n\n\n\n
\u2227 \u00afx<\/p>\n\n\n\n
n+1<\/p>\n\n\n\n
) \u2295 (f<\/p>\n\n\n\n
1<\/p>\n\n\n\n
\u2227 x<\/p>\n\n\n\n
n+1<\/p>\n\n\n\n
). (6.12)<\/p>\n\n\n\n
Thus f<\/p>\n\n\n\n
n+1<\/p>\n\n\n\n
can be implemented by the circuit of Figure 6.2.<\/p>\n\n\n\n
FIGURE 6.2: Classical circuit for function evaluation<\/p>\n","protected":false},"excerpt":{"rendered":"
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 \u2192 0 1 \u2192 0 f(x) = […]<\/p>\n","protected":false},"author":1,"featured_media":4040,"comment_status":"open","ping_status":"open","sticky":false,"template":"","format":"standard","meta":{"footnotes":""},"categories":[495],"tags":[],"class_list":["post-4052","post","type-post","status-publish","format-standard","has-post-thumbnail","hentry","category-computation-models-and-computational-complexity"],"jetpack_featured_media_url":"https:\/\/workhouse.sweetdishy.com\/wp-content\/uploads\/2024\/09\/download-1.png","_links":{"self":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4052","targetHints":{"allow":["GET"]}}],"collection":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/users\/1"}],"replies":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/comments?post=4052"}],"version-history":[{"count":1,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4052\/revisions"}],"predecessor-version":[{"id":4053,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/posts\/4052\/revisions\/4053"}],"wp:featuredmedia":[{"embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media\/4040"}],"wp:attachment":[{"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/media?parent=4052"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/categories?post=4052"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/workhouse.sweetdishy.com\/index.php\/wp-json\/wp\/v2\/tags?post=4052"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}