The Basic GEA in Problem Solving - Gene Expression Programming - page 152

system, for instance, with ANDs and NOTs plus another function, say XOR,
it will also be a universal logical system. In fact, such system does exist - the
Reed-Muller system - as it seems to be advantageous in the design of certain
logical circuits.
But perhaps the most important is understanding and exploring the most
compact universal logical systems, that is, universal logical systems com-
posed of just one basic function (say, any function of two or three argu-
ments) plus any combination of the simple units {NOT, 0, 1}. This is, in fact,
what constitutes what is called a universal logical module (ULM). Thus, for
the sixteen functions of two arguments there are four well studied ULMs:
{AND, NOT}, {OR, NOT}, {NAND}, and {NOR}. But there are also other
less studied ULMs among the functions of two arguments: the systems {LT,
NOT}, {GT, NOT}, {LOE, NOT}, and {GOE, NOT}. These systems are
very interesting because they tell us something very important about the
{NAND} and {NOR} systems: they are what they are (ULMs composed of
just one unit), not because they are the inversion of AND or OR, both of
them ULMs themselves, as this is no recipe for creating another ULM. In
fact, by inverting LT one gets GOE and vice versa; and GT is the negation of
LOE and vice versa. And neither of these functions are universal logical
modules like NAND or NOR. Furthermore, besides the ones described above,
among the functions of two arguments no more ULMs can be found or, more
specifically, neither XOR nor NXOR are ULMs, and not even the combina-
tion of both these functions with the simple units {NOT, 0, 1} forms a uni-
versal logical system.
There is another concept I would like to introduce before starting to use
all these interesting universal systems: the concept of a NAND/NOR-like
module (NLM). The {NAND} and {NOR} systems are special in the sense
that they do not require any other element (be it an inverter, 0, or 1) to de-
scribe any other logical function. And although they are certainly unique
among the 16 functions of two arguments, there are lots of other functions
with these same properties and it is important to have a name for them. For
instance, among the 256 functions of three arguments there are a total of 56
NLMs, all of them listed in Table 4.8. Also shown are the parsimonious
solutions to the NAND function designed with each one of these NLMs. For
simplicity, the character “F” is used to represent all the NLMs in the K-
expressions. The numbering scheme used for identifying the rules is the same
proposed by Wolfram (1983) for naming the logical functions with three
arguments in connection with one-dimensional cellular automata.