Cílený důkaz - Focused proof

V matematické logice zaměřené důkazy jsou rodina analytické důkazy které vznikají prostřednictvím cíleného korektury a jsou předmětem studia teorie strukturního důkazu a reduktivní logika. Tvoří nejobecnější definici cílené proof-search —, kdy si někdo zvolí vzorec a provede dědičné redukce, dokud výsledek nesplní nějakou podmínku. Extrémní případ, kdy redukce končí pouze při dosažení axiomů, tvoří podskupinu jednotný důkazy.^[1]

Sekvenční kalkul má vlastnost zaostřování, když jsou zaostřené důkazy úplné pro některou konečnou podmínku. Pro Systém LK, Systém LJ, a Systém LL, uniformní důkazy jsou soustředěné důkazy, kde jsou všem atomům přiřazena záporná polarita.^[2] Ukázalo se, že mnoho dalších po sobě jdoucích kamenů má vlastnost zaostřování, zejména vnořené následné kameny jak klasické, tak intuitivní varianty modálních logik v Kostka S5.^[3][4]

Jednotné důkazy

V následném počtu pro intuitivní logiku lze jednotné důkazy charakterizovat jako ty, ve kterých čtení směrem vzhůru provádí všechna správná pravidla před pravidly levými. Jednotné důkazy obvykle nejsou pro logiku úplné, tj. Ne všechny sekvence nebo vzorce připouštějí jednotný důkaz, takže je třeba brát v úvahu fragmenty, kde jsou úplné, např. dědičná Harrop fragment z Intuitivní logika. Kvůli deterministickému chování bylo jako kontrolní mechanismus definující jednotné kontrolní vyhledávání použito jednotné kontrolní vyhledávání programovací jazyk paradigma logické programování.^[1] Příležitostně je jednotné vyhledávání důkazů implementováno ve variantě sekvenčního počtu pro danou logiku, kde je kontextová správa automatická, čímž se zvyšuje fragment, pro který lze definovat logický programovací jazyk.^[5]

Cílené důkazy

Princip zaostření byl původně klasifikován prostřednictvím disambiguace mezi synchronním a asynchronním spojovacím vstupem Lineární logika tj. spojky, které interagují s kontextem a ty, které ne, v důsledku výzkumu na logické programování. Nyní jsou stále důležitějším příkladem kontroly v reduktivní logika, a může drasticky zlepšit postupy kontroly důkazů v průmyslu. Základní myšlenkou zaměření je identifikovat a spojit nedeterministické volby v důkazu, aby bylo možné na důkaz pohlížet jako na střídání negativních fází (kde se dychtivě uplatňují invertibilní pravidla) a pozitivních fází (kde aplikace druhého pravidla jsou omezena a kontrolována).^[3]

Polarizace

Podle pravidel v následném počtu jsou vzorce kanonicky dány do jedné ze dvou nazývaných tříd pozitivní a negativní např. v LK a LJ vzorec ${ displaystyle phi lor psi}$ je pozitivní. Jediná svoboda je nad atomy, kterým je volně přiřazena polarita. U negativních vzorců je prokazatelnost neměnná při použití správného pravidla; a, duálně, pro pozitivní vzorce je prokazatelnost neměnná při použití levého pravidla. V obou případech lze bezpečně použít pravidla v jakémkoli pořadí na dědičné podvzorec se stejnou polaritou.

V případě pravého pravidla použitého na pozitivní vzorec nebo levého pravidla použitého na negativní vzorec může mít za následek neplatné sekvence, např. V LK a LJ neexistuje žádný důkaz sekvence ${ displaystyle B lor A znamená A lor B}$ počínaje správným pravidlem. Kalkul připouští princip zaostřování pokud bylo možné prokázat původní redukci, pak jsou prokazatelné i dědičné redukce stejné polarity. To znamená, že se člověk může zavázat, že se zaměří na rozložení vzorce a jeho podformulí se stejnou polaritou bez ztráty úplnosti.

Zaměřený systém

Sekvenční kalkul se často ukazuje, že má vlastnost zaostření tím, že pracuje v souvisejícím kalkulu, kde polarita výslovně určuje, která pravidla se použijí. Důkazy v takových systémech jsou v soustředěných, neurčitých nebo neutrálních fázích, kde první dva jsou charakterizovány dědičným rozkladem; a druhý vynucením volby zaměření. Jedním z nejdůležitějších provozních chování, kterému může procedura projít, je ustoupit tj. návrat do dřívější fáze výpočtu, kde byla provedena volba. V zaměřených systémech pro klasickou a intuitivní logiku lze použití zpětného sledování simulovat pseudo-kontrakcí.

Nechat ${ displaystyle uparrow}$ a ${ displaystyle downarrow}$ označit změnu polarity, přičemž první způsobí vzorec negativní a druhý pozitivní; a zavoláme vzorec se šipkou neutrální. Odvolej to ${ displaystyle lor}$ je pozitivní a zvažte neutrální polarizovaný sled ${ displaystyle downarrow uparrow phi lor psi znamená uparrow phi lor psi}$, který je interpretován jako skutečný sled ${ Displaystyle phi lor psi znamená phi lor psi}$. U neutrálních sekvencí, jako je tento, zaměřený systém nutí explicitně zvolit, na který vzorec se má zaměřit, označený ${ displaystyle langle , rangle}$. Pro provedení korektury je nejlepší zvolit levý vzorec ${ displaystyle lor}$ je pozitivní, vskutku (jak je uvedeno výše) v některých případech neexistují žádné důkazy o tom, že se zaměřujeme na správný vzorec. Abychom to překonali, některé zaměřené kameny vytvářejí bod zpětného sledování, který se zaměřuje na správné výnosy ${ displaystyle downarrow uparrow phi lor psi znamená langle phi lor psi rangle, uparrow phi lor psi}$, který je stále jako ${ displaystyle phi lor psi znamená phi lor psi}$. Druhý vzorec vpravo lze odebrat pouze po dokončení zaostřené fáze, ale pokud dojde k zaseknutí kontroly důkazů dříve, než k tomu dojde, sekvence může odebrat zaostřenou složku, čímž se vrátí k výběru, např. ${ displaystyle downarrow uparrow B lor A znamená langle A rangle, uparrow A lor B}$ musí být přijato ${ displaystyle downarrow uparrow B lor A znamená uparrow A lor B}$ protože nelze učinit žádný další redukční závěr. Jedná se o pseudo-kontrakci, protože má syntaktickou formu kontrakce napravo, ale skutečný vzorec neexistuje, tj. Při interpretaci důkazu v zaměřeném systému má sekvence pouze jeden vzorec vpravo.

Reference