Description
Dieses Buch ist entstanden aus einer Lehrveranstaltung, die wir in den Jahren 1987 und 1988 konzipiert und weiterentwickelt haben. Sie ist an der Technischen Universitlit Berlin unter dem Namen “LOGIK II fUr Informatiker: Grundlagen des maschinellen Beweisens” Bestandteil des Lehrangebots in Theoretischer Informatik und schlieBt direkt an die “WGIK fUr Informatiker: F ormalisieren und Beweisen” an. Das Buch richtet sich somit in erster Linie an fortgeschrittene Student(inn)en im Informatik Hauptstudium, aber auch ganz allgemein an Wissenschaftler(innen) in Informatik und Mathematik, die sich fUr die logischen Grundlagen des maschinellen Theorembeweisens und die ersten Schritte zu deren Anwendung interessieren. Eine Reihe wichtiger englischsprachiger BUcher in diesem Themenfeld -wenn auch mit sehr unterschiedlichen Schwerpunktsetzungen -ist seit dem Beginn der 70er Jahre entstanden, U. a. Chang & Lee [CL73], Loveland [Lov78], Boyer & Moore [BM79], Bibel [Bib82/87], Bundy [Bun83], Wos, Overbeek, Lusk & Boyle [WOLB84], Gallier [GaI86], Genesereth & Nilsson [GN87] und Padawitz [Pad88]; in deutscher Sprache etwa Bllisius & BUrckert [BB87] oder Richter [Rich89]. Wir verstehen unser Buch als Erglinzung solcher BUcher fUr den deutschen Sprachraum mit dem Ziel, eine eher mathematisch orientierte Einflihrung in diese Thematik zu geben. Wir knUpfen an Grundkenntnisse der Logik an und stellen daher die spliter benotigten Begriffe in Kapitell nur in gestraffter Form bereit. Einen ersten Schwerpunkt bildet in Kapitel 2 die Resolution, ein handlicher AbleitungskalkUl, der die Prlidikatenlogik erster Stufe prinzipiell dem Rechner zuglinglich macht. 1 Grundbegriffe der Prdikatenlogik.- 1.1 Syntax der Prdikatenlogik.- 1.2 Semantik der Prdikatenlogik.- 1.3 Normierung der Syntax: Gentzenformeln und die Schnittregel.- 1.4 Normierung der Semantik: Herbrand-Strukturen.- 1.5 Korrektheit und Vollstndigkeit.- 1.6 Theorembeweisen durch Widerlegungen.- 2 Resolution.- 2.1 Unifikation.- 2.2 Resolution und Faktorisierung.- 3 Einschrnkung des Suchraums.- 3.1 Der Suchraum.- 3.2 Allgemeine Konzepte.- 3.3 Strukturelle Konzepte.- 3.4 Ordnungskonzepte.- 3.5 Semantische Konzepte.- 3.6 Kombination von Konzepten.- 4 Reprsentation des Suchraums.- 4.1 Connection-Graph-Resolution.- 4.2 Matrix-Verfahren.- 4.3 Tableau-Verfahren.- 5 Paramodulation.- 5.1 Gleichheit.- 5.2 Paramodulation.- 6 Termersetzung: Grundlagen.- 6.1 Termersetzungssysteme.- 6.2 Ersetzungssysteme: Termination und Konfluenz.- 6.3 Lokale Konfluenz und kritische Paare.- 7 Termersetzung: Spezielle Techniken.- 7.1 Terminationskriterien.- 7.2 Knuth-Bendix-Vervollstndigung.- 7.3 Induktive Beweise.- 7.4 Lsen von Gleichungen: Narrowing.- 7.5 Beweisen in speziellen Gleichheitstheorien.- Schlubemerkungen.- Literatur.- Symbolverzeichnis.- Sachwortverzeichnis.
