EinführungindiemoderneLogik0. Organisatorisches 0.0.0.1. BasiskursLogik • Auch bekannt als: PHI-M04 und PHI-M10.4 und außerdem anrechenbar in PHI-M35.2undalsfreieLeistungspunkte

Einführung in die moderne Logik

SkriptSommersemester 2013

Dr. Tim KraftInstitut für Philosophie

Univ. Regensburg

[email protected]

mailto:[email protected]

Vorbemerkungen

Stand 11. November 2013

Hinweise Bei diesem Skript handelt es sich um eine überarbeitete Version meiner Skrip-te aus dem Wintersemester 2010/11 (Univ. Göttingen), dem Sommersemester 2012 (Univ.Regensburg) und dem Sommersemester 2013 (Univ. Regensburg). Die vorliegende Versionentspricht der Version, die im Sommersemester 2013 verwendet wurde (vom 10.4.2013), mitder Ausnahme einiger Errata, die für die Novemberversion korrigiert wurden.

Danksagung Danken möchte ich Dolf Rami, von dessen Logikskript (Univ. Göttingen,Wintersemester 2009/10) ich einige Anregungen und Beispiele übernommen habe, HolgerLeuz fürs aufmerksame Lesen der Überarbeitung und den Tutoren meines Göttinger Logik-kurses (Univ. Göttingen, Wintersemester 2010/11) Carina Dettmar, Wilfried Keller, TammoLossau, Johanna Mardt, Gordon N. Rößler und Sinje Stange, die auch ihre Namen für vieleBeispiele hergeben mussten.

Copyright CC BY-NC-SA Dieses Skript steht unter einer Creative Commons Lizenz vomTyp Namensnennung – Nicht-kommerziell – Weitergabe unter gleichen Bedingungen 3.0Deutschland. Für die Details: http://creativecommons.org/licenses/by-nc-sa/3.0/de/Ausgenommen ist die Zeichnung auf S. vi: ©Daniel Wawrzyniak

ii

http://creativecommons.org/licenses/by-nc-sa/3.0/de/

Inhaltsverzeichnis

0. Organisatorisches 1

1. Grundbegriffe der Logik: Argumente und Folgerichtigkeit 31.1. Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 31.2. Argumente . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41.3. Folgerichtigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 81.4. Deduktion, Induktion, Abduktion . . . . . . . . . . . . . . . . . . . . . . . . . . 151.5. Ergänzungen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

I. Aussagenlogik 19

2. Aussagenlogik: Grundlagen 202.1. Wahrheitsfunktionale Satzoperatoren . . . . . . . . . . . . . . . . . . . . . . . . 202.2. Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

3. Aussagenlogik: Logische Form natürlichsprachlicher Sätze 263.1. Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 263.2. Negation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 273.3. Konjunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 283.4. Disjunktion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 323.5. Konditional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 343.6. Bikonditional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 373.7. Zusammenfassung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 38

4. Aussagenlogik: Wahrheitstafelmethode und Semantik 394.1. Wahrheitstafelmethode . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 394.2. Formale Sprachen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 434.3. Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 44

5. Aussagenlogik: Baumkalkül 475.1. Baumkalkül . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 475.2. Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 495.3. Überblick über alle Regeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 53

6. Aussagenlogik: Ergänzungen 576.1. Baumkalkül: Interpretationen ablesen . . . . . . . . . . . . . . . . . . . . . . . . 576.2. Konditional und Implikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 586.3. *Korrektheit und Vollständigkeit . . . . . . . . . . . . . . . . . . . . . . . . . . 596.4. *Philosophisches Argumentieren . . . . . . . . . . . . . . . . . . . . . . . . . . . 60

iii

Inhaltsverzeichnis

II. Prädikatenlogik 64

7. Prädikatenlogik: Grundlagen 657.1. Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 657.2. Prädikation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 667.3. Syntax . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 687.4. Quantoren . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

8. Prädikatenlogik: Semantik 778.1. Mengenlehre . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 778.2. Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 808.3. Interpretationen und Gegenbeispiele . . . . . . . . . . . . . . . . . . . . . . . . 838.4. *Appendix zur Semantik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 86

9. Prädikatenlogik: Baumkalkül 889.1. Neue Regeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 889.2. Beispiele . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 909.3. Interpretationen ablesen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 94

10.Prädikatenlogik: Erweiterung um Identität 9610.1. Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9610.2. Syntax, Semantik, Kalkül . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9710.3. Beispiele Baumkalkül . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 9910.4. Beispielsätze . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 100

11.Prädikatenlogik: Ergänzungen 10111.1. *PL erster Stufe vs. höherer Stufe . . . . . . . . . . . . . . . . . . . . . . . . . . 10111.2. *Korrektheit, Vollständigkeit, Entscheidbarkeit . . . . . . . . . . . . . . . . . . 10111.3. Beziehungen zwischen Formeln . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10211.4. Notwendige und hinreichende Bedingungen . . . . . . . . . . . . . . . . . . . . 103

III. Weiterführendes 105

12.*Modallogik 10612.1. Wozu Modallogik? . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 10612.2. Notwendigkeit und Möglichkeit . . . . . . . . . . . . . . . . . . . . . . . . . . . 10712.3. Syntax, Semantik, Kalkül . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 110

13.*Andere Kalküle 11613.1. Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11613.2. Axiomatischer Kalkül . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11613.3. Natürliches Schließen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 118

14.*Korrektheit und Vollständigkeit 12314.1. Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 12314.2. Aussagenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 125

iv

Inhaltsverzeichnis

14.3. Prädikatenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 127

Anhänge 129

A. Regeln Baumkalkül 129A.1. Aussagen- und Prädikatenlogik . . . . . . . . . . . . . . . . . . . . . . . . . . . 129A.2. Modallogik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131

B. *Logische Notation 133B.1. Einleitung . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133B.2. Varianten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 133B.3. Alternativen . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 135B.4. Weitere Besonderheiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 136

C. *Traditionelle Bezeichnungen von logischen Gesetzen 138C.1. Logische Schlüsse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 138C.2. Logische Wahrheiten . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139C.3. Fehlschlüsse . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 139

D. *Logikbücher – Eine kommentierte Literaturliste 140D.1. Einführungen in die Logik . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 140D.2. Weiterführende Bücher . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 142

Mit einem * markierte Abschnitte sind nicht klausurrelevant.

v

vi

0. Organisatorisches0.0.0.1. Basiskurs Logik

• Auch bekannt als: PHI-M04 und PHI-M10.4 und außerdem anrechenbar in PHI-M35.2 und als freie Leistungspunkte

• Leistungspunkte: 9, benotet wird die Abschlussklausur

• Zwei Bestandteile

1. Kurs: Do 14:15–16:00 (Wir machen jeweils um ca. 15:00 eine viertelstündige Pau-se.)

2. Übung: verschiedene Termine (Besprechung von wöchentlichen Übungsaufgaben)

• Modulprüfung Klausur (90 Minuten) am Do 25.7. 14:15–15:45

– Voraussetzung für Teilnahme an der Klausur: Mind. 50% der Punkte beiÜbungszetteln

– Voraussetzung für Teilnahme an der Klausur: Anmeldung im FlexNow!(Ausnahme: Lehramt Erweiterungsfach, dann bekommen Sie einen Papierschein)Achtung: Sie müssen sich über die Übung, nicht über den Kurs anmelden (Aus-nahme sind Masterstudierende: Anmeldung über Kurs)!

0.0.0.2. Kurs: Ablauf

• Dieser Kurs ist keine Vorlesung im wörtlichen Sinne: Ich lese keinen vorgefertigten Textvor, sondern arbeite mit Folien (Theorie) und Tafel (Beispiele).

• Das ändert nichts daran, dass Sie hier meistens passiv sein werden. Aber: Ich kannleiser oder lauter sprechen, schneller oder langsamer durch den Stoff gehen, etwas nocheinmal erklären oder auch ein Beispiel weglassen – melden Sie sich bitte, wenn Sie indie eine oder andere Richtung Änderung wünschen!

0.0.0.3. Übung: Ablauf

Wer? Wann? Wo?

Dr. Holger Leuz Mi 8–10 ZH8Dr. Holger Leuz Fr 10–12 ZH2Dr. Holger Leuz Fr 12–14 PT2.0.5

Achtung! Die Übungen beginnen in der zweiten Semesterwoche!

1

0. Organisatorisches

Verteilung auf Übungsgruppen

• Um einer Übungsgruppe zugeordnet zu werden, müssen Sie sich auf die jeweilige Listeeintragen (während der ersten Sitzung).

• Bitte schauen Sie, dass die Teilnehmerzahl der Übungen etwa gleich ist. (Wir behaltenuns Umverteilungsmaßnahmen vor, hoffen aber, dass das unnötig sein wird.)

0.0.0.4. Material

• K-Platte „Kurssoft“ https://netstorage.uni-regensburg.de/NetStorage/

• Skript findet sich online auf der K-Platte, kann aber für eine Unkostenbeteiligung von2,–e erworben werden (Ringbindung). Sie brauchen kein Lehrbuch lesen; wichtigerals Lesen ist sowieso das regelmäßige Bearbeiten der Übungsblätter und die aktiveTeilnahme an der Übung.

• Übungsblätter werden von Woche zu Woche zur Verfügung gestellt. Näheres wird inder Übung besprochen.

• Weiteres, eine Errata-Liste und evtl. Ergänzungen, wird im Laufe des Semesters zurVerfügung gestellt.

0.0.0.5. Kontakt

• Fragen zum Inhalt? Übung!

• Hartnäckige inhaltliche oder organisatorische Probleme?

– Nach dem Kurs oder in meiner Sprechstunde (Do 11:00 bis 12:30 und nach Ver-einbarung, Raum: PT 4.3.15)

– E-Mail: tim.kraft@ur.

• Fehler im Skript gefunden? Bitte kontaktieren Sie mich, damit ich den Fehler aufdie Errata-Liste setzen kann!

0.0.0.6. SemesterplanNr. Datum Thema Skript

1 18.4. Organisatorisches und Grundbegriffe der Logik Kap. 0, Kap. 12 25.4.3 2.5.– 9.5. Feiertag4 16.5.5 23.5.– 30.5. Feiertag6 6.6.7 13.6.8 20.6.9 27.6.10 4.7.11 11.7.12 18.7.– 25.7. Klausur

2

https://netstorage.uni-regensburg.de/NetStorage/

mailto:[email protected]

1. Grundbegriffe der Logik: Argumenteund Folgerichtigkeit

1.1. Was ist Logik und warum sollte man sich mit ihrbeschäftigen?

1.1.1. Was ist Logik?

Definition 1 (Logik). Gegenstand der Logik sind Argumente und ihre Folgerichtigkeit.

Zwei Grundfragen der Logik Dementsprechend beschäftigt die Logik sich mit zwei Grund-fragen:

1. Was ist ein folgerichtiges Argument?

2. Wie kann man feststellen, ob ein Argument folgerichtig ist?

Gegenstand der Logik, in anderen Worten Manche Autoren bevorzugen andere Formu-lierungen:

• Logik ist die Lehre von den gültigen Schlüssen.

• Logik ist die Lehre vom korrekten Schließen.

• Logik ist die „Lehre des vernünftigen Schlussfolgerns“. (Wikipedia)

Lassen Sie sich nicht verwirren: Diese Formulierungen laufen auf dasselbe hinaus!

Drei Auffassungen von Argumenten bzw. Schlüssen. . .

• . . . sind abstrakte Strukturen und dementsprechend handelt die Logik von der Grund-struktur der Welt.

• . . . sind Vorgänge im (menschlichen) Geist und dementsprechend handelt die Logik vonden grundlegenden Gesetzen des Denkens.

• . . . bestehen aus Sätzen und dementsprechend handelt die Logik von der Grundstrukturder Sprache (oder: den Grenzen des Sinns).

Verabredung Wir werden diese und andere meta-logische Fragen ignorieren. Es gibt nichtohne Grund neben der Logik auch noch die Philosophie der Logik, die solche Fragenbehandelt.

3

1. Grundbegriffe der Logik: Argumente und Folgerichtigkeit

1.1.2. Warum mit Logik beschäftigen?

. . . u. a. weil . . .

1. Analyse von Argumenten: . . . weil Klarheit über Begriffe wie Prämisse/Konklusion,Folgerichtigkeit, Deduktion vs. Induktion, Konsistenz, usw. essentiell ist, um Argumen-te – in der Philosophie und anderswo – zu analysieren.

2. Voraussetzung fürs Philosophiestudium: . . . weil elementare Kenntnisse des logi-schen Symbolismus das Lesen philosophischer Texte deutlich vereinfachen.

3. Anwendungen der Logik: . . . weil die Logik in diversen Bereichen der Philosophie(Philosophie der Mathematik, Sprachphilosophie, Wissenschaftsphilosophie, Metaphy-sik, Entscheidungstheorie usw.) und anderen Disziplinen (Mathematik, Informatik,Sprachwissenschaft, Kognitionswissenschaft usw.) angewendet wird.

1.1.3. Gliederung

Wir werden im Laufe des Kurses verschiedene Mittel zur Analyse von Argumenten kennenler-nen. Heute gibt es einen Einblick in die Logik anhand der zwei zentralen Grundbegriffe:

1. Argument

2. Folgerichtigkeit

1.2. Was ist ein Argument?

1.2.1. Beispiele und Gegenbeispiele

Erstes Beispiel Alle Menschen sind sterblich. Sokrates ist ein Mensch. Also ist Sokratessterblich.

Zweites Beispiel Sokrates ist sterblich oder ein Halbgott. Er ist jedenfalls kein Halbgott.Also muss Sokrates sterblich sein.

Drittes Beispiel Wenn es regnet, ist die Straße nass. Es regnet. Also ist die Straße nass.

Viertes Beispiel (Platon) [Der Sophist Dionysodoros zum Jüngling Ktesippos:] Sage mir,hast du einen Hund? – Und das einen recht bösen, sprach Ktesippos. – Hat er auch Junge?– Ja sprach er, ebensolche. – Deren Vater ist also doch der Hund? – Jawohl, sprach er, ichhabe selbst gesehen, wie er die Hündin beschwängerte. – Wie nun, ist der Hund nicht dein?– Freilich, sagte er. – Und so wie dein, ist er auch Vater; so daß der Hund dein Vater ist,und du der jungen Hunde Bruder.

(aus: Platon: Euthydemos. 298d–e, zitiert nach der Übers. von Friedrich Schleiermacher.)

4


Fünftes Beispiel (Gedankenknoten)

Jill You think I am stupid.

Jack I don’t think you’re stupid.

Jill I must be stupid to think I’m stupid if you don’t: or you must be lying.

I am stupid every way:

to think I’m stupid, if I am stupid

to think I’m stupid, if I’m not stupid

to think you think I’m stupid, if you don’t.

(aus: R.D. Laing: Knots. 1970, S. 22.)

Kein Argument gibt, wer . . .

• einfach widerspricht,

• (nur) eine Frage stellt,

• (nur) einen Befehl gibt,

• bloß seine Meinung bekundet,

• etwas berichtet oder beschreibt,

• usw.

1.2.2. Definition Argument

1.2.2.1. Argumente I: Erste Beobachtung

Woraus Argumente bestehen Argumente bestehen aus wahrheitswertfähigen Sätzen,das heißt aus Sätzen, von denen sinnvoll gesagt werden kann, dass sie wahr sind.

Erläuterung

• „sinnvoll“: Ein Satz ist sinnvoll, wenn man ihn verstehen kann.

• „sagen“: Einen Satz zu sagen oder äußern ist nicht dasselbe wie ihn zu behaupten. (Z. B.im Sprachunterricht werden oft sinnvolle Sätze geäußert, ohne behauptet zu werden.)

• Also: Es kommt nur darauf an, ob Äußerungen der Art „Der folgende Satz ist wahr:S“ sinnvoll oder verständlich sind (nicht ob sie tatsächlich wahr, begründet o. ä. sind).Insbesondere kann man auch von falschen Sätzen sinnvoll sagen, sie seien wahr.

5


Alternative Definitionen

• Warum so kompliziert? Warum nicht einfach „Ein Satz ist wahrheitswertfähig genaudann, wenn er wahr oder falsch ist“?

• Es ist in der Sprachphilosophie/Logik umstritten, wie viele Wahrheitswerte es gibt undwie viele Wahrheitswerte ein Satz haben kann. Die Definition ist neutral hinsichtlichdieser Fragen.

Nicht wahrheitswertfähig sind z. B. die folgenden Sätze:

• Reihst du dich in unsere Demo ein?

• Reih dich in die Demo ein!

• Alter Schwede!

• Grüne Ideen schlafen wütend. (?)

• Schön, dass du gekommen bist! (?)

• Erdbeereis ist lecker. (?)

1.2.2.2. Argumente II: Zweite Beobachtung

Signalwörter Argumente erkennt man an Signalwörtern wie „also“, „deshalb“, „folglich“,„aus diesen Gründen“, „es muss so sein, dass“ usw.

Zwei Teile Wir können daher jedes Argument aufteilen in:

1. den Satz nach dem „also“ = das, wofür argumentiert wird (das Ergebnis)

2. den Sätzen vor dem „also“ = das, womit argumentiert wird (das, was dafür angeführtwird)

1.2.2.3. Argumente III: Prämissen und Konklusion

Definition 2 (Prämisse/Konklusion). Das, wofür argumentiert wird, ist die Konklu-sion. Das, was für die Konklusion angeführt wird, sind die Prämissen.

1.2.2.4. Argumente IV: Prämissen und Konklusion (Forts.)

Verabredung

1. Ein Argument hat genau eine Konklusion.

2. Ein Argument hat beliebig viele Prämissen.

6


Zwei Sonderfälle

1. Null Prämissen: Das lassen wir zu. Dazu später mehr.

2. Unendlich viele Prämissen: Das lassen wir zu. Argumente mit unendlich vielenPrämissen werden in diesem Logikkurs aber keine Rolle spielen.

1.2.2.5. Argumente V: Definition

Definition 3 (Argument). Ein Argument besteht aus einer Menge von Sätzen – denPrämissen – und einem einzigen Satz, der als Konklusion gekennzeichnet ist.

1.2.2.6. Argumente VI: Erläuterung

Achtung I Weitere Bedingungen werden nicht gestellt, insbesondere wird nicht verlangt,dass. . .

• . . . Prämissen und Konklusion verschieden sind. (Beispiel: Es regnet. Also regnet es.)

• . . . Prämissen und Konklusion inhaltlich zusammenhängen. (Beispiel: Es regnet. Alsoist die Erde eine Kugel.)

1.2.2.7. Argumente VII: Argumente und Argumentieren

Achtung II Die Definition lässt auch offen, mit welcher Absicht ein Argument vorgebrachtwird.

Argumente können für viele verschiedene Zwecke eingesetzt werden

• . . . um eine Behauptung zu begründen.

• . . . um eine Behauptung auf Voraussetzungen zurückzuführen.

• . . . um etwas zusammenzufassen.

• . . . um Zusammenhänge zwischen verschiedenen Behauptungen aufzuzeigen.

• . . . um zu zeigen, dass eine Position unerwünschte Konsequenzen hat (z. B. Paradoxien).

• usw.

1.2.2.8. Argumente VIII: Überleitung

Merke Folgerichtigkeit – gleich mehr dazu, was das ist – soll. . .

• . . . keine Eigenschaft sein, die schlechte Argumente von guten, überzeugenden Argu-menten unterscheidet,

• . . . sondern eine Voraussetzung, die jedes Argument erfüllen sollte – ganz unabhängigdavon, zu welchem konkreten Zweck es eingesetzt wird.

7


1.2.3. Darstellung eines Arguments

Natürlichsprachliche Argumente Wie wir anhand der Beispiele gesehen haben, werden inder natürlichen Sprache Argumente sehr verschieden dargestellt:

• Die Konklusion kann am Ende, aber auch am Anfang stehen.

• Die Konklusion wird mit einer Bandbreite von Ausdrücken markiert.

• Als selbstverständlich geltende Prämissen werden einfach weggelassen. (Argumente mitfehlenden Prämissen werden auch Enthymeme genannt.)

In der Philosophie ist es üblich, Argumente etwas aufgeräumter zu präsentieren:

. . . nämlich so . . .

(1) Wenn es regnet, ist die Straße nass.

(2) Es regnet.

(3) ∴ Die Straße ist nass.

. . . oder so . . .

(1) Wenn es regnet, ist die Straße nass.

(2) Es regnet.

(3) Die Straße ist nass.

. . . oder so . . .

(1) Wenn es regnet, ist die Straße nass. (Prämisse, Schmidt 2008: 37)

(2) Es regnet. (Prämisse, Beobachtung)

(3) Die Straße ist nass. (aus 1 und 2)

1.3. Was ist Folgerichtigkeit?

1.3.1. Folgerichtigkeit – Die Idee

Argumente

• . . . bestehen aus Sätzen, die wahr/falsch sind.

• . . . können aber selber weder wahr noch falsch sein (sondern folgerichtig/nicht folge-richtig).

• . . . haben dennoch etwas mit Wahrheit zu tun.

8


Folgerichtigkeit, intuitiv formuliert Ein Argument ist folgerichtig genau dann, wenn gilt:

• Wahrheit wird von den Prämissen auf die Konklusion übertragen. (Wahrheitstransfer)

• Wahrheit kann nicht unterwegs verloren gehen. (Wahrheitserhaltung)

• Es erlaubt ist, von den Prämissen, falls sie wahr sind, zur Konklusion überzugehen.(inference ticket)

Definition 4 (Folgerichtigkeit: Positive modale Version). Ein Argument ist fol-gerichtig genau dann, wenn gilt: Wenn die Prämissen wahr sind, muss die Konklusionebenfalls wahr sein.

Definition 5 (Folgerichtigkeit: Negative modale Version). Ein Argument ist fol-gerichtig genau dann, wenn gilt: Es ist unmöglich, dass die Prämissen wahr sind und dieKonklusion falsch.

1.3.2. Wahrheit und Folgerichtigkeit

Wichtig! Folgerichtigkeit vs. Wahrheit Zwei Fragen müssen streng auseinander gehaltenwerden:

1. Ist das Argument folgerichtig?

2. Sind die Prämissen wahr?

Dass ein Argument folgerichtig ist, besagt nur folgendes:

• Positive Fassung: Wenn die Prämissen wahr sind, dann ist die Konklusion auch wahr.

• Negative Fassung: Es sind nicht zugleich sowohl die Prämissen wahr, als auch dieKonklusion falsch.

Beispiel

(1) Alle Logiker haben lange Haare.

(2) Poldi ist Logiker.

(3) Poldi hat lange Haare.

AuswertungPrämissen? falschKonklusion? falschArgument? folgerichtig

Merke Es kann sein, dass ein Argument folgerichtig ist, obwohl alle Prämissen und dieKonklusion falsch sind.

9


Beispiel

(1) Alle Logiker sind schlau.

(2) Wilfried ist schlau.

(3) Wilfried ist Logiker.

AuswertungPrämissen? wahrKonklusion? wahrArgument? nicht folgerichtig

Merke Es kann sein, dass ein Argument nicht folgerichtig ist, obwohl alle Prämissen unddie Konklusion wahr sind.

Merke

• Argumente können nicht wahr (oder falsch) sein, nur Sätze sind wahr oder falsch.

• Argumente sind folgerichtig oder nicht folgerichtig, Sätze können nicht folgerichtig sein.

• Nur weil ein Argument für eine Konklusion folgerichtig ist, heißt das nicht, dass dieKonklusion wahr sein muss. (Es müssen außerdem die Prämissen wahr sein.)

• Nur weil ein Argument für eine Konklusion nicht folgerichtig ist, heißt das nicht, dassdie Konklusion falsch sein muss.

Wiederholung: Was Sie sich unbedingt merken sollten! Wenn ein Argument folgerichtigist, dann . . .

1. . . . sind alle Verteilungen von Wahrheitswerten möglich bis auf eine, nämlich:

• Die Prämissen sind wahr und

• die Konklusion ist falsch.

2. . . . , oder mit anderen Worten: Wenn die Prämissen wahr sind, dann ist auch dieKonklusion wahr.

Terminologie

Folgerichtig Folgerichtig plusalle Prämissen wahr

zwingend schlagendkorrekt schlüssigschlüssig gültiggültig Beweisvalid soundsound ?

10


Verabredung In diesem Logikkurs verwenden wir „folgerichtig“.

Äquivalente Formulierungen Dem Adjektiv „folgerichtig“ entsprechen die Verben „(lo-gisch) implizieren“ und „(logisch) folgen“. Die folgenden Formulierungen sind äquivalent:

• Das Argument ist (logisch) folgerichtig. (Adjektiv)

• Die Konklusion folgt (logisch) aus den Prämissen. (Verb)

• Die Prämissen implizieren (logisch) die Konklusion. (Verb)

• P1, P2, P3, ⋅ ⋅ ⋅ ⊧K (formale Notation)

1.3.3. Logische Notwendigkeit

1.3.3.1. Notwendigkeit I: Das Problem

Wiederholung Definition Folgerichtigkeit Ein Argument ist folgerichtig genau dann,wenn gilt: Es ist unmöglich, dass die Prämissen wahr sind und die Konklusion falsch.

Problem Was bedeutet hier „unmöglich“?

1.3.3.2. Notwendigkeit II: Naturgesetzliche Notwendigkeit

Beispiel

(1) Das Geländer besteht aus Metall.

(2) Das Geländer wird erhitzt.

(3) Das Geländer dehnt sich aus.

Auswertung

• Es ist naturgesetzlich unmöglich (physikalisch unmöglich), dass die Prämisse wahrund die Konklusion falsch ist.

• Es ist aber logisch möglich, dass die Prämissen wahr und die Konklusion falsch ist.

1.3.3.3. Notwendigkeit III: Begriffliche Notwendigkeit

Beispiel

(1) Gordon ist Junggeselle.

(2) Gordon ist unverheiratet.

11


Auswertung

• Es ist begrifflich unmöglich, dass die Prämisse wahr, aber die Konklusion falsch ist.

• Es ist aber logisch möglich, dass die Prämissen wahr und die Konklusion falsch ist.

Hinweis Begrifflich notwendige Sätze nennt man auch „analytisch wahr“, begrifflich unmög-liche Sätze auch „analytisch falsch“ und alle anderen Sätze „synthetisch“.

1.3.3.4. Notwendigkeit IV: Begriffliche vs. logische Notwendigkeit

Beispiel: Begrifflich

(1) Johanna hat Schweine und heiratet den ersten Fremden.

(2) Johanna hat beide Karo-Asse und beide Kreuz-Damen.

Beispiel: Logisch

(1) Johanna hat Schweine und heiratet den ersten Fremden.

(2*) Johanna hat Schweine.

1.3.3.5. Notwendigkeit V: Begriffliche vs. logische Notwendigkeit

Begriffliche Notwendigkeit . . .

• . . . ergibt sich aus der Bedeutung der sprachlichen Ausdrücke, die in den Prämissenund der Konklusion vorkommen.

• . . . ergibt sich aus dem themen-spezifischen Vokabular (hier: Doppelkopf-Vokabular).

Logische Notwendigkeit . . .

• . . . ergibt sich aus der Bedeutung des themen-neutralen Vokabular (z. B. „und“,„oder“, „wenn–dann“, „nicht“, „alle“, „einige“).

• . . . ergibt sich nicht aus dem Inhalt, sondern aus der Form der Prämissen und Kon-klusion.

1.3.3.6. Notwendigkeit VI: Ergebnis

Definition 6 (Folgerichtigkeit: verbesserte negative modale Version). Ein Ar-gument ist folgerichtig genau dann, wenn gilt: Es ist logisch unmöglich, dass die Prämissenwahr sind und die Konklusion falsch.

12


Was nun?

• Diese Definition stimmt, ist aber nicht informativ.

• Wir müssen daher klären, was logische Notwendigkeit ist, genauer: was es mit der Un-terscheidung zwischen themen-spezifischem und themen-neutralem Vokabular bzw. derUnterscheidung zwischen Form und Inhalt auf sich hat. Mit dieser Aufgabe beginnenwir im nächsten Kapitel.

1.3.4. Folgerichtigkeit und logische Wahrheit

Was ist mit logischen Wahrheiten?

• Definition: Logik handelt von Argumenten und ihrer Folgerichtigkeit.

• Frage: Geht es nicht auch logische Gesetze, die nichts damit zu tun haben, was worausfolgt?

Einige prominente logische Gesetze

• Satz vom ausgeschlossenen Widerspruch: Etwas kann nicht sowohl der Fall alsauch nicht der Fall sein.

• Satz vom ausgeschlossenen Dritten: Etwas ist der Fall oder nicht der Fall – einedritte Option gibt es nicht

• Gesetz der Selbstidentität: Alles ist mit sich selbst identisch

Das Problem Diese Gesetze betreffen prima facie nicht Argumente und deren Folgerich-tigkeit, sondern einzelne Aussagen und deren logische Wahrheit bzw. logische Falschheit.

Definition 7 (Tautologie). Ein Satz ist logisch wahr oder tautologisch genau dann,wenn es logisch unmöglich ist, dass er falsch ist.

Definition 8 (Kontradiktion). Ein Satz ist logisch falsch oder kontradiktorisch ge-nau dann, wenn es logisch unmöglich ist, dass er wahr ist.

Definition 9 (Logische Kontingenz). Ein Satz ist logisch kontingent genau dann,wenn es logisch möglich ist, dass er wahr ist, und es logisch möglich ist, dass er falsch ist.

Beispiele für Tautologien

• Gordon ist in der Mensa oder er ist nicht in der Mensa.

• Wenn Sinje die Übung leitet, dann leitet Sinje die Übung.

• Alle Logiker sind Logiker.

13


Beispiele für Kontradiktionen

• Gordon ist in der Mensa und er ist nicht in der Mensa.

• Es gibt einen Logiker, der kein Logiker ist.

Beispiele für logische Kontingenzen

• Wilfried ist Logiker.

• Wenn Wilfried Logik unterrichtet, freuen sich die Studierenden.

Zusammenhang Folgerichtigkeit und logische Wahrheit Das Problem ist nur ein schein-bares Problem. Denn es besteht der folgende Zusammenhang: S ist eine logische Wahrheitgenau dann, wenn das Argument mit S als Konklusion und leerer Prämissenmenge folge-richtig ist, kurz: ⊧ S

Erläuterung

• Ein Argument ist folgerichtig⇔ Es ist logisch unmöglich, dass (a) alle Prämissen wahrsind und (b) die Konklusion falsch ist

• Wenn es keine Prämissen gibt, ist die erste Bedingung trivialerweise erfüllt. Daher gilt:

• Ein Argument ohne Prämissen ist folgerichtig ⇔ Es ist logisch unmöglich, dass dieKonklusion falsch ist.

Zwei Beobachtungen

1. Wenn die Konklusion eines Argumentes tautologisch ist, dann ist das Argumentimmer folgerichtig (unabhängig davon, ob und welche Prämissen es hat).

• Begründung: Die Konklusion ist unmöglich falsch ⇒ Es ist erst recht unmöglich,dass die Prämissen wahr und die Konklusion falsch ist.

2. Wenn eine Prämisse eines Argumentes kontradiktorisch ist, dann ist das Argumentimmer folgerichtig (unabhängig davon, wie die Konklusion und die weiteren Prämissenlauten).

• Begründung: Die Prämissen sind unmöglich wahr ⇒ Es ist erst recht unmöglich,dass die Prämissen wahr und die Konklusion falsch ist.

14


1.4. Deduktion, Induktion, Abduktion

1.4.1. Deduktion vs. Induktion

Frage Es gibt auch Argumente, bei denen die Konklusion nicht wahr sein muss, wenndie Prämissen wahr sind, sondern die Konklusion lediglich wahrscheinlich wahr ist, wenndie Prämissen wahr sind. Sollten wir die Definition von Folgerichtigkeit nicht entsprechendlockern?

Definition 10 (Induktive Güte). Ein Argument ist induktiv gut (oder induktiv fol-gerichtig) genau dann, wenn gilt: Wenn die Prämissen wahr sind, ist die Konklusion wahr-scheinlich wahr.

Anmerkung Zum Zweck der Abgrenzung nennt man Folgerichtigkeit, so wie sie oben mit-tels logischer Notwendigkeit/Unmöglichkeit definiert wurde, auch deduktive Folgerichtig-keit.

Humes Beispiel Jemand argumentiert:

(1) Heute ging die Sonne auf.

(2) Gestern ging die Sonne auf.

(3) Vorgestern ging die Sonne auf.

(4) . . .

(5) ∴ Die Sonne wird auch morgen aufgehen.

Russells Beispiel Das Huhn argumentiert:

(1) Heute hat der Bauer mich gefüttert.

(2) Gestern hat der Bauer mich gefüttert.

(3) Vorgestern hat der Bauer mich gefüttert.

(4) . . .

(5) ∴ Der Bauer wird mich auch morgen füttern.

Ergebnis

• Die beiden Argumente haben dieselbe Form. Dennoch ist Humes Argument intuitivgut, Russells Argument intuitiv schlecht.

• Es hängt nicht nur von der Form bzw. dem themen-neutralen Vokabular ab, ob diePrämissen die Konklusion wahrscheinlich machen.

15


Verabredung Deshalb beschäftigen wir uns in diesem Logikkurs nicht mit Induktion. Mit„Folgerichtigkeit“ ist im Folgenden immer deduktive Folgerichtigkeit gemeint.

1.4.2. Deduktion vs. Induktion und Abduktion

Abduktion

• Unsere Definition von Induktion ist sehr weit. Oft werden induktive Argumente nochfeiner unterschieden.

• Peirces Unterscheidung:

– Deduktion: wie oben

– Induktion (im engeren Sinn): Schluss von Einzelfällen auf eine Generalisierung

– Abduktion: Schluss auf eine erklärende Hypothese, Schluss auf die beste Erklä-rung

Deduktion, Induktion, Abduktion

1. Alle ICEs haben Verspätung. Mein Zug ist ein ICE. Also: Mein Zug hat Verspätung.(Deduktion)

2. Mein Zug ist ein ICE. Mein Zug hat Verspätung. Also: Alle ICEs haben Verspätung.(Induktion i.e.S., Schluss vom Einzelfall auf eine Generalisierung)

3. Alle ICEs haben Verspätung. Mein Zug hat Verspätung. Also: Mein Zug ist ein ICE.(Abduktion, Schluss auf die beste Erklärung)

Ergebnis Es hängt nicht nur von der Form bzw. dem themen-neutralen Vokabular ab, obein abduktiver Schluss gut ist.

Verabredung Deshalb beschäftigen wir uns in diesem Logikkurs nicht mit Abduktion. Mit„Folgerichtigkeit“ ist im Folgenden immer deduktive Folgerichtigkeit gemeint.

1.5. Ergänzungen

1.5.1. Gliederung

Drei Unterscheidungen

1. Sätze vs. Propositionen

2. Verwendung vs. Erwähnung

3. Typen vs. Vorkommnisse

16


1.5.2. Sätze und Propositionen

Wiederholung Definition Argument Ein Argument besteht aus einer Menge von Sätzen– den Prämissen – und einem einzigen Satz, der als Konklusion gekennzeichnet ist.

Frage Bestehen Argumente wirklich aus Sätzen?

Warum Argumente nicht aus Sätzen bestehen

(1) Jetzt ist es 15:32.

(2) Jetzt ist es 15:34.

(3) ∴ Jetzt ist es 15:32 und jetzt ist es 15:34.

Auswertung

• Dieses Argument ist nicht folgerichtig, denn . . .

• . . . „ jetzt“ bezieht sich zu verschiedenen Äußerungszeitpunkten auf verschiedene Zeit-punkte.

Was sind Propositionen? Proposition (oder: Aussage) = das, was mit einer Äußerungeines Satzes gesagt wird

Erläuterung

• Äußerungen desselben Satzes können verschiedene Propositionen ausdrücken. Bsp:„Jetzt ist es angenehm warm“ drückt zu verschiedenen Zeitpunkten verschiedene Pro-positionen aus.

• Äußerungen verschiedener Sätze können dieselbe Proposition ausdrücken. Bsp: „Heuteist Mittwoch“ am Mittwoch geäußert, „Gestern war Mittwoch“ am Donnerstag geäu-ßert.

Verabredung In diesem Logikkurs gehen wir – vereinfachend! – davon aus, dass Argumenteaus Sätzen bestehen.

1.5.3. Verwendung vs. Erwähnung

Verwendung vs. Erwähnung eines sprachlichen Ausdrucks Wenn man über einen sprach-lichen Ausdruck spricht (Erwähnung, mention), dann gehört der sprachliche Ausdruck inAnführungszeichen. Wenn man einen sprachlichen Ausdruck verwendet (Verwendung, use),dann gehört der sprachliche Ausdruck nicht in Anführungszeichen.

17


Warum es wichtig ist, Verwendung und Erwähnung zu unterscheiden I

1. „Tim“ ist einsilbig. (Erwähnung; es geht um den Namen)

2. Tim ist einsilbig. (Verwendung; es geht um die Person)

Warum es wichtig ist, Verwendung und Erwähnung zu unterscheiden II

1. „Minute“ ist so lang wie „Stunde“. (Erwähnung, es geht um die Wörter)

2. Eine Minute ist so lang wie eine Stunde. (Verwendung, es geht um die Zeit)

Verabredung In der Logik sprechen wir oft über Sätze bzw. Formeln. Dann müssen wireigentlich Anführungszeichen verwenden. Da aber Mehrdeutigkeiten wie oben selten sind,werde ich mich nicht sklavisch um Präzision bemühen.

1.5.4. Typen vs. Vorkommnisse

Die Unterscheidung

• Typen (type) sind Arten von Gegenständen

• Vorkommnisse (token) sind Exemplare dieses Gegenstandes.

Beispiele

• Wie viele Buchstaben enthält Schillers Glocke? 29 Buchstaben (Typen, es kommt kein„x“ vor) oder mehr als 10.000 Buchstaben (Vorkommnisse)?

• Wie viele Logikskripte sind in diesem Raum? Eins (Typen) oder viele (Vorkommnisse)?

• Ist die Schlagzeile „Mehr Tiere vom Aussterben bedroht“ eine gute oder schlechte Nach-richt? Gibt es mehr vom Aussterben bedrohte Tierarten (Typen) oder mehr einzelneTiere (Vorkommnisse)?

18

Teil I.

Aussagenlogik

19

2. Aussagenlogik: Grundlagen

2.1. Wahrheitsfunktionale Satzoperatoren

2.1.1. Aussagenlogik: Die Idee

Programm

• Die Idee Logische Notwendigkeit ergibt sich aus dem themen-neutralen Vokabular,das die Form eines Satzes bestimmt.

• Frage Welches Vokabular ist das?

• Antwort Das werden wir Schritt für Schritt beantworten. Wir beginnen heute mitder Aussagenlogik (AL), in der wahrheitsfunktionale Satzoperatoren wie „und“, „oder“,„wenn–dann“ usw. im Mittelpunkt stehen.

2.1.2. Wahrheitsfunktionale Satzoperatoren

Satzoperatoren Satzoperatoren sind Ausdrücke, mit denen man aus beliebigen Sätzeneinen neuen, komplexen Satz bilden kann.

Beispiele

• Es ist nicht der Fall, dass es regnet.

• Leider regnet es.

• Es ist unbekannt, ob es regnet.

• Es regnet und Tammo lächelt.

• Es regnet, aber Tammo lächelt.

• Weil es regnet, lächelt Tammo.

• Während es regnet, lächelt Tammo.

• Wenn es regnet, dann lächelt Tammo.

20


Unterscheidung ein- und zweistellig

• Manche Satzoperatoren erzeugen aus einem Satz einen neuen Satz. Diese nennen wireinstellige Satzoperatoren.

• Manche Satzoperatoren erzeugen aus zwei Sätzen einen neuen Satz. Diese nennen wirzweistellige Satzoperatoren.

Definition 11 (n-stelliger Satzoperator). Ein Satzoperator, der aus n (n > 0) Sätzeneinen neuen Satz erzeugt, ist ein n-stelliger Satzoperator.

Definition 12 (Wahrheitsfunktionalität). Ein Satzoperator ist wahrheitsfunktio-nal genau dann, wenn der Wahrheitswert des komplexen Satz nur von den Wahrheitswertender Teilsätze abhängt.

Annahmen über Wahrheit Wir gehen in diesem Logikkurs ohne weitere Diskussion vonzwei Annahmen aus:

1. Es gibt genau zwei Wahrheitswerte, nämlich wahr und falsch. (Es gibt keine weiterenWahrheitswerte wie unbestimmt o. ä.)

2. Jeder Satz hat genau einen Wahrheitswert. (Kein Satz ist sowohl wahr als auch falschoder weder wahr noch falsch.)

„und“ Es regnet und Tammo lächelt.

Es regnet Tammo lächelt Es regnet und Tammo lächeltfalsch falsch falschwahr falsch falschfalsch wahr falschwahr wahr wahr

Ergebnis Der Wahrheitswert des Gesamtsatz hängt nur von den Wahrheitswerten der Teil-sätze ab. „und“ ist wahrheitsfunktional.

„weil“ Weil es regnet, lächelt Tammo.

Es regnet Tammo lächelt Weil es regnet, lächelt Tammofalsch falsch falschwahr falsch falschfalsch wahr falschwahr wahr ???

Ergebnis Der Wahrheitswert des Gesamtsatz hängt nicht nur von den Wahrheitswertender Teilsätze ab. „weil“ ist nicht wahrheitsfunktional.

21


2.2. Syntax

2.2.1. Was ist Aussagenlogik?

Programm

• Wir ordnen jedem natürlichsprachlichen Satz eine aussagenlogische Formel zu.

• In aussagenlogischen Formel gibt es Zeichen für die wahrheitsfunktionalen Satzopera-toren (Junktoren) und Zeichen für die Sätze (Satzbuchstaben).

• Die so gewonnenen Formeln geben die aussagenlogische Form des Satzes wieder.

Damit Sie schon einmal sehen, wohin der Hase läuft, zwei Vorabbeispiele:

1. Natürlichsprachlicher Satz: Es regnet und Tammo lächelt.

Aussagenlogische Formel: (P ∧Q)

2. Natürlichsprachlicher Satz: Gordon ist in der Mensa oder nicht.

Aussagenlogische Formel: (P ∨ ¬P )

Vorgehen

1. Welche Zeichenketten sind aussagenlogische Formeln? (dieses Kapitel)

2. Wie kann man natürlichsprachlichen Sätzen eine aussagenlogische Formel zuordnen?(nächstes Kapitel)

2.2.2. Verwendete Symbole

2.2.2.1. Symbole I: Junktoren

Junktoren Um die wahrheitsfunktionalen Satzoperatoren wiederzugeben, verwenden wirsogenannte Junktoren:

Junktor Entsprechung Bezeichnung

¬ Es ist nicht der Fall, dass . . . Negation∧ . . . und . . . Konjunktion∨ . . . oder . . . Disjunktion→ wenn . . . , dann . . . Konditional↔ . . . genau dann, wenn . . . Bikonditional

2.2.2.2. Symbole II: Satzbuchstaben

Satzbuchstaben Die Teilsätze, die durch wahrheitsfunktionale Satzoperatoren verbundenwerden, geben wir mit Satzbuchstaben wieder. Wir verwenden dafür:

P,Q,R,S,T,P1,Q1,R1, . . .

22


2.2.2.3. Symbole III: Gliederungszeichen

Klammern Außerdem verwenden wir runde Klammern, um komplexe Formeln zu gliedern:

(, )

2.2.2.4. Definition aussagenlogische Formel I

Definition 13 (Aussagenlogische Formel). Eine Zeichenkette x ist eine aussagenlo-gische Formel genau dann, wenn gilt:

1. x ist einer der Satzbuchstaben P,Q,R,S,T,P1,Q1, . . . oder

2. x ergibt sich aus einer aussagenlogische Formel durch Anwendung der folgenden Regeln:

2.1. Wenn Φ eine aussagenlogische Formel ist, dann ist auch ¬Φ eine aussagenlogischeFormel.

2.2. Wenn Φ und Ψ aussagenlogische Formeln sind, dann sind auch (Φ∧Ψ), (Φ∨Ψ),(Φ→ Ψ) und (Φ↔ Ψ) aussagenlogische Formeln.

2.2.2.5. Definition aussagenlogische Formel II

Rekursive Definition Bei der Definition handelt es sich um eine besondere Art von Defi-nition, nämlich einer rekursiven Definition. Eine rekursive Definition eines Begriffs bestehtaus zwei (oder drei) Bestandteilen:

1. einer Ausgangsmenge von Gegenständen, die unter den Begriff fallen

2. einer oder mehrere Klauseln, mit der die Ausgangsmenge erweitert wird („Wenn xdazugehört, dann gehört auch jedes y, das sich durch blabla aus x ergibt, dazu“)

3. (der Festlegung, dass sonst kein Gegenstand unter den Begriff fällt)

Beweise per vollständiger Induktion Rekursive Definitionen ermöglichen Beweise per voll-ständiger Induktion (auch: mathematische Induktion; nicht zu verwechseln mit Induktion imSinne von Abs. 1.4!); dazu mehr im letzten Kapitel (und der Übung).

2.2.2.6. Beispiel I

¬(¬P ∧Q) ist eine al Formel, denn:

1. P ist eine al Formel wegen 1

2. ¬P ist eine al Formel wegen 2.1

3. Q ist eine al Formel wegen 1

4. (¬P ∧Q) ist eine al Formel wegen 2.2

5. ¬(¬P ∧Q) ist eine al Formel wegen 2.1

23


2.2.2.7. Beispiel II

((P ∨Q)→ ¬T ) ist eine al Formel, denn:

1. P ist eine al Formel wegen 1

2. Q ist eine al Formel wegen 1

3. (P ∨Q) ist eine al Formel wegen 2.2

4. T ist eine al Formel wegen 1

5. ¬T ist eine al Formel wegen 2.1

6. ((P ∨Q)→ ¬T ) ist eine al Formel wegen 2.2

2.2.2.8. Beispiel III

¬¬¬¬¬P17 ist eine al Formel, denn:

1. P17 ist eine al Formel wegen 1

2. ¬P17 ist eine al Formel wegen 2.1

3. ¬¬P17 ist eine al Formel wegen 2.1

4. ¬¬¬P17 ist eine al Formel wegen 2.1

5. ¬¬¬¬P17 ist eine al Formel wegen 2.1

6. ¬¬¬¬¬P17 ist eine al Formel wegen 2.1

2.2.2.9. Gegenbeispiele

Keine al Formeln sind

• PQ (Junktor fehlt)

• P¬ (Junktor auf der falschen Seite)

• P ∧Q ∨R (Klammern fehlen)

• (¬P ) (zu viele Klammern, Klausel 2.1 erzeugt keine Klammern!)

2.2.2.10. Klammereinsparungsregel

Klammereinsparungsregel Wenn eine al Formel mit einer Klammer beginnt und mit einerKlammer endet, dürfen diese beiden Klammern weggelassen werden. (Das ist eine Erlaub-nisregel; es ist daher kein Fehler, die äußeren Klammern stehen zu lassen!)

24


Beispiele

• Statt (P ∧Q) darf auch P ∧Q geschrieben werden.

• Statt (P ∨ (Q→ ¬P )) darf auch P ∨ (Q→ ¬P ) geschrieben werden.

• Achtung: ¬(P ∧ Q) beginnt nicht mit einer Klammer und deshalb darf hier keineKlammer weggelassen werden!

Für weitere Klammereinsparungsregeln, die wir jedoch nicht übernehmen, siehe den Anhang„Logische Notation“.

25

3. Aussagenlogik: Logische Formnatürlichsprachlicher Sätze

3.1. Einleitung

Junktor Entsprechung in der natürl. Sprache Bezeichnung

¬ Es ist nicht der Fall, dass . . . Negation∧ . . . und . . . Konjunktion∨ . . . oder . . . Disjunktion→ wenn . . . , dann . . . Konditional↔ . . . genau dann, wenn . . . Bikonditional

Auffassungen über das Verhältnis zwischen Logik und natürlicher Sprache Es ist um-stritten, wie sich natürlichsprachliche Sätze zu der ihnen zugeordneten logischen Formelverhalten.

• Logische Form als Tiefengrammatik: Jeder natürlichsprachliche Satz hat eine(eindeutige) logische Form als eine Art Tiefengrammatik. Die logische Formel machtetwas explizit, das in dem natürlichsprachlichen Satz bereits implizit enthalten ist.

• Logische Form als Übersetzung: Jeder natürlichsprachliche Satz kann in die Spra-che der Logik übersetzt werden.

• Logische Form als Präzisierung: Bei der Logik handelt es sich um ein Hilfsmittel,um zwischen verschiedenen möglichen Lesarten zu unterscheiden und damit präziserals die natürliche Sprache zu sein.

Verabredung Wir werden diese Frage nicht entscheiden. Wir sprechen von der logischenForm eines Satzes und Formalisierung, ohne damit eine bestimmte Auffassung vom Verhält-nis zwischen Logik und natürlicher Sprache vorauszusetzen.

Vorgehen beim Analysieren natürlichsprachlicher Sätze

1. Natürlichsprachlicher Satz: Der Ausgangspunkt

2. Paraphrase: Synonyme Umformulierung, die die logische Struktur deutlich macht(Pronomina auflösen, Ellipsen auflösen usw.)

3. Symbolisierungsbasis: Angabe, welcher Teilsatz durch P repräsentiert wird, welcherdurch Q usw.

4. Formalisierung: Die Lösung

26

3. Aussagenlogik: Logische Form natürlichsprachlicher Sätze

Hinweis zu Übungsaufgaben Sie können bei den Aufgaben auf den Schritt Paraphraseverzichten!

3.2. Negation

3.2.1. Analyse Negation

Der Junktor ¬ ist ein einstelliger Junktor.

Φ ¬Φ

W FF W

Merke Bei der Negation wird der Wahrheitswert „umgedreht“.

In der natürlichen Sprache entsprechen viele Ausdrücke dem Junktor ¬:

• „Es ist nicht der Fall, dass . . . “

• „nicht“

• „kein“, „nichts“, „niemand“, „nirgends“, „niemals“, „keinesfalls“, „keineswegs“

• die Vorsilben „un-“, „in-“ und „a-“ (nicht immer!)

Beispiel 1

• Natürlichsprachlicher Satz: Gordon hat keinen Hunger.

• Paraphrase: Es ist nicht der Fall, dass Gordon Hunger hat.

• Symbolisierungsbasis: P: Gordon hat Hunger.

• Formalisierung: ¬P

Beispiel 2

• Natürlichsprachlicher Satz: Keine Übung wird von keinem Studenten besucht.

• Paraphrase: Es ist nicht der Fall, dass es eine Übung gibt, die von keinem Studentenbesucht wird.

• Falsche Paraphrase: Es ist nicht der Fall, dass es keine Übung gibt, die von einemStudenten besucht wird.

• Symbolisierungsbasis: P: Es gibt eine Übung, die von keinem Studenten besucht wird.

• Formalisierung: ¬P

27


3.2.2. Probleme Negation

Keine Negation trotz Negationsindikator

• Bei Nebel ist die Gasse unheimlich. = ? ¬P

• Katzen sind nicht unmoralisch, sondern amoralisch. = ???

Negation trotz fehlendem Negationsindikator

• Das Fenster ist geschlossen und es ist offen. = ? P ∧ ¬P

• Sinje ist still oder sie macht ein Geräusch. = ? P ∨ ¬P

Doppelte Negation

• Niemandem habe ich nichts weggenommen!

= ? Ich habe niemandem etwas weggenommen.

= ? Ich habe jedem etwas weggenommen.

Negation und Skopus

• Nicht Tammo hat den Müll rausgebracht.

= ? Es ist nicht der Fall, dass Tammo den Müll rausgebracht hat.

= ? Jemand hat den Müll rausgebracht, aber Tammo hat ihn nicht rausgebracht.

Merke Ob ein natürlichsprachlicher Satz eine Negation enthält und, falls ja, was genaunegiert wird, lässt sich nicht mechanisch entscheiden.

3.3. Konjunktion

3.3.1. Analyse Konjunktion

∧ ist ein zweistelliger Junktor.

Φ Ψ Φ ∧Ψ

W W WW F FF W FF F F

Merke Eine Konjunktion ist wahr, wenn beide Teilsätze wahr sind, und ansonsten falsch.

28


Beispiel 1

• Natürlichsprachlicher Satz: Sinje und Johanna gehen gerne ins Kino.

• Paraphrase: Sinje geht gerne ins Kino und Johanna geht gerne ins Kino.

• Symbolisierungsbasis: P: Sinje geht gerne ins Kino, Q: Johanna geht gerne ins Kino

• Formalisierung: P ∧Q

Beachte Nicht jedes „und“ verbindet zwei (Teil-)Sätze, z. B.

• Sinje und Johanna sind Nachbarn. ≠ Sinje ist ein Nachbar und Johanna ist ein Nachbar.

• Regensburg liegt zwischen München und Nürnberg. ≠ Regensburg liegt zwischen Mün-chen und Regensburg liegt zwischen Nürnberg.

Beide Beispielsätze werden daher schlicht mit P formalisiert.

Beispiel 2

• Natürlichsprachlicher Satz: Tammo, der Johanna aus dem Platon-Seminar kennt, gehtmit ihr in die Mensa.

• Paraphrase: Tammo kennt Johanna aus dem Platon-Seminar und Tammo geht mitJohanna in die Mensa.

• Symbolisierungsbasis P: Tammo kennt Johanna aus dem Platon-Seminar, Q: Tammogeht mit Johanna in die Mensa

• Formalisierung: P ∧Q

Beachte Nur manche Relativsätze sind Konjunktionen! Beispiel: Wilfried sucht jemanden,der gerne Doppelkopf spielt ≠ Wilfried sucht jemanden und jemand spielt gerne Doppelkopf.

Beispiel 3

• Natürlichsprachlicher Satz: Carina geht früh schlafen, aber Wilfried nicht.

• Paraphrase: Carina geht früh schlafen und es ist nicht der Fall, dass Wilfried frühschlafen geht.

• Symbolisierungsbasis P: Carina geht früh schlafen, Q: Wilfried geht früh schlafen

• Formalisierung: P ∧ ¬Q

29


Sätze, die von uns als Konjunktion behandelt werden

• Einerseits P, andererseits Q.

• Sowohl P, als auch Q.

• P, aber Q.

• Obwohl P, Q.

• P, jedoch Q.

• Während P, Q.

• Nachdem P, Q.

Verabredung Obwohl die Satzoperatoren streng genommen nicht wahrheitsfunktional sind,formalisieren wir alle diese Sätze mit P ∧Q.

Beispiel zur Rechtfertigung dieses Vorgehens

A: Obwohl Studiengebühren ungerecht sind, verbessern sie die Lehre.

B: Nein, sie verbessern die Lehre nicht. Sie werden sinnlos verplempert.

Erster Vorschlag: „obwohl“ nicht wahrheitsfunktional

• A: P

• B: ¬Q

• Ergebnis: B widerspricht A nicht.

Zweiter Vorschlag: „obwohl“ wahrheitsfunktional

• A: R ∧Q

• B: ¬Q

• Ergebnis: B widerspricht einer Teilbehauptung von A.

Ergebnis Pro wahrheitsfunktionale Analyse: Es wird deutlich, inwiefern B A widerspricht.

Merke Wir konzentrieren uns auf den wahrheitsfunktionalen Kern natürlichsprachlicherSatzoperatoren, auch wenn wir damit den Inhalt natürlichsprachlicher Sätze nicht immervollständig einfangen können.

30


3.3.2. *Grices Theorie der Implikaturen

Problemfall: „und“ immer wahrheitsfunktional?

1. Tim trank eine Flasche Whisky und fuhr mit dem Auto nach Hause.

2. Tim fuhr mit dem Auto nach Hause und trank eine Flasche Whisky.

Theorie der Implikaturen Bei einer Äußerung eines Satzes kann unterschieden werdenzwischen . . . (Grice „Logic and Conversation“, 1975)

• was wortwörtlich gesagt wird oder aus dem wortwörtlichen Gesagten logisch folgt (Im-plikation)

• was mitgemeint wird und suggeriert wird (Implikatur)

Grices These Die zeitliche Reihenfolge wird nicht impliziert, sondern implikiert.

Weitere Beispiele für Implikaturen

1. „Einige Politiker sind ehrlich“ / Implikatur: Nicht alle Politiker sind ehrlich.

2. „Kommst du zur Party? – Ich muss noch ein Referat vorbereiten.“ / Implikatur: Ichkomme nicht.

3. „Ich habe zwei Kinder“ / Implikatur: Ich habe genau zwei Kinder.

Grices Test: Kündbarkeit

1. Tim trank eine Flasche Whisky und fuhr nach Hause, aber es ist nur eins davon wahr.(Widerspruch)

2. Tim trank eine Flasche Whisky und fuhr nach Hause, aber nicht unbedingt in dieserReihenfolge. (Kein Widerspruch)

Implikaturen kann man kündigen, Implikationen nicht.

Maximen Grice erklärt Implikaturen dadurch, dass Gesprächspartner einander unterstel-len, die folgenden Maximen einzuhalten:

1. Maxime der Qualität: Man sagt nur, was man weiß oder wofür man hinreichend guteGründe hat.

2. Maxime der Quantität: Man sagt genug, aber auch nicht zuviel.

3. Maxime der Relevanz: Man sagt nur, was einschlägig fürs Gesprächsthema ist.

4. Maxime der Modalität: Man sagt alles in übersichtlicher, verständlicher Art und Weise.

31


Anwendung auf „und“ Wer bei einer Konjunktion anti-chronologisch erzählt, würde dieMaxime der Modalität verletzen. Da wir aber Befolgung der Maximen unterstellen, unter-stellen wir, dass chronologisch erzählt wird.

3.4. Disjunktion

3.4.1. Analyse Disjunktion

∨ ist ein zweistelliger Junktor.

Φ Ψ Φ ∨Ψ

W W WW F WF W WF F F

Merke Eine Disjunktion ist wahr, wenn mindestens ein Teilsatz wahr ist, und ansonstenfalsch.

Terminologische Alternativen Disjunktion = Adjunktion

Beispiel 1

• Natürlichsprachlicher Satz: Johanna ist nicht hungrig oder sie ist zu müde, in die Mensazu kommen.

• Paraphrase: Es ist nicht der Fall, dass Johanna hungrig ist, oder Johanna ist zumüde, in die Mensa zu kommen.

• Symbolisierungsbasis: P: Johanna ist hungrig, Q: Johanna ist ist zu müde, in die Mensazu kommen.

• Formalisierung: ¬P ∨Q

Unterscheidung: Einschließendes und ausschließendes Oder

1. Einschließend: das eine oder das andere oder beides

2. Ausschließend: das eine oder das andere aber nicht beides

Terminologische Alternativen Ausschließendes Oder = Kontravalenz = AntivalenzAußerdem wird manchmal – anders als hier! – das einschließende Oder „Alternation“ und

das ausschließende „Disjunktion“ genannt.

Verabredung

• Wir verstehen „oder“ immer als einschließendes Oder.

• Wir verstehen „entweder–oder“ immer als ausschließendes Oder.

32


Beispiel 2

• Natürlichsprachlicher Satz: Entweder Tammo kommt in die Mensa oder Gordon isstalleine.

• Paraphrase: Tammo kommt oder Gordon isst alleine und es ist nicht der Fall, dassTammo kommt und Gordon alleine isst.

• Symbolisierungsbasis: P: Tammo kommt, Q: Gordon isst alleine.

• Formalisierung: (P ∨Q) ∧ ¬(P ∧Q)

• (Alternative: ¬(P ↔ Q))

3.4.2. *Probleme Disjunktion

Zwei Probleme

1. „oder“ wird manchmal ausschließend verwendet.

2. „entweder–oder“ wird nicht immer ausschließend verwendet.

Beispiele für ausschließendes „oder“

• Zu Beginn jeder Runde darf jeder Spieler ein Dorf bauen oder seine Spielfigur auf einbeliebiges freies Feld versetzen.

• Donnerstags kommt Carina zur Logikvorlesung oder geht schwimmen. Nächsten Don-nerstag kommt sie zur Logikvorlesung. Also geht sie nicht schwimmen. (Dieses Argu-ment ist intuitiv folgerichtig, ist dies aber nur, wenn „oder“ ausschließend verwendetwerden kann.)

Zwei Auffassungen von „entweder–oder“ Dass „entweder–oder“ ausschließend zu verste-hen ist, ist umstritten. Zwei Theorien sind im Umlauf:

1. „entweder“ dient zur Unterscheidung zwischen einschließendem und ausschließendemOder.

2. „entweder“ ist ein natürlichsprachliches Äquivalent für Klammern.

Beispiel Wir kaufen Bier und Prosecco oder Wein.

Zwei Lesarten mit Hilfe von Klammern

• Wir kaufen (Bier und Proseccco) oder Wein.

• Wir kaufen Bier und (Prosecco oder Wein).

33


Zwei Lesarten mit Hilfe von „entweder“ und „sowohl“

• Wir kaufen entweder Bier und Prosecco oder Wein.

• Wir kaufen sowohl Bier als auch Prosecco oder Wein.

Verabredung Da die Funktion von „entweder–oder“ umstritten ist, schließen wir uns derMehrheitsmeinung an: „entweder–oder“ ist das ausschließende Oder.

3.5. Konditional

3.5.1. Analyse Konditional

→ ist ein zwei-stelliger Junktor.

Φ Ψ Φ→ Ψ

W W WW F FF W WF F W

Merke Ein Konditional ist falsch, wenn der Vordersatz wahr und der Nachsatz falsch ist –und sonst wahr.

Terminologische Alternativen

• Vordersatz = das Antezedens

• Nachsatz = das Konsequens

• Konditional = Subjunktion = materiale Implikation

Frage Warum gerade diese Wahrheitstafel?

Beispiel 1 Wenn du mich besuchen kommst, koch ich eine Tomatensuppe!

Auswertung Ausgeschlossen wird, dass der Besuch kommt, es aber keine Tomatensuppegibt. Darüber, was geschehen wird, wenn kein Besuch kommt, wird keine Aussage gemacht– vielleicht wird trotzdem Tomatensuppe gekocht, vielleicht auch nicht.Also ist das „wenn–dann“ falsch, wenn der Vordersatz wahr und der Nachsatz falsch ist

und ansonsten immerhin nicht falsch, also wahr.

Beispiel 2

• Wenn Sie Ihr Auto hier stehenlassen, dann rufe ich die Polizei!

. . . besagt so viel wie . . .

• Sie fahren Ihr Auto weg oder ich rufe die Polizei!

34


Auswertung

• P → Q besagt also dasselbe wie ¬P ∨Q.

• ¬P ∨Q ist falsch, wenn P wahr und Q falsch ist, und ansonsten wahr.

• Das ist nichts anderes als die vorgeschlagene Wahrheitstafel!

Ein weiteres Argument . . . werden wir später kennenlernen: Mit dieser Analyse des Kon-ditionals lassen sich All-Sätze wie „Alle Menschen sind sterblich“ als versteckte Konditionaledeuten, nämlich „Wenn etwas ein Mensch ist, dann ist es sterblich“.

Beispiel 3

• Natürlichsprachlicher Satz: Falls Sinje in die Mensa kommt, kommt auch Carina.

• Paraphrase: Wenn Sinje in die Mensa kommt, dann kommt Carina in die Mensa.

• Symbolisierungsbasis: P: Sinje kommt in die Mensa, Q: Carina kommt in die Mensa

• Formalisierung: P → Q

Weitere Sätze, die von uns als Konditionale behandelt werden

• Sofern P, Q

• Vorausgesetzt P, Q.

• Gesetzt den Fall, dass P, Q.

3.5.2. „Nur“-Konditionale

„Nur wenn“ und „nur dann“

1. Nur wenn Sinje in der Mensa ist, freut sich Carina.

2. Nur dann ist Sinje in der Mensa, wenn Carina sich freut.

Merke „nur“ dreht die Richtung des Pfeils um, d. h. was vorher der Vordersatz wahr, istjetzt der Nachsatz und umgekehrt.

Lösungen P: Sinje ist in der Mensa, Q: Carina freut sich

1. = Wenn Carina sich freut, ist Sinje in der Mensa. (Q→ P )

2. = Wenn Sinje in der Mensa ist, freut sich Carina. (P → Q)

35


Wirklich?

1. Nur wenn Gordon trainiert hat, schafft er den Marathon.

= Wenn Gordon den Marathon schafft, dann hat Gordon trainiert.

• Denn: Training ist keine Garantie dafür, den Marathon zu schaffen, sondern nureine notwendige Voraussetzung: Kein Marathon ohne Training, nicht umgekehrt.

2. Gordon trainiert nur dann, wenn es über 10℃ ist.

= Wenn Gordon trainiert, ist es über 10℃.

• Denn: Gordon trainiert nicht pausenlos, bis das Thermometer unter 10℃ sinkt!Es handelt sich nur um eine notwendige Voraussetzung.

3.5.3. *Probleme Konditional

Problematische Konditionale Die folgenden Sätze sind alle wahr – das ist kontraintuitiv:

• Wenn 2+2=37, dann ist Wilfried in der Mensa.

• Wenn der letzte Dinosaurier weiblich war, ist 2+2=4.

• Wenn Watson der Vater von Holmes ist, ist Watson jünger als Holmes.

Allgemein (sog. Paradox der materialen Implikation)

• P ⊧ Q→ P (mit beliebigem Q)

• ¬P ⊧ P → Q (mit beliebigem Q)

Problematische Argumente mit Konditionalen Das folgende Argument ist folgerichtig –das ist kontraintuitiv:

1. Wenn Gordon zu spät kommt, warten alle auf ihn. (P → Q)

2. ∴ Wenn Gordon zu spät kommt und dies niemandem auffällt, warten alle auf ihn.((P ∧Q)→ R)

Kontrafaktische Konditionale Die Analyse des Konditionals ist nicht anwendbar auf sog.kontrafaktische Konditionale:

• Wenn Gordon den Bus verpasst hätte, wäre er zu spät gekommen.

Ergebnis Die wahrheitsfunktionale Analyse von „wenn–dann“ hat Vor- und Nachteile. So-lange es keine überzeugende Alternative zu dieser Analyse gibt, sollten wir sie trotz ihrerNachteile schlucken.

36


3.6. Bikonditional

3.6.1. Analyse Bikonditional

↔ ist ein zwei-stelliger Junktor.

Φ Ψ Φ↔ Ψ

W W WW F FF W FF F W

Merke Ein Bikonditional ist wahr, wenn beide Teilsätze wahr oder beide Teilsätze falschsind – und sonst falsch.

Terminologische Alternativen Bikonditional = Bisubjunktion = materiale Äquivalenz

Merke Die Bikonditional kann auch so definiert werden:

(Φ↔ Ψ) ≡def (Φ→ Ψ) ∧ (Ψ→ Φ)

Deshalb heißt das Bi-Konditional auch so!

Sätze, die von uns als Bikonditionale behandelt werden

• Genau dann P, wenn Q.

• P dann und nur dann, wenn Q.

Beispiel 1

• Natürlichsprachlicher Satz: Tammo kommt in die Mensa, es sei denn er ist schonsatt.

• Paraphrase: Tammo kommt genau dann in die Mensa, wenn es nicht der Fall ist,dass er schon satt ist.

• Symbolisierungsbasis: P: Tammo kommt in die Mensa, Q: Er ist schon satt.

• Formalisierung: P ↔ ¬Q

Beispiel 2

• Natürlichsprachlicher Satz: Entweder Tammo kommt in die Mensa oder Gordon isstalleine.

• Symbolisierungsbasis: P: Tammo kommt in die Mensa, Q: Gordon isst alleine

37


P Q (P ↔ Q) ¬(P ↔ Q)W W W FW F F WF W F WF F W F

• Formalisierung: ¬(P ↔ Q)

3.7. Zusammenfassung

3.7.0.1. Zusammenfassung

Natürliche Sprache AL

Es ist nicht der Fall, dass P ¬PP und Q P ∧QP, aber Q P ∧QObwohl P, Q P ∧QEinerseits P, andererseits Q P ∧QSowohl P, als auch Q P ∧QWeder P, noch Q ¬P ∧ ¬QP oder Q P ∨QEntweder P oder Q Möglichkeit a: (P ∨Q) ∧ ¬(P ∧Q)

Möglichkeit b: ¬(P ↔ Q)Wenn P, dann Q P → QFalls P, Q P → QNur wenn P, Q Q→ PNur dann P, wenn Q P → QP genau dann, wenn Q P ↔ QP dann und nur dann, wenn Q P ↔ QP, es sei denn Q P ↔ ¬Q

38

4. Aussagenlogik: Wahrheitstafelmethodeund Semantik

4.1. Wahrheitstafelmethode

4.1.1. Grundlagen der Wahrheitstafelmethode

Die Wahrheitstafelmethode ist . . . ein Verfahren, mit dem festgestellt werden kann, ob. . .

• . . . eine aussagenlogische Formel tautologisch, kontradiktorisch oder kontingent ist.

• . . . ein aussagenlogisches Argument folgerichtig ist.

• . . . zwei aussagenlogische Formeln äquivalent sind.

Anmerkung: Die Wahrheitstafelmethode wird im Logikkurs an der Tafel, nicht per Beamervorgestellt. Im Folgenden das Wichtigste und einige Beispiele zum Nacharbeiten.

Schritt für Schritt Wie überprüfe ich, ob eine Formel tautologisch, kontradiktorisch oderkontingent ist?

1. Bestimme die Anzahl n der Satzbuchstaben, die in der zu prüfenden Formel enthaltensind.

2. Zeichne eine Tabelle, die (a) mit n Spalten beginnt und die (b) (2n + 1) Zeilen hat.

3. Trage in die erste Zeile jeweils in die erste bis n-te Spalte einen der n Satzbuchstabenein.

4. Trage in die Zeilen unterhalb der Spalten, in denen die n Aussagebuchstaben ein-getragen sind, die 2n möglichen Zuordnungen der Wahrheitswerte W und F zu denAussagebuchstaben ein.

5. Baue in den Spalten beginnend mit der n + 1-ten Spalte sukzessive (das heißt gemäßder rekursiven Definition einer aussagenlogischen Formel) die zu überprüfende Formelauf.

6. Bestimme spaltenweise von links nach rechts beginnend mit der n + 1-ten Spalte dieWahrheitswerte der jeweiligen (Teil-)Formel.

7. Interpretiere das Ergebnis für die Gesamtformel auf der folgenden Grundlage:

• Die Formel ist tautologisch genau dann, wenn in der Spalte der Gesamtformelausschließlich Ws zu finden sind.

39

4. Aussagenlogik: Wahrheitstafelmethode und Semantik

• Die Formel ist kontradiktorisch genau dann, wenn in der Spalte der Gesamt-formel ausschließlich Fs zu finden sind.

• Die Formel ist kontingent genau dann, wenn in der Spalte der Gesamtformelmindestens ein W und mindestens ein F zu finden sind.

Erläuterung Anzahl Zeilen Die Anzahl der Zeilen bemisst sich nach der Anzahl der Satz-buchstaben:

• 1 Satzbuchstabe = 2 Zeilen

• 2 Satzbuchstaben = 4 Zeilen

• 3 Satzbuchstaben = 8 Zeilen

• ⋯

• n Satzbuchstaben = 2n Zeilen

(Dazu kommt dann noch die „Überschriftenzeile“.)

4.1.2. Beispiele

4.1.2.1. Beispiel I

Ist P ∧ ¬P tautologisch, kontradiktorisch oder kontingent?

P ¬P P ∧ ¬PW F FF W F

Da in der Spalte für P ∧ ¬P nur Fs vorkommen, ist diese Formel kontradiktorisch.

4.1.2.2. Beispiel II

Ist (P ∨ ¬Q) ∨Q tautologisch, kontradiktorisch oder kontingent?

P Q ¬Q (P ∨ ¬Q) (P ∨ ¬Q) ∨QW W F W WW F W W WF W F F WF F W W W

Da in der Spalte für (P ∨ ¬Q) ∨Q nur Ws vorkommen, ist diese Formel tautologisch.

40


4.1.2.3. Beispiel III

Ist P → ¬(P ∧Q) tautologisch, kontradiktorisch oder kontingent?

P Q (P ∧Q) ¬(P ∧Q) P → ¬(P ∧Q)W W W F FW F F W WF W F W WF F F W W

Da in der Spalte für P → ¬(P ∧ Q) sowohl mindestens ein W, als auch mindestens ein Fvorkommt, ist diese Formel kontingent.

4.1.3. Argumente überprüfen

4.1.3.1. Wahrheitsfafelmethode und Argumente I

Folgerichtigkeit Aufgabe: Ist das Argument folgerichtig?

Lösungsmöglichkeit 1

• Das Argument ist folgerichtig genau dann, wenn in jeder Zeile, in der bei den Prä-missen Ws stehen, auch bei der Konklusion ein W steht.

• Beachte: Wenn es keine Zeile gibt, in der alle Prämissen wahr sind, ist das Argumentfolgerichtig!

4.1.3.2. Wahrheitsfafelmethode und Argumente II

Folgerichtigkeit Aufgabe: Ist das Argument folgerichtig?

Lösungsmöglichkeit 2

• Aus den Prämissen P1, P2, . . . , Pn folgt die KonklusionK genau dann, wenn die Formel((P1 ∧ P2) ∧ ⋅ ⋅ ⋅ ∧ Pn)→K tautologisch ist.

4.1.4. Beispiele

4.1.4.1. Beispiele I

Gilt P → Q,¬Q ⊧ ¬P?P Q P → Q ¬Q ¬PW W W F FW F F W FF W W F WF F W W W

Wir suchen zunächst die Zeilen, in denen beide Prämissen wahr sind (Spalten 3 und 4). Dasist nur in der letzten Zeile der Fall. Nun ist in dieser Zeile aber auch die Konklusion (Spalte5) wahr. Also ist das Argument folgerichtig.

41


4.1.4.2. Beispiele II

Gilt P ∨Q,P ∧ ¬Q ⊧ P?

P Q P ∨Q ¬P ¬Q ¬P ∧ ¬QW W W F F FW F W F W FF W W W F FF F F W W W

Wir suchen zunächst die Zeilen, in denen beide Prämissen wahr sind (Spalten 3 und 6). Dasist aber in keiner Zeile der Fall. Also ist das Argument folgerichtig. (Hinweis: Folgerichtigkeitist definiert als Es ist unmöglich, dass die Prämissen wahr sind und. . . . Die Prämissen sindbei diesem Argument unmöglich wahr und deshalb ist das Argument folgerichtig.)

4.1.5. Äquivalenz überprüfen

Äquivalenz Aufgabe: Sind die beiden Formeln äquivalent?

Lösungsmöglichkeit 1 Die beiden Formeln sind äquivalent genau dann, wenn in jederZeile, in der die eine Formel ein W stehen hat, auch die andere Formel ein W stehen hat,und in jeder Zeile, in der die eine Formel ein F hat, die andere Formel auch ein F hat.

Lösungsmöglichkeit 2 Zwei Formeln Φ und Ψ sind äquivalent genau dann, wenn dieFormel Φ↔ Ψ tautologisch ist.

4.1.6. Vor- und Nachteile der Wahrheitsfafelmethode

Vorteile

• Rein mechanisches Verfahren

• Man muss nur wissen, wie die Junktoren definiert sind.

Nachteile

• Bei mehr als 3 Satzbuchstaben (mehr als 8 Zeilen) umständlich.

• Bei langen Formeln umständlich

Hinweis Wir werden noch ein zweites Verfahren kennenlernen (den sog. Baumkalkül), dasdiese Nachteile nicht hat. Bevor wir dahin kommen, werden wir jedoch ausgehend von derWahrheitsfafelmethode die formale Semantik der AL besprechen.

42


4.2. Formale Sprachen

4.2.1. Was ist eine formale Sprache?

Eine formale Sprache besteht aus Syntax, Semantik und Beweisverfahren (Kalkül).

1. Syntax: Welche Zeichenketten sind Formeln?

2. Semantik: Was bedeuten die Zeichen?

3. Kalkül: Wie kann man prüfen, ob ein Argument folgerichtig ist?

Motivation

• Philosophische Motivation:Unsere bisherigen Definitionen enthalten die Ausdrücke„logisch notwendig“ bzw. „logisch unmöglich“. Mittels der formalen Semantik lassen sichDefinitionen geben, die auf diese ungeklärten Begriffe verzichten.

• Formale Motivation: Nur wenn man die Logik formal darstellt, kann man „ordent-liche“ Beweise in der Logik führen. (Das werden wir aber nicht machen!)

4.2.2. Syntax, Semantik, Kalkül

4.2.2.1. Syntax

Zur Syntax gehört . . .

1. ein Vokabular (d. h. eine Menge an Zeichen)

2. eine Definition, die angibt, welche Zeichenketten wohlgeformte Formeln sind.

Diese Aufgabe haben wir mit der rekursiven Definition einer Formel bereits erledigt.

4.2.2.2. Semantik

Die Semantik . . .

1. gibt an, was die einzelnen Zeichen bedeuten, und

2. wie sich aus der Bedeutung der einzelnen Zeichen die Bedeutung einer komplexenFormeln ergibt.

Diese Aufgabe haben wir implizit schon erledigt, soll nun aber auch explizit erledigt werden.

4.2.2.3. Kalkül

Ein Kalkül/Beweisverfahren haben wir schon kennen gelernt: Die Wahrheitstafelmethode.

43


4.2.2.4. Objekt- und Metasprache

Objekt- und Metasprache

• Objektsprache: Sprache, über die geredet wird.

• Metasprache: Sprache, in der geredet wird.

Beispiele

• „The sun is shining“ ist ein englischer Satz. (Objektsprache ist Englisch, MetaspracheDeutsch.)

• P → P ist eine Tautologie. (Objektsprache ist AL, Metasprache Deutsch.)

• ⊧ P → P (Objektsprache ist AL, Metasprache ist Deutsch plus Zusatzsymbole.)

4.3. Semantik

4.3.1. Semantik

Interpretation Eine Interpretation ordnet jedem Satzbuchstaben genau einen der beidenWahrheitswerte {W,F} zu. Eine Interpretation ist also eine Funktion

I ∶ {P,Q,R, . . .}→ {W,F}

Anstelle von „Interpretation“ wird auch der Ausdruck „Modell“ verwendet.

Bewertung Eine Bewertung ist eine Funktion BI , die auf der Grundlage der Interpreta-tion I jeder Formel einen der beiden Wahrheitswerte {W,F} zuordnet:

BI ∶Menge aller al Formeln→ {W,F}

und dabei wie folgt aufgebaut ist:

1. Wenn Φ ein Satzbuchstabe von AL ist, dann gilt:

BI(Φ) =W gdw. I(Φ) =W

BI(Φ) = F gdw. I(Φ) = F

44


2. Wenn Φ irgendeine Formel von AL ist, dann gilt:

BI(¬Φ) =W gdw. BI(Φ) = F

BI(¬Φ) = F gdw. BI(Φ) =W

3. Wenn Φ und Ψ irgendwelche Formeln von AL sind, dann gilt:

BI((Φ ∧Ψ)) =W gdw. BI(Φ) =W und BI(Ψ) =W

und ansonsten BI((Φ ∧Ψ)) = F


BI((Φ ∨Ψ)) =W gdw. BI(Φ) =W oder BI(Ψ) =W

und ansonsten BI((Φ ∧Ψ)) = F


BI((Φ→ Ψ)) = F gdw. BI(Φ) =W und BI(Ψ) = F

und ansonsten BI((Φ ∧Ψ)) =W

Wahrheit relativ zu einer Interpretation Statt BI(Φ) =W sagen wir auch:

• Φ ist wahr relativ zu der Interpretation I oder

• Die Interpretation I erfüllt die Formel Φ.

Totale vs. partielle Interpretation Da wir uns meistens nicht für alle Satzbuchtstaben undalle Formeln interessieren, arbeiten wir meist mit sog. partiellen Interpretationen:

Definition 14 (Totale Interpretation). Eine totale Interpretation ordnet jedemSatzbuchstaben genau einen Wahrheitswert zu.

Definition 15 (Partielle Interpretation). Eine partielle Interpretation ordnetmanchen (bspw. den von uns betrachteten) Satzbuchstaben genau einen Wahrheitswertzu.

Semantik und Wahrheitstafeln

• Jede Zeile einer Wahrheitstafel ist eine (partielle) Bewertung.

• Der Anfang jeder Zeile – das heißt: die Verteilung von Wahrheitswerten auf die Satz-buchstaben – ist eine (partielle) Interpretation.

45


Beispiel

P Q (P ∧Q) ¬(P ∧Q) P → ¬(P ∧Q)W W

::W

:F

::F

W F F W WF W F W WF F F W W

• Unterstrichen = eine (partielle) Interpretation mit I(P ) =W und I(Q) =W

• Unterstrichen oder Unterkringelt = Bewertung mit zum Beispiel BI((P ∧ Q)) = W ,BI(¬(P ∧Q)) = F usw.

4.3.2. Definitionen ohne modale Termini

Zur Erinnerung: Wir suchen nach Definitionen, die ohne „(logisch) notwendig“ bzw. „(lo-gisch) unmöglich“ auskommen. Der Begriff der Interpretation leistet genau das.

Definition 16 (Tautologie). Eine Formel Φ ist tautologisch genau dann, wenn gilt: Fürjede Interpretation I gilt, dass BI(Φ) =W .

Definition 17 (Kontradiktion). Eine Formel Φ ist kontradiktorisch genau dann, wenngilt: Für jede Interpretation I gilt, dass BI(Φ) = F .

Definition 18 (Kontingenz). Eine Formel Φ ist kontingent genau dann, wenn gilt: Esgibt eine Interpretation I, so dass BI(Φ) = W und es gibt eine Interpretation I ′, so dassBI′(Φ) = F .

Definition 19 (Folgerichtigkeit, negative Formulierung). Ein Argument ist fol-gerichtig genau dann, wenn gilt: Es gibt keine Interpretation I, so dass für jede PrämissePj ∶ BI(Pj) =W und für die Konklusion K ∶ BI(K) = F .

Definition 20 (Folgerichtigkeit, positive Formulierung). Ein Argument ist fol-gerichtig genau dann, wenn gilt: Für jede Interpretation I gilt: Wenn für jede PrämissePj ∶ BI(Pj) =W , gilt auch für die Konklusion K ∶ BI(K) =W .

Definition 21 (Äquivalenz). Zwei Formeln Φ und Ψ sind äquivalent genau dann, wennfür jede Interpretation I gilt I(Φ) = I(Ψ)

Definition 22 (Konsistenz). Eine MengeM von Formeln ist konsistent (erfüllbar) genaudann, wenn gilt: Es gibt eine Interpretation I, so dass für jedes m ∈M ∶ BI(m) =W .

Definition 23 (Inkonsistenz). Eine MengeM von Formeln ist inkonsistent (unerfüllbar)genau dann, wenn gilt: Es gibt keine Interpretation I, so dass für jedes m ∈M ∶ BI(m) =W .

46

5. Aussagenlogik: Baumkalkül

5.1. Baumkalkül

Was ist ein Baumkalkül? Der Baumkalkül ist ein weiteres Beweisverfahren (Kalkül) nebenWahrheitstafeln, das heißt ein (rein syntaktisches, streng nach Regeln ablaufendes) Verfah-ren, mit dem man feststellen kann, ob . . .

• . . . eine Formel tautologisch, kontradiktorisch oder kontingent ist.

• . . . ein Argument folgerichtig ist.

• . . . zwei Formeln äquivalent sind.

Der Grundgedanke Es handelt sich um ein Widerspruchsverfahren:

• Um zu zeigen, dass eine Formel tautologisch ist, nehmen wir an, sie könnte falschwerden und zeigen, dass sich daraus ein Widerspruch ergibt.

• Um zu zeigen, dass ein Argument folgerichtig ist, nehmen wir an, die Prämissen könn-ten wahr und die Konklusion falsch sein, und zeigen, dass sich daraus ein Widerspruchergibt.

Grundsätzliches

1. In die erste(n) Zeile(n) – die sog. Wurzel – schreiben wir Formeln, die durch die Auf-gabenstellung vorgegeben sind. Welche das sind, hängt von der jeweiligen Aufgaben-stellung ab.

2. Die Zeilen werden durchnummeriert. Das sind die Zahlen, mit denen die Zeilen begin-nen.

3. Am Ende jeder Zeile (mit Ausnahme der Wurzel) wird notiert, aus welcher vorherigenZeile die Zeile abgeleitet wird.

4. Eine Zeile, die abgearbeitet wurde, wird abgehakt (mit „✓“).

47


1. . . .✓2. . . .✓

3. . . . (2)✓4. . . . (2)✓

5. . . . (1) 6. . . . (1)✓7. . . . (6)✓

8. . . . (7) 9. . . . (7)

• Die ersten beiden Zeilen bilden die Wurzel.

• Der Baum besteht aus drei Ästen: Der erste Ast sind die Zeilen 1, 2, 3, 4, 5. Der zweiteAst sind die Zeilen 1, 2, 3, 4, 6, 7, 8. der dritte Ast sind die Zeilen 1, 2, 3, 4, 6, 7, 9.

Geschlossene und offene Äste

• Ein Ast ist geschlossen genau dann, wenn er einen Widerspruch enthält, das heißtsowohl eine Formel Φ als auch die Formel ¬Φ. Geschlossene Äste werden mit „×“markiert. (= sog. Schließungsregel)

• Ein Ast ist offen genau dann, wenn alle Zeilen abgearbeitet wurden und der Ast keinenWiderspruch enthält.

Geschlossene und offene Bäume

• Ein Baum ist geschlossen genau dann, wenn alle seine Äste geschlossen sind.

• Ein Baum ist offen genau dann, wenn mindestens einer seiner Äste offen ist.

Entwicklungsregeln

• Wie entstehen in einem Baum neue Zeilen (auch „Knoten“ genannt)? Das legen dieEntwicklungsregeln fest.

• Diese Regeln stehen auf dem Regelblatt (das auch in der Klausur verwendet werdendarf).

• Auf den folgenden Seiten führen wir die Regeln nach und nach anhand von Beispielenein.

48


Grundsätzliches zu den Entwicklungsregeln

• Es gibt für jeden zweistelligen Junktor zwei Regeln und für jeden einstelligen Junktor(= Negation) eine Regel.

• Der Pfeil ist als Erlaubnis zu verstehen: Wenn man in einer Zeile das stehen hat, wasüber dem Pfeil steht, darf man die Zeile(n) unter dem Pfeil zu dem Baum hinzufügen.

• Die Regeln sorgen dafür, dass die Formeln kürzer werden. Deshalb kommt man irgend-wann an einen Punkt, an dem keine Regeln mehr angewendet werden können.

5.2. Beispiele

Achtung Die Beispiele werden an der Tafel vorgeführt, hier finden sich nur die Ergebnisse!

5.2.1. Formeln

5.2.1.1. Beispiel 1

Aufgabe: Wir wollen zeigen, dass die folgende Formel eine Tautologie ist.

¬((P ∧Q) ∧ ¬P )

Vorgehen: Wir nehmen an, die Formel könnte falsch sein und führen dies zu einem Wider-spruch, das heißt: Die Wurzel besteht aus der negierten (!) Formel.

1. ¬¬((P ∧Q) ∧ ¬P )✓2. ((P ∧Q) ∧ ¬P ) (1)✓

3. (P ∧Q) (2)✓4. ¬P (2)5. P (3)6. Q (3)

×

Verwendete Regeln: Regeln für die Negation und für die KonjunktionErgebnis: Der Baum ist geschlossen. Also ist die Formel ¬((P ∧Q) ∧ ¬P ) tautologisch.

5.2.1.2. Beispiel 2


P ∨ (¬P ∨Q)

49


Vorgehen: Wir nehmen an, die Formel könnte falsch sein und führen dies zu einem Wider-spruch, das heißt: Die Wurzel besteht aus der negierten (!) Formel.

1. ¬(P ∨ (¬P ∨Q))✓2. ¬P (1)

3. ¬(¬P ∨Q) (1)✓4. ¬¬P (3)✓

5. ¬Q (3)6. P (4)

×

Verwendete Regeln: Zweimal Regel für die negierte Disjunktion, einmal Regel für dieNegationErgebnis: Der Baum ist geschlossen. Also ist die (nicht negierte!) Formel P ∨ (¬P ∨ Q)tautologisch.

5.2.1.3. Beispiel 3

Aufgabe: Wir wollen zeigen, dass die folgende Formel eine Kontradiktion ist.

¬(P → P ) ∨ (¬Q ∧Q)

Vorgehen: Wir nehmen an, die Formel könnte wahr sein und führen dies zu einem Wider-spruch, das heißt: Die Wurzel besteht aus der (nicht-negierten!) Formel.

1. ¬(P → P ) ∨ (¬Q ∧Q)✓

2. ¬(P → P ) (1)✓4. P (2)

5. ¬P (2)×

3. (¬Q ∧Q) (1)✓6. ¬Q (3)7. Q (3)

×

Verwendete Regeln: Regeln für die Disjunktion, für das negierte Konditional und für dieKonjunktionErgebnis: Der Baum ist geschlossen. Also ist die Formel ¬(P → P ) ∨ (¬Q ∧Q) kontradik-torisch.

5.2.1.4. Beispiel 4


¬(P ∧Q)→ (¬P ∨ ¬Q)

Vorgehen: Wir nehmen an, die Formel könnte falsch sein und führen dies zu einem Wider-spruch, das heißt: Die Wurzel besteht aus der negierten Formel.

50


1. ¬(¬(P ∧Q)→ (¬P ∨ ¬Q))✓2. ¬(P ∧Q) (1)✓

3. ¬(¬P ∨ ¬Q) (1)✓4. ¬¬P (3)✓5. ¬¬Q (3)✓

6. P (4)7. Q (5)

8.¬P (2)×

9. ¬Q (2)×

Verwendete Regeln: Regel für das negierte Konditional, für die negierte Disjunktion,zweimal für die Negation und für die negierte KonjunktionErgebnis: Der Baum ist geschlossen. Also ist die (nicht negierte!) Formel ¬(P ∧ Q) →(¬P ∨ ¬Q) tautologisch.

5.2.1.5. Beispiel 5

Aufgabe: Wir wollen zeigen, dass die folgende Formel kontingent ist.

¬(P ∧Q)→ (P ↔ Q)

Vorgehen: Wir müssen zwei Bäume entwickeln. Wir müssen einmal zeigen, dass die Formelkeine Tautologie ist, und einmal zeigen, dass sie keine Kontradiktion ist, das heißt: ein Baumhat als Wurzel die negierte Formel und ein Baum als Wurzel die nicht-negierte Formel.

Erster Baum: Negierte Formel (Test auf Tautologie)1. ¬(¬(P ∧Q)→ (P ↔ Q))✓

2. ¬(P ∧Q) (1)✓3. ¬(P ↔ Q) (1)✓

4. ¬P (2)

6. P (3)7.¬Q (3)

×

8. ¬P (3)9. Q (3)

5. ¬Q (2)

10. P (3)11. ¬Q (3)

12. ¬P (3)13. Q (3)

×

Zweiter Baum: Nicht-negierte Formel (Test auf Kontradiktion)1. ¬(P ∧Q)→ (P ↔ Q)✓

2. ¬¬(P ∧Q) (1)✓4. P ∧Q (2)✓

5. P (4)6. Q (4)

3. P ↔ Q (1)✓

7. P (3)8. Q (3)

9. ¬P (3)10. ¬P (3)

51


Ergebnis: Beide Bäume sind offen. Also ist die ursprünglich Formel ¬(P ∧Q) → (P ↔ Q)weder tautologisch, noch kontradiktorisch. Also ist sie kontingent.

5.2.1.6. Beispiel 5: Anmerkung

Warum zeigt, der erste Baum alleine nicht, dass die Formel kontingent ist? Hier ist einBeispiel für eine Formel, die bei Test auf Tautologie offene und geschlossene Äste erzeugt,aber dennoch eine Kontradiktion (und keine kontingente Formel) ist)

¬((P ∧ ¬P ) ∨ ¬(P ∧ ¬P ))

5.2.2. Argumente

5.2.2.1. Beispiel 6

Aufgabe: Wir wollen zeigen, dass das folgende Argument folgerichtig ist

P → Q

Q→ R

∴ P → R

bzw. wir wollen zeigen, dass die folgende Behauptung stimmt:

P → Q,Q→ R ⊧ P → R

Vorgehen: Wir nehmen an, die Prämissen wären wahr und die Konklusion falsch und füh-ren dies zu einem Widerspruch, das heißt: Die Wurzel besteht aus den Prämissen und dernegierten Konklusion.

1. P → Q✓2. Q→ R✓

3. ¬(P → R)✓4. P (3)

5. ¬R (3)

6. ¬P (1)×

7. Q (1)

8. ¬Q (2)×

9. R (2)×

Verwendete Regeln: Regeln für das Konditional und für das negierte KonditionalErgebnis: Der Baum ist geschlossen. Also ist das Argument mit den Prämissen P → Q undQ→ R sowie der Konklusion P → R folgerichtig.

52


5.2.2.2. Beispiel 7

Aufgabe: Wir wollen zeigen, dass das folgende Argument folgerichtig ist

P ∧Q∴ P ↔ Q

bzw. wir wollen zeigen, dass die folgende Behauptung stimmt:

P ∧Q ⊧ P ↔ Q

Vorgehen: Wir nehmen an, die Prämissen wären wahr und die Konklusion falsch und füh-ren dies zu einem Widerspruch, das heißt: Die Wurzel besteht aus den Prämissen und dernegierten Konklusion.

1. P ∧Q✓2. ¬(P ↔ Q)✓

3. P (1)4. Q (1)

5. P (2)6. ¬Q (2)

×

7. ¬P (2)8. Q (2)

×

Verwendete Regeln: Regel für die Konjunktion und für das negierte KonditionalErgebnis: Der Baum ist geschlossen. Also ist das Argument mit der Prämisse P ∧Q undder Konklusion P ↔ Q folgerichtig.

5.3. Überblick über alle Regeln

5.3.0.1. Überblick

Arten von Regeln

1. Schreibregeln: Wie schreibt man Bäume auf?

2. Anfangsregeln: Was gehört in die Wurzel?

3. Entwicklungsregeln: Was darf man aus bestehenden Zeilen ableiten?

4. Eine Wachstumsregel: Wohin werden die neuen Zeilen geschrieben?

5. Eine Schließungsregel: Wann ist ein Ast bzw. Baum geschlossen?

6. Eine Klugheitsregel: In welcher Reihenfolge sollten die Zeilen geschickterweise abgear-beitet werden?

53


5.3.0.2. Schreibregeln

Nicht vergessen

• Zeilen durchnummerieren!

• Zeile angeben, aus der eine neue Zeile stammt!

• Abgearbeitete Zeilen abhaken!

5.3.0.3. Anfangsregeln I

Tautologisch, kontradiktorisch oder kontingent?

• Eine Formel ist tautologisch genau dann, wenn gilt: Der Baum mit der Negationdieser Formel als Wurzel ist geschlossen.

• Eine Formel ist kontradiktorisch genau dann, wenn gilt: Der Baum mit dieser Formelals Wurzel ist geschlossen.

• Eine Formel ist kontingent genau dann, wenn gilt: Der Baum mit dieser Formel alsWurzel ist offen und der Baum mit der Negation dieser Formel als Wurzel ist offen.

5.3.0.4. Anfangsregeln II

Folgerichtig oder nicht folgerichtig?

• Ein Argument ist folgerichtig genau dann, wenn gilt: Der Baum mit den Prämissenund der negierten Konklusion als Wurzel ist geschlossen.

• Ein Argument ist nicht folgerichtig genau dann, wenn gilt: Der Baum mit den Prä-missen und der negierten Konklusion als Wurzel ist offen.

5.3.0.5. Anfangsregeln III

Äquivalent oder nicht äquivalent?

• Zwei Formeln sind äquivalent genau dann, wenn

(a) der Baum mit der ersten Formel und der negierten zweiten Formel als Wurzelgeschlossen ist und

(b) der Baum mit der zweiten Formel und der negierten ersten Formel als Wurzelgeschlossen ist.

(Man muss also zwei Bäume entwickeln!)

• Zwei Formeln Φ und Ψ sind äquivalent genau dann, wenn der Baum mit ¬(Φ↔ Ψ)als Wurzel geschlossen ist.

(Man muss nur einen Baum entwickeln!)

5.3.0.6. Entwicklungsregeln

54


Negation ¬¬Φ↓Φ

Konjunktion (Φ ∧Ψ)↓ΦΨ

Negierte Konjunktion ¬(Φ ∧Ψ)↓

¬Φ ¬Ψ

Disjunktion (Φ ∨Ψ)↓

Φ Ψ

Negierte Disjunktion ¬(Φ ∨Ψ)↓¬Φ¬Ψ

Konditional (Φ→ Ψ)↓

¬Φ Ψ

Negiertes Konditional ¬(Φ→ Ψ)↓Φ¬Ψ

Bikonditional (Φ↔ Ψ)↓

ΦΨ

¬Φ¬Ψ

Negiertes Bikonditional ¬(Φ↔ Ψ)↓

Φ¬Ψ

¬ΦΨ

5.3.0.7. Wachstumsregel

Die Wachstumsregel Wenn eine der Entwicklungsregeln auf eine Formel angewendet wird,dann müssen die neuen Zeilen an alle bestehenden offenen Äste angefügt werden, die dieseFormel enthalten.

5.3.0.8. Schließungsregel

Schließungsregel

• Ein Ast ist geschlossen genau dann, wenn er einen Widerspruch enthält, das heißtsowohl eine Formel Φ als auch die Formel ¬Φ. Geschlossene Äste werden mit „×“markiert. Ansonsten ist der Ast offen.

• Ein Baum ist geschlossen genau dann, wenn alle seine Äste geschlossen sind. Ansons-ten ist der Baum offen.

55


5.3.0.9. Klugheitsregel

Klugheitsregel Wenn man zwischen mehreren Regelanwendungen auswählen kann, sollteman eine Regel anwenden, die nicht zu einer Verzweigung führt.

• Verzweigend: Disjunktion, negierte Konjunktion, Konditional, Bikonditional, negier-tes Bikonditional

• Nicht-Verzweigend: Negation, Konjunktion, negierte Disjunktion, negiertes Kondi-tional

56

6. Aussagenlogik: Ergänzungen

6.1. Baumkalkül: Interpretationen ablesen

6.1.1. Baumkalkül und Interpretationen

Weitere Anwendung des Baumkalküls Von offenen Ästen können Interpretationen abge-lesen werden.Das ist nützlich, wenn man ein Gegenbeispiel angeben will:

• Ein Gegenbeispiel zur Annahme, dass eine Formel tautologisch ist, ist eine Interpreta-tion, relativ zu der die Formel falsch ist.

• Ein Gegenbeispiel zur Annahme, dass ein Argument folgerichtig ist, ist eine Interpre-tation, relativ zu der die Prämissen wahr sind, aber die Konklusion falsch.

Hinweis Die gängigen anderen Kalküle (Axiomatischer Kalkül, Natürliches Schließen, Se-quenzenkalkül) erlauben das Ablesen von Gegenbeispielen nicht.

Vorgehen

1. Entwickle den Baum für die Negation der angeblich tautologischen Formel vollständigbzw. entwickle den Baum für die Prämissen und die negierte Konklusion des angeblichfolgerichtigen Arguments vollständig.

2. Wähle einen offenen Ast des Baumes aus. (Wenn es mehrere offene Äste gibt, ist esegal, welcher Ast ausgewählt wird.)

3. Kennzeichne die Zeilen dieses Astes, die einen Satzbuchstaben oder die Negation einesSatzbuchstaben enthalten.

4. Enthält die jeweilige Zeile einen Satzbuchstaben, dann ordne ihm den WahrheitswertWahr zu. Enthält die jeweilige Zeile die Negation eines Satzbuchstabens, dann ordneihm den Wahrheitswert Falsch zu.

57


6.1.2. Beispiele

6.1.2.1. Beispiel 1

1. ¬(Q ∨ (P ∧ (P ∨Q)))✓2. ¬Q (1)

3. ¬(P ∧ (P ∨Q)) (1)✓

4. ¬P (3) 5. ¬(P ∨Q) (3)✓6. ¬P (5)7. ¬Q (5)

Ergebnis Die Formel ist nicht tautologisch.Gegenbeispiel aus dem linken Ast (Zeile 2 und 4) oder aus dem rechten Ast (Zeile 2, 6, 7)ablesen: I(P ) = F und I(Q) = F

6.1.2.2. Beispiel 2

Aufgabe Gib eine Interpretation an, relativ zu der die Prämisse des folgenden Argumentswahr und seine Konklusion falsch!

(P ∧Q)

∴ ¬(¬P → ¬Q)

1. (P ∧Q)✓2. ¬¬(¬P → ¬Q)✓3. ¬P → ¬Q (2)✓

4. P (1)5. Q (1)

6. ¬¬P (3)✓8. P (6)

7. ¬Q(3)×

Ergebnis Das Argument ist nicht folgerichtig.Gegenbeispiel ablesen aus dem linken Ast (Zeilen 4, 5, 8): I(P ) =W und I(Q) =W

6.2. Konditional und Implikation

Zusammenhang zwischen Folgerichtigkeit und Tautologie Die folgenden Behauptungensind äquivalent:

1. P1, P2, . . . , Pn ⊧K (Folgerichtigkeit)

2. ⊧ ((P1 ∧ P2) ∧ ⋅ ⋅ ⋅ ∧ Pn)→K (Tautologie)

Merkspruch Implikation ist die logische Wahrheit des Konditionals.

58


Erläuterung

1. Konditional: Es ist de facto nicht der Fall, dass der Vordersatz wahr und der Nachsatzfalsch ist.

2. Implikation: Es ist unmöglich, dass der Vordersatz wahr und der Nachsatz falsch ist.

Frage Warum bestehen Logiker eigentlich darauf, dass es in der Logik um Folgerichtigkeitund nicht um logische Wahrheiten oder Tautologien geht?

Beobachtung Eine Folgerichtigkeitsbehauptung kann man nur dann in eine Tautologiebe-hauptung übersetzen, wenn in der Objektsprache das Konditional „→“ vorkommt.

Konsequenz Der Begriff der Folgerichtigkeit ist ein universell anwendbarer Begriff (undwird deshalb von den Logikern bevorzugt).

6.3. *Korrektheit und Vollständigkeit

6.3.0.1. Korrektheit und Vollständigkeit I

Dieser Kurs heißt nicht ohne Grund „Einführung in die Logik“. Es folgt ein kurzer Ausblickauf die formale Logik jenseits der Einführung. Dazu zunächst etwas Symbolkunde:

Semantische Folgerung und Ableitbarkeit

• ⊧ wird mittels des Begriffs der Interpretation definiert (semantische Folgerung).

• ⊢ wird mittels des Begriffs der Beweisbarkeit oder Ableitbarkeit in einem Kalkül de-finiert. (Beispielsweise: Γ ⊢ Φ genau dann, wenn alle Äste des Baum mit der Wurzel{Γ,¬Φ} geschlossen sind.)

Φ,Ψ, . . . stehen für eine beliebige FormelΓ,∆, . . . stehen für eine beliebige Menge von Formeln

6.3.0.2. Korrektheit und Vollständigkeit II: Das Symbol ⊧Γ ⊧ Φ Aus Γ folgt Φ

oder mit anderen Worten: Γ impliziert Φoder mit anderen Worten: Das Arg. bestehend aus Γ und der Konkl. Φ ist folgerichtig

Γ ⊭ Φ Aus Γ folgt Φ nicht.⊧ Φ Φ ist tautologisch⊧ ¬Φ Φ ist kontradiktorisch⊭ Φ Φ ist nicht tautologisch⊭ ¬Φ Φ ist nicht kontradiktorischΦ â⊧ Ψ Φ und Ψ sind äquivalent

59


6.3.0.3. Korrektheit und Vollständigkeit III: Das Symbol ⊢Γ ⊢ Φ Aus Γ ist Φ ableitbarΓ ⊬ Φ Aus Γ ist Φ nicht ableitbar⊢ Φ Φ ist ableitbar⊢ ¬Φ Die Negation von Φ ist ableitbar⊬ Φ Φ ist nicht ableitbar⊬ ¬Φ Die Negation von Φ ist nicht ableitbarΦ ⊣⊢ Ψ Φ ist aus Ψ ableitbar und umgekehrt

6.3.0.4. Korrektheit und Vollständigkeit IV: Definitionen

Definition 24 (Korrektheit). Ein Kalkül ist korrekt genau dann, wenn gilt: Wenn eineFormel aus einer Menge von Formeln ableitbar ist, dann folgt diese Formel auch logisch ausder Menge von Formeln. Wenn Γ ⊢ Φ, dann auch Γ ⊧ Φ.

Definition 25 (Vollständigkeit). Ein Kalkül ist vollständig genau dann, wenn gilt:Wenn eine Formel aus einer Menge von Formeln logisch folgt, dann ist diese Formel auchaus der Menge von Formeln ableitbar. Wenn Γ ⊧ Φ, dann auch Γ ⊢ Φ.

6.3.0.5. Korrektheit und Vollständigkeit V: AL

Vollständigkeit und Korrektheit der Aussagenlogik Der von uns verwendete Baumkalkülist sowohl korrekt als auch vollständig. Für beide Umstände gibt es Beweise! Siehe dazumehr in Kap. 14.

6.4. *Philosophisches Argumentieren

Wie Logik beim Analysieren von Argumenten helfen kann

1. Argument im Text identifizieren

2. Rekonstruktion und übersichtliche Darstellung

• Prämissen identifizieren

• Konklusion identifizieren

• evtl. stillschweigend vorausgesetzte Prämissen ergänzen

• Ausdrucksweise vereinfachen

• usw.

3. Formalisierung

4. Überprüfung der Folgerichtigkeit

5. Auswertung

60


6.4.1. Primärtext von Epikur

Quelle Wir betrachten ein Argument von Epikur (341 bis 271/270 v. u. Z.). Quelle: Briefan Menoikeus, überliefert in Diogenes Laertios: Leben und Lehre der Philosophen Buch X,Nr. 124–126. In diesem Argument will Epikur zeigen, dass der Tod weder etwas Schlechtesnoch etwas Gutes ist und dementsprechend weder Todesangst noch Todessehnsucht ange-messen sind.

Epikur über den Tod „Ferner gewöhne Dich an den Gedanken, dass der Tod uns nichtsangeht. Beruht doch alles Gute und alles Üble nur auf Empfindung, der Tod aber ist Auf-hebung der Empfindung. Darum macht die Erkenntnis, dass der Tod uns nichts angeht,uns das vergängliche Leben erst köstlich. Dieses Wissen hebt natürlich die zeitliche Grenzeunseres Daseins nicht auf, aber es nimmt uns das Verlangen, unsterblich zu sein, denn wereingesehen hat, dass am Nichtleben gar nichts Schreckliches ist, den kann auch am Lebennichts schrecken. Sagt aber einer, er fürchte den Tod ja nicht deshalb, weil er Leid bringt,wenn er da ist, sondern weil sein Bevorstehen schon schmerzlich sei, ist er ein Tor; denn es istdoch Unsinn, dass etwas, dessen Vorhandensein uns nicht beunruhigen kann, uns dennochLeid bereiten soll, weil und solange es nur erwartet wird!So geht uns also der Tod, das vermeintlich schrecklichste der Übel, nichts an: Solange wir

da sind, ist er nicht da, und wenn er da ist, sind wir nicht mehr. Folglich betrifft er weder dieLebenden noch die Gestorbenen, denn wo jene sind, ist er nicht, und diese sind ja überhauptnicht mehr da.Freilich, die große Masse meidet entweder den Tod als das größte der Übel oder sehnt ihn

herbei als ein Ausruhen von den Mühsalen des Lebens. Der Weise dagegen lehnt weder dasLeben ab, noch fürchtet er sich vor dem Nichtmehrleben, denn ihn widert das Leben nichtan, und er betrachtet das Nichtmehrleben nicht als ein Übel. Und wie er beim Essen nichtunbedingt möglichst viel haben will, sondern mehr Wert auf die gute Zubereitung legt, so ister auch beim Leben nicht auf dessen Dauer bedacht, sondern auf die Köstlichkeit der Ernte,die es ihm einträgt.“

6.4.2. Argumentanalyse

6.4.2.1. Argumentanalyse I

(1) Wenn ich nicht mehr lebe, habe ich keine Empfindungen.

(2) Wenn ich keine Empfindungen habe, ist nichts ein Übel für mich.

(3) Wenn nichts ein Übel für mich ist, dann ist auch der Tod kein Übel für mich.

(4) Also: Wenn ich nicht mehr lebe, ist der Tod kein Übel für mich. (aus 1 bis 3)

(5) Wenn ich noch lebe, ist der Tod nur dann ein Übel für mich, wenn die Aussicht aufden Tod ein Übel für mich ist.

(6) Die Aussicht auf den Tod ist nur dann ein Übel für mich, wenn gilt: Wenn ich tot wäre,wäre der Tod ein Übel für mich.

(7) Also: Wenn ich noch lebe, ist der Tod kein Übel für mich. (aus 4 bis 6)

61


(8) Also: Der Tod ist kein Übel für mich. (aus 4 und 7)

6.4.2.2. Argumentanalyse II

• Ein paralleles Argument lässt sich mit „Gut“ an der Stelle von „Übel“ führen, indemjedes Vorkommnis des Wortes „Übel“ durch das Wort „Gut“ ersetze wird.

• Epikur kann dann so für seine These, dass der Tod uns nichts angeht, argumentieren:

(1*) Der Tod ist kein Übel für mich. (siehe das Argument oben)

(2*) Der Tod ist kein Gut für mich. (siehe das Parallel-Argument)

(3*) Wenn der Tod weder ein Übel noch ein Gut für mich ist, dann geht der Tod michnichts an.

(4*) Also: Der Tod geht mich nichts an. (aus 1 bis 3)

6.4.2.3. Argumentanalyse III: Exkurs

Rolle von Zwischenkonklusionen Der Übersicht halber kommen in der Rekonstruktionviele Zwischenkonklusionen vor. Diese sind jedoch redundant und dürfen daher bei der For-malisierung weggelassen werden. Das rechte Argument unterscheidet sich nur in der Darstel-lungsweise, nicht in der Substanz von dem linken Argument!

A AB B

∴ CD D

∴ EF F

∴ G ∴ G

6.4.2.4. Argumentanalyse IV

Da wir es mit einem langen Argument zu tun haben, werden wir es nicht vollständig forma-lisieren. Wir konzentrieren uns auf den folgenden Kern des Arguments:

(4) Wenn ich nicht mehr lebe, ist der Tod kein Übel für mich.

(5) Wenn ich noch lebe, ist der Tod nur dann ein Übel für mich, wenn die Aussicht aufden Tod ein Übel für mich ist.

(6) Die Aussicht auf den Tod ist nur dann ein Übel für mich, wenn gilt: Wenn ich tot wäre,wäre das Totsein ein Übel für mich.

(8) Also: Der Tod ist kein Übel für mich. (aus 4 bis 6)

62


6.4.2.5. Argumentanalyse V: Formalisierung

(4) Wenn ich nicht mehr lebe, ist der Tod kein Übel für mich. ¬P → ¬Q

(5) Wenn ich noch lebe, ist der Tod nur dann ein Übel für mich, wenn die Aussicht aufden Tod ein Übel für mich ist. P → (Q→ R)

(6) Die Aussicht auf den Tod ist nur dann ein Übel für mich, wenn gilt: Wenn ich tot wäre,wäre das Totsein ein Übel für mich. R → ¬(¬P → ¬Q)

(8) Also: Der Tod ist kein Übel für mich. ¬Q

6.4.2.6. Argumentanalyse VI: Folgerichtig?

1. ¬P → ¬Q✓2. P → (Q→ R)✓

3. R → ¬(¬P → ¬Q)✓4. ¬¬Q✓5. Q (4)

6. ¬R (3)

8. ¬P (2)

10. ¬¬P (1)×

11. ¬Q (1)×

9. Q→ R (2)✓

12. ¬Q (9)×

13. R (9)×

7. ¬(¬P → ¬Q) (3)×

6.4.2.7. Argumentanalyse VII: Auswertung

• Das Argument ist folgerichtig, das heißt: Jeder muss entweder die Konklusion akzep-tieren oder mind. eine der Prämissen ablehnen.

• Welche der Optionen besser ist, ist freilich keine Sache der Logik mehr. Aber dassman sich überhaupt entscheiden muss, ist eine logische Erkenntnis.

• Nur fürs Protokoll: Besonders diskussionswürdig sind die Prämissen (6) und (2).

63

Teil II.

Prädikatenlogik

64

7. Prädikatenlogik: Grundlagen

7.1. Einleitung

Beispiel für ein intuitiv folgerichtiges Argument

(1) Alle Menschen sind sterblich.

(2) Sokrates ist ein Mensch.

(3) Also ist Sokrates sterblich.

Aussagenlogische Form

(1) P

(2) Q

(3) R

Auswertung Mit aussagenlogischen Mitteln können wir nicht zeigen, dass dieses Argumentfolgerichtig ist.

Allgemein gilt

• Wenn ein Argument aussagenlogisch analysiert folgerichtig ist, dann ist es auch prädi-katenlogisch analysiert folgerichtig.

• Wenn ein Argument aussagenlogisch analysiert nicht folgerichtig ist, dann ist es mög-lich, dass es prädikatenlogisch analysiert folgerichtig ist.

Aussagen- vs. Prädikatenlogik

• In der Aussagenlogik werden wahrheitsfunktionale Verknüpfungen ganzer Sätze un-tersucht.

• In der Prädikatenlogik wird auch der innere Aufbau der Sätze untersucht.

65


7.2. Prädikation

7.2.1. Übersicht ZeichenBezeichnung Prädikatenlogisches ZeichenIndividuenkonstanten a, b, c, d, e, a1, b1, . . .Prädikate F,G,H,J,K,F1,G1, . . .Junktoren ¬,∧,∨,→,↔(Individuen-)Variablen x, y, z, x1, y1, . . .Quantoren ∀,∃Klammern (, )

7.2.2. Individuenkonstanten und Prädikate

7.2.2.1. Prädikative Grundstruktur

Individuenkonstanten und Prädikate

• Einfache natürlichsprachliche Sätze enthalten Ausdrücke, die auf einen GegenstandBezug nehmen, und solche, die etwas über diesen Gegenstand aussagen.

• Ausdrücke, die für einen einzigen Gegenstand stehen, werden in der PL durch Indivi-duenkonstanten repräsentiert.

• Ausdrücke, die etwas über einen Gegenstand aussagen, werden in der PL durch Prä-dikate repräsentiert.

7.2.2.2. Individuenkonstanten

Beispiele für Ausdrücke, die mit Individuenkonstanten wiedergegeben werden

• Wilfried

• Regensburg

• die Mensa

• die Tafel

• die Montagsübungsgruppe

• der gegenwärtige Bundespräsident

• ich

• heute

7.2.2.3. Prädikate I

Was ist ein Prädikat? Das Prädikat ist das, was übrig bleibt, wenn man in einem einfa-chen Satz (keine Satzoperatoren, keine Ausdrücke wie „alle“, „es gibt“ usw.) alle Ausdrücke,die für einen einzelnen Gegenstand stehen, weglässt.

66


Beispiele

• In „Tammo lächelt“ ist das Prädikat „. . . lächelt“.

• In „Johanna geht mit Sinje und Gordon in die Mensa“ ist das Prädikat „. . . geht mit. . . und . . . in . . . “

7.2.2.4. Prädikate II

• Ein Prädikat, dass genau einen freien Platz (markiert durch die Pünktchen) enthält,ist einstellig. Für sie benutzen wir als Zeichen F,G, . . . .

• Ein Prädikat, dass genau zwei freie Plätze (markiert durch die Pünktchen) enthält, istzweistellig. Für sie benutzen wir als Zeichen F ′,G′, . . . . (Der Strich zeigt an, dass dasPrädikat zweistellig ist.)

• Ein Prädikat, dass genau drei freie Plätze (markiert durch die Pünktchen) enthält, istdreistellig. Für sie benutzen wir als Zeichen F ′′,G′′, . . . . (Die zwei Striche zeigen an,dass das Prädikat dreistellig ist.)

• . . .

• Ein Prädikat, dass genau n freie Plätze (markiert durch die Pünktchen) enthält, istn-stellig. Die Stelligkeit wird mit n − 1 Strichen markiert.

7.2.2.5. Beispiele I

Einige Beispiele

• Tammo lächelt. Formalisierung: Fa

• Regensburg liegt nördlich von München. Formalisierung: F ′ab

• Johanna geht mit Sinje und Gordon in die Mensa. Formalisierung: F ′′′abcd

• Mir ist das Glas heruntergefallen. Formalisierung: F ′ab

7.2.2.6. Beispiele II

Beispiele mit Junktoren

• Johanna lächtelt und Wilfried auch. Formalisierung: Fa ∧ Fb

• Tim ist ein blonder Philosoph. Paraphrase: Tim ist blond und Philosoph. Formalisie-rung: Fa ∧Ga

• Sinje und Gordon, der für den Berlinmarathon trainiert, sind in der Mensa. Paraphrase:Sinje ist in der Mensa und Gordon ist in der Mensa und Gordon trainiert für denBerlinmarathon. Formalisierung: Fa ∧ (Fb ∧G′bc)

67


7.2.3. Quantoren

Der Allquantor ∀ (umgekehrtes „A“ für „alle“) steht kurz für „Für alle . . . gilt: . . . “.

Der Existenzquantor ∃ (umgekehrtes „E“ für „existiert“) steht kurz für „Es gibt ein . . . ,für das gilt: . . . “.

Bedeutung der Quantoren

• ∀xFx = Für alle x gilt: x ist F.

• ∃xFx = Es gibt (mindestens) ein x, für das gilt: x ist F.

• ∀x(Fx ∨Gx) = Für alle x gilt: x ist F oder x ist G.

• ∃x(Fx ∧Gx) = Es gibt (mindestens) ein x, für das gilt: x ist F und x ist G.

Beispiele Allquantor

• Alles wird gut. Formalisierung: ∀xFx

• Alle Menschen sind sterblich. Formalisierung: ∀x(Fx→ Gx)

Beispiele Existenzquantor

• Es gibt Menschen. Formalisierung: ∃xFx

• Es gibt sterbliche Menschen. Formalisierung: ∃x(Fx ∧Gx)

Vorgehen Bevor wir uns den Details der Formalisierung natürlichsprachlicher Sätze mittelsQuantoren zuwenden, schieben wir die Syntax ein.

7.3. Syntax

7.3.1. Definition prädikatenlogische Formel

7.3.1.1. Zwei Hilfsdefinitionen

Individuensymbol Ein Zeichen ist ein Individuensymbol genau dann, wenn es eine Indi-viduenkonstante oder eine Individuenvariable ist.

Atomare Formel Eine Zeichenkette ist eine atomare Formel genau dann, wenn sie auseinem n-stelligen Prädikat gefolgt von genau n Individuensymbolen besteht.

68


7.3.1.2. Definition Prädikatenlogische Formeln

Prädikatenlogische Formel Eine Zeichenkette x ist eine prädikatenlogische Formel ge-nau dann, wenn

1. x eine atomare Formel ist oder

2. x ergibt sich durch Anwendung der folgenden Regeln:

2.1. Wenn Φ eine prädikatenlogische Formel ist, dann ist auch ¬Φ eine prädikatenlo-gische Formel.

2.2. Wenn Φ und Ψ prädikatenlogische Formeln sind, dann sind auch (Φ∧Ψ), (Φ∨Ψ),(Φ→ Ψ) und (Φ↔ Ψ) prädikatenlogische Formeln.

2.3. Wenn Φ eine prädikatenlogische Formel und α eine Individuenvariable ist, dannsind auch ∀αΦ und ∃αΦ prädikatenlogische Formeln.

7.3.1.3. Beispiele

Prädikatenlogische Formeln sind beispielsweise

• Fa

• F ′xa

• F ′ab

• ∃xFx (keine Klammern!)

• ∀x∀y∀z(F ′xy ∨ F ′xz)↔ F ′aa

• ∀xFa (Variable muss im Rest der Formel nicht vorkommen!)

• ∀x∃xFx (derselbe Variablentyp kann an zwei Quantoren hängen!)

7.3.1.4. Beispiele

Keine prädikatenlogische Formeln sind beispielsweise

• ∀x∃y (es fehlt eine atomare Formel als Ausgangspunkt)

• ∃x(F ′xa) (zu viele Klammern)

• (∃x)F ′xa (zu viele Klammern)

• ∃x↔ ∀xFx (∃x wurde auf keine Formel „angewendet“)

69


7.3.2. Weitere Definitionen

7.3.2.1. Offene und geschlossene Formeln I

Definition 26 (Quantorenphrase). EineQuantorenphrase ist ein Quantor gefolgt voneiner Individuenvariable.

Definition 27 (Skopus). Der Skopus einer Quantorenphrase ist diejenige Teilformel Φ,auf die beim rekursiven Aufbau der Gesamtformel die Klausel 2.3 angewendet wird, wenndie Quantorenphrase eingeführt wird.

7.3.2.2. Offene und geschlossene Formeln II

Beispiele Skopus

• Fa ∧ ∃xFx – Der Skopus von ∃x ist Fx.

• ∀x(Fx→ Gx) – Der Skopus von ∀x ist (Fx→ Gx).

• ∀xFx→ Gx – Der Skopus von ∀x ist Fx.

• ∀x∀x∃xFx – Der Skopus von ∃x ist Fx, der Skopus des zweiten Vorkommnis von ∀xist ∃xFx, der Skopus des ersten Vorkommnis von ∀x ist ∀x∃xFx.

7.3.2.3. Offene und geschlossene Formeln III

Definition 28 (Freie Variable). Ein Vorkommnis der Individuenvariable α ist frei (oder:ungebunden) in der Formel Φ genau dann, wenn es nicht Bestandteil einer Quantorenphraseist und sich nicht im Skopus (mind.) einer Quantorenphrase ∀α oder ∃α befindet.

Definition 29 (Gebundene Variable). Ein Vorkommnis der Individuenvariable α istgebunden in der Formel Φ genau dann, wenn es Bestandteil einer Quantorenphrase istoder sich im Skopus (mind.) einer Quantorenphrase ∀α oder ∃α befindet.

Definition 30 (Bindung durch eine Quantorenphrase). Eine Quantorenphrase ∀αoder ∃α bindet ein Vorkommnis von α in der Formel Φ genau dann, wenn dieses Vorkommnisim Skopus der Quantorenphrase frei ist.

7.3.2.4. Offene und geschlossene Formeln IV

Beispiele Binden

• Fa ∧ ∃xFx – Die Quantorenphrase bindet das x in Fx.

• ∀x(Fx→ Gx) – Die Quantorphrase bindet beide Vorkommnisse von x in (Fx→ Gx)

• ∀xFx→ Gx – Die Quantorenphrase bindet nur das x in Fx; das x in Gx ist frei.

• ∀x(Fx→ ∃xGx) – Die ∀x bindet das x in Fx, ∃x das x in Gx.

70


7.3.2.5. Offene und geschlossene Formeln V

Definition 31 (Offene Formel). Eine Formel ist offen genau dann, wenn mindestensein Vorkommnis einer Individuenvariable frei ist.

Definition 32 (Geschlossene Formel/Satz). Eine Formel ist geschlossen genau dann,wenn alle Vorkommnisse aller Individuenvariable gebunden sind. (Geschlossene Formeln wer-den auch Satz genannt.)

7.3.2.6. Offene und geschlossene Formeln VI

Beispiele

• Fa ∧ ∃xFx – geschlossene Formel

• F ′xa – offene Formel

• ∀x(Fx→ Gx) – geschlossene Formel

• ∀xFx→ Gx – offene Formel (x kommt zweimal gebunden, aber auch einmal ungebun-den vor)

7.4. Quantoren

7.4.1. Existenzquantor

Der Existenzquantor Dem „∃“ entsprechen in der natürlichen Sprache Wendungen wie „Esgibt ein . . . , das . . . “.

Anmerkungen

• Unter „Es gibt ein . . . “ verstehen wir stets „Es gibt mindestens ein . . . “. Auch „Es gibtschwarze Schwäne“ verstehen wir als „Es gibt mindestens einen schwarzen Schwan“

• „Es gibt ein . . . “ verstehen wir unzeitlich, das heißt „Es gibt mind. einen schwarzenSchwan“ ist genau dann wahr, wenn es einen schwarz Schwan gab, gibt oder gebenwird.

• In der PL ist Existenz kein Prädikat, das auf Individuenkonstanten angewendet wird,sondern nur auf andere Prädikate („Prädikat zweiter Stufe“).

Beispiel

• Natürlichsprachlicher Satz: Es gibt grüne Frösche.

• Paraphrase: Es gibt (mind.) ein x, für das gilt: x ist ein Frosch und x ist grün

• Symbolisierungsbasis: F: . . . ist ein Frosch, G: . . . ist grün

• Formalisierung: ∃x(Fx ∧Gx)

71


Weitere Beispiele

• Es gibt Frösche, die grün sind. ∃x(Fx ∧Gx)

• Manche Frösche sind grün. ∃x(Fx ∧Gx)

• Einige Frösche sind grün. ∃x(Fx ∧Gx)

• Es existieren grüne Frösche. ∃x(Fx ∧Gx)

• Es gibt grüne Frösche, die Heißhunger haben. ∃x((Fx ∧Gx) ∧Hx)

7.4.2. Allquantor

Der Allquantor Dem Allquantor „∀“ entsprechen in der natürlichen Sprache Wendungenwie „Für alle . . . gilt . . . “.

Anmerkungen

• „Alle“ bedeutet wirklich alles! Das ist in der natürlichen Sprache selten der Fall, vgl.„Hast du auch alles eingepackt?“.

• Unter „alles“ fallen vergangene, gegenwärtige und zukünftige Gegenstände, raum-zeit-liche Gegenstände (Steine, Stühle, Menschen usw.) ebenso wie abstrakte Gegenstände(Zahlen, Mengen, der Äquator usw.)

Beispiel

• Natürlichsprachlicher Satz: Alle Frösche sind grün.

• Paraphrase: Für alle Gegenstände x gilt: Wenn x ein Frosch ist, dann ist x grün.

• Symbolisierungsbasis: F: . . . ist ein Frosch, G: . . . ist grün

• Formalisierung: ∀x(Fx→ Gx)

∀ und → Diese Formalisierung ist gewöhnungsbedürftig. Denn: Gemäß der Formalisierunghandelt „alle F sind G“ nicht nur von allen F, sondern von absolut allem. Es wird behauptet,dass für jeden beliebigen Gegenstand gilt: wenn er ein F ist, dann ist er G.

Ist das plausibel? Betrachten wir das Kondtional: Wenn x ein Frosch ist, dann ist x grün.

• Nachbars Katze erfüllt das Konditional: Der Vordersatz ist falsch, somit ist das Kon-ditional wahr.

• Eine grüne Tasse erfüllt das Konditional: Der Vordersatz ist falsch, somit ist das Kon-ditional wahr. (Der Nachsatz ist wahr, aber das spielt bei einem falschen Vordersatzkeine Rolle mehr.)

72


• Sokrates erfüllt das Konditional: Der Vordersatz ist falsch, somit ist das Konditionalwahr.

• Kermit der Frosch erfüllt das Konditional: Der Vordersatz ist wahr, aber auch derNachsatz, somit ist das Konditional wahr.

Also: Alle Nicht-Frösche erfüllen das Konditional trivialerweise. Es schadet daher nicht, wennein Allsatz von allen Gegenständen handelt.

∀ und → – Das Umformungsargument

1. Alle Menschen sind sterblich.

2. ⇔ Es ist nicht der Fall, dass es einen unsterblichen Menschen gibt.

3. ⇔ ¬∃x(Fx ∧ ¬Gx)

4. ⇔ ∀x¬(Fx ∧ ¬Gx) (da „Es gibt kein x, das F ist“ synonym mit „Alle x sind nicht F“)

5. ⇔ ∀x(¬Fx ∨Gx) (da ¬(A ∧ ¬B) äquivalent mit ¬A ∨B)

6. ⇔ ∀x(Fx→ Gx) (da ¬A ∨B äquivalent mit A→ B)

Wichtige Konsequenz Wenn es keine Fs gibt, ist jeder Satz der Form „Alle Fs sind . . . “wahr. Formal: ¬∃xFx ⊧ ∀x(Fx→ Gx)

Beispiele

• Alle Einhörner sind weiß. – Wahr, weil es keine Einhörner gibt.

• Alle Einhörner sind nicht weiß. – Wahr, weil es keine Einhörner gibt.

• Alle Einhörner sind keine Einhörner – Wahr, weil es keine Einhörner gibt.

Weitere Beispiele

• Alle grünen Frösche haben Heißhunger. ∀x((Fx ∧Gx)→Hx)

• Alle Frösche, die grün sind, haben Heißhunger. ∀x((Fx ∧Gx)→Hx)

• Alle Frösche und Heuschrecken sind grün. ∀x(Fx→ Gx)∧∀y(Hy → Gy) oder ∀x((Fx∨Hx)→ Gx)

73


7.4.3. Zusammenfassung

Formalisierungen

Satz Formel

Alle Fs sind Gs ∀x(Fx→ Gx)Fs, die ein G sind, sind H ∀x((Fx ∧Gx)→Hx)Es gibt f-ige Gs ∃x(Fx ∧Gx)Es gibt/existieren Fs, die G sind ∃x(Fx ∧Gx)Manche/Einige Fs sind Gs ∃x(Fx ∧Gx)

Merke

• Steht vorne eine ∀ kommt als Hauptjunktor (fast immer) ein →!

• Steht vorne eine ∃ kommt als Hauptjunktor (fast immer) ein ∧!

Äquivalenzen

Satz Formel Satz Formel

Nicht alle Fs sindGs

¬∀x(Fx→ Gx) ⇔ Es gibt ein F, dasnicht G ist

∃x(Fx ∧ ¬Gx)

Kein F ist G / Esgibt kein F, das Gist

¬∃x(Fx ∧Gx) ⇔ Alle Fs sind nichtG

∀x(Fx→ ¬Gx)

Interdefinierbarkeit der Quantoren

1. ¬∀x¬. . . â⊧ ∃x . . .

2. ¬∃x¬. . . â⊧ ∀x . . .

7.4.4. Eingebettete Quantoren

Eingebettete Quantoren Innerhalb des Skopus eines Quantor kommt ein weiterer Quantorvor.

Erstes Beispiel Jeder Rationalist kritisiert jeden Empiristen.

Lösung

• F: . . . ist Rationalist, G: . . . ist Empirist, F’: . . . kritisiert . . .

• ∀x(Fx→ ∀y(Gy → F ′xy)) oder

• ∀x∀y((Fx ∧Gy)→ F ′xy)

74


Zweites Beispiel Wenn alle alle mögen, hasst niemand jemanden.

Lösung

• F’: . . .mag . . . , G’: . . . hasst . . .

• ∀x∀yF ′xy → ¬∃x∃yG′xy

Alternative Lösung

• F’: . . .mag . . . , G’: . . . hasst . . . , H: . . . ist ein Mensch

• ∀x∀y((Hx ∧Hy)→ F ′xy)→ ¬∃x∃y((Hx ∧Hy) ∧G′xy)

Drittes Beispiel

1. Alles ist irgendwann vorbei.

2. Irgendwann ist alles vorbei.

Lösungen F: . . . ist ein Zeitpunkt, G’: . . . ist zu . . . vorbei

1. ∀x∃y(Fy ∧G′xy)

2. ∃y∀x(Fy ∧G′xy)

Viertes Beispiel

1. Jeder mag ein Getränk.

2. Es gibt ein Getränk, das jeder mag.

Lösungen F: . . . ist ein Mensch, G: . . . ist ein Getränk, F’: . . .mag . . .

1. Zwei Lösungen:

• ∀x(Fx→ ∃y(Gy ∧ F ′xy))• ∀x∃y(Fx→ (Gy ∧ F ′xy))

2. Zwei Lösungen:

• ∃x(Gx ∧ ∀y(Fy → F ′yx))• ∃x∀y(Gx ∧ (Fy → F ′yx))

75


Mehrdeutige Sätze Es ist oft nicht einfach zu entscheiden, welche Lesart gemeint ist.

• Einen geheimen Freibadzugang kennt jeder Jugendliche.

• Die Hälfte aller Länder hat jeder Globetrotter bereist.

Fünftes Beispiele

1. Alle Idioten sägen an dem Ast, auf dem sie selber sitzen.

2. Es gibt einen Weisen, der an allen Ästen sägt, aber nicht an dem, auf dem er selbersitzt.

Lösungen

1. F: . . . ist weise, G: . . . ist ein Ast, H’: . . . sägt an . . . , J: . . . ist ein Idiot, K’: . . . sitzt auf. . .

2. ∀x(Jx→ ∃y((Gy ∧K ′xy) ∧H ′xy))

3. ∃x(Fx ∧ ∀y((Gy ∧ ¬K ′xy)→H ′xy))

Zusammenfassung eingebettete Quantoren

Satz Formel

Alle F stehen in Relation H zu einem G ∀x(Fx→ ∃y(Gy ∧H ′xy))∀x∃y(Fx→ (Gy ∧H ′xy))

Ein G steht in Relation H zu allen F ∃y(Gy ∧ ∀x(Fx→H ′xy))∃y∀x(Gy ∧ (Fx→H ′xy))

76

8. Prädikatenlogik: Semantik

8.1. Mengenlehre

8.1.1. Semantik der PL: Ausblick

Individuenkonstanten und Prädikate

• Eine pl Interpretation ordnet jeder Individuenkonstante genau einen Gegenstand zu.

• Eine pl Interpretation ordnet jedem einstelligen Prädikat eine Menge von Gegenstän-den zu.

• Eine pl Interpretation ordnet jedem zweistelligen Prädikat eine Menge von Paaren vonGegenständen zu.

• Eine pl Interpretation ordnet jedem n-stelligen Prädikat eine Menge von n-Tupeln vonGegenständen zu.

Um das zu verstehen, müssen wir zunächst einige Grundbegriffe der (naiven) Mengenlehreklären, nämlich die Begriffe der Menge, des Paars und des n-Tupels u. a.

8.1.2. Mengenlehre

8.1.2.1. Mengenlehre I: Mengen

Menge Eine Menge ist eine Ansammlung beliebiger Gegenstände, bei der es auf die Rei-henfolge nicht ankommt. Die Gegenstände, aus denen eine Menge besteht, sind dieElementedieser Menge.

Schreibweise

• a ∈M – Der Gegenstand a ist Element der Menge M

• {a, b, c} – Die Menge bestehend aus den Elementen a, b und c.

• {x ∶ Fx} – Die Menge bestehend aus allen x, auf die das Prädikat F zutrifft.

8.1.2.2. Mengenlehre II: Mengen

Beispiele

• {x: x ist Regensburger Logikdozent} = {Hans Rott, Holger Leuz, Tim Kraft}

• Sinje ∈ {x: x ist Logiker}

77


• {Regensburg, die Mensa, 7, der Äquator}

• {{Sokrates, Platon, Aristoteles}, {Locke, Berkeley, Hume}}

8.1.2.3. Mengenlehre III: Leermengen

Leermenge Auch die Leermenge ∅ = {} ist eine Menge. Die Leermenge hat kein Element.

8.1.2.4. Mengenlehre IV: Identität von Mengen

Definition 33 (Identität von Mengen). Zwei Mengen sind identisch genau dann, wennsie dieselben Elemente haben. Formal:M =M ′ genau dann, wenn für alle x gilt: x ∈M genaudann, wenn x ∈M ′

Beispiele

• {1,2,3} = {2,1,3}

• {1,2,3} = {1,2,2 + 1}

• {x: x ist Regensburger Logikdozent} ≠ {Hans Rott, Holger Leuz, Tim Kraft, Poldi}

• {1,2,3} ≠ {{1,2,3}}

8.1.2.5. Mengenlehre V: Teilmenge

Definition 34 (Teilmenge). Eine Menge A ist Teilmenge der Menge B genau dann,wenn jedes Element von A auch ein Element von B ist. A ⊆ B genau dann, wenn für alle xgilt: wenn x ∈ A, dann x ∈ B.

Es gilt

• Die Leermenge ist Teilmenge jeder Menge M: {} ⊆M

• Jede Menge M ist Teilmenge von sich selbst: M ⊆M

8.1.2.6. Mengenlehre VI: Teilmenge

Beispiele

• {1,2} ⊆ {1,2,3}

• {1,2,3} ⊆ {1,2,3}

• {} ⊆ {1,2,3}

• {} ⊆ {}

78


8.1.2.7. Mengenlehre VII: Vereinigungs- und Schnittmenge

Definition 35 (Vereinigungs- und Schnittmenge). Seien A und B beliebige Mengen.Die Vereinigungsmenge von A und B ist die Menge aller Elemente, die Element von A oderElement von B sind. Formal:

A ∪B = {x ∶ x ∈ A ∨ x ∈ B}

Die Schnittmenge von A und B ist die Menge aller Elemente, die Element von A und Elementvon B sind. Formal:

A ∩B = {x ∶ x ∈ A ∧ x ∈ B}

8.1.2.8. Mengenlehre VIII: Vereinigungs- und Schnittmenge

Beispiele SeiA = {Berlin, München, Hamburg} undB = {Berlin, Kopenhagen, Stockholm}Dann ist:

• A ∪B = {Berlin, München, Hamburg, Kopenhagen, Stockholm}

• A ∩B = {Berlin}

8.1.2.9. Mengenlehre IX: n-Tupel

Reihenfolge Bei Mengen kommt es nicht auf die Reihenfolge an. Bei mehrstelligen Prädi-katen ist die Reihenfolge aber wichtig.

Beispiel:

• Natürlichsprachlicher Satz: Regensburg liegt nördlich von München

• Symbolisierungsbasis: a: Regensburg, b: München, F’: . . . liegt nördlich von . . .

• Ergebnis: F ′ab ist richtig, F ′ba ist falsch.

8.1.2.10. Mengenlehre X: n-Tupel

Geordnete Paare Das geordnete Paar ⟨a, b⟩ besteht aus den Elementen a und b in dieserReihenfolge.

Beispiel:

• ⟨Regensburg, München⟩ ≠ ⟨München, Regensburg⟩

8.1.2.11. Mengenlehre XI: n-Tupel

Geordnete Paare bestehen aus genau zwei Elementen. Dies lässt sich verallgemeinern:

n-Tupel Ein n-Tupel ist eine Ansammlung von n Gegenständen, bei der es auf die Rei-henfolge ankommt.

79


Beispiele

• 3-Tupel bzw. Tripel: ⟨München, Regensburg, Ingolstadt⟩

• 4-Tupel bzw. Quadrupel: ⟨Wien, Österreich, Budapest, Ungarn⟩

• usw.

Betr. 1-Tupel: Per Konvention sei ein 1-Tupel identisch mit seinem einzigen Element:⟨a⟩ = a

8.1.2.12. Mengenlehre XII: Kartesisches Produkt

Kartesisches Produkt Das kartesische ProduktM×N ist die Menge aller geordneten Paare,die an der ersten Stelle ein Element von M haben und an der zweiten Stelle ein Element vonN.

Kartesisches Produkt verallgemeinert Das kartesische ProduktM1×⋅ ⋅ ⋅×Mn ist die Mengealler n-Tupel, die an der i-ten Stelle jeweils ein Element von Mi haben.

Schreibweise Statt M ×M schreiben wir auch M2, statt M ×M ×M auch M3 usw.

8.1.2.13. Mengenlehre XIII: Kartesisches Produkt

Beispiel 1 Sei M = {Anna,Ben}. Dann ist:M ×M = { ⟨Anna,Anna⟩,

⟨Anna,Ben⟩,⟨Ben,Anna⟩,⟨Ben,Ben⟩ }

8.1.2.14. Mengenlehre XII: Kartesisches Produkt

Beispiel 2 Sei M = {Anna,Ben}. Dann ist:M ×M ×M = { ⟨Anna,Anna,Anna⟩,

⟨Anna,Anna,Ben⟩,⟨Anna,Ben,Anna⟩,⟨Anna,Ben,Ben⟩,⟨Ben,Anna,Anna⟩,⟨Ben,Anna,Ben⟩,⟨Ben,Ben,Anna⟩,⟨Ben,Ben,Ben⟩ }

8.2. Semantik

8.2.1. Semantik

Ziel Ziel der Semantik ist es, allen (geschlossenen) Formeln Wahrheitswerte zuzuordnen.

80


Der Grundgedanke Individuenkonstanten stehen für einzelne Gegenstände. Prädikate ste-hen für Mengen von (n-Tupeln von) Gegenständen.

Vom Grundgedanken zu Wahrheitswerten

• Die Formel Fa ist wahr genau dann, wenn der Gegenstand, für den a steht, Elementder Menge, für die F steht, ist.

• Die Formel F ′ab ist wahr genau dann, wenn das geordnete Paar bestehend aus denGegenständen, für die a und b stehen, Element der Menge, für die F ′ steht, ist.

• Die Formel ∃xFx ist wahr genau dann, wenn es einen Gegenstand gibt, der Elementder Menge ist, für die F steht.

• Die Formel ∀xFx ist wahr genau dann, wenn alle Gegenstände Element der Mengesind, für die F steht.

Interpretation Eine prädikatenlogische Interpretation (oder: Modell) besteht aus:

1. Einer nicht-leeren Menge D, dem sog. Gegenstandsbereich, und

2. einer Interpretation ID, das heißt eine Funktion, die

a) jeder Individuenkonstante einen Gegenstand aus D zuordnet und

b) jedem ein-stelligen Prädikat eine Teilmenge von D zuordnet, jedem zwei-stelligenPrädikat eine Teilmenge vonD2 zuordnet usw. oder, allgemein ausgedrückt, jedemn-stelligen Prädikat eine Teilmenge von Dn zuordnet.

Anmerkung Den Index D in ID lassen wir im Folgenden weg und setzen ihn stillschweigendvoraus.

Wozu Gegenstandsbereich? (engl. domain)

• Eine Tautologie ist wahr unabhängig davon, wie viele und welche Gegenstände estatsächlich gibt. Ein Argument ist folgerichtig unabhängig davon, wie viele und welcheGegenstände es tatsächlich gibt.

• Diese Unabhängigkeit spiegelt sich darin wider, dass wir den Gegenstandsbereich (oder:Diskursuniversum) variabel halten.

Warum darf der Gegenstandsbereich nicht leer sein? Wäre der Gegenstandsbereich leer,könnten Individuenkonstanten nicht interpretiert werden.

81


Beispiel Angenommen wir wollen die Individuenkonstanten a, b, c und die Prädikate F, G,H’ interpretieren. Wir suchen uns zunächst einen Gegenstandsbereich aus, beispielsweise:D = {Carina,Gordon, Johanna}

Wir ordnen jeder Individuenkonstante einen Gegenstand aus D zu, beispielsweise:I(a) = Carina, I(b) = Gordon, I(c) = Gordon

Wir ordnen jedem einstelligen Prädikat eine Teilmenge von D zu, beispielsweise:I(F ) = {Carina,Gordon}, I(G) = {}

Wir ordnen jedem n-stelligem Prädikat eine Teilmenge von Dn zu, beispielsweise:I(F ′) = {⟨Carina,Carina⟩, ⟨Carina,Gordon⟩}

Bewertung Eine pl Bewertung ist eine Funktion BI , die auf der Grundlage einer Interpre-tation I (genauer: auf der Grundlage eines Gegenstandsbereich D und einer InterpretationID) jeder geschlossenen Formel von PL genau einen der Wahrheitswerte Wahr und Falschzuordnet.

Vorgehen Wir verzichten darauf, die Bewertungsfunktion streng zu definieren und be-schränken uns auf Beispiele! (Die Definition findet sich aber im Anhang zu diesem Kapitel,siehe 8.4!)

Bewertungsfunktion anhand von Beispielen

• BI(Fa) =W genau dann, wenn I(a) ∈ I(F )

• BI(F ′ab) =W genau dann, wenn ⟨I(a), I(b)⟩ ∈ I(F ′)

• BI(∃xFx) =W genau dann, wenn es einen Gegenstand x ∈D gibt, so dass x ∈ I(F )

• BI(∀xFx) =W genau dann, wenn für alle Gegenstände x ∈D gilt, dass x ∈ I(F ) ist.

• BI(∀x(Fx → Gx)) = W genau dann, wenn für alle Gegenstände x ∈ D gilt, dassx ∉ I(F ) ist oder x ∈ I(G) ist.

8.2.2. Definitionen

Die Definitionen von Tautologie, Kontradiktion, Folgerichtigkeit usw. bleiben erhalten. Bei-spiele:

Tautologie Eine pl Formel ist eine Tautologie genau dann, wenn sie wahr relativ zu jederInterpretation ist.

Folgerichtigkeit Ein pl Argument ist folgerichtig genau dann, wenn es keine Interpreta-tion gibt, relativ zu der die Prämissen wahr und die Konklusion falsch ist.

82


8.3. Interpretationen und Gegenbeispiele

8.3.1. Einleitung

Konsequenz der Semantik Der Einblick in die Semantik macht deutlich, dass es in der PLkein Verfahren analog zu Wahrheitstafeln gibt. Mit Wahrheitstafeln geht man einfach alleMöglichkeiten (der Verteilung von Wahrheitswerten auf Satzbuchstaben) durch. Da es aberschon bei der Interpretation eines einzigen Prädikates unendlich viele Möglichkeiten gibt,kann man in der PL nicht alle Möglichkeiten durchgehen.

Interpretationen und Gegenbeispiele Der Apparat der formalen Semantik ist hilfreich, umBeispiele und Gegenbeispiele angeben zu können.

Drei Arten von Beispielen

• Interpretation, relativ zu der eine Formel wahr ist (Beispiel für Erfüllbarkeit)

• Interpretation, relativ zu der eine Formel falsch ist (Gegenbeispiel gegen Tautologie)

• Interpretation, relativ zu der die Prämissen wahr sind, aber die Konklusion falsch(Gegenbeispiel gegen Folgerichtigkeit)

8.3.2. Formeln

8.3.2.1. Beispiel 1

Aufgabe Gib eine Interpretation an, relativ zu der die Formel

Fa

wahr ist. Der Gegenstandsbereich sei D = {Sinje, Tammo, Wilfried}.

Lösung

• I(a) = Sinje, I(F ) = {Sinje, Tammo} oder

• I(a) = Tammo, I(F ) = {Sinje, Tammo,Wilfried} oder

• I(a) = Sinje, I(F ) = {Sinje} oder

• . . .

8.3.2.2. Beispiel 2


F ′ab ∧ F ′aa

wahr ist. Der Gegenstandsbereich sei D = {Carina,Gordon, Johanna}.

83


LösungI(a) = Carina

I(b) = Gordon

I(F ′) = {⟨Carina,Gordon⟩, ⟨Carina,Carina⟩}

8.3.2.3. Beispiel 3


∀x(Fx→ Gx)


LösungI(F ) = {Carina}

I(G) = {Carina,Gordon}

8.3.2.4. Beispiel 4

Aufgabe (Wiederholung) Gib eine Interpretation an, relativ zu der die Formel

∀x(Fx→ Gx)


Andere LösungI(F ) = {}

I(G) = {}

8.3.2.5. Beispiel 5


Fa ∨ (Fb ∧Gb)

wahr ist. Der Gegenstandsbereich sei D = {1,2,3}.

LösungI(a) = 1

I(b) = 1

I(F ) = {1}

I(G) = {}

84


8.3.2.6. Hinweise

Gesammelte Hinweise

• Es müssen alle in der Formel vorkommenden Individuenkonstanten und Prädikate in-terpretiert werden.

• Mehreren Individuenkonstanten darf derselbe Gegenstand zugeordnet werden.

• Prädikaten darf die Leermenge zugeordnet werden (aber auch der gesamte Gegen-standsbereich D).

• Um die Interpretation nicht unnötig komplex werden zu lassen, wählen wir als Gegen-standsbereich gerne kleine Mengen wie D = {1,2,3}.

8.3.3. Argumente

8.3.3.1. Beispiel 1

Aufgabe Gib eine Interpretation an, relativ zu der die Prämissen wahr und die Konklusionfalsch ist.

∀x(Fx→ Gx)

∴∃x(¬Fx ∧Gx)

Der Gegenstandsbereich sei D = {1,2,3}.

LösungI(F ) = {1,2}

I(G) = {1,2}

Jede Interpretation mit I(F ) = I(G) ist eine Lösung.

8.3.3.2. Beispiel 2

Aufgabe Gib eine Interpretation an, relativ zu der die Prämissen wahr und die Konklusionfalsch ist.

∀x(F ′ax↔ F ′xa)

∴F ′ab ∨ F ′ba

Der Gegenstandsbereich sei D = {1,2,3}.

LösungI(a) = 1

I(b) = 1

I(F ′) = {⟨1,2⟩, ⟨2,1⟩, ⟨3,1⟩, ⟨1,3⟩}

85


8.3.4. Ausblick

Ausblick Mit Kreativität kommt man zwar oft auf geeignete Beispiele, aber ein mechani-sches Verfahren zur Überprüfung, ob ein Formel tautologisch oder ein Argument folgerichtigist, wäre einfacher. Im nächsten Kapitel lernen wir mit dem Baumkalkül für die PL einsolches Verfahren kennen.

8.4. *Appendix zur Semantik

Bewertungsfunktion Die prädikatenlogische Bewertungsfunktion BI bei einer gegebenenprädikatenlogischen Interpretation I über einen Gegenstandsbereich D lässt sich wie folgtinduktiv definieren:

1. Wenn Θ irgendein n-stelliger Prädikatausdruck ist und α1, . . . αn Individuenkonstantensind, dann gilt:

BI(Θα1, . . . , αn) =W ⇔ ⟨I(α1), . . . , I(αn)⟩ ∈ I(Θ)

BI(Θα1, . . . , αn) = F ⇔ ⟨I(α1), . . . , I(αn)⟩ ∉ I(Θ)

2. Wenn Φ eine geschlossene pl Formel ist, dann gilt:

BI(¬Φ) =W ⇔ BI(Φ) = F

BI(¬Φ) = F ⇔ BI(Φ) =W

3. Wenn Φ und Ψ geschlossene pl Formeln sind, dann gilt:

BI(Φ ∧Ψ) =W ⇔ BI(Φ) =Wund BI(Ψ) =W

BI(Φ ∧Ψ) = F ⇔ in allen anderen Fällen

Analoge Regeln gelten für ∨, → und ↔

4. Wenn Φ eine pl Formel ist und alle freien Vorkommnisse einer Individuenvariablen inΦ, Vorkommnisse der Individuenvariable α sind, dann gilt:

a) BI(∀αΦ) = W ⇔ für alle Interpretationen I ′, die sich von I höchstens dadurchunterscheiden, was sie β zuordnen, gilt: BI′(Φ′) =W , wobei Φ′ das Ergebnis derErsetzung aller freien Vorkommnisse von α in Φ durch die Individuenkonstanteβ ist, die in Φ noch nicht vorkommt

b) BI(∀αΦ) = F ⇔ für mindestens eine Interpretation I ′, die sich von I höchs-tens dadurch unterscheidet, was sie β zuordnet, gilt: BI′(Φ′) = F , wobei Φ′ dasErgebnis der Ersetzung aller freien Vorkommnisse von α in Φ durch die Indivi-duenkonstante β ist, die in Φ noch nicht vorkommt

c) BI(∃αΦ) = W ⇔ für mindestens eine Interpretation I ′, die sich von I höchs-tens dadurch unterscheidet, was sie β zuordnet, gilt: BI′(Φ′) =W , wobei Φ′ dasErgebnis der Ersetzung aller freien Vorkommnisse von α in Φ durch die Indivi-duenkonstante β ist, die in Φ noch nicht vorkommt

86


d) BI(∃αΦ) = F ⇔ für alle Interpretationen I ′, die sich von I höchstens dadurchunterscheidet, was sie β zuordnet, gilt: BI′(Φ′) = F , wobei Φ′ das Ergebnis derErsetzung aller freien Vorkommnisse von α in Φ durch die Individuenkonstanteβ ist, die in Φ noch nicht vorkommt

Anmerkungen

• BI ordnet jeder geschlossenen Formel einen Wahrheitswert zu; offene Formeln habenkeinen Wahrheitswert.

• Statt BI(Φ) =W wird oft auch ID ⊧ Φ o. ä. geschrieben. Das Zeichen ⊧ bedeutet hiernicht „impliziert logisch“, sondern „die Interpretation (oder: das Modell) ID erfüllt Φ“.Meist entscheidet der Kontext, welche Lesart gemeint ist.

Vereinfachung Die Definition der Bewertungsfunktion lässt sich mittels zusätzlicher Defi-nitionen noch vereinfachen:

1. Φ[α∣β] =Def. das Ergebnis der Ersetzung aller freien Vorkommnisse der Individuenva-riable α in Φ durch die Individuenkonstante β, die in Φ noch nicht vorkommt.

2. I ′ ist eine β-Variante von I genau dann, wenn I ′ sich von I höchstens dadurchunterscheidet, was I ′ β zuordnet.

Variante der Definition der Bewertungsfunktion Nun können wir die Klausel 4. auch wiefolgt formulieren:

a) BI(∀αΦ) =W ⇔ für alle β-Varianten I ′ von I gilt: BI′(Φ[α∣β]) =Wb) BI(∀αΦ) = F ⇔ für mind. eine β-Variante I ′ von I gilt: BI′(Φ[α∣β]) = Fc) BI(∃αΦ) =W ⇔ für mind. eine β-Variante I ′ von I gilt: BI′(Φ[α∣β]) =Wd) BI(∃αΦ) = F ⇔ für alle β-Varianten I ′ von I gilt: BI′(Φ[α∣β]) = F

Hinweise Diese Art, formale Semantik zu betreiben, geht auf Tarskis Der Wahrheitsbegriffin den formalen Sprachen (1933/35) zurück. Anders als Tarski verzichten wir hier auf Varia-blenbelegungen. Der Knackpunkt ist die Klausel „Ersetzung durch die Individuenkonstanteβ, die in Φ noch nicht vorkommt“. Das oben beschriebene Verfahren setzt voraus, dass esfür jede Formel eine solche Individuenkonstante gibt; wir dürfen dies voraussetzen, weil wirin der Syntax explizit unendlich viele Individuenkonstanten vorgesehen haben, jede Formelaber nur endlich viele Individuenkonstanten enthalten kann. Tarskis ursprünglicher Ansatzhat den Vorteil, auch auf Varianten der PL anwendbar zu sein, bei der diese Voraussetzungnicht erfüllt ist, etwa eine PL ohne Individuenkonstanten. (Siehe Beckermann und Büh-ler für die hier vorgestellte Version der formalen Semantik und bspw. Halbach für Tarskisursprünglichen Vorschlag; für Literaturangaben siehe Anhang D.)

87

9. Prädikatenlogik: Baumkalkül

9.1. Neue Regeln

9.1.1. Gliederung

Programm Wir suchen ein Verfahren, mit dem gezeigt werden kann, dass . . .

• . . . eine Formel tautologisch, kontradiktorisch oder kontingent ist.

• . . . ein Argument folgerichtig ist.

Der Baumkalkül für die PL . . .

• . . . ähnelt weitgehend dem Baumkalkül für die AL

• . . . zusätzliche Regeln auf dem Regeblatt

9.1.2. Neue Regeln

Wie viele neue Regeln werden benötigt? Wir haben für jeden zweistelligen Junktor jeweilszwei Regeln, einmal für den nicht-negiert Junktor und einmal für den negiert Junktor. Ebensoführen wir für die Quantoren jeweils zwei Regeln ein: Eine Regel für die nicht-negiertenQuantoren und eine Regel für die negierten Quantoren.

Regel für den Allquantor ∀αΦ↓

Φ[α∣β]

Erläuterung: In Φ werden alle freien Vorkommnisse der Variable α durch eine beliebigeIndividuenkonstante β ersetzt.

Rechtfertigung der Regel

• Alle lächeln. (∀xFx)

Wenn alle lächeln, dann lächelt auch Carina, aber auch Wilfried, und auch . . . usw. Alsofolgt:

• Carina lächelt. (Fa)

Da mit „alles“ wirklich Alles gemeint ist, kann man also eine beliebige Individuenkonstanteeinsetzen.

88


Regel für den Existenzquantor ∃αΦ↓

Φ[α∣ν]

Erläuterung: In Φ werden alle freien Vorkommnisse der Variable α durch eine (in diesemAst) neue Individuenkonstante ν ersetzt.


• Es gibt jemanden, der lächelt. (∃xFx)

Wir wissen nicht, wie sie/er heißt, nennen wir sie/ihn doch – wer auch immer das sein mag!– „Smiley“. Also folgt:

• Smiley lächelt. (Fa)

Da wir nicht wissen, welcher Gegenstand die behauptete Eigenschaft hat, müssen wir zueinem Trick greifen: Wir führen eine neue Individuenkonstante ein und definieren, dass die-se Individiduenkonstante für denjenigen steht – wer auch immer das sein mag –, der diebehauptete Eigenschaft hat. Deshalb muss die Individuenkonstante neu sein.

Regel für den negierten Allquantor ¬∀αΦ↓

∃α¬Φ


• Nicht alles ist vergänglich (¬∀xFx)

besagt dasselbe wie:

• Es gibt etwas, das nicht vergänglich ist. (∃x¬Fx)

Regel für den negierten Existenzquantor ¬∃αΦ↓

∀α¬Φ


• Es gibt nicht etwas, das vergänglich ist. (¬∃xFx)

besagt dasselbe wie:

• Alles ist nicht vergänglich. (∀x¬Fx)

89


Nicht abhaken!

• Da die Regel für den Allquantor und die Regel für den Existenzquantor mehrfach an-gewendet werden können, werden die Zeilen, auf die diese Regeln angewendet wurden,nicht abgehakt.

• Wir notieren jedoch, welche Individuenkonstante eingesetzt wurde.

• Wenn die Regel für den negierten Allquantor oder die Regel für den negierten Exis-tenzquantor angewendet werden, wird wie gehabt abgehakt.

Beachte

• Auf die Zeile∀x(Fx→ Gx)

kann nicht die Regel für das Konditional angewendet werden!

• Auf die Zeile∀xFx→ Ga

kann nicht die Regel für den Allquantor angewendet werden!

Klugheitsregel Es ist sinnvoll, die Regeln in der folgenden Reihenfolge anzuwenden:

1. Junktorenregeln, die nicht aufspalten

2. Junktorenregeln, die aufspalten

3. Regeln für negierte Quantoren

4. Regel für Existenzquantor

5. Regel für Allquantor

9.2. Beispiele

9.2.1. Beispiele Formeln

9.2.1.1. Beispiel 1

Aufgabe: Zeige mit dem Baumkalkül, dass die folgende prädikatenlogische Formel tautolo-gisch ist!

¬∃x(Fx ∧ ¬Fx)

90


Ansatz: Entwickle den Baum mit der negierten Formel als Wurzel!

1. ¬¬∃x(Fx ∧ ¬Fx)✓2. ∃x(Fx ∧ ¬Fx) (1)[a]

3. Fa ∧ ¬Fa (2)✓4. Fa (3)

5. ¬Fa (3)×

Ergebnis: Die Formel ¬∃x(Fx ∧ ¬Fx) ist tautologisch.

9.2.1.2. Beispiel 2

Aufgabe Zeige mit dem Baumkalkül, dass die folgende prädikatenlogische Formel kontra-diktorisch ist!

¬Fa ∧ ∀xFxAnsatz: Entwickle den Baum mit der Formel als Wurzel!

1. ¬Fa ∧ ∀xFx✓2. ¬Fa (1)

3. ∀xFx (1)[a]4. Fa (3)

×

Ergebnis: Die Formel ¬Fa ∧ ∀xFx ist kontradiktorisch.

9.2.2. Beispiele Argumente

9.2.2.1. Beispiel 3

Aufgabe: Zeige mit dem Baumkalkül, dass das folgende prädikatenlogische Argument fol-gerichtig ist!

∀x(Fx→ Gx)

Fa

∴ Ga

Ansatz: Entwickle den Baum mit der Prämissen und der negierten Konklusion als Wurzel!

1. ∀x(Fx→ Gx) [a]2. Fa

3. ¬Ga4. Fa→ Ga (1)✓

5. ¬Fa (4)×

6. Ga (4)×

Ergebnis: Das Argument ist folgerichtig.

91


9.2.2.2. Beispiel 4


∃x(Fx ∨Gx)

∃xFx ∨ ∃yFy


1. ∃x(Fx ∨Gx) [a]2. ¬(∃xFx ∨ ∃yGy)✓

3. ¬∃xFx (2)✓4. ¬∃yGy (2)✓

5. ∀x¬Fx (3)[a]6. ∀y¬Gy (4)[a]7. Fa ∨Ga (1)✓

8. Fa (7)10. ¬Fa (5)

×

9. Ga (7)11. ¬Ga (6)

×Ergebnis: Das Argument ist folgerichtig.

9.2.2.3. Beispiel 5


∃xF ′xa ∧ ¬∀yF ′ya

¬(∀x¬F ′xa ∨ ∀yF ′ya)


1. ∃xF ′xa ∧ ¬∀yF ′ya✓2. ¬¬(∀x¬F ′xa ∨ ∀yF ′ya)✓3. (∀x¬F ′xa ∨ ∀yF ′ya) (2)

4. ∃xF ′xa (1)[b]5. ¬∀yF ′ya (1)✓6. ∃¬yF ′ya (5)[b]

7. ∀x¬F ′xa (3)[b]9. F ′ba (4)

10. ¬F ′ba(7)×

8. ∀yF ′ya (3)[b]11.¬F ′ba (6)12.F ′ba (8)

×

Ergebnis: Das Argument ist folgerichtig.

92


9.2.3. Letztes Beispiel

Hinweis: Zum Abschluss noch ein besonders kniffliges Beispiel.Aufgabe: ⊧ ¬∀y∃x(F ′xa ∧ ¬F ′ya) ∧ (∀xF ′xa→ ∃yF ′ya)

1. ¬(¬∀y∃x(F ′xa ∧ ¬F ′ya) ∧ (∀xF ′xa→ ∃yF ′ya))✓

2. ¬¬∀y∃x(F ′xa ∧ ¬F ′ya) (1)✓9. ∀y∃x(F ′xa ∧ ¬F ′ya) (2) [a][b]

10. ∃x(F ′xa ∧ ¬F ′aa) (9) [b]11. F ′ba ∧ F ′aa (10)✓

12. F ′ba (11)13. F ′aa (11)

3. ¬(∀xF ′xa→ ∃yF ′ya) (1)✓4. ∀xF ′xa (3) [a]5. ¬∃yF ′ya (3)✓6. ∀y¬F ′ya (5) [a]

7. F ′aa (4)8. ¬F ′aa (6)

×Erläuterung: Jede Zeile wurde abgearbeitet, aber der linke Ast ist offen. Folgt daraus, dassdie Formel nicht tautologisch ist? Nein! Denn obwohl jede Zeile mindestens einmal abgear-beitet wurde, können wir manche Zeilen (9, 10) noch einmal abarbeiten. Und tatsächlich: Indiesem Beispiel schließt der Baum, wenn man Zeile 9 noch einmal abarbeitet

1. ¬(¬∀y∃x(F ′xa ∧ ¬F ′ya) ∧ (∀xF ′xa→ ∃yF ′ya))✓

2. ¬¬∀y∃x(F ′xa ∧ ¬F ′ya) (1)✓9. ∀y∃x(F ′xa ∧ ¬F ′ya) (2) [a][b]

10. ∃x(F ′xa ∧ ¬F ′aa) (9) [b]11. F ′ba ∧ F ′aa (10)✓

12. F ′ba (11)13. F ′aa (11)

14. ∃x(F ′xa ∧ ¬F ′ba) (9) [c]15. F ′ca ∧ ¬F ′ba (14)✓

16. F ′ca (15)17. F ′ba (15)

×

3. ¬(∀xF ′xa→ ∃yF ′ya) (1)✓4. ∀xF ′xa (3) [a]5. ¬∃yF ′ya (3)✓6. ∀y¬F ′ya (5) [a]

7. F ′aa (4)8. ¬F ′aa (6)

×

Erläuterung: Nach dem zweiten Abarbeiten von Zeile 9 schließt der Baum. Dies beweist,dass die Formel tautologisch ist. Der Beispielbaum schließt nur, wenn der Allquantor inZeile 9 auf zwei Individuenkonstanten angewendet wird. Dies liegt daran, dass hier jeder derbeiden Quantoren nur auf ein Konjunkt „zugreift“.

Wichtig! Wenn ein Baum offen bleibt, hat man noch nichts bewiesen! Unter Umständen istder Baum nur deshalb offen geblieben, weil man ungeeignete Individuenkonstanten eingesetzthat oder diese in einer ungeeigneten Reihenfolge eingesetzt hat oder nicht oft genug eingesetzthat.

93


9.3. Interpretationen ablesen

9.3.1. Einleitung

Gegenbeispiele Bäume können helfen, ein Gegenbeispiel zu finden, das heißt

• eine Interpretation relativ zu der eine Formel falsch ist.

• eine Interpretation relativ zu der die Prämissen wahr sind, aber die Konklusion falsch.

.

9.3.2. Beispiele

9.3.2.1. Beispiel 1

Aufgabe Entwickle den Baum für die folgende prädikatenlogische Formel und lies ein Ge-genbeispiel ab, das heißt, gib eine Interpretation an, relativ zu der die Formel falsch ist!

∃x(Fx ∧Gx)→ ∀y(Fy → Gy)

(1) ¬(∃x(Fx ∧Gx)→ ∀y(Fy → Gy))✓(2) ∃x(Fx ∧Gx) (1)[a](3) ¬∀y(Fy → Gy) (1)✓(4) ∃y¬(Fy → Gy) (3)[b]

(5) Fa ∧Ga (2)✓(6) ¬(Fb→ Gb) (4)✓

(7) Fa (5)(8) Ga (5)(9) Fb (6)

(10) ¬Gb (6)Gegenbeispiel: kann aus den Zeilen 7 bis 10 abgelesen werden:

I(a) = 1, I(b) = 2, I(F ) = {1,2}, I(G) = {1},D = {1,2}

Hinweis: Für das Gegenbeispiel sind die Angaben I(a) = 1 und I(b) = 2 streng genom-men entbehrlich, da in der Formel (siehe Aufgabenstellung) gar keine Individuenkonstantenvorkommen. Es ist aber dennoch nützlich, diese Angaben zu notieren, damit das Beispielleichter nachvollzogen werden kann.

9.3.2.2. Beispiel 2

Aufgabe Entwickle den Baum für das folgende prädikatenlogische Argument und lies einGegenbeispiel ab, das heißt, gib eine Interpretation an, relativ zu der die Formel falsch ist!

∀x(Fx→ Gx)

Ga

94


∴¬Fa

(1) ∀x(Fx→ Gx) [a](2) Ga

(3) ¬¬Fa✓(4) Fa (3)

(5) Fa→ Ga (1)✓

(6) ¬Fa (5)×

(7) Ga (5)

Gegenbeispiel: kann aus den Zeilen 2, 4 und 7 abgelesen werden:

I(a) = 1, I(F ) = {1}, I(G) = {1},D = {1}

9.3.2.3. Vorgehen

Rezept zum Ablesen von Gegenbeispielen: Anwendbar auf die meisten Bäume, diesich nach einmaliger Entwicklung der entwickelbaren Zeilen ergeben.

1. Wähle einen offenen Ast des betrachteten Baumes aus.

2. Kennzeichne die Zeilen dieses Astes, die eine atomare Formel oder die Negation eineratomaren Formel enthalten.

3. Erstelle unter dem offenen Baum eine Liste, der zu interpretierenden Individuenkon-stanten und Prädikate. Interpretiert werden müssen alle Individuenkonstanten undPrädikate (mindestens die, die in der Wurzel vorgenommen). Außerdem muss ein Ge-genstandsbereich angegeben werden.

4. Auswertung der markierten Zeilen:

• Wenn in einer markierten Zeile Θα steht, ordne α einen Gegenstand zu und fügedenselben Gegenstand der Menge, die Θ zugeordnet wird, hinzu. (Analoges giltfür zwei- und mehr-stellige Prädikate.)

• Wenn in einer markierten Zeilen ¬Θα steht, ordne α einen Gegenstand zu und fügedenselben Gegenstand nicht der Menge, die Θ zugeordnet wird, hinzu. (Analogesgilt für zwei- und mehr-stellige Prädikate.)

• Beachte: Du kannst den Individuenkonstante denselben oder verschiedene Gegen-stände zuordnen.

5. Gib einen Gegenstandsbereich an, in den alle für die Interpretation verwendeten Ge-genstände aufgenommen werden.

6. Überprüfe, ob die erstellte Interpretation wirklich ein Gegenbeispiel liefert.

95

10. Prädikatenlogik: Erweiterung umIdentität

10.1. Motivation

PL= Erweiterung der PL um das Identitätszeichen „=“.

Warum machen wir das?

1. Es gibt folgerichtige Argumente, von denen wir in der PL (ohne Identität) nicht zeigenkönnen, dass sie folgerichtig sind.

2. Es gibt Ausdrücke (nämlich Kennzeichnungen), deren logische Form wir ohne Identitätnicht richtig analysieren können.

Beispiel 1

(1) Mary Anne Evans ist George Eliot. (F ′ab versus a = b)

(2) Mary Anne Evans ist weiblich. (Ga)

(3) George Eliot ist weiblich. (Gb)

Folgerichtig?

• In der PL ohne Identität ist dieses Argument nicht folgerichtig.

• In der PL mit Identität ist dieses Argument folgerichtig.

Funktionen von „sein“

1. Prädikation (z. B. „Sokrates ist sterblich“)

2. Identität (z. B. „Mary Anne Evans ist George Eliot“)

3. Existenz (z. B. „Gott ist“)

4. Wahrheit (z. B. „Er hat schon wieder nicht angerufen – Das kann doch nicht sein!“)

(3. und 4. kommen im Deutschen selten vor.)

96

10. Prädikatenlogik: Erweiterung um Identität

Beispiel 2 (Kennzeichnungen, Russells Beispiel) Der gegenwärtige König von Frankreichist kahl.

Kennzeichnungen Ausdrücke wie „der/die/das F“ sind Kennzeichnungen. (Bsp. „der ge-genwärtige König von Frankreich“, „der Besitzer des DEZ“, „die größte Stadt“.)

Warum sich Kennzeichnungen ohne Identität nicht wiedergeben lassen

• Gb ist eine schlechte Formalisierung, da Individuenkonstanten immer für etwas stehen,es aber keinen König von Frankreich gibt.

• ∀x(F ′xa → Gx) ist eine schlechte Formalisierung, da dies auch dann wahr ist, wennes keinen König von Frankreich gibt.

Russells Analyse (aus: „On Denoting“, 1905) Der gegenwärtige König von Frankreich istkahl. ⇔

1. Es gibt mindestens einen König von Frankreich und

2. Es gibt höchstens einen König von Frankreich und

3. Alle Könige von Frankreich sind kahl.

Formalisierung F’: . . . ist König von . . .G: . . . ist kahla: Frankreich

∃x((F ′xa ∧ ∀y(F ′ya→ x = y)) ∧Gx)

10.2. Syntax, Semantik, Kalkül

10.2.1. Syntax

Wir ergänzen die Definition einer atomaren (prädikatenlogischen) Formel um die zweiteBedingung:

Atomare Formel Eine Zeichenkette ist eine atomare Formel genau dann, wenn

• sie aus einem n-stelligen Prädikat gefolgt von genau n Individuensymbolen bestehtoder

• sie aus einem Individuensymbol gefolgt von dem Identitätszeichen gefolgt von einemIndividuensymbol besteht.

Klammern Zur besseren Lesbarkeit dürfen Klammern verwendet werden, das heißt: Wennα und β Individuensymbole sind, dann sind sowohl α = β als auch (α = β) Formeln. Statt¬(α = β) oder ¬α = β darf auch α ≠ β geschrieben werden.

97


10.2.2. Semantik

Semantik von „=“

• Informell: a = b ist wahr genau dann, wenn „a“ und „b“ für denselben Gegenstandstehen.

• Formal: BI(α = β) =W genau dann, wenn I(α) = I(β), sonst BI(α = β) = F

10.2.3. Kalkül

Neue Regeln Auch für die Identität brauchen wir zwei neue Regeln, die jedoch etwasanders aussehen als die bekannten Regeln: Wir nennen sie „Identität I“ und „Identität II“.

Identität I β = γΦ↓

Φ[β∣γ]Beliebig viele Vorkommnisse der Konstante β (bzw. γ) in Φ werden durch γ (bzw. β) ersetzt.

Besonderheit dieser Regel: Die Regel wird auf zwei vorherige Zeilen angewendet.

Beispiel ⋮(1) Fa→ Ga

(2) a = b(3) Fb→ Gb (1,2)

⋮

Nicht abhaken! Keine der beiden Zeilen, auf die die Regel angewendet wurde, wird abge-hakt!

Identität II ⋅↓

β = ββ ist eine beliebige Konstante.

Besonderheit dieser Regel: Die Regel wird auf keine vorherige Zeile angewendet. Sieerlaubt es an beliebiger Stelle – egal, was vorher im Baum steht – Zeilen wie a = a einzufügen.

Beispiel ⋮(1) ∃x¬(x = x) [a]

(2) ¬(a = a)(3) a = a (Id)

×Dürfte man in Zeile (3) nicht die Trivialität a = a hinzufügen, würde der Baum nicht schlie-ßen.

98


Nicht abhaken! Da die Regel nicht auf eine vorherige Zeile angewendet wird, kann nichtsabgehakt werden. Statt in Klammern die Zeile anzugeben, aus der die neue Zeile herkommt,notieren wir „(Id)“.

10.3. Beispiele Baumkalkül

10.3.0.1. Beispiel 1

Aufgabe: Zeige, dass die folgende Formel tautologisch ist!

∀x∀y(x = y → y = x)

(1) ¬∀x∀y(x = y → y = x)✓(2) ∃x¬∀y(x = y → y = x) (1)[a](3) ¬∀y(a = y → y = a) (2)✓(4) ∃y¬(a = y → y = a) (3)[b](5) ¬(a = b→ b = a) (4)✓

(6) a = b (5)(7) ¬(b = a) (5)(8) ¬(b = b) (6,7)

(9) b = b (Id)×

Ergebnis: Die Formel ist tautologisch.


Aufgabe: Zeige, dass die folgende Formel tautologisch ist!

∀x∀y∀z((x = y ∧ y = z)→ x = z)

(1) ¬∀x∀y∀z((x = y ∧ y = z)→ x = z)✓(2) ∃x¬∀y∀z((x = y ∧ y = z)→ x = z) (1)[a](3) ¬∀y∀z((a = y ∧ y = z)→ a = z) (2)✓(4) ∃y¬∀z((a = y ∧ y = z)→ a = z) (3)[b](5) ¬∀z((a = b ∧ b = z)→ a = z) (4)✓(6) ∃z¬((a = b ∧ b = z)→ a = z) (5)[c](7) ¬((a = b ∧ b = c)→ a = c) (4)✓

(8) a = b ∧ b = c (7)✓(9) ¬(a = c) (7)(10 a = b (8)(11) b = c (10)

(12) ¬(b = c)(9,10)×

Ergebnis: Die Formel ist tautologisch.

99


10.4. Beispielsätze

10.4.1. Weitere Bespiele

Erstes Beispiel

• Alle Amberger außer Anton angeln.

• ∀x((F ′xa ∧ x ≠ a)→ Gx)

Zweites Beispiel

• Es gibt einen Mensch, der Anton mag, aber das ist nicht Beate.

• ∃x(F ′xa ∧ x ≠ b)

100

11. Prädikatenlogik: Ergänzungen

11.1. *PL erster Stufe vs. höherer Stufe

PL erster Stufe Die PL, die wir kennen gelernt haben, heißt auch: Prädikatenlogik ersterStufe mit Identität. Was bedeutet das und was wären Alternativen?

Beobachtung Bei den Individuensymbolen haben wir zwischen Individuenkonstanten und-variablen unterschieden, bei den Prädikatsymbolen aber nicht.

PL höherer Stufe Es gibt Prädikatkonstanten (F,G,H usw.) und -variablen (X,Y,Z usw.)

Beispiel 1

(1) Anna hat dunkle Haare. Fa

(2) Ben hat dunkle Haare. Fb

(3) Also: Anna und Ben haben etwas gemeinsam. ∃X(Xa ∧Xb)

Beispiel 2 Prinzip der Identität des Ununterscheidbaren:

∀X∀y∀z((Xy↔Xz)→ y = z)

Nachteile der PL zweiter Stufe

1. Nicht vollständig

2. Verhältnis Logik–Mengenlehre wird verwischt

3. Anfälligkeit für Paradoxien der Mengenlehre

11.2. *Korrektheit, Vollständigkeit, Entscheidbarkeit

11.2.1. Übersicht Korrektheit, Vollständigkeit, Entscheidbarkeit

Korrektheit, Vollständigkeit, Entscheidbarkeit

korrekt vollständig entscheidbar

AL ✓ ✓ ✓PL ✓ ✓ ×PL 2. Stufe ✓ × ×

101


Beweise Für diese Umstände gibt es Beweise! Siehe dazu mehr in Kap. 14.

11.2.2. Entscheidbarkeit

Definition Entscheidbarkeit Ein logisches System ist entscheidbar genau dann, wenn eseinen Kalkül gibt, der in endlich vielen Schritten für jedes Argument eine Entscheidungliefert, ob dieses Argument folgerichtig ist.

Warum ist die Prädikatenlogik nicht entscheidbar?

• Die Regeln für die Quantoren können unendlich oft angewendet werden, da es immerunendlich viele Individuenkonstanten gibt, die eingesetzt werden können. Es gibt daherÄste, die nicht schließen, auf die jedoch weiterhin Regeln angewendet werden können.

• Wenn man die „falsche“ Individuenkonstante einsetzt, schließt der Ast nicht.

• Wenn man die Zeilen in der „falschen“ Reihenfolge abarbeitet, schließt der Ast nicht.

Konsequenzen I

• Wenn ein Baum geschlossen ist, dann heißt das:

– Die Negation der Wurzel ist eine Tautologie bzw.

– Das untersuchte Argument ist folgerichtig.

• Wenn ein Baum nicht geschlossen ist, dann heißt das nicht:

– Die untersuchte Formel ist nicht tautologisch bzw.

– Das untersuchte Argument ist nicht folgerichtig.

Konsequenzen II

• Wenn man zeigen will, dass eine Formel kontingent ist, muss man eine Interpretationangeben, relativ zu der die Formel wahr ist, und eine Interpretation, relativ zu der dieFormel falsch ist.

• Wenn man zeigen will, dass ein Argument nicht folgerichtig ist, muss man eine Inter-pretation angeben, relativ zu der die Prämissen wahr sind und die Konklusion falsch.

11.3. Beziehungen zwischen Formeln

Ein Paar von Formeln

• . . . kann logisch unabhängig sein.

• . . . kann äquivalent sein.

• . . . kann gegensätzlich sein.

102


Definition 36 (Äquivalenz). Zwei Formeln sind Φ und Ψ sind äquivalent genau dann,wenn es unmöglich ist, dass sie verschiedene Wahrheitswerte haben. Das heißt: Φ ↔ Ψ isttautologisch.

Definition 37 (Kontradiktorisches Gegenteil). Zwei Formeln sind Φ und Ψ sindkontradiktorisch genau dann, wenn es unmöglich ist, dass sie denselben Wahrheitswerthaben. Das heißt: Φ↔ Ψ ist kontradiktorisch.

Definition 38 (Konträres Gegenteil). Zwei Formeln Φ und Ψ sind konträr genaudann, wenn es unmöglich ist, dass beide wahr sind (höchstens eine Formel ist wahr). Dasheißt: Φ ∧Ψ ist kontradiktorisch.

Definition 39 (Subkonträres Gegenteil). Zwei Formeln Φ und Ψ sind subkonträrgenau dann, wenn es unmöglich ist, dass beide falsch sind (mindestens eine Formel ist wahr).Das heißt: ¬Φ ∧ ¬Ψ ist kontradiktorisch.

Beispiele

• ∀xFx und ¬∃x¬Fx sind äquivalent.

• ∀xFx und ¬∀xFx sind kontradiktorisch.

• ∀xFx und ¬∃xFx sind konträr. (Wenn es sowohl Fs als auch Nicht-Fs gibt, sind beidefalsch.)

• ∃xFx und ¬∀xFx sind subkonträr. (Wenn es sowohl Fs als auch Nicht-Fs gibt, sindbeide wahr.)

11.4. Notwendige und hinreichende Bedingungen

Eine Anwendung der PL Man kann definieren, was notwendige und hinreichende Bedin-gungen sind.

Beispiele

• Männlich zu sein ist notwendig (aber nicht hinreichend) dafür, ein Erpel zu sein.

• Ein Erpel zu sein ist hinreichend (aber nicht notwendig) dafür, eine Ente zu sein.

• Eine männliche Ente zu sein ist hinreichend und notwendig dafür, ein Erpel zu sein.

Beispiele aus der Philosophie

• Selbstbewusstsein ist notwendig für Bewusstsein.

• Wahrheit ist notwendig für Wissen.

• Unwissenheit ist hinreichend für fehlende Verantwortung.

103


Definition 40 (Notwendige Bedingung). Dass x A ist, ist eine notwendige Bedingungdafür, dass x B ist, genau dann, wenn

∀x(Bx→ Ax)

Definition 41 (Hinreichende Bedingung). Dass x A ist, ist eine hinreichende Bedin-gung dafür, dass x B ist, genau dann, wenn

∀x(Ax→ Bx)

Definition 42 (Notwendige und hinreichende Bedingung). Dass x A ist, ist einenotwendige und hinreichende Bedingung dafür, dass x B ist, genau dann, wenn

∀x(Ax↔ Bx)

Beispiele

• Männlich zu sein (F) ist notwendig (aber nicht hinreichend) dafür, ein Erpel zu sein(G). = ∀x(Gx→ Fx)

• Ein Erpel zu sein (G) ist hinreichend (aber nicht notwendig) dafür, eine Ente zu sein(H). = ∀x(Gx→Hx)

• Eine männliche (F) Ente (H) zu sein ist hinreichend und notwendig dafür, ein Erpelzu sein (G). = ∀x((Fx ∧Hx)↔ Gx)


• Selbstbewusstsein ist notwendig für Bewusstsein.

∀x(x hat Bewusstsein→ x hat Selbstbewusstsein)

• Unwissenheit ist hinreichend für fehlende Verantwortung.

∀x(¬(x weiß, was x tut)

→ ¬(x ist verantwortlich für die Handlung))

104

Teil III.

Weiterführendes

105

12. *Modallogik

12.1. Wozu Modallogik?

Einleitung Das Folgende ist eine ultraknappe Einführung in die Philosophie und Logik vonMöglichkeit und Notwendigkeit. Im ersten Teil werden einige begriffliche Unterscheidungenrund um Möglichkeit und Notwendigkeit eingeführt, im zweiten Teil wird in die Modallogik(nur Erweiterung der AL) eingeführt.

Allgemeines In Logikeinführungen entsteht oft der Eindruck, es gebe nur eine Logik, näm-lich die Prädikatenlogik erster Stufe mit oder ohne Identität (PL) plus die Aussagenlogik(AL) als propädeutische Vorstufe. Beides zusammen wird oft „klassische Logik“ genannt.Tatsächlich ist jedoch die PL nur ein logisches System unter vielen. Es gibt PL zweiter Stu-fe (man kann auch an die Stelle von Prädikatkonstanten hineinquantifizieren), mehrwertigeLogik (mehr als zwei Wahrheitswerte), Relevanzlogik (nicht jedes Konditional mit falschemVordersatz ist wahr), parakonsistente Logik (manche Widersprüche sind wahr), intuitionis-tische Logik (ohne tertium non datur und Doppelte-Negation-Elimination) usw. usf. WelcheLogik die „richtige“ ist, wird in der Gegenwartsphilosophie heiß diskutiert.

Erweiterungen vs. Revisionen Manche nicht-klassischen Logiken sind Erweiterungen derklassischen Logik, d. h. jedes Argument, das in der klassischen Logik folgerichtig ist, ist auchin der erweiterten Logik folgerichtig. Die Modallogik ist eine Erweiterung der klassischenLogik. Viele der eben genannten Logiken sind jedoch echte Alternativen zur klassischenLogik, d. h. mind. ein Argument, das in der klassischen Logik folgerichtig ist, ist in ihnennicht folgerichtig.

Intuitiv folgerichtige Argumente Wir haben den Übergang von der Aussagenlogik zurPrädikatenlogik wie folgt motiviert: Das Argument

(1) Sokrates ist ein Mensch.

(2) Alle Menschen sind sterblich.

(3) ∴ Sokrates ist sterblich

ist nicht aussagenlogisch folgerichtig. Intuitiv handelt es sich jedoch um eine folgerichtigesArgument. Um dieser Intuition gerecht zu werden, wird die Prädikatenlogik entwickelt.

Intuitiv folgerichtige Argumente mit Modalausdrücken Das Argument

(1) Der FC Liverpool hat 2005 das Champions League Finale gewonnen, nachdemer zur Halbzeit 0:3 zurücklag.

106

12. *Modallogik

(2) ∴ Es ist möglich, dass jemand ein Finale gewinnt, nachdem er zur Halbzeit0:3 zurückliegt.

ist nicht prädikatenlogisch folgerichtig. Intuitiv handelt es sich jedoch um ein folgerichtigesArgument. Um dieser Intuition gerecht zu werden, wird die Modallogik entwickelt.

12.2. Notwendigkeit und Möglichkeit

12.2.1. Arten von Möglichkeit und Notwendigkeit

Übersicht In Kap. 1 haben wir bereits einige Arten von Möglichkeit und Notwendigkeitkennengelernt:

• Logische Möglichkeit

• Begriffliche Möglichkeit

• Naturgesetzliche Möglichkeit

Außerdem gibt es (mind.) noch:

• Metaphysische Möglichkeit

• Epistemische Möglichkeit

• Deontische Möglichkeit

Logische Möglichkeit und Notwendigkeit Wenn man sagt „Wenn P wahr ist und P → Qwahr ist, dann muss auch Q“, dann ist das „müssen“ im Sinne logischer Notwendigkeit zuverstehen. Es ist logisch unmöglich, dass die beiden Prämissen (P ; P → Q) wahr sind, aberdie Konklusion (P ) falsch.

Begriffliche (oder analytische) Möglichkeit und Notwendigkeit Wenn man sagt „WennGordon ein Junggeselle ist, dann muss er unverheiratet sein“, dann ist „müssen“ im Sinnebegrifflicher Notwendigkeit zu verstehen. So wie es sich mit dem Begriff des Junggesellenverhält, gibt es keine unverheirateten Junggesellen und kann es auch keine geben.

Naturgesetzliche (nomologische, physikalische) Möglichkeit und Notwendigkeit Wennman sagt „Nichts kann sich schneller als mit Lichtgeschwindigkeit bewegen“, dann ist „kön-nen“ im Sinne naturgesetzlicher Möglichkeit zu verstehen. So wie die Naturgesetze nun malsind, würde ein Gegenstand, der sich schneller als Lichtgeschwindigkeit bewegt, ein Natur-gesetz verletzen.

107

12. *Modallogik

Metaphysische Möglichkeit und Notwendigkeit Wenn man sagt „Sinje könnte nicht eineAmeise sein“, dann ist „nicht können“ im Sinne metaphysischer Unmöglichkeit zu verstehen.Eine wichtige Klasse metaphysischer Notwendigkeiten betrifft essentielle Eigenschaften, d. h.Eigenschaften, die ein Gegenstand nicht verlieren kann, ohne aufzuhören dieser Gegenstandzu sein. Sinje könnte ein paar Zentimeter größer oder kleiner sein, aber die Eigenschaft,ein Mensch zu sein, kann sie nicht verlieren. Oft wird ein enger Zusammenhang zwischenmetaphysischer Möglichkeit und Vorstellbarkeit/Denkbarkeit (conceiveability) angenommen.Alles, was irgendwie denkbar ist, ist metaphysisch möglich, und alles, was metaphysischmöglich ist, ist irgendwie denkbar.

Epistemische Möglichkeit und Notwendigkeit Der Zeuge vor Gericht sagt „Es kann sein,dass sie dem Angeklagten das Geld zugesteckt hat“. Hier geht es um epistemische Möglich-keit: Es ist mit allem, was der Zeuge weiß, mit allen seinen Wahrnehmungen und sonstigenAnhaltspunkten vereinbar, dass sie ihm das Geld zugesteckt hat. Epistemische Möglichkeitist immer relativ zu einem Stand des Wissens oder einer Menge an Evidenzen. Ein ande-rer kann vielleicht ausschließen, dass sie ihm das Geld zugesteckt hat. Was für den einenepistemisch möglich ist, muss dies nicht für einen anderen sein.

Deontische Möglichkeit und Notwendigkeit Wenn man sagt „Du musst ihr das Geldzurückgeben“, dann ist „müssen“ im Sinne deontischer Notwendigkeit zu verstehen. Es istgefordert, eine moralische Verpflichtung, eine praktische Notwendigkeit, das Geld zurückzu-geben.

Ergebnis Es gibt viele verschiedene Arten von Möglichkeit und Notwendigkeit. Die ver-schiedenen Varianten der Modallogik dienen dazu, unterschiedlichen Arten von Möglichkeiteinzufangen.

12.2.2. Übungsaufgabe

Um welche Art von Möglichkeit bzw. Notwendigkeit geht es jeweils?

1. Es ist möglich, dass sich meine Eltern nie getroffen haben/hätten.

2. Es ist möglich, mehr als 9m weit zu springen.

3. Der Schlüssel könnte unter dem Sofa liegen.

4. Es ist notwendig, dass der Gewinner der Tour de France radfahren kann.

5. Wenn du jonglieren lernen willst, musst du üben.

6. Wenn Ben ein Junggeselle ist, dann muss er unverheiratet sein.

7. Man kann nur Wahres wissen.

8. Ich könnte einen eineiigen Zwillingsbruder haben.

9. Es könnte sein, dass alle Katzen gut getarnte Roboter sind.

108

12. *Modallogik

12.2.3. Einige Erläuterungen

Terminologie Notwendigkeit und Möglichkeit nennt man auch „Modalitäten“. Der Aus-druck kommt aus der klassischen Urteilslehre, der zufolge jedes Urteil die Form ⟨S ist P⟩hat und außerdem eine Qualität (bejahend, verneinend), eine Quantität (alle, einige, dieses)und eben auch eine Modalität (wirklich, möglich, notwendig) hat.

Kontingent. Neben „möglich“ und „notwendig“ wird oft auch „kontingent“ verwendet. Esist kontingent, dass P, wenn es möglich ist, dass P, und es möglich ist, dass nicht P.

Intensionaler Kontext „Normalerweise“ kann man jeden Ausdruck durch einen ko-referen-tiellen Ausdruck ersetzen, ohne dass sich der Wahrheitswert des Satzes ändert (Substitu-ierbarkeit salva veritate). Liegt Substituierbarkeit salva veritate vor, spricht man auch voneinem extensionalen Kontext. Ein Beispiel:

1. 16 ist durch 4 teilbar. (wahr)

2. Die Anzahl der deutschen Bundesländer ist durch 4 teilbar. (wahr; ergibt sich durchErsetzen von „16“ durch den ko-referentiellen Ausdruck „die Anzahl der deutschenBundesländer“)

Intensionaler Kontext (Forts.) Gleiches gilt für „Es ist notwendig, dass. . . “ und „Es istmöglich, dass. . . “ nicht.

1. Es ist notwendig, dass 16 durch 4 teilbar ist. (wahr)

2. Es ist notwendig, dass die Anzahl der deutschen Bundesländer durch 4 teilbar ist.(falsch; es ist möglich, dass Deutschland aus 15 Bundesländern besteht und 15 istnicht durch 4 teilbar)

„Es ist notwendig, dass. . . “ erzeugt einen intensionalen Kontext. An der Stelle der Pünktchendürfen Ausdrücke nicht einfach so durch ko-referentielle Ausdrücke ersetzt werden.

De re und de dicto. Hätte der Gewinner der Präsidentenwahl 2009 die Präsidentenwahl2009 auch verlieren können? Einerseits ja, andererseits nein. Dass wer auch immer die Präsi-dentenwahl 2009 gewinnt, die Präsidentenwahl 2009 gewinnt, ist logisch und begrifflich wahr.Dies ist die de dicto-Lesart des Beispiels. Aber dass von dem Gewinner der Präsidentenwahl2009 – d. h. Horst Köhler – gilt, dass er die Wahl auch hätte verlieren können, ist ebenfallswahr. Dies ist die de re-Lesart des Beispiels.

Possibilia Bisher ging es um Eigenschaften existierender Gegenstände. Ein eigenes Themasind nicht existierende, bloß mögliche Gegenstände, sog. Possibilia. Kant hatte keine Kinder.Es ist möglich, dass Kant Kinder gehabt hätte. Aber gibt es auch mögliche Kinder Kants?Falls ja, handelt es sich bei ihnen um sog. Possibilia.

109

12. *Modallogik

12.3. Syntax, Semantik, Kalkül

12.3.1. Syntax

Symbole Es werden zwei neue Symbole eingeführt:

◊Φ – Es ist möglich, dass Φ (sog. Raute, engl. diamond)

◻Φ – Es ist notwendig, dass Φ (sog. Box, engl. box )

Die beiden Operatoren sind interdefinierbar:

◊Φ ≡ ¬ ◻ ¬Φ

◻Φ ≡ ¬◊¬Φ

Genau genommen würde es daher reichen, ein neues Zeichen einzuführen.

Rekursive Definition Die übliche rekursive Definition wird um eine Klausel ergänzt.

• Wenn Φ eine modallogische Formel ist, dann sind auch ◊Φ und ◻Φ modallogischeFormeln.

Beispiele für modallogische Formeln

• ◊(P ∧Q)

• ◻(P → Q)

• P → ◻Q

• P → ◻(¬Q ∨ P )

• ◊ ◻ P

• ◻ ◻ (P ∨ ¬P )

• ¬ ◻ P → ◻◊¬P

12.3.2. Semantik

Die Semantik der Aussagenlogik Eine Interpretation ordnet jeder atomaren Formel einenWahrheitswert zu. Der Wahrheitswert einer komplexen Formel ergibt sich dann aus denWahrheitswerten der Teilformeln. Beispiel:

BI(Φ ∧Ψ) =W genau dann, wenn I(Φ) =W und I(Ψ) =W

ansonsten I(Φ ∧Ψ) = F

110

12. *Modallogik

Die Semantik der Prädikatenlogik. Eine Interpretation I ordnet jeder Individuenkonstan-te einen Gegenstand aus dem Gegenstandsbereich zu, jeder einstelligen Prädikatkonstanteeine Teilmenge des Gegenstandsbereich, jeder zweistelligen Prädikatkonstante ein (geord-netes) Paar aus Elementen des Gegenstandsbereich usw. Fa ist wahr genau dann, wennI(a) ∈ I(F ); usw.

Die Semantik der Modallogik Für die Semantik der Modallogik brauchen wir mehr. DieGrundidee lässt sich am besten mittels Beispielen darstellen:

Es ist notwendig, dass ich eines Tages sterbe = In allen möglichen Welten werdeich eines Tages sterben.

Es ist möglich, dass ich morgen sterbe = Es gibt mind. eine mögliche Welt, inder ich morgen sterbe.

Warum ist das eine hilfreiche Idee? (1) Notwendigkeit können wir ähnlich zum Allquantor (inallen möglichen Welten), Möglichkeit ähnlich zum Existenzquantor (es gibt eine möglicheWelt) behandeln. (2) Worüber quantifiziert wird, ist jedoch etwas Neues: Der Gegenstands-bereich dieser Quantoren besteht aus möglichen Welten.

Was sind mögliche Welten? Diese Frage wird in der Philosophie heiß diskutiert. Um dieFrage diskutieren zu können, sollte man zunächst kennenlernen, wozu mögliche Welten inder Modallogik gebraucht werden. Deshalb hier nur einige Andeutungen: Eine mögliche Weltist eine Weise, wie die Welt sein könnte. Wir können uns ohne weiteres vorstellen, in welchenHinsichten die Welt anders sein könnte, als sie in Wirklichkeit ist: Ich könnte einen halbenZentimeter größer oder kleiner sein, Anwalt statt Philosoph usw.usf. Wenn einer sagt „Ichkönnte einen halben Zentimeter größer sein“, dann sagt er in etwa: Es gibt eine möglicheWelt, in der er einen halben Zentimeter größer ist.

Zugänglichkeitsrelation Es wird leider etwas komplizierter. Ein Beispiel: Heute ist es mög-lich, dass ich morgen ein Eis esse. Aber übermorgen ist es nicht mehr möglich, dass ich amvorherigen Tag ein Eis gegessen habe, wenn ich es nicht getan habe. Zu unterschiedlichenZeitpunkten sind unterschiedliche Propositionen (noch) möglich Es ist deshalb sinnvoll, nurrelativ zu einer Welt zu sagen, etwas sei möglich. Um diese Relativität einzufangen, führenwir eine Zugänglichkeitsrelation zwischen möglichen Welten ein:

w1Rw2 = von Welt 1 aus ist Welt 2 zugänglich bzw. möglich

Im Beispiel: Sei w0 die heutige Welt, w1 die mögliche Welt, in der ich morgen ein Eis esse,w2 die mögliche Welt, in der ich morgen kein Eis esse. Dann gilt w0Rw1 und w0Rw2, abernicht w1Rw2.

Zusammenfassung Eine modallogische Interpretation ist ein Tripel ⟨W,R,F ⟩, wobei Weine Menge von möglichen Welten ist, R eine Zugänglichkeitsrelation und F eine Funktion,die allen atomaren Formeln und Welten einen Wahrheitswert zuordnet.

111

12. *Modallogik

Diagramme Am einfachsten stellt man eine modallogische Interpretation mittels eines Dia-gramms dar. Hier ist ein Beispiel:

↷ ↷ ↷w0 → w1 ← w2

P ;¬Q ¬P ;Q ¬P ;¬QDie Pfeile symbolisieren die Zugänglichkeitsrelation. Unter den Bezeichnungen der Weltensteht (ausschnittsweise), was in ihnen der Fall ist. Dieses Diagramm können wir nun auswer-ten: Im Beispiel ist R reflexiv, nicht symmetrisch, nicht transitiv. In w0 gilt (zum Beispiel)P ∧◊¬P . In w1 gilt (zum Beispiel) ◻¬P . In w2 gilt (zum Beispiel) ◻¬P . In allen Welten gilt(zum Beispiel) ◻¬(P ∧Q).

12.3.3. Übungsaufgaben

Zeichne ein Weltendiagramm . . .

1. . . .mit mind. drei möglichen Weilten, die die folgende Bedingung erfüllen: In allenmöglichen Welten gilt ◻P .

2. . . . , das folgende Bedingungen erfüllt: In mind. einer möglichen Welt ist ¬◊P ∧ ◊◊Pwahr.

3. . . . , in dem jede Welt jeder Welt zugänglich ist und das ein Gegenbeispiel zu folgendemArgument ist:

(1) ◻(P → Q)(2) P

(3) ◻Q

12.3.4. Verschiedene modallogische Systeme

Warum überhaupt mehr als ein modallogisches System? Je nach, welchen Möglichkeits-begriff man einfangen will, stellt man verschiedene Anforderungen an die Zugänglichkeits-relation. Daraus ergeben sich verschiedene modallogische Systeme. Die Modallogik, die sichergibt, wenn man keinerlei Anforderungen an die Zugänglichkeitsrelation stellt, nennt manK.

Eigenschaften der Zugänglichkeitsrelation Je nach dem, welche Annahmen man über dieZugänglichkeitsrelation macht, erhält man verschiedene Modallogiken.

Reflexiv (ρ). ∀i ∶ wiRwiSymmetrisch (σ). ∀i,∀j ∶ wiRwj → wjRwi

Transitiv (τ). ∀i,∀j,∀k ∶ (wiRwj ∧wjRwk)→ wiRwk

Universell (υ). ∀i,∀j ∶ wiRwjDie Modallogik, deren Zugänglichkeitsrelation reflexiv ist, wird mit Kρ bezeichnet, die Mo-dallogik, deren Zugänglichkeitsrelation reflexiv und symmetrisch ist, mit Kρσ, usw.

112

12. *Modallogik

S4 und S5 Auf zwei modallogische Systeme stößt man in der Literatur immer wieder, dassind die sogenannten S4 und S5. Es gilt:

S4 =Kρτ

S5 =Kρστ =Kυ

Charakteristisch für diese Systeme sind:

(1) ◻A→ ◻ ◻A

(2) ¬ ◻A→ ◻¬ ◻A

In S4 ist (1), aber nicht (2) tautologisch, in S5 sind beide tautologisch.

12.3.5. Kalkül

Kalkül Um die Sache einfach zu halten, beschränken wir uns auf K und S5 = Kρστ = Kυ.Ich nenne jedoch alle Regeln, damit Sie einen Eindruck bekommen. Ganz am Ende findenSie eine Zusammenfassung für S5.

Erste Neuerung In jeder Zeile notieren wir zusätzlich, in welcher Welt die Zeile gelten soll(und zwar mit w0,w1 usw.). Das sieht z. B. so aus:

⋮(8) P ∧Q,w17

(9) P,w17 (8)(10) Q,w17 (8)

⋮

Zweite Neuerung Es gibt eine neue Art von Zeile. Wenn wir etwas über die Zugänglich-keitsrelation erfahren, notieren wir das wie folgt:

⋮(13) w3 r w4

⋮

Neue Regeln Außerdem brauchen wir noch zusätzliche Kalkülregeln für die Modalopera-toren ◊ und ◻. Es handelt sich dabei um Abwandlungen der Regeln für die Quantoren.

Regel für den Notwendigkeitsoperator ◻Φ,wiwi r wj↓

Φ,wj

113

12. *Modallogik

Regel für den Möglichkeitsoperator ◊Φ,wi↓

wi r wjΦ,wj

Wichtig: j muss hier neu sein, d. h. darf im Ast noch nicht vorkommen.

Regel für den negierten Notwendigkeitsoperator ¬ ◻Φ,wj↓

◊¬Φ,wj

Regel für den negierten Möglichkeitsoperator ¬◊Φ,wj↓

◻¬Φ,wj

Regel für Reflexivität ⋅↓

wi r wi

Regel für Symmetrie wi r wj↓

wj r wi

Regel für Transitivität wi r wjwj r wk↓

wi r wk

Besonderheiten S5 Da in S5 jeder Welt jede Welt zugänglich ist, können wir es uns sparendie Zugänglichkeitsrelation zu notieren. Außerdem ändert sich die Regel für den Notwendig-keitsoperator leicht.

Regel für den Notwendigkeitsoperator in S5 ◻Φ,wi↓

Φ,wj

Wichtig: j darf hier beliebig gewählt werden.

12.3.6. Übungen

Beispielaufgaben (siehe Tafel)

1. ⊢S5 ◊P → ◊◊P

2. ◊P ⊢S5 ◻◊P

3. ⊢S5 ◻(◻P → Q) ∨ ◻(◻Q→ ◻P )

114

12. *Modallogik

4. ◻(◊P → Q) ⊣⊢S5 ◻(P → ◻Q)

Literaturhinweise

Wer mehr über Modallogik erfahren will, sollte zu einem der Lehrbücher von Priest (be-sondere Empfehlung), Sider oder Burgess greifen. Wer mehr über mögliche Welten erfahrenwill, findet bei Read einen Einstieg. Literaturangaben finden sich in Anhang D.

115

13. *Andere Kalküle

13.1. Einleitung

Kalküle Wir haben bisher mit dem Baumkalkül gearbeitet, der besonders gut geeignet ist,um einen Einstieg in die Logik zu gewinnen. Tatsächlich wird in der Logik jedoch mit einerganzen Reihe von Kalkülen gearbeitet. Keiner dieser Kalküle kann beanspruchen, der einerichtige Kalkül zu sein. Für verschiedene Zwecke sind verschiedene Kalküle am zweckmä-ßigsten.

Zur Erinnerung: Was ist ein Kalkül? Kalkül = ein rein syntaktisch operierendes Systemvon Ableitungsregeln.

Vier Typen von logischen Kalkülen

• Axiomatischer Kalkül (Hilbert)

• Natürliches Schließen (natural deduction, Gentzen, Jaśkowski)

• Baumkalkül (semantic tableaux, Beth, Jeffrey, Smullyan)

• Sequenzenkalkül (sequent calculus, Gentzen)

Programm In diesem Kapitel werden zwei weitere Kalküle und ihre philosophische Rele-vanz vorgestellt: Axiomatischer Kalkül und Natürliches Schließen. Den Sequenzen-kalkül werden wir jedoch nicht betrachten. Er unterscheidet sich von den anderen Kalkülendadurch, dass in die Zeilen nicht Formeln sondern sog. Sequenzen geschrieben werden, dasheißt Zeichenketten der Form A1, . . . ,An ⊢ B1, . . . ,Bk.

13.2. Axiomatischer Kalkül

13.2.1. Der axiomatische Kalkül

Eigenschaften

• Wenige Regeln

• Erlaubt axiomatisches Nachdenken (Welches System ergibt sich, wenn ein Axiom weg-gelassen oder hinzugenommen wird?)

• Nähe zur Mathematik

116


Der axiomatische Kalkül wird auch Hilbertkalkül genannt.

Verwendete Junktoren Im axiomatischen Kalkül benutzt man als Junktoren nur → und¬. Alle anderen Junktoren werden mittels der folgenden Äquivalenzen eliminiert:

• (ϕ ∧ ψ) ≡ ¬(¬ϕ→ ψ)

• (ϕ ∨ ψ) ≡ (¬ϕ→ ψ)

• (ϕ↔ ψ) ≡ ((ϕ→ ψ)∧ (ψ → ϕ)) (∧ muss noch mittels der ersten Äquivalenz eliminiertwerden)

Einführungsregel Ein Axiom oder eine Prämisse darf in einer beliebigen Zeile eingeführtwerden.

Schlussregel (MP) Aus ϕ→ ψ und ϕ darf ψ geschlossen werden.

Axiome für AL (es gibt mehrere äquivalente Axiomatisierungen!)

A1 ϕ→ (ψ → ϕ)

A2 (ϕ→ (ψ → χ))→ ((ϕ→ ψ)→ (ϕ→ χ))

A3 (¬ψ → ¬ϕ)→ ((¬ψ → ϕ)→ ψ)

Erläuterung zu den Axiomen Bei den Axiomen handelt es sich genau genommen umAxiomenschemata, d. h. jede Formel, die man durch uniforme Einsetzungen für ϕ,ψ,χ erhält,ist ein Axiom. Beachte: Man darf auch die gleiche Formel für ϕ und ψ (und χ) einsetzen.

Beispiele

• P → (Q→ P ) ist eine Instanz von A1

• P → (P → P ) ist eine Instanz von A1

• ¬P → (¬¬¬Q→ ¬P ) ist eine Instanz von A1

• ((P → ¬Q) → (¬P → ¬Q)) → (((P → ¬Q) → ¬P ) → ((P → ¬Q) → ¬Q)) ist eineInstanz von A2

13.2.2. Beispiele

Erstes Beispiel Beweise ⊢ (P → Q)→ (P → P )!1. P → (Q→ P ) A1

2. P → (Q→ P ))→ ((P → Q)→ (P → P )) A2

3. (P → Q)→ (P → P ) MP 1,2

117


Zweites Beispiel Beweise ⊢ (R → P )→ (R → (Q→ P ))!1. (R → (P → (Q→ P )))→ ((R → P )→ (R → (Q→ P ))) A2

2. P → (Q→ P ) A1

3. [P → (Q→ P )]→ [R → (P → (Q→ P ))] A1

4. R → (P → (Q→ P )) MP 2,3

5. (R → P )→ (R → (Q→ P )) MP 1,4

13.2.3. Diskussion

Merke Der axiomatische Kalkül ist hilfreich, um über ein logisches System (z. B. AL oderPL) zu reden, aber nicht sonderlich hilfreich, um in einem logischen System Beweise zuführen.

Intuitionistische Logik Die intuitionistische Logik (in der tertium non datur und doppelteNegationselimation nicht gelten) erhält man, wenn das dritte Axiom durch das folgendeAxiom ersetzt:

¬ϕ→ (ϕ→ ψ)

13.3. Natürliches Schließen

13.3.1. Einleitung

Die Rolle von Annahmen Argumentieren in Alltag und Wissenschaften kommt nicht ohneAnnahmen aus. Diese können im Baumkalkül nicht gut eingefangen werden.

Beispiele aus der Mathematik I Angenommen es gibt nur endlich viele Primzahlen. Dannbilden wir das Produkt alles Primzahlen und. . . Das ist ein Widerspruch. Also ist die An-nahme falsch und es muss unendlich viele Primzahlen geben. (Widerspruchsbeweis, reductioad absurdum)

Beispiele aus der Mathematik II Gibt es irratinale Zahlen a und b, so dass ab rational ist?√

2

√2ist entweder rational oder irrational. Falls rational, haben wir die gesuchten Zahlen a

und b bereits gefunden. Falls irrational, setze a =√

2

√2und b =

√2. Da

ab = (√

2

√2)√

2

=√

2

√2√2 =

√22 = 2

ist ab rational. (Beweis per Fallunterscheidung)

Das philosophisch Interessante an diesem Beweis ist, dass man zeigt, dass es zwei Zahlenmit einer gewünschten Eigenschaft gibt, ohne dass man herausbekommt, welche Zahlen dieseEigenschaft haben.

118



1. Angenommen Wissen wäre wahre Meinung. Dann könnte ich die Lottozahlen wissen,indem ich richtig rate. Das ist absurd. Also ist die Annahme falsch und Wissen istmehr als wahre Meinung. (Widerspruchsbeweis, reductio ad absurdum)

2. Kann ich wissen, ob ich jetzt gerade träume? Entweder gibt es einen Wachheitstest(Kneifen?) oder nicht. Wenn es keinen gibt, kann ich offensichtlich nicht wissen, ob ichträume. Wenn es einen gibt, kann ich nicht wissen, ob ich die Durchführung des Testsnur geträumt habe. Also kann ich nicht wissen, ob ich jetzt träume. (Argument perFallunterscheidung)

13.3.2. Natürliches Schließen

13.3.2.1. Aufbau der Beweise

Darstellungsformen In der Literatur finden sich drei Darstellungsformen fürs NatürlicheSchließen, der Gentzen-Stil (zweidimensionale Darstellung), der Lemmon-Stil (eindimensio-nale Darstellung) und der Fitch-Stil (Kompromiss mit Strichen am linken Rand). Wir schau-en uns nur den Fitch-Stil an.

Schreibweise

• Alle Zeilen werden durchnummeriert. Rechts neben der Formel wird angegeben, woherdie Zeile kommt (Nennung der Regel plus Zeile(n), auf die sie angewendet wurde).

• Prämissen (falls vorhanden) werden in die ersten Zeilen geschrieben.

• Konklusion ist das, was in der letzten Zeile steht.

• Prämissen und Annahmen werden durch kleine horizontale Striche abgegrenzt. AlleÜberlegungen, die unter einer bestimmten Annahme stehen, werden durch lange ver-tikale Striche als zusammengehörig markiert.

13.3.2.2. Regeln

Art der Regeln

• Für jeden Junktor und Quantor gibt es zwei Regeln, nämlich eine Einführungsregel(introduction) und eine Beseitigungsregel (elimination).

• Da es auch Einführungsregeln gibt, werden die Formeln im Laufe des Beweises nichtzwingend kürzer. Beweise im Natürlichen Schließen können daher (auch in der AL)immer weiter fortgesetzt werden.

• Die Auswahl der anzuwendenden Regel ist (anders als bei Bäumen) nicht mechanisch;man braucht oft Einsicht oder Intuition, wie der Beweis aufzubauen ist.

119


13.3.2.3. Regeln Negation I

¬-Beseitigung

¬¬Φ

⋮

Φ

13.3.2.4. Regeln Negation II

¬-Einführung

Φ

⋮

¬Φ oder: Ψ ∧ ¬Ψ

¬Φ

13.3.2.5. Regeln Konjunktion I

∧-Beseitigung

Φ ∧Ψ

⋮

Φ

Ψ

13.3.2.6. Regeln Konjunktion II

∧-Einführung

Φ

⋮

Ψ

⋮

Φ ∧Ψ

13.3.2.7. Regeln Disjunktion I

∨-Beseitigung

Φ ∨Ψ

Φ

⋮

χ

Ψ

⋮

χ

χ

13.3.2.8. Regeln Disjunktion II

∨-Einführung

Φ

⋮

Φ ∨Ψ oder: Ψ ∨Φ

120


13.3.2.9. Regeln Konditional I

→-Beseitigung

Φ→ Ψ

⋮

Φ

⋮

Ψ

13.3.2.10. Regeln Konditional II

→-Einführung

Φ

⋮

Ψ

Φ→ Ψ

13.3.3. Beispiele

Erstes Beispiel (Beweis per Fallunterscheidung) (P ∧Q) ∨ (R ∧ S) ⊢ Q ∨ S

1 (P ∧Q) ∨ (R ∧ S) Prämisse

2 P ∧Q Annahme

3 P ∧-Bes. 2

4 Q ∧-Bes. 2

5 Q ∨ S ∨-Einf. 4

6 R ∧ S Annahme

7 R ∧-Bes. 6

8 S ∧-Bes. 6

9 Q ∨ S ∨-Einf. 8

10 Q ∨ S ∨-Bes. 5, 9

Zweites Beispiel (Einführung Konditional) (P ∨ ¬Q)→ R ⊢ P → R

1 (P ∨ ¬Q)→ R Prämisse

2 P Annahme

3 P ∨ ¬Q ∨-Einf. 2

4 R →-Bes. 3

5 P → R →-Einf. 4

121


Drittes Beispiel (Widerspruchsbeweis) ⊢ ¬((P ∧Q) ∧ ¬P )

1 ((P ∧Q) ∧ ¬P ) Annahme

2 P ∧Q ∧-Bes. 1

3 ¬P ∧-Bes. 1

4 P ∧-Bes. 2

5 Q ∧-Bes. 1

6 P ∧ ¬P ∧-Einf. 4, 3

7 ¬((P ∧Q) ∧ ¬P ) ¬-Einf. 1, 6

13.3.4. Diskussion

13.3.4.1. Vor- und Nachteile

Pro

• Argumentieren mit Annahmen (Widerspruchsbeweis, Fallunterscheidung) kann nach-vollzogen werden

• Näher am Nachdenken und Argumentieren (die Konklusion wird aus den Prämissenentwickelt, im Baumkalkül wird ein Argument überprüft, aber nicht die Konklusiontatsächlich aus den Prämmissen entwickelt)

• Anwendung in der Sprachphilosophie (dazu gleich mehr)

Contra

• Kein mechanisches Überprüfen

• Es können keine Gegenbeispiele abgelesen werden

13.3.4.2. Semantik logischer Ausdrücke

Was muss jemand wissen, um beispielsweise „und“ zu verstehen? Zwei Antworten:

1. Meaning as Denotation: Sie muss wissen, wofür „und“ steht (d. h. für welche Wahr-heitsfunktion).

2. Meaning as Use: Sie muss wissen, nach welchen Regeln „und“ verwendet wird.

122

14. *Korrektheit und Vollständigkeit

14.1. Einleitung

14.1.1. Metalogik

14.1.1.1. Metalogik

In diesem Kapitel betreiben wir nicht mehr Aussagen-, Prädikaten- oder Modallogik, sondernreden über solche Logiken. (Wenn von „Logiken“ im Plural die Rede ist, sind immer solchelogischen Systeme gemeint.)

14.1.2. Beispiele


Substitutionstheorem der AL Angenommen Φ â⊧ Ψ. Sei A eine beliebige Formel und A∗

die Formel, die man erhält, wenn man in A beliebig viele Vorkommnisse der Teilformel Φdurch Ψ ersetzt und/oder umgekehrt. Dann gilt: A â⊧ A∗

Erläuterung Hier wird eine allgemeine Aussage über aussagenlogische Formeln und ihreÄquivalenz getroffen. Diese Aussage wird nicht im Kalkül der Aussagenlogik bewiesen, son-dern mit metalogischen Mitteln (vollständige Induktion).


Deduktionstheorem Wenn Γ,Φ ⊢ Ψ, dann auch Γ ⊢ Φ→ Ψ.

Erläuterung Man beachte, dass hier über Ableitungen in einem Kalkül gesprochen wird:Wenn es in dem Kalkül eine Ableitung der Konklusion Ψ aus der Prämissenmenge Γ ∪ {Φ}gibt, dann gibt es auch eine Ableitung der Konklusion Φ→ Ψ aus der Prämmissenmenge Γ.Das Deduktionstheorem gilt für alle Logiken (und Kalküle), die in diesem Kurs vorgestelltwerden.


Kompaktheit Wenn Γ ⊧ Φ, gibt es eine endliche Menge ∆ ⊆ Γ, so dass ∆ ⊧ Φ.

Erläuterungen Alle Logiken, die in diesem Kurs vorgestellt werden, sind kompakt. Kom-paktheit bedeutet, dass ein Argument mit unendlicher Prämissenmenge nur dann folgerichtigist, wenn es auch ein Argument mit endlicher Teilmenge der Prämissenmenge gibt, aus der

123


ebenfalls die Konklusion folgt. Mit Kompaktheit lässt sich rechtfertigen, warum wir Argu-mente mit unendlich vielen Prämissen zugelassen haben, diese aber nicht weiter beachtethaben.

14.1.3. Induktion

14.1.3.1. Induktionsbeweise I

Beweise per vollständiger Induktion In einem ersten Schritt (sog. Induktionsanfang oder -basis) wird gezeigt, dass die zu beweisende Behauptung für die Ausgangsmenge gilt (etwa: fürdie Zahl 0 oder für alle atomaren Formeln). In einem zweiten Schritt (sog. Induktionsschritt)wird gezeigt: Wenn die zu beweisende Behauptung für alle Elemente einer Menge gilt, danngilt sie auch für alle Elemente der Menge, die sich ergibt, wenn man die Klauseln aus derrekursiven Definition anwendet (etwa: wenn eine Behauptung für die Zahl n gilt, dann giltsie auch für deren Nachfolger n + 1; wenn eine Behauptung für die Formeln A und B gilt,dann gilt sie auch für ¬A, (A∧B) usw.). Im dritten Schritt (sog. Induktionsschluss) schließtman dann auf die zu beweisende Behauptung.

14.1.3.2. Induktionsbeweise II: Beispiel

Behauptung Jede aussagenlogische Formel hat eine gerade Anzahl an Klammern.

Beweis 1. Induktionsbasis: Eine atomare al Formel besteht nur aus einem Satzbuchsta-ben und hat daher 0 Klammern, also eine gerade Anzahl an Klammern.2. Induktionsschritt: Angenommen A ist eine aussagenlogische Formel, für die die Be-

hauptung gilt.

• Dann gilt die Behauptung auch für ¬A, da die Anzahl Klammern gleich bleibt.

Angenommen A und B sind aussagenlogische Formeln, für die die Behauptung gilt. Dann:

• . . . gilt die Behauptung für (A∧B). Sei a die Anzahl Klammern in A und b die AnzahlKlammern in B. Dann ist die Anzahl Klammern a + b + 2. Wenn a und b gerade sind,muss auch a + b + 2 gerade sein.

• . . . gilt die Behauptung für (A∨B). Sei a die Anzahl Klammern in A und b die AnzahlKlammern in B. Dann ist die Anzahl Klammern a + b + 2. Wenn a und b gerade sind,muss auch a + b + 2 gerade sein.

• . . . gilt die Behauptung für (A→ B). Sei a die Anzahl Klammern in A und b die AnzahlKlammern in B. Dann ist die Anzahl Klammern a + b + 2. Wenn a und b gerade sind,muss auch a + b + 2 gerade sein.

• . . . gilt die Behauptung für (A ↔ B). Sei a die Anzahl Klammern in A und b dieAnzahl Klammern in B. Dann ist die Anzahl Klammern a+b+2. Wenn a und b geradesind, muss auch a + b + 2 gerade sein.

3. Induktionsschluss: Aus Induktionsbasis und -schritt folgt: Jede aussagenlogische For-mel enthält eine gerade Anzahl an Klammern. q.e.d.

124


14.1.4. Literatur

Quellenangabe Die folgenden Beweise stammen aus

• Graham Priest: An Introduction to Non-Classical Logic. 2. Aufl., Cambridge: CUP,2008, Kap. 1.11 (AL) und 12.8 (PL).

Die relevanten Beweise (und andere) finden sich auch ausführlicher aufbereitet in:

• Colin Howson: Logic with Trees. London: Routledge, 1997, Kap. 4 (AL) und 8 (PL).

14.2. Aussagenlogik

14.2.1. Beweisideen

Beweisidee Korrektheit

• Zu zeigen ist: Wenn Γ ⊢ Φ, dann auch Γ ⊧ Φ. Das heißt: Wenn der Baum geschlossenist, dann gibt es keine Interpretation, die die Wurzel wahr macht.

• Beweis per Kontraposition: Wenn es eine solche Interpretation gibt, kann der Baumnicht geschlossen werden.

• Denn: Angenommen es gibt eine Interpretation, die die Wurzel wahr macht. Dann sorgtAbarbeiten der Regeln niemals dafür, dass diese Interpretation unterwegs „verloren“geht.

Beweisidee Vollständigkeit

• Zu zeigen ist: Wenn Γ ⊧ Φ, dann auch Γ ⊢ Φ. Das heißt: Wenn es keine Interpretationgibt, die die Wurzel wahr macht, dann ist der Baum auf jeden Fall geschlossen.

• Beweis per Kontraposition: Wenn der Baum offen ist, dann gibt es eine solche Inter-pretation.

• Denn: Wir zeigen per Induktion, dass sich aus jedem offenen Baum eine Interpretationkonstruieren lässt.

14.2.2. Korrektheit

Definition 43 (Treue Interpretation). Sei I eine (aussagenlogische) Interpretation. Seia ein Ast in einem Baum. Dann ist I eine zu a treue Interpretation genau dann, wenn fürjede Formel Φ im Ast a gilt: I(Φ) =W .

Korrektheitslemma Wenn I treu zu a ist und eine Entwicklungsregel auf a angewendetwird, dann ist I zu mindestens einem der entstehenden Äste treu.

125


Beweis des Korrektheitslemmas Der Beweis besteht in einer Betrachtung der einzelnenEntwicklungsregeln. Wir beschränken uns auf die Regeln für →; die anderen Fällen sindvöllig parallel.(a) Angenommen I ist treu zu a, a enthält eine Zeile der Form ¬(Φ → Ψ) und die Regel

für das negierte Konditional wird auf diese Zeile angewendet. Dann entsteht nur ein Ast,der sich von a in der Hinzunahme von Φ und ¬Ψ unterscheidet. Da I treu zu a ist, machtI jede Zeile in b wahr (siehe Definition). Deshalb gilt auch I(¬(Φ → Ψ)) = W . DeshalbI(Φ → Ψ) = F , deshalb I(Φ) = W und I(Ψ) = F , deshalb I(¬Ψ) = W . Also, macht I jedeZeile des neuen Astes wahr.(b) Angenommen I ist treu zu a, a enthält eine Zeile der Form Φ → Ψ und die Regel

für das Konditional wird auf diese Zeile angewendet. Dann enstehen zwei neue Äste: Einerbesteht in der Hinzunahme von ¬Φ, einer in der Hinzunahme von Ψ. Da I treu zu a ist,macht I jede Zeile in b wahr (siehe Definition). Deshalb gilt auch I(Φ → Ψ) = W . Deshalbentweder I(Φ) = F und deshalb I(¬Φ) =W oder I(Ψ) =W . Im ersten Fall ist I treu zu demersten Ast, im zweiten Fall zum zweiten Ast. Also, macht I jede Zeile mind. eines neuenAstes wahr. q.e.d.

Korrektheit Für endliche Γ gilt: wenn Γ ⊢ Φ, dann Γ ⊧ Φ

Anmerkung Wegen Kompaktheit (s. o.) genügt es, Korrektheit für endliche Prämissenmen-gen zu zeigen.

Beweis von Korrektheit Wir beweisen die Kontraposition: wenn Γ ⊭ Φ, dann Γ ⊬ Φ.Angenommen Γ ⊭ Φ. Dann gibt es ein I, dass jede Prämisse aus Γ wahr und Φ falsch, also

¬Φ wahr macht. Sei B ein vollständig abgearbeiteter Baum mit Γ und ¬Φ als Wurzel. I isttreu zur Wurzel. Wenn eine Entwicklungsregel auf die Wurzel angewendet wird, gilt gemäßdem Korrektheitslemma, dass I zu mind. einem der entstehenden Ast treu ist. Ebenso gilt,dass, wenn wir auf diesen Ast eine Entwicklungsregel anwenden, gemäß dem Korrektheits-lemma I zu mind. einem der entstehenden Äste treu ist, und so weiter. Durch wiederholtesAnwenden des Korrektheitslemmas ergibt sich, dass I treu zu mind. einem Ast von B ist.Wir müssen zeigen, dass Γ ⊬ Φ, das heißt, dass dieser Ast offen ist. Der Ast a, zu dem

I treu ist, muss offen sein. Angenommen er wäre geschlossen. Dann enthielte a eine FormelΨ und ¬Ψ und I(Ψ) = I(¬Ψ) = W , was der Annahme widerspricht (gemäß der I Γ und Φwahr macht). Also ist der Ast a offen, also Γ ⊬ Φ. q.e.d.

14.2.3. Vollständigkeit

Definition 44 (durch einen Ast induzierte Interpretation). Sei a ein offener Asteines vollständigen Baumes. Die durch a induzierte Interpretation I ist diejenige Interpre-tation, für die gilt I(S) = W , wenn der Satzbuchstabe S in einer Zeile von a steht, undI(S) = F , wenn ¬S in einer Zeile von a steht. (Wenn beides nicht der Fall ist, ist I(S)beliebig.) Beachte, dass a ein offener Ast ist und daher nicht sowohl S als auch ¬S in demAst vorkommen können.

Vollständigkeitslemma Sei a ein offener Ast eines vollständigen Baums B. Sei I die durcha induzierte Interpretation. Dann gilt:

126


Wenn Φ zu a gehört, I(Φ) =W

Wenn ¬Φ zu a gehört, I(Φ) = F

Beweis des Vollständigkeitslemmas Der Beweis ist ein Induktionsbeweis über den Aufbauvon Φ.Induktionsbasis: Wenn Φ ein Satzbuchstabe ist, gilt die Behauptung wegen der Definition

einer durch den Ast a induzierten Interpretation.Induktionsschritt: Angenommen die Behauptung gilt für beliebige Formeln Ψ und X.

Zu zeigen ist, dass sie dann auch für die komplexen Formeln von der Form ¬Ψ, (Ψ ∧X),(Ψ ∨ X), (Ψ → X) oder (Ψ ↔ X) gilt. Wir beschränken uns auf den Fall (Ψ ∧ X); dieanderen Fälle sind völlig parallel. Da der Ast a vollständig entwickelt wurde, muss die Regelfür die Konjunktion angewendet worden sein. Deshalb sind Ψ und X im Ast. Wegen derInduktionsannahme gilt: I(Ψ) = I(X) =WInduktionsschluss: Aus Induktionsbasis und -schritt folgt die Behauptung. q.e.d.

Vollständigkeit Für endliche Γ gilt: wenn Γ ⊧ Φ, dann Γ ⊢ Φ

Anmerkung Wegen Kompaktheit (s. o.) genügt es, Korrektheit für endliche Prämissenmen-gen zu zeigen.

Beweis von Vollständigkeit Wir beweisen die Kontraposition: wenn Γ ⊬ Φ, dann Γ ⊭ Φ.Angenommen Γ ⊬ Φ, das heißt mind. ein Ast a des vollständig entwickelten Baumes mit

der Wurzel Γ und ¬Φ ist offen. Die durch diesen Ast a induzierte Interpretation macht alleZeilen im Ast a wahr gemäß Vollständigkeitslemma, das heißt Γ wahr und Φ falsch. AlsoΓ ⊭ Φ. q.e.d.

14.3. Prädikatenlogik

14.3.1. Beweisideen

Die Beweisideen sind dieselben wie in der AL. Es ergeben sich jedoch Komplikationen:

• Korrektheit: wie gehabt. Wenn es eine Interpretation gibt, die die Wurzel wahr macht,geht sie durch Abarbeiten der Regeln nicht verloren.

• Vollständigkeit: Für die Konstruktion einer Interpretation brauchen wir spezielle Mit-tel. Kniff: Individuenkonstanten stehen für sich selbst.

14.3.2. Korrektheit und Vollständigkeit

– Bei Zeit und Bedarf an der Tafel! (oder siehe bei Priest) –

127

Anhänge

128

A. Regeln Baumkalkül

A.1. Aussagen- und Prädikatenlogik

Negation ¬¬Φ↓Φ

Konjunktion (Φ ∧Ψ)↓ΦΨ

Negierte Konjunktion ¬(Φ ∧Ψ)↓

¬Φ ¬Ψ

Disjunktion (Φ ∨Ψ)↓

Φ Ψ

Negierte Disjunktion ¬(Φ ∨Ψ)↓¬Φ¬Ψ

Konditional (Φ→ Ψ)↓

¬Φ Ψ

Negiertes Konditional ¬(Φ→ Ψ)↓Φ¬Ψ

Bikonditional (Φ↔ Ψ)↓

ΦΨ

¬Φ¬Ψ

Negiertes Bikonditional ¬(Φ↔ Ψ)↓

Φ¬Ψ

¬ΦΨ

129


Allquantor ∀αΦ↓

Φ[α∣β]Jedes freie Vorkommnisder Variable α wirddurch eine beliebigeKonstante β ersetzt.

Negierter Allquantor ¬∀αΦ↓

∃α¬Φ

Existenzquantor ∃αΦ↓

Φ[α∣ν]Jedes freie Vorkommnisder Variable α wirddurch eine (in diesem

Ast) neueKonstante ν ersetzt.

Negierter Existenzquantor ¬∃αΦ↓

∀α¬Φ

Identität I β = γΦ↓

Φ[β∣γ]Beliebig viele Vor-kommnisse der Kon-stante β (bzw. γ)in Φ werden durch

γ (bzw. β)ersetzt.

Identität II ⋅↓

β = ββ ist einebeliebigeKonstante

Hinweis Die Regeln für die Junktoren sind in AL und PL dieselben. Für PL gelten zusätz-lich die Regeln für die Quantoren. Die Regeln für die Identität gelten nur für PL=.

Metaregeln

1. Schließungsregel: Ein Ast, der sowohl eine Formel Φ als auch ¬Φ enthält, ist geschlossenund wird mit „×“ markiert.

2. Klugheitsregel: Wenn man zwischen mehreren Regelanwendungen auswählen kann,sollte man eine Regel anwenden, die nicht zu einer Verzweigung führt. Bei den Re-geln für die Quantoren sollte man als erstes die Regeln für die negierten Quantoren,als zweites die Regel für den Existenzquantor und zuletzt die Regel für den Allquantoranwenden.

130


Wie zeige ich . . . ?

Ich will zeigen, dass eine Formel tautologisch ist! Zeige dass der Baum mit der negiertenFormel als Wurzel geschlossen ist.

Ich will zeigen, dass eine Formel kontradiktorisch ist! Zeige, dass der Baum mit derFormel als Wurzel geschlossen ist.

Ich will zeigen, dass eine Formel kontingent ist! Gib erstens eine Interpretation an,relativ zu der die Formel wahr ist, und zweitens eine Interpretation, relativ zu der dieFormel falsch ist.

Ich will zeigen, dass ein Argument folgerichtig ist! Zeige, dass der Baum mit den Prä-missen und der negierten Konklusion als Wurzel geschlossen ist.

Ich will zeigen, dass ein Argument nicht folgerichtig ist! Gib eine Interpretation an,relativ zu der die Prämissen wahr sind und die Konklusion falsch.

A.2. Modallogik

Neuerungen

• In jeder Zeile notieren wir zusätzlich, in welcher Welt die Zeile gelten soll (und zwarmit w0,w1 usw.).

• Es gibt eine neue Art von Zeile. Wenn wir etwas über die Zugänglichkeitsrelationerfahren, notieren wir das z. B. mit (13) w3 r w4

Regel für den Notwendigkeitsoperator ◻Φ,wiwi r wj↓

Φ,wj

Regel für den Möglichkeitsoperator ◊Φ,wi↓

wi r wjΦ,wj

Wichtig: j muss hier neu sein, d. h. darf im Ast noch nicht vorkommen.

Regel für den negierten Notwendigkeitsoperator ¬ ◻Φ,wj↓

◊¬Φ,wj

131


Regel für den negierten Möglichkeitsoperator ¬◊Φ,wj↓

◻¬Φ,wj

Regel für Reflexivität ⋅↓

wi r wi

Regel für Symmetrie wi r wj↓

wj r wi

Regel für Transitivität wi r wjwj r wk↓

wi r wk

Besonderheiten S5 Da in S5 jeder Welt jede Welt zugänglich ist, können wir es uns sparen,die Zugänglichkeitsrelation zu notieren. Außerdem ändert sich die Regel für den Notwendig-keitsoperator leicht.

Regel für den Notwendigkeitsoperator in S5 ◻Φ,wi↓

Φ,wj

Wichtig: j darf hier beliebig gewählt werden.

132

B. *Logische Notation

B.1. Einleitung

B.1.0.1. Einleitung

In der Geschichte der Logik wurden diverse Notationen entwickelt. Oft waren Autoren alleinschon durch die Möglichkeiten des Buchdrucks eingeschränkt und mussten ihre Notation andie zur Verfügung stehenden Möglichkeiten anpassen. Dieser Anhang stellt einige ebenfallsverwendete Symbole und Notationsvarianten vor, damit Sie nicht ganz aufgeschmissen sind,wenn diese Ihnen in einem Text begegnen. Ich unterscheide dabei, etwas willkürlich, zwischenNotationsvarianten und -alternativen. Varianten unterscheiden sich nur in Details von derNotation aus unserem Logikkurs, während Alternativen deutlich davon abweichen

B.2. Varianten

B.2.0.1. Übersicht: Junktoren und Quantoren

Bezeichnung Unser Zeichen Andere Zeichen

Negation ¬ ∼, ϕ (Strich über der zunegierenden Formel)

Konjunktion ∧ &, •

Disjunktion ∨Ausschließende Disjunktion/Kontravalenz ⊕, ∨̇, ∨, ��

Konditional/Subjunktion → ⊃Bikonditional/Bisubjunktion ↔ ≡

Allquantor ∀ ⋀, ()Existenzquantor ∃ ⋁

B.2.0.2. Erläuterungen I

Achtung! Manche logische Systeme verwenden auch beide Zeichen für die Negation (oderbeide Zeichen für das Konditional), nämlich dann wenn sie zwischen verschiedenen Negatio-nen (oder „Wenn–Dann“-Verknüpfungen) unterscheiden.

B.2.0.3. Erläuterungen II: AL

Konjunktion Für die Konjunktion wird manchmal auch gar kein Zeichen verwendet. StattP ∧Q schreibt man dann PQ.

133


Satzbuchstaben Wir verwenden als Satzbuchstaben die Großbuchstaben P,Q,R usw. An-dere verwenden statt dessen Kleinbuchstaben p, q, r usw. oder die Großbuchstaben A,B,Cusw.

B.2.0.4. Erläuterungen III: PL

Prädikate Wir verwenden für Prädikate die Großbuchstaben F,G,H usw. Andere verwen-den beliebige Großbuchstaben. Die Stelligkeit markieren wir mit Strichen (z. B. F ′, H ′′).Andere markieren die Stelligkeit mit hochgestellten Ziffern (auch bei einstelligen Prädika-ten!): F 1,G3 usw. Für zweistellige Prädikate (= Relationen) wird oft R in Infix-Notationverwendet (also z. B. aRb statt F ′ab)

Quantoren In vielen älteren Texten werden Klammern für den Allquantor verwendet: Stattbeispielsweise ∀x(Fx → Gx) steht dann (x)(Fx → Gx). Manche Logiker klammern jedeQuantorenphrase ein: Statt ∀x(Fx → Gx) steht dann (∀x)(Fx → Gx) und statt ∃x(Fx ∧Gx) steht dann (∃x)(Fx ∧Gx)Manchmal werden die Quantoren auch mit einem überdimensioniertem „oder“ (⋁) und

einen überdimensioniertem „und“ (⋀) geschrieben. Dahinter steht der Gedanke, dass es einenbegrifflichen Zusammenhang zwischen „alle“ und „und“ und zwischen „es gibt ein“ und „oder“gebe. ∃xFx bedeute beispielsweise: Der erste Gegenstand aus dem Gegenstandsbereich istF oder der zweite Gegenstand aus dem Gegenstandsbereich ist F oder . . .∀xFx bedeutebeispielsweise: Der erste Gegenstand aus dem Gegenstandsbereich ist F und der zweiteGegenstand aus dem Gegenstandsbereich ist F und . . . . (Wie der Zusammenhang zwischenAllaussagen und Konjunktionen und zwischen Existenzaussagen und Disjunktionen genauerausbuchstabiert werden kann, ist jedoch umstritten.)

B.2.0.5. Erläuterungen IV: Klammern

Klammereinsparungsregeln Notationen unterscheiden sich oft darin, wie viele Klammer-einsparungsregeln sie verwenden. Neben der von benutzten Regel, dass äußere Klammernweggelassen werden dürfen, kennen viele Logiker die Regel, dass „∧“ und „∨“ stärker bindenals „→“ und „↔“. Statt

(P ∧Q)→ R

darf man dannP ∧Q→ R

schreiben. InP ∧ (Q→ R)

darf dagegen keine Klammer weggelassen werden.

B.2.0.6. Erläuterungen V: Klammern

Principia-Notation Russell und Whitehead (in: Principia Mathematica 1910 ff.) verwendenstatt Klammern Punkte: Statt beispielsweise

((P ∨ P )→ P )

134


schreiben sie∶ P ∨ P.→ .P

Wer diese Schreibweisen kennen lernen möchte, möge einen Blick in den entsprechendenArtikel in der Stanford Encyclopedia of Philosophy werfen: http://plato.stanford.edu/entries/pm-notation/

B.3. Alternativen

B.3.1. Polnische Notation

Die sog. Polnische Notation wurde in den späten 1920ern von dem Polnischen Logiker JanŁukasiewicz eingeführt. Sie unterscheidet sich dadurch von der sonst verwendeten Notation,dass Junktoren nicht zwischen die Satzbuchstaben geschrieben werden (Infix-Notation) son-dern vor diese (Präfix-Notation). Als Satzbuchstaben werden (beliebige) Kleinbuchstabenverwendet. Für die Junktoren werden die folgenden Großbuchstaben verwendet:

Unsere Notation Polnische Notation Abk. für

¬ N Negation∧ K Konjunktion∨ A Alternation→ C conditional / Konditional↔ E equivalence / Bikonditional

Die polnische Notation kommt ohne Klammern aus.

Unsere Notation Polnische Notation

P ∧Q Kpq¬(P ∧Q) NKpq

¬(P ∧Q) ∧ ¬P KNKpqNpP → (Q→ (P ∨R)) CpCqApr

Vorteile

• Normale Buchstaben anstatt spezieller logischer Zeichen

• Keine Klammern nötig, Vorteilhaft für die Computer-Programmierung

Nachteile

• Unübersichtlich

135

http://plato.stanford.edu/entries/pm-notation/

http://plato.stanford.edu/entries/pm-notation/


B.3.2. Freges Begriffsschrift

Wenn man noch weiter in die Geschichte der logischen Notationen zurückgeht, findet mannoch einige weitere Schreibweisen. Prominent, wenn auch nicht mehr in Gebrauch, ist dieSchreibweise von Frege (aus: Begriffsschrift 1879). Freges Notation unterscheidet sich von denheutigen Notationen dadurch, dass sie zwei-dimensional ist, d. h. man schreibt eine Formelnicht nur von links nach rechts, sondern von links nach rechts und von oben nach unten.Hier sind einige Beispiele, damit Sie einen Eindruck von Freges Notation bekommen (Fregebenutzt andere Buchstaben als wir, wie das letzte Beispiel zeigt):

Freges Notation Gewöhnliche Notation

Q

PP → Q

Q

PP → ¬Q

Q

P¬(P → ¬Q) oder P ∧Q

a G(a)F (a)

∀x(Fx→ Gx)

Wer diese Schreibweisen kennen lernen möchte, möge einen Blick in den entsprechendenArtikel in der Stanford Encyclopedia of Philosophy werfen: http://plato.stanford.edu/entries/frege/

B.4. Weitere Besonderheiten

B.4.1. Anführungszeichen

Wir sind wenig genau mit Anführungszeichen umgegangen. Beispielsweise in

(1) Wenn Φ eine al Formel ist, dann ist auch ¬Φ eine al Formel.

fehlen Anführungszeichen. Aber

(1*) Wenn „Φ“ eine al Formel ist, dann ist auch „¬Φ“ eine al Formel.

stimmt genau genommen ebenfalls nicht. Denn „¬Φ“ ist keine al Formel, da zum Zeichen-vorrat der AL keine griechischen Buchstaben gehören. Was gemeint ist, ist vielmehr: Wennman in „¬Φ“ anstelle von „Φ“ eine al Formel einsetzt, dann erhält man eine tatsächliche alFormel. Um diesem Umstand Rechnung zu tragen, werden in der Logik sog. corner quotesverwendet:

(1**) Wenn ⌜Φ⌝ eine al Formel ist, dann ist auch ⌜¬Φ⌝ eine al Formel.

Grob gesagt müssten corner quotes immer dann verwendet werden, wenn mit metasprachli-chen Platzhaltern für objektsprachliche Zeichenketten gearbeitet wird.

136

http://plato.stanford.edu/entries/frege/

http://plato.stanford.edu/entries/frege/


B.4.2. Zusätzliche Zeichen

B.4.2.1. Zusätzliche Zeichen

Unter dieser Rubrik folgen Zeichen, die alle ohne viel Aufhebens zur AL bzw. PL hinzugefügtwerden können, da es sich um Abkürzungen handelt. Im Folgenden steht „A(x)“ für einebeliebige pl. Formel, die höchstens x als ungebundene Variable enthält.

B.4.2.2. Zusätzliche Zeichen: Quantoren

Zeichen Bedeutung Abkürzung für

∃!xA(x) Es gibt genau einen Gegenstand, der A ist ∃x(A(x) ∧ ∀y(A(y)→ x = y))∃nxA(x) Es gibt mind. n Gegenstände, die A sind zur Übung∃n!xA(x) Es gibt genau n Gegenstände, die A sind zur Übung

B.4.2.3. Zusätzliche Zeichen: Falsum und Verum

Zwei zusätzliche Zeichen Manchmal werden noch zwei zusätzliche Zeichen (zur Objekt-sprache) hinzugefügt, nämlich:

• Falsum: �

• Verum: ⊺

Beide werden syntaktisch wie Satzbuchstaben (AL) bzw. atomare Formeln (PL) verwendet,so dass dann z. B. auch �→ P oder ∀x(Fx→ ⊺) wohlgebildete Formeln sind. Semantisch be-trachtet ist � falsch relativ zu jeder Interpretation und ⊺ wahr relativ zu jeder Interpretation.Die beiden Zeichen lassen sich daher auch als Abkürzungen verstehen: � ist eine Abkürzungfür eine beliebige Kontradiktion (z. B. P ∧¬P ), ⊺ für eine beliebige Tautologie (z. B. P ∨¬P ).

137

C. *Traditionelle Bezeichnungen vonlogischen Gesetzen

C.1. Logische Schlüsse

Bezeichnung

modus ponens A→ B,A ⊧ Bmodus tollens A→ B,¬B ⊧ ¬Aconsequentia mirabilis ¬A→ A ⊧ AKontraposition A→ B â⊧ ¬B → ¬AVerstärkung des Antezedens A→ B ⊧ (A ∧C)→ BAbschwächung des Konsequens A→ B ⊧ A→ (B ∨C)Kettenschluss, Transitivität des Konditionals A→ B,B → C ⊧ A→ CImportation A→ (B → C) ⊧ (A ∧B)→ CExportation (A ∧B)→ C ⊧ A→ (B → C)

Doppelte-Negation-Elimination ¬¬A ⊧ Aex falso quodlibet, ex contradictione quodlibet � ⊧ ADisjunktiver Syllogismus A ∨B,¬B ⊧ A

Assoziativgesetze (A ∨B) ∨C â⊧ A ∨ (B ∨C)(A ∧B) ∧C â⊧ A ∧ (B ∧C)(A↔ B)↔ C â⊧ A↔ (B ↔ C)

Kommutativgesetze A ∨B â⊧ B ∨AA ∧B â⊧ B ∧AA↔ B â⊧ B ↔ A

Distributivgesetze A ∧ (B ∨C) â⊧ (A ∧B) ∨ (A ∧C)A ∨ (B ∧C) â⊧ (A ∨B) ∧ (A ∨C)

De Morgansche Gesetze ¬(A ∧B) â⊧ ¬A ∨ ¬B¬(A ∨B) â⊧ ¬A ∧ ¬B

Quantorentausch ∀x∀y Φ(x, y) â⊧ ∀y∀x Φ(x, y)∃x∃y Φ(x, y) â⊧ ∃y∃x Φ(x, y)∃x∀y Φ(x, y) ⊧ ∀y∃x Φ(x, y)

138

C. *Traditionelle Bezeichnungen von logischen Gesetzen

C.2. Logische Wahrheiten

Bezeichnung

Gesetz vom (ausgeschlossenen) Widerspruch ⊧ ¬(A ∧ ¬A)Gesetz vom ausgeschlossenen Dritten, tertium nondatur

⊧ A ∨ ¬A

Gesetz der Identität ⊧ ∀x x = xLeibniz’ Gesetz (nur in PL zweiter Stufe ausdrück-bar!)

⊧ ∀x∀y∀X(x = y↔ (Xx↔Xy))

C.3. Fehlschlüsse

Eine Auflistung aller formalen Fehlschlüsse ist ein hoffnungsloses Unterfangen, aber drei sindbesonders bekannt und wichtig:

Bezeichnung

Bejahung des Konsequens (benannt nach der zwei-ten Prämisse)

A→ B,B ⊭ A

Verneinung des Antezedens (benannt nach der zwei-ten Prämisse)

A→ B,¬A ⊭ ¬B

Falsches Dilemma A ∨B,A ⊭ ¬B

139

D. *Logikbücher – Eine kommentierteLiteraturliste

Für das Verständnis des Logikkurses ist es nicht nötig, ein Logikbuch zu konsultieren. Die-se Liste ist daher für diejenigen, die (aus welchen Gründen auch immer) einmal schauenmöchten, wie andere den Stoff präsentieren oder bestimmte Begriffe definieren, oder die denStoff vertiefen und ergänzen möchten. Im ersten Teil nennen wir Logikeinführungen, diesich inhaltlich weitgehend mit dem Stoff unseres Logikkurses überschneiden, und im zweitenTeil Bücher, die an den Stoff unseres Logikkurses anschließen, das heißt, die ohne Grund-kenntnisse, wie sie in unserem Kurs vermittelt werden, kaum verständlich sind. Wir habennur Bücher aufgenommen, die wir kennen und guten Gewissens empfehlen können. Es gibtselbstverständlich noch viel mehr Logikbücher und darunter bestimmt auch viele gute!

D.1. Einführungen in die Logik

D.1.1. Neuere Einführungen (Baumkalkül)

Beckermann, Ansgar: Einführung in die Logik. 3. Aufl., Berlin: de Gruyter, 2011. Sehrausführlich, so wird beispielsweise die Semantik der Prädikatenlogik zweimal, einmal infor-mell, einmal formal abgehandelt. Das Buch ist daher besonders zum Selbststudium geeignet,aber weniger zum Nachschlagen. Insgesamt das deutschsprachige Lehrbuch, das neben demvon Bühler unserem Logikkurs am nächsten kommt.

Bühler, Axel: Einführung in die Logik. 4. Aufl., Freiburg: Alber, im Erscheinen. Einegut lesbare Einführung in die Aussagen- und Prädikatenlogik. Prägnanter und knapper alsBeckermann, mehr Metalogik. Insgesamt das deutschsprachige Lehrbuch, das neben demvon Beckermann unserem Logikkurs am nächsten kommt (allerdings keine Darlegung derWahrheitstafelmethode und nur wenige Übungsaufgaben zu den Kalkülen für AL und PL).

Lepore, Ernest und Sam Cummins: Meaning and Argument: An Introduction to Lo-gic through Language. 2. Aufl., Blackwell, 2009. Ausführliches, sehr an der natürlichenSprache orientiertes Lehrbuch, das daher für alle interessant ist, die mehr über die Anwen-dung der Logik auf Phänomene wie Anaphern, Kennzeichnungen usw. erfahren wollen. DieSemantik der Prädikatenlogik wird nur informell abgehandelt.

Restall, Greg: Logic: An Introduction. London: Routledge, 2006. Eine sehr gute Ein-führung in die Aussagen- und Prädikatenlogik, die auch auf philosophische Fragen zur Logik(z. B. Folgerungsbegriff, Vagheit) eingeht. In einem Kapitel wird zusätzlich der Kalkül desnatürlichen Schließens vorgestellt

140

D. *Logikbücher – Eine kommentierte Literaturliste

von Kutschera, Franz und Alfred Breitkopf: Einführung in die moderne Logik. 8. Aufl.,Freiburg: Alber, 2007. In Regensburg entstandenes Lehrbuch ohne viel Schnickschnack,das aber alles Wichtige enthält.

D.1.2. Neuere Einführungen (Natürliches Schließen)

Halbach, Volker: The Logic Manual. Oxford: OUP, 2010. Stärke dieses Lehrbuches istseine Knappheit, wodurch es zum Nachschlagen sehr gut geeignet ist. Es ist aber auch durch-aus formal angelegt. Halbach legt ein Augenmerk darauf, alle Begriffe präzise zu definieren.Übungsaufgaben finden sich auf der Homepage des Autors.

Hardy, Jörg und Christoph Schamberger: Logik der Philosophie. Göttingen: Vanden-hoeck & Ruprecht, 2012. Verwendet eine unorthodoxe Version des Natürlichen Schlie-ßens, ist aber besonders empfehlenswert für diejenigen, die sehen wollen, wie die Logik zurAnalyse „echter“ philosophischer Argumente eingesetzt werden kann.

Rosenkranz, Sven: Einführung in die Logik. Stuttgart: Metzler, 2006. Gelungenes Lehr-buch, das auf prägnante Weise und mit ausführlichen Beispielen ins Natürliche Schließeneinführt. Eine Besonderheit ist die Diskussion von Fehlschlüssen in Teil IV.

D.1.3. Klassische Einführungen

Jeffrey, Richard: Formal Logic: Its Scope and Limits. New York: McGraw-Hill, 1967 (undmehrere Neuauflagen). Logiklehrbuch von einem der Erfinder (neben Beth und Smullyan)des Baumkalküls. Sehr knapp gehalten, enthält aber alles Wichtige.

Lemmon, E. J.: Beginning Logic. Indianapolis: Hackett, 1978. (Diverse Nachdrucke,Erstveröffentlichung 1965.) Weitverbreitetes klassisches Logikbuch, macht auf den erstenBlick einen verstaubten Eindruck, wird aber immer noch gerne für Logikkurse, die Natürli-ches Schließen als Kalkül benutzen, verwendet.

Mates, Benson: Elementary Logic. Oxford: OUP, 1962. (dt. Elementare Logik. Prädika-tenlogik der ersten Stufe. 2. Aufl., Göttingen: Vandenhoeck & Ruprecht, 1978.) EinKlassiker unter den Einführungen in die Aussagen- und Prädikatenlogik, der ebenfalls aufden Kalkül des Natürlichen Schließens setzt. Enthält schöne Übersetzungsbeispiele und alsExtra einen interessanten Abschnitt zur Geschichte der Logik.

Quine, Willard Van Orman: Methods of Logic. Zuerst 1950, diverse Auflagen. (dt.Grundzüge der Logik. 13. Aufl., Frankfurt/M.: Suhrkamp, 2009.) Ein Klassiker, der inSymbolismus und Kalkül sehr von unserem Logikkurs abweicht, aber aufgrund seines klas-sischen Status und dem Rang seines Autors nicht so schnell aus den Regalen verschwindenwird.

141

D. *Logikbücher – Eine kommentierte Literaturliste

D.2. Weiterführende Bücher

D.2.1. Philosophie der Logik

Read, Stephen: Thinking about Logic. Oxford: OUP, 1995. Bestes Buch, das in dieDebatten um Wahrheit, Paradoxien, mögliche Welten usw. einführt. Weniger sprachphiloso-phisch angelegt als Tugendhat/Wolf.

Tugendhat, Ernst und Ursula Wolf: Logisch-Semantische Propädeutik. Stuttgart: Re-clam, 1983. Kein Logikbuch im engen Sinn, da Tugendhat/Wolf sehr an semantischenGrundbegriffen interessiert sind. Gerade dadurch wird aber die Schnittstelle zwischen Logikund Sprachphilosophie, Metaphysik usw. deutlich. (Das Buch ist leider etwas veraltet, aberdennoch das beste deutschsprachige Buch in dieser Rubrik.)

D.2.2. Formale Logik und nicht-klassische Logik

Boolos, George, John Burgess und Richard Jeffrey: Computability and Logic. 5. Aufl.,Cambridge: CUP, 2007. Klassische Einführung in die Metalogik, in der eine Breite vonThemen angesprochen wird. Formal anspruchsvoll.

Burgess, John: Philosophical Logic. Princeton: PUP, 2009. Geht sowohl auf Erweite-rungen (Modallogik, Zeitlogik), aber auch Revisionen (Relevanzlogik, intuitionistische Logik)der klassischen Logik ein. Formal nicht ohne Anspruch.

Link, Godehard: Collegium Logicum. 2 Bände. Paderborn: Mentis, 2009. Eher einHandbuch als ein Lehrbuch, das neben dem Grundlagenstoff viele Themen behandelt. Formalanspruchsvoll.

Priest, Graham: An Introduction to Non-Classical Logic. 2. Aufl. Cambridge: CUP,2008. Das Standardlehrbuch zu nicht-klassischen Logiken, das außerdem den Vorteil hat,sich nicht in formalen Kleinkram zu verlieren. Priest verwendet außerdem den Baumkalkül,der aus unserem Logikkurs vertraut ist. (Achtung: die zweite Auflage ist gegenüber der erstendeutlich erweitert. Es gibt auch eine deutsche Übersetzung, die jedoch nur den ersten Teilumfasst.)

Sider, Ted: Logic for Philosophy. Oxford: OUP, 2010. Geht vor allem auf Erweiterungender klassischen Logik ein: Modallogik und ihre verschiedenen Anwendungen, Prädikatenlogikzweiter Stufe. Sider stellt außerdem zu Beginn verschiedene Kalküle vor. Dieses Buch kanndaher auch genutzt werden, um verschiedene Arten von Kalkülen kennenzulernen.

142

Documents

EinführungindiemoderneLogik0. Organisatorisches 0.0.0.1. BasiskursLogik • Auch bekannt als: PHI-M04 und PHI-M10.4 und außerdem anrechenbar in PHI-M35.2undalsfreieLeistungspunkte