Automatizované dokazování věty - Automated theorem proving
Automatizované dokazování věty (také známý jako ATP nebo automatický odpočet) je podpole z automatické uvažování a matematická logika zabývající se dokazováním matematické věty podle počítačové programy. Automatické uvažování skončilo matematický důkaz byl hlavním podnětem pro rozvoj počítačová věda.
Logické základy
Zatímco kořeny formalizovány logika jít zpět k Aristoteles Na konci 19. a na počátku 20. století došlo k rozvoji moderní logiky a formální matematiky. Frege je Begriffsschrift (1879) představil oba kompletní výrokový kalkul a co je v podstatě moderní predikátová logika.[1] Jeho Základy aritmetiky, publikováno 1884,[2] vyjádřená (část) matematiky ve formální logice. Tento přístup pokračoval Russell a Whitehead ve svém vlivném Principia Mathematica, poprvé publikováno v letech 1910–1913,[3] as revidovaným druhým vydáním v roce 1927.[4] Russell a Whitehead si mysleli, že mohou odvodit veškerou matematickou pravdu pomocí axiomů a odvozovacích pravidel formální logiky, což v zásadě otevírá proces automatizaci. V roce 1920 Thoralf Skolem zjednodušil předchozí výsledek o Leopold Löwenheim, vedoucí k Löwenheim – Skolemova věta a v roce 1930 k pojmu a Herbrandův vesmír a a Herbrandova interpretace která umožňovala (ne) uspokojivost vzorců prvního řádu (a tedy i platnost věty), které mají být redukovány na (potenciálně nekonečně mnoho) problémů výrokové uspokojivosti.[5]
V roce 1929 Mojżesz Presburger ukázal, že teorie přirozená čísla s přidáním a rovností (nyní se nazývá Presburgerova aritmetika na jeho počest) je rozhodnutelné a dal algoritmus, který mohl určit, zda je daná věta v jazyce pravdivá nebo nepravdivá.[6][7]Krátce po tomto pozitivním výsledku však Kurt Gödel zveřejněno K formálně nerozhodnutelným návrhům Principia Mathematica a souvisejících systémů (1931), což ukazuje, že v jakémkoli dostatečně silném axiomatickém systému existují pravdivá tvrzení, která v systému nelze dokázat. Toto téma dále rozvíjelo ve 30. letech 20. století Alonzo Church a Alan Turing, který na jedné straně dal dvě nezávislé, ale rovnocenné definice vypočítatelnost a na druhé straně uvedli konkrétní příklady nerozhodnutelných otázek.
První implementace
Krátce poté, co druhá světová válka, byly k dispozici první počítače pro všeobecné použití. V roce 1954 Martin Davis naprogramovaný Presburgerův algoritmus pro a JOHNNIAC počítač s elektronkou na internetu Princetonský institut pro pokročilé studium. Podle Davise „jeho velkým triumfem bylo dokázat, že součet dvou sudých čísel je sudý“.[7][8] Ambicióznější byl Stroj logické teorie v roce 1956 systém odpočtů pro výroková logika z Principia Mathematica, vyvinutý společností Allen Newell, Herbert A. Simon a J. C. Shaw. Stroj Logic Theory Machine, který běží také na JOHNNIAC, vytvořil důkazy z malé sady výrokových axiomů a tří pravidel pro dedukci: modus ponens (, výroková) proměnná substituce a nahrazení vzorců jejich definicí. Systém používal heuristické vedení a dokázal dokázat 38 z prvních 52 vět z Principia.[7]
„Heuristický“ přístup stroje logické teorie se pokusil napodobit lidské matematiky a nemohl zaručit, že pro každou platnou větu lze najít důkaz, a to i v zásadě. Naproti tomu jiné, systematičtější algoritmy dosáhly, alespoň teoreticky, úplnost pro logiku prvního řádu. Počáteční přístupy se opíraly o výsledky Herbranda a Skolema při převodu vzorce prvního řádu na postupně větší sady výrokové vzorce vytvořením instance proměnných s výrazy z Herbrandův vesmír. Výrokové vzorce by pak mohly být zkontrolovány z hlediska neuspokojivosti pomocí řady metod. Gilmorův program použil konverzi na disjunktivní normální forma, forma, ve které je zřejmá uspokojivost vzorce.[7][9]
Rozhodnutelnost problému
V závislosti na základní logice se problém rozhodování o platnosti vzorce liší od triviálního po nemožný. Pro častý případ výroková logika, problém je rozhodující, ale co-NP-kompletní, a proto se předpokládá, že existují pouze algoritmy exponenciálního času pro úkoly obecného důkazu. Pro predikátový počet prvního řádu, Gödelova věta o úplnosti uvádí, že věty (prokazatelné výroky) jsou přesně logicky platné dobře formulované vzorce, takže identifikace platných vzorců je rekurzivně spočetné: vzhledem k neomezeným zdrojům lze nakonec dokázat jakýkoli platný vzorec. Nicméně, neplatný vzorce (ty, které jsou ne dané teorií), nelze vždy rozpoznat.
Výše uvedené platí pro teorie prvního řádu, jako např Peano aritmetika. U konkrétního modelu, který lze popsat teorií prvního řádu, však mohou být některá tvrzení pravdivá, ale nerozhodná v teorii použité k popisu modelu. Například tím, že Gödelova věta o neúplnosti, víme, že každá teorie, jejíž správné axiomy platí pro přirozená čísla, nemůže dokázat, že všechny výroky prvního řádu jsou pravdivé pro přirozená čísla, i když je povoleno, aby byl seznam správných axiomů nekonečný výčet. Z toho vyplývá, že automatizovaný tester teorémů neskončí při hledání důkazu právě tehdy, když je vyšetřovaný výrok v použité teorii nerozhodnutelný, i když je pravdivý v modelu zájmu. Navzdory tomuto teoretickému limitu dokážou věty v praxi v praxi vyřešit mnoho těžkých problémů, a to i v modelech, které nejsou plně popsány žádnou teorií prvního řádu (například celá čísla).
Související problémy
Jednodušší, ale související problém je ověření důkazu, kde je existující důkaz věty ověřen jako platný. K tomu je obecně požadováno, aby každý jednotlivý krok kontroly mohl být ověřen a primitivní rekurzivní funkce nebo program, a proto je problém vždy rozhodnutelný.
Vzhledem k tomu, že důkazy generované automatizovanými prověrkami teorémů jsou obvykle velmi velké, představuje problém důkaz komprese je zásadní a byly vyvinuty různé techniky, jejichž cílem je zmenšit výstup proveru a následně jej snáze pochopit a zkontrolovat.
Důkazní asistenti vyžadovat, aby lidský uživatel poskytoval rady systému. V závislosti na stupni automatizace lze tester v zásadě omezit na kontrolu kontroly, přičemž uživatel poskytne důkaz formálním způsobem, nebo lze provést významné kontrolní úlohy automaticky. Interaktivní testery se používají pro různé úkoly, ale i plně automatické systémy prokázaly řadu zajímavých a tvrdých vět, včetně alespoň jedné, která se dlouhodobě vyhýbá lidským matematikům, konkrétně Robbinsova domněnka.[10][11] Tyto úspěchy jsou však sporadické a práce na náročných problémech obvykle vyžaduje zkušeného uživatele.
Někdy se rozlišuje mezi dokazováním teorémů a jinými technikami, kde se proces považuje za dokazování teorémů, pokud se skládá z tradičního důkazu, počínaje axiomy a vytvářením nových inferenčních kroků pomocí pravidel inference. Mezi další techniky patří kontrola modelu, který v nejjednodušším případě zahrnuje výčet hrubou silou mnoha možných stavů (ačkoli skutečná implementace kontrolních modelů vyžaduje hodně chytrosti a neomezuje se pouze na hrubou sílu).
Existují systémy dokazující hybridní věty, které používají kontrolu modelu jako pravidlo odvození. Existují také programy, které byly napsány, aby dokázaly určitou větu, s (obvykle neformálním) důkazem, že pokud program skončí s určitým výsledkem, je věta pravdivá. Dobrým příkladem toho byl strojem podporovaný důkaz čtyřbarevná věta, což bylo velmi kontroverzní, protože první tvrdil matematický důkaz, který bylo v zásadě nemožné ověřit lidmi kvůli enormní velikosti výpočtu programu (takové důkazy se nazývají nezměřitelné důkazy ). Dalším příkladem programově podporovaného důkazu je ten, který ukazuje, že hra o Připojte čtyři vždy může vyhrát první hráč.
Průmyslové použití
Komerční využití automatizovaného dokazování teorémů je většinou soustředěno do design integrovaného obvodu a ověření. Protože Chyba Pentium FDIV komplikované jednotky s plovoucí desetinnou čárkou moderních mikroprocesorů bylo navrženo s mimořádnou kontrolou. AMD, Intel a další používají automatizované dokazování teorémů k ověření, že rozdělení a další operace jsou správně implementovány v jejich procesorech.
Dokazování věty prvního řádu
![]() | Tato sekce potřebuje další citace pro ověření.Červenec 2020) (Zjistěte, jak a kdy odstranit tuto zprávu šablony) ( |
Na konci šedesátých let začaly agentury, které financují výzkum v automatickém dedukci, zdůrazňovat potřebu praktických aplikací. Jednou z prvních plodných oblastí byla oblast ověření programu přičemž na problém ověřování správnosti počítačových programů v jazycích, jako jsou Pascal, Ada atd., byly použity věty prvního řádu. Pozoruhodný mezi systémy včasného ověřování programů byl Stanford Pascal Verifier vyvinutý David Luckham na Stanfordská Univerzita. To bylo založeno na Stanford Resolution Prover vyvinutém také ve Stanfordu pomocí John Alan Robinson je rozlišení zásada. Jednalo se o první automatizovaný dedukční systém, který demonstroval schopnost řešit matematické problémy, které byly oznámeny v oznámeních Americké matematické společnosti před oficiálním zveřejněním řešení.[Citace je zapotřebí ]
První objednávka dokazování teorémů je jedním z nejzralejších podpolí automatizovaného dokazování teorémů. Logika je dostatečně expresivní, aby umožnila specifikaci libovolných problémů, často přiměřeně přirozeným a intuitivním způsobem. Na druhou stranu je stále polorozhodovatelný a byla vyvinuta řada zdravých a úplných kalkulů plně automatizované systémy.[Citace je zapotřebí ] Expresivnější logiky, jako např Logiky vyššího řádu, umožňují pohodlné vyjádření širšího rozsahu problémů než logika prvního řádu, ale věta dokazující tyto logiky je méně rozvinutá.[12][13]
Srovnávací hodnoty, soutěže a zdroje
Kvalita implementovaných systémů těží z existence velké knihovny standardních srovnávacích příkladů - Knihovny problémů Tisíce problémů pro poskytovatele teorémů (TPTP)[14] - stejně jako z Soutěž systému CADE ATP (CASC), každoroční soutěž systémů prvního řádu pro mnoho důležitých tříd problémů prvního řádu.
Níže jsou uvedeny některé důležité systémy (všechny vyhrály alespoň jednu soutěžní divizi CASC).
- E je vysoce výkonný prover pro plnou logiku prvního řádu, ale postavený na čistě rovnicový počet, původně vyvinuté ve skupině automatizovaného uvažování Technická univerzita v Mnichově pod vedením Wolfgang Bibel a nyní v Bádensko-Württemberská družstevní státní univerzita v Stuttgart.
- Vydra, vyvinutý na Argonne National Laboratory, je založeno na rozlišení prvního řádu a paramodulace. Vydra byla od té doby nahrazena Prover9, který je spárován s Mace4.
- SETHEO je vysoce výkonný systém založený na cílených cílech eliminace modelu kalkul, původně vyvinutý týmem pod vedením Wolfgang Bibel. E a SETHEO byly kombinovány (s jinými systémy) v kompozitním testovacím teorému E-SETHEO.
- Upír byl původně vyvinut a implementován v Manchester University Andrei Voronkov a Krystof Hoder. Nyní jej vyvíjí rostoucí mezinárodní tým. Pravidelně od roku 2001 vyhrála divizi FOF (mimo jiné divize) na soutěži CADE ATP System.
- Waldmeister je specializovaný systém pro jednotovou rovnici logiky prvního řádu vyvinutý společností Arnim Buch a Thomas Hillenbrand. Čtrnáct po sobě jdoucích let (1997–2010) vyhrál divizi CASC UEQ.
- SPASS je tester logiky věty prvního řádu s rovností. To je vyvíjeno výzkumnou skupinou Automation of Logic, Max Planck Institute for Computer Science.
The Věta Prover Museum je iniciativa na zachování zdrojů testovacích systémů vět pro budoucí analýzu, protože se jedná o důležité kulturní / vědecké artefakty. Má zdroje mnoha výše zmíněných systémů.
Populární techniky
- Rozlišení prvního řádu s unifikace
- Vyřazení modelu
- Metoda analytických obrazů
- Superpozice a termín přepis
- Kontrola modelu
- Matematická indukce[15]
- Binární rozhodovací diagramy
- DPLL
- Sjednocení vyšších řádů
Softwarové systémy
název | Typ licence | webová služba | Knihovna | Samostatný | Poslední aktualizace (RRRR-mm-dd formát ) |
---|---|---|---|---|---|
ACL2 | 3-klauzule BSD | Ne | Ne | Ano | Květen 2019 |
Prover9 / vydra | Veřejná doména | Přes Systém na TPTP | Ano | Ne | 2009 |
Metis | Licence MIT | Ne | Ano | Ne | 1. března 2018 |
MetiTarski | MIT | Přes Systém na TPTP | Ano | Ano | 21. října 2014 |
Žert | GPLv2 | Ano | Ano | Ne | 15. května 2015 |
PVS | GPLv2 | Ne | Ano | Ne | 14. ledna 2013 |
Lev II | Licence BSD | Přes Systém na TPTP | Ano | Ano | 2013 |
EQP | ? | Ne | Ano | Ne | Květen 2009 |
SMUTNÝ | GPLv3 | Ano | Ano | Ne | 27. srpna 2008 |
PhoX | ? | Ne | Ano | Ne | 28. září 2017 |
KeYmaera | GPL | Přes Webový start Java | Ano | Ano | 11. března 2015 |
Gandalfe | ? | Ne | Ano | Ne | 2009 |
E | GPL | Přes Systém na TPTP | Ne | Ano | 4. července 2017 |
SNARK | Veřejná licence Mozilla 1.1 | Ne | Ano | Ne | 2012 |
Upír | Upírská licence | Přes Systém na TPTP | Ano | Ano | 14. prosince 2017 |
Věta prokazující systém (TPS) | Smlouva o distribuci TPS | Ne | Ano | Ne | 4. února 2012 |
SPASS | Licence FreeBSD | Ano | Ano | Ano | Listopadu 2005 |
IsaPlanner | GPL | Ne | Ano | Ano | 2007 |
Klíč | GPL | Ano | Ano | Ano | 11. října 2017 |
Princezna | lgpl v2.1 | Přes Webový start Java a Systém na TPTP | Ano | Ano | 27. ledna 2018 |
iProver | GPL | Přes Systém na TPTP | Ne | Ano | 2018 |
Věta meta | Freeware | Ne | Ne | Ano | Duben 2020 |
Poskytovatel věty Z3 | Licence MIT | Ano | Ano | Ano | 19. listopadu 2019 |
Svobodný software
- Alt-Ergo
- Automath
- CVC
- E ([2] )
- GKC
- Stroj Gödel
- iProver
- IsaPlanner
- Prověřovač teorémů KED[16]
- leanCoP[17]
- Lev II ([3] )
- LCF
- Logické nástroje aplikace prohlížeče
- LoTREC[18]
- MetaPRL[19]
- Mizar
- NuPRL
- Paradox
- Prover9
- Zjednodušit (GPL'ed od 5/2011 )
- SPARK (programovací jazyk)
- Twelf
- Poskytovatel věty Z3
Proprietární software
- Acumen RuleManager (komerční produkt)
- ALLIGATOR (CC BY-NC-SA 2.0 UK)
- CARINE
- KIV (volně dostupné jako plugin pro Zatmění )
- Prover Plug-In (komerční motorový produkt)
- ProverBox
- Wolfram Mathematica[20]
- Výzkum Cyc
- Prokázat modulární aritmetickou větu
Viz také
Poznámky
- ^ Frege, Gottlob (1879). Begriffsschrift. Verlag Louis Neuert.
- ^ Frege, Gottlob (1884). Die Grundlagen der Arithmetik (PDF). Vratislav: Wilhelm Kobner. Archivovány od originál (PDF) dne 26. 9. 2007. Citováno 2012-09-02.
- ^ Bertrand Russell; Alfred North Whitehead (1910–1913). Principia Mathematica (1. vyd.). Cambridge University Press.
- ^ Bertrand Russell; Alfred North Whitehead (1927). Principia Mathematica (2. vyd.). Cambridge University Press.
- ^ Herbrand, Jaques (1930). Obnovuje sur la théorie de la démonstration.
- ^ Presburger, Mojżesz (1929). „Über die Vollständigkeit eines gewissen Systems der Arithmetik ganzer Zahlen, in welchem die Dodatek jako další operace hervortritt“. Comptes Rendus du I Congrès de Mathématiciens des Pays Slaves. Warszawa: 92–101.
- ^ A b C d Davis, Martin (2001), „Raná historie automatizovaného odpočtu“, v Robinson, Alan; Voronkov, Andreji (eds.), Příručka automatizovaného uvažování, 1, Elsevier)
- ^ Bibel, Wolfgang (2007). „Raná historie a perspektivy automatizovaného odpočtu“ (PDF). Ki 2007. LNAI. Springer (4667): 2–18. Citováno 2. září 2012.
- ^ Gilmore, Paul (1960). „Důkazový postup pro teorii kvantifikace: její zdůvodnění a realizace“. IBM Journal of Research and Development. 4: 28–35. doi:10.1147 / kolo 41.0028.
- ^ W.W. McCune (1997). „Řešení Robbinsova problému“. Journal of Automated Reasoning. 19 (3): 263–276. doi:10.1023 / A: 1005843212881.
- ^ Gina Kolata (10. prosince 1996). „Počítačový matematický důkaz ukazuje rozumnou sílu“. The New York Times. Citováno 2008-10-11.
- ^ Kerber, Manfred. "Jak dokázat věty vyššího řádu v logice prvního řádu." (1999).
- ^ Benzmüller, Christoph a kol. "LEO-II - kooperativní automatický testovací teorém pro klasickou logiku vyššího řádu (popis systému) "Mezinárodní společná konference o automatizovaném uvažování. Springer, Berlín, Heidelberg, 2008."
- ^ Sutcliffe, Geoff. „Knihovna problémů TPTP pro automatické ověřování vět“. Citováno 15. července 2019.
- ^ Bundy, Alan. Automatizace důkazu matematickou indukcí. 1999.
- ^ Artosi, Alberto, Paola Cattabriga a Guido Governatori. "Ked: Prokazatel deontické věty „Jedenáctá mezinárodní konference o logickém programování (ICLP’94). 1994.
- ^ Otten, Jens; Bibel, Wolfgang (2003). „LeanCoP: dokazování věty o štíhlém připojení“. Journal of Symbolic Computation. 36 (1–2): 139–161. doi:10.1016 / S0747-7171 (03) 00037-3.
- ^ del Cerro, Luis Farinas a kol. "Lotrec: obecný tablo prover pro modální a popisovou logiku "Mezinárodní společná konference o automatizovaném uvažování. Springer, Berlín, Heidelberg, 2001."
- ^ Hickey, Jason a kol. "MetaPRL - modulární logické prostředí "Mezinárodní konference o větě prokazující logiku vyšších řádů. Springer, Berlín, Heidelberg, 2003."
- ^ [1] Dokumentace Mathematica
Reference
- Chin-Liang Chang; Richard Char-Tung Lee (1973). Prokazování symbolické logiky a mechanické věty. Akademický tisk.
- Loveland, Donald W. (1978). Automatizované ověřování vět: Logický základ. Fundamental Studies in Computer Science Volume 6. North-Holland Publishing.
- Luckham, David (1990). Programování se specifikacemi: An Introduction to Anna, A Language for Specifying Ada Programmes. Springer-Verlag Texts and Monographs in Computer Science, 421 pp. ISBN 978-1461396871.
- Gallier, Jean H. (1986). Logika pro informatiku: Základy automatického ověřování věty. Vydavatelé Harper & Row (K dispozici ke stažení zdarma).
- Duffy, David A. (1991). Principy automatizovaného dokazování vět. John Wiley & Sons.
- Wos, Larry; Overbeek, Ross; Lusk, Ewing; Boyle, Jim (1992). Automatizované uvažování: Úvod a aplikace (2. vyd.). McGraw – Hill.
- Alan Robinson; Andrei Voronkov, eds. (2001). Příručka automatizovaného uvažování, svazek I a II. Elsevier a MIT Stiskněte.
- Fitting, Melvin (1996). Logika prvního řádu a automatické ověřování teorémů (2. vyd.). Springer.