Are you an EPFL student looking for a semester project?
Work with us on data science and visualisation projects, and deploy your project as an app on top of Graph Search.
Concept
Functional completeness
Summary
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. A well-known complete set of connectives is { AND, NOT }. Each of the singleton sets { NAND } and { NOR } is functionally complete. However, the set { AND, OR } is incomplete, due to its inability to express NOT.
A gate or set of gates which is functionally complete can also be called a universal gate / gates.
A functionally complete set of gates may utilise or generate 'garbage bits' as part of its computation which are either not part of the input or not part of the output to the system.
In a context of propositional logic, functionally complete sets of connectives are also called (expressively) adequate.
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.
Modern texts on logic typically take as primitive some subset of the connectives: conjunction (); disjunction (); negation (); material conditional (); and possibly the biconditional (). Further connectives can be defined, if so desired, by defining them in terms of these primitives. For example, NOR (sometimes denoted , the negation of the disjunction) can be expressed as conjunction of two negations:
Similarly, the negation of the conjunction, NAND (sometimes denoted as ), can be defined in terms of disjunction and negation. It turns out that every binary connective can be defined in terms of , so this set is functionally complete.
However, it still contains some redundancy: this set is not a minimal functionally complete set, because the conditional and biconditional can be defined in terms of the other connectives as
It follows that the smaller set is also functionally complete.
Official source
About this result
This page is automatically generated and may contain information that is not correct, complete, up-to-date, or relevant to your search query. The same applies to every other page on this website. Please make sure to verify the information with EPFL's official sources.