Transcript
Syntax Semantik
Syntax Semantik
Motivation Definition
Motivation Formale Grundlagen der Informatik 1 Kapitel 14 Mit der Aussagenlogik lassen sich einfache Verkn¨ upfungen zwischen (atomaren) Gebilden ausdr¨ ucken z.B.
Aussagenlogik Syntax & Semantik
A ∧ B f¨ ur A und B A ∨ B f¨ ur A oder B Frank Heitmann
[email protected]
Wenn A und B f¨ ur etwas stehen (z.B. A ≈ ’es regnet’) lassen sich so kompliziertere Aussagen formen.
1. Juni 2015 Frank Heitmann
[email protected]
Syntax Semantik
1/36
Frank Heitmann
[email protected]
Motivation Definition
Syntax Semantik
Motivation
2/36
Motivation Definition
Motivation
(Aussagen-)Logik ... als Grundlage der Mathematik,
Man kann dann 1
Etwas aus der realen Welt in der Logik abstrakt ausdr¨ ucken.
2
In der Logik Schl¨ usse ziehen.
3
Dies wieder in der realen Welt interpretieren.
f¨ ur Programmiersprachen (z.B. Prolog), f¨ ur k¨ unstliche Intelligenzen, f¨ ur Datenbanken, zur Beschreibung von Schaltkreisen, in der Verifikation ...
Frank Heitmann
[email protected]
3/36
Frank Heitmann
[email protected]
4/36
Syntax Semantik
Motivation Definition
Syntax Semantik
Motivation
Motivation Definition
Motivation Eine Aussage im Sinne der Aussagenlogik ist ein atomares sprachliches Gebilde das entweder wahr oder falsch ist. Notiert als A, B, C oder A1 , A2 , A3 , ... Diese nennt man Aussagensymbole. Die Aussagenlogik betrachtet den Wahrheitsgehalt einfacher Verkn¨ upfungen zwischen atomaren sprachlichen Gebilden (also Aussagen). Dies sind:
Die Aussagenlogik ist eine ganz grundlegende Logik (Basis vieler anderer Logiken bzw. in ihnen enthalten) an ihr l¨asst sich vieles ein¨ uben ist uns schon im SAT-Problem begegnet (und ist also ganz grundlegend f¨ ur den Begriff der NP-Vollst¨andigkeit und der Frage, was effizient l¨ osbar ist)
¬ f¨ ur nicht (Negation) ∧ f¨ ur und (Konjunktion) ∨ f¨ ur oder (Disjunktion) ⇒ f¨ ur wenn ... dann (Implikation) ⇔ f¨ ur genau dann, wenn (Biimplikation)
Die ¬, ∧, ∨, ⇒, ⇔ nennt man Junktoren.
Frank Heitmann
[email protected]
Syntax Semantik
5/36
Frank Heitmann
[email protected]
Motivation Definition
Syntax Semantik
Exkurs
6/36
Motivation Definition
Syntax: Motivation
Belegt man einzelne Aussagensymbole durch einfache (atomare) Aussagen, so kann man (nat¨ urlichsprachliche) S¨atze u ¨bertragen. Z.B.
Die Syntax legt nun zun¨achst nur fest, wie mit atomaren Formeln und Junktoren komplexe Formeln erstellen kann. Diese Formeln sind zun¨achst nur Zeichenkette ohne Bedeutung (Semantik).
A = es regnet B = ich trage einen Schirm A ⇒ B = Wenn es regnet, dann trage ich einen Schirm (Dabei ist aber Vorsicht geboten, da das nicht immer dem entspricht, was man intuitiv von der nat¨ urlichen Sprache erwartet.)
Frank Heitmann
[email protected]
7/36
Frank Heitmann
[email protected]
8/36
Syntax Semantik
Motivation Definition
Syntax Semantik
Syntax: Definition
Motivation Definition
Syntax: Definition Noch ein paar Bezeichnungen:
Definition (Syntax der Aussagenlogik) Mit ASAL sei die Menge der Aussagensymbol der Aussagenlogik bezeichnet. Wir notieren diese u ¨blicherweise als A1 , A2 , A3 , . . . oder A, B, C , . . .. Die Menge LAL der Formeln der Aussagenlogik definieren wir mittels 1
Jedes A ∈ ASAL ist eine (atomare) Formel.
2
Ist F eine Formel, so ist auch ¬F eine Formel.
3
Sind F und G Formeln, so sind auch (F ∨ G ), (F ∧ G ), (F ⇒ G ) und (F ⇔ G ) Formeln.
4
Es gibt keine anderen Formeln, als die, die durch endliche Anwendungen der Schritte 1-3 erzeugt werden.
Frank Heitmann
[email protected]
Syntax Semantik
Manchmal f¨ uhrt man noch das Alphabet ein. Dies besteht aus den Aussagesymbolen sowie aus den Junktoren und den Klammern ( und ). Die ¬, ∨, ∧, ⇒, ⇔ werden als Junktoren bezeichnet. Die entstehenden Formeln als Negation (¬), Disjunktion (∨), Konjunktion (∧), Implikation (⇒) und Biimplikation (⇔). Eine Formel, die beim Aufbau einer Formel F verwendet wird, heißt Teilformel von F . Außerdem ist F Teilformel von sich selbst. Der Junktor, der im letzten Konstruktionsschritt verwendet wird, heißt Hauptoperator. Nach ihm werden komplexe Formeln benannt. 9/36
Motivation Definition
Syntax Semantik
Syntax: Beispiel
10/36
Motivation Definition
Strukturb¨aume
Man kann Formeln auch durch sogenannte Strukturb¨aume ausdr¨ ucken:
Beispiele:
Der Hauptoperator markiert die Wurzel.
((A ∨ C ) ∧ B). Dies ist eine Konjunktion, da zuletzt ∧ angewandt wurde. Teilformeln sind A, B, C , (A ∨ C ) und ((A ∨ C ) ∧ B).
Teilformeln entsprechen Teilb¨aumen. Die Reihenfolge der Teilformeln wird beibehalten (linke Teilformel, linkes Kind).
(A ∨ ∨C ) ist keine Formel. A ∨ C zun¨achst auch nicht (Klammerung!)
Frank Heitmann
[email protected]
Frank Heitmann
[email protected]
Die Aussagesymbole werden dann die Bl¨atter des Baumes, die Junktoren sind die inneren Knoten. Dabei hat ¬ ein Kind, alle anderen Junktoren zwei.
11/36
Frank Heitmann
[email protected]
12/36
Syntax Semantik
Motivation Definition
Syntax Semantik
Strukturb¨aume
Motivation Definition
Strukturelle Induktion und Rekursion
Beispiel: ((A ∨ C ) ∧ ¬B) Den Aufbau komplexer Formeln aus einfache(re)n Formeln kann man nutzen um
∧
∨
Eigenschafen von Formeln nachzuweisen (strukturelle Induktion)
2
Funktionen u ¨ber die Formelmenge zu definieren (strukturelle Rekursion)
¬
A
C
B
Frank Heitmann
[email protected]
Syntax Semantik
13/36
Syntax Semantik
Anzunehmen, dass B(F ) und B(G ) f¨ ur zwei Formeln F und G gilt (Induktionsannahme).
3
Zu zeigen, dass unter der Annahme bei 2. nun auch B(¬F ), B(F ∨ G ), B(F ∧ G ), B(F ⇒ G ) und B(F ⇔ G ) gelten (Induktionsschritt).
Motivation Definition
Um eine Funktion f : LAL → D zu definieren (D ist dabei eine beliebige Menge) gen¨ ugt es:
Zu zeigen, dass B(F ) f¨ ur jede atomare Formel F gilt (Induktionsanfang).
2
14/36
Strukturelle Rekursion
Um eine Behauptung B(F ) f¨ ur jede Formel F ∈ LAL zu zeigen gen¨ ugt es:
Frank Heitmann
[email protected]
Frank Heitmann
[email protected]
Motivation Definition
Strukturelle Induktion
1
1
15/36
1
f (A) f¨ ur jedes A ∈ ASAL festzulegen.
2
eine Funktion f¬ : D → D und f¨ ur jeden Junktor ◦ ∈ {∨, ∧, ⇒, ⇔} eine Funktion f◦ : D × D → D zu definieren. Es ist dann z.B. f ((F ∧ G )) = f∧ (f (F ), f (G )).
Frank Heitmann
[email protected]
16/36
Syntax Semantik
Motivation Definition
Syntax Semantik
Strukturelle Rekursion: Beispiele
Grad und Tiefe
Wir definieren Grad und Tiefe einer Formel: 1
Die Funktion grad z¨ahlt die Anzahl der Junktoren. Die tiefe z¨ahlt die Anzahl der Junktoren auf dem l¨angsten Pfad im Strukturbaum (also quasi die tiefste Verschachtelung).
F¨ ur jedes A ∈ ASAL sei grad(A) = tiefe(A) = 0.
2
F¨ ur ¬ sei
Anmerkung
grad(¬F ) = grad¬ (grad(F )) = grad(F ) + 1 und tiefe(¬F ) = tiefe¬ (tiefe(F )) = tiefe(F ) + 1. 3
Motivation Definition
Man definiert also die Rekursionsbasis (was bei den Aussagesymbolen passiert) und den Rekursionsschritt (was bei den einzelnen Junktoren passiert; wobei man hier Negation und die zweistelligen Junktoren meist getrennt behandelt. Die zweistelligen Junktoren m¨ ussen dabei nicht wie oben alle gleich behandelt werden.)
F¨ ur ◦ ∈ {∨, ∧, ⇒, ⇔} sei grad((F ◦ G )) = grad◦ (grad(F ), grad(G )) = grad(F ) + grad(G ) + 1 und tiefe((F ◦ G )) = tiefe◦ (tiefe(F ), tiefe(G )) = max(tiefe(F ), tiefe(G )) + 1.
Frank Heitmann
[email protected]
Syntax Semantik
17/36
Frank Heitmann
[email protected]
Motivation Definition
Syntax Semantik
Zusammenfassung
18/36
Definition ¨ Aquivalenzen
Grundbegriffe
Zusammenfassung bis hier: Wir wollen nun die Bedeutung von Formeln definieren.
Motivation Definition der Syntax
Dazu
Alphabet, Junktor Aussagesymbol, atomare Formel, komplexe Formel Hauptoperator, Teilformel Negation, Disjunktion, Konjunktion, Implikation, Biimplikation
belegen wir die atomaren Formeln mit Wahrheitswerten berechnen daraus den Wahrheitswert einer komplexen Formel Die Menge der Wahrheitswerte enth¨alt genau zwei Elemente
Strukturb¨aume strukturelle Induktion
1 (’wahr’) und
strukturelle Rekursion
0 (’falsch’).
Grad und Tiefe einer Formel
Frank Heitmann
[email protected]
19/36
Frank Heitmann
[email protected]
20/36
Syntax Semantik
Definition ¨ Aquivalenzen
Syntax Semantik
Syntax: Definition (Wdh.)
Definition ¨ Aquivalenzen
Semantik
Definition (Syntax der Aussagenlogik) Mit ASAL sei die Menge der Aussagensymbol der Aussagenlogik bezeichnet. Wir notieren diese u ¨blicherweise als A1 , A2 , A3 , . . . oder A, B, C , . . .. Die Menge LAL der Formeln der Aussagenlogik definieren wir mittels 1
Jedes A ∈ ASAL ist eine (atomare) Formel.
2
Ist F eine Formel, so ist auch ¬F eine Formel.
3
Sind F und G Formeln, so sind auch (F ∨ G ), (F ∧ G ), (F ⇒ G ) und (F ⇔ G ) Formeln.
4
Es gibt keine anderen Formeln, als die, die durch endliche Anwendungen der Schritte 1-3 erzeugt werden.
Frank Heitmann
[email protected]
Syntax Semantik
Eine Belegung weist nun jedem Aussagesymbol einen Wahrheitswert zu. Aussagen und Formeln k¨onnen dann unter einer Belegung wahr oder falsch sein. Die aussagenlogische Semantik regelt u.a., wie komplexe Formeln zu Wahrheitswerten kommen.
21/36
Frank Heitmann
[email protected]
Definition ¨ Aquivalenzen
Syntax Semantik
Semantik
Definition ¨ Aquivalenzen
Semantik - Anmerkung
Definition (Semantik der Aussagenlogik)
Anmerkung Bspw. die Definition
Eine Belegung ist eine Funktion AAS : ASAL → {0, 1}, die jedem Aussagesymbol einen Wahrheitswert zuordnet. Zu dieser wird rekursiv eine Funktion A : LAL → {0, 1} definiert, die alle Formeln bewertet. Es ist f¨ ur jedes A ∈ ASAL ist A(A) = AA S(A) und f¨ ur alle Formeln F , G ∈ LAL sei
A((F ∨ G )) = 1 gdw. A(F ) = 1 oder A(G ) = 1 bedeutet, dass A(F ∨ G ) zu 1 ausgewertet wird, wenn
A(¬F ) = 1 genau dann, wenn A(F ) = 0
A(F ) = 1 ist oder wenn
A((F ∨ G )) = 1 gdw. A(F ) = 1 oder A(G ) = 1
A(G ) = 1 ist oder wenn
A((F ∧ G )) = 1 gdw. A(F ) = 1 und A(G ) = 1
beides gilt. In allen anderen F¨allen (hier nur A(F ) = A(G ) = 0) ist A((F ∨ G )) = 0.
A((F ⇒ G )) = 1 gdw. A(F ) = 0 oder A(G ) = 1 A((F ⇔ G )) = 1 gdw. A(F ) = A(G )
Frank Heitmann
[email protected]
22/36
23/36
Frank Heitmann
[email protected]
24/36
Syntax Semantik
Definition ¨ Aquivalenzen
Syntax Semantik
Semantik - Wahrheitstafeln
Zur Nachbereitung
Wahrheitstafeln geben f¨ ur die atomaren Formeln alle m¨oglichen Belegungen an und f¨ ur die anderen Formeln die entsprechenden Bewertungen. Sie stellen die Definition von eben u ¨bersichtlich dar. A B 0 0 0 1 1 0 1 1
F¨ ur ¬A h¨atte auch die kleinere Tabelle A 0 1
¬A A ∨ B A ∧ B A ⇒ B A ⇔ B 1 0 0 1 1 1 1 0 1 0 0 1 0 0 0 0 1 1 1 1
Frank Heitmann
[email protected]
Syntax Semantik
¬A 1 0
gen¨ ugt, aber so wie oben hat dann alles in eine Tabelle gepasst.
25/36
Frank Heitmann
[email protected]
Definition ¨ Aquivalenzen
Aufgabe A B 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1
Definition ¨ Aquivalenzen
26/36
Syntax Semantik
Definition ¨ Aquivalenzen
C ∧ ¬D 0 0 1 0 0 0 1 0 0 0 1 0 0 0 1 0
¬(A ∨ ¬B) ∧ (C ∧ ¬D) 0 0 0 0 0 0 1 0 0 0 0 0 0 0 0 0
L¨osung der Aufgabe C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
A ∨ ¬B
C ∧ ¬D
Frank Heitmann
[email protected]
¬(A ∨ ¬B) ∧ (C ∧ ¬D)
A B 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 1 0 1 0 1 0 1 0 1 1 1 1 1 1 1 1 27/36
C 0 0 1 1 0 0 1 1 0 0 1 1 0 0 1 1
D 0 1 0 1 0 1 0 1 0 1 0 1 0 1 0 1
A ∨ ¬B 1 1 1 1 0 0 0 0 1 1 1 1 1 1 1 1
Frank Heitmann
[email protected]
28/36
Syntax Semantik
Definition ¨ Aquivalenzen
Syntax Semantik
Wahrheitstafeln: Anmerkungen
Kategorien
Definition Eine Belegung A mit A(F ) = 1 nennt man ein Modell f¨ ur F oder eine erf¨ ullende Belegung von F . Ist A(F ) = 0, so ist A eine falsifizierende Belegung von F .
In jeder Zeile einer Wahrheitstafel steht eine Belegung. Jede Zeile beschreibt einen (prinzipiell) m¨oglichen Zustand der Welt.
Ist ferner M eine (evtl. sogar unendliche) Formelmenge. So nennt man eine Belegung A, die alle Formeln F aus M wahr macht, ebenfalls ein Modell f¨ ur M und schreibt daf¨ ur bisweilen auch kurz A(M) = 1.
Enth¨alt eine Formel n verschiedene atomare Formeln / Aussagensymbole, so existieren 2n Zeilen in der Tafel. Eine Spalte wird als Wahrheitswerteverlauf (WWV) der zugeh¨origen Formel bezeichnet.
Frank Heitmann
[email protected]
Syntax Semantik
Definition ¨ Aquivalenzen
Zudem ist jede Belegung Modell der leeren Menge. Die leere Menge ist also erf¨ ullbar.
29/36
Frank Heitmann
[email protected]
Definition ¨ Aquivalenzen
Syntax Semantik
Kategorien
30/36
Definition ¨ Aquivalenzen
Kategorien - Notationen
Definition Besitzt F mindestens eine erf¨ ullende Belegung (ein Modell), so heißt F erf¨ ullbare Formel.
Notationen:
Besitzt F mindestens eine falsifizierende Belegung, so heißt F falsifizierbare Formel.
A ist Modell von F bzw. macht F wahr wird kurz geschrieben als A |= F .
Besitzt F mindestens eine erf¨ ullende und mindestens eine falsifizierende Belegung so heißt F kontingente Formel.
A falsifiziert F bzw. macht F falsch wird kurz geschrieben als A 6|= F .
Besitzt F kein Modell, so heißt F unerf¨ ullbare Formel oder Kontradiktion.
Ist F eine Tautologie, wird dies kurz notiert als |= F . Ist F eine Kontradiktion, wird dies kurz notiert als F |=.
Ist F unter jeder m¨ oglichen Belegung wahr“, so heißt F ” (allgemein-)g¨ ultig oder Tautologie.
Frank Heitmann
[email protected]
31/36
Frank Heitmann
[email protected]
32/36
Syntax Semantik
Definition ¨ Aquivalenzen
Syntax Semantik
Tautologie vs. Kontradiktion
Zusammenfassung 1
Satz F ist g¨ ultig genau dann, wenn ¬F unerf¨ ullbar ist.
Zusammenfassung Syntax: Motivation Definition der Syntax:
Beweis.
gdw . gdw . gdw . gdw . gdw .
Definition ¨ Aquivalenzen
F ist g¨ ultig jede Belegung ist ein Modell von F A(F ) = 1 f¨ ur jede Belegung A A(¬F ) = 0 f¨ ur jede Belegung A keine Belegung ist ein Modell von ¬F ¬F ist unerf¨ ullbar
Alphabet, Junktor Aussagesymbol, atomare Formel, komplexe Formel Hauptoperator, Teilformel Negation, Disjunktion, Konjunktion, Implikation, Biimplikation
(Def. der G¨ ultigkeit) (Def. eines Modells) (Eigenschaft von ¬) (Def. eines Modells) (Def. der Unerf¨ ullbarkeit)
Strukturb¨aume strukturelle Induktion strukturelle Rekursion Grad und Tiefe einer Formel
Frank Heitmann
[email protected]
Syntax Semantik
33/36
Frank Heitmann
[email protected]
Definition ¨ Aquivalenzen
Syntax Semantik
Zusammenfassung 2
34/36
Definition ¨ Aquivalenzen
Ausblick
Zusammenfassung Semantik: N¨achstes Mal besch¨aftigen wir uns mit
Belegung, Auswertung (einer Formel) Wahrheitstafeln, Wahrheitswerteverlauf erf¨ ullende Belegung, falsifizierende Belegung, Modell
¨aquivalenten Formeln, ¨ (Aquivalenz-)Umformungen und
kontingent, (allgemein-)g¨ ultig, unerf¨ ullbar
der Herstellung zweier Normalformen.
Tautologie, Kontradiktion A |= F , A 6|= F , |= F , F |=
Frank Heitmann
[email protected]
35/36
Frank Heitmann
[email protected]
36/36
