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)
“Silence is to all creatures thus attacked the only means of salvation; it fatigues the Cossack charges of the envious, the enemy’s savage ruses; it results in a cruising and complete victory.”
—Honoré De Balzac (1799–1850)
“To me this world is all one continued vision of fancy or imagination, and I feel flattered when I am told so. What is it sets Homer, Virgil and Milton in so high a rank of art? Why is Bible more entertaining and instructive than any other book? Is it not because they are addressed to the imagination, which is spiritual sensation, and but mediately to the understanding or reason?”
—William Blake (1757–1827)