Functional Completeness
See also: Functional completenessBecause a function may be expressed as a composition, a truth-functional logical calculus does not need to have dedicated symbols for all of the above-mentioned functions to be functionally complete. This is expressed in a propositional calculus as logical equivalence of certain compound statements. For example, classical logic has ¬P ∨ Q equivalent to 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 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:
- One element
- {↑}, {↓}.
- Two elements
- {, ¬}, {, ¬}, {→, ¬}, {←, ¬}, {→, }, {←, }, {→, }, {←, }, {→, }, {→, }, {←, }, {←, }, {, ¬}, {, ¬}, {, }, {, }, {, }, {, }.
- Three elements
- {, }, {, }, {, }, {, }, {, }, {, }.
Read more about this topic: Truth Function
Famous quotes containing the words functional and/or completeness:
“Indigenous to Minnesota, and almost completely ignored by its people, are the stark, unornamented, functional clusters of concrete—Minnesota’s grain elevators. These may be said to express unconsciously all the principles of modernism, being built for use only, with little regard for the tenets of esthetic design.”
—Federal Writers’ Project Of The Wor, U.S. public relief program (1935-1943)
“Poetry presents indivisible wholes of human consciousness, modified and ordered by the stringent requirements of form. Prose, aiming at a definite and concrete goal, generally suppresses everything inessential to its purpose; poetry, existing only to exhibit itself as an aesthetic object, aims only at completeness and perfection of form.”
—Richard Harter Fogle, U.S. critic, educator. The Imagery of Keats and Shelley, ch. 1, University of North Carolina Press (1949)