Isabelle (asistentka) - Isabelle (proof assistant)
![]() Isabelle / jEdit běží dál Operační Systém Mac | |
Původní autoři | Lawrence Paulson |
---|---|
Vývojáři | Univerzita v Cambridge a Technická univerzita v Mnichově et al. |
První vydání | 1986[1] |
Stabilní uvolnění | 2019 / červen 2019 |
Napsáno | Standardní ML a Scala |
Operační systém | Linux, Okna, Mac OS X |
Typ | Matematika |
Licence | Licence BSD |
webová stránka | isabelle |
The Isabelle[A] automatizovaný testovací teorém je interaktivní věta prover, a proveror věty vyššího řádu (HOL). Je to LCF styl důkaz věty (napsán v Standardní ML ). Je tedy založen na malém logickém jádru (jádře), které zvyšuje důvěryhodnost důkazů, aniž by vyžadovalo (přesto podporuje) explicitní objekty důkazů.
Funkce
Isabelle je obecná: poskytuje a meta-logika (slabý teorie typů ), který se používá k zakódování logiky objektů jako logika prvního řádu (FOL), logika vyššího řádu (HOL) nebo Teorie množin Zermelo – Fraenkel (ZFC). Nejčastěji používanou logikou objektů je Isabelle / HOL, ačkoli v Isabelle / ZF byl dokončen významný vývoj teorie množin. Isabellina hlavní důkazní metoda je verze vyššího řádu rozlišení, na základě vyššího řádu unifikace.
Přestože je Isabelle interaktivní, nabízí účinné nástroje automatického uvažování, například a přepis termínu motor a tablo prover, různé rozhodovací postupy a prostřednictvím Perlík rozhraní pro automatizaci proof, externí teorie uspokojivosti modulo (SMT) řešitelé (včetně CVC4 ) a rozlišení -na základě automatizované věty provers (ATP), včetně E a SPASS (dále jen Metis[b] proof metoda rekonstruuje důkazy o rozlišení generované těmito ATP).[2] Je také vybaven dvěma Modelka nálezci (protiklad generátory): Nitpick[3] a Nunchaku.[4]
Funkce Isabelle národní prostředí což jsou moduly, které strukturují velké nátisky. Národní prostředí opravuje typy, konstanty a předpoklady v rámci zadaného rozsahu[3] aby se nemuseli opakovat pro všechny lemma.
Isar ("srozumitelné poloautomatické uvažování") je Isabellin formální důkazní jazyk. Je inspirován Systém Mizar.[3]
Isabelle byla použita k formalizaci mnoha vět z matematika a počítačová věda, jako Gödelova věta o úplnosti Gödelova věta o konzistenci axiom volby, věta o prvočísle, správnost bezpečnostní protokoly a vlastnosti sémantika programovacího jazyka. Mnoho z formálních důkazů je uchováváno v archivu formálních důkazů, který obsahuje (od roku 2019) nejméně 500 článků s celkem více než 2 miliony řádků důkazů.[5]
Prokazatel věty Isabelle je svobodný software, vydané pod revidovaným Licence BSD.
Isabelle byla jmenována Lawrence Paulson po Gérard Huet dcera.[6]
Příklad důkazu
Isabelle umožňuje, aby byly důkazy psány dvěma různými styly: procesní a deklarativní. Procesní důkazy specifikují řadu taktika (dokazování věty funkce / postupy ) použít; zatímco odrážejí postup, který by lidský matematik mohl použít k prokázání výsledku, jsou obvykle těžko čitelné, protože nepopisují výsledek těchto kroků. Deklarativní důkazy (podporované Isabellinou jazykovou verzí, Isar) na druhé straně specifikují skutečné matematické operace, které mají být provedeny, a jsou proto snadněji čitelné a kontrolovatelné lidmi.
Procedurální styl byl v posledních verzích Isabelle zastaralý.
Například deklarativní důkaz v rozporu v Isarovi druhá odmocnina ze dvou není racionální lze psát následovně.
teorém sqrt2_not_rational: „sqrt 2 ∉ ℚ“důkaz nechat ? x = „sqrt 2“ převzít „? x ∈ ℚ“ pak získat m n :: nat kde sqrt_rat: „¦? X¦ = m / n“ a nejnižší termíny: "coprime m n" podle (pravidlo Rats_abs_nat_div_natE) proto „m ^ 2 =? x ^ 2 * n ^ 2“ podle (auto simp add: power2_eq_square) proto eq: „m ^ 2 = 2 * n ^ 2“ použitím of_nat_eq_iff power2_eq_square podle rychlá síla proto „2 dvd m ^ 2“ podle simp proto „2 dvd m“ podle simp mít „2 dvd n“ důkaz - z ‹2 dvd m› získat k kde „m = 2 * k“ .. s ekv mít „2 * n ^ 2 = 2 ^ 2 * k ^ 2“ podle simp proto „2 dvd n ^ 2“ podle simp tím pádem „2 dvd n“ podle simp qed s ‹2 dvd m› mít „2 dvd gcd m n“ podle (pravidlo gcd_greatest) s nejnižší_podmínky mít „2 dvd 1“ podle simp tím pádem Nepravdivé použitím lichý podle výbuchqed
Aplikace
Isabelle byla zvyklá pomáhat formální metody pro specifikaci, vývoj a ověření softwarových a hardwarových systémů.
- V roce 2009 ověřil projekt L4 NICTA předložil první formální důkaz funkční správnosti jádra univerzálního operačního systému:[7] seL4 (zabezpečený vestavěný L4 ) mikrokernel. Důkaz je sestrojen a zkontrolován v Isabelle / HOL a obsahuje více než 200 000 řádků zkušebního skriptu k ověření 7500 řádků C. Ověření zahrnuje kód, design a implementaci a hlavní teorém uvádí, že kód C správně implementuje formální specifikaci jádro. Důkaz odhalil 144 chyb v rané verzi C kódu jádra seL4 a asi 150 problémů v každém designu a specifikaci.
- Programovací jazyk Lehká Java bylo prokázáno typový zvuk v Isabelle.[8]
Larry Paulson udržuje seznam výzkumných projektů kteří používají Isabelle.
Alternativy
Několik důkazní asistenti poskytují podobné funkce jako Isabelle, včetně:
- Coq, podobný systém napsaný v OCaml
- HOL, podobně jako implementace HOL od Isabelle
- Opírat se, podobný systém napsaný v C ++
- Systém Mizar
- Metamath
- Prover9
Poznámky
Reference
- ^ Paulson, L. C. (1986). "Přirozený odpočet jako rozlišení vyššího řádu". The Journal of Logic Programming. 3 (3): 237. arXiv:cs / 9301104. doi:10.1016/0743-1066(86)90015-4.
- ^ Jasmin Christian Blanchette, Lukas Bulwahn, Tobias Nipkow, „Automatická kontrola a deaktivace v Isabelle / HOL“, in: Cesare Tinelli, Viorica Sofronie-Stokkermans (eds.), Mezinárodní sympozium o hranicích kombinovaných systémů - FroCoS 2011, Springer, 2011.
- ^ A b C Jasmin Christian Blanchette, Mathias Fleury, Peter Lammich & Christoph Weidenbach, „Ověřený rámec SAT Solver s funkcí Learn, Forget, Restart a Incrementality“, Journal of Automated Reasoning 61:333–365 (2018).
- ^ Andrew Reynolds, Jasmin Christian Blanchette, Simon Cruanes, Cesare Tinelli, "Hledání modelu pro rekurzivní funkce v SMT", in: Nicola Olivetti, Ashish Tiwari (eds.), 8. mezinárodní společná konference o automatizovaném uvažování, Springer, 2016.
- ^ Eberl, Manuel; Klein, Gerwin; Nipkow, Tobias; Paulson, Larry; Thiemann, René. „Archiv formálních důkazů“. Citováno 22. října 2019.
- ^ Gordon, Mike (16. 11. 1994). "1.2 Historie". Isabelle a HOL. Cambridge AR Research (The Automated Reasoning Group). Citováno 2016-04-28.
- ^ Klein, Gerwin; Elphinstone, Kevin; Heiser, Gernot; Andronick, červen; Kohout, David; Derrin, Philip; Elkaduwe, Dhammika; Engelhardt, Kai; Kolanski, Rafal; Norrish, Michael; Sewell, Thomas; Tuch, Harvey; Winwood, Simon (říjen 2009). "seL4: Formální ověření jádra OS" (PDF). 22. sympozium ACM o zásadách operačního systému. Big Sky, Montana, USA. 207–200.
- ^ afp.sourceforge.net
Další čtení
- Lawrence C. Paulson, „Založení poskytovatele obecné věty“, Journal of Automated Reasoning, Svazek 5, číslo 3 (září 1989), strany: 363–397, ISSN 0168-7433.
- Lawrence C. Paulson a Tobias Nipkow, „Výukový program Isabelle a uživatelská příručka“, 1990.
- M. A. Ozols, K. A. Eastaughffe a A. Cant, „DOVE: Design Oriented Verification and Evaluation“, Sborník AMAST 97, M. Johnson, redaktor, Sydney, Austrálie. Lecture Notes in Computer Science (LNCS) Vol. 1349, Springer Verlag, 1997.
- Tobias Nipkow, Lawrence C. Paulson, Markus Wenzel, „Isabelle / HOL - důkazový asistent pro logiku vyšších řádů“, 2020.