Elementare Aussagenlogik

ISBN-13: 9783540529743 / Niemiecki / Miękka / 1991 / 238 str.

Friedrich L. Bauer; Martin Wirsing

Opis

Dieses Buch uber elementare Aussagenlogik (wie auch seine geplante Fortsetzung uber Elementare Pradikatenlogik und Universelle Algebra) ist aus Vorlesungen an der Technischen Universitat Munchen entstanden. Es basiert auf der Uberzeugung, dass fur Studierende der Informatik nicht nur ein anderer Aufbau des mathematischen Grundstudiums geboten ist als etwa fur Ingenieure oder Physiker, sondern auch ein anderes Menu, als es sich an unseren Universitaten nach den GAMM-NTG-Empfehlungen der siebziger Jahre eingeburgert hat. Neben den unentbehrlichen Einfuhrungsvorlesungen in Mathematik sind fur die Informatiker vor dem Vordiplom handwerkliche Grundkenntnisse in Logik und Universeller Algebra erforderlich - als Grundlage fur die Praktische und die Theoretische Informatik im zweiten Studienabschnitt. Im Gegensatz zu vielen anderen Buchern uber Logik ist dieses fur den Anfanger der Informatik geschrieben und didaktisch auf sein Niveau eingestellt. Dabei sind sonst eher ausserhalb der Aussagenlogik liegende Gegenstande wie die Schaltlogik systematisch einbezogen worden, wo immer es moglich war: von dem fur die Programmiersprachen so wichtigen Gebiet der dyadischen Fallunterscheidungen uber die Resolventenmethode, die den Anschluss an die Pradikatenlogik vorbereitet, bis zu modalen Aussagenlogiken. Die eingestreuten Ubungsaufgaben greifen haufig Gedanken auf, die im Text nur nebenbei erwahnt sind, und stellen Querbezuge her. Die Losungshinweise am Ende des Buches bieten manche Uberraschungen."

Spis treści

I. Natürliches Begriffsfeld.- 1. Aussagen und Aussagenverbindungen.- 1.1 Zweiwertiger Aussagenraum.- 1.2 Aussagenverbindungen.- 1.3 Extensionalität der Aussagenlogik.- 2. Aussageformen.- 2.1 Zeichen.- 2.2 Aussagenlogische Grundfunktionen.- 2.3 Aussagekonstanten.- 3. Syntax der Aussageformen.- 3.1 Kontextfreie Grammatik.- 3.2 Algorithmen zur Erkennung von Aussageformen.- 3.3 Induktive Beweise über den Aufbau von Aussageformen.- 3.4 Vielfachkonjunktion, Vielfachadjunktion.- 3.5 Gebundene Bezeichner.- 3.6 Syntaktische Identitäten.- II. Wertverlauf.- 4. Tautologien und erfüllbare Aussageformen.- 4.1 Bewertung von Aussageformen.- 4.2 Tautologie und Kontradiktion.- 4.3 Identifizierung von Unbestimmten.- 4.4 Hauptregeln.- 4.5 Einsetzungsregel.- 4.6 Formgesetze.- 5. Äquivalenz und Ordnung von Aussageformen.- 5.1 Wertverlaufsinklusion.- 5.2 Die Stärker-Regel für Implikationen.- 5.3 Wertverlaufsgleichheit.- 5.4 Die Gleichstark-Regel für Biimplikationen.- 5.5 Wertverlaufsgleichheit in Teilsprachen.- 5.6 Implikation und Biimplikation, Anreicherung.- 5.7 Verträglichkeit.- 6. Die selbständige Rolle der Subjunktion.- 6.1 Subjunktion als Umkehroperation.- 6.2 Schranken.- 6.3 Die Stärkerrelation als Verbandsordnung.- 6.4 Interpolation.- III. Funktionale und Algebraische Aspekte.- 7. Aussagenlogische Funktionen.- 7.1 Ersetzbarkeitstheorem.- 7.2 Äquivalenzklassen.- 7.3 Couffignal-Codierung und Würfel-Darstellungen.- 7.4 Folgen-Codierung aller Klassen gleichstarker Aussageformen.- 8 Repräsentantensysteme.- 8.1 Repräsentationstheorem für aussagenlogische Funktionen.- 8.2 Elimination von Grundoperationen: C und E.- 8.3 Elimination von Grundoperationen: A oder K.- 8.4 Zurückführung auf Subjunktion und Negation.- 8.5 Zurückführung auf Bisubjunktion und Negation.- 8.6 $$overline K$$ oder ? als Basis.- 8.7 Dreistellige Operationen.- 8.8 Dualität.- 8.9 Minimale Sprachbasen.- 9 Algebra der Aussageformen.- 9.1 Induzierte Operationen auf Aussageformen.- 9.2 Der Boolesche Verband der Aussageformen.- 9.3 Die Gruppe und der Boolesche Ring der Aussageformen.- 9.4 Andere algebraische Strukturen von Aussageformen.- 9.5 Mengen als Modelle des Booleschen Verbands.- 9.6 Rechnen unter Verwendung der Couffignal-Codierung.- 10. Programmiersprachen: Fallunterscheidungskalkül.- 10.1 Vereinfachungen.- 10.2 Grundgesetze über dyadische Fallunterscheidungen.- 10.3 Die dreistellige Operation B als Fallunterscheidung.- 10.4 Sequentielle und bewachte Fallunterscheidungen.- 10.5 Ubergang von sequentieller zu bewachter Fallunterscheidung.- 10.6 Übergang von bewachter zu sequentieller Fallunterscheidung.- IV. Formale Reduktionen.- 11. Auswertung und Teilauswertung „von außen“.- 11.1 Zurückgestellte Operationen.- 11.2 Teilauswertung.- 11.3 Quines Entscheidungsalgorithmus für Tautologien.- 12. Normalformen.- 12.1 Aussagenlogische Verneinungstechnik.- 12.2 Verneinungstechnische Normalform: NAND-Bäume.- 12.3 Verneinungstechnische Normalform: Kontaktschaltungen.- 12.4 Prämissen-Normalform.- 12.5 Prämissen-Normalform: Entscheidungsbäume und -netze.- 13. Adjunktive und konjunktive Normalformen.- 13.1 Adjunktive Normalform.- 13.2 Konjunktive Normalform.- 13.3 Bereinigte Normalformen.- 13.4 Klauseln und Klauselmengen.- 13.5 Abschließung.- 13.6 Beths Entscheidungsalgorithmus für Tautologien.- 13.7 Quines Algorithmus für adjunktive Normalformen.- 13.8 Anwendung auf Diodennetze und NOR-Schaltungen.- 14. Kanonische Normalformen.- 14.1 Adjunktive Boolesche Normalform.- 14.2 Das Normalformtheorem von Boole.- 14.3 Nochmals: Nachweis der Tautologieeigenschaft.- 14.4 Konjunktive Boolesche Normalform.- 14.5 Übergang zwischen den kanonischen Normalformen.- 14.6 Die kanonische Prämissen-Normalform.- 14.7 Die kanonische Ring-Normalform.- 15. Die Resolventenmethode.- 15.1 Entscheidung einer Tautologie.- 15.2 Der Schichtenalgorithmus und der Eliminationsalgorithmus.- 15.3 Die duale Methode: Pfeilgerüste.- 15.4 Minimale Normalformen.- 15.5 Minimierung einer Kanonischen Normalform.- 16. Die Methode des Widerspruchs.- V. Formale Ableitungen.- 17. Gewinnung von Schlußregeln.- 17.1 Schlußregeln für Tautologien.- 17.2 Schlußregeln für Folgerungen.- 17.3 Linksstabiler Beweis von Folgerungen.- 17.4 Ein formales relationentheoretisches System.- 17.5 Technik der formalen Ableitung.- 18. Ableitungssysteme für Tautologien.- 18.1 Das klassische Ableitungssystem.- 18.2 Durchführung von Ableitungen.- 18.3 Vollständigkeit.- 18.4 Formalsprachlicher Aspekt.- 18.5 Varianten des klassischen Ableitungssystems.- 18.6 Intuitionistische Aussagenlogik.- 19. Ableitungssysteme für Folgerungen.- 19.1 Das Gentzensche Ableitungssystem.- 19.2 Monotoniesatz.- 19.3 Deduktionssatz.- 19.4 Vollständigkeit.- 20. Kompaktheit.- 20.1 Kompaktheitssatz für die Erfüllbarkeit.- 20.2 Kompaktheitssatz für Folgerungen.- 20.3 Dualer Kompaktheitssatz.- VI. Modale Aussagenlogiken.- 21. Die Sprache der Modallogiken.- 21.1 Dualität der modalen Junktoren, minimale Modallogik K.- 21.2 Deontische und alethische Modallogiken.- 21.3 Temporale und existentiale Modallogiken.- 21.4 Zusammenhang der modalen Logiken.- 22. Semantik modaler Logiken.- 22.1 Kripke-Strukturen.- 22.2 Omega-Modell, temporale Modallogiken S4.4 und Grz.- 22.3 Präordnung und Äquivalenz von modalen Aussageformen.- 22.4 Entscheidungsalgorithmen für modale Aussageformen.- 22.5 Ableitungssysteme für Modallogiken.- 23. Dimodale Logiken.- 23.1 Die Axiome von McTaggart und Prior.- 23.2 Spezielle dimodale Logiken.- 24. Multimodale Logiken.- 24.1 Modale Schritt-Logiken.- 24.2 Kripke-Strukturen mit Hüllen.- 24.3 Kripke-Strukturen der Schritt-Logiken.- Hinweise zur Lösung der Aufgaben.- Aussagenlogische Operationen.- Tautologien.- Schlußregeln für Tautologien.- Schlußregeln für Folgerungen.- Modallogische Regeln und Gesetze.- Literatur und Quellen.- Namen- und Sachverzeichnis.

O autorze

Prof. Dr. Martin Wirsing ist Leiter des Lehrstuhls für Programmierung und Software-Technik des Instituts für Informatik der LMU München und Vizepräsident der LMU für den Bereich Studium.