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)
“Thus when I come to shape here at this table between my hands the story of my life and set it before you as a complete thing, I have to recall things gone far, gone deep, sunk into this life or that and become part of it; dreams, too, things surrounding me, and the inmates, those old half-articulate ghosts who keep up their hauntings by day and night ... shadows of people one might have been; unborn selves.”
—Virginia Woolf (1882–1941)
“Wilson adventured for the whole of the human race. Not as a servant, but as a champion. So pure was this motive, so unflecked with anything that his worst enemies could find, except the mildest and most excusable, a personal vanity, practically the minimum to be human, that in a sense his adventure is that of humanity itself. In Wilson, the whole of mankind breaks camp, sets out from home and wrestles with the universe and its gods.”
—William Bolitho (1890–1930)