LowerUnits - LowerUnits

tento článek může být pro většinu čtenářů příliš technická na to, aby je pochopili. Prosím pomozte to vylepšit na aby to bylo srozumitelné pro neodborníky, aniž by byly odstraněny technické podrobnosti. (Dubna 2014) (Zjistěte, jak a kdy odstranit tuto zprávu šablony)

v důkaz komprese LowerUnits (LU) je algoritmus používaný ke kompresi výroková logika rozlišení důkazů. Hlavní myšlenkou LowerUnits je využít následující skutečnost:^[1]

Teorém: Nechat ${ displaystyle  varphi}$ být potenciálně nadbytečný důkaz, a ${ displaystyle  eta}$ být nadbytečným důkazem redundantní uzel. Li ${ displaystyle  eta}$Je doložka je jednotková klauze, pak ${ displaystyle  varphi}$ je nadbytečné.

Algoritmus cílí přesně na třídu globální redundance vyplývající z více rozlišení s jednotkovými klauzulemi. Algoritmus odvozuje svůj název od skutečnosti, že když je toto přepsání hotové a výsledný důkaz je zobrazen jako DAG (směrovaný acyklický graf ), uzel jednotky ${ displaystyle eta}$ jeví se níže (tj. blíže ke kořenu), než se objevovala v původním důkazu.

Naivní implementace využívající teorém by vyžadovala, aby byl důkaz spuštěn a opraven po spuštění každého uzlu jednotky. Je však možné to udělat lépe tak, že nejprve shromáždíte a odstraníte všechny uzly jednotek v jednom průchodu a poté zafixujete celý důkaz v jednom druhém průchodu. Nakonec musí být nashromážděné a pevné uzly jednotek znovu vloženy do spodní části důkazu.

Je třeba dávat pozor na případy, kdy je uzel jednotky ${ displaystyle eta ^ { prime}}$ nastane výše v dílčí izolaci, která odvozuje další uzel jednotky ${ displaystyle eta}$. V takových případech, ${ displaystyle eta}$ záleží na ${ displaystyle eta ^ { prime}}$. Nechat ${ displaystyle ell}$ být doslovný jednotkové klauzule ${ displaystyle eta ^ { prime}}$. Pak jakýkoli výskyt ${ displaystyle { overline { ell}}}$ v subproof výše ${ displaystyle eta}$ nebude zrušeno na základě závěrů o rozlišení s ${ displaystyle eta ^ { prime}}$ už. Tudíž, ${ displaystyle { overline { ell}}}$ se bude šířit směrem dolů, až bude důkaz opraven, a objeví se v klauzuli ${ displaystyle eta}$. Potížím s takovými závislostmi se lze snadno vyhnout, pokud znovu vložíme uzel horní jednotky ${ displaystyle eta ^ { prime}}$ po opětovném vložení uzlu jednotky ${ displaystyle eta}$ (tj. po opětovném vložení, ${ displaystyle eta ^ { prime}}$ musí se objevit níže ${ displaystyle eta}$, zrušit další literál ${ displaystyle { overline { ell}}}$ z ${ displaystyle eta}$Doložka). To lze zajistit shromážděním uzlů jednotek ve frontě během procházení důkazu zdola nahoru a opětovným vložením v pořadí, ve kterém byly zařazeny do fronty.

Algoritmus pro upevnění důkazu obsahujícího mnoho kořenů provede procházení důkazu shora dolů, přepočítá resolventy a nahradí poškozené uzly (např. Uzly, které mají odstraněného NodeMarker jako jednoho ze svých rodičů) jejich přeživšími rodiči (např. Druhým rodičem, v případě, že jeden rodič byl odstraněnNodeMarker).

Když jsou jednotkové uzly shromážděny a odstraněny z důkazu klauzule ${ displaystyle kappa}$ a důkaz je pevný, doložka ${ displaystyle kappa ^ { prime}}$ v kořenovém uzlu nového důkazu se nerovná ${ displaystyle kappa}$ already, but contains (some of) the duals of the literals of the unit clauses that have been removed from the proof. Opětovné vložení uzlů jednotek ve spodní části korektury je vyřešeno ${ displaystyle kappa ^ { prime}}$ s klauzulemi (některých) shromážděných uzlů jednotek za účelem získání důkazu o ${ displaystyle kappa}$ znovu.

Algoritmus

Obecná struktura algoritmu

Algoritmus Vstup LowerUnits: Důkaz ${ displaystyle  psi}$  Výstup: Důkaz ${ displaystyle  psi ^ { prime}}$ bez globální redundance s jednotkovým redundantním uzlem

  (unitsQueue, ${ displaystyle  psi _ {b}}$) ← collectUnits (${ displaystyle  psi}$);   ${ displaystyle  psi _ {f}}$ ← opravit (${ displaystyle  psi _ {b}}$); fixedUnitsQueue ← fix (unitsQueue); ${ displaystyle  psi ^ { prime}}$ ← znovu vložte jednotky (${ displaystyle  psi _ {f}}$, fixedUnitsQueue); vrátit se ${ displaystyle  psi ^ { prime}}$;

Jednotkové doložky shromažďujeme následovně

Algoritmus CollectUnits Input: Důkaz ${ displaystyle  psi}$  Výstup: Pár obsahující frontu všech uzlů jednotek (unitsQueue), které jsou použity více než jednou ${ displaystyle  psi}$ a nefunkční důkaz ${ displaystyle  psi _ {b}}$

${ displaystyle  psi _ {b}}$ ← ${ displaystyle  psi}$; přejít ${ displaystyle  psi _ {b}}$ zdola nahoru a pro každého uzel ${ displaystyle  eta}$ v ${ displaystyle  psi _ {b}}$ dělat  -li ${ displaystyle  eta}$ je jednotka a ${ displaystyle  eta}$ má více než jedno dítě pak      přidat ${ displaystyle  eta}$ to unitsQueue; odstranit ${ displaystyle  eta}$ z ${ displaystyle  psi _ {b}}$;   koneckonecvrátit se (unitsQueue, ${ displaystyle  psi _ {b}}$); 

Pak znovu vložíme jednotky

Algoritmus Vstup ReinsertUnits: Důkaz ${ displaystyle  psi _ {f}}$ (s jediným kořenem) a fronta ${ displaystyle q}$ kořenových uzlů Výstup: Důkaz ${ displaystyle  psi ^ { prime}}$

${ displaystyle  psi ^ { prime}}$ ← ${ displaystyle  psi _ {f}}$; zatímco ${ displaystyle q  neq  emptyset}$ dělat    ${ displaystyle  eta}$ ← první prvek ${ displaystyle q}$;    ${ displaystyle q}$ ← ocas ${ displaystyle q}$;    -li ${ displaystyle  eta}$ je vyřešitelný s kořenem ${ displaystyle  psi ^ { prime}}$ pak        ${ displaystyle  psi ^ { prime}}$ ← resolvent z ${ displaystyle  eta}$ s kořenem ${ displaystyle  psi ^ { prime}}$;     konec konecvrátit se ${ displaystyle  psi ^ { prime}}$;

Poznámky