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)
“As to a thorough eradication of prostitution, nothing can accomplish that save a complete transvaluation of all accepted values—especially the moral ones—coupled with the abolition of industrial slavery.”
—Emma Goldman (1869–1940)
“A horse, a buggy and several sets of harness, valued in all at about $250, were stolen last night from the stable of Howard Quinlan, near Kingsville. The county police are at work on the case, but so far no trace of either thieves or booty has been found.”
—H.L. (Henry Lewis)