Information Technology Reference
In-Depth Information
We have seen already that the universal logical systems {MUX, NOT}
and {MUX, 0, 1} are both universal, and for this study we are going to use the
last one as 0's and 1's come very cheaply in digital circuits as they corre-
spond to the ground and power. The parsimonious solutions presented in
Table 4.13 were discovered using the same evolutionary strategies and the
same head sizes used in the previous sections, but here, since we are using a
three-argument function in the function set, the gene sizes are correspond-
ingly larger. Thus, for the two-input functions, a gene size of 31 was used,
whereas for the three-input functions, a gene size of 61 was used. For the
sake of simplicity, in the K-expressions shown in Table 4.13, the MUX func-
tion is represented by the character “M”, and zero and one are represented
respectively by “0” and “1”.
As you can see in Table 4.13, overall, the MUX system is extremely com-
pact, requiring a total of 134 nodes to describe all the 20 functions. Indeed,
Table 4.13
Parsimonious solutions designed with the universal system {MUX, 0, 1}.
Rule Name
Rule #
Rule Table
Parsimonious Solution
Size
AND
8
1000
Mbba
4
OR
14
1110
Maba
4
NAND
7
0111
MM10bba
7
NOR
1
0001
MM10bab
7
LT
2
0010
Mab0
4
GT
4
0100
Mba0
4
LOE
11
1011
Ma1b
4
GOE
13
1101
Mb1a
4
XOR
6
0110
MabMba0
7
NXOR
9
1001
MaMbb1a
7
MUX
172
10101100
Mabc
4
IF
202
11001010
Macb
4
MAJ
232
11101000
MMcbacb
7
MIN
23
00010111
MM10Mbcabc
10
EVEN
105
01101001
MMMbacMb10ca0
13
ODD
150
10010110
MMcMabMc10ba0
13
NLM39
39
00100111
MM10cab
7
NLM27
27
00011011
MM10cba
7
NLM115
115
01110011
Mb1Mca0
7
NLM103
103
01100111
MM10bMccab
10
