Was bisher geschah: klassische Aussagenlogik Syntax Symbole und Struktur Junktoren: t, f (nullstellig), ¬ (einstellig), ∨, ∧, →, ↔ (zweistellig) aussagenlogische Formeln AL(P) induktive Definition: IA Atome : Aussagenvariablen (p, q, r , . . .) IS zusammengesetzte Formeln (ϕ, ψ, η, . . .): Verknüpfung von Formeln durch Junktoren Prinzip der strukturellen Induktion über Baumstruktur von Formeln Semantik (Bedeutung der Syntaxelemente) eines Junktors: Wahrheitswertfunktion einer Aussagenvariablen: Wahrheitswert aller Aussagenvariablen einer Menge P: Belegung (Interpretation) W : P → {0, 1} einer Formel aus AL(P): Funktion W : AL(P) → {0, 1} Boolesche Funktion Erfüllbarkeit, Allgemeingültigkeit von Formeln Äquivalenz von Formeln, z.B. p → q ≡ ¬p ∨ q 43 Formelmengen Formelmenge Φ ⊆ AL(P) (Menge von Bedingungen) Beispiele: {p, p → q} ⊆ AL(P) {p, p → q, ¬q} ⊆ AL(P) {p → q} ⊆ AL(P) ∅ ⊆ AL(P) 44 Semantik von Formelmengen Eine Belegung W : P −→ {0, 1} erfüllt eine Menge Φ ⊆ AL(P) von Formeln genau dann, wenn W jede Formel ϕ ∈ Φ erfüllt. Bestimmung der erfüllenden Belegungen z.B. durch Wahrheitswerttabellen Beispiele: einzige erfüllende Belegung für {p, p → q}: [p → 1, q → 1], {p, p → q, ¬q} hat keine erfüllende Belegung. erfüllende Belegungen für {p → q}: [p → 0, q → 0], [p → 0, q → 1], [p → 1, q → 1] Jede Belegung ist ein Modell für die Formelmenge ∅. Fakt Eine Belegung W : P → {0, 1} erfüllt eine endliche Formelmenge Φ = {ϕ1 , . . . , ϕn } genau dann, wenn sie die Formel ϕ1 ∧ · · · ∧ ϕn erfüllt. 45 Modellierung durch aussagenlogische Formelmengen Aussagen: 1. Es wird nicht mehr viel Eis gekauft, wenn es kalt ist. 2. Der Eisverkäufer ist traurig, wenn nicht viel Eis gekauft wird. 3. Es ist kalt. Darstellung als Formelmenge Φ ⊆ AL({k , t, v }): Φ = {k → ¬v , ¬v → t, k } erfüllende Belegungen für Φ: [k → 1, t → 1, v → 0] neue zusätzliche Aussage: 4. Der Eisverkäufer ist nicht traurig. Erweiterung der Formelmenge Φ zu Φ = Φ ∩ {¬t} = {k → ¬v , ¬v → t, k , ¬t} erfüllende Belegungen für Φ : keine 46 Modellierungsbeispiel Zuordnungen In einem Eisenbahnabteil sitzen die Herren Lehmann und Müller. Einer ist Sachse und einer Thüringer. Jeder der beiden Personen kommt aus genau einem Land, also 1. Jede Person kommt aus wenigstens einem Land. LS ∨ LT , MS ∨ MT 2. Aus jedem Land kommt wenigstens eine Person. LS ∨ MS, LT ∨ MT 3. Jede Person kommt aus höchstens einem Land. LS → ¬LT , LT → ¬LS, MS → ¬MT , MT → ¬MS oder (äquivalent) ¬LS ∨ ¬LT , ¬MS ∨ ¬MT 4. Aus jedem Land kommt höchstens eine Person. (ÜA) Zuordnungen kommen (mit viel mehr beteiligten Individuen) in vielen praktischen Anwendungen vor, z.B. Ressourcen-Planung Stundenplan Aufgabenverteilung Job-Scheduling (Betriebssystem) 47 Beschränkte Ausdrucksstärke der Aussagenlogik Aussagen immer zweiwertig (nur wahr oder falsch, keine Zwischenwerte), z.B.: Die Rose ist rot. Das Bier ist kalt. Der Student ist fleißig. (Erweiterung zu mehrwertigen Logiken, fuzzy logic) Aussagen immer absolut (keine Abhängigkeit vom Kontext, z.B. Ort, Zeitpunkt), z.B.: Es regnet. x > 3 (Erweiterung zur Modal- und Temporallogiken) Aussagen über alle Elemente „großer“ Mengen aufwendig (Erstellung, Platzbedarf), z.B. Zuordnungen keine Aussagen über Elemente einer unendlichen Mengen oder Mengen unbestimmter Mächtigkeit möglich, z.B. Jede durch 4 teilbare Zahl ist gerade. In jedem zusammenhängenden Graphen mit ≥ 2 Knoten hat jeder Knoten einen Nachbarn. Es ist nicht alles Gold was glänzt. (Erweiterung zur Prädikatenlogik) 48 Modellierungsbeispiel 1. Max ist ein Fisch. 2. Alle Fische schwimmen. 3. Also schwimmt Max. Individuenbereich (Objekte): Lebewesen Individuen (Konstanten) Max Eigenschaften: istFisch, schwimmt prädikatenlogische Formeln: 1. istFisch(Max) 2. ∀x(istFisch(x) → schwimmt(x)) 3. schwimmt(Max) 49 Modellierung in Prädikatenlogik Grundannahme: Die zu modellierende Welt besteht aus Individuen, die Eigenschaften haben und zueinander in Beziehungen (Relationen, Funktionen) stehen. Aussagen beschreiben Eigenschaften von und und Beziehungen zwischen Individuen. Formalisierung solcher Aussagen durch prädikatenlogische Formeln. 50 Prädikatenlogische Aussagen – Beispiele Personen sind genau dann Geschwister, wenn sie dieselbe Mutter oder denselben Vater haben. A ist genau dann Nachfahre von B, wenn B A’s Vater oder A’s Mutter ist oder ein Elternteil von A Nachfahre von B ist. Nachfahren derselben Person sind verwandt. Individuenbereich: Menge von Personen Beziehungen: Nachfahre, verwandt, Geschwister Funktionen: Mutter, Vater Primzahlen sind genau diejenigen natürlichen Zahlen, die genau zwei verschiedene Teiler haben. Gerade Zahlen sind genau diejenigen natürlichen Zahlen, die durch 2 teilbar sind. Es existieren gerade Primzahlen. Nachfolger ungerader Primzahlen sind nicht prim. Das Quadrat jeder geraden Zahl ist gerade. Individuenbereich: Menge aller natürlichen Zahlen Eigenschaft: prim, gerade Beziehung: teilt Funktion: Nachfolger, Quadrat ◆ 51 Atome (elementare Aussagen) Aussagenlogik : Aussagenvariable, bekommt festen Wahrheitswert durch Belegung Prädikatenlogik : (parametrisierte) Aussage über Eigenschaften von oder Beziehungen zwischen Individuen Wahrheitswert abhängig von beteiligten Individuen z.B. nebeneinander(x, y ),gerade(n) , x < 3, x < y , geschwister(x, mutter(y )) 52 Prädikatenlogik (der ersten Stufe) – Syntax bekannt: aussagenlogische Junktoren t, f, ¬, ∨, ∧, →, ↔ neu: prädikatenlogische Atome, Quantoren ∀, ∃ Definition (induktiv) Die Menge aller Formeln der Prädikatenlogik ist definiert durch: IA: Alle Atome sind Formeln. IS: t und f sind Formeln. Ist ϕ eine Formel und x eine Individuenvariable, dann sind auch ¬ϕ, ∀xϕ, ∃xϕ Formeln. Sind ϕ und ψ Formeln, dann sind auch ϕ ∨ ψ, ϕ ∧ ψ, ϕ → ψ und ϕ ↔ ψ Formeln. Baumstruktur der Formeln 53 Modellierung in Prädikatenlogik – Beispiel Auf jeden Topf passt ein Deckel. Individuenbereich: Kochgeschirr Eigenschaften: ist-Topf T (_), ist-Deckel D(_) Beziehung: passt-auf P(_) Schrittweise Entwicklung einer Formel: 1. Atome: P(x, y ) (x passt auf y ), D(x) (x ist ein Deckel), T (y ) (y ist ein Topf) 2. Formel D(x) ∧ T (y ) ∧ P(x, y ) Der Deckel x passt auf den Topf y . 3. Formel ∃x (D(x) ∧ T (y ) ∧ P(x, y )) Es gibt einen Deckel, welcher auf den Topf y passt. 4. Formel ∀y ∃x (D(x) ∧ T (y ) ∧ P(x, y )) Zu jedem Topf gibt es einen Deckel, der auf diesen Topf passt. bedeutet dasselbe wie: Auf jeden Topf passt ein Deckel. 54 Modellierung in Prädikatenlogik – Beispiele Personen sind genau dann Geschwister, wenn sie dieselbe Mutter oder denselben Vater haben. Individuenbereich: Personen Beziehungen: sind-Geschwister G(_, _), ist-Mutter-von M(_, _) , ist-Vater-von V (_, _) Zwischenschritte: Atome: G(x, y ), M(z, x), M(z, y ), V (u, x), V (u, y ) M(z, x) ∧ M(z, y ) z ist Mutter von x und y . ∃z (M(z, x) ∧ M(z, y )) x und y haben dieselbe Mutter (z). ∃z (M(z, x) ∧ M(z, y )) ∨ ∃u (V (u, x) ∧ V (u, y )) x und y haben dieselbe Mutter (z) oder denselben Vater (u). G(x, y ) ↔ (∃z (M(z, x) ∧ M(z, y )) ∨ ∃u (V (u, x) ∧ V (u, y ))) x und y sind genau dann Geschwister, wenn Sie dieselbe Mutter oder denselben Vater haben. (Zwei beliebige) Personen sind genau dann Geschwister, wenn Sie dieselbe Mutter oder denselben Vater haben. ∀x∀y (G(x, y ) ↔ (∃z (M(z, x) ∧ M(z, y )) ∨ ∃u (V (u, x) ∧ V (u, y )))) 55