Automatizuotas teoremos įrodymas

Straipsnis iš Enciklopedijos Lietuvai ir Pasauliui (ELIP).
 Broom icon.svg  Šį puslapį ar jo dalį reikia sutvarkyti pagal Enciklopedijos standartus.
Jei galite, sutvarkykite; apie sutvarkymą galite pranešti specialiame Enciklopedijos projekte.

Automatizuotas teoremos įrodymas (ATĮ) arba automatizavimo išvada - šiuo metu labiausiai išplėtotas automatizuoto pagrindimo (AP) pogrupis, paremtas matematinių teoremų įrodymu kompiuterine programa.

Problemos sprendimas

Priklausomai nuo logikos, kuria vadovaujamasi, gali kilti menka ar kur kas sudėtingesnė problema sprendžiant, ar formulė tinkama ar ne. Dėl dažnai pasitaikančių matematinės logikos atvejų, problema yra išsprendžiama, tačiau neturinti ND baigtumo (Nedeterminuotasis Daugianaris laikas). Taigi, manoma, kad tik eksponentinio laiko algoritmai tinka spręsti bendrąsias įrodymų užduotis. Kalbant apie pirmojo lygmens predikatinių skaičiavimus, be jokių ("tinkamų") aksiomų, Godelio užbaigtumo teorema teigia, kad teoremos (įrodomi teiginiai) yra visiškai logiškai pagrįstos gerai sudarytos formulės. Vadinasi, tinkamų formulių nustatymas yra rekursiškai išvardijamas (recursively enumerable): turint neribotus išteklius, bet kuri svarbi formulė galiausiai gali būti įrodyta. Tačiau, neteisingos formulės (kurios yra nesusijusios su tam tikra teorija) ne visada gali būti suvoktos. Pagal Godelio neužbaigtumo teoremą, atitinkama oficiali teorija, į kuria įeina pirmojo lygmens natūralių skaičių teorija (turinti tam tikras "tinkamas aksiomas"), apima teisingus teiginius, kurių neįmanoma įrodyti. Tokiais atvejais, gali nepavykti įrodyti automatizavimo teoremos, kol bus atliekama patikra. Nepaisant šių teorinių apribojimų, praktikoje teoremos įrodymas gali išspręsti daugelį sudėtingų problemų, netgi ir šių, paremtų neišsprendžiama logika.

Susijusios problemos

Paprastesnė, tačiau susijusi problema yra įrodymų patikrinimas, kai teoremos įrodymas yra pripažįstamas svariu. Šiuo atveju paprastai reikalaujama, kad kiekvieno įrodymo pakopa būtų patikrinama pagal primityvią rekursyvinę funkciją, todėl problema yra visada išsprendžiama. Interaktyvios teoremos įrodymas reikalauja, kad žmogus pateiktų užuominų sistemai. Priklausomai nuo automatizavimo lygio, patikra gali būti iš esmės sutrumpinta iki įrodymo tikrinimo, kai vartotojas pateikia įrodymą formaliu būdu arba svarbių įrodymų užduotys atliekamos automatiškai. Interaktyvus įrodymas naudojamas įvairioms užduotims atlikti, tačiau daugelis automatinių sistemų įrodė daugybę įdomių ir sunkių teoremų, įskaitant keletą tokių, kurių matematikams ilgą laiką nepavyko įrodyti. Tačiau, tokie atvejai yra pavieniai, o sprendžiant sunkias problemas dažniausiai reikia patyrusio vartotojo. Kitas skirtumas yra tarp teoremos įrodymo ir kitų metodikų, kuriose procesas yra laikomas teoremos įrodymu jei jis susideda iš tradicinio įrodymo, pradedant aksiomomis ir pateikiant naujos išvados žingsnius naudojantis išvados taisyklėmis. Kiti metodai apima modelio tikrinimą, kuris yra ekvivalentiškas daugelio galimų padėčių išvardijimui jėgos metodu (nors realaus modelio įgyvendinimo patikrinimas reikalauja didesnio sumanumo ir taip paprastai nesutrumpinamas iki jėgos metodo). Yra mišrių teoremos įrodymo sistemų, kurios naudoja modelio patikrinimą kaip išvados darymo taisyklę. Taip pat yra programų, kurios buvo sukurtos tam tikrų teoremų įrodymui. Jos pateikia įrodymą (dažnai neformalų), kuris parodo, kad programai gavus tam tikrą rezultatą, teorema yra teisinga. Geras tokios programos darbo pavyzdys yra mašininis keturių spalvų teoremos įrodymas, kuris buvo labai prieštaringas kaip ir pirmasis pasiektas matematinis įrodymas. Jo žmonėms buvo iš esmės neįmanoma patvirtinti dėl milžiniškų programos atliktų skaičiavimų (tokie įrodymai vadinami netiriamais). Kitas pavyzdys galėtų būti įrodymas, kad žaidime ,,Sujunk keturis” (angl. Connect Four) visada laimi pirmasis žaidėjas.

Pramoninis naudojimas

Komercijai ATĮ daugiausiai naudojamas integrinės schemos projektavimui ir atestacijai. Nuo Pentuim FDIV klaidos, sudėtingos modernių mikroprocesorių slankiojo kablelio grandys buvo projektuojamos ypatingai kruopščiai. Naujausiuose procesoriuose po AMD, Intel ir kitų, ATĮ buvo naudojamas patvirtinti, kad paskirstymas ir kiti procesai vyksta teisingai.

Pirmojo lygmens teoremos įrodymas

Pirmojo lygmens teoremos įrodymas yra vienas iš labiausiai išnagrinėtų automatizavimo teoremos įrodymo pogrupių. Logika yra pakankamai aiški, kad būtų galima natūraliai ir intuityviai patikslinti atsitiktines problemas. Kita vertus, problemos tik pusiau išsprendžiamos, todėl buvo sukurtas tam tikras skaičius garsų ir išbaigtų skaičiavimų, kurie leidžia veikti pilnai automatizuotoms sistemoms. Dar konkretesnė logika, pavyzdžiui, aukštesnės sekos arba modalinė, leidžia patogiai išreikšti įvairesnes problemas nei pirmojo lygmens logika, tačiau šių logikų teoremos įrodymas yra mažiau išplėtotas. Įgyvendintos sistemos kokybę gerina didžiulis standartinių kompiuterių sistemos darbo bandymų (standard benchmark) pavyzdžių rinkinys (,,Thousands of Problems for Theorem Provers” (TPTP) Nuoroda) taip pat ,,CADE ATP System Competition” (CASC) kasmetinis pirmojo lygmens sistemų konkurencijos forumas, skirtas daugeliui svarbių pirmojo lygio problemų klasių. Keletas svarbių sistemų (visos yra laimėjusios nors vieną CASC konkurencijos nominaciją) pateiktos žemiau:

  • E yra aukštos kokybės patikros programa, skirta pilnai pirmojo lygio logikai, bet pagrįsta vien tik lygčių skaičiavimu. Ji buvo sukurta Miuncheno technologijos universiteto automatinių motyvų grupėje.
  • Otter buvo sukurta Argono valstybinėje laboratorijoje. Ji yra pirmoji plačiai naudojama aukštos kokybės teoremos patikros programa, paremta pirmojo lygmens geba ir paramoduliais. ,,Otter” pakeitė ,,Prover9” programą, susijusią su ,,Mace4”.
  • SETHEO yra aukštos kokybės sistema paremta tikslingu modelio eliminavimo skaičiavimu. Sukurtas Miuncheno technologijos universiteto automatinių motyvų grupėje. ,,E” ir ,,SETHEO” buvo sujungtos (su kitomis sistemomis) į kombinuotos teoremos patikros programą ,,E-SETHEO”.
  • Vampire buvo sukurta ir realizuota Andrei’o Voronkovo iš Mančesterio universiteto kartu su Alexandre’u Riazanovu. Ši programa 8 kartus (1999, 2001-2007) laimėjo "pasaulio taurę už teoremos patikros programą" (,,CADE ATP System Competition”) prestižiniame CNF (MIX) divizione.
  • Waldmeister yra specializuota pirmojo lygio logikos vieneto-lygties sistema (specialized system for unit-equational first-order logic). Ji laimėjo apdovanojimą CASC UEQ divizione 10 metų iš eilės (1997-2006).

Deontinės teoremos įrodymas

Deontinė logika yra susijusi su normatyviniais teiginiais, naudojamais tokiose srityse kaip teisė, techninės instrukcijos ar kompiuterinės programos. Kitaip tariant, šie teiginiai yra komandų vertimai arba kasdieninės kalbos pareiškimai ,,turėtum” arba ,,privalai (nedaryti)”. Deontinis tokios logikos požymis reikalauja formalumo, kuris išplėstų pirmojo lygmens predikatinius skaičiavimus. Tą padaryti padeda priemonė ,,KED”.

Populiarios metodikos

  • Pirmosios eilės rezoliucija su suvienodinimu;
  • Efektyvumo teoremos įrodymas;
  • Modelio eliminavimas;
  • Analitiškai vaizdingas metodas (method of analytic tableaux);
  • Superpozicija ir termino perrašymas;
  • Modelio patikra;
  • Matematinė indukcija;
  • Dvinarė sprendimo diagrama;
  • DPLL algoritmas (angl. DPLL: Davis-Putnam-Logemann-Loveland);
  • Didesnės vertės suvienodinimas.

Taip pat skaitykite

  • Nemokama programinė įrananga
    • ACL2
    • Alt-Ergo
    • Automath
    • Coq
    • CVC
    • E
    • EQP
    • Gandalf
    • Gödel-machines
    • HOL
    • HOL Light
    • Isabelle
    • IsaPlanner
    • Jape
    • KED
    • KeY
    • KeYmaera
    • LCF
    • Leo II
    • LoTREC
    • MetaPRL
    • Matita
    • NuPRL
    • Otter
    • Paradox
    • PhoX
    • Prover9/Mace4
    • PVS
    • SAD
    • SNARK
    • SPASS
    • Tau
    • Theorema
    • Theorem Checker
  • Patentuota programinė įranga, įskaitant komercinius ir nekomercinius
    • Acumen RuleManager (commercial product)
    • Alligator
    • CARINE
    • KIV
    • Mizar
    • Prover Plug-In (commercial proof engine product)
    • ProverBox
    • ResearchCyc
    • Simplify
    • SPARK (programming language)
    • Spear modular arithmetic theorem prover
    • Theorem Proving System (TPS)
    • Twelf
    • Vampire/Vampyre
    • Waldmeister

Žymūs žmonės

  • Leo Bachmair, co-developer of the superposition calculus.
  • Woody Bledsoe, artificial intelligence pioneer.
  • Robert S. Boyer, co-author of the Boyer-Moore theorem prover, co-recipient of the Herbrand Award 1999.
  • Alan Bundy, University of Edinburgh, meta-level reasoning for guiding inductive proof, proof planning and recipient of 2007 IJCAI Award for Research Excellence, Herbrand Award, and 2003 Donald E. Walker Distinguished Service Award.
  • William McCune Argonne National Laboratory, author of Otter, the first high-performance theorem prover. Many important papers, recipient of the Herbrand Award 2000.
  • Hubert Comon, CNRS and now ENS Cachan. Many important papers.
  • Robert Constable, Cornell University. Important contributions to type theory, NuPRL.
  • Martin Davis, author of the "Handbook of Artificial Reasoning", co-inventor of the DPLL algorithm, recipient of the Herbrand Award 2005.
  • Branden Fitelson University of California at Berkeley. Work in automated discovery of shortest axiomatic bases for logic systems.
  • Harald Ganzinger, co-developer of the superposition calculus, head of the MPI Saarbrücken, recipient of the Herbrand Award 2004 (posthumous).
  • Michael Genesereth, Stanford University professor of Computer Science.
  • Keith Goolsbey chief developer of the Cyc inference engine.
  • Michael J. C. Gordon led the development of the HOL theorem prover.
  • Gerard Huet Term rewriting, HOL logics, Herbrand Award 1998
  • Robert Kowalski developed the connection graph theorem-prover and SLD resolution, the inference engine that executes logic programs.
  • Donald W. Loveland Duke University. Author, co-developer of the DPLL-procedure, developer of model elimination, recipient of the Herbrand Award 2001.
  • Norman Megill, developer of Metamath, and maintainer of its site at metamath.org, an online database of automatically verified proofs.
  • J Strother Moore, co-author of the Boyer-Moore theorem prover, co-recipient of the Herbrand Award 1999.
  • Robert Nieuwenhuis University of Barcelona. Co-developer of the superposition calculus.
  • Tobias Nipkow Technical University of Munich, contributions to (higher-order) rewriting, co-developer of the Isabelle, proof assistant
  • Ross Overbeek Argonne National Laboratory. Founder of The Fellowship for Interpretation of Genomes
  • Lawrence C. Paulson University of Cambridge, work on higher-order logic system, co-developer of the Isabelle proof assistant
  • David A. Plaisted University of North Carolina at Chapel Hill. Complexity results, contributions to rewriting and completion, instance-based theorem proving.
  • John Rushby Program Director - SRI International
  • J. Alan Robinson Syracuse University. Developed original resolution and unification based first order theorem proving, co-editor of the "Handbook of Automated Reasoning", recipient of the Herbrand Award 1996
  • Jürgen Schmidhuber Work on Gödel Machines: Self-Referential Universal Problem Solvers Making Provably Optimal Self-Improvements
  • Stephan Schulz, E theorem Prover.
  • Natarajan Shankar SRI International, work on decision procedures, little engines of proof, co-developer of PVS.
  • Mark Stickel SRI. Recipient of the Herbrand Award 2002.
  • Geoff Sutcliffe University of Miami. Maintainer of the TPTP collection, an organizer of the CADE annual contest.
  • Dolph Ulrich Purdue, Work on automated discovery of shortest axiomatic bases for systems.
  • Robert Veroff University of New Mexico. Many important papers.
  • Andrei Voronkov Developer of Vampire and Co-Editor of the "Handbook of Automated Reasoning"
  • Larry Wos Argonne National Laboratory. (Otter) Many important papers. Very first Herbrand Award winner (1992)
  • Wen-Tsun Wu Work in geometric theorem proving: Wu's method, Herbrand Award 1997

Taip pat skaitykite

  • Symbolic computation
  • Computer-aided proof
  • Automated reasoning
  • Formal verification
  • Logic programming
  • Proof checking
  • Model checking
  • Proof complexity
  • Computer algebra system
  • Program analysis (computer science)

Raštai

1. ^ W.W. McCune (1997). "Solution of the Robbins Problem". Journal of Automated Reasoning 19 (3). http://www.springerlink.com/content/h77246751668616h/. 2. ^ Gina Kolata (December 10, 1996). "Computer Math Proof Shows Reasoning Power". The New York Times. http://www.nytimes.com/library/cyber/week/1210math.html. Retrieved 2008-10-11. 3. ^ http://www.cs.miami.edu/~tptp/ 4. ^ Artosi, Alberto, Cattabriga, Paola and Governatori, Guido (1994-01-01). KED: A Deontic Theorem Prover. In: Biagioli, Carlo, Sartor, Giovanni and Tiscornia, Daniela Workshop on Legal Application of Logic Programming, Santa Margherita Ligure, Italy, (60-76).

Nuorodos

  • Chin-Liang Chang; Richard Char-Tung Lee (1973). Symbolic Logic and Mechanical Theorem Proving. Academic Press1.
  • Loveland, Donald W. (1978). Automated Theorem Proving: A Logical Basis. Fundamental Studies in Computer Science Volume 6. North-Holland Publishing.
  • Gallier, Jean H. (1986). Logic for Computer Science: Foundations of Automatic Theorem Proving. Harper & Row Publishers (Available for free download). http://www.cis.upenn.edu/~jean/gbooks/logic.html.
  • Duffy, David A. (1991). Principles of Automated Theorem Proving. John Wiley & Sons.
  • Wos, Larry; Overbeek, Ross; Lusk, Ewing; Boyle, Jim (1992). Automated Reasoning: Introduction and Applications (2nd ed.). McGraw-Hill.
  • Alan Robinson and Andrei Voronkov (eds.), ed (2001). Handbook of Automated Reasoning Volume I & II. Elsevier and MIT Press.
  • Fitting, Melvin (1996). First-Order Logic and Automated Theorem Proving (2nd ed.). Springer. http://comet.lehman.cuny.edu/fitting/.


Sudarytojai, rašytojai ir redaktoriai

Kitur naudojant ar cituojant šį straipsnį, būtina nurodyti jo sumanytojus, sudarytojus, rašytojus ir redaktorius.
  • Vitas Povilaitis – autorius ir redaktorius – 100% (+14333-50=14283 wiki spaudos ženklai).