Post's lattice

Post's lattice

In logic and universal algebra, Post's lattice denotes the lattice of all clones on a two-element set {0, 1}, ordered by inclusion. It is named for Emil Post, who published a complete description of the lattice in 1941 [E. L. Post, "The two-valued iterative systems of mathematical logic", Annals of Mathematics studies, no. 5, Princeton University Press, Princeton 1941, 122 pp.] . 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, and a complicated inner structure. A modern exposition of Post's result can be found in Lau (2006) [D. Lau, "Function algebras on finite sets: Basic course on many-valued logic and clone theory", Springer, New York, 2006, 668 pp. ISBN 978-3-540-36022-3] .

Basic concepts

A Boolean function, or logical connective, is an "n"-ary operation nowrap|"f": 2"n"2 for some nowrap|"n" ≥ 1, where 2 denotes the two-element set {0, 1}. Particular Boolean functions are the projections:pi_k^n(x_1,dots,x_n)=x_k,and given an "m"-ary function "f", and "n"-ary functions "g"1, …, "g""m", we can construct another "n"-ary function:h(x_1,dots,x_n)=f(g_1(x_1,dots,x_n),dots,g_m(x_1,dots,x_n)),called their composition. A set of functions closed under composition, and containing all projections, is called a clone.

Let "B" be a set of connectives. The functions which can be defined by a formula using propositional variables 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 [0, 1, ⋀, ⋁] are the monotone functions.

We use the operations ¬ (negation), ⋀ (conjunction or meet), ⋁ (disjunction or join), → (implication), ↔ (biconditional), + (exclusive disjunction or Boolean ring addition), ↛ (nonimplication), ?: (the ternary ) and the constant unary functions 0 and 1. Moreover, we need the threshold functions:mathrm{th}^n_k(x_1,dots,x_n)=egin{cases}1& ext{if }igl|{imid x_i=1}igr|ge k,\0& ext{otherwise.}end{cases}For example, th1"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:mathrm{maj}=mathrm{th}^3_2=(xland y)lor(xland z)lor(yland z).

We denote elements of 2"n" (i.e., truth-assignments) as vectors: nowrap|1=a = ("a"1, …, "a""n"). The set 2"n" carries a natural product Boolean algebra structure. That is, ordering, meets, joins, and other operations on "n"-ary truth assignments are defined pointwise::(a_1,dots,a_n)le(b_1,dots,b_n)iff a_ile b_i ext{ for every }i=1,dots,n,:(a_1,dots,a_n)land(b_1,dots,b_n)=(a_1land b_1,dots,a_nland b_n).

Naming of clones

Intersection of an arbitrary number of clones is again a clone. It is convenient to denote intersection of clones by simple , i.e., the clone nowrap|"C"1 ⋂ "C"2 ⋂ … ⋂ "C""k" is denoted by "C"1"C"2…"C""k". Some special clones are introduced below:
*M is the set of monotone functions: nowrap|"f"(a) ≤ "f"(b) for every nowrap|ab.
*D is the set of self-dual functions: nowrap|1=¬"f"(a) = "f"(¬a).
*A is the set of affine functions: the functions satisfying::f(a_1,dots,a_{i-1},c,a_{i+1},dots,a_n)=f(a_1,dots,d,a_{i+1},dots) Rightarrow f(b_1,dots,c,b_{i+1},dots)=f(b_1,dots,d,b_{i+1},dots):for every "i" ≤ "n", a, b2"n", and "c", "d" ∈ 2. Equivalently, the functions expressible as nowrap|1="f"("x"1, …, "x""n") = "a"0 + "a"1"x"1 + … + "a""n""x""n" 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 nowrap|1="f"(a) = "f"(b) whenever nowrap|1="a""i" = "b""i".
*Λ is the set of "conjunctive" functions: nowrap|1="f"(ab) = "f"(a) ⋀ "f"(b). The clone Λ consists of the conjunctions f(x_1,dots,x_n)=igwedge_{iin I}x_i for all subsets "I" of {1, …, "n"} (including the empty conjunction, i.e., the constant 1), and the constant 0.
*V is the set of "disjunctive" functions: nowrap|1="f"(ab) = "f"(a) ⋁ "f"(b). Equivalently, V consists of the disjunctions f(x_1,dots,x_n)=igvee_{iin I}x_i for all subsets "I" of {1, …, "n"} (including the empty disjunction 0), and the constant 1.
*For any "k" ≥ 1, T0"k" is the set of functions "f" such that::mathbf a^1landcdotslandmathbf a^k=mathbf 0 Rightarrow f(mathbf a^1)landcdotsland f(mathbf a^k)=0.:Moreover, mathrm{T}_0^infty=igcap_{k=1}^inftymathrm{T}_0^k is the set of functions bounded above by a variable: there exists "i" = 1, …, "n" such that nowrap|"f"(a) ≤ "a""i" for all a.:As a special case, nowrap|1=P0 = T01 is the set of "0-preserving" functions: nowrap|1="f"(0) = 0.
*For any "k" ≥ 1, T1"k" is the set of functions "f" such that::mathbf a^1lorcdotslormathbf a^k=mathbf 1 Rightarrow f(mathbf a^1)lorcdotslor f(mathbf a^k)=1,:and mathrm{T}_1^infty=igcap_{k=1}^inftymathrm{T}_1^k is the set of functions bounded below by a variable: there exists "i" = 1, …, "n" such that nowrap|"f"(a) ≥ "a""i" for all a.:The special case nowrap|1=P1 = T11 consists of the "1-preserving" functions: nowrap|1="f"(1) = 1.
*The largest clone of all functions is denoted ⊤, the smallest clone (which contains only projections) is denoted ⊥, and nowrap|1=P = P0P1 is the clone of "constant-preserving" functions.

The lattice

The set of all clones is a closure system, hence it forms a complete lattice. The lattice is countably infinite, 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: nowrap|1=T01 = P0, nowrap|1=T11 = P1, nowrap|1=PT01 = PT11 = P, nowrap|1=MT01 = MP0, nowrap|1=MT11 = MP1, nowrap|1=MPT01 = MPT11 = MP.

The lattice has a natural symmetry mapping each clone "C" to its dual clone nowrap|1="C""d" = {"f"d "f" ∈ "C"}, where nowrap|1="f""d"("x"1, …, "x""n") = ¬"f"(¬"x"1, …, ¬"x""n") is the de Morgan dual of a Boolean function "f". For example, nowrap|1=Λ"d" = V, nowrap|1=(T0"k")"d" = T1"k", and nowrap|1=M"d" = M.

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, P0, P1, and every proper subclone of ⊤ is contained in one of them. As a set "B" of connectives is functionally complete 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 for Boolean formulas is NP-complete 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 [H. R. Lewis, "Satisfiability problems for propositional calculi", Mathematical Systems Theory 13 (1979), pp. 45–­53.] used the description of Post's lattice to show that "B"-SAT is NP-complete if and only if the function ↛ can be generated from "B" (i.e., nowrap| ["B"] ⊇ T0), and in all the other cases "B"-SAT is polynomial-time decidable.

Variants

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:h(x_1,dots,x_{n+m-1})=f(x_1,dots,x_{n-1},g(x_n,dots,x_{n+m-1})),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.

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".

References


Wikimedia Foundation. 2010.

См. также в других словарях:

  • Emil Leon Post — Infobox Scientist name = Emil Leon Post image width = birth date = February 11, 1897 birth place = Augustów, then Russian Empire death date = April 21 1954, death place = New York City, flagicon|USA U.S. residence = nationality = field =… …   Wikipedia

  • Functional completeness — 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.[1][2] A well known complete set of… …   Wikipedia

  • Clone (algebra) — In universal algebra, a clone is a set C of operations on a set A such that C contains all the projections πkn: An → A, defined by πkn(x1, …,xn) = xk, C is closed under (finitary multiple) composition (or superposition [1]): if f, g1, …, gm are… …   Wikipedia

  • List of mathematics articles (P) — NOTOC P P = NP problem P adic analysis P adic number P adic order P compact group P group P² irreducible P Laplacian P matrix P rep P value P vector P y method Pacific Journal of Mathematics Package merge algorithm Packed storage matrix Packing… …   Wikipedia

  • mast — 1. n. & v. n. 1 a long upright post of timber, iron, etc., set up on a ship s keel, esp. to support sails. 2 a post or lattice work upright for supporting a radio or television aerial. 3 a flag pole (half mast). 4 (in full mooring mast) a strong… …   Useful english dictionary

  • Turing degree — Post s problem redirects here. For the other Post s problem , see Post s correspondence problem. In computer science and mathematical logic the Turing degree or degree of unsolvability of a set of natural numbers measures the level of algorithmic …   Wikipedia

  • Computability theory — For the concept of computability, see Computability. Computability theory, also called recursion theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown …   Wikipedia

  • Boolean algebras canonically defined — Boolean algebras have been formally defined variously as a kind of lattice and as a kind of ring. This article presents them more neutrally but equally formally as simply the models of the equational theory of two values, and observes the… …   Wikipedia

  • Recursion theory — Recursion theory, also called computability theory, is a branch of mathematical logic that originated in the 1930s with the study of computable functions and Turing degrees. The field has grown to include the study of generalized computability… …   Wikipedia

  • Truss bridge — for a single track railway, converted to pedestrian use and pipeline support Ancestor Beam bridge[ …   Wikipedia


Поделиться ссылкой на выделенное

Прямая ссылка:
Нажмите правой клавишей мыши и выберите «Копировать ссылку»