Redukce odolnosti proti rozlišení pomocí přepisu místního kontextu - Resolution proof reduction via local context rewriting

v teorie důkazů, oblast matematická logika, snížení důkazu rozlišení prostřednictvím přepisu místního kontextu je technika řešení redukce důkazu prostřednictvím místního kontextu přepis.^[1] Tento důkaz komprese metoda byla prezentována jako pojmenovaný algoritmus ReduceAndReconstruct, který funguje jako následné zpracování rozlišení důkazy.

ReduceAndReconstruct je založen na sadě místních pravidel přepisování důkazu, která transformují subproof na ekvivalentní nebo silnější.^[1] Každé pravidlo je definováno tak, aby odpovídalo konkrétnímu kontextu.

Kontext^[1] zahrnuje dva čepy (${ displaystyle p}$ a ${ displaystyle q}$) a pět doložek (${ displaystyle alpha}$, ${ displaystyle beta}$, ${ displaystyle gamma}$, ${ displaystyle delta}$ a ${ displaystyle eta}$). Struktura kontextu je uvedena v (1). To znamená, že to znamená ${ displaystyle p}$ je obsažen v ${ displaystyle beta}$ a ${ displaystyle gamma}$ (s opačnou polaritou) a ${ displaystyle q}$ je obsažen v ${ displaystyle delta}$ a ${ displaystyle alpha}$ (také s opačnou polaritou).

${ displaystyle { cfrac {{ cfrac { beta qquad gamma} { delta}} , p qquad alpha} { eta}} , q}$

(1)

V tabulce níže jsou uvedena pravidla přepisování navržená Simone et al..^[1] Myšlenkou algoritmu je zmenšit velikost důkazu oportunistickým použitím těchto pravidel.

Kontext	Pravidlo
Případ A1: ${ displaystyle s notin alpha, t in gamma}$	${ displaystyle { cfrac {{ cfrac {stC qquad { overline {s}} tD} {tCD}} , operatorname {var} (s) qquad { overline {t}} E} {CDE }} , operatorname {var} (t) Rightarrow { cfrac {{ cfrac {stC qquad { overline {t}} E} {sCE}} , operatorname {var} (t) qquad { cfrac {{ overline {t}} E qquad { overline {s}} tD} {{ overline {s}} DE}} , operatorname {var} (t)} {CDE}} , operatorname {var} (s)}$
Případ A2: ${ displaystyle s notin alpha, t notin gamma}$	${ displaystyle { cfrac {{ cfrac {stC qquad { overline {s}} D} {tCD}} , operatorname {var} (s) qquad { overline {t}} E} {CDE }} , operatorname {var} (t) Rightarrow { cfrac {{ cfrac {stC qquad { overline {t}} E} {sCE}} , operatorname {var} (t) qquad { overline {s}} D} {CDE}} , operatorname {var} (s)}$
Případ B1: ${ displaystyle s in alpha, t in gamma}$	${ displaystyle { cfrac {{ cfrac {stC qquad { overline {s}} tD} {tCD}} , operatorname {var} (s) qquad s { overline {t}} E} { sCDE}} , operatorname {var} (t) Rightarrow { cfrac {stC qquad s { overline {t}} E} {sCE}} , operatorname {var} (t)}$
Případ B2: ${ displaystyle s in alpha, t notin gamma}$	${ displaystyle { cfrac {{ cfrac {stC qquad { overline {s}} D} {tDC}} , operatorname {var} (s) qquad s { overline {t}} E} { sCDE}} , operatorname {var} (t) Rightarrow { cfrac {{ cfrac {stC qquad s { overline {t}} E} {sCE}} , operatorname {var} (t) qquad { overline {s}} D} {CDE}} , operatorname {var} (s)}$
Případ B3: ${ displaystyle { overline {s}} in alpha, t notin gamma}$	${ displaystyle { cfrac {{ cfrac {stC qquad { overline {s}} D} {tDC}} , operatorname {var} (s) qquad { overline {s}} { overline { t}} E} {{ overline {s}} CDE}} , operatorname {var} (t) Rightarrow { overline {s}} D}$
Případ A1 '	${ displaystyle { cfrac {{ cfrac {stC qquad { overline {s}} tD} {tCD}} , operatorname {var} (s) qquad { overline {t}} E} {CDE }} , operatorname {var} (t) Leftarrow { cfrac {{ cfrac {stC qquad { overline {t}} E} {sCE}} , operatorname {var} (t) qquad { cfrac {{ overline {t}} E qquad { overline {s}} tD} {{ overline {s}} DE}} , operatorname {var} (t)} {CDE}} , operatorname {var} (s)}$
Případ B2 ': ${ displaystyle t notin gamma}$	${ displaystyle { cfrac {{ cfrac {stC qquad { overline {s}} D} {tCD}} , operatorname {var} (s) qquad s { overline {t}} E} { sCDE}} , operatorname {var} (t) Rightarrow { cfrac {stC qquad s { overline {t}} E} {sCE}} , operatorname {var} (t)}$

Prvních pět pravidel bylo představeno v dřívějším článku.^[2] Navíc:

• Pravidlo A2 samo o sobě neprovádí žádné snižování. Je to však stále užitečné kvůli jeho „přesouvacímu“ účinku, který může vytvořit nové příležitosti pro uplatnění ostatních pravidel;
• Pravidlo A1 se v praxi nepoužívá, protože může zvýšit velikost důkazu;
• Pravidla B1, B2, B2 'a B3 jsou přímo zodpovědná za redukci, protože vytvářejí transformovanou kořenovou klauzuli silnější než původní;
• Použití pravidla B může vést k nezákonnému důkazu (viz příklad níže), protože některé literály chybějící v klauzuli transformovaného kořene mohou být zapojeny do dalšího kroku řešení podél cesty k kořenu důkazu. Algoritmus proto také musí „rekonstruovat“ právní důkaz, když k tomu dojde.

Následující příklad^[1] ukazuje situaci, kdy se důkaz stane nezákonným po použití pravidla B2 ':

${ displaystyle { cfrac {{ cfrac {{ cfrac {{ cfrac { mathbf {pq} qquad mathbf {{ overline {p}} o}} { mathbf {qo}}} , p qquad mathbf {p { overline {q}}}} { mathbf {po}}} , q qquad { cfrac {qr qquad { overline {p}} { overline {q}}} {{ overline {p}} r}} , q} {nebo}} , p qquad { overline {o}} s} {rs}} , o}$

(2)

Aplikování pravidla B2 'na zvýrazněný kontext:

${ displaystyle { cfrac {{ cfrac {{ cfrac { mathbf {pq} qquad mathbf {p { overline {q}}}} { mathbf {p}}} , q qquad { cfrac {qr qquad { overline {p}} { overline {q}}} {{ overline {p}} r}} , q} {nebo}} , p qquad { overline {o} } s} {rs}} , o}$

(3)

Důkaz je nyní nezákonný, protože doslovný ${ displaystyle o}$ chybí v transformované kořenové klauzuli. K rekonstrukci důkazu je možné jej odebrat ${ displaystyle o}$ společně s posledním krokem řešení (to je nyní nadbytečné). Konečným výsledkem je následující právní (a silnější) důkaz:

${ displaystyle { cfrac {{ cfrac {pq qquad p { overline {q}}} {p}} , q qquad { cfrac {qr qquad { overline {p}} { overline { q}}} {{ overline {p}} r}} , q} {r}} , p}$

(4)

Další snížení tohoto důkazu uplatněním pravidla A2 k vytvoření nové příležitosti uplatnit pravidlo B2 '.^[1]

Obvykle existuje obrovské množství kontextů, kde lze použít pravidlo A2, takže vyčerpávající přístup není obecně proveditelný. Jeden návrh^[1] je vykonat ReduceAndReconstruct jako smyčka se dvěma kritérii ukončení: počet iterací a časový limit (co je dosaženo jako první). Pseudokód^[1] níže to ukazuje.

 1  funkce ReduceAndReconstruct (${ displaystyle  pi}$ /* důkaz */, lhůta, maxIterace): 2      pro i = 1 až maxIterace dělat 3 ReduceAndReconstructLoop (); 4 -li čas > lhůta pak        // Časový limit 5              přestávka; 6      konec pro 7  koncová funkce

ReduceAndReconstruct používá funkci ReduceAndReconstructLoop, který je uveden níže. První část algoritmu dělá a topologické uspořádání z graf rozlišení (vzhledem k tomu, že hrany přecházejí z antecedentes na resolventy). To se provádí, aby se zajistilo, že každý uzel je navštíven po svých předchůdcích (tímto způsobem jsou vždy nalezeny a opraveny rozbité kroky řešení).^[1]

 1  funkce ReduceAndReconstructLoop (${ displaystyle  pi}$ /* důkaz */): 2      TS = Topologické třídění (${ displaystyle  pi}$); 3      pro každého uzel ${ displaystyle n}$ v TS 4          -li ${ displaystyle n}$ není list 5 -li ${ displaystyle n _ { text {piv}}  in n _ { text {klauzule}} ^ { text {left}}}$ a ${ displaystyle { overline {n _ { text {piv}}}}  v n _ { text {klauzule}} ^ { text {right}}}$ pak 6                  ${ displaystyle n _ { text {klauzule}}}$ = Rozlišení (${ displaystyle n _ { text {clause}} ^ { text {left}}}$, ${ displaystyle n _ { text {clause}} ^ { text {right}}}$); 7 Určete levý kontext ${ displaystyle n}$, jestli nějaký; 8 Určete správný kontext ${ displaystyle n}$, jestli nějaký; 9 Heuristicky vyberte jeden kontext (pokud existuje) a použijte odpovídající pravidlo; 10 jinak pokud ${ displaystyle n _ { text {piv}}  notin n _ { text {clause}} ^ { text {left}}}$ a ${ displaystyle { overline {n _ { text {piv}}}}  in n _ { text {clause}} ^ { text {right}}}$ pak11 Náhradník ${ displaystyle n}$ s ${ displaystyle n ^ { text {left}}}$;12              jinak pokud ${ displaystyle n _ { text {piv}}  v n _ { text {klauzule}} ^ { text {left}}}$ a ${ displaystyle { overline {n _ { text {piv}}}}  notin n _ { text {clause}} ^ { text {right}}}$ pak13 Náhradník ${ displaystyle n}$ s ${ displaystyle n ^ { text {right}}}$;14              jinak pokud ${ displaystyle n _ { text {piv}}  notin n _ { text {klauzule}} ^ { text {left}}}$ a ${ displaystyle { overline {n _ { text {piv}}}}  notin n _ { text {klause}} ^ { text {right}}}$ pak15 Heuristicky si vyberte předchůdce ${ displaystyle n ^ { text {left}}}$ nebo ${ displaystyle n ^ { text {right}}}$; 16 Náhradník ${ displaystyle n}$ s ${ displaystyle n ^ { text {left}}}$ nebo ${ displaystyle n ^ { text {right}}}$;17      konec pro18  koncová funkce

Pokud vstupní důkaz není strom (obecně jsou to grafy rozlišení směrované acyklické grafy ), pak klauzule ${ displaystyle delta}$ kontextu může být zapojen do více než jednoho kroku řešení krize. V tomto případě, aby bylo zajištěno, že aplikace pravidla přepisování nebude zasahovat do dalších kroků řešení, je bezpečným řešením vytvoření kopie uzlu představovaného klauzulí ${ displaystyle delta}$.^[1] Toto řešení zvyšuje velikost důkazu a při tom je nutná určitá opatrnost.

The heuristický pro výběr pravidla je důležité dosáhnout dobrého kompresního výkonu. Simone et al. ^[1] použijte následující pořadí preferencí pravidel (pokud je to pro daný kontext použitelné): B2> B3> {B2 ', B1}> A1'> A2 (X> Y znamená, že X je upřednostňováno před Y).

Pokusy ukázaly, že ReduceAndReconstruct samotný má horší poměr komprese a času než algoritmus Recyklovat čepy.^[3] Zatímco RecyclePivots lze na důkaz použít pouze jednou, ReduceAndReconstruct lze použít několikrát, aby se dosáhlo lepší komprese. Pokus o kombinaci algoritmů ReduceAndReconstruct a RecyclePivots vedl k dobrým výsledkům.^[1]

Poznámky