Příspěvky mříž - Posts lattice - Wikipedia

v logika a univerzální algebra, Postova mříž označuje mříž ze všech klony na dvouprvkové sadě {0, 1}, seřazené podle zařazení. Je pojmenován pro Emil Post, který v roce 1941 zveřejnil kompletní popis mříže.^[1] Relativní jednoduchost Postovy mřížky je v ostrém kontrastu s mřížkou klonů na tříprvkové (nebo větší) množině, která má mohutnost kontinua a složitá vnitřní struktura. Moderní výklad Postova výsledku lze najít v Lau (2006).^[2]

Základní pojmy

A Booleovská funkce nebo logické pojivo, je n-ary úkon F: 2ⁿ → 2 pro některé n ≥ 1, kde 2 označuje sadu dvou prvků {0, 1}. Mezi konkrétní booleovské funkce patří projekce

{ displaystyle pi _ {k} ^ {n} (x_ {1}, dots, x_ {n}) = x_ {k},}

a dostal m-ary funkce F, a n- různé funkce G₁, ..., G_m, můžeme postavit další n-ary funkce

{ displaystyle h (x_ {1}, dots, x_ {n}) = f (g_ {1} (x_ {1}, dots, x_ {n}), dots, g_ {m} (x_ { 1}, tečky, x_ {n})),}

volali jejich složení. Sada funkcí uzavřených ve složení a obsahující všechny projekce se nazývá a klon.

Nechat B být množinou spojovacích prostředků. Funkce, které lze definovat pomocí a vzorec použitím výrokové proměnné a spojky z B vytvořit klon [B], je to nejmenší klon, který zahrnuje B. Voláme [B] klon generováno podle B, a řekni to B je základ z [B]. Například [¬, ∧] jsou všechny booleovské funkce a [0, 1, ∧, ∨] jsou monotónní funkce.

Používáme operace ¬, Np, (negace ), ∧, K.pq, (spojení nebo setkat ), ∨, Apq, (disjunkce nebo připojit se ), →, C.pq, (implikace ), ↔, Epq, (dvojpodmínečné ), +, Jpq (výlučná disjunkce nebo Booleovský prsten přidání ), ↛, Lpq,^[3] (neimplikace ),?: (ternární podmíněný operátor ) a konstantní unární funkce 0 a 1. Navíc potřebujeme prahové funkce

{ displaystyle mathrm {th} _ {k} ^ {n} (x_ {1}, dots, x_ {n}) = { begin {cases} 1 & { text {if}} { bigl |} {i mid x_ {i} = 1 } { bigr |} geq k, 0 & { text {jinak.}} end {případy}}}

Například th₁ⁿ je velká disjunkce všech proměnných X_ia th_nⁿ je velká spojka. Zvláštní význam má většinová funkce

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

Označujeme prvky 2ⁿ (tj. přiřazení pravdy) jako vektory: A = (A₁, ..., A_n). Sada 2ⁿ nese přirozenou produkt Booleova algebra struktura. To znamená, objednávání, setkávání, připojení a další operace n- přiřazení pravdy je definováno bodově:

{ displaystyle (a_ {1}, tečky, a_ {n}) leq (b_ {1}, dots, b_ {n}) iff a_ {i} leq b_ {i} { text {pro }} i = 1, tečky, n,}

{ displaystyle (a_ {1}, dots, a_ {n}) land (b_ {1}, dots, b_ {n}) = (a_ {1} land b_ {1}, dots, a_ {n} land b_ {n}).}

Pojmenování klonů

Průsečík libovolného počtu klonů je opět klon. Je vhodné označit průnik klonů jednoduchým juxtapozice tj. klon C₁ ∩ C₂ ∩ ... ∩ C_k je označen C₁C₂...C_k. Níže jsou uvedeny některé speciální klony:

M je množina monotónní funkce: F(A) ≤ F(b) pro každého A ≤ b.
D je sada self-dual funkce: ¬F(A) = F(¬A).
A je sada afinní funkce: funkce vyhovující

{ displaystyle { 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 {zarovnáno}}}

pro každého i ≤ n, A, b ∈ 2ⁿ, a C, d ∈ 2. Ekvivalentně, funkce vyjádřitelné jako F(X₁, ..., X_n) = A₀ + A₁X₁ + ... + A_nX_n pro některé A₀, A.

U je sada v podstatě unární funkce, tj. funkce, které závisí na nanejvýš jedné vstupní proměnné: existuje i = 1, ..., n takhle F(A) = F(b) kdykoli A_i = b_i.
Λ je množina konjunktivní funkce: F(A ∧ b) = F(A) ∧ F(b). Klon Λ se skládá ze spojení ${ displaystyle f (x_ {1}, dots, x_ {n}) = bigwedge _ {i in I} x_ {i}}$ pro všechny podskupiny Já z {1, ..., n} (včetně prázdné konjunkce, tj. konstanty 1) a konstanty 0.
V je množina disjunktivní funkce: F(A ∨ b) = F(A) ∨ F(b). Ekvivalentně V sestává z disjunkce ${ displaystyle f (x_ {1}, tečky, x_ {n}) = bigvee _ {i v I} x_ {i}}$ pro všechny podskupiny Já z {1, ..., n} (včetně prázdné disjunkce 0) a konstanta 1.
Pro všechny k ≥ 1, T₀^k je sada funkcí F takhle

{ displaystyle mathbf {a} ^ {1} land cdots land mathbf {a} ^ {k} = mathbf {0} Rightarrow f ( mathbf {a} ^ {1}) land cdots land f ( mathbf {a} ^ {k}) = 0.}

Navíc,

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

je sada funkcí ohraničená výše proměnnou: existuje i = 1, ..., n takhle F(A) ≤ A_i pro všechny A.

Jako zvláštní případ P₀ = T₀¹ je sada 0-konzervování funkce: F(0) = 0. Dále lze uvažovat ⊤ T₀⁰ když vezmeme v úvahu prázdnou schůzku.

Pro všechny k ≥ 1, T₁^k je sada funkcí F takhle

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

a

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

je sada funkcí ohraničená níže proměnnou: existuje i = 1, ..., n takhle F(A) ≥ A_i pro všechny A.

Zvláštní případ P₁ = T₁¹ se skládá z 1-konzervování funkce: F(1) = 1. Dále lze uvažovat ⊤ T₁⁰ když vezmeme v úvahu prázdné spojení.

Největší klon všech funkcí je označen ⊤, nejmenší klon (který obsahuje pouze projekce) je označen ⊥ a P = P₀P₁ je klon konstantní zachování funkce.

Popis mřížky

Sada všech klonů je a uzavírací systém, proto tvoří a úplná mříž. Mřížka je počítatelně nekonečný a všichni jeho členové jsou definitivně generováni. Všechny klony jsou uvedeny v tabulce níže.

Hasseův diagram Postovy mříže

Střední část mřížky

klon	jedna z jeho základen
⊤	∨, ¬
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
MP₀	∧, ∨, 0
MP₁	∧, ∨, 1
MP	∧, ∨
MT₀^k, k ≥ 2	th_k^k+1, 0
MT₀^∞	X ∧ (y ∨ z), 0
MPT₀^k, k ≥ 2	th_k^k+1 pro k ≥ 3, maj, X ∧ (y ∨ z) pro k = 2
MPT₀^∞	X ∧ (y ∨ z)
MT₁^k, k ≥ 2	th₂^k+1, 1
MT₁^∞	X ∨ (y ∧ z), 1
MPT₁^k, k ≥ 2	th₂^k+1 pro k ≥ 3, maj, X ∨ (y ∧ z) pro k = 2
MPT₁^∞	X ∨ (y ∧ z)
Λ	∧, 0, 1
ΛP₀	∧, 0
ΛP₁	∧, 1
ΛP	∧
PROTI	∨, 0, 1
VP₀	∨, 0
VP₁	∨, 1
VP	∨
D	maj, ¬
DP	maj, X + y + z
DM	maj
A	↔, 0
INZERÁT	¬, X + y + z
AP₀	+
AP₁	↔
AP	X + y + z
U	¬, 0
UD	¬
UM	0, 1
NAHORU₀	0
NAHORU₁	1
⊥

Osm nekonečných rodin má ve skutečnosti také členy k = 1, ale ty se v tabulce objevují samostatně: T₀¹ = P₀, T₁¹ = P₁, PT₀¹ = PT₁¹ = P, MT₀¹ = MP₀, MT₁¹ = MP₁, MPT₀¹ = MPT₁¹ = MP.

Mřížka má přirozenou symetrii mapující každý klon C do jeho duálního klonu C^d = {F^d | F ∈ C}, kde F^d(X₁, ..., X_n) = ¬F(¬X₁, ..., ¬X_n) je de Morgan dual booleovské funkce F. Například, Λ^d = V, (T.₀^k)^d = T₁^k, a M^d = M..

Aplikace

Kompletní klasifikace booleovských klonů daná Postem pomáhá vyřešit různé otázky týkající se tříd booleovských funkcí. Například:

Inspekce mřížky ukazuje, že maximální klony se liší od ⊤ (často nazývané Třídy příspěvků) jsou M, D, A, P₀, P₁a každý vlastní subklon proper je obsažen v jednom z nich. Jako sada B spojivek je funkčně kompletní právě když generuje ⊤, získáme následující charakterizaci: B je funkčně kompletní, pokud není zahrnut v jedné z pěti tříd Postu.
The problém uspokojivosti pro booleovské vzorce je NP-kompletní podle Cookova věta. Zvažte omezenou verzi problému: pro pevnou konečnou množinu B spojek, nechť B-SAT je algoritmický problém kontroly, zda daný B-formula je uspokojivá. Lewis^[4] k tomu použil popis Postovy mřížky B-SAT je NP-kompletní, pokud lze generovat funkci function B (tj., [B] ⊇ T₀^∞) a ve všech ostatních případech B-SAT je polynomiální čas rozhodnutelné.

Varianty

Post původně nepracoval s moderní definicí klonů, ale s tzv iterační systémy, což jsou sady operací uzavřených substitucí

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

stejně jako permutace a identifikace proměnných. Hlavní rozdíl spočívá v tom, že iterační systémy nemusí nutně obsahovat všechny projekce. Každý klon je iterační systém a existuje 20 neprázdných iteračních systémů, které nejsou klony. (Post také vyloučil prázdný iterační systém z klasifikace, proto jeho diagram nemá nejmenší prvek a není mřížkou.) Jako další alternativu někteří autoři pracují s pojmem a uzavřená třída, což je iterační systém uzavřený zavedením fiktivních proměnných. Existují čtyři uzavřené třídy, které nejsou klony: prázdná množina, množina funkcí konstanty 0, množina funkcí konstanty 1 a množina všech konstantních funkcí.

Samotné složení neumožňuje generovat nulovou funkci z odpovídající unární konstantní funkce, to je technický důvod, proč jsou nulové funkce vyloučeny z klonů v Postově klasifikaci. Pokud zrušíme omezení, získáme více klonů. Konkrétně každý klon C v Postově mřížce, která obsahuje alespoň jednu konstantní funkci, odpovídají dva klony podle méně omezující definice: C, a C společně se všemi nullovými funkcemi, jejichž unární verze jsou v C.

Reference

^ E. L. Post, Dvouhodnotové iterační systémy matematické logiky, Annals of Mathematics studies, no. 5, Princeton University Press, Princeton 1941, 122 s.
^ D. Lau, Funkční algebry na konečných množinách: Základní kurz o mnohohodnotné logice a klonové teoriiSpringer, New York, 2006, 668 stran ISBN 978-3-540-36022-3
^ Jozef Maria Bochenski (1959), rev., Albert Menne, ed. a trans., Otto Bird, Přesnost Matematická logika, New York: Gordon and Breach, část II, „Logika vět“, kap. 3,23, “„ Np, „“ Sekce 3.32, „16 funktorů dyadické pravdy“, s. 10–11.
^ H. R. Lewis, Problémy se splnitelností u výrokových kalkulů, The Mathematical Systems Theory 13 (1979), s. 45–53.

[1] E. L. Post, Dvouhodnotové iterační systémy matematické logiky, Annals of Mathematics studies, no. 5, Princeton University Press, Princeton 1941, 122 s.

[2] D. Lau, Funkční algebry na konečných množinách: Základní kurz o mnohohodnotné logice a klonové teoriiSpringer, New York, 2006, 668 stran ISBN 978-3-540-36022-3

[3] Jozef Maria Bochenski (1959), rev., Albert Menne, ed. a trans., Otto Bird, Přesnost Matematická logika, New York: Gordon and Breach, část II, „Logika vět“, kap. 3,23, “„ Np, „“ Sekce 3.32, „16 funktorů dyadické pravdy“, s. 10–11.

[4] H. R. Lewis, Problémy se splnitelností u výrokových kalkulů, The Mathematical Systems Theory 13 (1979), s. 45–53.

[1]

[2]

[3]

[4]