243
Vorlesung Logiksysteme Teil 1: Aussagenlogik Martin Mundhenk Univ. Jena, Institut f¨ ur Informatik 10. M¨ arz 2020 v11 Wintersemester 2019/20

Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

  • Upload
    others

  • View
    3

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Vorlesung LogiksystemeTeil 1: Aussagenlogik

Martin Mundhenk

Univ. Jena, Institut fur Informatik

10. Marz 2020

v11

Wintersemester 2019/20

Page 2: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einleitung: Uber Sinn und Form

Symbolisches Addieren Al-Chwarizmi (etwa 783–850)

Problem: Was ist

MMMDCCCXCIX plus CMLIV ??

Page 3: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einleitung: Uber Sinn und Form

Symbolisches Addieren Al-Chwarizmi (etwa 783–850)

Problem: Was ist

MMMDCCCXCIX plus CMLIV ??

Abhilfe:I Dezimaldarstellung

= eine Sprache fur Zahlen

I erlaubt symbolisches Addieren

7 8 2 2 4

+ 1 3 8 1 2

9 2 0 3 6

Page 4: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Additionen kann man puzzeln

I Grundwahrheiten (Axiome) . . . sind wie Puzzlestucke.

211

936

376

055

311

742

476

999

1

+ +

I Regeln . . . korrektes Zusammenlegen zu einer schonen Form. . .

Beispiel:

1

+

Jede korrekte Addition lasst sich puzzeln!

Geht das auch fur die ganze Mathematik?

Page 5: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Additionen kann man puzzeln

I Grundwahrheiten (Axiome) . . . sind wie Puzzlestucke.

211

936

376

055

311

742

476

999

1

+ +

I Regeln . . . korrektes Zusammenlegen zu einer schonen Form. . .

Beispiel:

999

1

+

Jede korrekte Addition lasst sich puzzeln!

Geht das auch fur die ganze Mathematik?

Page 6: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Additionen kann man puzzeln

I Grundwahrheiten (Axiome) . . . sind wie Puzzlestucke.

211

936

376

055

311

742

476

999

1

+ +

I Regeln . . . korrektes Zusammenlegen zu einer schonen Form. . .

Beispiel:

376

999

1

+

Jede korrekte Addition lasst sich puzzeln!

Geht das auch fur die ganze Mathematik?

Page 7: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Additionen kann man puzzeln

I Grundwahrheiten (Axiome) . . . sind wie Puzzlestucke.

211

936

376

055

311

742

476

999

1

+ +

I Regeln . . . korrektes Zusammenlegen zu einer schonen Form. . .

Beispiel:

211

376

999

1

+

Jede korrekte Addition lasst sich puzzeln!

Geht das auch fur die ganze Mathematik?

Page 8: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Additionen kann man puzzeln

I Grundwahrheiten (Axiome) . . . sind wie Puzzlestucke.

211

936

376

055

311

742

476

999

1

+ +

I Regeln . . . korrektes Zusammenlegen zu einer schonen Form. . .

Beispiel:

742

211

376

999

1

+

Jede korrekte Addition lasst sich puzzeln!

Geht das auch fur die ganze Mathematik?

Page 9: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Additionen kann man puzzeln

I Grundwahrheiten (Axiome) . . . sind wie Puzzlestucke.

211

936

376

055

311

742

476

999

1

+ +

I Regeln . . . korrektes Zusammenlegen zu einer schonen Form. . .

Beispiel:

055

742

211

376

999

1

+

Jede korrekte Addition lasst sich puzzeln!

Geht das auch fur die ganze Mathematik?

Page 10: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Additionen kann man puzzeln

I Grundwahrheiten (Axiome) . . . sind wie Puzzlestucke.

211

936

376

055

311

742

476

999

1

+ +

I Regeln . . . korrektes Zusammenlegen zu einer schonen Form. . .

Beispiel:

936

055

742

211

376

999

1

+

Jede korrekte Addition lasst sich puzzeln!

Geht das auch fur die ganze Mathematik?

Page 11: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Additionen kann man puzzeln

I Grundwahrheiten (Axiome) . . . sind wie Puzzlestucke.

211

936

376

055

311

742

476

999

1

+ +

I Regeln . . . korrektes Zusammenlegen zu einer schonen Form. . .

Beispiel:

211

936

055

742

211

376

999

1

+

Jede korrekte Addition lasst sich puzzeln!

Geht das auch fur die ganze Mathematik?

Page 12: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Additionen kann man puzzeln

I Grundwahrheiten (Axiome) . . . sind wie Puzzlestucke.

211

936

376

055

311

742

476

999

1

+ +

I Regeln . . . korrektes Zusammenlegen zu einer schonen Form. . .

Beispiel:

211

936

055

742

211

376

999

1

+

Jede korrekte Addition lasst sich puzzeln!

Geht das auch fur die ganze Mathematik?

Page 13: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Hilberts Programm (1920)Hilbert (1862-1943)

Aufgabe 1:

finde einen streng formalisierten Kalkul mit

einfachen unmittelbar einleuchtenden Axiomen,

der die Mathematik und Logik auf eine gemeinsame,

nachweisbar konsistente Basis stellt

d.h. finde die Puzzlestucke fur das Mathe-Puzzle

und beweise, dass das stimmt.

Page 14: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Godels Unvollstandigkeitssatz (1931)Godel (1906-1978)

Hilberts Aufgabe 1

hat keine Losung!

(Es gibt kein Mathe-Puzzle. . . )

(Das wird in der VL Logik und Beweisbarkeit betrachtet . . . )

Page 15: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Hilberts Entscheidungsproblem (1927)Hilbert (1862-1943)

Aufgabe 2:

finde einen streng formalisierten Kalkul (Axiome & Regeln)

mit einfachen unmittelbar einleuchtenden Axiomen, mit dem

man jede wahre (pradikaten-)logische Formel beweisen kann.

I Finde Puzzlestucke, aus denen man alle wahren

pradikatenlogischen Formeln puzzeln kann.

X(Vollstandigkeitssatz, Godel 1930)

I Finde Puzzlestucke, aus denen man alle wahren

aussagenlogischen Formeln puzzeln kann.

X(Vollstandigkeitssatz, Post 1920)

Page 16: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Hilberts Entscheidungsproblem (1927)Hilbert (1862-1943)

Aufgabe 2:

finde einen streng formalisierten Kalkul (Axiome & Regeln)

mit einfachen unmittelbar einleuchtenden Axiomen, mit dem

man jede wahre (pradikaten-)logische Formel beweisen kann.

I Finde Puzzlestucke, aus denen man alle wahren

pradikatenlogischen Formeln puzzeln kann.

X(Vollstandigkeitssatz, Godel 1930)

I Finde Puzzlestucke, aus denen man alle wahren

aussagenlogischen Formeln puzzeln kann.

X(Vollstandigkeitssatz, Post 1920)

Page 17: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Hilberts Entscheidungsproblem (1927)Hilbert (1862-1943)

Aufgabe 2:

finde einen streng formalisierten Kalkul (Axiome & Regeln)

mit einfachen unmittelbar einleuchtenden Axiomen, mit dem

man jede wahre (pradikaten-)logische Formel beweisen kann.

I Finde Puzzlestucke, aus denen man alle wahren

pradikatenlogischen Formeln puzzeln kann. X(Vollstandigkeitssatz, Godel 1930)

I Finde Puzzlestucke, aus denen man alle wahren

aussagenlogischen Formeln puzzeln kann.

X(Vollstandigkeitssatz, Post 1920)

Page 18: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Hilberts Entscheidungsproblem (1927)Hilbert (1862-1943)

Aufgabe 2:

finde einen streng formalisierten Kalkul (Axiome & Regeln)

mit einfachen unmittelbar einleuchtenden Axiomen, mit dem

man jede wahre (pradikaten-)logische Formel beweisen kann.

I Finde Puzzlestucke, aus denen man alle wahren

pradikatenlogischen Formeln puzzeln kann. X(Vollstandigkeitssatz, Godel 1930)

I Finde Puzzlestucke, aus denen man alle wahren

aussagenlogischen Formeln puzzeln kann. X(Vollstandigkeitssatz, Post 1920)

Page 19: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Zitate

Edsger W. Dijkstra:

Informatik = VLSAL

(Very Large Scale Application of Logics)

Georg Gottlob:

Informatik ist die Fortsetzung der Logik mit anderen Mitteln.

Page 20: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Inhalt dieser Vorlesung

I Was wird betrachtet?

1. Formale Aussagenlogik

2. Nicht-klassische formale AussagenlogikenI ModallogikI mehrwertige Logik, temporale Logik, intuitionistische Logik oder . . .

I Wie wird es betrachtet?

Verschiedene Beweissysteme (”Puzzle“) und deren Vollstandigkeit

I Wie lassen sich”wahre“ Formeln formal/algorithmisch beschreiben?

I Ziel: Verinnerlichung der Idee, was ein Beweis ist;

Verstandnis unterschiedlicher Logiken und Beweissysteme,

ihrer Vollstandigkeitsbeweise

und Befahigung zum selbstandigen Fuhren”kleiner“ Beweise

Page 21: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Vorlesung Logiksysteme (Winter 2019/20)

1. AussagenlogikVL01: Umgangssprachliche und formale AussagenlogikVL02: Adaquate Verknupfungszeichen, erfullbare und gultige Formeln

VL03: Ein Tableau-KalkulVL04: Ein Frege-KalkulVL05: Die Vollstandigkeitssatze fur die KalkuleVL08: Frege-Kalkul fur ModallogikVL09: Exkurs und Abschluss

Page 22: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Formalien zur Vorlesung/Ubung

I Termine:

Ubung montags 14:15-15:45

Vorlesung dienstags 14:15-15:45

Logik-Cafe freitags 10-12 Uhr (und n.V.)

I Zulassungsvoraussetzung zur Modulprufung:

80% der Ubungsaufgaben wurden”bestanden“

(Abgabe spatestens montags vor der Ubung,

Nachbesserung punktlich abgegebener Losungen ist moglich)

aktive Teilnahme an den Ubungen

I Modulprufung:

mundliche Prufung in der vorlesungsfreien Zeit

Termine werden bekanntgegeben

Page 23: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Die Grammatik des Lernens (Klaus Zierer)

1. Lernen erfordert Anstrengung und Einsatz

Der Mensch braucht 6-8 Wiederholungen,

damit etwas vom Kurzzeit- ins Langzeitgedachtnis kommt.

2. Lernen ist eine Herausforderung

Lernen ist nicht leicht.

Es gibt die Moglichkeit des Erfolges und die Moglichkeit des Scheiterns.

3. Lernen erfordert positive Beziehungen

Wer lernt, braucht jemanden, der ihm/ihr den Spiegel vorhalt.

4. Lernen erfordert Motivation

Wer lernt, muss ein eigenes Interesse an der Sache haben.

5. Lernen erfordert Oberflachenverstandnis,um Tiefenverstandnis zu entwickeln

Wer lernt, muss Fakten kennen, um tiefere Erkenntnis zu gewinnen.

Page 24: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Teil 1: Aussagenlogik

1. AussagenlogikVL01: Umgangssprachliche und formale AussagenlogikVL02: Adaquate Verknupfungszeichen, erfullbare und gultige Formeln

VL03: Ein Tableau-KalkulVL04: Ein Frege-KalkulVL05: Die Vollstandigkeitssatze fur die Kalkule

[ Literatur (siehe Semesterapparat):

Schoning: Logik fur Informatiker VL01/02

Priest: An Introduction to Non-classical Logic VL01/02/03/05

Mendelson: Introduction to Mathematical Logic VL04/05 ]

Teil 1 Inhaltsverzeichnis

Page 25: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

1.1+2 Grundbegriffe der Aussagenlogik

Zuerst werden wir uns aussagenlogische Konstrukte in der Umgangssprache anschauen.

Dann werden die Grundbegriffe der (formalen) Aussagenlogik definiert:

I Wie sehen aussagenlogische Formeln aus?

I Was ist eine Belegung und wann erfullt sie eine Formel?

I Wann sind Formeln aquivalent?

I Welche Verknupfungszeichen braucht man uberhaupt in Formeln? (adaquate

Verknupfungszeichen)

I Was sind gultige, erfullbare und unerfullbare Formeln?

VL 1+2 Ubersicht

Page 26: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Vorlesung 1:

Umgangssprachliche und formale Aussagenlogik

Wir benutzen Logik in der Umgangssprache.Daraus hat sich die formale Logik entwickelt.

Wir wollen uns klarmachen, wann wir umgangssprachliche Logik und wann wir formale Logikbenutzen.

1. AussagenlogikVL01: Umgangssprachliche und formale Aussagenlogik

Umgangssprachliche Aussagenlogik

Formale Aussagenlogik

VL02: Adaquate Verknupfungszeichen, erfullbare und gultige Formeln

VL03: Ein Tableau-KalkulVL04: Ein Frege-KalkulVL05: Die Vollstandigkeitssatze fur die Kalkule

1.1.1

Page 27: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

1.1 Umgangssprachliche AussagenlogikEinfuhrendes Beispiel

Aussagenlogik betrachtet Aussagen und deren Zusammensetzung,

und untersucht das korrekte Schlussfolgern.

Beispiel:

(1) Ingo trifft Peter oder Maria.

(2) Wenn er Peter trifft, dann trifft er Vera oder Andreas.

(3) Wenn er Vera trifft, dann trifft er auch Maria.

(4) Wenn er Vera nicht trifft, dann trifft er nicht Andreas.

Ist”Ingo trifft Maria“ eine korrekte Folgerung aus (1)–(4)?

1.1.2

Page 28: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Aussagen

Eine umgangssprachliche Aussage ist ein Satz, der entweder wahr oder falsch ist.

Aus einzelnen Aussagen konnen neue Aussagen gebildet werden,

indem Aussagen sprachlich so verknupft werden,

dass neue Aussagen entstehen.

Ob die neue Aussage wahr oder falsch ist,

ergibt sich aus den Wahrheitswerten der Aussagen,

aus denen sie gebildet wird.

Dazu geben wir fur jede Verknupfung in einer Wahrheitswertetabelle an,

wie sich der Wahrheitswert der neuen Aussage

aus den Wahrheitswerten der verknupften Aussagen ergibt.

1.1.3

Page 29: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Umgangssprachliche Negation

Die Negation einer umgangssprachlichen Aussage x ist”Nicht x“.

Die Negation der Aussage z = 2 schreibt man auch z 6= 2.

Diese”Negation durch Durchstreichen“ macht man gerne mit formalen Symbolen.

Das werden wir spater auch so machen.

Wenn die Aussage x wahr ist, dann ist die Aussage”Nicht x“ falsch,

und wenn x falsch ist, dann ist”Nicht x“ wahr.

Das schreiben wir als Wahrheitswertetabelle auf:

x Nicht x

wahr falsch

falsch wahr

1.1.4

Page 30: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Umgangssprachliche Konjunktion

Die Konjunktion zweier umgangssprachlicher Aussagen x und y

ist die Aussage”x und y“.

Zum schnellen oder kurzen Aufschreiben schreibt man”x und y“ auch als

”x & y“.

Die Wahrheitswertetabelle fur die Konjunktion ist:

x y x und y

wahr wahr wahr

wahr falsch falsch

falsch wahr falsch

falsch falsch falsch

1.1.5

Page 31: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Umgangssprachliche Disjunktion

Die Disjunktion zweier umgangssprachlicher Aussagen x und y

ist die Aussage”x oder y“.

Die Wahrheitswertetabelle fur die Disjunktion ist:

x y x oder y

wahr wahr wahr

wahr falsch wahr

falsch wahr wahr

falsch falsch falsch

Man beachte, dass die Bedeutung der Aussage”Entweder x oder y“ anders ist als die von

”x oder y“.

1.1.6

Page 32: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Umgangssprachliche Implikation

Die Implikation einer ugs. Aussage y aus einer ugs. Aussage x

ist die Aussage”Wenn x , dann y“ oder

”Aus x folgt y“.

Zum schnellen oder kurzen Aufschreiben schreibt man

”Wenn x , dann y“ auch als

”x ⇒ y“.

Die Wahrheitswertetabelle fur die Implikation ist:

x y wenn x , dann y

wahr wahr wahr

wahr falsch falsch

falsch wahr wahr

falsch falsch wahr

1.1.7

Page 33: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Umgangssprachliche Aquivalenz

Die Aquivalenz zweier ugs. Aussagen x und y

ist die Aussage”x genau dann, wenn y“.

Zum schnellen oder kurzen Aufschreiben schreibt man

”x genau dann, wenn y“ auch als

”x gdw. y“ oder als

”x ⇔ y“.

Die Wahrheitswertetabelle fur die Aquivalenz ist:

x y x genau dann, wenn y

wahr wahr wahr

wahr falsch falsch

falsch wahr falsch

falsch falsch wahr

1.1.8

Page 34: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Aquivalente Aussagen

Die folgende Aussage ist wahr fur alle ugs. Aussagen x und y :

”nicht ‘x und y ’“ gdw.

”‘nicht x ’ oder ‘nicht y ’“.

x y x und y nicht ‘x und y ’ ‘nicht x ’ ‘nicht y ’ ‘nicht x ’ oder ‘nicht y ’wahr wahr wahr falsch falsch falsch falschwahr falsch falsch wahr falsch wahr wahrfalsch wahr falsch wahr wahr falsch wahrfalsch falsch falsch wahr wahr wahr wahr

”nicht ‘x und y ’“ gdw.

”‘nicht x ’ oder ‘nicht y ’“

wahrwahrwahrwahr

1.1.9

Page 35: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Das kann man entsprechend fur Negationen beliebig zusammengesetzter Aussagen machen

und kommt zu folgendem Ergebnis.

Zusammenfassung 1.1 (Aquivalenzen umgangssprachlicher Negationen)

Die folgenden Aussagen sind wahr fur alle ugs. Aussagen x und y:

1.”nicht nicht x“ gdw. x.

2.”nicht ‘x und y’“ gdw.

”‘nicht x’ oder ‘nicht y ’“.

3.”nicht ‘x oder y ’“ gdw.

”‘nicht x’ und ‘nicht y ’“.

4.”nicht ‘wenn x, dann y’“ gdw.

”x und nicht y“.

5.”nicht ‘x genau dann, wenn y’“ gdw.

genau eine der beiden Aussagen x bzw. y ist wahr (und die andere ist falsch).

Die Beweise fuhrt man – wie auf der vorherigen Folie – mittels Wahrheitstafeln.

1.1.10

Page 36: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Zusammenfassung 1.2 (Vertauschung der Reihenfolge (Kommutativitat))

Die folgenden Aussagen sind wahr fur alle ugs. Aussagen x und y:

1.”x und y“ gdw.

”y und x“

2.”x oder y“ gdw.

”y oder x“

Zusammenfassung 1.3 (Klammerung von und bzw. oder ist egal (Assoziativitat))

Die folgenden Aussagen sind wahr fur alle ugs. Aussagen x, y und z:

1.”‘x und y’ und z“ gdw.

”x und ‘y und z’“

2.”‘x oder y ’ oder z“ gdw.

”x oder ‘y oder z’“

Die Beweise fuhrt man – wie auf den vorherigen Folien – mittels Wahrheitstafeln.

1.1.11

Page 37: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Zusammenfassung 1.4 (Vermischung von ‘und’ und ‘oder’ (Distributivitat))

Die folgenden Aussagen sind wahr fur alle ugs. Aussagen x, y und z:

1.”x und ‘y oder z’“ gdw.

”‘x und y’ oder ‘x und z’“

2.”x oder ‘y und z’“ gdw.

”‘x oder y ’ und ‘x oder z’“

Zusammenfassung 1.5 (Absorption wahrer bzw. falscher Aussagen)

Die folgenden Aussagen sind wahr fur alle ugs. Aussagen x, alle wahren Aussagen w und

alle falschen Aussagen f :

1. x gdw.”x oder f “

2. x gdw.”x und w“

Die Beweise fuhrt man – wie auf den vorherigen Folien – mittels Wahrheitstafeln.1.1.12

Page 38: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Zuruck zum Anfangsbeispiel

(1) Ingo trifft Peter oder Maria. (P oder M.)(2) Wenn er Peter trifft, dann trifft er Vera oder Andreas.

(Wenn P, dann (V oder A).)(3) Wenn er Vera trifft, dann trifft er auch Maria. (Wenn V , dann M.)(4) Wenn er Vera nicht trifft, dann trifft er nicht Andreas.

(Wenn nicht V , dann nicht A.)

Ist”Ingo trifft Maria“ (M) eine Folgerung aus (1)–(4)?

D.h.: ist die”große“ Aussage

”Wenn (P oder M) und

(wenn P , dann (V oder A)) und

(wenn V , dann M) und

(wenn nicht V , dann nicht A),

dann M .“

wahr ? Dazu schauen wir uns die Wahrheitswertetabelle der großen Aussage an . . .1.1.13

Page 39: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

P M V A (1) (2) (3) (4) große Aussagewahr wahr wahr wahr wahr wahr wahr wahr wahrwahr wahr wahr falsch wahr wahr wahr wahr wahrwahr wahr falsch wahr wahr wahr wahr falsch wahrwahr wahr falsch falsch wahr falsch wahr wahr wahrwahr falsch wahr wahr wahr wahr falsch wahr wahrwahr falsch wahr falsch wahr wahr falsch wahr wahrwahr falsch falsch wahr wahr wahr wahr falsch wahrwahr falsch falsch falsch wahr falsch wahr wahr wahrfalsch wahr wahr wahr wahr wahr wahr wahr wahrfalsch wahr wahr falsch wahr wahr wahr wahr wahrfalsch wahr falsch wahr wahr wahr wahr falsch wahrfalsch wahr falsch falsch wahr wahr wahr wahr wahrfalsch falsch wahr wahr falsch wahr falsch wahr wahrfalsch falsch wahr falsch falsch wahr falsch wahr wahrfalsch falsch falsch wahr falsch wahr wahr falsch wahrfalsch falsch falsch falsch falsch wahr wahr wahr wahr

Also: die”große Aussage“ (

”Ingo trifft Maria“ ist eine Folgerung aus (1)–(4)) ist wahr!

1.1.14

Page 40: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

1.2 Formale Aussagenlogik

Die formale Aussagenlogik ist ein abstraktes Modell der umgangssprachlichen

Aussagenlogik.

Zuerst modelliert man die Zusammensetzung von Aussagen (Syntax).

Das ergibt die Formeln der Aussagenlogik (wie eine formale Sprache).

Anschließend modelliert man die Wahrheitswerte durch eine Erfullungsrelation (Semantik).

Abschließend werden semantische Eigenschaften von Formeln definiert und betrachtet.

1.1.15

Page 41: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Definition 1.1 (die Syntax der Aussagenlogik: Formeln)

Die Menge aller Atome ist eine abzahlbare Menge {A0,A1,A2, . . .}.

(Aussagenlogische) Formeln sind induktiv definiert wie folgt.

1. Die Konstanten > (verum) und ⊥ (falsum) und alle Atome sind Formeln.

2. Fur alle Formeln α ist ¬α (Negation von α) ebenfalls eine Formel.

Fur alle Formeln α und β sind

(α ∧ β) (Konjunktion von α und β, logisches Und ),

(α ∨ β) (Disjunktion von α und β, logisches Oder ) und

(α→ β) (Implikation von α und β, logisches Wenn . . . dann )

ebenfalls Formeln.

(3. Es gibt keine anderen Formeln.)

1.1.16

Page 42: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Wir haben gesehen,

wie die Form von ugs. Aussagen durch Formeln modelliert wird.

Nun brauchen wir noch eine Modellierung der Wahrheitswerte.

Dazu definieren wir die Belegung und die Erfullungsrelation.

Definition 1.2 (Belegung)

Eine Belegung B ist eine Menge B ⊆ {A0,A1,A2, . . .} von Atomen.

Der Wahrheitswert der Aussage”Ai ∈ B“ modelliert,

dass Ai fur eine wahre Aussage steht – bezogen auf die”Welt“ B.

Die Erfullungsrelation modelliert,

wie sich Wahrheitswerte in zusammengesetzten Aussagen ubertragen.

[Die Begriffe Aussage, Wahrheitswert, wahr und falsch werden in der formalen Logik nicht

verwendet!]

. . .1.1.17

Page 43: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Definition 1.3 (die Semantik der Aussagenlogik: die Erfullungsrelation )

Sei B eine Belegung, α und β seien Formeln.

Die Erfullungsrelation zwischen Belegungen und Formeln ist wie folgt definiert.

B >B 6 ⊥B Ai gdw. Ai ∈ B, fur atomare Formeln Ai

B ¬α gdw. B 6 α

B (α ∧ β) gdw. B α und B β

B (α ∨ β) gdw. B α oder B β

B (α→ β) gdw. B 6 α oder B β

Man spricht die Aussage”B ϕ“ als

”B erfullt ϕ“ aus.

Fur”Nicht B ϕ“ schreibt man

”B 6 ϕ“ (auch

”B erfullt ϕ nicht“).

1.1.18

Page 44: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Beispiel: {A0,A2,A4} ¬(A0 → A1) ∧ A2

Mit der Semantik der Aussagenlogik (Definition (1.3)) und Aquivalenzen ugs. Aussagenlogik(Zusammenfassung (1.1)) konnen wir folgende aquivalente Umformungen machen:

{A0,A2,A4} ¬(A0 → A1) ∧ A2

gdw. {A0,A2,A4} ¬(A0 → A1) und {A0,A2,A4} A2 (Semantik von ∧)

gdw. {A0,A2,A4} 6 A0 → A1 und {A0,A2,A4} A2 (Semantik von ¬)

gdw. nicht ‘{A0,A2,A4} 6 A0 oder {A0,A2,A4} A1’ und {A0,A2,A4} A2

(Semantik von →)

gdw. ‘nicht {A0,A2,A4} 6 A0 und nicht {A0,A2,A4} A1’ und {A0,A2,A4} A2

(ugs. (1.1)(3))

gdw. ‘{A0,A2,A4} A0 und {A0,A2,A4} 6 A1’ und {A0,A2,A4} A2 (ugs. (1.1)(1))

gdw. ‘A0 ∈ {A0,A2,A4} und A1 /∈ {A0,A2,A4}’ und A2 ∈ {A0,A2,A4}︸ ︷︷ ︸wahre Aussage

(Semantik von Ai )

Also ist {A0,A2,A4} ¬(A0 → A1) ∧ A2 eine wahre Aussage.

1.1.19

Page 45: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Beispiel: {A1} 6 (A0 → A1)→ (A1 → A0)

Mit der Semantik der Aussagenlogik (Definition (1.3)) und Aquivalenzen ugs. Aussagenlogik(Zusammenfassung (1.1)) konnen wir folgende aquivalente Umformungen machen:

{A1} (A0 → A1)→ (A1 → A0)

gdw. {A1} 6 A0 → A1 oder {A1} A1 → A0 (Semantik von →)

gdw. nicht ‘{A1} 6 A0 oder {A1} A1’ oder {A1} A1 → A0 (Semantik von →)

gdw. ‘{A1} A0 und {A1} 6 A1’ oder ‘{A1} 6 A1 oder {A1} A0’ (ugs. (1.1)(1,3))

gdw. ‘A0 ∈ {A1} und A1 /∈ {A1}’ oder ‘A1 /∈ {A1} oder A0 ∈ {A1}’︸ ︷︷ ︸falsche Aussage

(Semantik von Ai )

Also ist {A1} (A0 → A1)→ (A1 → A0) eine falsche Aussage.

D.h. {A1} 6 (A0 → A1)→ (A1 → A0) ist eine wahre Aussage.

1.1.20

Page 46: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 1.4

Seien α und β Formeln.

Fur jede Belegung B gilt:

B α→ β genau dann, wenn B ¬α oder B β.

Beweis:

Sei B eine beliebige Belegung.

Wir konnen die beiden Aussagen mit folgenden Schritten aquivalent ineinander umformen.

B α→ β

gdw. B 6 α oder B β (Semantik von →)

gdw. B ¬α oder B β (Semantik von ¬)

X

1.1.21

Page 47: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 1.5

Seien α und β Formeln.

Fur jede Belegung B gilt:

B 6 α→ β genau dann, wenn B α und B 6 β.

Beweis:

Sei B eine beliebige Belegung.

Wir konnen die beiden Aussagen mit folgenden Schritten aquivalent ineinander umformen.

B 6 α→ β

gdw. nicht”B 6 α oder B β“ (Semantik von →)

gdw. B α und B 6 β (ugs.)

X

1.1.22

Page 48: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Was haben wir in Vorlesung 1 gelernt?

I Wir haben die umgangssprachliche Aussagenlogik aus Aussagen, Aussageverknupfungen

”nicht“,

”und“,

”oder“,

”wenn . . . dann. . .“ und

”. . . genau dann, wenn . . .“ kennengelernt

und gesehen, wie sich die Wahrheitswerte”wahr“ und

”falsch“ von Aussagen auf

Aussageverknupfungen ubertragen.Das haben wir mit Hilfe von Wahrheitswertetabellen aufgeschrieben.

I Wir haben die formale Aussagenlogik kennengelernt.Wir kennen Formeln, die induktiv aus Atomen, ⊥, > und den Verknupfungszeichen ¬, ∧, ∨und → aufgebaut sind.Wir wissen, was eine Belegung ist,und kennen die Erfullungsrelation zwischen Belegungen und Formeln, die induktiv uberden Aufbau der Formeln definiert ist.

I Wichtig: wir wollen die Begriffe der umgangssprachlichen Logik mit denen der formalenLogik nicht durcheinanderbringen.

1.1.23

Page 49: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Vorlesung 2: Adaquate Verknupfungszeichen

und wichtige Eigenschaften von Formeln

Wir gehen der Frage nach, mit welchen Kombinationen der Verknupfungszeichen >, ⊥, ¬, ∧, ∨,→ man bereits alle Formeln aquivalent beschreiben kann. Wir werden eine Kombination finden,die uns spater das Beweisen leichter machen wird.

1. AussagenlogikVL01: Umgangssprachliche und formale AussagenlogikVL02: Adaquate Verknupfungszeichen, erfullbare und gultige Formeln

Aquivalente Formeln

Adaquate Verknupfungszeichen

Erfullbarkeit und Gultigkeit

VL03: Ein Tableau-KalkulVL04: Ein Frege-KalkulVL05: Die Vollstandigkeitssatze fur die Kalkule

1.2.1

Page 50: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

2.1 Aquivalente Formeln

Abkurzende Schreibweise: wir schreiben auch A,B,C , . . . fur A0,A1,A2, . . . .

Die Formeln (A ∧ B) und ¬(¬A ∨ ¬B) werden von den gleichen Belegungen erfullt.I Die Belegung {A,B} erfullt beide Formeln.

I Die Belegungen ∅, {A} und {B} erfullen beide Formeln nicht.

I Jede andere Belegung entspricht fur die Atome A und B einer der obigen Belegungen.

Definition 2.1 ((semantische) Aquivalenz von Formeln)

Seien α und β Formeln. Die Relation ≡ zwischen Formeln ist wie folgt definiert:α ≡ β (

”α ist aquivalent zu β“) genau dann, wenn

fur jede Belegung B gilt: B α genau dann, wenn B β.

Lemma 2.2 (≡ ist eine Aquivalenzrelation)

Die Relation ≡ ist reflexiv, symmetrisch und transitiv.

1.2.2

Page 51: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Aquivalenzen, die wir noch brauchen werden

Lemma 2.3

> ≡ ¬⊥

Beweis:

Zu zeigen ist: fur jede Belegung B gilt: B > gdw. B ¬⊥.

Gemaß Definition von gilt B > fur jede Belegung B.

Also bleibt zu zeigen: fur jede Belegung B gilt B ¬⊥.

Das zeigen wir, indem wir eine beliebige Belegung B0 nehmen und B0 ¬⊥ zeigen.

Sei B0 eine beliebige Belegung.

Dann gilt B0 6 ⊥ gemaß der Definition von .

Das ist aquivalent zu B0 ¬⊥ aufgrund der Semantik von ¬.

Folglich gilt B0 ¬⊥ ebenfalls. X1.2.3

Page 52: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 2.4

Fur jede Formel α gilt: ¬α ≡ α→ ⊥.

Beweis:

Sei α eine beliebige Formel.

Zu zeigen ist:

fur jede Belegung B gilt: B ¬α gdw. B α→ ⊥.

Sei B eine beliebige Belegung.

Dann gilt: B ¬α gdw. B 6 α (Semantik von ¬)

gdw. B 6 α oder B ⊥ (da B 6 ⊥, ugs.)

gdw. B α→ ⊥ (Semantik von →)

Damit ist”B ¬α gdw. B α→ ⊥“ gezeigt. X

Folgerung 2.5 (aus (2.3), (2.4 mit α = ⊥) und (2.2))

> ≡ ⊥ → ⊥1.2.4

Page 53: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 2.6

Fur alle Formeln α und β gilt: α ∨ β ≡ (α→ ⊥)→ β.

Beweis:

Seien α und β beliebige Formeln. Zu zeigen ist:

fur jede Belegung B gilt: B α ∨ β gdw. B (α→ ⊥)→ β.

Sei B eine beliebige Belegung.

Dann gilt:

B α ∨ β gdw. B α oder B β (Semantik von ∨)

gdw. nicht nicht B α oder B β (ugs. Doppelnegation)

gdw. B 6 ¬α oder B β (Semantik von ¬)

gdw. B 6 α→ ⊥ oder B β (Lemma (2.4))

gdw. B (α→ ⊥)→ β (Semantik von →)

Damit ist”B α ∨ β gdw. B (α→ ⊥)→ β“ gezeigt. X

1.2.5

Page 54: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 2.7

Fur alle Formeln α und β gilt: α ∧ β ≡ (α→ (β → ⊥))→ ⊥.

Beweis:

Seien α und β beliebige Formeln. Zu zeigen ist:

fur jede Belegung B gilt: B α ∧ β gdw. B (α→ (β → ⊥))→ ⊥.

Sei B eine beliebige Belegung. Dann gilt:

B α ∧ β gdw. B α und B β (Semantik von ∧)gdw. nicht nicht ‘B α und B β’ (ugs.)gdw. nicht

”B 6 α oder B 6 β“ (ugs.)

gdw. nicht”B 6 α oder B ¬β“ (Semantik von ¬)

gdw. nicht”B 6 α oder B β → ⊥“ (Lemma (2.4))

gdw. nicht”B α→ (β → ⊥)“ (Semantik von →)

gdw. B 6 α→ (β → ⊥) (Schreibweise)gdw. B ¬(α→ (β → ⊥)) (Semantik von ¬)gdw. B (α→ (β → ⊥))→ ⊥ (Lemma (2.4))

Damit ist”B α ∧ β gdw. B (α→ (β → ⊥))→ ⊥“ gezeigt. X

1.2.6

Page 55: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 2.8 (aquivalente Ersetzung von Teilformeln)

Seien α, β, α′ und β′ Formeln, und es gelte α ≡ α′ und β ≡ β′.Dann gilt:

1. ¬α ≡ ¬α′

2. α ∧ β ≡ α′ ∧ β′3. α ∨ β ≡ α′ ∨ β′

4. α→ β ≡ α′ → β′

Beweis:1. Seien α und α′ Formeln mit α ≡ α′.Zu zeigen ist: fur jede Belegung B gilt B ¬α gdw. B ¬α′.Sei B eine Belegung. Dann gilt:B ¬α gdw. B 6 α (Semantik von ¬)

gdw. B 6 α′ (da α ≡ α′, d.h. B α gdw. B α′)gdw. B ¬α′ (Semantik von ¬)

2.-4.: geht entsprechend. X

1.2.7

Page 56: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Definition 2.9 (Teilformeln)

Sei α eine Formel.

Die Menge Tf(α) aller Teilformeln von α ist definiert durch

Tf(α) =

{α}, falls α ein Atom ist

{α} ∪ Tf(β), falls α = ¬β

{α} ∪ Tf(β) ∪ Tf(γ),falls α = β ∧ γ, α = β ∨ γ

oder α = β → γ

Folgerung 2.10 (aus Lemma 2.8, Ersetzbarkeitstheorem)

Sei α eine Formel mit einer Teilformel β, und β ≡ β′.

Dann ist die Formel α′, die aus α entsteht, indem ein Vorkommen der Teilformel β durch

β′ ersetzt wird, aquivalent zu α.

1.2.8

Page 57: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

2.2 Adaquate Verknupfungszeichen

Definition 2.11 (adaquate Mengen von Verknupfungszeichen)

Eine Menge M ⊆ {>,⊥,¬,∧,∨,→, . . .} von Verknupfungszeichen heißt adaquat,

falls es fur jede Formel eine aquivalente Formel gibt, die nur aus Atomen sowie

Verknupfungszeichen aus M besteht.

Beispiel:

Da ((α→ ⊥)→ β) ≡ (α ∨ β) (2.6),

kann man alle Formeln aquivalent durch Formeln ohne ∨ ausdrucken.

Also ist {>,⊥,¬,∧,→} adaquat.

1.2.9

Page 58: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 2.12 ({⊥,→} ist adaquat)

{⊥,→} ist eine adaquate Menge von Verknupfungszeichen.

D.h. fur jede Formel ϕ gibt es eine aquivalente Formel ϕ′,

die nur aus Atomen, ⊥ und → besteht.

Beispiel fur die Umwandlung einer Formel:

¬(A ∧ B) ∨ ¬C≡ (¬(A ∧ B)→ ⊥)→ ¬C (2.6)

≡ (¬(A ∧ B)→ ⊥)→ (C → ⊥) (2.4)

≡ (((A ∧ B)→ ⊥)→ ⊥)→ (C → ⊥) (2.4)

≡ ((((A→ (B → ⊥))→ ⊥)→ ⊥)→ ⊥)→ (C → ⊥) (2.7)

Informelle Idee:wandle wiederholt Teilformeln mit ¬, ∨ und ∧ entsprechend (2.4), (2.6) und (2.7) um,bis die Formel nur noch aus Atomen, ⊥ und → besteht.

Formale Umsetzung:fuhre den Beweis mittels Induktion uber den Formelaufbau . . . 1.2.10

Page 59: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Der Beweis, dass alle Formeln die Eigenschaft E haben,

soll mittels Induktion uber den Formelaufbau gefuhrt werden.

Was ist zu zeigen?

(1) Die”Basisformeln“ >, ⊥ und alle Atome haben Eigenschaft E .

(2) Fur alle Formeln α und β gilt:

wenn α und β Eigenschaft E haben,

dann haben auch ¬α, α ∧ β, α ∨ β und α→ β Eigenschaft E .

[Aus (1) und (2) folgt: alle Formeln haben Eigenschaft E .]

Wie zeigt man es?

Zuerst zeigt man (1): das nennt man Induktionsanfang.

Anschließend zeigt man (2): das ist ein”fur alle“-Beweis, den man wie folgt fuhrt:

Man nimmt α und β beliebig (aber fest).

Man setzt voraus, dass α und β Eigenschaft E haben (Induktionsvoraussetzung).

Man zeigt, dass ¬α, α ∧ β, α ∨ β und α→ β Eigenschaft E haben (Induktionsschluss).1.2.11

Page 60: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Beweis: mittels Induktion uber den Formelaufbau der Formel ϕ.

Induktionsanfang:

Zu zeigen ist:

>, ⊥ und alle Atome besitzen aquivalente Formeln,

die nur aus Atomen, ⊥ und → bestehen.

Fall 1: > ist aquivalent zu ⊥ → ⊥ (2.5),

und ⊥ → ⊥ besteht nur aus Atomen, ⊥ und →.

Fall 2: ⊥ besteht bereits nur aus Atomen, ⊥ und →.

Fall 3: Ai besteht ebenfalls nur aus Atomen, ⊥ und →.

1.2.12

Page 61: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Beweis: mittels Induktion uber den Formelaufbau der Formel ϕ.

Induktionsanfang:

Zu zeigen ist:

>, ⊥ und alle Atome besitzen aquivalente Formeln,

die nur aus Atomen, ⊥ und → bestehen.

Fall 1: > ist aquivalent zu ⊥ → ⊥ (2.5),

und ⊥ → ⊥ besteht nur aus Atomen, ⊥ und →.

Fall 2: ⊥ besteht bereits nur aus Atomen, ⊥ und →.

Fall 3: Ai besteht ebenfalls nur aus Atomen, ⊥ und →.

1.2.12

Page 62: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Induktionsvoraussetzung (IV):α und β sind beliebige Formeln.α und β besitzen aquivalente Formeln α′ ≡ α bzw. β′ ≡ β,

die nur aus Atomen, ⊥ und → bestehen.

Induktionsschluss:

Zu zeigen ist: ¬α, (α ∧ β), (α ∨ β) und (α→ β) besitzen aquivalente Formeln,die nur aus Atomen, ⊥ und → bestehen.

Fall 1: zeige”¬α besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Es gilt: ¬α ≡ ¬α′ (IV und Lemma (2.8))

≡ α′ → ⊥ (Lemma (2.4))

Da in α′ laut IV nur Atome, ⊥ und → vorkommen,kommen in α′ → ⊥ nur Atome, ⊥ und → vor.

Da α′ → ⊥ auch aquivalent zu ¬α ist, ist α′ → ⊥ die gesuchte Formel.

1.2.13

Page 63: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Induktionsvoraussetzung (IV):α und β sind beliebige Formeln.α und β besitzen aquivalente Formeln α′ ≡ α bzw. β′ ≡ β,

die nur aus Atomen, ⊥ und → bestehen.

Induktionsschluss:

Zu zeigen ist: ¬α, (α ∧ β), (α ∨ β) und (α→ β) besitzen aquivalente Formeln,die nur aus Atomen, ⊥ und → bestehen.

Fall 1: zeige”¬α besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Es gilt: ¬α ≡ ¬α′ (IV und Lemma (2.8))

≡ α′ → ⊥ (Lemma (2.4))

Da in α′ laut IV nur Atome, ⊥ und → vorkommen,kommen in α′ → ⊥ nur Atome, ⊥ und → vor.

Da α′ → ⊥ auch aquivalent zu ¬α ist, ist α′ → ⊥ die gesuchte Formel.

1.2.13

Page 64: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Induktionsvoraussetzung (IV):α und β sind beliebige Formeln.α und β besitzen aquivalente Formeln α′ ≡ α bzw. β′ ≡ β,

die nur aus Atomen, ⊥ und → bestehen.

Induktionsschluss:

Zu zeigen ist: ¬α, (α ∧ β), (α ∨ β) und (α→ β) besitzen aquivalente Formeln,die nur aus Atomen, ⊥ und → bestehen.

Fall 1: zeige”¬α besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Es gilt: ¬α ≡ ¬α′ (IV und Lemma (2.8))

≡ α′ → ⊥ (Lemma (2.4))

Da in α′ laut IV nur Atome, ⊥ und → vorkommen,kommen in α′ → ⊥ nur Atome, ⊥ und → vor.

Da α′ → ⊥ auch aquivalent zu ¬α ist, ist α′ → ⊥ die gesuchte Formel.

1.2.13

Page 65: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall 2: zeige”α ∧ β besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Es gilt: α ∧ β ≡ α′ ∧ β′ (IV und Lemma (2.8))

≡ (α′ → (β′ → ⊥))→ ⊥ (Lemma (2.6))

Also ist (α′ → (β′ → ⊥))→ ⊥ aquivalent zu α ∧ β.Da in α′ und β′ laut IV nur Atome, ⊥ und → vorkommen,

kommen in (α′ → (β′ → ⊥))→ ⊥ nur Atome, ⊥ und → vor.

Fall 3: zeige”α ∨ β besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Es gilt: α ∨ β ≡ α′ ∨ β′ (IV und Lemma (2.8))

≡ (α′ → ⊥)→ β′ (Lemma (2.7))

Also ist (α′ → ⊥)→ β′ aquivalent zu α ∨ β.

Da in α′ und β′ laut IV nur Atome, ⊥ und → vorkommen,kommen in (α′ → ⊥)→ β nur Atome, ⊥ und → vor.

Fall 4: zeige”α→ β besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Dann ist α′ → β′ aquivalent zu α→ β (IV und Lemma (2.8)),und in α′ → β′ kommen gemaß IV nur Atome, ⊥ und → vor. X

1.2.14

Page 66: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall 2: zeige”α ∧ β besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Es gilt: α ∧ β ≡ α′ ∧ β′ (IV und Lemma (2.8))

≡ (α′ → (β′ → ⊥))→ ⊥ (Lemma (2.6))

Also ist (α′ → (β′ → ⊥))→ ⊥ aquivalent zu α ∧ β.Da in α′ und β′ laut IV nur Atome, ⊥ und → vorkommen,

kommen in (α′ → (β′ → ⊥))→ ⊥ nur Atome, ⊥ und → vor.

Fall 3: zeige”α ∨ β besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Es gilt: α ∨ β ≡ α′ ∨ β′ (IV und Lemma (2.8))

≡ (α′ → ⊥)→ β′ (Lemma (2.7))

Also ist (α′ → ⊥)→ β′ aquivalent zu α ∨ β.

Da in α′ und β′ laut IV nur Atome, ⊥ und → vorkommen,kommen in (α′ → ⊥)→ β nur Atome, ⊥ und → vor.

Fall 4: zeige”α→ β besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Dann ist α′ → β′ aquivalent zu α→ β (IV und Lemma (2.8)),und in α′ → β′ kommen gemaß IV nur Atome, ⊥ und → vor. X

1.2.14

Page 67: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall 2: zeige”α ∧ β besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Es gilt: α ∧ β ≡ α′ ∧ β′ (IV und Lemma (2.8))

≡ (α′ → (β′ → ⊥))→ ⊥ (Lemma (2.6))

Also ist (α′ → (β′ → ⊥))→ ⊥ aquivalent zu α ∧ β.Da in α′ und β′ laut IV nur Atome, ⊥ und → vorkommen,

kommen in (α′ → (β′ → ⊥))→ ⊥ nur Atome, ⊥ und → vor.

Fall 3: zeige”α ∨ β besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Es gilt: α ∨ β ≡ α′ ∨ β′ (IV und Lemma (2.8))

≡ (α′ → ⊥)→ β′ (Lemma (2.7))

Also ist (α′ → ⊥)→ β′ aquivalent zu α ∨ β.

Da in α′ und β′ laut IV nur Atome, ⊥ und → vorkommen,kommen in (α′ → ⊥)→ β nur Atome, ⊥ und → vor.

Fall 4: zeige”α→ β besitzt eine aquivalente Formel aus Atomen, ⊥ und →“.

Dann ist α′ → β′ aquivalent zu α→ β (IV und Lemma (2.8)),und in α′ → β′ kommen gemaß IV nur Atome, ⊥ und → vor. X

1.2.14

Page 68: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

{⊥,→} ist nicht die einzige adaquate Menge.

Satz 2.13 (Adaquate Mengen von Verknupfungszeichen)

Die folgenden Mengen von Verknupfungszeichen sind adaquat.

1. {⊥,→}2. {¬,∧}3. {¬,∨}4. {¬,→}

Die Beweise fur die anderen Mengen gehen ahnlich wie der Beweis von Lemma (2.12).

1.2.15

Page 69: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

2.3 Erfullbarkeit und Gultigkeit

Von besonderem Interesse sind Formeln,

die von jeder Belegung erfullt werden.

Definition 2.14 (gultig, erfullbar)

1. Eine Formel α heißt gultig (oder Tautologie),

wenn α von jeder Belegung erfullt wird (Schreibweise: α).

2. Eine Formel heißt erfullbar,

wenn es eine Belegung gibt, die sie erfullt.

Anderenfalls heißt die Formel unerfullbar (oder Kontradiktion).

Zur Ubung im Umgang mit den Begriffen beweisen wir ein paar Lemmas,

die wir spater gebrauchen werden.1.2.16

Page 70: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 2.15

Fur alle Formeln α und β gilt: α→ (β → α) ist gultig.

Beweis:Zu zeigen ist: fur jede Belegung B gilt B α→ (β → α).

Sei B eine Belegung. Es gilt:

B α→ (β → α) gdw. B 6 α oder B β → α (Sem. von →)

gdw. B 6 α oder B 6 β oder B α (Sem. von →)

gdw. B 6 α oder B α (ugs.)

Da”B 6 α oder B α“ eine wahre Aussage ist,

ist”B α→ (β → α)“ ebenfalls eine wahre Aussage.

1.2.17

Page 71: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 2.16

Fur alle Formeln α, β und ϕ gilt:

(α→(β→ϕ))→((α→β)→(α→ϕ)) ist gultig.

Beweis:

Zu zeigen ist:

fur jede Belegung B gilt B (α→(β→ϕ))→((α→β)→(α→ϕ)).

Wir werden benutzen, dass die Aussagen

”x oder ‘nicht x und y ’“ und

”x oder y“

aquivalent sind.

Das gleiche gilt fur die Aussagen

”x und ‘nicht x oder y ’“ und

”x und y“.

Das kann man sich z.B. mit Hilfe von Wahrheitstafeln klar machen.

1.2.18

Page 72: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Sei A eine Belegung.

Mit der Semantik von → und ugs. Logik kann man die Aussage wie folgt umformulieren:

B (α→(β→ϕ))→((α→β)→(α→ϕ))

gdw. B 6 α→(β→ϕ) oder B 6 α→β oder B 6 α oder B ϕ (Sem. →)

gdw. B ϕ oder ‘B α und B β und B 6 ϕ’

oder B 6 α oder ‘B α und B 6 β’ (Sem. →)

gdw. B ϕ oder ‘B α und B β’ oder B 6 α oder B 6 β (ugs.)

gdw. B ϕ oder B β oder B 6 α oder B 6 β (ugs.)

gdw. B β oder B 6 β (ugs.)

Da”B β oder B 6 β“ eine wahre Aussage ist,

ist”B (α→(β→ϕ))→((α→β)→(α→ϕ))“ ebenfalls eine wahre Aussage.

1.2.19

Page 73: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 2.17

Seien α und β Formeln.

Wenn α und α→ β gultig sind, dann ist auch β gultig.

Beweis:

Zu zeigen ist: wenn α und α→ β gultig sind, dann gilt fur jede Belegung B: B β.

Sei B eine Belegung.

Da α gultig ist, gilt B α.

Da α→ β gultig ist, gilt B α→ β.

Insgesamt gilt also B α und ‘B 6 α oder B β’.

Da B 6 α falsch ist, gilt B α und B β.

Folglich gilt B β.

1.2.20

Page 74: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Was haben wir in Vorlesung 2 gelernt?

I Wir kennen die Relation ≡ der Aquivalenz von Formeln.

I Wir wissen, wie man die Aquivalenz von Formeln beweisen kann.

I Wir wissen, dass {⊥,→} eine adaquate Mengen von Verknupfungszeichen ist und

konnen das mittels Induktion uber den Formelaufbau beweisen.

I Wir kennen weitere Mengen adaquater Verknupfungszeichen.

I Wir konnen mit den Begriffen erfullbar, gultig und unerfullbar umgehen.

1.2.21

Page 75: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

1.3–5 Zwei aussagenlogische Beweis-Kalkule

Wir wollen uberprufen, ob eine Formel α gultig ist.Wir wollen also eine semantische Eigenschaft von Formeln uberprufen.Jeder Beweis-Kalkul liefert ein Verfahren dafur.Diese Verfahren arbeiten rein syntaktisch – d.h. sie argumentieren nur uber die Struktur derFormeln.Wir werden zwei beispielhafte Kalkule kennenlernen:

I Tableau-Kalkul(die Formel wird auseinandergenommen, und die Einzelteile werden analysiert)

I Frege-Kalkul(die Formel wird aus Einzelteilen mit bekannten Eigenschaften zusammengesetzt)

Da Beweis-Kalkule syntaktisch arbeiten, der Begriff der Gultigkeit jedoch semantisch ist, istnicht offensichtlich, dass die beiden Kalkule genau die gultigen Formeln herausfinden. Deshalbmuss das abschließend bewiesen werden – und das ist die Hauptarbeit in diesen Vorlesungen.

1.2.1

Page 76: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Vorlesung 3: Ein Tableau-Kalkul

1. Aussagenlogik

VL01: Umgangssprachliche und formale Aussagenlogik

VL02: Adaquate Verknupfungszeichen, erfullbare und gultige Formeln

VL03: Ein Tableau-KalkulEinfuhrende Beispiele

Tableau

Tableau-Beweisbarkeit

Algorithmische Umsetzung

VL04: Ein Frege-Kalkul

VL05: Die Vollstandigkeitssatze fur die Kalkule

1.3.1

Page 77: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Fur jeden Pfad wird eine Belegung mit bestimmtenEigenschaften gesucht.α,+ bedeutet,

dass eine Belegung gesucht wird, die α erfullt.α,− bedeutet,

dass eine Belegung gesucht wird, die α nicht erfullt.

1.3.2

Page 78: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 79: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 80: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 81: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 82: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 83: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 84: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 85: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 86: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 87: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+

B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 88: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+

A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 89: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+

B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 90: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Expansionsregeln:

α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.2

Page 91: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.1 Einfuhrende Beispiele (1)

¬(A ∧ B) ∧ ¬(¬A ∧ ¬B),+

¬(A ∧ B),+

¬(¬A ∧ ¬B),+

A ∧ B,−

¬A ∧ ¬B,−

A,− B,−

¬A,− ¬B,− ¬A,− ¬B,−

A,+ B,+ A,+ B,+

Ein (analytisches) Tableau ist ein Baum, dessen Knoten mitFormeln sowie + oder − markiert sind.

Man beginnt mit einem Baum, der nur aus einer Wurzelbesteht. Der Baum wird entsprechend den Markierungen soexpandiert, dass die Pfade immer kleinere Teilformeln alsKnoten haben.

Ein Pfad heißt widerspruchlich,wenn er fur eine Formel α Markierungen α,+ und α,−

enthalt.Wenn ein Pfad nicht widerspruchlich ist, dann ist die Mengealler Atome Ai , die in Markierungen Ai ,+ auf dem Pfadvorkommen, eine Belegung, die alle Formeln auf dem Pfadentsprechend ihrer +/−-Markierung erfullt.

Erfullende Belegungen der Wurzel-Formel sind hier also:{B} und {A}.

1.3.2

Page 92: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (2)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),+:

¬(A ∧ ¬(A ∧ ¬B)),+ Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.3

Page 93: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (2)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),+:

¬(A ∧ ¬(A ∧ ¬B)),+

A ∧ ¬(A ∧ ¬B),−

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.3

Page 94: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (2)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),+:

¬(A ∧ ¬(A ∧ ¬B)),+

A ∧ ¬(A ∧ ¬B),−

A,− ¬(A ∧ ¬B),−

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.3

Page 95: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (2)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),+:

¬(A ∧ ¬(A ∧ ¬B)),+

A ∧ ¬(A ∧ ¬B),−

A,− ¬(A ∧ ¬B),−

A ∧ ¬B,+

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.3

Page 96: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (2)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),+:

¬(A ∧ ¬(A ∧ ¬B)),+

A ∧ ¬(A ∧ ¬B),−

A,− ¬(A ∧ ¬B),−

A ∧ ¬B,+

A,+

¬B,+

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.3

Page 97: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (2)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),+:

¬(A ∧ ¬(A ∧ ¬B)),+

A ∧ ¬(A ∧ ¬B),−

A,− ¬(A ∧ ¬B),−

A ∧ ¬B,+

A,+

¬B,+

B,−

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.3

Page 98: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (2)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),+:

¬(A ∧ ¬(A ∧ ¬B)),+

A ∧ ¬(A ∧ ¬B),−

A,− ¬(A ∧ ¬B),−

A ∧ ¬B,+

A,+

¬B,+

B,−

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

Erfullende Belegungen von ¬(A ∧ ¬(A ∧ ¬B)):

∅ und {A},und {B}

1.3.3

Page 99: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (3)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),−:

¬(A ∧ ¬(A ∧ ¬B)),− Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.4

Page 100: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (3)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),−:

¬(A ∧ ¬(A ∧ ¬B)),−

A ∧ ¬(A ∧ ¬B),+

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.4

Page 101: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (3)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),−:

¬(A ∧ ¬(A ∧ ¬B)),−

A ∧ ¬(A ∧ ¬B),+

A,+

¬(A ∧ ¬B),+

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.4

Page 102: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (3)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),−:

¬(A ∧ ¬(A ∧ ¬B)),−

A ∧ ¬(A ∧ ¬B),+

A,+

¬(A ∧ ¬B),+

A ∧ ¬B,−

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.4

Page 103: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (3)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),−:

¬(A ∧ ¬(A ∧ ¬B)),−

A ∧ ¬(A ∧ ¬B),+

A,+

¬(A ∧ ¬B),+

A ∧ ¬B,−

A,− ¬B,−

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.4

Page 104: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (3)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),−:

¬(A ∧ ¬(A ∧ ¬B)),−

A ∧ ¬(A ∧ ¬B),+

A,+

¬(A ∧ ¬B),+

A ∧ ¬B,−

A,− ¬B,−

B,+

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

1.3.4

Page 105: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einfuhrende Beispiele (3)

Ein Tableau fur ¬(A ∧ ¬(A ∧ ¬B)),−:

¬(A ∧ ¬(A ∧ ¬B)),−

A ∧ ¬(A ∧ ¬B),+

A,+

¬(A ∧ ¬B),+

A ∧ ¬B,−

A,− ¬B,−

B,+

Expansionsregeln:α ∧ β,+ :•

α,+

β,+

α ∧ β,− :•

α,− β,−

¬β,+ :•

β,−

¬β,− :•

β,+

Nicht-erfullende Belegungen von ¬(A ∧ ¬(A ∧ ¬B)):

{A,B}

1.3.4

Page 106: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Definition 3.1 (Tableau fur Formeln aus Atomen, ⊥ und →)

Sei ϕ eine Formel (aus Atomen, ⊥ und →).

1. Ein Knoten, der mit ϕ,+ bzw. ϕ,− markiert ist, ist ein Tableau fur ϕ,+ bzw. ϕ,−.

2. Sei T ein Tableau fur ϕ,+ oder ϕ,−, und v sei ein Knoten in T mit Markierung ψ,+bzw. ψ,−. Wenn ψ eine Formel der Form α→ β ist, dann kann v mit der jeweiligenExpansionsregel expandiert werden.

α→ β,+: •

α,− β,+

α→ β,−: •

α,+

β,−Expansion von v heißt:

an jedes Blatt von T , das von v aus erreicht werden kann, werdenKnoten angehangt, wie es in der Expansionsregel fur ψ beschrieben ist.In der Expansionsregel steht • fur das jeweilige Blatt.

Durch Expansion von v entsteht ein (weiteres) Tableau fur ϕ,+ bzw. ϕ,−.

1.3.5

Page 107: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

1.3.6

Page 108: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],− Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

1.3.6

Page 109: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],− Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

1.3.6

Page 110: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

1.3.6

Page 111: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

1.3.6

Page 112: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

1.3.6

Page 113: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

1.3.6

Page 114: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

1.3.6

Page 115: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

1.3.6

Page 116: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 117: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 118: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 119: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 120: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 121: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 122: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 123: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 124: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 125: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 126: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 127: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,−

α,+

⊥,−

¬α,−

α,+

1.3.6

Page 128: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,+

α,− ⊥,+

¬α,+

α,−

1.3.6

Page 129: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,+

α,− ⊥,+

¬α,+

α,−

1.3.6

Page 130: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,+

α,− ⊥,+

¬α,+

α,−

1.3.6

Page 131: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Abkurzung von . . . ist . . .¬α,+

α,− ⊥,+

¬α,+

α,−

1.3.6

Page 132: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

1.3.6

Page 133: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

¬A,− B,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

1.3.6

Page 134: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

¬A,− B,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

1.3.6

Page 135: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

¬A,− B,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

1.3.6

Page 136: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

¬A,− B,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

1.3.6

Page 137: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

¬A,− B,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

1.3.6

Page 138: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

¬A,− B,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

1.3.6

Page 139: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

¬A,− B,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

1.3.6

Page 140: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

¬A,− B,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

1.3.6

Page 141: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Systematischer Aufbau eines Tableaus

[(¬(A→ C )→ (B → C ))→ ((¬A→ B)→ C )],−

¬(A→ C )→ (B → C ),+

(¬A→ B)→ C ,−

¬(A→ C ),− B → C ,+

¬A→ B,+

C ,−

¬A→ B,+

C ,−

A→ C ,+

¬A,− B,+

A,− C ,+ A,− C ,+

A,+

B,− C ,+

¬A,− B,+

A,+

Jeder Knoten wird einmalexpandiert.

Der nachste zu expandierende

Knoten ist der erste (gemaß

pre-order) nicht-expandierte

Knoten des Baumes.

Widerspruchliche Pfade

werden nicht expandiert.

Belegungen, die die

Startformel nicht erfullen:

{B} und {A}.1.3.6

Page 142: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Definition 3.2 (Eigenschaften von Pfaden und Tableaux)

Ein Pfad durch ein Tableau heißt widerspruchlich, wenner ⊥,+ enthalt oder wenn er α,+ und α,− fur eine Formel α enthalt.

Ein Pfad durch ein Tableau heißt geschlossen,wenn er widerspruchlich ist oderwenn jeder seiner expandierbaren Knoten expandiert wurde.

Ein Tableau heißt geschlossen,wenn jeder Pfad durch das Tableau geschlossen ist.

Ein Tableau heißt widerspruchlich,wenn jeder Pfad durch das Tableau widerspruchlich ist.

1.3.7

Page 143: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Uns interessiert,

ob eine Formel ein widerspruchliches Tableau hat.

Wir werden sehen (Vollstandigkeitssatz fur den Tableau-Kalkul (5.11)):

I Formel α ist gultig genau dann,

wenn α,− ein widerspruchliches Tableau hat.

1.3.8

Page 144: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.3 Tableau-Beweisbarkeit

Wir definieren nun ein Beweissystem, das auf Tableaux basiert.

Da alle aussagenlogischen Formeln aquivalent zu Formeln aus Atomen, ⊥ und → sind, reicht esdabei, Tableaux fur solche Formeln zu definieren.

Ein Vorteil dieser Tableaux ist es,dass sie mit zwei Expansionsregeln auskommen.

Das macht alle Beweise von Eigenschaften von Tableaux einfacher(siehe Lemmas (3.4), (5.4), (5.7)).

1.3.9

Page 145: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Definition 3.3 (Tableau-beweisbar)

Sei α eine Formel.

α ist Tableau-beweisbar (Schreibweise:Tab

α),

wenn es ein widerspruchliches Tableau fur α,− gibt.

Wir werden zeigen (Satz (5.11)):

Fur jede Formel α gilt:Tab

α genau dann, wenn α.

Das heißt also:

α gdw. es ein widerspruchliches Tableau fur α,− gibt.

1.3.10

Page 146: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Bsp.:Tab

A→ (B → A)

Wir zeigenTab

α,

indem wir ein widerspruchliches Tableau fur α,− angeben:

A→ (B → A),−

A,+

B → A,−

B,+

A,−×

1.3.11

Page 147: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Bsp.:Tab

(A→ B)→ ((B → C )→ (A→ C ))

Wir zeigenTab

α, indem wir einwiderspruchliches Tableau fur α,−angeben:

(A→ B)→ ((B → C )→ (A→ C )),−

A→ B,+

(B → C )→ (A→ C ),−

B → C ,+

A→ C ,−

A,+

C ,−

A,− B,+

B,− C ,+×

× ×1.3.12

Page 148: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Expansionsregeln fur andere Verknupfungszeichen

Man kann Tableau-Kalkule fur Formelmengen mit”beliebigen“ Verknupfungszeichen

definieren.

Typ 1:α ∧ β,+ :•

α,+

β,+

α ∨ β,− :•

α,−

β,−

α→ β,− :•

α,+

β,−

¬α,+ :•

α,−

¬α,− :•

α,+

Typ 2:α ∧ β,− :•

α,− β,−

α ∨ β,+ :•

α,+ β,+

α→ β,+ :•

α,− β,+

1.3.13

Page 149: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Bsp:Tab¬((¬(A ∧ ¬B) ∧ ¬(B ∧ ¬C )) ∧ (A ∧ ¬C ))

Wir zeigenTab

α, indem wir

ein widerspruchliches Tableau

fur α,− angeben:

¬((¬(A ∧ ¬B) ∧ ¬(B ∧ ¬C)) ∧ (A ∧ ¬C)),−

(¬(A ∧ ¬B) ∧ ¬(B ∧ ¬C)) ∧ (A ∧ ¬C),+

¬(A ∧ ¬B) ∧ ¬(B ∧ ¬C),+

A ∧ ¬C ,+

¬(A ∧ ¬B),+

¬(B ∧ ¬C),+

A ∧ ¬B,−

B ∧ ¬C ,−

A,+

¬C ,+

A,− ¬B,−

B,+

B,− ¬C ,−

×

× ×

1.3.14

Page 150: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 3.4 (endliche Tableaux reichen)

Sei ϕ eine Formel (aus Atomen, ⊥ und →), und

‖ϕ‖ bezeichne die Anzahl von Vorkommen von Klammern, Atomen, ⊥ und → in ϕ.

ϕ,+ und ϕ,− haben geschlossene Tableaus mit 6 2‖ϕ‖ Knoten.

‖ϕ‖ steht fur die Lange von ϕ.

Beispiel fur ‖ϕ‖:‖(⊥ → (⊥ → ⊥))→ (A→ (⊥ → A))‖ = 19

1.3.15

Page 151: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Beweis:Wir schreiben #Knoten(ϕ, ∗)

fur die Anzahl der Knoten im kleinsten geschlossenen Tableau fur ϕ, ∗.Das Lemma sagt also aus: fur alle Formeln ϕ gilt #Knoten(ϕ, ∗) 6 2‖ϕ‖.

Wir werden eine Eigenschaft naturlicher Zahlen benutzen:

Behauptung: Wenn a, b > 2, dann ist a + b 6 a · b.

Beweis der Behauptung:Seien a, b > 2.Dann gilt

a + b 6

{a · 2, falls b 6 a2 · b, falls a < b

}6 a · b .

Wir zeigen das Lemma mittels Induktion uber den Formelaufbau von ϕ.IA: ϕ ist ein Atom oder ⊥.Dann kann weder ϕ,+ noch ϕ,− expandiert werden,und es gilt #Knoten(ϕ, ∗) = 1 6 2‖ϕ‖.

1.3.16

Page 152: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

IV: Fur beliebige Formeln γ und δ gilt

#Knoten(γ,+) 6 2‖γ‖ und #Knoten(γ,−) 6 2‖γ‖, sowie

#Knoten(δ,+) 6 2‖δ‖ und #Knoten(δ,−) 6 2‖δ‖.

IS: zu zeigen ist:

#Knoten( (γ → δ) ,+) 6 2‖(γ→δ)‖ und

#Knoten( (γ → δ) ,−) 6 2‖(γ→δ)‖.

1.3.17

Page 153: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall (1):Abschatzung von #Knoten( (γ → δ) ,−).

(γ → δ),−

Wir konstruieren ein geschlossenes Tableau fur(γ → δ),−, indem wir

(1) zuerst (γ → δ),− expandieren,(2) anschließend γ,+ zu einemgeschlossenen Tableau expandieren, und(3) abschließend an jedem Blatt desTableaus δ,− zu einem geschlossenenTableau expandieren.Dann gilt:

#Knoten( (γ → δ) ,−)Konstr .6 #Knoten(γ,+) ·#Knoten(δ,−) + 2IV6 2‖γ‖ · 2‖δ‖ + 2Beh.6 2‖γ‖ · 2‖δ‖ · 2= 2‖γ‖+‖δ‖+1

6 2‖(γ→δ)‖

1.3.18

Page 154: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall (1):Abschatzung von #Knoten( (γ → δ) ,−).

(γ → δ),−

Wir konstruieren ein geschlossenes Tableau fur(γ → δ),−, indem wir(1) zuerst (γ → δ),− expandieren,

(2) anschließend γ,+ zu einemgeschlossenen Tableau expandieren, und(3) abschließend an jedem Blatt desTableaus δ,− zu einem geschlossenenTableau expandieren.Dann gilt:

#Knoten( (γ → δ) ,−)Konstr .6 #Knoten(γ,+) ·#Knoten(δ,−) + 2IV6 2‖γ‖ · 2‖δ‖ + 2Beh.6 2‖γ‖ · 2‖δ‖ · 2= 2‖γ‖+‖δ‖+1

6 2‖(γ→δ)‖

1.3.18

Page 155: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall (1):Abschatzung von #Knoten( (γ → δ) ,−).

(γ → δ),−

γ,+

δ,−

Wir konstruieren ein geschlossenes Tableau fur(γ → δ),−, indem wir(1) zuerst (γ → δ),− expandieren,

(2) anschließend γ,+ zu einemgeschlossenen Tableau expandieren, und(3) abschließend an jedem Blatt desTableaus δ,− zu einem geschlossenenTableau expandieren.Dann gilt:

#Knoten( (γ → δ) ,−)Konstr .6 #Knoten(γ,+) ·#Knoten(δ,−) + 2IV6 2‖γ‖ · 2‖δ‖ + 2Beh.6 2‖γ‖ · 2‖δ‖ · 2= 2‖γ‖+‖δ‖+1

6 2‖(γ→δ)‖

1.3.18

Page 156: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall (1):Abschatzung von #Knoten( (γ → δ) ,−).

(γ → δ),−

γ,+

δ,−

Wir konstruieren ein geschlossenes Tableau fur(γ → δ),−, indem wir(1) zuerst (γ → δ),− expandieren,(2) anschließend γ,+ zu einemgeschlossenen Tableau expandieren, und

(3) abschließend an jedem Blatt desTableaus δ,− zu einem geschlossenenTableau expandieren.Dann gilt:

#Knoten( (γ → δ) ,−)Konstr .6 #Knoten(γ,+) ·#Knoten(δ,−) + 2IV6 2‖γ‖ · 2‖δ‖ + 2Beh.6 2‖γ‖ · 2‖δ‖ · 2= 2‖γ‖+‖δ‖+1

6 2‖(γ→δ)‖

1.3.18

Page 157: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall (1):Abschatzung von #Knoten( (γ → δ) ,−).

(γ → δ),−

γ,+

δ,−

geschlossenesTableaufur γ,+

Wir konstruieren ein geschlossenes Tableau fur(γ → δ),−, indem wir(1) zuerst (γ → δ),− expandieren,(2) anschließend γ,+ zu einemgeschlossenen Tableau expandieren, und

(3) abschließend an jedem Blatt desTableaus δ,− zu einem geschlossenenTableau expandieren.Dann gilt:

#Knoten( (γ → δ) ,−)Konstr .6 #Knoten(γ,+) ·#Knoten(δ,−) + 2IV6 2‖γ‖ · 2‖δ‖ + 2Beh.6 2‖γ‖ · 2‖δ‖ · 2= 2‖γ‖+‖δ‖+1

6 2‖(γ→δ)‖

1.3.18

Page 158: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall (1):Abschatzung von #Knoten( (γ → δ) ,−).

(γ → δ),−

γ,+

δ,−

geschlossenesTableaufur γ,+

Wir konstruieren ein geschlossenes Tableau fur(γ → δ),−, indem wir(1) zuerst (γ → δ),− expandieren,(2) anschließend γ,+ zu einemgeschlossenen Tableau expandieren, und(3) abschließend an jedem Blatt desTableaus δ,− zu einem geschlossenenTableau expandieren.

Dann gilt:

#Knoten( (γ → δ) ,−)Konstr .6 #Knoten(γ,+) ·#Knoten(δ,−) + 2IV6 2‖γ‖ · 2‖δ‖ + 2Beh.6 2‖γ‖ · 2‖δ‖ · 2= 2‖γ‖+‖δ‖+1

6 2‖(γ→δ)‖

1.3.18

Page 159: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall (1):Abschatzung von #Knoten( (γ → δ) ,−).

(γ → δ),−

γ,+

δ,−

geschlossenesTableaufur γ,+

geschlossenesTableau fur δ,−

geschlossenesTableau fur δ,−

· · ·

Wir konstruieren ein geschlossenes Tableau fur(γ → δ),−, indem wir(1) zuerst (γ → δ),− expandieren,(2) anschließend γ,+ zu einemgeschlossenen Tableau expandieren, und(3) abschließend an jedem Blatt desTableaus δ,− zu einem geschlossenenTableau expandieren.

Dann gilt:

#Knoten( (γ → δ) ,−)Konstr .6 #Knoten(γ,+) ·#Knoten(δ,−) + 2IV6 2‖γ‖ · 2‖δ‖ + 2Beh.6 2‖γ‖ · 2‖δ‖ · 2= 2‖γ‖+‖δ‖+1

6 2‖(γ→δ)‖

1.3.18

Page 160: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall (1):Abschatzung von #Knoten( (γ → δ) ,−).

(γ → δ),−

γ,+

δ,−

geschlossenesTableaufur γ,+

geschlossenesTableau fur δ,−

geschlossenesTableau fur δ,−

· · ·

Wir konstruieren ein geschlossenes Tableau fur(γ → δ),−, indem wir(1) zuerst (γ → δ),− expandieren,(2) anschließend γ,+ zu einemgeschlossenen Tableau expandieren, und(3) abschließend an jedem Blatt desTableaus δ,− zu einem geschlossenenTableau expandieren.Dann gilt:

#Knoten( (γ → δ) ,−)Konstr .6 #Knoten(γ,+) ·#Knoten(δ,−) + 2IV6 2‖γ‖ · 2‖δ‖ + 2Beh.6 2‖γ‖ · 2‖δ‖ · 2= 2‖γ‖+‖δ‖+1

6 2‖(γ→δ)‖1.3.18

Page 161: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall (2): Abschatzung von #Knoten( (γ → δ) ,+).Wir konstruieren ein geschlossenes Tableau fur (γ → δ),+, indem wir(1) zuerst (γ → δ),+ expandieren, und(2) anschließend γ,− und δ,+ zu geschlossenen Tableaux expandieren.

(γ → δ),+

γ,− δ,+

geschlossenesTableaufur γ,−

geschlossenesTableau fur δ,+

Dann gilt: #Knoten( (γ → δ) ,+)6 #Knoten(γ,−) + #Knoten(δ,+) + 1 (Konstruktion des Tableaus)

6 2‖γ‖ + 2‖δ‖ + 1 (IV)

6 2‖γ‖ + 2‖δ‖ + 2

6 2‖γ‖ · 2‖δ‖ · 2 (Beh.)

6 2‖(γ→δ)‖ X1.3.19

Page 162: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

[((A→ C ) ∨ (B → C ))→ ((A ∨ B)→ C )],−

(A→ C ) ∨ (B → C ),+

(A ∨ B)→ C ,−

A→ C ,+ B → C ,+

A ∨ B,+

C ,−

A ∨ B,+

C ,−

A,− C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 163: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

{((A→ C ) ∨ (B → C ))→ ((A ∨ B)→ C )−}

(A→ C ) ∨ (B → C ),+

(A ∨ B)→ C ,−

A→ C ,+ B → C ,+

A ∨ B,+

C ,−

A ∨ B,+

C ,−

A,− C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 164: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

{((A→ C ) ∨ (B → C ))→ ((A ∨ B)→ C )−}

{(A→ C ) ∨ (B → C )+, (A ∨ B)→ C−}

A→ C ,+ B → C ,+

A ∨ B,+

C ,−

A ∨ B,+

C ,−

A,− C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 165: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

{(A→ C ) ∨ (B → C )+, (A ∨ B)→ C−}

A→ C ,+ B → C ,+

A ∨ B,+

C ,−

A ∨ B,+

C ,−

A,− C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 166: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

{(A→ C ) ∨ (B → C )+, (A ∨ B)→ C−}

{A→ C+, (A ∨ B)→ C−} B → C ,+

A ∨ B,+

C ,−

A ∨ B,+

C ,−

A,− C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 167: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

{A→ C+, (A ∨ B)→ C−} B → C ,+

A ∨ B,+

C ,−

A ∨ B,+

C ,−

A,− C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 168: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

{A→ C+, (A ∨ B)→ C−} B → C ,+

{A→ C+,A ∨ B+,C−}

A ∨ B,+

C ,−

A,− C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 169: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

B → C ,+

{A→ C+,A ∨ B+,C−}

A ∨ B,+

C ,−

A,− C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 170: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

B → C ,+

{A→ C+,A ∨ B+,C−}

A ∨ B,+

C ,−

{A−,A ∨ B+,C−} C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 171: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

B → C ,+

A ∨ B,+

C ,−

{A−,A ∨ B+,C−} C ,+

A,+ B,+

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 172: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

B → C ,+

A ∨ B,+

C ,−

{A−,A ∨ B+,C−} C ,+

A,+ {A−,B+,C−}

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 173: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

3.4 Algorithmische Umsetzung des Tableau-Aufbaus

Pfade werden durch Mengen von Markierungen, die auf ihnen noch nicht expandiert wurden, dargestellt.

Kurzschreibweise α+ fur (α,+) etc.

B → C ,+

A ∨ B,+

C ,−

C ,+

A,+ {A−,B+,C−}

B,− C ,+

A,+ B,+

×

×

×

× 1.3.20

Page 174: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Jedes Tableau bestimmt einen Formelmengenbaum

{((A→ C ) ∨ (B → C ))→ ((A ∨ B)→ C )−}

{(A→ C ) ∨ (B → C )+, (A ∨ B)→ C−}

{A→ C+, (A ∨ B)→ C−} {B → C+, (A ∨ B)→ C−}

{A→ C+,A ∨ B+,C−} {B → C+,A ∨ B+,C−}

{A−,A ∨ B+,C−}{C+,A ∨ B−,C−}

{A−,A+,C−}{A−,B+,C−}

{B−,A ∨ B+,C−}{C+,A ∨ B+,C−}

{B−,A+,C−}{B−,B+,C−}×

×

×

×

Jede Menge reprasentiert einen Prafix eines Pfades durch das Tableau.1.3.21

Page 175: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Jedes Tableau bestimmt einen Formelmengenbaum

{((A→ C ) ∨ (B → C ))→ ((A ∨ B)→ C )−}

{(A→ C ) ∨ (B → C )+, (A ∨ B)→ C−}

{A→ C+, (A ∨ B)→ C−} {B → C+, (A ∨ B)→ C−}

{A→ C+,A ∨ B+,C−} {B → C+,A ∨ B+,C−}

{A−,A ∨ B+,C−}{C+,A ∨ B−,C−}

{A−,A+,C−}{A−,B+,C−}

{B−,A ∨ B+,C−}{C+,A ∨ B+,C−}

{B−,A+,C−}{B−,B+,C−}0

0

0

0

Jede Menge reprasentiert einen Prafix eines Pfades durch das Tableau.1.3.21

Page 176: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Jedes Tableau bestimmt einen Formelmengenbaum

{((A→ C ) ∨ (B → C ))→ ((A ∨ B)→ C )−}

{(A→ C ) ∨ (B → C )+, (A ∨ B)→ C−}

{A→ C+, (A ∨ B)→ C−} {B → C+, (A ∨ B)→ C−}

{A→ C+,A ∨ B+,C−} {B → C+,A ∨ B+,C−}

{A−,A ∨ B+,C−}{C+,A ∨ B−,C−}

{A−,A+,C−}{A−,B+,C−}

{B−,A ∨ B+,C−}{C+,A ∨ B+,C−}

{B−,A+,C−}{B−,B+,C−}0

0

0

01 1

Jede Menge reprasentiert einen Prafix eines Pfades durch das Tableau.1.3.21

Page 177: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Jedes Tableau bestimmt einen Formelmengenbaum

{((A→ C ) ∨ (B → C ))→ ((A ∨ B)→ C )−}

{(A→ C ) ∨ (B → C )+, (A ∨ B)→ C−}

{A→ C+, (A ∨ B)→ C−} {B → C+, (A ∨ B)→ C−}

{A→ C+,A ∨ B+,C−} {B → C+,A ∨ B+,C−}

{A−,A ∨ B+,C−}{C+,A ∨ B−,C−}

{A−,A+,C−}{A−,B+,C−}

{B−,A ∨ B+,C−}{C+,A ∨ B+,C−}

{B−,A+,C−}{B−,B+,C−}0

0

0

01 1

max

max max

max max

Jede Menge reprasentiert einen Prafix eines Pfades durch das Tableau.1.3.21

Page 178: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Idee fur einen Algorithmus

Stelle mittels Tiefensuche durch den Formelmengenbaum fest,

dass alle Pfade des Tableaus widerspruchlich sind.

Das geht genauso wie:

Stelle mittels Tiefensuche durch den Formelmengenbaum fest,

dass es einen geschlossenen (nicht-widerspruchlichen) Pfad durch das Tableau gibt.

Im folgenden Algorithmus ist S eine Menge von Markierungen der Form (ϕ,+) bzw. (ϕ,−).S heißt erfullbar, falls es eine Belegung B gibt, so dass

I fur alle (ϕ,+) ∈ S gilt B ϕ, und

I fur alle (ψ,−) ∈ S gilt B 6 ψ.

1.3.22

Page 179: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Gultigkeitstest gemaß Tableau-Kalkulfur aussagenlogische Formeln mittels einer rekursiven Methode

fur die Tiefensuche durch den Formelmengenbaum

Methode erfullbar(Markierungenmenge S):

(∗ liefert Ergebnis 1, falls S erfullbar ist, und Ergebnis 0 sonst ∗)falls S widerspruchlich ist: return 0 (∗ S ist widerspruchlich ∗)

falls S eine Markierung m der Form (α→ β,−) enthalt:(∗ ersetze m durch alle seine Zerlegungsformeln ∗)return erfullbar((S − {m}) ∪ {(α,+), (β,−)})

sonst: falls S eine Markierung m der Form (α→ β,+) enthalt:(∗ ersetze m

”parallel“ durch jeweils eine Zerlegungsformel ∗)

return maxt∈{(α,−),(β,+)}

erfullbar((S − {m}) ∪ {t})

sonst: (∗ S ist nicht widerspruchlich und enthalt nur noch markierte Atome ∗)return 1 (∗ {Ai | (Ai ,+) ∈ S} ist erfullende Belegung von ϕ ∗)

Tableau-Algorithmus (liefert Ergebnis 1, falls ϕ gultig ist, und Ergebnis 0 sonst)Eingabe Formel ϕAusgabe 1− erfullbar({(ϕ,−)})

1.3.23

Page 180: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Grobe Analyse des Tableau-Algorithmusfur Aussagenlogik

Der Algorithmus simuliert das Tableau-Verfahren.

Jeder Tiefensuchepfad entspricht einem Pfad durch das Tableau.

Die Menge S enthalt stets die Markierungen auf dem Pfad,

die noch nicht expandiert wurden.

Da jede Formel der Lange n hochstens 2n Teilformeln besitzt,

wird jeder Tiefensuchepfad in polynomieller Zeit durchlaufen,

Da das Tableau fur eine Formel der Lange n hochsten 2n Knoten hat,

hat der Algorithmus exponentielle Rechenzeit.

1.3.24

Page 181: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Das gleiche als nichtdeterministischer Algorithmus

nichtdeterministischer Tableau-Algorithmus:Eingabe: Markierungenmenge S

solange S nicht widerspruchlich und expandierbar ist, wiederhole:

falls S eine Markierung m der Form α→ β,− enthalt:(∗ ersetze m durch alle ihre Zerlegungsformeln ∗)S = (S − {m}) ∪ {(α,+), (β,−)}

sonst: falls S eine Markierung m der Form α→ β,+ enthalt:(∗ wahle nichtdeterministisch eine Zerlegungsformel ∗)wahle (existentiell) nichtdeterministisch t ∈ {(α,−), (β,+)}S = (S − {m}) ∪ {t}

falls S nicht widerspruchlich ist: akzeptiere (∗ entspricht Ausgabe 1 ∗)sonst: verwirf (∗ entspricht Ausgabe 0 ∗)

Es gilt: (1) der nichtdetermistische Algorithmus hat bei Eingabe {(ϕ,+)} einen akzeptierendenBerechnungspfad genau dann, wenn ϕ erfullbar ist.

(2) der nichtdeterministische Algorithmus hat polynomielle Rechenzeit.1.3.25

Page 182: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Was haben wir in Vorlesung 3 gelernt?

I Wir wissen, wie man mittels Expansionsregeln fur verschiedene Verknupfungszeichen

ein Tableau fur eine Formel oder eine Formelmenge aufbaut, und wie groß das

Tableau hochstens werden kann, wenn man sich nicht zu ungeschickt anstellt.

I Wir kennen die Eigenschaften”geschlossen“ und

”widerspruchlich“ von Tableaux.

I Wir kennen die RelationTab

der Tableau-Beweisbarkeit.

I Wir haben gehort, dass gultige Formeln genau die Tableau-beweisbaren Formeln sind.

I Wir wissen, wie man die Idee der Tableau-Konstruktion algorithmisch umsetzen kann.

Dadurch erhalt man einen determistischen Gultigkeitstest mit exponentieller

Rechenzeit oder einen nichtdeterministischen Erfullbarkeitstest mit polynomieller

Rechenzeit (”NP-Algorithmus“).

1.3.26

Page 183: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Vorlesung 4: Ein Frege-Kalkul

1. Aussagenlogik

VL01: Umgangssprachliche und formale Aussagenlogik

VL02: Adaquate Verknupfungszeichen, erfullbare und gultige Formeln

VL03: Ein Tableau-Kalkul

VL04: Ein Frege-KalkulAxiome, Regeln und Beweise

Das Deduktionstheorem

Ahnliche Kalkule

VL05: Die Vollstandigkeitssatze fur die Kalkule

[Literatur: Mendelson: Introduction to Mathematical Logic]

1.4.1

Page 184: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Gottlob Frege (1848-1925)Grundgesetze der Arithmetik (1893, 1902)

Gottlob Frege (1848-1925) war Professor in Jena.

Er wollte die Grundgesetze der Mathematik finden,

aus denen sich jeder mathematische Satz herleiten lasst.

Dadurch wurde er zum Grundungsvater der formalen Logik.

1.4.2

Page 185: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Gottlob Frege (1848-1925)Grundgesetze der Arithmetik (1893, 1902)

Gottlob Frege (1848-1925) war Professor in Jena.

Er wollte die Grundgesetze der Mathematik finden,

aus denen sich jeder mathematische Satz herleiten lasst.

Dadurch wurde er zum Grundungsvater der formalen Logik.

1.4.2

Page 186: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Frege-Kalkulen liegt die Idee zu Grunde, dass man aus grundlegenden gultigen Formeln

(Axiomen) alle anderen gultigen Formeln zusammensetzen kann.

Die Regeln fur das Zusammensetzen spiegeln das korrekte Ziehen von Schlussen wider.

Wir werden fur den Frege-Kalkul nur Formeln aus Atomen, → und ⊥ betrachten.

In dieser Vorlesung werden wir folgendes machen.

I Definition von Axiomen und Schlussregeln fur Frege-Beweise.

I Werkzeuge zum Vereinfachen von Frege-Beweisen.

I (Viele) Beispiele fur Frege-Beweise.

1.4.3

Page 187: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Grundidee und Beispiel

Die Axiome des Frege-Kalkuls sind fur alle Formeln α, β, ϕ:(A1) α→ (β → α)

(A2) (α→ (β → ϕ))→ ((α→ β)→ (α→ ϕ))

(A3) (¬¬α)→ α

Die einzige Schlussregel des Frege-Kalkuls ist modus ponens (MP):aus α und α→ β kann man in einem Schritt β herleiten.

Eine Herleitung einer Formel besteht aus einer Folge von Axiomen und Formeln, die durchAnwendung der Schlussregel auf bereits hergeleitete Formeln entstehen.

(1) B → ( (B → B) → B ) Axiom (A1)

(2) ( B → ( (B → B) → B ))→ (( B → (B → B) )→ ( B → B )) Axiom (A2)

(3) (B → (B → B))→ (B → B) MP mit (1) und (2)

(4) B → ( B → B ) Axiom (A1)

(5) B → B MP mit (4) und (3)

1.4.4

Page 188: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

4.1 Axiome, Schlussregeln, Herleitungen und Beweise

Definition 4.1 (Herleitung von Formeln im Frege-Kalkul)

Der Frege-Kalkul dient zur Herleitung von Formeln aus Axiomen.

1. Die Elemente des Frege-Kalkuls sind die aussagenlogischen Formeln aus Atomen, ⊥und → (¬α ist abkurzende Schreibweise fur α→ ⊥; > ist Abkurzung fur ¬⊥).

2. Die Axiome des Frege-Kalkuls sind fur alle Formeln α, β, ϕ:

(A1) α→ (β → α)

(A2) (α→ (β → ϕ))→ ((α→ β)→ (α→ ϕ))

(A3) (¬¬α)→ α

3. Die einzige Schlussregel des Frege-Kalkuls ist modus ponens (MP). Fur alle Formeln

α und β gilt: aus α und α→ β kann man in einem Schritt β herleiten.

Das wird auch beschrieben durchα α→β

β .1.4.5

Page 189: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(Fortsetzung von Definition 4.1)

4. Eine Herleitung einer Formel α aus einer Formelmenge Γ im Frege-Kalkul ist eineFolge α1, α2, . . . , α` von Formeln, an deren Ende α(= α`) steht und deren Elementefolgende Eigenschaften haben (fur i = 1, 2, . . . , `):

I αi ist ein Axiom oder αi ∈ Γ (αi heißt dann”Hypothese“), oder

I es gibt αa, αb mit a, b < i ,

aus denen αi in einem Schritt mit modus ponens hergeleitet werden kann

(d.h. es gibt a, b < i mit αb = αa → αi).

(Statt Herleitung verwendet man gerne auch (Frege-)Beweis.)

1.4.6

Page 190: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Bsp.: eine Herleitung fur B → B

α1 = B → ( (B → B) → B ) Axiom (A1)

α2 = ( B → ( (B → B) → B ))→ (( B → (B → B) )→ ( B → B ))

Axiom (A2)

α3 = (B → (B → B))→ (B → B) MP mit α1 und α2

α4 = B → ( B → B ) Axiom (A1)

α5 = B → B MP mit α4 und α3

Nimmt man statt Atom B eine beliebige Formel β,dann hat man eine Herleitung fur β → β fur alle β.

1.4.7

Page 191: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Definition 4.2 (Frege-beweisbar)

Sei Γ eine Formelmenge und α eine Formel.

Die RelationFre

zwischen Formelmengen und Formeln ist definiert durch:

ΓFre

α genau dann,

wenn es eine Herleitung von α aus Γ im Frege-Kalkul gibt.

”Γ

Freα“ spricht man aus als

”α ist Frege-herleitbar aus Γ“ oder

”α ist Frege-beweisbar aus Γ“.

Fur ∅Fre

α schreibt man kurzFre

α.

Eine Formel α mitFre

α nennt man auch (Frege-)Theorem.

1.4.8

Page 192: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Wir zeigen (wie im obigen Beispiel),

dass β → β ein Theorem des Frege-Kalkuls ist.

Lemma 4.3

Freβ → β fur jede Formel β.

Beweis:

Sei β eine Formel.

Wir geben eine Herleitung von β → β im Frege-Kalkul an.

(1) β → ((β → β)→ β) (A1)

(2) (β → ((β → β)→ β))→ ((β → (β → β))→ (β → β)) (A2)

(3) (β → (β → β))→ (β → β) MP (1), (2)

(4) β → (β → β) (A1)

(5) β → β MP (4), (3)X1.4.9

Page 193: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Nun schauen wir uns Herleitungen mit Hypothesen an.

Lemma 4.4 (TRANS)

{α→ β, β → γ}Fre

α→ γ fur alle Formeln α, β, γ.

Beweis:

Seien α, β und γ Formeln.

Wir geben eine Herleitung von α→ γ aus α→ β und β → γ im Frege-Kalkul an.

(1) β → γ Hypothese

(2) (β → γ)→ (α→ (β → γ)) (A1)

(3) α→ (β → γ) MP (1), (2)

(4) (α→ (β → γ))→ ((α→ β)→ (α→ γ)) (A2)

(5) (α→ β)→ (α→ γ) MP (3), (4)

(6) α→ β Hypothese

(7) α→ γ MP (6), (5) X1.4.10

Page 194: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Wie bei verzichten wir auch beiFre

zur Abkurzung auf Mengenzeichen.

Lemma 4.5

⊥Fre

α fur alle Formeln α.

Beweis:Sei α eine Formel. Wir geben eine Herleitung von α aus ⊥ im Frege-Kalkul an.

(1) ⊥ Hypothese(2) ⊥ → (¬α→ ⊥︸ ︷︷ ︸

¬¬α

) (A1)

(3) ¬¬α MP (1), (2)(4) ¬¬α→ α (A3)(5) α MP (3), (4) X

Wir wissen, dass ⊥ → α gultig ist.Es ist nicht soo leicht zu sehen, wie man ⊥ → α herleiten kann.Man kann aus der Herleitung von α aus ⊥ eine Herleitung von ⊥ → α (ohne Hypothesen)machen, indem man systematisch

”⊥ →“ vor jede hergeleitete Formel schreibt und ein paar

Zwischenschritte einfugt . . . Das wird dann im Deduktionstheorem (4.6) formalisiert.1.4.11

Page 195: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(1) ⊥ Hyp ⊥ → ⊥ Lemma (4.3)

(1.1) ⊥ → ¬¬α (A1)

(1.2) (⊥→¬¬α)→(⊥→(⊥→¬¬α)) (A1)

(2) ⊥ → (¬α→ ⊥︸ ︷︷ ︸¬¬α

) (A1) ⊥ → (⊥→¬¬α) MP(1.1),(1.2)

(2.1) (⊥→(⊥→¬¬α))→((⊥→⊥)→(⊥→¬¬α)) (A2)

(2.2) (⊥→⊥)→(⊥→¬¬α) MP(2),(2.1)

(3) ¬¬α MP(1),(2) ⊥ → ¬¬α MP(1),(2.2)

(3.1) ¬¬α→ α (A3)

(3.2) (¬¬α→α)→(⊥→(¬¬α→α)) (A1)

(4) ¬¬α→ α (A3) ⊥ → (¬¬α→ α) MP(3.1),(3.2)

(4.1) (⊥→(¬¬α→α))→((⊥→¬¬α)→(⊥→α)) (A2)

(4.2) (⊥→¬¬α)→(⊥→α) MP(4),(4.1)

(5) α MP(3),(4) ⊥ → α MP (3),(4.2)

1.4.12

Page 196: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(1) ⊥ Hyp ⊥ → ⊥ Lemma (4.3)

(1.1) ⊥ → ¬¬α (A1)

(1.2) (⊥→¬¬α)→(⊥→(⊥→¬¬α)) (A1)

(2) ⊥ → (¬α→ ⊥︸ ︷︷ ︸¬¬α

) (A1) ⊥ → (⊥→¬¬α) MP(1.1),(1.2)

(2.1) (⊥→(⊥→¬¬α))→((⊥→⊥)→(⊥→¬¬α)) (A2)

(2.2) (⊥→⊥)→(⊥→¬¬α) MP(2),(2.1)

(3) ¬¬α MP(1),(2) ⊥ → ¬¬α MP(1),(2.2)

(3.1) ¬¬α→ α (A3)

(3.2) (¬¬α→α)→(⊥→(¬¬α→α)) (A1)

(4) ¬¬α→ α (A3) ⊥ → (¬¬α→ α) MP(3.1),(3.2)

(4.1) (⊥→(¬¬α→α))→((⊥→¬¬α)→(⊥→α)) (A2)

(4.2) (⊥→¬¬α)→(⊥→α) MP(4),(4.1)

(5) α MP(3),(4) ⊥ → α MP (3),(4.2)

1.4.12

Page 197: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(1) ⊥ Hyp ⊥ → ⊥ Lemma (4.3)

(1.1) ⊥ → ¬¬α (A1)

(1.2) (⊥→¬¬α)→(⊥→(⊥→¬¬α)) (A1)

(2) ⊥ → (¬α→ ⊥︸ ︷︷ ︸¬¬α

) (A1) ⊥ → (⊥→¬¬α) MP(1.1),(1.2)

(2.1) (⊥→(⊥→¬¬α))→((⊥→⊥)→(⊥→¬¬α)) (A2)

(2.2) (⊥→⊥)→(⊥→¬¬α) MP(2),(2.1)

(3) ¬¬α MP(1),(2) ⊥ → ¬¬α MP(1),(2.2)

(3.1) ¬¬α→ α (A3)

(3.2) (¬¬α→α)→(⊥→(¬¬α→α)) (A1)

(4) ¬¬α→ α (A3) ⊥ → (¬¬α→ α) MP(3.1),(3.2)

(4.1) (⊥→(¬¬α→α))→((⊥→¬¬α)→(⊥→α)) (A2)

(4.2) (⊥→¬¬α)→(⊥→α) MP(4),(4.1)

(5) α MP(3),(4) ⊥ → α MP (3),(4.2)

1.4.12

Page 198: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(1) ⊥ Hyp ⊥ → ⊥ Lemma (4.3)

(1.1) ⊥ → ¬¬α (A1)

(1.2) (⊥→¬¬α)→(⊥→(⊥→¬¬α)) (A1)

(2) ⊥ → (¬α→ ⊥︸ ︷︷ ︸¬¬α

) (A1) ⊥ → (⊥→¬¬α) MP(1.1),(1.2)

(2.1) (⊥→(⊥→¬¬α))→((⊥→⊥)→(⊥→¬¬α)) (A2)

(2.2) (⊥→⊥)→(⊥→¬¬α) MP(2),(2.1)

(3) ¬¬α MP(1),(2) ⊥ → ¬¬α MP(1),(2.2)

(3.1) ¬¬α→ α (A3)

(3.2) (¬¬α→α)→(⊥→(¬¬α→α)) (A1)

(4) ¬¬α→ α (A3) ⊥ → (¬¬α→ α) MP(3.1),(3.2)

(4.1) (⊥→(¬¬α→α))→((⊥→¬¬α)→(⊥→α)) (A2)

(4.2) (⊥→¬¬α)→(⊥→α) MP(4),(4.1)

(5) α MP(3),(4) ⊥ → α MP (3),(4.2)

1.4.12

Page 199: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(1) ⊥ Hyp ⊥ → ⊥ Lemma (4.3)

(1.1) ⊥ → ¬¬α (A1)

(1.2) (⊥→¬¬α)→(⊥→(⊥→¬¬α)) (A1)

(2) ⊥ → (¬α→ ⊥︸ ︷︷ ︸¬¬α

) (A1) ⊥ → (⊥→¬¬α) MP(1.1),(1.2)

(2.1) (⊥→(⊥→¬¬α))→((⊥→⊥)→(⊥→¬¬α)) (A2)

(2.2) (⊥→⊥)→(⊥→¬¬α) MP(2),(2.1)

(3) ¬¬α MP(1),(2) ⊥ → ¬¬α MP(1),(2.2)

(3.1) ¬¬α→ α (A3)

(3.2) (¬¬α→α)→(⊥→(¬¬α→α)) (A1)

(4) ¬¬α→ α (A3) ⊥ → (¬¬α→ α) MP(3.1),(3.2)

(4.1) (⊥→(¬¬α→α))→((⊥→¬¬α)→(⊥→α)) (A2)

(4.2) (⊥→¬¬α)→(⊥→α) MP(4),(4.1)

(5) α MP(3),(4) ⊥ → α MP (3),(4.2)

1.4.12

Page 200: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

4.2 Werkzeuge zum Vereinfachen von Herleitungen

Satz 4.6 (Deduktionstheorem fur den Frege-Kalkul der Aussagenlogik (DT))

Sei Γ eine Menge von Formeln, α und β seien Formeln.Dann gilt: Γ ∪ {α}

Freβ genau dann, wenn Γ

Freα→ β.

Beweis:

⇐: Sei ΓFre

α→ β. Dann gibt es folgenden Beweis mit Hypothesen aus Γ ∪ {α}.

(1) . . .}

hier steht die Herleitung von α→ β aus Γ......

(k) α→ β(k + 1) α Hypothese(k + 2) β MP (k + 1), (k)

Damit haben wir einen Beweis von β aufgeschrieben,in dem Hypothesen aus Γ (Schritte (1)–(k)) und Hypothese α benutzt werden (Schritt (k + 1)).

Also haben wir Γ ∪ {α}Fre

β.1.4.13

Page 201: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

⇒: Wir fuhren einen Induktionsbeweis uber die Lange `

von Herleitungen α1, . . . , α` von β aus Γ ∪ {α}.

IA ` = 1: Sei Γ ∪ {α}Fre

β mit einer Herleitung der Lange 1.

Dann ist β ein Axiom, oder β ∈ Γ, oder β = α (andere Herleitungen von β mit Lange 1 gibt es nicht).

Zu zeigen ist nun: ΓFre

α→ β.

Fall 1: β ist Axiom oder β ∈ Γ:

dann konnen wir folgende Herleitung aus Γ aufschreiben:

(1) β Hypothese aus Γ oder Axiom

(2) β → (α→ β) (A1)

(3) α→ β MP (1),(2)Also folgt Γ

Freα→ β.

Fall 2: β = α: es giltFre

β → β fur jede Formel β (4.3).

Also gilt auch ΓFre

β → β, d.h. hier ΓFre

α→ β.

Das sind alle Moglichkeiten fur β, und stets folgt ΓFre

α→ β.1.4.14

Page 202: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

IV: Fur bel. festes k und fur alle Γ, α, β gilt:

Wenn Γ ∪ {α}Fre

β mittels einer Herleitung mit ` 6 k Schritten,

dann folgt ΓFre

α→ β.

IS: z.z: Wenn Γ ∪ {α}Fre

β mittels einer Herleitung aus k + 1 Schritten,

dann folgt ΓFre

α→ β.

Sei α1, . . . , αk+1 eine Herleitung von β (= αk+1) aus Γ ∪ {α}.

Fall 1: β ist Axiom oder β ∈ Γ ∪ {α}.Dann folgt Γ

Freα→ β wie im IA.

1.4.15

Page 203: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall 2: β entsteht mit MP aus αi und αj (i , j 6 k).

Dann ist αj = αi → β.

Nach IV gilt ΓFre

α→ (αi → β) und ΓFre

α→ αi .Folgende Herleitung zeigt Γ

Freα→ β.

(1) . . . }Herleitung vonα→ (αi → β) aus Γ gemaß IV

......

(s) α→ (αi → β)

(s + 1) . . . }Herleitung vonα→ αi aus Γ gemaß IV

......

(m) α→ αi

(m + 1) (α→ (αi → β))→ ((α→ αi )→ (α→ β)) (A2)

(m + 2) (α→ αi )→ (α→ β) MP (s), (m + 1)

(m + 3) α→ β MP (m), (m + 2)

Damit haben wir eine Herleitung von α→ β aus Hypothesen in Γ,

d.h. ΓFre

α→ β. X1.4.16

Page 204: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Beispiele: Benutzung des Deduktionstheoremszur Vereinfachung von Herleitungen

Lemma 4.7 (Die fehlende Richtung des Doppelnegationsgesetzes)

Freα→ ¬¬α fur alle Formeln α.

Beweis:

Zuerst zeigen wir α,¬αFre⊥ mit folgender Herleitung.

(1) α Hyp(2) ¬α Hyp(3) ⊥ MP (1),(2) (Nun ist α,¬α Fre ⊥ bewiesen.)

Aus α,¬αFre⊥ folgt

αFre

(¬α)→ ⊥︸ ︷︷ ︸=¬¬α

mit dem Deduktionstheorem (4.6).

Aus αFre¬¬α folgt

Freα→ ¬¬α mit dem Deduktionstheorem (4.6). X

1.4.17

Page 205: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

UmFre

α→ ¬¬α zu zeigen,haben wir jetzt nicht mehr die ganze Herleitung von α→ ¬¬α angegeben,

sondern nur noch argumentiert,dass man aus einer Herleitung von ⊥ aus den Hypothesen {α,¬α}mit dem Deduktionstheorem die Existenz einer Herleitung von α→ ¬¬α folgern kann.

Deshalb verallgemeinern wir jetzt die Schreibweise fur Herleitungenzu einer Schreibweise fur die Existenz von Herleitungen.Darin konnen wir Herleitungsschritte wie bisher im Frege-Kalkul begrundenund verallgemeinerte Herleitungsschritte durch das Deduktionstheorem oder andere Lemmasbegrunden.

Beispiel fur das Aufschreiben des letzten Beweisesals verallgemeinerte Herleitung (Mengenzeichen werden weggelassen):

(1) α,¬αFre

α Hyp(2) α,¬α

Fre¬α Hyp

(3) α,¬αFre

⊥ MP (1),(2)(4) α

Fre¬¬α DT (3) [¬α→ ⊥ = ¬¬α]

(5)Fre

α→ ¬¬α DT (4)

1.4.18

Page 206: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

UmFre

α→ ¬¬α zu zeigen,haben wir jetzt nicht mehr die ganze Herleitung von α→ ¬¬α angegeben,

sondern nur noch argumentiert,dass man aus einer Herleitung von ⊥ aus den Hypothesen {α,¬α}mit dem Deduktionstheorem die Existenz einer Herleitung von α→ ¬¬α folgern kann.

Deshalb verallgemeinern wir jetzt die Schreibweise fur Herleitungenzu einer Schreibweise fur die Existenz von Herleitungen.Darin konnen wir Herleitungsschritte wie bisher im Frege-Kalkul begrundenund verallgemeinerte Herleitungsschritte durch das Deduktionstheorem oder andere Lemmasbegrunden.

Beispiel fur das Aufschreiben des letzten Beweisesals verallgemeinerte Herleitung (Mengenzeichen werden weggelassen):

(1) αFre

α Hyp(2) ¬α

Fre¬α Hyp

(3) α,¬αFre

⊥ MP (1),(2) [Hypothesenmengen der beteiligten Formeln werden vereinigt]

(4) αFre

¬¬α DT (3) [¬α→ ⊥ = ¬¬α](5)

Freα→ ¬¬α DT (4)

1.4.18

Page 207: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 4.8 (ex falso quod libet)

Fre⊥ → α fur alle Formeln α.

Beweis (anders als im Beispiel vor dem Deduktionstheorem):

(1) ¬α,⊥Fre

⊥ Hyp(2) ⊥

Fre¬¬α DT (1)

(3)Fre

¬¬α→ α (A3)(4) ⊥

Freα MP (2),(3) [Hypothesenmengen vereinigen!]

(5)Fre

⊥ → α DT (4) X

Wenn man eine verallgemeinerte Herleitung hat,dann weiß man, dass (und wie) man daraus eine Herleitung im Frege-Kalkul

”basteln“ kann

(und spart sich den muhseligen technischen Aufwand dazu).

1.4.19

Page 208: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 4.9 (reductio ad absurdum)

Sei Γ eine Formelmenge, und α sei eine Formel.

Aus Γ,¬αFre⊥ folgt Γ

Freα.

Beweis (als verallgemeinerte Herleitung):

(1) Γ,¬αFre⊥ Voraussetzung

(2) ΓFre¬¬α DT (1)

(3)Fre¬¬α→ α (A3)

(4) ΓFre

α MP (2),(3) [Hypothesenmengen vereinigen!] X

1.4.20

Page 209: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Formeln, deren Herleitung bereits bekannt ist (Theoreme),

konnen in verallgemeinerte Herleitungen eingebaut werden.

Lemma 4.10 (ex falso quod libet (allgemeiner))

Fre¬α→ (α→ β) fur alle Formeln α und β.

Beweis:

(1) αFre

α Hyp

(2) ¬αFre¬α Hyp

(3) α,¬αFre⊥ MP (1),(2)

(4)Fre⊥ → β (4.8)

(5) α,¬αFre

β MP (3),(4)

(6) ¬αFre

α→ β DT (5)

(7)Fre¬α→ (α→ β) DT (6) X

1.4.21

Page 210: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 4.11 (Herleitungen ersetzen Hypothesen)

Seien ∆ und Γ Formelmengen, α und β seien Formeln.

Aus Γ, αFre

β und ∆Fre

α folgt Γ,∆Fre

β.

Beweis:

Aus Γ, αFre

β folgt ΓFre

α→ β mit dem Deduktionstheorem (4.6).

Aus ∆Fre

α folgt Γ,∆Fre

α, da eine Herleitung mit Hypothesen

aus ∆ auch eine Herleitung mit Hypothesen aus Γ ∪∆ ist.

Entsprechend folgt Γ,∆Fre

α→ β aus ΓFre

α→ β.

Aus der Herleitung ϕ1, . . . , ϕm von α aus Γ ∪∆

und der Herleitung ψ1, . . . , ψ` von α→ β aus Γ ∪∆

erhalt man eine Herleitung ϕ1, . . . , ϕm, ψ1, . . . , ψ`, β aus Γ ∪∆,

bei der β durch MP aus ϕm = α und ψ` = α→ β entsteht.

Also gilt Γ,∆Fre

β. X

1.4.22

Page 211: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 4.12 (Verallgemeinerung von TRANS)

Fur jedes k > 1 und alle Formeln α1, . . . , αk , β, γ gilt

α1→(α2→(. . .→(αk→β) . . .)), β→γFre

α1→(α2→(. . .→(αk→γ). . .)).

Beweis: mittels Induktion uber k .

Fur Formeln α1→(α2→(. . .→(αk→β) . . .)) benutzen wir als Abkurzung κ(α1, . . . , αk , β).

IA k = 1: z.z. ist α1→β, β→γFre

α1→γ. Das ist TRANS (4.4).

IV: fur beliebiges festes k und alle Formeln α1, . . . , αk , β, γ gilt

κ(α1, . . . , αk , β), β→γFre

κ(α1, . . . , αk , γ).

IS: zu zeigen: κ(α1, α2, . . . , αk+1, β), β→γFre

κ(α1, α2, . . . , αk+1, γ)

(1) κ(α1, α2, . . . , αk+1, β), β→γFre

κ(α1, α2, . . . , αk+1, β) Hyp(2) κ(α1, α2, . . . , αk+1, β), β→γ, α1 Fre

κ(α2, . . . , αk+1, β) DT (1)(3) κ(α2, . . . , αk+1, β), β→γ

Freκ(α2, . . . , αk+1, γ) IV

(4) κ(α1, α2, . . . , αk+1, β), β→γ, α1 Freκ(α2, . . . , αk+1, γ) (4.11) mit (2)(3)

(4) κ(α1, α2, . . . , αk+1, β), β→γFre

κ(α1, α2, . . . , αk+1, γ) DT (3) X

1.4.23

Page 212: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Satz 4.13 (”

Wichtige“ Theoreme des Frege-Kalkuls)

Fur alle Formeln α und β gilt:

1.Fre

α→ α (4.3)

2.Fre

α→ ¬¬α (4.7)

3.Fre¬α→ (α→ β) (4.10)

4.Fre

(α→ β)→ (¬β → ¬α)

5.Fre

α→ (¬β → ¬(α→ β))

6.Fre

(α→ β)→ ((¬α→ β)→ β)

7. ¬(α→ β)Fre

α

8. ¬(α→ β)Fre¬β

1.4.24

Page 213: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(4)Fre

(α→ β)→ (¬β → ¬α)

(1) α→ β,¬β, αFre

α→ β Hyp

(2) α→ β,¬β, αFre

α Hyp

(3) α→ β,¬β, αFre

β MP (1),(2)

(4) α→ β,¬β, αFre¬β Hyp

(5) α→ β,¬β, αFre⊥ MP (3),(4)

(6) α→ β,¬βFre¬α DT (5)

(7) α→ βFre¬β → ¬α DT (6)

(8)Fre

(α→ β)→ (¬β → ¬α) DT (7)

1.4.25

Page 214: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(5)Fre

α→ (¬β → ¬(α→ β))

(1) α,¬β, α→ βFre

α→ β Hyp

(2) α,¬β, α→ βFre

α Hyp

(3) α,¬β, α→ βFre

β MP (1),(2)

(4) α,¬β, α→ βFre¬β Hyp

(5) α,¬β, α→ βFre⊥ MP (3),(4)

(6) α,¬βFre¬(α→ β) DT (5)

(7) αFre¬β → ¬(α→ β) DT (6)

(8)Fre

α→ (¬β → ¬(α→ β)) DT (7)

1.4.26

Page 215: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(6)Fre

(α→ β)→ ((¬α→ β)→ β)

(1) α→ β,¬α→ β,¬βFre

α→ β Hyp(2) α→ β,¬α→ β,¬β

Fre¬α→ β Hyp

(3) α→ β,¬α→ β,¬βFre

(α→ β)→ (¬β → ¬α) Satz (4.13)(4)(4) α→ β,¬α→ β,¬β

Fre¬β → ¬α MP (1),(3)

(5) α→ β,¬α→ β,¬βFre

(¬α→ β)→ (¬β → ¬¬α) Satz (4.13)(4)(6) α→ β,¬α→ β,¬β

Fre¬β → ¬¬α MP (2),(5)

(7) α→ β,¬α→ β,¬βFre

¬β Hyp(8) α→ β,¬α→ β,¬β

Fre¬α MP (7),(4)

(9) α→ β,¬α→ β,¬βFre

¬¬α MP (7),(6)(10) α→ β,¬α→ β,¬β

Fre⊥ MP (8),(9)

(11) α→ β,¬α→ βFre

β Satz (4.9) mit (10)(12) α→ β

Fre(¬α→ β)→ β DT (11)

(13)Fre

(α→ β)→ ((¬α→ β)→ β) DT (12)

1.4.27

Page 216: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(7) ¬(α→ β)Fre

α

(1)Fre¬α→ (α→ β) Satz (4.13)(3)

(2)Fre

(¬α→ (α→ β))→ (¬(α→ β)→ ¬¬α) Satz (4.13)(4)

(3)Fre¬(α→ β)→ ¬¬α MP (1),(2)

(4) ¬(α→ β)Fre¬¬α DT (3)

(5)Fre¬¬α→ α (A3)

(6) ¬(α→ β)Fre

α MP (4),(5)

1.4.28

Page 217: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

(8) ¬(α→ β)Fre¬β

(1)Fre

β → (α→ β) (A1)

(2)Fre

(β → (α→ β))→ (¬(α→ β)→ ¬β) Satz (4.13)(4)

(3)Fre¬(α→ β)→ ¬β MP (1),(2)

(4) ¬(α→ β)Fre¬β DT (3)

1.4.29

Page 218: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

4.3 Ahnliche Kalkule

Die Auswahl der Axiome in”unserem“ Frege-Kalkul hat das Ziel, den Beweis des Vollstandigkeitssatzes

technisch einfach zu machen.Eine Theorie von Kleene (1952) hat Modus Ponens und die folgenden Axiome(fur Formeln mit Verknupfungszeichen →, ∧, ∨ und ¬).

1. α→ (β → α)

2. (α→ (β → γ))→ ((α→ β)→ (α→ γ))

3. (α ∧ β)→ α und (α ∧ β)→ β

4. α→ (β → (α ∧ β))

5. α→ (α ∨ β) und β → (α ∨ β)

6. (α→ γ)→ ((β → γ)→ ((α ∨ β)→ γ))

7. (α→ β)→ ((α→ ¬β)→ ¬α)

8. ¬¬α→ α

Durch Weglassen des letzten Axioms (Doppelnegationsgesetz)erhalt man einen Kalkul fur die intuitionistische Logik.

1.4.30

Page 219: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Ein Kalkul, der im Buch von Mendelson benutzt wird,

hat Modus Ponens und die folgenden Axiome

(fur Formeln mit Verknupfungszeichen → und ¬).

1. α→ (β → α)

2. (α→ (β → γ))→ ((α→ β)→ (α→ γ))

3. (¬β → ¬α)→ ((¬β → α)→ β)

1.4.31

Page 220: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Was haben wir in Vorlesung 4 gelernt?

I Wir kennen die drei Axiomenschemata und die Schlussregel modus ponens und

wissen, was die Herleitung einer Formel im Frege-Kalkul ist.

I Wir kennen die RelationFre

der Frege-Beweisbarkeit.

I Wir kennen das Deduktionstheorem und konnen es zum Herleiten von Formeln

benutzen.

I Wir haben gehort, dass gultige Formeln genau die Frege-beweisbaren Formeln sind,

und warten gespannt auf die nachste Vorlesung, in der wir den Beweis dafur sehen

werden.

1.4.32

Page 221: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Vorlesung 5:

Die Vollstandigkeitssatze fur die Kalkule

1. Aussagenlogik

VL01: Umgangssprachliche und formale Aussagenlogik

VL02: Adaquate Verknupfungszeichen, erfullbare und gultige Formeln

VL03: Ein Tableau-Kalkul

VL04: Ein Frege-Kalkul

VL05: Die Vollstandigkeitssatze fur die KalkuleKorrektheit des Frege-Kalkuls

Vollstandigkeit des Tableau-Kalkuls

Umwandlung von Tableau-Beweisen in Frege-Beweise

Die Vollstandigkeitssatze

1.5.1

Page 222: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Einleitung

Ein Kalkul unterteilt die Menge aller Formelnin beweisbare und nicht-beweisbare Formeln.

Wir vermuten,dass die beweisbaren Formeln genau die gultigen Formeln sind.

In dieser Vorlesung werden wir beweisen, dass das stimmt.

Unsere Vermutung besteht aus zwei Teilen:

1) Jede beweisbare Formel ist gultig. (Korrektheit des Kalkuls)

2) Jede gultige Formel ist beweisbar. (Vollstandigkeit des Kalkuls)

Die beiden Teile lassen sich am besten getrennt beweisen.Da wir das fur zwei Kalkule machen wollen, sieht es so aus, als ob wir vier (dicke) Beweisefuhren mussten. Aber: wir konnen uns einen Beweis sparen!Wir zeigen die Korrektheit des Frege-Kalkuls, die Vollstandigkeit des Tableau-Kalkuls und wieman Tableau-Beweise in Frege-Beweise umwandeln kann.Daraus folgt dann die Vollstandigkeit des Frege-Kalkuls und die Korrektheit des Tableau-Kalkuls. . . 1.5.2

Page 223: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

5.1 Korrektheit des Frege-Kalkuls

Wir wollen zeigen, dass jede herleitbare Formel gultig ist,

– d.h. ausFre

α folgt α.

Wir werden den Beweis mittels Induktion uber die Lange der Herleitung fuhren.

Jede Herleitung beginnt mit einem Axiom.

Also werden wir benotigen, dass jedes Axiom gultig ist.

1.5.3

Page 224: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 5.1 (Alle Axiome des Frege-Kalkuls sind gultig)

Fur alle Formeln α, β und ϕ gilt

1. α→ (β → α) ist gultig,

2. (α→(β→ϕ))→((α→β)→(α→ϕ)) ist gultig und

3. ¬¬α→ α ist gultig.

Beweis:

1. und 2. wurde in (2.15) und (2.16) gezeigt.

Es bleibt also noch die Gultigkeit von ¬¬α→ α zu zeigen.

Sei A eine Belegung. Es gilt

A ¬¬α→ α gdw. A 6 ¬¬α oder A α (Semantik von →)

gdw. A ¬α oder A α (Lemma (1.5), ugs. Vereinfachung)

gdw. A 6 α oder A ⊥ oder A α (∗) (Semantik von →)

Die Aussage (∗) ist wahr. Folglich ist die aquivalente Aussage”A ¬¬α→ α“ wahr. X

1.5.4

Page 225: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 5.2 (Korrektheit vonFre

)

Sei α eine Formel. WennFre

α, dann α.

(D.h.: wenn α Frege-beweisbar ist, dann ist α gultig.)

Beweis: Induktion uber die Lange ` der Herleitung von α.

IA ` = 1: Sei α mit einer Herleitung der Lange 1 herleitbar. Dann ist α ein Axiom.

Da jedes Axiom gultig ist (5.1), folgt α.

IV: fur bel. festes k gilt:

wenn eine Formel α mit einer Herleitung der Lange 6 k herleitbar ist, dann folgt α.

IS ` = k + 1: α sei mit einer Herleitung der Lange k + 1 herleitbar.

Falls α ein Axiom ist, dann folgt α (5.1).

Sonst entsteht α mit MP aus αi und αj = αi → α (mit i , j 6 k).

Nach IV gilt αi und αi → α.

Dann gilt auch α (2.17). X

1.5.5

Page 226: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

5.2 Vollstandigkeit des Tableau-Kalkuls

Wir wollen zeigen:Jede gultige Formel ist Tableau-beweisbar.

D.h.: Fur jede Formel α gilt: wenn α gultig ist, dann ist α Tableau-beweisbar.

Das ist aquivalent zu:Fur jede Formel α gilt:

wenn α nicht Tableau-beweisbar ist, dann ist α nicht gultig.

Anders gesagt:Fur jede Formel α gilt:

wenn jedes geschlossene Tableau fur (α,−) einen nicht-widerspruchlichen Pfad hat,dann gibt es eine Belegung B mit B 6 α.

Wir suchen also einen Zusammenhang zwischen nicht-widerspruchlichen Pfaden in geschlossenen Tableaux fur (α,−) und

erfullenden Belegungen von α . . .

1.5.6

Page 227: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Man betrachtet die Belegung Bπ aus

den Atomen auf einem geschlossenen nicht-widerspruchlichen Pfad π und zeigt,

dass diese Belegung alle Formeln auf dem Pfad entsprechend ihrer Markierung erfullt.

Lemma 5.3 (Pfad bestimmt Belegung, die jede seiner Formeln Markierungs-treu erfullt)

Sei T ein nicht-widerspruchliches geschlossenes Tableau

und π = m1,m2, . . . ,mk ein nicht-widerspruchlicher geschlossener Pfad durch T .

Dann gilt fur die Belegung Bπ = {Ai | fur ein j mit 1 6 j 6 k ist (Ai ,+) = mj}und alle j = 1, 2, . . . , k:

1. wenn mj = (αj ,+), dann Bπ αj , und

2. wenn mj = (αj ,−), dann Bπ 6 αj .

Fur mj = (αj , sj) kann man 1.) und 2.) zusammenfassen zu Bπ αj gdw. sj = +.

1.5.7

Page 228: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Beweis:

Sei T ein nicht-widerspruchliches geschlossenes Tableau,und π = m1,m2, . . . ,mk sei ein nicht-widerspruchlicher Pfad durch T mit mi = (αi , si ).(Also sind alle expandierbaren Knoten auf π expandiert.)

Sei Bπ = {Ai | fur ein j mit 1 6 j 6 k ist (Ai ,+) = mj} die Belegung,die genau aus den Atomen mit + -Markierung auf dem Pfad besteht.

Wir zeigen induktiv fur j = k , k − 1, . . . , 1, dass Bπ αj ⇔ sj = +.

IA: z.z.: fur mk = (αk , sk) gilt Bπ αk ⇔ sk = +.

αk ist eine Formel, die nicht expandiert werden kann.

Dann ist (1) αk = Ai mit Ai ∈ Bπ,und es gilt Bπ Ai ⇔ sk = + aufgrund der Definition von Bπ.Oder (2) αk = ⊥. Dann ist sk = −, da π nicht widerspruchlich ist,und es gilt Bπ 6 ⊥ und sk = −, da π nicht widerspruchlich ist.

1.5.8

Page 229: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

IV: fur beliebiges festes ` 6 k und alle i = k, k − 1, . . . , ` gilt: Bπ αi ⇔ si = +.

IS: zu zeigen: Bπ α`−1 ⇔ s`−1 = +.Wenn m`−1 nicht expandiert werden kann, folgt Bπ α`−1 ⇔ s`−1 = + wie im IA.Wenn m`−1 expandiert werden kann,dann ist α`−1 = β → γ und es gibt folgende Moglichkeiten.

Fall 1: s`−1 = −.Da m` expandiert wurde, gibt es mi = (β,+) und mj = (γ,−) mit i , j > `.Also gilt Bπ β und Bπ 6 γ gemaß IV.Mit (1.5) folgt daraus Bπ 6 β → γ.

β → γ,− :•

β,+

γ,−

Fall 2: s`−1 = +.Da m` expandiert wurde, gibt es mi = (β,−) oder mi = (γ,+) mit i > `.Mit der IV folgt Bπ 6 β oder Bπ γ.Mit der Semantik von → folgt daraus Bπ β → γ.

β → γ,+ :•

β,− γ,+

X1.5.9

Page 230: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 5.4 (Vollstandigkeit des Tableau-Kalkuls)

Sei α eine Formel. Wenn α, dannTab

α.

(D.h.: wenn α gultig ist, dann ist α Tableau-beweisbar.)

Beweis:

Wir zeigen die aquivalente Aussage: wenn 6Tab

α, dann 6 α.

Sei 6Tab

α.

Dann gibt es fur (α,−) ein geschlossenes Tableau T0 (3.4), das nicht widerspruchlich ist.

Also gibt es einen nicht-widerspruchlichen Pfad π durch T0,

auf dem jeder Knoten expandiert ist.

Nach (5.3) gibt es eine Belegung Bπ, die jede Formel auf π Markierungs-treu erfullt.

Da (α,−) auf π steht, folgt Bπ 6 α.

Folglich ist α nicht gultig, d.h. 6 α. X

1.5.10

Page 231: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

5.3 Umwandlung von Tableau-Beweisen in

Frege-Beweise

Was haben wir bereits?

Was fehlt noch zum Vollstandigkeitssatz?

Freα

(5.2)=⇒ α

Tabα

(5.4)

⇐=

(5.7) =⇒

Aus (5.2), (5.4) und (5.7) folgt dann, dass

gultige, Frege-beweisbare und Tableau-beweisbare Formeln

genau die gleichen Formeln sind.

1.5.11

Page 232: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

5.3 Umwandlung von Tableau-Beweisen in

Frege-Beweise

Was haben wir bereits? Was fehlt noch zum Vollstandigkeitssatz?

Freα

(5.2)=⇒ α

Tabα

(5.4)

⇐=(5

.7) =⇒

Aus (5.2), (5.4) und (5.7) folgt dann, dass

gultige, Frege-beweisbare und Tableau-beweisbare Formeln

genau die gleichen Formeln sind.

1.5.11

Page 233: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Frege-Herleitungen aus widerspruchlichen Tableaux

Wir wollen zeigen:

aus einem widerspruchlichen Tableau fur (α,−)

lasst sich eine Frege-Herleitung von ⊥ aus ¬α konstruieren.

Zuerst zeigen wir:

zum Frege-Herleiten von ⊥ aus einer Hypothesenmenge Γ sind Formeln uberflussig,

die aus einer Formel in Γ durch Tableau-Expansion entstehen.

1.5.12

Page 234: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 5.5 (aus ¬(β → γ) expandierte Formeln sind uberflussig)

Sei Γ eine Formelmenge. α, β und γ seien Formeln.

Wenn Γ,¬(β → γ), β,¬γFre

α, dann Γ,¬(β → γ)Fre

α.

(Die Beweislange wachst dabei um eine Konstante unabhangig von Γ, α, β und γ.)

Beweis:

(1) Γ,¬(β → γ), β,¬γFre

α Voraussetzung

(2) Γ,¬(β → γ), βFre

¬γ → α DT (1)(3) Γ,¬(β → γ), β

Fre¬γ Satz (4.13)(8)

(4) Γ,¬(β → γ), βFre

α MP (2)(3)

(5) Γ,¬(β → γ)Fre

β → α DT (4)(6) Γ,¬(β → γ)

Freβ Satz (4.13)(7)

(7) Γ,¬(β → γ)Fre

α MP (5)(6) X

1.5.13

Page 235: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 5.6 (aus β → γ expandierte Formeln sind uberflussig)

Sei Γ eine Formelmenge. α, β und γ seien Formeln.

Wenn Γ, β → γ,¬βFre

α und Γ, β → γ, γFre

α, dann Γ, β → γFre

α.

(Die Beweislange wachst dabei um eine Konstante unabhangig von Γ, α, β und γ.)

Beweis:

(1) Γ, β → γ, γFre

α Voraussetzung(2) Γ, β → γ

Freγ → α DT (1)

(3) Γ, β → γFre

β → α TRANS (2)

(4) Γ, β → γ,¬βFre

α Voraussetzung(5) Γ, β → γ

Fre¬β → α DT (4)

(6) Γ, β → γFre

(β → α)→ ((¬β → α)→ α) Satz (4.13)(6)

(7) Γ, β → γFre

(¬β → α)→ α MP (3)(6)

(8) Γ, β → γFre

α MP (5)(7) X

1.5.14

Page 236: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 5.7 (Frege-Herleitungen von ⊥ aus widerspruchlichen Tableaux fur (ϕ,−))

Sei ϕ eine Formel, und T sei ein widerspruchliches Tableau fur (ϕ,−).

Fur jeden Pfad π = m1, . . . ,m` durch T mit markierten Formeln mi = (αi , si) fur

si ∈ {+,−} gilt: fur jedes i = `, `− 1, . . . , 1 ist α∗1, . . . , α∗i Fre

⊥,wobei α∗i = αi , falls si = +, und α∗i = ¬αi , falls si = −.

Beispiel fur ein widerspruchliches Tableau:

(A→ B)→ ((B → C)→ (A→ C)),−

A→ B,+

(B → C)→ (A→ C),−

B → C ,+

A→ C ,−

A,+

C ,−

A,− B,+

B,− C ,+

Beispiele fur mogliche Herleitungen nach (5.7):

¬[(A→ B)→ ((B → C)→ (A→ C))] Fre ⊥

¬[(A→ B)→ ((B → C)→ (A→ C))],A→ B Fre ⊥

¬[(A→ B)→ ((B → C)→ (A→ C))],A→ B, . . . ,¬A Fre ⊥

¬[(A→ B)→ ((B → C)→ (A→ C))],A→ B, . . . ,B Fre ⊥

¬[(A→ B)→ ((B → C)→ (A→ C))],A→ B, . . . ,B,¬B Fre ⊥

1.5.15

Page 237: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Beweis:

Sei n die Lange des langsten Pfades durch T .

Wir fuhren eine Induktion uber i = n, n − 1, . . . , 1.

IA: zu zeigen: fur alle Pfade π = m1, . . . ,mn durch T mit Lange n gilt α∗1, . . . , α∗n Fre

⊥.

Sei π ein Pfad der Lange n – also ein langster Pfad – durch T .

Da T widerspruchlich ist, ist π widerspruchlich.

Also gibt es k , t 6 m, so dass αk = αt fur mk = (αk ,+) und mt = (αt ,−) auf π,

d.h. ¬α∗k = α∗t .

MitFre

α∗t → (α∗k → ϕ) (Lemma (4.10)) und (DT) folgt α∗k , α∗t Fre

⊥.

1.5.16

Page 238: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

IV: Fur (bel. festes) j > 1 und

fur jeden Pfad π = m1, . . . ,m` durch T und ` > j gilt α∗1, . . . , α∗j Fre

⊥.

IS: zu zeigen ist:

Fur jeden Pfad π = m1, . . . ,m` durch T und ` > j − 1 gilt α∗1, . . . , α∗j−1 Fre

⊥.

Fall 1: ` = j − 1, d.h. π ist ein widerspruchlicher Pfad mit Lange j − 1.

Dann folgt α∗1, . . . , α∗` Fre

⊥ (d.h. α∗1, . . . , α∗j−1 Fre

⊥) wie im IA.

Fall 2: ` > j , d.h. mj entsteht durch Expansion eines me mit e < j .

Fall 2a: me = (β → γ,+).

Dann gibt es die beiden Pfade mit m1, . . . ,me , . . . ,mj−1, (β,−), . . .

und m1, . . . ,me , . . . ,mj−1, (γ,+), . . . durch T .Nach IV gilt fur deren Anfangsabschnitte der Lange j

α∗1, . . . , α∗e , . . . , α

∗j−1,¬β Fre

⊥ und α∗1, . . . , α∗e , . . . , α

∗j−1, γ Fre

⊥.

Dann folgt mit Lemma (5.6), dass α∗1, . . . , α∗e , . . . , α

∗j−1 Fre

⊥.1.5.17

Page 239: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Fall 2b: me = (β → γ,−).

Dann gibt es den Pfad m1, . . . ,me , . . . ,mj−1, (β,+), (γ,−), . . . durch T .

Nach IV gilt fur dessen Anfangsabschnitt der Lange j + 1

α∗1, . . . , α∗e , . . . , α

∗j−1, β,¬γ Fre

⊥ .

Dann folgt α∗1, . . . , α∗j−1 Fre

⊥ aus Lemma (5.5).

Andere Falle gibt es nicht. Also gilt stets α∗1, . . . , α∗j−1 Fre

⊥. X

1.5.18

Page 240: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Lemma 5.8 (aus Tableau-Beweisen konnen Frege-Beweise gemacht werden)

Sei α eine Formel. WennTab

α, dannFre

α.

(D.h.: wenn α Tableau-beweisbar ist, dann ist α auch Frege-beweisbar.)

Beweis:Gelte

Tabα.

Also gibt es ein widerspruchliches Tableau fur (α,−).Der Fall i = 1 von Lemma (5.7) liefert ¬α

Fre⊥, also

Fre¬¬α.

Mit (A3) und (MP) folgtFre

α. X

Bemerkung zur Lange der Frege-Herleitung.Die Lange der Frege-Herleitung von α wird bei dieser Umwandlung asymptotisch hochstens so groß wiedas widerspruchliche Tableau fur (α,−).Die Abschatzung der Lange der Herleitung folgt daraus, dass gemaß (5.5)–(5.7) jede Expansion einesKnotens im Tableau durch eine konstante Anzahl an Schritten in der Frege-Herleitung

”simuliert“ wird.

1.5.19

Page 241: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

5.4 Zusammenfuhrung der Resultate

Satz 5.9 (Vollstandigkeitssatz furFre

undTab

)

Sei ϕ eine Formel. Die folgenden Aussagen sind aquivalent:

1.Fre

ϕ (ϕ ist Frege-beweisbar)

2. ϕ (ϕ ist gultig)

3.Tab

ϕ (ϕ ist Tableau-beweisbar)

Beweis:

1. ⇒ 2. ist Lemma (5.2),

2. ⇒ 3. ist Lemma (5.4), und

3. ⇒ 1. ist Lemma (5.7). X

1.5.20

Page 242: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Die einzelnen Vollstandigkeitssatze fur die beiden Kalkule

Satz 5.10 (Vollstandigkeitssatz fur den Frege-Kalkul)

ϕ genau dann, wennFre

ϕ.

und

Satz 5.11 (Vollstandigkeitssatz fur den Tableau-Kalkul)

ϕ genau dann, wennTab

α.

folgen direkt aus (5.9).

Bem.:

I”Gultigkeit“ ist uber Belegungen definiert: semantisch.

I”Beweisbarkeit“ ist uber Formeln definiert: syntaktisch.

1.5.21

Page 243: Vorlesung Logiksysteme - Teil 1: Aussagenlogik€¦ · 1.1 Umgangssprachliche Aussagenlogik Einf uhrendes Beispiel Aussagenlogik betrachtet Aussagen und deren Zusammensetzung, und

Was haben wir in Vorlesung 5 gelernt?

I Wir kennen die Begriffe Korrektheit, Vollstandigkeit und die Vollstandigkeitssatze fur denFrege-Kalkul und den Tableau-Kalkul.

I Wir wissen, dass die Axiome des Frege-Kalkuls gultig sind und konnen den Beweis fur (A1)reproduzieren.

I Wir wissen, dass im Frege-Kalkul nur gultige Formeln herleitbar sind und konnen denBeweis mittels Induktion uber die Lange der Herleitung reproduzieren.

I Wir wissen, dass jede gultige Formel im Tableau-Kalkul bewiesen werden kann und konnenden Beweis mittels Induktion uber die Pfadlange in geschlossenen Tableaux reproduzieren.

I Wir wissen, wie man Tableau-Beweise in Frege-Beweise umwandeln kann und konnen denBeweis mittels Induktion uber die Pfadlange in widerspruchlichen Tableaux reproduzieren.

1.5.22