Information Technology Reference
In-Depth Information
Table 4.8 Continued.
Rule
Rule Table
NAND Solution (K-expression)
Size
97
01100001
FaFabFaaab
10
99
01100011
Faab
4
101
01100101
Faba
4
103
01100111
Faab
4
107
01101011
Fbba
4
109
01101101
Fbab
4
111
01101111
Fbba
4
115
01110011
Fbba
4
117
01110101
Faba
4
119
01110111
Fbba
4
121
01111001
Fbaa
4
123
01111011
Fbba
4
125
01111101
Fabb
4
127
01111111
Fbba
4
While building this list, I found it surprising not finding functions such as the
widely used 3-multiplexer (MUX) (rule 172) and IF functions (if a = 1, then b ,
else c ) (rule 202) among them. I later found out that, despite being ULMs,
these functions are not NLMs: indeed, the MUX function can form a univer-
sal system with {MUX, NOT} and {MUX, 0, 1} and, therefore, is by defini-
tion a ULM; and the IF function can form a universal system with {IF, NOT}
and {IF, 0, 1} and, therefore, is also a ULM.
These functions, the MUX and the IF functions, are two of the functions
of three arguments that we are going to use as examples to design the most
parsimonious representations using five different universal logical systems.
But we will also use other functions of three arguments as examples: the
already familiar majority function (rule 232) and the closely related minority
function (rule 23); the more challenging even-parity (rule 105) and odd-par-
ity (rule 150) functions; and four interesting NLMs: rule 39 ( a ' b ' + b ' c ), rule
27 ( a ' + b ') · ( b ' + c ), rule 115 (If a < b , then ( a · c ), else ( b · c )'), and rule 103
(If a > b , then ( a · c ), else ( b · c )'). The majority and minority functions were
chosen not only because of their simplicity but also because they are ULMs
forming the following universal systems {MAJ, NOT, 0}, {MAJ, NOT, 1},
{MIN, 0}, and {MIN, 1}. The even-parity and odd-parity functions were
chosen because they are hard to describe using most conventional universal
systems such as the {NOT, AND, OR}, the {NAND}, or {NOR} systems
(obviously it is elementary to describe these functions using the Reed-Muller
system of NOTs, ANDs, and XORs).
 
Search WWH ::




Custom Search