Adequate Connectives in Nonbinary Logic

A functionally complete set of logical connectives of Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean (binary) expression. See for instance the article in Wikipedia. The single elements of {NAND} and {NOR} functions are functionally complete and are the adequate connectives.

The NAND can be formed from {NOT, AND}. The set {NOT, AND} is thus also a set of adequate connectives from which all binary functions can be formed. The NOT is a binary inverter which can be expressed as [0 1] → [1 0]. In words, a state 0 is inverted to state 1 and state 1 is inverted to state 0.

While commonly only [0 1] → [1 0] is mentioned as a binary inverter, there are in fact 4 binary inverters:
i1: [0 1] → [1 0], the standard inverter.
i2: [0 1] → [0 1], the identity.
i3: [0 1] → [0 0], the always 'off' inverter.
i4: [0 1] → [1 1], the always 'on' inverter.

Under a new definition a set of adequate connectives is {i1, i2, i3, i4, BIN} or a set consisting of at least one of the 4 binary inverters and one binary two input/single output function.

What are then the sets of adequate connectives? Well there are 8 of them, for sets of inverters with one of 8 qualifying BIN functions. What are those qualifying BIN functions? The qualifying functions BIN have and odd number of 0s (and thus of 1s). See in the following diagram.

The above configuration is the universal representation for the binary adequate connective. A single function BIN is unable to generate all 16 functions. A set of Matlab/Freemat programs can be found here that evaluate all 16 binary functions BIN. Download and extract the programs into a single folder and run 'makebinfun' under Matlab or Freemat.

The ternary or 3-state universal connective

One can find similar universal adequate connectives in 3-state or any n-state switching machine logic. In the ternary case there are 27 3-state inverters, of which some are listed below:
[0 1 2]→[0 0 0];
[0 1 2]→[0 0 1];
[0 1 2]→[0 2 1];
[0 1 2]→[2 1 0];

The following figure illustrates one possible universal 3-state adequate connective under the new definition.

The above configuration using TER and the 3-state inverters is able to generate all 19,683 3-state or ternary 2-input/single output functions.

Copyright 2013 Peter Lablans. All rights reserved.