From WikiChip
functional completeness - Boolean Algebra
< boolean algebra(Redirected from boolean algebra/functionally complete)

Logic function classification
Func Monotone Inc Self-dual Linear 0-preserving 1-preserving
LOW
HIGH
NOT
AND
OR
XOR

A set of logic operations are said to be functionally complete provided every propositional function can be expressed entirely in terms of operations in the set - i.e. by combining the various logic operations in a set one could create every truth table. Two notable sets are { NAND } and { NOR }. Such sets are also called complete sets.

Examples[edit]

The following are some examples of functionally complete sets:

Determining Completeness[edit]

From the table it can be seen that the following sets are functionally complete: { AND, NOT }, { OR, NOT }, { AND, OR, NOT }.

See also[edit]