Rozhodnutelnost (logika) - Decidability (logic)

v logika, true / false rozhodovací problém je rozhodnutelné pokud existuje efektivní metoda za odvození správné odpovědi. Logické systémy jako výroková logika jsou rozhodnutelné, pokud je členství v jejich sadě logicky platné vzorce (nebo věty) lze účinně určit. A teorie (sada vět Zavřeno pod logický důsledek ) v pevném logickém systému je rozhodnutelný, pokud existuje účinná metoda pro určení, zda jsou do teorie zahrnuty libovolné vzorce. Mnoho důležitých problémů je nerozhodnutelný To znamená, že bylo prokázáno, že pro ně nemůže existovat žádná účinná metoda pro určení členství (vrácení správné odpovědi po konečné, i když možná velmi dlouhé době).

Rozhodnutelnost logického systému

Každý logický systém přichází s oběma syntaktická složka, což mimo jiné určuje pojem prokazatelnost a sémantická složka, který určuje pojem logická platnost. Logicky platné vzorce systému se někdy nazývají věty systému, zejména v kontextu logiky prvního řádu, kde Gödelova věta o úplnosti stanoví rovnocennost sémantických a syntaktických důsledků. V dalších nastaveních, jako je lineární logika, vztah syntaktických důsledků (prokazatelnosti) lze použít k definování vět systému.

Logický systém je rozhodnutelný, pokud existuje účinná metoda pro určení, zda jsou libovolné vzorce věty logického systému. Například, výroková logika je rozhodnutelné, protože pravdivostní tabulka metodu lze použít k určení, zda je libovolná výrokový vzorec je logicky platný.

Logika prvního řádu není obecně rozhodnutelné; zejména soubor logických validit v libovolném podpis který zahrnuje rovnost a alespoň jeden další predikát se dvěma nebo více argumenty není rozhodnutelný.[1] Logické systémy rozšiřující logiku prvního řádu, jako např logika druhého řádu a teorie typů, jsou také nerozhodnutelné.

Platnost monadický predikátový počet s identitou jsou však rozhodnutelné. Tento systém je logikou prvního řádu omezen na ty podpisy, které nemají žádné funkční symboly a jejichž relační symboly jiné než rovnost nikdy nepřijímají více než jeden argument.

Některé logické systémy nejsou adekvátně reprezentovány samotnou sadou vět. (Například, Kleeneova logika nemá vůbec žádné věty.) V takových případech se často používají alternativní definice rozhodovatelnosti logického systému, které vyžadují efektivní metodu pro určení něčeho obecnějšího než jen platnost vzorců; například platnost sekvence, nebo vztah následků {(Г, A) | Г ⊧ A} logiky.

Rozhodnutelnost teorie

A teorie je sada vzorců, často se předpokládá, že jsou uzavřeny pod logický důsledek. Rozhodnutelnost pro teorii se týká toho, zda existuje účinný postup, který rozhoduje o tom, zda je vzorec členem teorie nebo ne, vzhledem k libovolnému vzorci v podpisu teorie. Problém rozhodovatelnosti nastává přirozeně, když je teorie definována jako sada logických důsledků pevné sady axiomů.

Existuje několik základních výsledků o rozhodovatelnosti teorií. Každý (ne-parakonzistentní ) nekonzistentní teorie je rozhodnutelná, protože každý vzorec v podpisu teorie bude logickým důsledkem teorie, a tudíž jejím členem. Každý kompletní rekurzivně spočetné teorie prvního řádu je rozhodnutelná. Rozšíření rozhodné teorie nemusí být rozhodnutelné. Například v propoziční logice existují nerozhodnutelné teorie, i když rozhodující je soubor validit (nejmenší teorie).

Konzistentní teorie, která má tu vlastnost, že každé konzistentní rozšíření je nerozhodnutelné, se říká v podstatě nerozhodnutelné. Ve skutečnosti bude každé konzistentní rozšíření v podstatě nerozhodnutelné. Teorie polí je nerozhodnutelná, ale v zásadě nerozhodnutelná. Robinsonova aritmetika je známo, že je v zásadě nerozhodnutelný, a proto je každá (každá) konzistentní teorie zahrnující nebo interpretující Robinsonovu aritmetiku také (v podstatě) nerozhodnutelná.

Mezi příklady rozhodujících teorií prvního řádu patří teorie skutečná uzavřená pole, a Presburgerova aritmetika, zatímco teorie skupiny a Robinsonova aritmetika jsou příklady nerozhodnutelných teorií.

Některé rozhodné teorie

Některé rozhodné teorie zahrnují (Monk 1976, s. 234):[2]

Mezi metody použité ke stanovení rozhodnutelnosti patří eliminace kvantifikátoru, úplnost modelu, a Vaughtův test.

Některé nerozhodnutelné teorie

Některé nerozhodnutelné teorie zahrnují (Monk 1976, s. 279):[2]

  • Sada logických validit v jakémkoli podpisu prvního řádu s rovností a buď: relační symbol arity ne menší než 2, nebo dva unární funkční symboly, nebo jeden funkční symbol arity ne menší než 2, stanovený Trakhtenbrot v roce 1953.
  • Teorie prvního řádu přirozených čísel sčítáním, násobením a rovností, kterou založili Tarski a Andrzej Mostowski v roce 1949.
  • Teorie prvního řádu racionálních čísel sčítáním, násobením a rovností, založená Julia Robinson v roce 1949.
  • Teorie skupin prvního řádu, založená Alfred Tarski v roce 1953.[3] Je pozoruhodné, že nejen obecná teorie grup je nerozhodnutelná, ale také několik konkrétnějších teorií, například (jak je stanoveno Mal'cevem 1961) teorie konečných grup. Mal'cev také prokázal, že teorie pologrup a teorie prstenů jsou nerozhodnutelné. Robinson v roce 1949 stanovil, že teorie polí je nerozhodnutelná.
  • Robinsonova aritmetika (a tedy jakékoli konzistentní rozšíření, například Peano aritmetika ) je v zásadě nerozhodnutelný, jak stanoví Raphael Robinson v roce 1950.
  • Teorie prvního řádu s rovností a dvěma funkčními symboly[4]

The interpretovatelnost metoda se často používá k určení nerozhodnutelnosti teorií. Pokud v podstatě nerozhodnutelná teorie T je interpretovatelný konzistentní teorií S, pak S je také v podstatě nerozhodnutelné. To úzce souvisí s konceptem a mnoho-jedna redukce v teorii vypočítatelnosti.

Semidecidovatelnost

Vlastnost teorie nebo logického systému je slabší než rozhodnutelnost semidecidovatelnost. Teorie je semidecidable, pokud existuje účinná metoda, která vzhledem k libovolnému vzorci vždy řekne správně, kdy je vzorec v teorii, ale může dát buď negativní odpověď, nebo vůbec žádnou odpověď, když vzorec není v teorii. Logický systém je semidecidovatelný, pokud existuje efektivní metoda pro generování vět (a pouze vět) tak, že každá věta bude nakonec vygenerována. To se liší od rozhodnutelnosti, protože v semidecidovatelném systému nemusí existovat žádný efektivní postup pro kontrolu, zda vzorec existuje ne věta.

Každá rozhodovatelná teorie nebo logický systém je semidecidovatelný, ale obráceně obecně není pravda; teorie je rozhodnutelná tehdy a jen tehdy, pokud je jak ona, tak její doplněk částečně rozhodnutelná. Například sada logických validit PROTI logiky prvního řádu je polorozhodovatelná, ale nerozhoditelná. V tomto případě je to proto, že neexistuje efektivní metoda pro stanovení libovolného vzorce A zda A není v PROTI. Podobně sada logických důsledků jakéhokoli rekurzivně vyčíslitelná množina axiomů prvního řádu je semidecidable. Mnoho výše uvedených příkladů nerozhodnutelných teorií prvního řádu má tuto formu.

Vztah s úplností

Rozhodnutelnost by neměla být zaměňována s úplnost. Například teorie algebraicky uzavřená pole je rozhodnutelný, ale neúplný, zatímco sada všech pravdivých příkazů prvního řádu o nezáporných celých číslech v jazyce s + a × je úplná, ale nerozhodnutelná. Jako terminologická nejednoznačnost se bohužel někdy používá termín „nerozhodnutelné tvrzení“ jako synonymum pro nezávislé prohlášení.

Vztah k vyčíslitelnosti

Stejně jako u konceptu a rozhodnutelná množina, definici rozhodující teorie nebo logického systému lze uvést buď z hlediska efektivní metody nebo z hlediska vypočítatelné funkce. Ty jsou obecně považovány za ekvivalentní na Církevní teze. Důkaz, že logický systém nebo teorie je nerozhodnutelný, ve skutečnosti použije formální definici vypočítatelnosti k prokázání, že vhodná množina není rozhodnutelnou množinou, a poté vyvolá církevní tezi, aby prokázal, že teorie nebo logický systém není rozhodnutelný žádným efektivním metoda (Enderton 2001, s. 206ff.).

V kontextu her

Nějaký hry byly klasifikovány podle jejich rozhodovatelnosti:

  • Šachy je rozhodnutelné.[5][6] Totéž platí pro všechny ostatní konečné hry pro dva hráče s dokonalými informacemi.
  • Mate dovnitř n v nekonečné šachy (s omezeními pravidel a her) je rozhodující.[7][8] Existují však pozice (s konečně mnoha figurkami), které jsou vynucené vyhrávat, ale ne se páří n pro každou konečnou n.[9]
  • Některé týmové hry s nedokonalými informacemi na konečné desce (ale s neomezeným časem) jsou nerozhodnutelné.[10]

Viz také

Reference

Poznámky

  1. ^ Trakhtenbrot, 1953
  2. ^ A b Donald Monk (1976). Matematická logika. Springer-Verlag. ISBN  9780387901701.
  3. ^ Tarski, A .; Mostovski, A .; Robinson, R. (1953), Nerozhodnutelné teorie„Studies in Logic and the Foundation of Mathematics, North-Holland, Amsterdam
  4. ^ Gurevič, Jurij (1976). „Problém s rozhodováním pro standardní třídy“. J. Symb. Log. 41 (2): 460–464. CiteSeerX  10.1.1.360.1517. doi:10.1017 / S0022481200051513. Citováno 5. srpna 2014.
  5. ^ Stack Exchange Computer Science. „Je pohyb šachové hry rozhodnutelný?“
  6. ^ Nerozhodnutelný šachový problém?
  7. ^ Mathoverflow.net/Decidability-of-chess-on-an-infinite-board Decidability-of-chess-on-an-infinite-board
  8. ^ Dan Brumleve, Joel David Hamkins, Philipp Schlicht, Problém nekonečných šachů Mate-in-n je rozhodnutelný, Poznámky k přednášce z informatiky, svazek 7318, 2012, str. 78–88, Springer [1], Dostupné v arXiv:1201.5597.
  9. ^ „Lo.logic - mat v tahech $ omega $?“.
  10. ^ Nerozhodnutelné problémy: Sampler autor: Bjorn Poonen (oddíl 14.1, „Abstraktní hry“).

Bibliografie

  • Barwise, Jon (1982), „Úvod do logiky prvního řádu“, Barwise, Jon (ed.), Příručka matematické logiky„Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN  978-0-444-86388-1
  • Cantone, D., E. G. Omodeo a A. Policriti, "Set Theory for Computing. From Decision Procedures to Logic Programming with Sets", Monographs in Computer Science, Springer, 2001.
  • Chagrov, Alexander; Zakharyaschev, Michael (1997), Modální logika, Oxford Logic Guides, 35Clarendon Press Oxford University Press, ISBN  978-0-19-853779-3, PAN  1464942
  • Davis, Martin (1958), Vyčíslitelnost a neřešitelnost, McGraw-Hill Book Company, Inc, New York
  • Enderton, Herbert (2001), Matematický úvod do logiky (2. vyd.), Boston, MA: Akademický tisk, ISBN  978-0-12-238452-3
  • Keisler, H. J. (1982), „Základy teorie modelů“, Barwise, Jon (ed.), Příručka matematické logiky„Studies in Logic and the Foundations of Mathematics, Amsterdam: North-Holland, ISBN  978-0-444-86388-1
  • Monk, J. Donald (1976), Matematická logika, Berlín, New York: Springer-Verlag