Automatisierter Lehrsatz-Beweis (ATP) oder automatisierter Abzug, zurzeit das am meisten gut entwickelte Teilfeld des automatisierten Denkens (AR), sind der Beweis von mathematischen Lehrsätzen durch ein Computerprogramm.

Entscheidbarkeit des Problems

Abhängig von der zu Grunde liegenden Logik ändert sich das Problem, die Gültigkeit einer Formel zu entscheiden, vom trivialen bis Unmöglichen. Für den häufigen Fall der Satzlogik ist das Problem entscheidbar, aber, wie man glaubt, bestehen Co-NP-Complete, und folglich nur exponentialmalige Algorithmen für allgemeine Probeaufgaben. Für eine erste Ordnungsprädikat-Rechnung, ohne ("richtige") Axiome, stellt der Vollständigkeitslehrsatz von Gödel fest, dass die Lehrsätze (nachweisbare Behauptungen) genau die logisch gültigen gut gebildeten Formeln sind, ist so das Identifizieren gültiger Formeln rekursiv enumerable: In Anbetracht unbegrenzter Mittel kann jede gültige Formel schließlich bewiesen werden.

Jedoch können ungültige Formeln (diejenigen, die durch eine gegebene Theorie nicht zur Folge gehabt werden), nicht immer anerkannt werden. Außerdem enthält eine konsequente formelle Theorie, die die Theorie der ersten Ordnung der natürlichen Zahlen enthält (so bestimmte "richtige Axiome" habend) durch den Unvollständigkeitslehrsatz von Gödel, wahre Behauptungen, die nicht bewiesen werden können. In diesen Fällen kann ein automatisierter Lehrsatz prover scheitern zu enden, während er nach einem Beweis sucht. Trotz dieser theoretischen Grenzen, in der Praxis, kann Lehrsatz provers viele harte Probleme sogar in dieser unentscheidbaren Logik beheben.

Zusammenhängende Probleme

Ein einfacherer, aber verbunden, Problem ist Probeüberprüfung, wo ein vorhandener Beweis für einen Lehrsatz gültig bescheinigt wird. Dafür ist es allgemein erforderlich, dass jeder individuelle Probeschritt durch eine primitive rekursive Funktion oder Programm nachgeprüft werden kann, und folglich das Problem immer entscheidbar ist.

Seit den durch den automatisierten Lehrsatz erzeugten Beweisen sind provers normalerweise sehr groß, das Problem der Probekompression ist entscheidende und verschiedene Techniken zielend auf das Bilden der Produktion des prover kleiner, und folglich leichter verständlich und checkable, sind entwickelt worden.

Interaktiver Lehrsatz provers verlangt, dass ein menschlicher Benutzer Hinweise dem System gibt. Abhängig vom Grad der Automation kann der prover im Wesentlichen auf einen Probekontrolleur mit dem Benutzer reduziert werden, der den Beweis auf eine formelle Weise zur Verfügung stellt, oder bedeutende Probeaufgaben können automatisch durchgeführt werden. Interaktive provers werden für eine Vielfalt von Aufgaben verwendet, aber sogar vollautomatische Systeme haben mehrere interessante und harte Lehrsätze, einschließlich einiger bewiesen, die sich menschlichen Mathematikern seit langem entzogen haben. Jedoch sind diese Erfolge sporadisch, und die Arbeit an harten Problemen verlangt gewöhnlich einen tüchtigen Benutzer.

Ein anderer Unterschied wird manchmal zwischen Lehrsatz-Beweis und anderen Techniken gemacht, wo, wie man betrachtet, ein Prozess Lehrsatz ist, der sich erweist, ob es aus einem traditionellen Beweis besteht, mit Axiomen anfangend und neue Interferenzschritte mit Regeln der Schlussfolgerung erzeugend. Andere Techniken würden Musterüberprüfung einschließen, die, im einfachsten Fall, mit Enumeration der rohen Gewalt von vielen möglichen Staaten verbunden ist (obwohl die wirkliche Durchführung von Musterkontrolleuren viel Klugheit verlangt, und zur rohen Gewalt nicht einfach abnimmt).

Es gibt hybride Lehrsatz-Beweis-Systeme, die Modell verwenden, das als eine Interferenzregel überprüft. Es gibt auch Programme, die geschrieben wurden, um einen besonderen Lehrsatz, mit (gewöhnlich informell) Beweis dass zu beweisen, wenn das Programm mit einem bestimmten Ergebnis fertig ist, dann ist der Lehrsatz wahr. Ein gutes Beispiel davon war der maschinengeholfene Beweis des vier Farbenlehrsatzes, der als der erste geforderte mathematische Beweis sehr umstritten war, der im Wesentlichen unmöglich war, durch Menschen wegen der enormen Größe der Berechnung des Programms nachzuprüfen (solche Beweise werden non-surveyable Beweise genannt). Ein anderes Beispiel würde der Beweis sein, dass das Spiel Vier In Verbindung steht, ist ein Gewinn für den ersten Spieler.

Industriegebrauch

Der kommerzielle Gebrauch des automatisierten Lehrsatzes, der sich erweist, wird größtenteils im einheitlichen Stromkreis-Design und der Überprüfung konzentriert. Seit dem Pentium FDIV Programmfehler sind die komplizierten Schwimmpunkt-Einheiten von modernen Mikroprozessoren mit der zusätzlichen genauen Untersuchung entworfen worden. Heutzutage, AMD, verwenden Intel und andere automatisierten Lehrsatz, der sich erweist nachzuprüfen, dass Abteilung und andere Operationen in ihren Verarbeitern richtig durchgeführt werden.

Lehrsatz-Beweis der ersten Ordnung

Lehrsatz der ersten Ordnung, der sich erweist, ist eines der reifsten Teilfelder des automatisierten Lehrsatz-Beweises. Die Logik ist ausdrucksvoll genug, um die Spezifizierung von willkürlichen Problemen häufig auf eine vernünftig natürliche und intuitive Weise zu erlauben. Andererseits ist es noch, und mehrere halbentscheidbar Ton und ganze Rechnungen sind entwickelt worden, völlig automatisierte Systeme ermöglichend. Ausdrucksvollere Logik, wie höhere Ordnungslogik, erlaubt den günstigen Ausdruck einer breiteren Reihe von Problemen als die erste Ordnungslogik, aber Lehrsatz, der sich für diese Logik erweist, wird weniger gut entwickelt.

Abrisspunkte und Konkurrenzen

Die Qualität des durchgeführten Systems hat aus der Existenz einer großen Bibliothek von Standardabrisspunkt-Beispielen — den Tausenden von Problemen für den Lehrsatz Provers (TPTP) Problem-Bibliothek — sowie von CADE ATP System Competition (CASC), einer jährlichen Konkurrenz von Systemen der ersten Ordnung für viele wichtige Klassen von Problemen der ersten Ordnung einen Nutzen gezogen.

Einige wichtige Systeme (haben alle mindestens eine CASC Konkurrenz-Abteilung gewonnen), werden unten verzeichnet.

• E ist ein Hochleistungsprover für die volle Logik der ersten Ordnung, aber gebaut rein equational Rechnung, entwickelt in erster Linie in der automatisierten vernünftig urteilenden Gruppe der Technischen Universität Münchens.
• Otter, der am Argonne Nationalen Laboratorium entwickelt ist, ist der erste weit verwendete Hochleistungslehrsatz prover. Es basiert auf der Entschlossenheit der ersten Ordnung und Paramodulation. Otter ist durch Prover9 seitdem ersetzt worden, der mit Mace4 paarweise angeordnet wird.
• SETHEO ist ein auf der Absicht-geleiteten Musterbeseitigungsrechnung gestütztes Hochleistungssystem. Es wird in der automatisierten vernünftig urteilenden Gruppe der Technischen Universität Münchens entwickelt. E und SETHEO sind (mit anderen Systemen) im zerlegbaren Lehrsatz prover E-SETHEO verbunden worden.
• Vampir wird entwickelt und an der Universität von Manchester von Andrei Voronkov und Krystof Hoder früher auch von Alexandre Riazanov durchgeführt. Es hat den "Weltpokal für den Lehrsatz provers" (der CADE ATP Systemkonkurrenz) im renommiertsten CNF (MISCHUNG) Abteilung seit elf Jahren (1999, 2001-2010) gewonnen.
• Waldmeister ist ein Spezialsystem für die Logik der ersten Ordnung der Einheit-equational. Es hat den CASC UEQ Abteilung seit den letzten vierzehn Jahren (1997-2010) gewonnen.
• SPASS ist ein erster Ordnungslogiklehrsatz prover mit der Gleichheit. Das wird durch die Forschungsgruppenautomation der Logik, des Instituts von Max Planck für die Informatik entwickelt.

Populäre Techniken

• Entschlossenheit der ersten Ordnung mit der Vereinigung
• Magerer Lehrsatz, der sich erweist
• Musterbeseitigung
• Methode von analytischen Gemälden
• Überlagerung und Begriff, umschreibend
• Modell, das überprüft
• Mathematische Induktion
• Binäre Entscheidungsdiagramme
• DPLL
• Höherwertige Vereinigung

Vergleich

Siehe auch: Beweis assistant#Comparison und

Kostenlose Software

• Alt-Ergo
• Automathematik
• CVC
• Gödel-Maschinen
• iProver
• IsaPlanner
• KED Lehrsatz prover
• LCF
• LoTREC
• MetaPRL
• NuPRL
• Paradox
• Vereinfachen Sie (GPL'ed seitdem 5/2011)

Eigentumssoftware

• Scharfsinn RuleManager (kommerzielles Produkt)
• ALLIGATOR
• CARINE
• KIV
• Prover Einfügefunktion (kommerzielles Probemotorprodukt)
• ProverBox
• ResearchCyc
• SPRÜHEN SIE (Programmiersprache) FUNKEN
• Speer arithmetischer Modullehrsatz prover
• Twelf

Bemerkenswerte Leute

• Leo Bachmair, Co-Entwickler der Überlagerungsrechnung.
• Woody Bledsoe, Pionier der künstlichen Intelligenz.
• Robert S. Boyer, Mitverfasser des Lehrsatzes von Boyer-Moore prover, Co-Empfänger des Herbrand-Preises 1999.
• Alan Bundy, Universität Edinburghs, Meta-Niveau, das vernünftig urteilt, um induktiven Beweis, Probeplanung und Empfänger von 2007 IJCAI Award für die Forschungsvorzüglichkeit, Herbrand Award, und 2003 Donald E. Walker Distinguished Service Award zu führen.
• William McCune Argonne Nationales Laboratorium, Autor des Otters, der erste Hochleistungslehrsatz prover. Viele wichtige Papiere, Empfänger des Herbrand-Preises 2000.
• Hubert Comon, CNRS und jetzt ENS Cachan. Viele wichtige Papiere.
• Polizist von Robert Lee, Universität von Cornell. Wichtige Beiträge zur Typ-Theorie, NuPRL.
• Martin Davis, Autor des "Handbuches des Künstlichen Denkens", Co-Erfinder des DPLL Algorithmus, Empfänger des Herbrand-Preises 2005.
• Universität von Branden Fitelson Kaliforniens an Berkeley. Arbeit in der automatisierten Entdeckung von kürzesten axiomatischen Basen für Logiksysteme.
• Harald Ganzinger, Co-Entwickler der Überlagerungsrechnung, Leiter des MPI Saarbrücken, Empfänger des Herbrand-Preises (postumer) 2004.
• Michael Genesereth, Ordentlicher Professor von Stanford der Informatik.
• Hauptentwickler von Keith Goolsbey des Interferenzmotors von Cyc.
• Michael J. C. Gordon hat die Entwicklung des HOL Lehrsatzes prover geführt.
• Gérard Huet Term, der, HOL Logik, Herbrand Preis 1998 umschreibt.
• Robert Kowalski hat den Verbindungsgraph-Lehrsatz-prover und die SLD Entschlossenheit, der Interferenzmotor entwickelt, der Logikprogramme durchführt.
• Herzog von Donald W. Loveland Universität. Autor, Co-Entwickler des DPLL-Verfahrens, Entwickler der Musterbeseitigung, Empfänger des Herbrand-Preises 2001.
• Norman Megill, Entwickler von Metamath, und maintainer seiner Seite an metamath.org, eine Online-Datenbank automatisch nachgeprüfter Beweise.
• J Strother Moore, Mitverfasser des Lehrsatzes von Boyer-Moore prover, Co-Empfänger des Herbrand-Preises 1999.
• Universität von Robert Nieuwenhuis Barcelonas. Co-Entwickler der Überlagerungsrechnung.
• Tobias Nipkow von der Technischen Universität Münchens, Beiträge zum (höherwertigen) Neuschreiben, Co-Entwickler des Probehelfers von Isabelle
• Ross Overbeek Argonne nationales Laboratorium. Gründer der Kameradschaft für die Interpretation von Genomen
• Lawrence C. Paulson von der Universität des Cambridges, arbeiten Sie am höherwertigen Logiksystem, Co-Entwickler der Isabelle Theorem Provers
• Universität von David A. Plaisted North Carolinas am Kapelle-Hügel. Kompliziertheitsergebnisse, Beiträge zum Neuschreiben und der Vollziehung, dem Beispiel-basierten Lehrsatz-Beweis.
• Programm-Direktor von John Rushby - SRI internationaler
• J. Universität von Alan Robinson Syracuse. Entwickelte ursprüngliche Entschlossenheit und Vereinigung haben den ersten Ordnungslehrsatz-Beweis, Mitherausgeber des "Handbuches des Automatisierten Denkens", Empfänger des Herbrand-Preises 1996 gestützt
• Arbeit von Jürgen Schmidhuber an Gödel Maschinen: Universales Selbstverweisungsproblem Solvers, der nachweisbar optimale Selbstverbesserungen macht
• Stephan Schulz, E Lehrsatz Prover.
• Natarajan Shankar SRI International, arbeiten Sie an Entscheidungsverfahren, kleinen Motoren des Beweises, Co-Entwickler von PVS.
• Mark Stickel SRI International. Empfänger des Herbrand-Preises 2002.
• Universität von Geoff Sutcliffe Miamis. Maintainer der TPTP Sammlung, ein Veranstalter des CADE jährlichen Streits.
• Dolph Ulrich Purdue, Arbeit an der automatisierten Entdeckung von kürzesten axiomatischen Basen für Systeme.
• Universität von Robert Veroff New Mexicos. Viele wichtige Papiere.
• Entwickler von Andrei Voronkov des Vampirs und Mitherausgebers des "Handbuches des automatisierten Denkens"
• Larry Wos Argonne Nationales Laboratorium. (Otter) Viele wichtige Papiere. Der allererste Herbrand-Preis-Sieger (1992)
• Wen-Tsun Wu Work im geometrischen Lehrsatz, der sich erweist: Die Methode von Wu, Herbrand Preis 1997
• Christoph Weidenbach, Autor von SPASS, hat Lehrsatz prover automatisiert.

Siehe auch

• Symbolische Berechnung
• Computergestützter Beweis
• Das automatisierte Denken
• Formelle Überprüfung
• Logik, programmierend
• Beweis, der überprüft
• Modell, das überprüft
• Probekompliziertheit
• Computeralgebra-System
• Programm-Analyse (Informatik)
• Allgemeines Problem Solver
• Metamath - eine Sprache, um sich ausschließlich zu entwickeln, hat mathematische Definitionen und Beweise formalisiert, die durch einen Probekontrolleur für diese Sprache und eine wachsende Datenbank von Tausenden von bewiesenen Lehrsätzen begleitet sind; während die Sprache von Metamath mit einem automatisierten Lehrsatz prover nicht begleitet wird, kann sie als wichtig betrachtet werden, weil die formelle Sprache dahinter Entwicklung solch einer Software erlaubt; bezüglich des Märzes 2012, dort ist nicht solche Software "weit" bekannt, so ist es nicht ein Thema des "automatisierten Lehrsatzes, der sich" erweist (es kann solch ein Thema werden), aber es ist ein Probehelfer.

Zeichen