Difference between revisions of "Functional completeness"
Karl Jones (Talk | contribs) (Created page with "In logic, a '''functionally complete''' set of logical connectives or Boolean operators is one which can be used to express all...") |
Karl Jones (Talk | contribs) (→See also) |
||
| Line 26: | Line 26: | ||
* [[Mathematics]] | * [[Mathematics]] | ||
* [[Truth table]] | * [[Truth table]] | ||
| + | * [[Turing completeness]] | ||
== External links == | == External links == | ||
* [https://en.wikipedia.org/wiki/Functional_completeness Functional completeness] @ Wikipedia | * [https://en.wikipedia.org/wiki/Functional_completeness Functional completeness] @ Wikipedia | ||
Revision as of 06:07, 16 February 2016
In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.
Description
A well-known complete set of connectives is { AND, NOT }, consisting of binary conjunction and negation. The singleton sets { NAND } and { NOR } are also functionally complete.
Propositional logic
In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.
Digital electronics
From the point of view of digital electronics, functional completeness means that every possible logic gate can be realized as a network of gates of the types prescribed by the set.
In particular, all logic gates can be assembled from either only binary NAND gates, or only binary NOR gates.
See also
- Boolean expression
- Boolean function
- Boolean operator
- Digital electronics
- Logic
- Logical mathematics
- Logic gate
- Mathematics
- Truth table
- Turing completeness
External links
- Functional completeness @ Wikipedia
