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) (→External links) |
||
| (One intermediate revision by the same user not shown) | |||
| 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 | ||
| + | |||
| + | [[Category:Logic]] | ||
Latest revision as of 03:46, 25 April 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
