コンテンツにスキップ

利用者:Distart/working/ポスト束

ポスト束 (: Post's lattice) とは、論理学普遍代数学において、{0, 1}の集合上にありえるクローン英語版包含関係によって順序付けたのひとつである。名前は1941年この束について発表したエミール・ポストに因む[1]。3要素以上からなる集合についてのクローンの束が連続体濃度をもつのに比べて、比較的単純な内部構造をもつことで知られている。近年のポストによる成果はLau (2006)に詳しい[2]

概要[編集]

ブール関数あるいは論理結合子は一般に n 引数の関数 f: 2n2 として表せる。ただし、{nowrap|n ≥ 1}} で, 2 は2要素の集合 {0, 1} を表す。特に、射影関数

m 引数関数 fn 引数関数 g1, ..., gm を組み合わせることで、別の n 引数関数

合成する事ができる。合成とすべての射影関数を含み閉じている関数集合のことをクローン英語版と呼ぶ。

B を論理結合子の集合とする。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 conditional operator) and the constant unary functions 0 and 1. Moreover, we need the threshold functions

For example, th1n is the large disjunction of all the variables xi, and thnn is the large conjunction. Of particular importance is the majority function

We denote elements of 2n (i.e., truth-assignments) as vectors: a = (a1, ..., an). The set 2n carries a natural product Boolean algebra structure. That is, ordering, meets, joins, and other operations on n-ary truth assignments are defined pointwise:

Naming of clones[編集]

Intersection of an arbitrary number of clones is again a clone. It is convenient to denote intersection of clones by simple juxtaposition, i.e., the clone C1C2 ∩ ... ∩ Ck is denoted by C1C2...Ck. Some special clones are introduced below:

  • M is the set of monotone functions: f(a) ≤ f(b) for every ab.
  • D is the set of self-dual functions: ¬f(a) = fa).
  • A is the set of affine functions: the functions satisfying
for every in, a, b2n, and c, d2. Equivalently, the functions expressible as f(x1, ..., xn) = a0 + a1x1 + ... + anxn for some a0, 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 f(a) = f(b) whenever ai = bi.
  • Λ is the set of conjunctive functions: f(ab) = f(a) ∧ f(b). The clone Λ consists of the conjunctions 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: f(ab) = f(a) ∨ f(b). Equivalently, V consists of the disjunctions for all subsets I of {1, ..., n} (including the empty disjunction 0), and the constant 1.
  • For any k ≥ 1, T0k 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 f(a) ≤ ai for all a.
As a special case, P0 = T01 is the set of 0-preserving functions: f(0) = 0.
  • For any k ≥ 1, T1k 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 f(a) ≥ ai for all a.
The special case P1 = T11 consists of the 1-preserving functions: f(1) = 1.
  • The largest clone of all functions is denoted ⊤, the smallest clone (which contains only projections) is denoted ⊥, and P = P0P1 is the clone of constant-preserving functions.

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.

Hasse diagram of Post's lattice
Central part of the lattice
clone one of its bases
∨, ¬
P0 ∨, +
P1 ∧, →
P x ? y : z
T0k, k ≥ 2 thkk+1, ↛
T0
PT0k, k ≥ 2 thkk+1, x ∧ (yz)
PT0 x ∧ (yz)
T1k, k ≥ 2 th2k+1, →
T1
PT1k, k ≥ 2 th2k+1, x ∨ (y + z)
PT1 x ∨ (y + z)
M ∧, ∨, 0, 1
MP0 ∧, ∨, 0
MP1 ∧, ∨, 1
MP ∧, ∨
MT0k, k ≥ 2 thkk+1, 0
MT0 x ∧ (yz), 0
MPT0k, k ≥ 2 thkk+1 for k ≥ 3,
maj, x ∧ (yz) for k = 2
MPT0 x ∧ (yz)
MT1k, k ≥ 2 th2k+1, 1
MT1 x ∨ (yz), 1
MPT1k, k ≥ 2 th2k+1 for k ≥ 3,
maj, x ∨ (yz) for k = 2
MPT1 x ∨ (yz)
Λ ∧, 0, 1
ΛP0 ∧, 0
ΛP1 ∧, 1
ΛP
V ∨, 0, 1
VP0 ∨, 0
VP1 ∨, 1
VP
D maj, ¬
DP maj, x + y + z
DM maj
A ↔, 0
AD ¬, x + y + z
AP0 +
AP1
AP x + y + z
U ¬, 0
UD ¬
UM 0, 1
UP0 0
UP1 1

The eight infinite families have actually also members with k = 1, but these appear separately in the table: T01 = P0, T11 = P1, PT01 = PT11 = P, MT01 = MP0, MT11 = MP1, MPT01 = MPT11 = MP.

The lattice has a natural symmetry mapping each clone C to its dual clone Cd = {fd | fC}, where fd(x1, ..., xn) = ¬fx1, ..., ¬xn) is the de Morgan dual of a Boolean function f. For example, Λd = V, (T0k)d = T1k, and Md = 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[3] 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., [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

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[編集]

  1. ^ E. L. Post, The two-valued iterative systems of mathematical logic, Annals of Mathematics studies, no. 5, Princeton University Press, Princeton 1941, 122 pp.
  2. ^ 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
  3. ^ H. R. Lewis, Satisfiability problems for propositional calculi, Mathematical Systems Theory 13 (1979), pp. 45–53.

References[編集]