Klausurvorbereitung zum Seminar „Formale Logik“ im Sommersemester 2005

Philipps-Universität Marburg, Fachbereich 03. Dozent: Willem Warnecke.

Zusammenfassung

Beispiele

Merkblatt I und Formelsammlung (jeweils korrigiert)

(w) Manuel Haim, 05-Jul-2005

Dieses Dokument soll eine Kurzzusammenfassung des Seminars darstellen und ersetzt keinesfalls das Seminar selbst!

Syllogismen (siehe auch Merkblatt I)

Aus zwei gegebenen Prämissen (Voraussetzungen) folgt eine Conclusio (Schlussfolgerung).

Begriffe: Prädikat (P), Subjekt (S), Mittelbegriff (M).

Es gibt vier Syllogismus-Figuren. Die Position von M merkt man sich anhand des W-Schemas. P steht in der ersten, S in der zweiten Prämisse. Die Conclusio ist in allen Figuren SxP.

Für die gültigen Syllogismen gibt es Namen (barbara usw.):

Deren Vokale geben an, in welchem Bezug die Begriffe in den Prämissen und der Conclusio zueinander stehen (a, i, e, o, von: affirmo=ich bestätige, nego=ich verneine, Merkhilfe: a=alle sind, i=einige sind, e=alle sind nicht=keins ist, o=einige sind nicht).

Prüfen der Richtigkeit z.B. mit Venn-Diagramm (Mengendiagramm, hier mit drei Mengen P, S, M)

a, e: nichtzutreffenden Mengenteil schraffieren

i, o: ein kleines x in zutreffenden Mengenteil/Rand malen

aus beiden Prämissen muss sich die Conclusio ergeben

Die Konsonanten geben an, wie man den Syllogismus in die erste Figur umformt:

Erster Buchstabe gibt den Syllogismus der ersten Figur an.

Die Buchstaben s, p, m, c geben die notwendige Veränderung an und stehen hinter dem Vokal, auf den sie sich beziehen.

s: Tausch der Begriffe (z.B. wird SxP zu PxS)

p: Tausch der Begriffe und Übernehmen des Bezugs aus Zielfigur

m: Tausch der beiden Prämissen

c: Tausch der Zeile mit Conclusio und Negation beider Bezüge (aus a wird o und umgekehrt, aus i wird e und umgekehrt)

Die vier Bezüge a, i, e, o bilden ein Logisches Quadrat.

Darin gibt's diese Gegensätze: konträr, subkonträr, kontradiktorisch, subaltern (lernen!)

Aussagenlogik (Junktorenlogik) (siehe auch Formelsammlung)

Logik = Lehre von gültigen Schlüssen

Eine Aussage stellt einen Sachverhalt dar („Alle Rosen sind rot.“). Sachverhalte können wahr oder nicht wahr sein.

Tatsachen sind bestehende Sachverhalte.

Aussagen sind die Atome der Aussagenlogik (Großbuchstaben, hier: Formelvariablen)

Eine Formel ist eine einzelne Formelvariable/Atom oder eine Verknüpfung von anderen Formeln (oder Formelvariablen/Atomen) durch Junktoren

Junktoren

einstellig:

zweistellig: (wie A in engl. AND, lat. ATQUE), (wie V in lat. VEL), , , (Sheffer-Strich = NAND = NOT AND)

Wahrheitstafeln

haben Zeilen für alle Belegungskombinationen (1, 0) der Formelvariablen.

Bei n verschiedenen Formelvariablen gibt es 2n solcher Kombinationen, also 2n Zeilen.

Über der ersten Zeile steht eine Formel (z.B. ).

Jede Zeile ist eine Welt, in der die Formelvariablen eindeutig belegt sind (1, 0).

Nachdem man alle Belegungen unter die Formelvariablen geschrieben hat, kann man die Belegungen für die Junktoren „ausrechnen“, wobei man bei den innersten Junktoren beginnt (genauso wie man in Mathe z.B. ausrechnet, also , , ).

Die Belegung unter dem höchsten Junktor entspricht dann der Belegung der Formel.

Ein Modell einer Formel ist eine Welt, in der die Formel wahr ist.

Eine Formel, bei der alle Welten Modelle sind, nennt man Tautologie oder allgemeingültig (immer wahr).

Regeln von deMorgan:

Auflösung von Bisubjunktion und Subjunktion:

Normalformen

Erhält man durch Umformung, kann man aber auch direkt aus Wahrheitstafel ablesen.

Man sieht dann leicht, ob eine Formel eine Tautologie ist.

Jede Formel lässt sich sowohl in KNF als auch in DNF umformen.

Konjunktive Normalform (KNF)

Konjunktion von Disjunktionen, z.B. oder

Alle Glieder müssen Tautologie sein, damit die Formel eine Tautologie ist.

Disjunktive Normalform (DNF)

Disjunktion von Konjunktionen, z.B. oder

Mindestens ein kontradiktorischer Gegensatz, damit die Formel eine Tautologie ist.

Schlussregeln

Modus Ponens (MP) (lat. „setzend“)

Konstruktives Dilemma (KD)

Hypothetischer Syllogismus (HS)

Modus Tollens (MT) (lat. „hebend“)

Destruktives Dilemma (DD)

Disjunktiver Syllogismus (DS)

Lateinische Merksätze

Salva veritate – Aus Wahrem soll Wahres folgen.

„Paradoxien der materialen Implikation“:

Ex falso quodlibet – Aus Falschem folgt Beliebiges:

Verum ex quodlibet – Das Wahre folgt aus Beliebigem:

Duplex negatio affirmat – Doppelte Verneinung fällt weg:

Tertium non datur – Satz vom ausgeschlossenen Dritten:

(entspricht nach deMorgan dem Satz vom ausgeschlossenen Widerspruch: )

Antezedens und Sukzedens bei Subjunktion:

Prädikatenlogik (siehe auch Formelsammlung)

„Subjekt = Prädikat“ (Subjekt: Kleinbuchstabe, Prädikat: Großbuchstabe)

Die Legende gibt die Belegung von Prädikatenkonstanten und Individualkonstanten an.

z.B. folgende Legende:

Mx – x ist ein Mensch, s – Sokrates

Dann heißt Ms „Sokrates ist ein Mensch“

All- und Existenz-Quantoren:

„für alle x gilt: Ax“

„es gibt mindestens ein x, für das gilt: Ax“

„es gibt kein x, für das gilt: Ax“

„für nicht alle x gilt: Ax“

Individualkonstanten (freie Individualvariablen)

stehen für ein Ding

werden in der Legende definiert

sind „freie“ Individualvariablen, da sie nicht an All-/Existenz-Quantor gebunden sind

Individualvariablen (gebundene Individualvariablen)

stehen für ein Ding

sind an All-/Existenz-Quantor gebunden

Prädikatenkonstanten (freie Prädikatenvariablen)

weisen Dingen Eigenschaften zu

werden in Legende definiert

sind „freie“ Prädikatenvariablen, da sie nicht an All-/Existenz-Quantor gebunden sind

Prädikatenvariablen (gebundene Prädikatenvariablen)

weisen Dingen Eigenschaften zu

sind an All-/Existenz-Quantor gebunden

Kalkül des natürlichen Schließens (siehe auch Formelsammlung)

Ein System zum Schlussfolgern durch gegebene Formeln (Prämissen) und Regeln.

Vorgehen mittels Tabelle (hier als Beispiel der Beweis des Modus Ponens):

Zeile	Formel	Regel	Angewandt auf	Abhängig von
1.		P		(1)
2.		P		(2)
3.			1, 2	(1, 2)

Vier Regeltypen: Prämisse (P), Annahme (A), Einführung (E), Beseitigung (B)

P: Alle Prämissen stehen ganz zu Anfang. Prämissen sind nur von sich selbst abhängig.

A: Beliebige Annahmen sind dann jederzeit möglich (man braucht sie oft für die E- und B-Regeln) und sind nur von sich selbst abhängig.

E, B: Diverse Regeln zur Einführung und Beseitigung von Junktoren.

Diese werden jeweils auf existierende Zeilen angewandt.

In Klammern wird die Abhängigkeit notiert. Das sind genau die Zeilennummern, die bei den von der Regel verwendeten Zeilen in Klammern stehen.

Steht bei der Regel eine Annahme in eckigen Klammern [], wird die der Annahme entsprechende Zeilennummer aus der Abhängigkeit gestrichen.

Eine Zeile lässt sich aus genau den Zeilen folgern, von denen sie abhängt.

Hinweise zu Quantorenlogischen Erweiterungen:

Alle Quantorenlogik ist Prädikatenlogik.

Das Quantifizieren über Prädikate ist eine Prädikatenlogik höherer Stufe.

Semantische Bäume (siehe auch Formelsammlung)

Eine indirekte Beweismethode. Die zu beweisende Formel wird negiert und ein Widerspruch hergeleitet. Wenn die negierte Formel immer falsch ist, dann ist die Formel selbst eine Tautologie (immer wahr).

Die negierte Formel wird gemäß der Entwicklungsregeln für die Semantischen Bäume „entwickelt“:

Entwickelte Formeln werden abgehakt (auf jede Formel passt nur eine einzige Regel).

Es können mehrere Verzweigungen entstehen:

Zweige, die auf einen Widerspruch (X) enden, werden nicht weiter entwickelt.

Hat man einmal mehrere Zweige und entwickelt eine Formel, die vor einer Verzweigung steht, muss man die Entwicklungen in alle Zweige der Verzweigung schreiben.

Es spart also viel Schreibarbeit, wenn man zunächst alle Regeln anwendet, die nicht verzweigen.

Jeder Zweig muss schließlich mit einem Widerspruch (X) enden.

Ist das der Fall, dann ist die negierte Formel immer falsch, also ist die Formel eine Tautologie. (Es müssen übrigens nicht alle Formeln im Baum abgehakt sein.)

Wenn sich nicht für alle Zweige Widersprüche entwickeln lassen, dann ist die Formel keine Tautologie.

Hinweise zu Quantorenlogischen Erweiterungen:

Erweitert die Semantischen Bäume hinsichtlich der Prädikatenlogik.

Es lassen sich dann also auch Formeln der Prädikatenlogik beweisen.

Beispiele

Einen Syllogismus aus dessen Namen heraus aufschreiben

barbara (1. Figur)

1. Figur, z.B.

Beweis eines Syllogismus mittels Venn-Diagramm

celarent (1. Figur)

bocardo (3. Figur)

Zurückführen eines Syllogismus auf die erste Figur

darapti (3. Figur)

darapti darii

baroco (2. Figur)

baroco barbara

dimaris (4. Figur)

dimaris darii

Bedeutungen der Junktoren

nur wahr wenn F falsch

nur wahr wenn beide wahr

nur falsch wenn beide falsch

nur falsch wenn F wahr aber G falsch

nur wahr wenn F derselbe Wahrheitswert wie G zukommt

Belegungskombinationen einer Wahrheitstafel

F	G	H
1	1	1
1	1	0
1	0	1
1	0	0
0	1	1
0	1	0
0	0	1
0	0	0

Eine Wahrheitstafel mit n verschiedenen Formelvariablen hat 2n Zeilen. Um alle Belegungen zu finden, gibt es zwei einfache Möglichkeiten, die auf das selbe Ergebnis hinauslaufen:

Binärzahl-Methode: Man zählt im 2er-Zahlensystem von nach

1-0-Abwechsel-Methode (einfach): Man belegt die Spalte der letzten Formelvariablen abwechselnd mit 1 und 0. Dann geht man zur Spalte der vorigen Formelvariablen und wechselt jeweils erst nach zwei Zeilen ab. Das macht man Spalte für Spalte und verdoppelt jeweils die Anzahl der Zeilen, nach denen man sich abwechselt.

Im Beispiel links gibt es 3 Formelvariablen, also 23 = 2*2*2 = 8 Zeilen.

Wenn eine Formelvariable mehrmals vorkommt, markiert man sich am besten das erste Auftauchen jeder Formelvariablen und befüllt zunächst nur diese Spalten. Dann „kopiert“ man die Einträge.

Ausrechnen einer Wahrheitstafel

Am Beispiel der Formel. Belegung mittels obiger 1-0-Abwechsel-Methode.

F	Ù	G	Þ	F
		1		
		0		
		1		
		0		

G ist die letzte Formelvariable.

F	Ù	G	Þ	F
1		1		
1		0		
0		1		
0		0		

F ist die zweitletzte Formelvariable.

F	Ù	G	Þ	F
1		1		1
1		0		1
0		1		0
0		0		0

Kopieren der Spalte F.

F	Ù	G	Þ	F
1	1	1		1
1	0	0		1
0	0	1		0
0	0	0		0

Innerste Junktoren zuerst ausrechnen.

F	Ù	G	Þ	F
1	1	1	1	1
1	0	0	1	1
0	0	1	1	0
0	0	0	1	0

Oberster Junktor ist immer 1, also ist die Formel gültig.

Beweis durch Umformung

Die Formel lässt sich auch durch Umformung beweisen:

Das Ergebnis ist hier eine Formel in DNF. Zwischen und besteht ein kontradiktorischer Gegensatz, also ist die Formel gültig.

Beweis durch das Kalkül des natürlichen Schließens

Beweis des Modus Tollens

1.		P(1)
2.		P(2)
3.		A(3)
4.		1, 3 (1, 3)
5.		2, 4 (1, 2, 3)
6.		3, 5 (1, 2, 3)

Beweis des Syllogismus barbara (1. Figur)

1.		P(1)
2.		P(2)
3.		1 (1)
4.		2 (2)
5.		A(5)
6.		4, 5 (2, 5)
7.		6, 3 (1, 2, 5)
8.		5, 7 (1, 2, 5)
9.		8 (1, 2)

Beweis des Syllogismus bocardo (3. Figur)

1.		P(1)
2.		P(2)
3.		A(3)
4.		2 (2)
5.		3 (3)
6.		4, 5 (2, 3)
7.		3 (3)
8.		6, 7 (2, 3)
9.		8 (2, 3)
10.		1, 3, 9 (1, 2, 3)

Beweis mittels Semantischen Bäumen

Beweis von

Beweis von

Beweis von

Beweis von disamis (3. Figur)

Hierzu werden alle Prämissen sowie die negierte Conclusio als Regel eingeführt, denn es gilt:

–9–

Manuel Haim

2005-07-02T17:07:01