52
FORMALE SYSTEME 21. Vorlesung: Aussagenlogik Markus Kr ¨ otzsch Lehrstuhl Wissensbasierte Systeme TU Dresden, 9. Januar 2017

Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

  • Upload
    others

  • View
    0

  • Download
    0

Embed Size (px)

Citation preview

Page 1: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

FORMALE SYSTEME

21. Vorlesung: Aussagenlogik

Markus Krotzsch

Lehrstuhl Wissensbasierte Systeme

TU Dresden, 9. Januar 2017

Page 2: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Besprechung Lehrevaluation

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 2 von 36

Page 3: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Kommentare: Allgemeines

Danke für die vielen freundlichen Kommentare!

Konkrete technische Verbesserungswünsche werden soweitmöglich umgesetzt:

• „Die Folien direkt nach der Vorlesung verfügbar haben“

• „Das Mikro ist im Raum E02 im HSZ regelmäßig zu leise“

• „Eine bessere Justierung des Beamers im HSZ/003 ;)“

• „Besser auf Vorwissen aus AuD und Programmierungabstimmen“

• „jede Woche 1 Baby-Foto“ (mal sehen . . . )

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 3 von 36

Page 4: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Kommentare: Beispiele und Praxisbezug

. . . besonders gut gefallen? Verbesserungswünsche?

„Sehr viele Beispiele“

„Ich finde es besser, wenn es ein bisschen mehr Beispiele gibt.“

„Viele einfache verständliche Beispiele“

„Mehr Beispiele.“

„macht eher ‘trockenen’ Stoff spannend“

„Praxisbezug erhöhen“

„Mehr Praxisbezug“

„Mehr Praxis-Beispiele“

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 4 von 36

Page 5: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Kommentare: Beweise und Tempo

. . . besonders gut gefallen? Verbesserungswünsche?

„Beweise <3“

„Ein oder zwei Beweise weniger wären gut. ;)“

„Weniger Beweise“

„Beweise gut erklärt“

„Beweise teilweise zu schnell erklärt“

„Tempo etwas verlangsamen“

„Weniger ausführliche Beweise“

„Manchmal werden Themen etwas zu schnell behandelt, wennman selbst Notizen machen will, vor allem Beweise“

„Tempo könnte an einigen Stellen deutlich höher sein (vor allemBeweise)“Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 5 von 36

Page 6: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Kommentare: Zusammenfassungen undWiederholungen

. . . besonders gut gefallen? Verbesserungswünsche?

„Regelmäßiges Zusammenfassen des Stoffes“

„Wiederholungen“

„Wiederholungen zur Festigung des Stoffes“

„Die Zusammenfassungen und Wiederholungen des bereitsabgeschlossenen Stoffes sind viel zu Ausführlich“

„nicht alles 3 mal erklären, man versteht es beim ersten mal“

„Mehr Wiederholungen. Explain it like I’m 5“

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 6 von 36

Page 7: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Kommentare: Tafel vs. Beamer. . . besonders gut gefallen? Verbesserungswünsche?

„Sehr gute Folien (interaktiv)“

„Bunte Folien, Schemata und Veranschaulichungen leichtverständlich“

„Sehr übersichtl. Folien“

„die Folien, die im Internet zur Verfügung stehen, finde ich prima“

„excellente Latex-Folien“

„Verständliche Folien“

„sehr anschauliche und erklärende Folien, die auchnachvollziehbar online sind“

„Tafelschriebe helfen mir konzentrierter zu bleiben“

„Verhältnis Powerpoint<->Tafel mehr zu Gunsten der Tafelverschieben. Bei ppt-Folien bleibt zu wenighängen bzw. das Tempoerhöht sich.“Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 7 von 36

Page 8: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Kommentare: Politik

. . . besonders gut gefallen? Verbesserungswünsche?

„‘politische’ Statements“

„Blick über den Tellerrand der Vorlesung, durch Kommentare zurPolitischen Situation“

„Zu viel Politik“

„bitte keine Werbung für ‘Herz-statt-Hetze’ oder ähnliches“

„keine/weniger politische Statements in Vorlesungen, Forschung +Lehre sollten neutral sein“

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 8 von 36

Page 9: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Ankündigung

Weitere Kommentare(gesellschaftspolitisch oder anderweitig)?

Dann kommen Sie zum

Professorenstammtisch11.1.201718:30 Uhr

Im „Campus“

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 9 von 36

Page 10: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logik

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 10 von 36

Page 11: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logik für Informatiker

Warum?

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 11 von 36

Page 12: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logik für Informatiker

Warum?

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 11 von 36

Page 13: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logik für Informatiker: Darum (1)

LogikInformatik

=Analysis

Ingenieurwesen

„Wer rechnende Systeme verstehen und konstruierenwill, der benötigt passende mathematische Modelle.

Dieser Weg führt oftmals zur Logik.“

• Modellierung von Programmlogik und logischen Schaltungen

• Berechnung praktisch relevanter Eigenschaften durchlogisches Schließen

• Hauptanwendung: Verifikation von Systemen

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 12 von 36

Page 14: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logik für Informatiker: Darum (2)

Logik = Wissenschaft vomfolgerichtigen Denken

„Wer intelligente Software entwickeln will, der musslogische Schlussfolgerungen algorithmisch umsetzen.

Die Logik liefert die nötigen Methoden.“

• Kodierung von gültigen Zusammenhängen und Regeln

• Logisches Schließen als Simulation von intelligentem Denken

• Hauptanwendung: Künstliche Intelligenz

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 13 von 36

Page 15: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logik für Informatiker: Darum (3)

Logisches Schließen = Problemlösen

„Bedeutende Klassen von (schweren) Problemenlassen sich durch logische Schlussfolgerung lösen.Algorithmen aus der Logik sind in vielen anderen

Bereichen anwendbar.“

• Logik als Spezifikationssprache für komplexe Probleme

• Logisches Schließen als Suche nach zulässigen Lösungen

• Anwendungen: Constraint-Satisfaction-Probleme undverwandte Optimierungsaufgaben

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 14 von 36

Page 16: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logik für Informatiker: Darum (4)

Logiken = Beschreibungssprachen

„Überall wo Informationen maschinell kodiert werdenund wo exakt spezifiziert ist, was eine Anwendung

aus dieser Kodierung ableiten darf,hat man es mit einer Art Logik zu tun.“

• Logik als Oberbegriff exakt spezifizierter Datenformate

• Schlussfolgerung zur Interpretation/Analyse/Optimierung

• Anwendungen: Wissensrepräsentation und Datenbanken

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 15 von 36

Page 17: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Was ist Logik?

„Logik“ ist ein allgemeiner Oberbegriff für viele mathematische undtechnische Formalismen, gekennzeichnet durch:

• Syntax: Sprache einer Logik (normalerweise Formeln mitlogischen Operatoren)

• Semantik: Definition der Bedeutung (Worauf beziehen sichdie Formeln? Wann ist eine Formel wahr oder falsch?)

Typische Zielstellung: Logische Schlussfolgerung

• Welche Schlüsse kann man aus einer gegebenen (Mengevon) Formel(n) ziehen?

• Spezifikation der korrekten Schlussfolgerungen sollte sich ausSemantik ergeben

• Praktische Berechnung von Schlussfolgerungen ist oftkompliziert

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 16 von 36

Page 18: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Was ist Logik?

„Logik“ ist ein allgemeiner Oberbegriff für viele mathematische undtechnische Formalismen, gekennzeichnet durch:

• Syntax: Sprache einer Logik (normalerweise Formeln mitlogischen Operatoren)

• Semantik: Definition der Bedeutung (Worauf beziehen sichdie Formeln? Wann ist eine Formel wahr oder falsch?)

Typische Zielstellung: Logische Schlussfolgerung

• Welche Schlüsse kann man aus einer gegebenen (Mengevon) Formel(n) ziehen?

• Spezifikation der korrekten Schlussfolgerungen sollte sich ausSemantik ergeben

• Praktische Berechnung von Schlussfolgerungen ist oftkompliziert

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 16 von 36

Page 19: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Was ist Logik?

„Logik“ ist ein allgemeiner Oberbegriff für viele mathematische undtechnische Formalismen, gekennzeichnet durch:

• Syntax: Sprache einer Logik (normalerweise Formeln mitlogischen Operatoren)

• Semantik: Definition der Bedeutung (Worauf beziehen sichdie Formeln? Wann ist eine Formel wahr oder falsch?)

Typische Zielstellung: Logische Schlussfolgerung

• Welche Schlüsse kann man aus einer gegebenen (Mengevon) Formel(n) ziehen?

• Spezifikation der korrekten Schlussfolgerungen sollte sich ausSemantik ergeben

• Praktische Berechnung von Schlussfolgerungen ist oftkompliziert

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 16 von 36

Page 20: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Viele Logiken

Es gibt sehr viele Logiken, z.B.

• Aussagenlogik

• Prädikatenlogik (erster Stufe)

• Prädikatenlogik zweiter Stufe

• Beschreibungslogiken (Wissensrepräsentation und KI)

• Temporallogiken (z.B. Verifikation zeitlicher Abläufe)

• Logikprogramme (Answer Set Programming, Prolog, . . . )

• Nicht-klassische Logiken (z.B. intuitionistische Logik)

• Mehrwertige Logiken (z.B. probabilistische Logik)

• . . . und viele andere mehr

{ In dieser Vorlesung lernen wir zunächst Aussagenlogik kennen

(Mehr gibt es in der Vorlesung „Theoretische Informatik und Logik“)

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 17 von 36

Page 21: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Aussagenlogik

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 18 von 36

Page 22: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

AussagenlogikDie Aussagenlogik untersucht logische Verknüpfungen vonatomaren Aussagen.

Atomare Aussagen sind Behauptungen, die wahr oder falsch seinkönnen, z.B.:

A1 „Morgen schneit es.“

A2 „Wir werden einen Schneemann bauen.“

B1 „Die Vorstellung von der globalen Erderwärmung wurde vonden Chinesen erfunden.“

B2 „Die Temperatur der Ozeane ist seit 1998 in unverminderterGeschwindigkeit angestiegen.“

C1 „Typ-2-Sprachen sind unter Schnitt abgeschlossen.“

C2 „Typ-2-Sprachen sind unter Komplement abgeschlossen.“

C3 „Typ-2-Sprachen sind unter Vereinigung abgeschlossen.“

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 19 von 36

Page 23: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Aussagen verknüpfen

Atomare Aussagen können mithilfe logischer Junktoren verknüpftwerden:• A1→ A2: „Wenn es morgen schneit, dann werden wir einen

Schneemann bauen.“

• A1 ∨ ¬A1: „Entweder schneit es morgen oder nicht.“

• B1→ ¬B2: „Falls die Chinesen die globale Erwärmungerfunden haben, dann steigt die Temperatur der Ozeanenicht unvermindert an.“

• (C1 ∧ C2)→ C3: „Sind Typ-2-Sprachen unter Schnitt undKomplement abgeschlossen, dann sind sie auch unterVereinigung abgeschlossen.“

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 20 von 36

Page 24: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logisches Schließen

Wenn einige Formeln als wahr angenommen werden, dann kanndie Wahrheit anderer Formeln daraus abgeleitet werden.

Beispiele:

• Aus B2 und B1→ ¬B2 folgt ¬B1

• Aus C1, ¬C3 und (C1 ∧ C2)→ C3 folgt ¬C2

• Aus A1→ A2 und ¬A1 folgt nicht ¬A2

Die Gültigkeit bestimmter Schlussfolgerungen hat nichts mitSchneemännern, Erderwärmung oder Typ-2-Sprachen zu tun!Sie ist eine rein logische Konsequenz.

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 21 von 36

Page 25: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logisches Schließen

Wenn einige Formeln als wahr angenommen werden, dann kanndie Wahrheit anderer Formeln daraus abgeleitet werden.

Beispiele:

• Aus B2 und B1→ ¬B2 folgt ¬B1

• Aus C1, ¬C3 und (C1 ∧ C2)→ C3 folgt ¬C2

• Aus A1→ A2 und ¬A1 folgt nicht ¬A2

Die Gültigkeit bestimmter Schlussfolgerungen hat nichts mitSchneemännern, Erderwärmung oder Typ-2-Sprachen zu tun!Sie ist eine rein logische Konsequenz.

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 21 von 36

Page 26: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Beispiel: Logelei

Anna behauptet: „Barbara lügt!“

Barbara behauptet: „Chris lügt!“

Chris behauptet: „Anna und Barbara lügen!“

Wer lügt?(Und wie kann man das beweisen?)

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 22 von 36

Page 27: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Aussagenlogik: SyntaxWir betrachten eine abzählbar unendliche Menge P von atomarenAussagen (auch bekannt als: aussagenlogische Variablen,Propositionen oder schlicht Atome)

Die Menge der aussagenlogischen Formeln ist induktiva definiert:

• Jedes Atom p ∈ P ist eine aussagenlogische Formel• Wenn F und G aussagenlogische Formeln sind, so auch:

– ¬F: Negation, „nicht F“– (F ∧ G): Konjunktion, „F und G“– (F ∨ G): Disjunktion, „F oder G“– (F → G): Implikation, „F impliziert G“– (F ↔ G): Äquivalenz, „F ist äquivalent zu G“

aDas bedeutet: Die Definition ist selbstbezüglich und soll die kleinsteMenge an Formeln beschreiben, die alle Bedingungen erfüllen.

Wir verzichten hier oft auf „aussagenlogisch“ und sprechen z.B.einfach von „Formeln“.Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 23 von 36

Page 28: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Beispiele

Die folgenden Ausdrücke sind aussagenlogische Formeln:

• p

• ((p→ q)→ p)→ p

• ¬¬¬p

Die folgenden Ausdrücke sind keine aussagenlogischen Formeln:

• p ∧ q ∨ r (fehlende Klammern)

Vereinfachung: Äußere Klammern dürfen wegfallen, d.h. wirerlauben z.B. p→ q anstatt auf (p→ q) zu bestehen.

• (p← q) (Operator← undefiniert)

• p ∧ q (wir verwenden nicht als Negation)

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 24 von 36

Page 29: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

TeilformelnWir können Formeln als Wörter über (endlichen Teilmengen aus)dem unendlichen Alphabet P ∪ {¬,∧,∨,→,↔, (, )} sehen:

F→ P | ¬F | (F∧F) | (F∨F) | (F→F) | (F↔F)

Eine Teilformel ist ein Teilwort (Infix) einer Formel, welches selbsteine Formel ist. Teilformeln werden auch Unterformeln genannt.

Alternativ kann man Teilformeln auch rekursiv definieren:

Die Menge Sub(F) der Teilformeln einer Formel F ist definiert als:

Sub(F) =

{F} falls F ∈ P

{¬G} ∪ Sub(G) falls F = ¬G

{(G1 ∧ G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 ∧ G2)

{(G1 ∨ G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 ∨ G2)

{(G1 → G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 → G2)

{(G1 ↔ G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 ↔ G2)

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 25 von 36

Page 30: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

TeilformelnWir können Formeln als Wörter über (endlichen Teilmengen aus)dem unendlichen Alphabet P ∪ {¬,∧,∨,→,↔, (, )} sehen:

F→ P | ¬F | (F∧F) | (F∨F) | (F→F) | (F↔F)

Eine Teilformel ist ein Teilwort (Infix) einer Formel, welches selbsteine Formel ist. Teilformeln werden auch Unterformeln genannt.

Alternativ kann man Teilformeln auch rekursiv definieren:

Die Menge Sub(F) der Teilformeln einer Formel F ist definiert als:

Sub(F) =

{F} falls F ∈ P

{¬G} ∪ Sub(G) falls F = ¬G

{(G1 ∧ G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 ∧ G2)

{(G1 ∨ G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 ∨ G2)

{(G1 → G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 → G2)

{(G1 ↔ G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 ↔ G2)

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 25 von 36

Page 31: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

TeilformelnWir können Formeln als Wörter über (endlichen Teilmengen aus)dem unendlichen Alphabet P ∪ {¬,∧,∨,→,↔, (, )} sehen:

F→ P | ¬F | (F∧F) | (F∨F) | (F→F) | (F↔F)

Eine Teilformel ist ein Teilwort (Infix) einer Formel, welches selbsteine Formel ist. Teilformeln werden auch Unterformeln genannt.

Alternativ kann man Teilformeln auch rekursiv definieren:

Die Menge Sub(F) der Teilformeln einer Formel F ist definiert als:

Sub(F) =

{F} falls F ∈ P

{¬G} ∪ Sub(G) falls F = ¬G

{(G1 ∧ G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 ∧ G2)

{(G1 ∨ G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 ∨ G2)

{(G1 → G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 → G2)

{(G1 ↔ G2)} ∪ Sub(G1) ∪ Sub(G2) falls F = (G1 ↔ G2)Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 25 von 36

Page 32: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Semantik

Was bedeutet eine aussagenlogische Formel?

• Atome an sich bedeuten zunächst nichts{ sie können einfach wahr oder falsch sein

• Je nachdem, welche Atome wahr sind und welche falsch,ergeben sich verschiedene „Interpretationen“{ dargestellt durch Wertzuweisungen

(Funktionen von P nach {1, 0}; 1=„wahr“ und 0=„falsch“)

• Die Wahrheit (oder Falschheit) einer Formel ergibt sich ausdem Wahrheitswert der in ihr vorkommenden Atome{Wertzuweisungen machen Formeln wahr oder falsch

Die Bedeutung einer Formel besteht darin, dass sie uns Infor-mationen darüber liefert, welche Wertzuweisungen möglich sind,wenn die Formel wahr sein soll.

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 26 von 36

Page 33: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Semantik

Was bedeutet eine aussagenlogische Formel?

• Atome an sich bedeuten zunächst nichts{ sie können einfach wahr oder falsch sein

• Je nachdem, welche Atome wahr sind und welche falsch,ergeben sich verschiedene „Interpretationen“{ dargestellt durch Wertzuweisungen

(Funktionen von P nach {1, 0}; 1=„wahr“ und 0=„falsch“)

• Die Wahrheit (oder Falschheit) einer Formel ergibt sich ausdem Wahrheitswert der in ihr vorkommenden Atome{Wertzuweisungen machen Formeln wahr oder falsch

Die Bedeutung einer Formel besteht darin, dass sie uns Infor-mationen darüber liefert, welche Wertzuweisungen möglich sind,wenn die Formel wahr sein soll.

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 26 von 36

Page 34: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Semantik

Was bedeutet eine aussagenlogische Formel?

• Atome an sich bedeuten zunächst nichts{ sie können einfach wahr oder falsch sein

• Je nachdem, welche Atome wahr sind und welche falsch,ergeben sich verschiedene „Interpretationen“{ dargestellt durch Wertzuweisungen

(Funktionen von P nach {1, 0}; 1=„wahr“ und 0=„falsch“)

• Die Wahrheit (oder Falschheit) einer Formel ergibt sich ausdem Wahrheitswert der in ihr vorkommenden Atome{Wertzuweisungen machen Formeln wahr oder falsch

Die Bedeutung einer Formel besteht darin, dass sie uns Infor-mationen darüber liefert, welche Wertzuweisungen möglich sind,wenn die Formel wahr sein soll.

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 26 von 36

Page 35: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Semantik

Was bedeutet eine aussagenlogische Formel?

• Atome an sich bedeuten zunächst nichts{ sie können einfach wahr oder falsch sein

• Je nachdem, welche Atome wahr sind und welche falsch,ergeben sich verschiedene „Interpretationen“{ dargestellt durch Wertzuweisungen

(Funktionen von P nach {1, 0}; 1=„wahr“ und 0=„falsch“)

• Die Wahrheit (oder Falschheit) einer Formel ergibt sich ausdem Wahrheitswert der in ihr vorkommenden Atome{Wertzuweisungen machen Formeln wahr oder falsch

Die Bedeutung einer Formel besteht darin, dass sie uns Infor-mationen darüber liefert, welche Wertzuweisungen möglich sind,wenn die Formel wahr sein soll.

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 26 von 36

Page 36: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Wertzuweisungen können Formeln erfüllenEine Wertzuweisung ist eine Funktion w : P→ {1, 0}

Eine Wertzuweisung w erfüllt eine Formel F, in Symbolen w |= F,wenn eine der folgenden rekursiven Bedingungen gilt:

Form von F w |= F wenn: w 6|= F wenn:

F ∈ P: w(F) = 1 w(F) = 0

F = ¬G w 6|= G w |= G

F = (G1 ∧ G2) w |= G1 und w |= G2 w 6|= G1 oder w 6|= G2

F = (G1 ∨ G2) w |= G1 oder w |= G2 w 6|= G1 und w 6|= G2

F = (G1 → G2) w 6|= G1 oder w |= G2 w |= G1 und w 6|= G2

F = (G1 ↔ G2) w |= G1 und w |= G2 w |= G1 und w 6|= G2

oder oderw 6|= G1 und w 6|= G2 w 6|= G1 und w |= G2

Dabei bedeutet „A oder B“ immer „A oder B oder beides“.Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 27 von 36

Page 37: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Formeln Wahrheitswerte zuweisenWir können Wertzuweisungen von Atomen auf Formeln erweitern:

w(F) =

1 falls w |= F

0 falls w 6|= F

Wahrheitswertetabellen illustrieren die Semantik der Junktoren:

w(F) w(¬F)

0 1

1 0

w(F) w(G) w(F ∧ G) w(F ∨ G) w(F → G) w(F ↔ G)

0 0 0 0 1 1

1 0 0 1 0 0

0 1 0 1 1 0

1 1 1 1 1 1

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 28 von 36

Page 38: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Formeln Wahrheitswerte zuweisenWir können Wertzuweisungen von Atomen auf Formeln erweitern:

w(F) =

1 falls w |= F

0 falls w 6|= F

Wahrheitswertetabellen illustrieren die Semantik der Junktoren:

w(F) w(¬F)

0 1

1 0

w(F) w(G) w(F ∧ G) w(F ∨ G) w(F → G) w(F ↔ G)

0 0 0 0 1 1

1 0 0 1 0 0

0 1 0 1 1 0

1 1 1 1 1 1Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 28 von 36

Page 39: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Wahrheitswerte von Formeln bestimmen

• Der Wahrheitswert einer Formel hängt nur vom Wahrheitswertder (endlich vielen) Atome ab, die in ihr vorkommen.{Wir geben oft nur diese an.

• Der Wahrheitswert einer Formel ergibt sich rekursiv aus demWahrheitswert ihrer Teilformeln.{ Darstellung in Wahrheitswertetabelle

Beispiel: Für die Formel F = ((p → q) ↔ (¬q → ¬p)) und Wert-zuweisung w mit w(p) = 0 und w(q) = 1 ergibt sich die folgendeTabelle:

w(p) w(q) w(p→ q) w(¬p) w(¬q) w(¬q→ ¬p) w(F)

0 1 1 1 0 1 1

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 29 von 36

Page 40: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Beispiel: Logelei

Anna behauptet: „Barbara lügt!“

A↔ ¬B

Barbara behauptet: „Chris lügt!“

B↔ ¬C

Chris behauptet: „Anna und Barbara lügen!“

C ↔ (¬A ∧ ¬B)

Wer lügt?(Und wie kann man das beweisen?)

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 30 von 36

Page 41: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Beispiel: Logelei

Anna behauptet: „Barbara lügt!“ A↔ ¬B

Barbara behauptet: „Chris lügt!“

B↔ ¬C

Chris behauptet: „Anna und Barbara lügen!“

C ↔ (¬A ∧ ¬B)

Wer lügt?(Und wie kann man das beweisen?)

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 30 von 36

Page 42: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Beispiel: Logelei

Anna behauptet: „Barbara lügt!“ A↔ ¬B

Barbara behauptet: „Chris lügt!“ B↔ ¬C

Chris behauptet: „Anna und Barbara lügen!“

C ↔ (¬A ∧ ¬B)

Wer lügt?(Und wie kann man das beweisen?)

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 30 von 36

Page 43: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Beispiel: Logelei

Anna behauptet: „Barbara lügt!“ A↔ ¬B

Barbara behauptet: „Chris lügt!“ B↔ ¬C

Chris behauptet: „Anna und Barbara lügen!“ C ↔ (¬A ∧ ¬B)

Wer lügt?(Und wie kann man das beweisen?)

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 30 von 36

Page 44: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logische Konsequenzen

Eine Wertzuweisung w ist Modell einer Formel F wenn w |= F(also wenn w(F) = 1). Ist F eine (möglicherweise unendliche)Menge von Formeln, dann ist w ein Modell der Menge F wennw |= F für alle F ∈ F gilt. In diesem Fall schreiben wir w |= F .

Die logischen Schlussfolgerungen aus einer Formel(menge)ergeben sich aus ihren Modellen:

Sei F eine Menge von Formeln. Eine Formel G ist eine logischeKonsequenz aus F wenn jedes Modell von F auch ein Modellvon G ist. In diesem Fall schreiben wir F |= G.

{ Die Formeln in F schränken die möglichen Interpretationen ein:Je mehr Formeln wahr sein sollen, desto weniger Freiheitengibt es bei der Wahl der Modelle

{ G ist eine logische Konsequenz wenn gilt: falls F wahr ist, dannist auch G garantiert wahr

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 31 von 36

Page 45: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Logische Konsequenzen

Eine Wertzuweisung w ist Modell einer Formel F wenn w |= F(also wenn w(F) = 1). Ist F eine (möglicherweise unendliche)Menge von Formeln, dann ist w ein Modell der Menge F wennw |= F für alle F ∈ F gilt. In diesem Fall schreiben wir w |= F .

Die logischen Schlussfolgerungen aus einer Formel(menge)ergeben sich aus ihren Modellen:

Sei F eine Menge von Formeln. Eine Formel G ist eine logischeKonsequenz aus F wenn jedes Modell von F auch ein Modellvon G ist. In diesem Fall schreiben wir F |= G.

{ Die Formeln in F schränken die möglichen Interpretationen ein:Je mehr Formeln wahr sein sollen, desto weniger Freiheitengibt es bei der Wahl der Modelle

{ G ist eine logische Konsequenz wenn gilt: falls F wahr ist, dannist auch G garantiert wahr

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 31 von 36

Page 46: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Beispiel: Logelei

Anna behauptet: „Barbara lügt!“ A↔ ¬B

Barbara behauptet: „Chris lügt!“ B↔ ¬C

Chris behauptet: „Anna und Barbara lügen!“ C ↔ (¬A ∧ ¬B)

w(A) w(B) w(C) w(A↔ ¬B) w(B↔ ¬C) w(C ↔ (¬A ∧ ¬B))

0 0 0 0 0 0

1 0 0 1 0 1

0 1 0 1 1 1

1 1 0 0 1 1

0 0 1 0 1 1

1 0 1 1 1 0

0 1 1 1 0 0

1 1 1 0 0 0Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 32 von 36

Page 47: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Beispiel: Logelei (2)

Anna behauptet: „Barbara lügt!“ A↔ ¬B

Barbara behauptet: „Chris lügt!“ B↔ ¬C

Chris behauptet: „Anna und Barbara lügen!“ C ↔ (¬A ∧ ¬B)

w(A) w(B) w(C) w(A↔ ¬B) w(B↔ ¬C) w(C ↔ (¬A ∧ ¬B))

0 1 0 1 1 1{ Genau ein Modell (bezüglich der relevanten Atome)

Logische Konsequenzen: Alle Formeln, die unter einerWertzuweisung mit w(A) = 0, w(B) = 1 und w(C) = 0 wahr sind, z.B.:• ¬A („Anna lügt“)• ¬C („Chris lügt“)• ¬A ∧ ¬C („Anna und Chris lügen“)• B („Barbara sagt die Wahrheit“)• Aber auch: D ∨ ¬D

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 33 von 36

Page 48: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Beispiel: Logelei (2)

Anna behauptet: „Barbara lügt!“ A↔ ¬B

Barbara behauptet: „Chris lügt!“ B↔ ¬C

Chris behauptet: „Anna und Barbara lügen!“ C ↔ (¬A ∧ ¬B)

w(A) w(B) w(C) w(A↔ ¬B) w(B↔ ¬C) w(C ↔ (¬A ∧ ¬B))

0 1 0 1 1 1{ Genau ein Modell (bezüglich der relevanten Atome)

Logische Konsequenzen: Alle Formeln, die unter einerWertzuweisung mit w(A) = 0, w(B) = 1 und w(C) = 0 wahr sind, z.B.:• ¬A („Anna lügt“)• ¬C („Chris lügt“)• ¬A ∧ ¬C („Anna und Chris lügen“)• B („Barbara sagt die Wahrheit“)• Aber auch: D ∨ ¬D

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 33 von 36

Page 49: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Allgemeingültigkeit und Co.

Eine Formel F ist:

• unerfüllbar (oder inkonsistent), wenn sie keine Modelle hat

• erfüllbar (oder konsistent), wenn sie Modelle hat

• allgemeingültig (oder eine Tautologie), wenn alleWertzuweisungen Modelle für die Formel sind

• widerlegbar, wenn sie nicht allgemeingültig ist

Diese Begriffe kann man für Mengen von Formeln genauso defi-nieren.

Beispiel:

• p ∧ ¬p ist unerfüllbar (und widerlegbar)

• p ∨ ¬p ist allgemeingültig (und erfüllbar)

• p ∧ q ist erfüllbar und widerlegbar

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 34 von 36

Page 50: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Allgemeingültigkeit und Unerfüllbarkeit

Satz:

(1) Eine allgemeingültige Formel ist logische Konsequenz jederanderen Formel(menge).

(2) Eine unerfüllbare Formel(menge) hat jede andere Formel alslogische Konsequenz.

Beweis: Folgt direkt aus Definition von logischer Konsequenz. Für(2) ist es wichtig, dass eine Eigenschaft „für alle Modelle“ gilt, wennes keine Modelle gibt (sie gilt dann für „alle null Modelle“). �

Der unerwartete(?) Effekt (2) ist im Deutschen sprichwörtlich:

„Wenn das stimmt, dann bin ich der Kaiser von China!“

drückt aus, dass aus einer mutmaßlich falschen Annahme allesfolgt, selbst wenn es offensichtlich unwahr ist.

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 35 von 36

Page 51: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Allgemeingültigkeit und Unerfüllbarkeit

Satz:

(1) Eine allgemeingültige Formel ist logische Konsequenz jederanderen Formel(menge).

(2) Eine unerfüllbare Formel(menge) hat jede andere Formel alslogische Konsequenz.

Beweis: Folgt direkt aus Definition von logischer Konsequenz. Für(2) ist es wichtig, dass eine Eigenschaft „für alle Modelle“ gilt, wennes keine Modelle gibt (sie gilt dann für „alle null Modelle“). �

Der unerwartete(?) Effekt (2) ist im Deutschen sprichwörtlich:

„Wenn das stimmt, dann bin ich der Kaiser von China!“

drückt aus, dass aus einer mutmaßlich falschen Annahme allesfolgt, selbst wenn es offensichtlich unwahr ist.

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 35 von 36

Page 52: Formale Systeme - 21. Vorlesung: AussagenlogikAussagenlogik Die Aussagenlogik untersuchtlogische Verknüpfungen von atomaren Aussagen. Atomare Aussagensind Behauptungen, die wahr oder

Zusammenfassung und Ausblick

Mithilfe der Aussagenlogik kann man logische Beziehungenatomarer Aussagen spezifizieren

Wertzuweisungen können eine aussagenlogische Formel erfüllen –dann nennt man sie Modell – oder widerlegen

Die Modelle einer Formel(menge) definieren ihre logischenKonsequenzen (=„alles, was in diesen Fällen noch gilt“)

Offene Fragen:

• Geht logisches Schließen auch ohneWahrheitswertetabellen?

• Wie (in)effizient ist logisches Schließen?

• Was hat das mit Sprachen, Berechnung und TMs zu tun?

Markus Krötzsch, 9. Januar 2017 Formale Systeme Folie 36 von 36