Editing Truth function (section)

== Functional completeness ==
{{Main|Functional completeness}}

Because a function may be expressed as a [[composition of functions|composition]], a truth-functional logical calculus does not need to have dedicated symbols for all of the above-mentioned functions to be [[functional completeness|functionally complete]]. This is expressed in a [[propositional calculus]] as [[logical equivalence]] of certain compound statements. For example, classical logic has {{math|¬''P'' ∨ ''Q''}} equivalent to {{math|''P'' → ''Q''}}. The conditional operator "→" is therefore not necessary for a classical-based [[logical system]] if "¬" (not) and "∨" (or) are already in use.

A [[minimal element|minimal]] set of operators that can express every statement expressible in the [[propositional calculus]] is called a ''minimal functionally complete set''. A minimally complete set of operators is achieved by NAND alone {↑} and NOR alone {↓}.

The following are the minimal functionally complete sets of operators whose arities do not exceed 2:<ref name="Wernick">Wernick, William (1942) "Complete Sets of Logical Functions," ''Transactions of the American Mathematical Society 51'': 117–32. In his list on the last page of the article, Wernick does not distinguish between ← and →, or between <math>\nleftarrow</math> and <math>\nrightarrow</math>.</ref>
;One element: {↑}, {↓}.
;Two elements: <math>\{\vee, \neg\}</math>, <math>\{\wedge, \neg\}</math>, <math>\{\to, \neg\}</math>, <math>\{\gets, \neg\}</math>, <math>\{\to, \bot\}</math>, <math>\{\gets, \bot\}</math>, <math>\{\to, \nleftrightarrow\}</math>, <math>\{\gets, \nleftrightarrow\}</math>, <math>\{\to, \nrightarrow\}</math>, <math>\{\to, \nleftarrow\}</math>, <math>\{\gets, \nrightarrow\}</math>, <math>\{\gets, \nleftarrow\}</math>, <math>\{\nrightarrow, \neg\}</math>, <math>\{\nleftarrow, \neg\}</math>, <math>\{\nrightarrow, \top\}</math>, <math>\{\nleftarrow, \top\}</math>, <math>\{\nrightarrow, \leftrightarrow\}</math>, <math>\{\nleftarrow, \leftrightarrow\}</math>.
;Three elements: <math>\{\lor, \leftrightarrow, \bot\}</math>, <math>\{\lor, \leftrightarrow, \nleftrightarrow\}</math>, <math>\{\lor, \nleftrightarrow, \top\}</math>, <math>\{\land, \leftrightarrow, \bot\}</math>, <math>\{\land, \leftrightarrow, \nleftrightarrow\}</math>, <math>\{\land, \nleftrightarrow, \top\}</math>.