Minimal Functionally Complete Operator Sets
When a single logical connective or Boolean operator is functionally complete by itself, it is called a Sheffer function or sometimes a sole sufficient operator. There are no unary operators with this property, and the only binary Sheffer functions — NAND and NOR are dual. These were discovered but not published by Charles Sanders Peirce around 1880, and rediscovered independently and published by Henry M. Sheffer in 1913. In digital electronics terminology, the binary NAND gate and the binary NOR gate are the only binary universal logic gates.
The following are the minimal functionally complete sets of logical connectives with arity ≤ 2:
- One element
- {NAND}, {NOR}.
- Two elements
- {, ¬}, {, ¬}, {→, ¬}, {←, ¬}, {→, }, {←, }, {→, }, {←, }, {→, }, {→, }, {←, }, {←, }, {, ¬}, {, ¬}, {, }, {, }, {, }, {, }.
- Three elements
- {, }, {, }, {, }, {, }, {, }, {, }.
There are no minimal functionally complete sets of more than three at most binary logical connectives. Constant unary or binary connectives and binary connectives that depend only on one of the arguments have been suppressed to keep the list readable. E.g. the set consisting of binary and the binary connective given by negation of the first argument (ignoring the second) is another minimal functionally complete set.
Read more about this topic: Functional Completeness
Famous quotes containing the words minimal, complete and/or sets:
“For those parents from lower-class and minority communities ... [who] have had minimal experience in negotiating dominant, external institutions or have had negative and hostile contact with social service agencies, their initial approaches to the school are often overwhelming and difficult. Not only does the school feel like an alien environment with incomprehensible norms and structures, but the families often do not feel entitled to make demands or force disagreements.”
—Sara Lawrence Lightfoot (20th century)
“Reporters for tabloid newspapers beat a path to the park entrance each summer when the national convention of nudists is held, but the cult’s requirement that visitors disrobe is an obstacle to complete coverage of nudist news. Local residents interested in the nudist movement but as yet unwilling to affiliate make observations from rowboats in Great Egg Harbor River.”
—For the State of New Jersey, U.S. public relief program (1935-1943)
“Drink, sir, is a great provoker of three things ... nose-painting, sleep, and urine. Lechery, sir, it provokes and unprovokes: it provokes the desire but it takes away the performance. Therefore much drink may be said to be an equivocator with lechery: it makes him and it mars him; it sets him on and it takes him off.”
—William Shakespeare (1564–1616)