In logic, a functionally complete set of logical connectives or Boolean operators is one that 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) that is functionally complete can also be called a universal gate (or a universal set of gates). 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.
Introduction Modern texts on logic typically take as primitive some subset of the connectives: conjunction ( ∧ {\displaystyle \land } ); disjunction ( ∨ {\displaystyle \lor } ); negation ( ¬ {\displaystyle \neg } ); material conditional ( → {\displaystyle \to } ); and possibly the biconditional ( ↔ {\displaystyle \leftrightarrow } ). Further connectives can be defined, if so desired, by defining them in terms of these primitives. For example, NOR (the negation of the disjunction, sometimes denoted ↓ {\displaystyle \downarrow } ) can be expressed as conjunction of two negations:
A ↓ B := ¬ A ∧ ¬ B {\displaystyle A\downarrow B:=\neg A\land \neg B}
Similarly, the negation of the conjunction, NAND (sometimes denoted as ↑ {\displaystyle \uparrow } ), can be defined in terms of disjunction and negation. Every binary connective can be defined in terms of { ¬ , ∧ , ∨ , → , ↔ } {\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}} , which means that set is functionally complete. However, it contains 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
A → B := ¬ A ∨ B A ↔ B := ( A → B ) ∧ ( B → A ) . {\displaystyle {\begin{aligned}A\to B&:=\neg A\lor B\\A\leftrightarrow B&:=(A\to B)\land (B\to A).\end{aligned}}}
It follows that the smaller set { ¬ , ∧ , ∨ } {\displaystyle \{\neg ,\land ,\lor \}} is also functionally complete. (Its functional completeness is also proved by the Disjunctive Normal Form Theorem.) But this is still not minimal, as ∨ {\displaystyle \lor } can be defined as
A ∨ B := ¬ ( ¬ A ∧ ¬ B ) . {\displaystyle A\lor B:=\neg (\neg A\land \neg B).}
Alternatively, ∧ {\displaystyle \land } may be defined in terms of ∨ {\displaystyle \lor } in a similar manner, or ∨ {\displaystyle \lor } may be defined in terms of → {\displaystyle \rightarrow } :
A ∨ B := ¬ A → B . {\displaystyle \ A\vee B:=\neg A\rightarrow B.}
No further simplifications are possible. Hence, every two-element set of connectives containing ¬ {\displaystyle \neg } and one of { ∧ , ∨ , → } {\displaystyle \{\land ,\lor ,\rightarrow \}} is a minimal functionally complete subset of { ¬ , ∧ , ∨ , → , ↔ } {\displaystyle \{\neg ,\land ,\lor ,\to ,\leftrightarrow \}} .
… excerpt ends here. Continue reading the full article.
