Alternate History

Functional completeness (Caroline Era)

41,126pages on
this wiki
Add New Page
Talk0 Share

Note: The understanding of this topic in the Gordon timelines is considerably more advanced than it is in the Caroline. Wikipedia has an article on it here.

Functional completeness, also known as expressive adequacy, is the ability for a set of logical operators to produce all possible truth tables if appropriately connected. In the context of digital electronics, it can be seen as the minimum number of sets of logic gates needed to achieve all possible binary signals.

Minimal sets of functionally complete operators

In Boolean algebra, there are no known sets of functionally complete operators with fewer than three members, and no known minimal functionally complete sets with more than three. The following sets are known:

{ AND, EQUIV, contradiction }


{ AND, NOT.EQUIV, tautology }

{ OR, EQUIV, contradiction }


{ OR, NOT.EQUIV, tautology }

Applications to digital electronics

Digital circuits, in order to be fully functional, must use at least three types of logic gates, though other logic functions can be constructed using a subset. Moreover, each of the following logic gates:

AND, EQUIV, contradiction, tautology, NOT.EQUIV, OR

can only be built from components which cannot perform logical functions themselves and cannot be combined in other ways. This means that each logic gate of these six types has never been designed from a set of other logic gates. This imposes a minimum size for digital circuits relative to the sizes of the basic components from which they are made.

Applications to programming

Conditional expressions can be quite long and complex, take longer to compile, interpret and execute, and can contain bugs which are difficult to detect. Software can therefore be slightly slower and take longer to develop. Also, the use of the arithmetic IF in FORTRAN means that expressions have to be converted to a form which yields a negative, zero or positive results, so they tend to be longer.

However, other factors compensate for these drawbacks and software is generally faster and more memory-efficient than in the Gordon timelines.

Expressive adequacy

(This is included here due to knowledge available in the Gordon Timelines)

There is a similar concept in Western philosophy known as expressive adequacy. It has been found that all logical connectives can be defined in terms of sets of two and one logical operators, and that at a minimum, only one logical operator is needed. These are either NAND or NOR.

However, since philosophy does not have a good reputation among scientists, mathematicians and engineers, this fact has neither been discovered or transferred to these disciplines and it is entirely unknown to them.

See also


Posterior Analytics

Ad blocker interference detected!

Wikia is a free-to-use site that makes money from advertising. We have a modified experience for viewers using ad blockers

Wikia is not accessible if you’ve made further modifications. Remove the custom ad blocker rule(s) and the page will load as expected.

Also on Fandom

Random Wiki