Information Technology Reference
In-Depth Information
Also as an illustration, we are also going to find the most parsimonious
representations to all the interesting functions of two arguments (that is, AND,
OR, NAND, NOR, LT, GT, LOE, GOE, XOR, and NXOR) for all the five
universal systems chosen for this exercise: the classical Boolean system
{AND, OR, NOT}, the {NAND} system, the {NOR} system, the Reed-Muller
system {AND, XOR, NOT}, and the {MUX, 0, 1} system.
Boolean Logic
The Boolean universal system of {AND, OR, NOT} is the most popular of
all universal systems and most of logic is based on it. There is nothing magi-
cal about this system, though, and the reason for its popularity and wide-
spread use is the fact that it reflects our way of thinking: we can easily follow
an argument described in terms of ANDs, ORs, and NOTs, but will have
some difficulty following an argument described in terms of LTs and NOTs
or even NANDs or NORs. Notwithstanding, this system is fairly compact as
you can see by the sizes of the evolved solutions presented in Table 4.9.
The parsimonious solutions presented in Table 4.9 were discovered using
small populations of 30 individuals. And in all cases, chromosomes com-
posed of just one gene were used so that no constraints whatsoever are im-
posed on the architecture of the solutions.
For all the two-input functions, a head length of 10 was used, correspond-
ing to maximum program length of 21 nodes, more than sufficient to realize
all the functions of two arguments using ANDs, ORs, and NOTs. The fitness
was evaluated by equation (3.8) prior to the discovery of a perfect solution,
and after that by equation (4.21) in order to design more parsimonious con-
figurations. And by letting the system run for a total of 20,000 generations it
was ensured that the most parsimonious solution was indeed found.
For all the three-input functions, a larger head length of 20 was chosen
(corresponding to maximum program length of 41) in order to cover for all
kinds of functions, and a little more time (100,000 generations) was given
for finding and pruning the perfect solutions.
By comparing the five universal systems in terms of compactness (see
Tables 4.9 - 4.12), it is worth pointing out that, for the two-input functions,
the {AND, OR, NOT} system is slightly less compact than the Reed-Muller
system {AND, XOR, NOT} (46 against 43 total nodes) and also less com-
pact in the three-input functions, even after removing the even- and odd-
parity functions, giving a total of 71 nodes for the classical Boolean system
and 69 for the Reed-Muller system.
