Nadbytečný důkaz - Redundant proof

tento článek potřebuje pozornost odborníka na matematiku. Přidejte prosím důvod nebo a mluvit parametr k této šabloně pro vysvětlení problému s článkem. Matematika WikiProject může pomoci s náborem odborníka. (Dubna 2014)

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 matematická logika, a nadbytečný důkaz je důkaz která má podmnožinu, která je kratším důkazem stejného výsledku. To je důkaz ${ displaystyle psi}$ z ${ displaystyle kappa}$ se považuje za nadbytečné, pokud existuje jiný důkaz ${ displaystyle psi ^ { prime}}$ z ${ displaystyle kappa ^ { prime}}$ takhle ${ displaystyle kappa ^ { prime} subseteq kappa}$ (tj. ${ displaystyle kappa ^ { prime} ; { text {subsumes}} ; kappa}$) a ${ displaystyle | psi ^ { prime} | <| psi |}$ kde ${ displaystyle | varphi |}$ je počet uzlů v ${ displaystyle varphi}$.^[1]

Místní nadbytečnost

Důkaz obsahující dílčí tvarovou formu (zde vynechány čepy^{[je třeba další vysvětlení ]} označte, že řešení musí být jednoznačně definována)

${ displaystyle ( eta odot eta _ {1}) odot ( eta odot eta _ {2}) { text {nebo}} eta odot ( eta _ {1} odot ( eta odot eta _ {2}))}$

je místně nadbytečný.

Ve skutečnosti lze obě tyto dílčí izolace rovnocenně nahradit kratší dílčí izolací ${ displaystyle eta odot ( eta _ {1} odot eta _ {2})}$. V případě lokální redundance se dvojice redundantních inferencí, které mají stejný pivot, vyskytují blízko sebe v důkazu. V důkazu však může dojít také k nadbytečným závěrům.

Následující definice zobecňuje místní redundanci zvážením závěrů se stejným pivotem, ke kterým dochází v různých kontextech. Píšeme ${ displaystyle psi doleva [ eta doprava]}$ k označení důkazního kontextu ${ displaystyle psi doleva [- doprava]}$ s jediným zástupným znakem nahrazeným subproofem ${ displaystyle eta}$.

Globální redundance

Důkaz

${ displaystyle psi [ psi _ {1} [ eta odot _ {p} eta _ {1}] odot psi _ {2} [ eta odot _ {p} eta _ {2 }]] { text {or}} psi [ psi _ {1} [ eta odot _ {p} ( eta _ {1} odot psi _ {2} [ eta odot _ { p} eta _ {2}])]]}}$

je potenciálně (globálně) nadbytečný. Kromě toho je (globálně) nadbytečné, pokud jej lze přepsat na jeden z následujících kratších důkazů:

${ displaystyle psi [ eta odot _ {p} ( psi _ {1} [ eta _ {1}] odot psi _ {2} [ eta _ {2}])]] { text {or}} eta odot _ {p} psi [ psi _ {1} [ eta _ {1}] odot psi _ {2} [ eta _ {2}]] {{text { nebo}} psi [ psi _ {1} [ eta _ {1}] odot psi _ {2} [ eta _ {2}]].}$

Příklad

Důkaz

${ displaystyle { cfrac {{ cfrac {{ cfrac { eta: , p, q , , , , eta _ {1}: , neg p, r} {q, r }} p , , , , , , { begin {pole} {c} eta _ {3}: , neg q end {pole}}} {r}} q , , , , , , , , , , , , , { cfrac {{ cfrac { eta , , , , , , , , , , , , , , eta _ {2}: , neg p, s, neg r} {q, s, neg r}} p , , , , { begin {pole} {c} eta _ {3} end {pole}}} {s, neg r}} q} { psi: , s}} r}$

je místně nadbytečný, protože se jedná o instanci prvního vzoru v definici ${ displaystyle (( eta odot _ {p} eta _ {1}) odot eta _ {3}) odot (( eta odot _ {p} eta _ {2}) odot eta _ {3}).}$

• Vzor je ${ displaystyle psi [ psi _ {1} [ eta odot _ {p} eta _ {1}] odot psi _ {2} [ eta odot _ {p} eta _ {2 }]]}$
• ${ displaystyle psi _ {1} [-] = psi _ {2} [-] = _ odot eta _ {3} { text {and}} psi [-] = _}$

Není však globálně nadbytečný, protože náhradní termíny podle definice obsahují ${ displaystyle psi _ {1} [ eta _ {1}] odot psi _ {2} [ eta _ {2}]}$ ve všech případech a ${ displaystyle psi _ {1} [ eta _ {1}] odot psi _ {2} [ eta _ {2}] = ( eta _ {1} odot eta _ {3}) odot ( eta _ {2} odot eta _ {3})}$ neodpovídá důkazu. Zejména ani jeden ${ displaystyle eta _ {1}}$ ani ${ displaystyle eta _ {2}}$ lze vyřešit pomocí ${ displaystyle eta _ {3}}$, protože neobsahují literál ${ displaystyle q}$.

Druhý vzorec potenciálně globálně nadbytečných důkazů, které se objevují v definici globální nadbytečnosti, souvisí se známým^{[je třeba další vysvětlení ]} pojem pravidelnosti^{[je třeba další vysvětlení ]}. Neformálně je důkaz nepravidelný, pokud existuje cesta od uzlu ke kořenu důkazu, takže literál je v této cestě použit více než jednou jako pivot.

Poznámky