Formale Semantik PDF

Subsection 4 Formale Semantik  Semantik der Prädikatenlogik - Strukturen Idee: Die Semantik wird mit Hilfe sogenannter Strukturen definiert. Eine Struktur besteht aus eine Grundmenge von Objekten, konkrete Funktionen und Prädikate über diese Objekte eine Zuordnung zwischen di...

Subsection 4 Formale Semantik  Semantik der Prädikatenlogik - Strukturen Idee: Die Semantik wird mit Hilfe sogenannter Strukturen definiert. Eine Struktur besteht aus eine Grundmenge von Objekten, konkrete Funktionen und Prädikate über diese Objekte eine Zuordnung zwischen diesen Funktionen/Prädikaten und den Funktionssymbolen/Prädikatensymbolen in der Formel Eine Funktion die jeder (freien) Variablen ein Objekt zuweist Atomare Formeln können in einer Struktur durch Einsetzen überprüft werden. Zusammengesetzte Formeln werden mit einem rekursiven Schema ausgewertet (ähnlich wie in der Aussagenlogik). Die Semantik einer Formel ergibt sich durch die Strukturen die Modell der Formel sind.  Semantik der Prädikatenlogik - Strukturen Zuerst müssen wir Strukturen definieren: Definition Eine zu einer Formel F passende Struktur ist ein Tupel ↵ = (U, ', , ⇠) U ist eine nicht leere Menge, das Universum oder die Grundmenge. ' eine Abbildung die jedem k-stelligen Funktionssymbol f in F eine Funktion f ' : U k ! U zuordnet. eine Abbildung die jedem k-stelligen Prädikatensymbol P in F ein Prädikat P ✓ U k zuordnet. ⇠ eine Abbildung die jeder Variablen x ein Element x ⇠ 2 U zuordnet. ⇠ gibt freien Variablen eine Bedeutung und hat keinen Einfluss auf die Semantik von geschlossenen Formeln.  Semantik der Prädikatenlogik - Strukturen Beispiel Betrachten wir die Formel: 9x Liebt(mutter (x), musik) Eine passende Struktur wäre: U = {JoAnn, Mum, STS} musik ' = STS mutter ' : mutter ' (JoAnn) = Mum, mutter ' (Mum) = JoAnn, mutter ' (STS) = STS Liebt = {(Mum, STS), (JoAnn, Mum)} x ⇠ = Mum  Semantik der Prädikatenlogik - Terme Wir definieren zunächst den Wert eines Terms in einer Struktur ↵ Definition Der Wert ↵(t) eines Terms t in der Struktur ↵ ist wie folgt gegeben: Ist t eine Variable dann ↵(t) = t ⇠ Ist t von der Form f (t1 ,... , tk ) dann ↵(t) = f ' (↵(t1 ),... , ↵(tk )) Beispiel Gegeben ↵ mit joAnn' = Susi, mutter ' (Susi) = Mum ↵(joAnn) =joAnn' = Susi ↵(mutter (joAnn)) =mutter ' (↵(joAnn)) = mutter ' (Susi) = Mum Beispiel Gegeben ↵ mit mutter ' (Mum) = JoAnn, x ⇠ = Mum ↵(x) = x ⇠ = Mum ↵(mutter (x)) = mutter ' (↵(x)) = mutter ' (Mum) = JoAnn  Semantik der Prädikatenlogik - Atome Definition Der Wahrheitswert ↵(F ) einer atomaren Formel F = P(t1 ,... , tk ) in einer Struktur ↵ ist gegeben durch ( 1 falls (↵(t1 ),... , ↵(tk )) 2 P ↵(F ) = 0 sonst Beispiel Gegeben Struktur ↵ mit ↵(joAnn) = joAnn' = Susi, ↵(musik) = musik ' = STS mutter ' (Susi) = Mum, mutter ' (Mum) = Susi, mutter ' (STS) = STS Liebt = {(Mum, STS), (Susi, Mum)} x ⇠ = Mum dann gilt 1 ↵(Liebt(mutter (joAnn), musik)) = Liebt (Mum, STS) = 1 2 ↵(Liebt(mutter (x), musik)) = Liebt (Susi, STS) = 0  Semantik der Prädikatenlogik Konstanten, 0-stellige Prädikate Zwei Spezialfälle: Konstanten, als 0-stelligen Funktionen, wird von ↵ immer ein Objekt u 2 U zugewiesen. 0-stelligen Prädikatensymbolen wird von ↵ ein Wahrheitswert zugewiesen.  Semantik der Prädikatenlogik – Boolesche Operatoren Die Semantik der Operatoren ¬, ^, und _ ist analog zur Aussagenlogik: ( 1 Wenn ↵(F ) = 1 und ↵(G ) = 1 ↵(F ^ G ) = 0 sonst ( 1 Wenn ↵(F ) = 1 oder ↵(G ) = 1 ↵(F _ G ) = 0 sonst ( 1 Wenn ↵(F ) = 0 ↵(¬F ) = 0 sonst ↵(F ! G ) = ↵(¬F _ G )  Semantik der Prädikatenlogik – Boolesche Operatoren Beispiel Gegeben Struktur ↵ mit ↵(joAnn) = Susi, ↵(musik) = STS ↵(mutter (Susi)) = Mum, ↵(mutter (Mum)) = Susi, ↵(mutter (STS)) = STS Liebt = {(Mum, STS), (Susi, Mum)} x ⇠ = Mum wir wissen schon 1 ↵(Liebt(mutter (joAnn), musik)) = Liebt (Mum, STS) = 1 2 ↵(Liebt(mutter (x), musik)) = Liebt (Susi, STS) = 0 Wir betrachten nun ↵ (Liebt(mutter (joAnn), musik) ^ Liebt(mutter (x), musik)) = ↵ (Liebt(mutter (joAnn), musik)) ^ ↵ (Liebt(mutter (x), musik)) = 1^0=0  Semantik der Prädikatenlogik – Quantoren Für die Semantik der Quantoren 8,9 benötigen wir zusätzliche Notation. Definition Für gegebene Struktur ↵ = (U, ', , ⇠), Variable x und u 2 U definieren ˜ sodass x ⇠˜ = u und y ⇠˜ = y ⇠ für alle ˜ xu = (U, ', , ⇠), wir die Struktur ↵ anderen Variablen y. ˜ xu setzt also ↵ ↵ ˜ xu (x) = u und lässt ↵ sonst unverändert. Beispiel Gegeben: ↵ = ({a, b, c}, ', , ⇠) mit x ⇠ = a, y ⇠ = b ↵(x) = a, ↵(y ) = b ↵ ˜ xc (x) = c, ↵ ˜ xc (y ) = b ↵ ˜ yc (x) = a, ↵ ˜ yc (y ) = c ↵ c,a ˜ x,y (x) = c, ↵ c,a ˜ x,y (y ) = a  Semantik der Prädikatenlogik – Quantoren Definition Die Wahrheitswerte ↵(8x F ), ↵(9x F ) sind wie folgt definiert: ( 1 ˜ xu (F ) = 1 falls für alle u 2 U gilt ↵ ↵ (8x F ) = 0 sonst ( 1 ˜ xu (F ) = 1 falls es ein u 2 U gibt sodass ↵ ↵ (9x F ) = 0 sonst  Semantik der Prädikatenlogik – Quantoren Beispiel Betrachte wieder die Struktur ↵ = (U, ', , ⇠): U = {JoAnn, Mum, STS} musik ' = STS mutter ' : mutter ' (JoAnn) = Mum, mutter ' (Mum) = JoAnn, mutter ' (STS) = STS Liebt = {(Mum, STS), (JoAnn, Mum)} x ⇠ = Mum Uns interessiert: ↵ (9x Liebt(mutter (x), musik)) und ↵ (8x Liebt(mutter (x), musik))  Semantik der Prädikatenlogik – Quantoren Beispiel (cont.) In beiden Fällen betrachte: ↵ ˜ xJoAnn (Liebt(mutter (x), musik))= Liebt (˜↵xJoAnn (mutter (x)), ↵ ˜ xJoAnn (musik))= Liebt (mutter ' (˜↵xJoAnn (x)), musik ' )= Liebt (mutter ' (JoAnn), STS)=Liebt (Mum, STS) = 1 ↵ ˜x Mum (Liebt(mutter (x), musik))=... = Liebt (mutter ' (Mum), STS)=Liebt (JoAnn, STS) = 0 ↵ ˜ xSTS (Liebt(mutter (x), musik))=... = Liebt (mutter ' (STS), STS)=Liebt (STS, STS) = 0 Wir erhalten ↵ (9x Liebt(mutter (x), musik)) = 1 ↵ (8x Liebt(mutter (x), musik)) = 0  Subsection 5 Fundamentale Begri↵e & Sätze  Prädikatenlogik – Begri↵e Elementare Begri↵e: Eine Struktur ↵ heißt Modell für F , wenn ↵(F ) = 1. Wir schreiben ↵ |= F. Eine Formel F heißt allgemein gültig oder Tautologie wenn alle zu F passenden Strukturen ↵ auch Modelle von F sind. Eine Formel F heißt erfüllbar wenn es ein Modell für F gibt, anderenfalls unerfüllbar. Anmerkungen F ist unerfüllbar genau dann wenn ¬F eine Tautologie ist. Die Aussagenlogik ist ein Spezialfall der Prädikatenlogik: Aussagenlogik entspricht der Prädikatenlogik mit ausschließlich 0-stelligen Prädikaten und ohne Quantoren.  Prädikatenlogik – Begri↵e Eine Struktur ↵ heißt Modell für eine Menge von Formeln F , wenn ↵ eine Modell jeder Formel G 2 F ist. Wir schreiben ↵ |= F. Zwei (Mengen von) Formeln F , G sind semantisch äquivalent wenn Sie die gleichen Modelle haben. Wir schreiben F ⌘ G. Eine Formel G folgt aus einer Formel / einer Menge von Formeln F /F wenn jedes Modell von F /F auch Modell von G ist. Wir schreiben F |= G /F |= G. Satz Zwei Formeln F ,G sind semantisch äquivalent (F ⌘ G ) genau dann wenn F |= G und G |= F. Satz (Ersetzungssatz) Seien F1 und F2 zwei semantisch äquivalente Formeln und sei G eine Formel die F1 als Teilformel enthält. Dann gilt G ⌘ G [F1 /F2 ]. Erinnerung: G [F1 /F2 ] erhält man aus G indem man F1 durch F2 ersetzt.  Prädikatenlogik – Fundamentale Äquivalenzen Es gelten die semantischen Äquivalenzen aus der Aussagenlogik und weiters gelten folgende Äquivalenzen für Quantoren: Vertauschen von Negation und Quantoren ¬8x F ⌘ 9x ¬F ¬9x F ⌘ 8x ¬F Reihenfolge von Quantoren 8x 8y F ⌘ 8y 8x F 9x 9y F ⌘ 9y 9x F Vorsicht: 8x 9y F 6⌘ 9y 8x F “Zu jedem Schloss gibt es einen passenden Schlüssel.” vs. “Es gibt einen Schlüssel der zu jedem Schloss passt.”  Prädikatenlogik – Fundamentale Äquivalenzen Quantoren und ^, _ 8x F ^ 8x G ⌘ 8x (F ^ G ) 9x F _ 9x G ⌘ 9x (F _ G ) Vorsicht: 8x F _ 8x G 6⌘ 8x (F _ G ): “Alle Hörer sind Frauen oder Alle Hörer sind Männer” vs. “Alle Hörer sind Frauen oder Männer” 9x F ^ 9x G 6⌘ 9x (F ^ G ) “Es gibt ein Auto mit Diesel-Motor und es gibt ein Auto mit Elektro-Motor” vs. “Es gibt ein Auto mit Diesel-Motor und Elektro-Motor”  Prädikatenlogik – Fundamentale Äquivalenzen Quantoren und ^, _ Wenn die Formel G die Variable x nicht enthält gilt auch: 8x F ^ G ⌘ 8x (F ^ G) 8x F _ G ⌘ 8x (F _ G) 9x F ^ G ⌘ 9x (F ^ G) 9x F _ G ⌘ 9x (F _ G)  Prädikatenlogik – Beispiel Gegeben: Formel: F = 8x9y Invers(x, y ) Struktur: ↵ = ({2, 3}, ', , ⇠) mit Invers (x, y ) = {(2, 2), (3, 3)}. Frage: Ist ↵ Modell von F ? Um ↵(8x9y Invers(x, y )) zu berechnen betrachte: ↵x2 (9y Invers(x, y )): ↵x,y 2,2 (Invers(x, y ))=Invers (2, 2) = 1 ↵x,y 2,3 (Invers(x, y ))=Invers (2, 3) = 0 ↵x2 (9y Invers(x, y )) = 1 ↵x3 (9y Invers(x, y )): ↵x,y 3,2 (Invers(x, y ))=Invers (3, 2) = 0 ↵x,y 3,3 (Invers(x, y ))=Invers (3, 3) = 1 ↵x3 (9y Invers(x, y )) = 1 ↵(8x9y Invers(x, y )) = 1 ) ↵ ist Modell von F.  Prädikatenlogik – Beispiel (zum Selbststudium) Gegeben: Formel F = 8x8y Gleich(plus(x, y ), plus(y , x)) Struktur ↵ = ({0, 1}, ', , ⇠) mit Gleich (x, y ) = {(0, 0), (1, 1)} und plus ' wie in der folgenden Tabelle gegeben x y plus ' (x, y ) 0 0 0 0 1 0 1 0 1 1 1 0 Frage: Ist ↵ Modell von F ?  Prädikatenlogik – Beispiel (zum Selbststudium) Um ↵(8x8y Gleich(plus(x, y ), plus(y , x))) zu berechnen betrachte: ↵x0 (8y Gleich(plus(x, y ), plus(y , x))): ↵x,y 0,0 (Gleich(plus(x, y ), plus(y , x))) = Gleich (plus ' (0, 0), plus ' (0, 0)) = Gleich (0, 0) = 1 ↵x,y 0,1 (Gleich(plus(x, y ), plus(y , x))) = Gleich (plus ' (0, 1), plus ' (1, 0)) = Gleich (0, 1) = 0 ↵x0 (8y Gleich(plus(x, y ), plus(y , x))) = 0 1 ↵x1 (8y Gleich(plus(x, y ), plus(y , x))): ↵x,y 1,0 (Gleich(plus(x, y ), plus(y , x)))=Gleich (1, 0) = 0 ↵x,y 1,1 (Gleich(plus(x, y ), plus(y , x)))=Gleich (0, 0) = 1 ↵x0 (8y Gleich(plus(x, y ), plus(y , x))) = 0 ↵(8x8y Gleich(plus(x, y ), plus(y , x))) = 0 ) ↵ ist kein Modell von F. 1 Wir könnten schon hier auf ↵(8x8y Gleich(plus(x, y ), plus(y , x))) = 0 schließen. Der Vollständigkeit halber betrachten wir aber auch die zweite Substitution.  Subsection 6 Formalisieren in Prädikatenlogik  Formalisieren in Prädikatenlogik - Faustregeln Zeitwörter bzw. Eigenschaften werden Prädikatensymbole Hauptwörter zu ihren Argumenten Konkrete Personen, Objekte werden Konstanten Beispiel Sokrates ist sterblich Sterblich(sokrates) Thomas läuft Laeuft(thomas) Alice spielt Ball SpieltBall(alice) Spielt(alice, ball) Alice spielt Schach Spielt(alice, schach) Thomas Mutter spielt Schach Spielt(mutter (thomas), schach)  Formalisieren in Prädikatenlogik - Faustregeln Regeln: Für alle Objekte mit einer Eigenschaft P gilt, dass... 8x(P(x) !... ) Stichworte: Alle, Jede,... manchmal aber auch nur wenn... dann“’ ” Existenzaussagen: Es gibt ein Objekt mit der Eigenschaft P, dass... 9x(P(x) ^... ) Stichworte: existiert, es gibt, (mindestens/hat/... ) einen,... Beispiel Aussage: Jeder Tennisspieler besitzt einen Tennisschläger. 8x TSpieler (x) ! (9y (Schlaeger (y ) ^ Besitzt(x, y ))) oder auch 8x 9y TSpieler (x) ! (Schlaeger (y ) ^ Besitzt(x, y )).  Prädikatenlogik – Beispiel 1 Aussage: Wenn zwei Zahlen negativ sind dann ist ihr Produkt positiv“ ” 8x8y (Negativ (x) ^ Negativ (y )) ! Positiv (produkt(x, y )) Ein Modell: U = { 1, 1} produkt ' : produkt ' (1, 1) = produkt ' ( 1, 1) = 1, produkt ' ( 1, 1) = produkt ' (1, 1) = 1 Negativ = { 1}, Positiv = {1} x ⇠ = 1, y ⇠ = 1 Ein anderes Modell wären die ganzen Zahlen Z, wobei produkt ' (.,.) die übliche Multiplikation ist und Negativ = Z , Positiv = Z+.  Prädikatenlogik – Beispiel 2 Aussage: Wenn es einen Weg von A nach B gibt und einen Weg von B ” nach C gibt dann gibt es auch einen Weg von A nach C.“ 8x8y 8z (Weg (x, y ) ^ Weg (y , z)) ! Weg (x, z) oder semantisch äquivalent 8x8y 8z ¬Weg (x, y ) _ ¬Weg (y , z) _ Weg (x, z) Ein Modell: U = {Wien, Berlin, Dresden, Eisenstadt} keine Funktionen/Konstanten Weg = {(Wien, Eisenstadt)}, x ⇠ = Wien, y ⇠ = Berlin, z ⇠ = Dresden  Beispiel 3 Wir wollen mehrere Aussagen in Prädikatenlogik formalisieren: 1 Nicht alle Musiker sind berühmt. 2 Es gibt berühmte Personen die keine Musiker sind. 3 Ein Musiker ist genau dann berühmt wenn er gut ist. 4 Es existieren sowohl schlechte als auch gute Musiker. Die Objekte“ sind in diesem Fall Personen. ” Wir erkennen mehrere Eigenschaften: ist Musiker, ist berühmt, ist gut, ist schlecht. ,! wir nutzen die folgenden Prädikate: Musiker (x)... x ist Musiker Beruehmt(x)... x ist berühmt Gut(x)... x ist gut Schlecht(x)... x ist schlecht  Beispiel 3 Wir wollen mehrere Aussagen in Prädikatenlogik formalisieren: 1 Nicht alle Musiker sind berühmt. 2 Es gibt berühmte Personen die keine Musiker sind. 3 Ein Musiker ist genau dann berühmt wenn er gut ist. 4 Es existieren sowohl schlechte als auch gute Musiker. 1 ¬8x(Musiker (x) ! Beruehmt(x)) oder 9x(Musiker (x) ^ ¬Beruehmt(x)) 2 9x(Beruehmt(x) ^ ¬Musiker (x)) 3 8x(Musiker (x) ! (Beruehmt(x) $ Gut(x))) 4 9x(Musiker (x) ^ Gut(x)) ^ 9y (Musiker (y ) ^ Schlecht(y ))  Beispiel 3 Wir wollen zeigen dass die Aussagen miteinander konsistent sind. 1 F1 = ¬8x(Musiker (x) ! Beruehmt(x)) 2 F2 = 9x(¬Musiker (x) ^ Beruehmt(x)) 3 F3 = 8x(Musiker (x) ! (Beruehmt(x) $ Gut(x))) 4 F4 = 9x(Musiker (x) ^ Gut(x)) ^ 9y (Musiker (y ) ^ Schlecht(y )) Um zu zeigen, dass F1 ^ F2 ^ F3 ^ F4 erfüllbar ist geben wir ein Modell an. Ein Modell: Ein anderes Modell: ↵ = ({Uli, Tom, Bob}, ', , ⇠) ↵0 = ({0, 1, 2}, ', , ⇠) Musiker (x) = {Uli, Tom} Musiker (x) = {0, 1} Beruehmt (x) = {Uli, Bob} Beruehmt (x) = {0, 2} Gut (x) = {Uli} Gut (x) = {0} Schlecht (x) = {Tom} Schlecht (x) = {1} x ⇠ = Tom, y ⇠ = Tom x ⇠ = 0, y ⇠ = 0