포스트 격자

로직과 유니버설 대수학에서 포스트의 격자는 포함에 의해 명령된 2개 요소 집합 {0, 1}에 있는 모든 클론의 격자를 나타낸다.1941년 격자에 대한 완전한 설명을 발표한 에밀 포스트의 이름을 따서 지은 것이다.^[1]포스트의 격자의 상대적인 단순성은 연속체의 카디널리티와 복잡한 내부 구조를 가진 3원(또는 더 큰) 세트의 클론의 격자와 극명한 대조를 이룬다.포스트의 결과에 대한 현대적인 설명은 라우(2006)에서 찾을 수 있다.^[2]

기본개념

부울 함수 또는 논리적 결합은 일부 n ≥ 1에 대해 n-ary 연산 f: 2 → 2이며ⁿ, 여기서 2는 2-element set {0, 1}을 의미한다. 특정한 부울 함수는 투영이다.

\pi _{k}^{n}(x_{1},\reason,x_{n}}=x_{k}}}

m-ari 함수 f, n-ari 함수 g₁, ..., g를_m 지정하면 다른 n-ari 함수를 구성할 수 있다.

h(x_{1},\reason,x_{n})=f(g_{1}(x_{1},\reason,x_{n}),\properties,g_{m}(x_{1},\reason,x_{n}),}}

그들의 작문을 불렀다.구성 하에서 닫히고 모든 투영을 포함하는 일련의 함수를 클론이라고 한다.

B를 커넥티브의 집합으로 합시다.명제 변수를 사용하여 공식으로 정의할 수 있는 기능과 B의 연결부가 클론 [B]를 형성하며, 실제로 그것은 B를 포함하는 가장 작은 클론이다.우리는 B에 의해 생성된 클론을 [B]라고 부르며, B가 [B]의 기본이라고 말한다.예를 들어, [¬, ]]은 모두 부울함수이며, [0, 1, ∧, ]]은 단조함수다.

We use the operations ¬, Np, (negation), ∧, Kpq, (conjunction or meet), ∨, Apq, (disjunction or join), →, Cpq, (implication), ↔, Epq, (biconditional), +, Jpq (exclusive disjunction or Boolean ring addition), ↛, Lpq,^[3] (nonimplication), ?: (the ternary conditional operator) and the constant unary functions 0 and 1.게다가, 우리는 한계치 기능이 필요하다.

\mathrm {th} _{k}^{n}(x_{1},\reason,x_{n})={\bigl }{{i\mid x_{i}=1\\bigr }\geq k,\\0&\text{n1}={n3}={nmod}.}}}\end{case}

예를 들어, th는₁ⁿ 모든 변수 x의_i 큰 분리이고 th는_nⁿ 큰 결합이다.특히 중요한 것은 대다수의 기능이다.

\mathrm {s} =\mathrm {th} _{2}^{3}=(x\land y)\lor(x\land z)\lor(y\land z).

우리는 2의ⁿ 요소(즉, 진리 할당)를 벡터: a = (a₁, ..., a_n)로 나타낸다.세트 2는ⁿ 자연산 부울 대수 구조를 가지고 있다.즉, n-arry 진리 할당에 대한 순서 지정, 모임, 조인 및 기타 작업이 포인트 방식으로 정의된다.

{\displaystyle(a_{1},\reason,a_{n})\leq(b_{1},\reason,b_{n})\iff a_{i}\leq b_{i}{\text{}{}{}}}{}}}}}}}}}}}}}}}}}}}:}

(a_{1},\reason,a_{n})\land (b_{1},\land b_{n}=(a_{1}, land b_{1}, land b_{n})=(a_{n}, land b_{n}).

클론 이름 지정

임의의 수의 클론의 교차점은 다시 클론이다.단순 대칭, 즉 클론 C₁ ∩ C ∩ ...에 의해₂ 클론의 교차점을 나타내는 것이 편리하다. ∩ C는_k CC₁₂...C에_k 의해 표시된다. 일부 특수 클론은 아래에 소개된다.

M은 단조함수의 집합이다: 모든 b b에 대해 f(a) ≤ f(b)이다.
D는 자기 이중 함수의 집합이다: :f(a) = f(¬a)
A는 아핀 함수의 집합이다: 만족하는 함수의 집합

{\begin{aligned}&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 )\end{aligned}}

모든 i ≤ n, a, b ∈ 2, cⁿ d ∈ 2. 동등하게 f(x₁, ..., x_n)로 표현할 수 있는 함수 = a + ax₀₁₁ + ... + a₀, a를 위한 도끼_n_n.

U는 본질적으로 단항함수의 집합으로, 즉, 입력_i 변수의 최대 하나에 의존하는 함수로서, a = b일_i 때마다 f(a) = f(b)가 되는 i = 1, ..., n이 존재한다.
λ은 결막함수의 집합이다: f(a ∧ b) = f(a) ∧ f(b)The clone Λ consists of the conjunctions $f(x_{1},\dots ,x_{n})=\bigwedge _{i\in I}x_{i}$ for all subsets I of {1, ..., n} (including the empty conjunction, i.e., the constant 1), and the constant 0.
V는 이항함수의 집합이다: f(a ∨ b) = f(a) ∨ f(b)동등하게 V는 {1, $f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}$ , x n $f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}$ )의 모든 하위 집합 I에 대한 $f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}$ 분리 $f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}$ …, $f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}$ ) $f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}$ $f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}$ I $f(x_{1},\dots ,x_{n})=\bigvee _{i\in I}x_{i}$ i ${\$ 상수로 구성된다.
k ≥ 1에 대해 T는₀^k 다음과 같은 함수 집합이다.

\mathbf {a}^{1}\land \cdots \land \mathbf {a}^{0} \Rightarrow \ f(\mathbf {a} ^1})\land \cdotsland f(\mathbf {a}{k}{k}}=0)=0)

Moreover,

\mathrm {T} _{0}^{\infty }=\bigcap _{k=1}^{\infty }\mathrm {T} _{0}^{k}

is the set of functions bounded above by a variable: there exists i = 1, ..., n such that f(a) ≤ a_i for all a.

특별한 경우로서, P₀ = T는₀¹ 0-보존함수의 집합이다: f(0) = 0. 나아가 ⊤은 빈 만남을 고려할 때 T로₀⁰ 간주할 수 있다.

k ≥ 1에 대해 T는₁^k 다음과 같은 함수 집합이다.

{\displaystyle \mathbf {a}^{1}\lor \cdots \lor \mathbf {a}^{1} \Rightarrow \ f(\mathbf {a}^1})\cdotslor f(\mathbf {a}{k}=1,},},},}}}}},},},},})

and

\mathrm {T} _{1}^{\infty }=\bigcap _{k=1}^{\infty }\mathrm {T} _{1}^{k}

is the set of functions bounded below by a variable: there exists i = 1, ..., n such that f(a) ≥ a_i for all a.

특수 케이스 P₁ = T는₁¹ 1 보존 기능인 f(1) = 1. 나아가 빈 조인트를 고려할 때 T로₁⁰ 간주할 수 있다.

모든 기능 중 가장 큰 클론은 ⊤, 가장 작은 클론(투영만 포함)은 ⊥, P = PP는 상시₀₁ 보존 기능의 클론이다.

격자 설명

모든 클론의 집합은 폐쇄 시스템이기 때문에 완전한 격자를 형성한다.격자는 셀 수 없이 무한하며, 모든 구성원이 미세하게 생성된다.모든 복제본이 아래 표에 나열되어 있다.

포스트 격자 하세도

격자의 중심부

복제하다	그 밑거름의 하나.
⊤	∨, ¬
P₀	∨, +
P₁	∧, →
P	x ? y : z
T₀^k, k ≥ 2	th_k^k+1, ↛
T₀^∞	↛
PT₀^k, k ≥ 2	th_k^k+1, x ∧ (y → z)
PT₀^∞	x ∧ (y → z)
T₁^k, k ≥ 2	th₂^k+1, →
T₁^∞	→
PT₁^k, k ≥ 2	th₂^k+1, x ∨ (y + z)
PT₁^∞	x ∨ (y + z)
M	∧, ∨, 0, 1
엠피₀	∧, ∨, 0
엠피₁	∧, ∨, 1
엠피	∧, ∨
MT₀^k, k ≥ 2	th_k^k+1, 0
MT₀^∞	x ∧ (y ∨ z), 0
MPT₀^k, k ≥ 2	t는_k^k+1 k ≥ 3에 대하여, maj, k = 2에 대한 x ∧ (y ∨ z)
MPT₀^∞	x ∧ (y ∨ z)
MT₁^k, k ≥ 2	th₂^k+1, 1
MT₁^∞	x ∨ (y ∧ z), 1
MPT₁^k, k ≥ 2	t는₂^k+1 k ≥ 3에 대하여, maj, k = 2에 대한 x ∨ (y ∧ z)
MPT₁^∞	x ∨ (y ∧ z)
Λ	∧, 0, 1
λP₀	∧, 0
λP₁	∧, 1
λP	∧
V	∨, 0, 1
부사장₀	∨, 0
부사장₁	∨, 1
부사장	∨
D	소, 소제
DP	maj, x + y + z
DM	불가항력의
A	↔, 0
AD	¬, x + y + z
AP₀	+
AP₁	↔
AP	x + y + z
U	¬, 0
UD	¬
음.	0, 1
UP₀	0
UP₁	1
⊥

8개의 무한가족은 실제로 k = 1의 멤버도 가지고 있지만, 이것들은 표에 따로 나타난다.T₀¹ = P₀, T₁¹ = P₁, PT₀¹ = P₁¹, MT₀¹ = MP₀, MTP₁¹₀¹ = MP₁₁¹.

격자는 각각의 클론 C^d = {f^d f ∈ C}에 각각의 클론 C를 매핑하는 자연적인 대칭성을 가지고 있다. 여기서_n f^d(x₁, ..., x) = ¬f(¬x₁, ..., ¬x_n)는 부울함수 f의 de Morgan 듀얼이다.예를^d^d 들어, = = V, (T₀^k)^d = T₁^k, M = M.

적용들

Post가 부여한 부울 클론의 완전한 분류는 부울함수의 클래스에 대한 다양한 질문을 해결하는 데 도움이 된다.예를 들면 다음과 같다.

격자 검사를 통해 ⊤(Post's classes)과는 다른 최대 클론이 M, D, A, P₀, P₁, 그 중 하나에 proper의 모든 적절한 하위 클론이 포함되어 있음을 알 수 있다.connectives의 세트 B는 그것이 ⊤을 생성하는 경우에만 기능적으로 완전하므로, 우리는 다음과 같은 특성화를 얻는다: 만약 그것이 다섯 개의 Post의 클래스 중 하나에 포함되지 않는다면, B는 기능적으로 완전하다.
부울 공식에 대한 만족도 문제는 쿡의 정리에 의한 NP-완전이다.문제의 제한된 버전을 고려하라: 커넥티브의 고정된 유한 집합 B의 경우, B-SAT를 주어진 B-포뮬라가 만족스러운지 확인하는 알고리즘적인 문제가 되게 하라.루이스는^[4] 포스트의 격자 설명을 이용하여 함수 ↛이 B(즉, [B] t₀^∞ T)에서 생성될 수 있다면 B-SAT는 NP-완전하다는 것을 보여주었고, 다른 모든 경우에서 B-SAT는 다항 시간 디커블이 가능하다.

변형

Post는 원래 클론의 현대적 정의로 작용한 것이 아니라, 대체에 따라 폐쇄된 일련의 작업인 소위 반복적 시스템과 함께 작용했다.

h(x_{1},\displaystyle ,x_{n+m-1}=f(x_{1},\n_{n-1},g(x_{n},\n_{n+m-1}),

변수의 순열 및 식별뿐 아니라가장 큰 차이는 반복 시스템이 반드시 모든 투영을 포함하는 것은 아니라는 것이다.모든 복제본은 반복 시스템이며, 복제되지 않는 20개의 비 반복 시스템이 있다. (Post 또한 빈 반복 시스템을 분류에서 제외했기 때문에, 그의 다이어그램은 최소 요소가 없고 격자가 되지 못한다.)또 다른 대안으로, 일부 저자들은 더미 변수의 도입에 따라 닫힌 반복 시스템인 닫힌 클래스의 개념으로 작업한다.클론이 아닌 닫힌 클래스는 빈 세트, 상수 0 함수의 집합, 상수 1 함수의 집합, 모든 상수 함수의 집합 등 4개다.

구성만으로는 해당 단항 상수함수로부터 무효함수를 생성할 수 없으며, 이것이 포스트의 분류에서 무효함수가 클론에서 제외되는 기술적 이유다.규제를 풀면 클론이 더 많아질 거야즉, 적어도 하나의 상수 함수를 포함하는 Post의 격자의 각 클론 C는 덜 제한적인 정의에 따른 두 개의 클론에 대응한다. 즉, C와 C는 단수 버전이 C에 있는 모든 무효 함수와 함께.

참조

^ E. L. 포스트, 수학 논리의 두 가지 가치 있는 반복 시스템, 수학 연보, 제5호, 프린스턴 대학 출판부, 프린스턴 1941년, 122 pp.
^ D. Lau, 유한 집합의 함수 알헤브라스: 많은 가치가 있는 논리와 클론 이론에 관한 기본 과정, Springer, New York, 2006, 668 pp. ISBN 978-3-540-36022-3
^ Jozef Maria Bochenski (1959), rev., Albert Menne, ed. and trans., Otto Bird, Precis of Mathematical Logic, New York: Gordon and Breach, Part II, "Logic of Sentences", Sec. 3.23,"'Np,'" Sec. 3.32, "16 dyadic truth functors", pp. 10-11.
^ H. R. 루이스, 명제 캘커리 만족도 문제, 수학 시스템 이론 13(1979), 페이지 45-53.

[1] E. L. 포스트, 수학 논리의 두 가지 가치 있는 반복 시스템, 수학 연보, 제5호, 프린스턴 대학 출판부, 프린스턴 1941년, 122 pp.

[2] D. Lau, 유한 집합의 함수 알헤브라스: 많은 가치가 있는 논리와 클론 이론에 관한 기본 과정, Springer, New York, 2006, 668 pp. ISBN 978-3-540-36022-3

[3] Jozef Maria Bochenski (1959), rev., Albert Menne, ed. and trans., Otto Bird, Precis of Mathematical Logic, New York: Gordon and Breach, Part II, "Logic of Sentences", Sec. 3.23,"'Np,'" Sec. 3.32, "16 dyadic truth functors", pp. 10-11.

[4] H. R. 루이스, 명제 캘커리 만족도 문제, 수학 시스템 이론 13(1979), 페이지 45-53.

[1]

[2]

[3]

[4]

Search

포스트 격자

네임스페이스

더

목차

기본개념

클론 이름 지정

격자 설명

적용들

변형

참조