Transformace tseytinu - Tseytin transformation

The Transformace tseytinu, alternativně písemné Transformace tseitinu, bere jako vstup libovolný kombinatorická logika obvod a vyrábí a booleovský vzorec v konjunktivní normální forma (CNF), což může vyřešit a CNF-SAT řešitel. Délka vzorce je lineární vzhledem k velikosti obvodu. Vstupní vektory, díky nimž je výstup obvodu „pravdivý“, jsou uvnitř Korespondence 1: 1 s úkoly, které splňují vzorec. Tím se snižuje problém uspokojivost obvodu na libovolném okruhu (včetně jakéhokoli vzorce) do uspokojivost problém na vzorcích 3-CNF.

Motivace

Naivní přístup je napsat obvod jako logický výraz a použít De Morganův zákon a distribuční vlastnictví převést na CNF. To však může mít za následek exponenciální zvětšení velikosti rovnice. Transformace Tseytin vydává vzorec, jehož velikost roste lineárně vzhledem ke vstupnímu obvodu.

Přístup

Výstupní rovnicí je konstanta 1, která se rovná výrazu. Tento výraz je spojením dílčích výrazů, kde uspokojení každého dílčího výrazu vynucuje správnou funkci jedné brány ve vstupním obvodu. Spokojenost celého výstupního výrazu tak vynucuje, aby celý vstupní obvod fungoval správně.

Pro každou bránu je zavedena nová proměnná představující její výstup. Malý předem vypočítaný CNF výraz, který souvisí se vstupy a výstupy, je připojen (pomocí operace „a“) ​​k výstupnímu výrazu. Všimněte si, že vstupy do těchto bran mohou být buď původní literály, nebo zavedené proměnné představující výstupy dílčích bran.

Ačkoli výstupní výraz obsahuje více proměnných než vstup, zůstává vyrovnatelný, což znamená, že je uspokojivá, pouze a pouze, je-li původní vstupní rovnice uspokojivá. Když je nalezeno uspokojivé přiřazení proměnných, lze tyto přiřazení pro zavedené proměnné jednoduše zahodit.

Závěrečná klauzule je připojena k jedinému literálu: výstupní proměnná konečné brány. Pokud je tento literál doplněn, pak uspokojení této klauzule vynutí výstupní výraz na false; jinak je výraz vynucen pravdivý.

Příklady

Zvažte následující vzorec ${ displaystyle phi}$ .

${ Displaystyle phi: = ((p lor q) land r) to ( neg s)}$

Zvažte všechny podformule (bez proměnných):

${ displaystyle { begin {zarovnáno} & neg s & p lor q & (p lor q) land r & ((p lor q) land r) to ( neg s) end {zarovnáno}}}$

Zavést novou proměnnou pro každý podformulář:

${ displaystyle { begin {zarovnáno} x_ {1} & leftrightarrow neg s x_ {2} & leftrightarrow p lor q x_ {3} & leftrightarrow x_ {2} land r x_ {4} & leftrightarrow x_ {3} to x_ {1} end {aligned}}}$

Spojte všechna střídání a střídání ${ displaystyle phi}$:

${ displaystyle T ( phi): = x_ {4} land (x_ {4} leftrightarrow x_ {3} až x_ {1}) land (x_ {3} leftrightarrow x_ {2} land r ) land (x_ {2} leftrightarrow p lor q) land (x_ {1} leftrightarrow neg s)}$

Všechny substituce lze transformovat na CNF, např.

${ displaystyle { begin {seřazeno} x_ {2} leftrightarrow p lor q & equiv (x_ {2} to (p lor q)) land ((p lor q) až x_ {2} ) & equiv ( neg x_ {2} lor p lor q) land ( neg (p lor q) lor x_ {2}) & equiv ( neg x_ {2} lor p lor q) land (( neg p land neg q) lor x_ {2}) & equiv ( neg x_ {2} lor p lor q) land ( neg p lor x_ {2}) land ( neg q lor x_ {2}) end {zarovnáno}}}$

Podvýrazy brány

Uvedeny jsou některé z možných dílčích výrazů, které lze vytvořit pro různé logické brány. Ve výrazu operace funguje C jako výstup; v subexpresi CNF působí C jako nová booleovská proměnná. Pro každou operaci je dílčí výraz CNF pravdivý právě tehdy, když C dodržuje kontrakt booleovské operace pro všechny možné vstupní hodnoty.

Typ	Úkon	CNF Dílčí výraz
A	${ displaystyle C = A cdot B}$	${ displaystyle ({ overline {A}} vee { overline {B}} vee C) wedge (A vee { overline {C}}) wedge (B vee { overline {C} })}$
NAND	${ displaystyle C = { overline {A cdot B}}}$	${ displaystyle ({ overline {A}} vee { overline {B}} vee { overline {C}}) klín (A vee C) klín (B vee C)}$
NEBO	${ displaystyle C = A + B}$	${ displaystyle (A vee B vee { overline {C}}) wedge ({ overline {A}} vee C) wedge ({ overline {B}} vee C)}$
ANI	${ displaystyle C = { overline {A + B}}}$	${ displaystyle (A vee B vee C) wedge ({ overline {A}} vee { overline {C}}) wedge ({ overline {B}} vee { overline {C} })}$
NE	${ displaystyle C = { overline {A}}}$	${ displaystyle ({ overline {A}} vee { overline {C}}) klín (A vee C)}$
XOR	${ displaystyle C = A oplus B}$	${ displaystyle ({ overline {A}} vee { overline {B}} vee { overline {C}}) wedge (A vee B vee { overline {C}}) wedge ( A vee { overline {B}} vee C) wedge ({ overline {A}} vee B vee C)}$
XNOR	${ displaystyle C = { overline {A oplus B}}}$	${ displaystyle ({ overline {A}} vee { overline {B}} vee C) klín (A vee B vee C) klín (A vee { overline {B}} vee { overline {C}}) wedge ({ overline {A}} vee B vee { overline {C}})}$

Jednoduchá kombinatorická logika

Následující obvod vrací true, pokud jsou alespoň některé z jeho vstupů pravdivé, ale ne více než dva najednou. Implementuje rovnici y = x1 · X2 + x1 · x2 + x2 · X3. Pro výstup každé brány je zavedena proměnná; zde je každý označen červeně:

Všimněte si, že výstup střídače s x₂ jako vstup má zavedeny dvě proměnné. I když je to nadbytečné, nemá to vliv na vyrovnatelnost výsledné rovnice. Nyní nahraďte každou bránu příslušnými CNF podvýraz:

Konečná výstupní proměnná je gate8, takže k vynucení toho, aby byl výstup tohoto obvodu pravdivý, je připojena jedna závěrečná jednoduchá klauzule: (gate8). Kombinace těchto rovnic vede k poslední instanci SAT:

(brána1 ∨ x1) ∧ (brána1 ∨ x1) ∧ (brána2 ∨ brána1) ∧ (brána2 ∨ x2) ∧

(x2 ∨ gate2 ∨ brána1) ∧ (brána3 ∨ x2) ∧ (brána3 ∨ x2) ∧ (brána4 ∨ x1) ∧

(brána4 ∨ brána3) ∧ (brána3 ∨ gate4 ∨ x1) ∧ (gate5 ∨ x2) ∧

(brána5 ∨ x2) ∧ (brána6 ∨ brána5) ∧ (brána6 ∨ x3) ∧

(x3 ∨ gate6 ∨ brána5) ∧ (brána7 ∨ brána2) ∧ (brána7 ∨ brána4) ∧

(brána 2 ∨ brána7 ∨ brána4) ∧ (brána8 ∨ brána6) ∧ (brána 8 ∨ brána7) ∧

(brána6 ∨ brána8 ∨ brána7) ∧ (brána8) = 1

Jedním z možných uspokojivých přiřazení těchto proměnných je:

Hodnoty zavedených proměnných jsou obvykle zahozeny, ale lze je použít ke sledování logické cesty v původním obvodu. Zde (x1, x2, x3) = (0,0,1) skutečně splňuje kritéria pro výstup původního obvodu true. Chcete-li najít jinou odpověď, doložku (x1 ∨ x2 ∨ x3) lze připojit a SAT řešič znovu spustit.

Derivace

Prezentována je jedna možná derivace CNF dílčí výraz pro vybrané brány:

NEBO brána

Brána OR se dvěma vstupy A a B a jeden výstup C splňuje následující podmínky:

1. pokud je výstup C je true, pak alespoň jeden z jeho vstupů A nebo B je pravda,
2. pokud je výstup C je false, pak oba jeho vstupy A a B jsou falešné.

Tyto dvě podmínky můžeme vyjádřit jako spojení dvou implikací:

${ displaystyle (C rightarrow (A vee B)) wedge ({ overline {C}} rightarrow ({ overline {A}} wedge { overline {B}}))}$

Nahrazení implikací ekvivalentními výrazy zahrnujícími pouze spojky, disjunkce a negace se získá

${ displaystyle ({ overline {C}} vee (A vee B)) wedge (C vee ({ overline {A}} wedge { overline {B}}))}}$

který je téměř v konjunktivní normální forma již. Distribuce klauzule úplně vpravo přináší dvakrát

${ displaystyle ({ overline {C}} vee A vee B) wedge ((C vee { overline {A}}) wedge (C vee { overline {B}}))}}$

a aplikace asociativity spojení dává vzorec CNF

${ displaystyle ({ overline {C}} vee A vee B) wedge (C vee { overline {A}}) wedge (C vee { overline {B}})}$

NENÍ brána

Brána NOT funguje správně, když jsou její vstup a výstup proti sobě. To je:

1. pokud je výstup C true, je vstup A false
2. pokud je výstup C nepravdivý, je vstup A pravdivý

vyjádřit tyto podmínky jako výraz, který musí být splněn:

${ displaystyle (C rightarrow { overline {A}}) wedge ({ overline {C}} rightarrow A)}$, ${ displaystyle ({ overline {C}} vee { overline {A}}) klín (C vee A)}$

Brána NOR

Brána NOR funguje správně, pokud jsou splněny následující podmínky:

1. pokud je výstup C pravdivý, pak ani A ani B nejsou pravdivé
2. pokud je výstup C nepravdivý, pak alespoň jedna z A a B byla pravdivá

vyjádřit tyto podmínky jako výraz, který musí být splněn:

${ displaystyle (C rightarrow { overline {(A vee B)}}) wedge ({ overline {C}} rightarrow (A vee B))}$, ${ displaystyle { overline { overline {({ overline {C}} vee ({ overline {A}} wedge { overline {B}}))}}} wedge (C vee A vee B))}$, ${ displaystyle { overline {(C klín (A vee B))}} klín (C vee A vee B))}$, ${ displaystyle { overline {(A klín C) vee (B klín C)}} klín (C vee A vee B))}$, ${ displaystyle ({ overline {A}} vee { overline {C}}) wedge ({ overline {B}} vee { overline {C}}) wedge (C vee A vee B))}$

Reference

• GS Tseytin: O složitosti derivace ve výrokovém počtu. In: Slisenko, A.O. (ed.) Studies in Constructive Mathematics and Mathematical Logic, Part II, Seminars in Mathematics, str. 115–125. Steklov Mathematical Institute (1970). Přeloženo z ruštiny: Zapiski Nauchnykh Seminarov LOMI 8 (1968), s. 234–259.
• GS Tseytin: O složitosti derivace ve výrokovém počtu. Prezentováno na Leningradském semináři o matematické logice, který se konal v září 1966.