
In
logic
Logic is the study of correct reasoning. It includes both formal and informal logic. Formal logic is the science of deductively valid inferences or of logical truths. It is a formal science investigating how conclusions follow from premis ...
and
universal algebra
Universal algebra (sometimes called general algebra) is the field of mathematics that studies algebraic structures themselves, not examples ("models") of algebraic structures.
For instance, rather than take particular Group (mathematics), groups as ...
, Post's lattice denotes the
lattice of all
clone
Clone or Clones or Cloning or Cloned or The Clone may refer to:
Places
* Clones, County Fermanagh
* Clones, County Monaghan, a town in Ireland
Biology
* Clone (B-cell), a lymphocyte clone, the massive presence of which may indicate a pathologi ...
s on a two-element set , ordered by
inclusion. It is named for
Emil Post
Emil Leon Post (; February 11, 1897 – April 21, 1954) was an American mathematician and logician. He is best known for his work in the field that eventually became known as computability theory.
Life
Post was born in Augustów, Suwałki Gove ...
, who published a complete description of the lattice in 1941. The relative simplicity of Post's lattice is in stark contrast to the lattice of clones on a three-element (or larger) set, which has the
cardinality of the continuum
In set theory, the cardinality of the continuum is the cardinality or "size" of the set of real numbers \mathbb R, sometimes called the continuum. It is an infinite cardinal number and is denoted by \mathfrak c (lowercase fraktur "c") or , \ma ...
, and a complicated inner structure. A modern exposition of Post's result can be found in Lau (2006).
Basic concepts
A
Boolean function
In mathematics, a Boolean function is a function whose arguments and result assume values from a two-element set (usually , or ). Alternative names are switching function, used especially in older computer science literature, and truth function ...
, or
logical connective
In logic, a logical connective (also called a logical operator, sentential connective, or sentential operator) is a logical constant. They can be used to connect logical formulas. For instance in the syntax of propositional logic, the binary ...
, is an ''n''-ary
operation
Operation or Operations may refer to:
Arts, entertainment and media
* ''Operation'' (game), a battery-operated board game that challenges dexterity
* Operation (music), a term used in musical set theory
* ''Operations'' (magazine), Multi-Man ...
for some , where 2 denotes the two-element set . Particular Boolean functions are the
projections
:
and given an ''m''-ary function ''f'', and ''n''-ary functions ''g''
1, ..., ''g''
''m'', we can construct another ''n''-ary function
:
called their
composition
Composition or Compositions may refer to:
Arts and literature
* Composition (dance), practice and teaching of choreography
*Composition (language), in literature and rhetoric, producing a work in spoken tradition and written discourse, to include ...
. A set of functions closed under composition, and containing all projections, is called a
clone
Clone or Clones or Cloning or Cloned or The Clone may refer to:
Places
* Clones, County Fermanagh
* Clones, County Monaghan, a town in Ireland
Biology
* Clone (B-cell), a lymphocyte clone, the massive presence of which may indicate a pathologi ...
.
Let ''B'' be a set of connectives. The functions which can be defined by a
formula using
propositional variable
In mathematical logic, a propositional variable (also called a sentential variable or sentential letter) is an input variable (that can either be true or false) of a truth function. Propositional variables are the basic building-blocks of propos ...
s and connectives from ''B'' form a clone
'B'' indeed it is the smallest clone which includes ''B''. We call
'B''the clone ''generated'' by ''B'', and say that ''B'' is the ''basis'' of
'B'' For example,
�, ∧are all Boolean functions, and
, 1, ∧, ∨
The comma is a punctuation mark that appears in several variants in different languages. It has the same shape as an apostrophe or single closing quotation mark () in many typefaces, but it differs from them in being placed on the baseline o ...
are the monotone functions.
We use the operations ¬, N''p'', (
negation
In logic, negation, also called the logical complement, is an operation that takes a proposition P to another proposition "not P", written \neg P, \mathord P or \overline. It is interpreted intuitively as being true when P is false, and fals ...
), ∧, K''pq'', (
conjunction
Conjunction may refer to:
* Conjunction (grammar), a part of speech
* Logical conjunction, a mathematical operator
** Conjunction introduction, a rule of inference of propositional logic
* Conjunction (astronomy), in which two astronomical bodies ...
or
meet), ∨, A''pq'', (
disjunction
In logic, disjunction is a logical connective typically notated as \lor and read aloud as "or". For instance, the English language sentence "it is raining or it is snowing" can be represented in logic using the disjunctive formula R \lor ...
or
join), →, C''pq'', (
implication), ↔, E''pq'', (
biconditional
In logic and mathematics, the logical biconditional, sometimes known as the material biconditional, is the logical connective (\leftrightarrow) used to conjoin two statements and to form the statement " if and only if ", where is known as t ...
), +, J''pq'' (
exclusive disjunction
Exclusive or or exclusive disjunction is a logical operation that is true if and only if its arguments differ (one is true, the other is false).
It is symbolized by the prefix operator J and by the infix operators XOR ( or ), EOR, EXOR, , , ...
or
Boolean ring In mathematics, a Boolean ring ''R'' is a ring for which ''x''2 = ''x'' for all ''x'' in ''R'', that is, a ring that consists only of idempotent elements. An example is the ring of integers modulo 2.
Every Boolean ring gives rise to a Boolean a ...
addition
Addition (usually signified by the plus symbol ) is one of the four basic operations of arithmetic, the other three being subtraction, multiplication and division. The addition of two whole numbers results in the total amount or ''sum'' of ...
), ↛, L''pq'', (
nonimplication), ?: (the ternary
conditional operator
The conditional operator is supported in many programming languages. This term usually refers to ?: as in C, C++, C#, and JavaScript. However, in Java, this term can also refer to && and , , .
&& and , ,
In some programming languages, e.g. Jav ...
) and the constant unary functions 0 and 1. Moreover, we need the threshold functions
:
For example, th
1''n'' is the large disjunction of all the variables ''x''
''i'', and th
''n''''n'' is the large conjunction. Of particular importance is the
majority function In Boolean logic, the majority function (also called the median operator) is the Boolean function that evaluates to false when half or more arguments are false and true otherwise, i.e. the value of the function equals the value of the majority of th ...
:
We denote elements of 2
''n'' (i.e., truth-assignments) as vectors: . The set 2
''n'' carries a natural
product
Product may refer to:
Business
* Product (business), an item that serves as a solution to a specific consumer problem.
* Product (project management), a deliverable or set of deliverables that contribute to a business solution
Mathematics
* Prod ...
Boolean algebra
In mathematics and mathematical logic, Boolean algebra is a branch of algebra. It differs from elementary algebra in two ways. First, the values of the variables are the truth values ''true'' and ''false'', usually denoted 1 and 0, whereas ...
structure. That is, ordering, meets, joins, and other operations on ''n''-ary truth assignments are defined pointwise:
:
:
Naming of clones
Intersection
In mathematics, the intersection of two or more objects is another object consisting of everything that is contained in all of the objects simultaneously. For example, in Euclidean geometry, when two lines in a plane are not parallel, thei ...
of an arbitrary number of clones is again a clone. It is convenient to denote intersection of clones by simple
juxtaposition
Juxtaposition is an act or instance of placing two elements close together or side by side. This is often done in order to compare/contrast the two, to show similarities or differences, etc.
Speech
Juxtaposition in literary terms is the showin ...
, i.e., the clone is denoted by ''C''
1''C''
2...''C''
''k''. Some special clones are introduced below:
*M is the set of
monotone
Monotone refers to a sound, for example music or speech, that has a single unvaried tone. See: monophony.
Monotone or monotonicity may also refer to:
In economics
* Monotone preferences, a property of a consumer's preference ordering.
*Monotonic ...
functions: for every .
* ''D'' is the set of
self-dual functions: .
* ''A'' is the set of
affine
Affine may describe any of various topics concerned with connections or affinities.
It may refer to:
* Affine, a Affinity_(law)#Terminology, relative by marriage in law and anthropology
* Affine cipher, a special case of the more general substi ...
functions: the functions satisfying
::
: for every ''i'' ≤ ''n'', a, b ∈ 2
''n'', and ''c'', ''d'' ∈ 2. Equivalently, the functions expressible as for some ''a''
0, a.
* ''U'' is the set of ''essentially unary'' functions, i.e., functions which depend on at most one input variable: there exists an ''i'' = 1, ..., ''n'' such that whenever .
*Λ is the set of ''conjunctive'' functions: . The clone Λ consists of the conjunctions
for all subsets ''I'' of (including the empty conjunction, i.e., the constant 1), and the constant 0.
* V is the set of ''disjunctive'' functions: . Equivalently, V consists of the disjunctions
for all subsets ''I'' of (including the empty disjunction 0), and the constant 1.
*For any ''k'' ≥ 1, ''T''
0''k'' is the set of functions ''f'' such that
::
:Moreover,
is the set of functions bounded above by a variable: there exists ''i'' = 1, ..., ''n'' such that for all a.
:As a special case, is the set of ''0-preserving'' functions: . Furthermore, ⊤ can be considered ''T''
00 when one takes the empty meet into account.
*For any ''k'' ≥ 1, T
1''k'' is the set of functions ''f'' such that
::
:and
is the set of functions bounded below by a variable: there exists ''i'' = 1, ..., ''n'' such that for all a.
:The special case consists of the ''1-preserving'' functions: . Furthermore, ⊤ can be considered ''T''
10 when one takes the empty join into account.
*The largest clone of all functions is denoted ⊤, the smallest clone (which contains only projections) is denoted ⊥, and is the clone of ''constant-preserving'' functions.
Description of the lattice
The set of all clones is a
closure system In mathematics, a closure operator on a set ''S'' is a function \operatorname: \mathcal(S)\rightarrow \mathcal(S) from the power set of ''S'' to itself that satisfies the following conditions for all sets X,Y\subseteq S
:
Closure operators are de ...
, hence it forms a
complete lattice
In mathematics, a complete lattice is a partially ordered set in which ''all'' subsets have both a supremum (join) and an infimum (meet). A lattice which satisfies at least one of these properties is known as a ''conditionally complete lattice.'' S ...
. The lattice is
countably infinite
In mathematics, a set is countable if either it is finite or it can be made in one to one correspondence with the set of natural numbers. Equivalently, a set is ''countable'' if there exists an injective function from it into the natural numbers ...
, and all its members are finitely generated. All the clones are listed in the table below.
The eight infinite families have actually also members with ''k'' = 1, but these appear separately in the table: , , , , , .
The lattice has a natural symmetry mapping each clone ''C'' to its dual clone , where is the
de Morgan dual
In propositional logic and Boolean algebra, De Morgan's laws, also known as De Morgan's theorem, are a pair of transformation rules that are both valid rules of inference. They are named after Augustus De Morgan, a 19th-century British mathema ...
of a Boolean function ''f''. For example, , , and .
Applications
The complete classification of Boolean clones given by Post helps to resolve various questions about classes of Boolean functions. For example:
*An inspection of the lattice shows that the maximal clones different from ⊤ (often called Post's classes) are M, D, A, P
0, P
1, and every proper subclone of ⊤ is contained in one of them. As a set ''B'' of connectives is
functionally complete In logic, a functionally complete set of logical connectives or Boolean operators is one which can be used to express all possible truth tables by combining members of the set into a Boolean expression.. ("Complete set of logical connectives").. (" ...
if and only if it generates ⊤, we obtain the following characterization: ''B'' is functionally complete iff it is not included in one of the five Post's classes.
*The
satisfiability problem
In mathematical logic, a formula is ''satisfiable'' if it is true under some assignment of values to its variables. For example, the formula x+3=y is satisfiable because it is true when x=3 and y=6, while the formula x+1=x is not satisfiable over ...
for Boolean formulas is
NP-complete
In computational complexity theory, a problem is NP-complete when:
# it is a problem for which the correctness of each solution can be verified quickly (namely, in polynomial time) and a brute-force search algorithm can find a solution by tryin ...
by
Cook's theorem. Consider a restricted version of the problem: for a fixed finite set ''B'' of connectives, let ''B''-SAT be the algorithmic problem of checking whether a given ''B''-formula is satisfiable. Lewis used the description of Post's lattice to show that ''B''-SAT is NP-complete if the function ↛ can be generated from ''B'' (i.e., ), and in all the other cases ''B''-SAT is
polynomial-time
In computer science, the time complexity is the computational complexity that describes the amount of computer time it takes to run an algorithm. Time complexity is commonly estimated by counting the number of elementary operations performed by t ...
decidable.
Variants
Clones requiring the constant functions
If one only considers clones that are required to contain the constant functions, the classification is much simpler: there are only 7 such clones: UM, Λ, V, U, A, M, and ⊤. While this can be derived from the full classification, there is a simpler proof, taking less than a page.
[Appendix 12 of ]
Clones allowing nullary functions
Composition alone does not allow to generate a nullary function from the corresponding unary constant function, this is the technical reason why nullary functions are excluded from clones in Post's classification. If we lift the restriction, we get more clones. Namely, each clone ''C'' in Post's lattice which contains at least one constant function corresponds to two clones under the less restrictive definition: ''C'', and ''C'' together with all nullary functions whose unary versions are in ''C''.
Iterative systems
Post originally did not work with the modern definition of clones, but with the so-called ''iterative systems'', which are sets of operations closed under substitution
:
as well as permutation and identification of variables. The main difference is that iterative systems do not necessarily contain all projections. Every clone is an iterative system, and there are 20 non-empty iterative systems which are not clones. (Post also excluded the empty iterative system from the classification, hence his diagram has no least element and fails to be a lattice.) As another alternative, some authors work with the notion of a ''closed class'', which is an iterative system closed under introduction of dummy variables. There are four closed classes which are not clones: the empty set, the set of constant 0 functions, the set of constant 1 functions, and the set of all constant functions.
References
Universal algebra
Logic