From WikiChip
boolean algebra/functional completeness
< boolean algebra
Revision as of 03:32, 24 November 2015 by Jon (talk | contribs)

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

A set of logic operations is functionally complete in Boolean algebra 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

The following are some examples of functionally complete sets:

Determining Completeness

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

See also