Mod-4.21 4.2 Prädikatenlogik Prädikatenlogik umfasst Aussagenlogik mit atomaren Aussagen, Variablen, Junktoren. Zusätzliche Konzepte: * A = (tau , Sigma ) ist die so genannte Termalgebra (mit Variablen, ohne Axiome) mit Signatur Sigma = ({T}, F), wobei T die Sorte "Term" ist und alle Operationen f element F von der Form f: Tn arrowright T sind. Terme sind die korrekten Terme bzgl. dieser Termalgebra. * n-stellige Prädikate sind Operationen P: Tn arrowright BOOL. In einer Konkretisierung entsprechen ihnen n-stellige Relationen, z. B. "x ist eine Katze" bzw. als Formel: istKatze(x) teilt(a,b), größterGemeinsamerTeiler(a, b, g) * Quantoren "für alle x gilt alpha " und "es gibt ein x, so dass alpha gilt" in Symbolen: für alle xalpha bzw. es gibt xalpha Beispiel: für alle x (esIstNacht logicaland istKatze(x) arrowright istGrau(x)); in Worten: "Nachts sind alle Katzen grau." Schon zur Modellierung einfacher Aufgaben braucht man Konzepte der Prädikatenlogik, z. B. größter gemeinsamer Teiler: gegeben: a element Iota N, b element Iota N; gesucht: größter gemeinsamer Teiler g von a und b, d. h. teilt(g, a) logicaland teilt(g, b) logicaland (für alle h (teilt(h, a) logicaland teilt(h, b) arrowright h lessequal g)) (c) 2007 bei Prof. Dr. Uwe Kastens überarbeitet 2004 Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 421 Ziele: Motivation der Prädikatenlogik in der Vorlesung: * Parametrisierung von Aussagen verdeutlichen * Prädikate und Relationen * Quantoren intuitiv * Einsatz in der Modellierung nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 Verständnisfragen: Warum kann man einfache Aufgaben für algorithmische Berechnungen nicht mit Aussagenlogik modellieren? -------------------------------------------------------------------------------- Mod-4.22 Vorschau auf Begriffe Ähnliche Folge von Begriffen wie in der Aussagenlogik: * prädikatenlogische Formeln als Sprache der Prädikatenlogik Syntax: Terme, Prädikate, logische Junktoren, Quantoren * gebundene und freie Variable * Individuenbereich: allgemeiner Wertebereich für Variable und Terme * Belegung von Variablen mit Werten aus dem Individuenbereich * Interpretation: Variablenbelegung und Definition der Funktionen und Prädikate * erfüllbar, allgemeingültig, widerspruchsvoll: wie in der Aussagenlogik definiert * logischer Schluss: wie in der Aussagenlogik definiert * Gesetze zum Umformen von Formeln mit Quantoren (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 422 Ziele: Übersicht in der Vorlesung: Vergleich mit Aussagenlogik -------------------------------------------------------------------------------- Mod-4.23 Prädikatenlogische Formeln Prädikatenlogische Formeln (PL-Formeln) werden induktiv wie folgt definiert: 1. Primformeln sind Anwendungen von Prädikaten in der Form P (t1, ..., tn) oder Gleichungen in der Form t1 = t2. Dabei ist P ein n-stelliges Prädikatsymbol und die ti sind Terme der Termalgebra. 0-stellige Prädikatsymbole entsprechen den atomaren Aussagen der Aussagenlogik. 2. logische Junktoren bilden prädikatenlogische Formeln: logicalnot alpha alpha logicaland beta alpha logicalor beta sowie alpha arrowright beta alpha arrowboth beta als Abkürzungen mit prädikatenlogischen Formeln alpha und beta 3. der Allquantor für alle und der Existenzquantor es gibt bilden prädikatenlogische Formeln: für alle x alpha und es gibt x alpha mit der prädikatenlogischen Formel alpha ; sie definieren die Variable x Nur nach (1. - 3.) gebildete Formeln sind syntaktisch korrekte prädikatenlogische Formeln. Quantoren haben die gleiche Präzedenz wie logicalnot , also höhere als logicaland . Beispiele: teilt(g, a) logicaland teilt(g, b) logicaland (für alle h (teilt(h, a) logicaland teilt(h, b) arrowright lessequal (h, g)) (siehe Folie 4.21) für alle x für alle y für alle z ((R(x, y) logicaland R(x,z)) arrowright y = z) "R ist eine Funktion" (c) 2011 bei Prof. Dr. Uwe Kastens überarbeitet 2006 Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 423 Ziele: Notation und Struktur in der Vorlesung: * Beispiele * Struktur an Bäumen erläutern * Signatur explizit machen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 Verständnisfragen: * Zeigen Sie, dass die Formeln auf Folie Mod-4.21 syntaktisch korrekt sind. * Zu welchen Signaturen gehören ihre Terme? -------------------------------------------------------------------------------- Mod-4.24 Anmerkungen zu prädikatenlogischen Formeln * Prädikatsymbole und Operationssymbole in Termen erhalten ihre Bedeutung erst durch die Interpretation der Formel (wie bei abstrakten Algebren), aber * Prädikate und Operationen werden häufig nicht explizit definiert, sondern mit üblicher Bedeutung der Symbole angenommen. * Signatur Sigma wird meist nicht explizit angegeben, sondern aus den Operationen angenommen, die in den Termen verwendet werden. * Hier: Prädikatenlogik erster Stufe: Variable sind nur als Operanden in Termen erlaubt, aber nicht für Funktionen oder für Prädikate. Nur solche Variablen dürfen quantifiziert werden. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 424 Ziele: PL Formeln in der Praxis in der Vorlesung: * Anmerkungen erläutern * PL erster Stufe abgrenzen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.25 Vorkommen von Variablen Wir sagen: (Eine Variable mit Namen) x kommt in einer PL-Formel alpha vor, wenn sie in einer Primformel und dort in einem Term vorkommt. Für eine PL-Formel der Form für alle x alpha oder es gibt x alpha ist alpha der Wirkungsbereich (für x) des Quantors. x ist der Name der Variablen des Quantors. Beispiel: für alle x (P(x) logicaland Q(x)) logicalor es gibt y (P(y) logicaland für alle z R(y, z)) Quantoren mit ihrenWirkungsbereichen Anmerkungen: * Eine Variable hat einen Namen; mehrere Variable können den gleichen Namen haben. * Ein Quantor definiert eine Variable, z. B. für alle x alpha definiert (eine Variable mit Namen) x. Ihr Name kann im Wirkungsbereich (auch mehrfach) vorkommen. * Wirkungsbereiche von Quantoren können geschachtelt sein, sogar mit (verschiedenen) Variablen, die dieselben Namen haben. (c) 2007 bei Prof. Dr. Uwe Kastens überarbeitet 2004 Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 425 Ziele: Bindung von Namen verstehen in der Vorlesung: * Wirkungsbereiche erläutern, und an Bäumen zeigen * Variablendefinition und ihre Anwendungen * Unterschied: Variable, ihr Name, dessen Vorkommen in einer Formel * Vergleich mit Variablendeklarationen in Programmen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.26 Freie und gebundene Variable (Ein Vorkommen von) x in einer Formel alpha heißt frei, wenn es nicht im Wirkungsbereich für x eines Quantors liegt. Ein Quantor für alle x alpha bzw. es gibt x alpha bindet alle (Vorkommen von) x, die frei sind in alpha . (Das Vorkommen von) x heißt dann gebunden. Beispiel: Formel alpha R(y) logicaland es gibt y (P(y, x) logicalor Q(y, z)) freie Vorkommen gebundene Vorkommen In alpha gibt es 3 freie Variable; sie haben die Namen y, x, z. 2 Variable haben den Namen y; eine kommt frei vor in R(y), die andere kommt 2 mal gebunden in alpha vor. (c) 2010 bei Prof. Dr. Uwe Kastens überarbeitet 2006 Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 426 Ziele: Freie Variable erkennen in der Vorlesung: * Variable sind frei in Bezug auf eine (Teil-)Formel, * weiter außen werden sie an eine Bedeutung gebunden. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.27 Umbenennung von Variablen In einer Formel können mehrere Vorkommen von Quantoren verschiedene Variable mit gleichem Namen einführen und in ihrem Wirkungsbereich binden: Beispiele: für alle y (es gibt x R(x, y) logicaland es gibt x Q(x, y)) für alle x für alle y (P(x, y) logicaland es gibt x R(x, y)) Umbenennung: In einer Formel kann man alle (gebundenen) Vorkommen des Namens x der Variablen eines Quantors in dessen Wirkungsbereich durch einen neuen Namen z ersetzen, der sonst nicht in der Formel vorkommt. Die Bedeutung der Formel, (genauer: semantische Aussagen über sie), ändert sich dadurch nicht. Beispiele von oben: für alle y (es gibt x R(x, y) logicaland es gibt z Q(z, y)) für alle x für alle y (P(x, y) logicaland es gibt z R(z, y)) Damit kann man erreichen, dass verschiedene Variable verschiedene Namen haben. Wir sagen dann: Die Variablen der Formel sind konsistent umbenannt. Formeln, in denen alle Variablen verschiedene Namen haben sind meist besser lesbar. Manche Definitionen sind einfacher für konsistent umbenannte Formeln. (c) 2011 bei Prof. Dr. Uwe Kastens überarbeitet 2006 Prof. Dr. Wilfried Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 427 Ziele: Konsistente Umbenennung verstehen in der Vorlesung: * Anwendungen ihren Definitionen zuordnen. * Wenn in geschachtelten Wirkungsbereichen die Variablen derQuantoren dieselben Namen haben, dann ist iminneren Wirkungsbereich die äußere Variable verdeckt. * Konsistente Umbenennung beachtet Bindungen, Substitution von Variablen aber nicht. * Vergleich mit Programmiersprachen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 Verständnisfragen: * Geben Sie ein Beispiel, wo eine unzulässige Umbenennung in einen schon verwendeten Variablennamen Bindungen verändert. -------------------------------------------------------------------------------- Mod-4.28 Interpretation zu prädikatenlogischer Formel Einer prädikatenlogischen Formel alpha wird durch eine Interpretation Ifraktur (alpha ) Bedeutung zugeordnet, sodass man ihren Wahrheitswert (w oder f) berechnen kann. Eine Interpretation Ifraktur wird bestimmt durch * einen Individuenbereich U, der nicht leer ist (auch Universum genannt). Aus U stammen die Werte der Variablen und Terme. * eine Abbildung der Funktions- und Prädikatsymbole auf dazu passende konkrete Funktionen und Relationen, notiert als z. B. Ifraktur (h), Ifraktur (P) * eine Belegung der freien Variablen mit Werten aus U, notiert z. B. Ifraktur (x). * die Interpretation der Junktoren und Quantoren (definiert auf Folie 4.31) Bemerkungen: * In der Prädikatenlogik enthält der Individuenbereich U alle Individuen - auch verschiedenartige - die für die Interpretation benötigt werden. Er ist nicht in Wertebereiche gleichartiger Individuen strukturiert (wie in Kapitel 2). * Der Sorte T wird deshalb der ganze Individuenbereich U zugeordnet. * Eine Interpretation wird immer passend zu einer Menge prädikatenlogischer Formeln definiert. Nur darin vorkommende Funktionen, Prädikate und Variable interessieren. (c) 2010 bei Prof. Dr. Uwe Kastens überarbeitet 2006 Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 428 Ziele: Interpretation als Zuordnung verstehen in der Vorlesung: * Beispiele für Individuenbereiche U * Vergleich mit Wertebereichen aus Abschnitt 2 * Beispiel von Mod-3.26 nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.29 Beispiel für eine passende Interpretation zu einer Formel Zur Formel alpha = (für alle x P(x, h(x))) logicaland Q(g(a, z)) ist folgendes Ifraktur eine passende Interpretation: U := Iota N Ifraktur (P) := { (m, n) | m, n element U und m < n } Ifraktur (Q) := { n | n element U und n ist Primzahl } Ifraktur (h) ist die Nachfolgerfunktion auf U, also Ifraktur (h)(n) = n + 1 Ifraktur (g) ist die Additionsfunktion auf U also Ifraktur (g)(m, n) = m + n Ifraktur (a) := 2 (a ist eine Konstante, d.h. eine 0-stellige Funktion, 2 element U) Ifraktur (z) := n (z ist eine freie Variable, n element U) Bemerkungen: * Häufig wird die Interpretation von Funktions- und Prädikatssymbolen nicht explizit angegeben, sondern die "übliche Bedeutung der Symbole" angenommen. * Die Anwendung von Ifraktur zeigt, wie die Variablen der Quantoren Werte erhalten (Folie 4.31). Das Beispiel stammt aus U. Schöning: Logik für Informatiker, Spektrum Akademischer Verlag, 4. Aufl., 1995, S. 55 (c) 2007 bei Prof. Dr. Uwe Kastens überarbeitet 2004 Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 429 Ziele: Konkretes Beispiel verstehen in der Vorlesung: * Beispiel erläutern * Andere Funktionen einsetzen Verständnisfragen: Variieren Sie das Beispiel mit anderen Funktionen und Prädikaten. -------------------------------------------------------------------------------- Mod-4.30 Wahrheitswerte prädikatenlogischer Formeln Sei alpha eine prädikatenlogische Formel und Ifraktur eine dazu passende Interpretation, dann berechnet man den Wahrheitswert Ifraktur (alpha ), indem man Ifraktur rekursiv anwendet auf die Teile von alpha : * die Prädikatsymbole und deren Terme, * die Funktionssymbole und deren Terme, * die freien und gebundenen Variablen, * die mit Junktoren verknüpften Teilformeln und * die Quantor-Formeln. (c) 2007 bei Prof. Dr. Uwe Kastens überarbeitet 2006 Prfo. Dr. Wilfried Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 430 Ziele: Interpretation auf Teile einer PL-Formel anwenden in der Vorlesung: * Übersicht geben -------------------------------------------------------------------------------- Mod-4.31 Interpretation von PL-Formeln (vollständige Definition) Die Interpretation der Symbole wird auf prädikatenlogische Formeln, deren Variablen konsistent umbenannt sind, erweitert: Für jeden Term h(t1, ..., tn) wird definiert: Ifraktur (h (t1, ..., tn)) = Ifraktur (h)(Ifraktur (t1), ..., Ifraktur (tn)). Für Formeln gilt (Definition durch Induktion über den Aufbau der prädikatenlogischen Formeln): 1. Ifraktur (P (t1, ..., tn)) = w genau dann, wenn (Ifraktur (t1), ..., Ifraktur (tn)) element Ifraktur (P) 2. Ifraktur (t1 = t2) = w genau dann, wenn Ifraktur (t1) = Ifraktur (t2) 3. Ifraktur (logicalnot alpha ) = w genau dann, wenn Ifraktur (alpha ) = f 4. Ifraktur (alpha logicaland beta ) = w genau dann, wenn Ifraktur (alpha ) = w und Ifraktur (beta ) = w 5. Ifraktur (alpha logicalor beta ) = w genau dann, wenn Ifraktur (alpha ) = w oder Ifraktur (beta ) = w 6. Ifraktur (für alle xalpha ) = w genau dann, wenn für jeden Wert d element U gilt Ifraktur [x/d] (alpha ) = w 7. Ifraktur (es gibt xalpha ) = w genau dann, wenn es einen Wert d element U gibt mit Ifraktur [x/d] (alpha ) = w Dabei ordnet Ifraktur [x/d] (alpha ) in alpha der Variablen x den Wert d zu und stimmt sonst mit der gerade angewandten Interpretation Ifraktur überein. (c) 2011 bei Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 431 Ziele: Exakte Definition der Interpretation verstehen in der Vorlesung: * rekursive Anwendung der Interpretation am Beispiel erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.32 Beispiel für Interpretation einer Formel Formel alpha : Interpretation Ifraktur : R logicaland für alle x für alle y P (x, y) U = { 1, 2, 3 } Ifraktur (P) = { (a, b) | a + b < 10 } Ifraktur (R) = w Interpretation Ifraktur rekursiv gemäß Mod-4.31 angewandt: Nr.: Ifraktur (R logicaland für alle x für alle y P (x, y)) 4 = Ifraktur (R) und Ifraktur (für alle x für alle y P (x, y)) Ifraktur ,6,6 = w und für jedes d, e element U gilt Ifraktur [x/d, y/e](P (x, y)) 1 = w und für jedes d, e element U gilt (Ifraktur [x/d, y/e](x), Ifraktur [x/d, y/e](y)) element Ifraktur [x/d, y/e](P) Ifraktur = w und für jedes d, e element { 1, 2, 3 } gilt (d, e) element { (a, b) | a + b < 10 } = w und w = w (c) 2010 bei Prof. Dr. Uwe Kastens überarbeitet 2004 Prof -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 432 Ziele: Beispiel zu Mod-3.27 in der Vorlesung: Erläuterungen dazu nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 2.5 -------------------------------------------------------------------------------- Mod-4.33 Elementare Interpretationen Wir betrachten für die Beispiele A bis G eine Interpretation Ifraktur mit Individuenbereich U = Iota N. a. freie Variable: Ifraktur (u) = 1 element U, Ifraktur (v) = 2 element U (bestimmte Elemente von U) b. 0-stellige Prädikate: Ifraktur (A) = w oder Ifraktur (A) = f (boolesche Variable) c. 1-stellige Prädikate: Ifraktur (P) = M := {1, 2, 3}reflexsubset U (Teilmenge von U) d. 2-stellige Prädikate: Ifraktur (Q) = R := {(1, 2), (2, 2)} reflexsubset U multiply U (Relation auf U) Alpha . Ifraktur (P(u)) = w gdw Ifraktur (u) element Ifraktur (P), d. h. 1 element M Beta . Ifraktur (Q(u, v)) = w gdw (Ifraktur (u), Ifraktur (v)) element Ifraktur (Q), d. h. (1, 2) element R C. Ifraktur (für alle x P(x)) = w gdw (Für alle d element U gilt: d element M) = f, d. h. M notequal U D. Ifraktur (es gibt x P(x)) = w gdw Es existiert d element U mit d element M, M notequal emptyset Epsilon . Ifraktur (für alle x Q(x, x)) = w gdw (Für alle d element U gilt: (d, d) element R) = f, d. h. R ist nicht reflexiv F. Ifraktur (es gibt x Q(x, x)) = w gdw Es gibt ein d element U mit (d, d) element R, d. h. R ist nicht irreflexiv G. Ifraktur (für alle x für alle y (Q(x,y) logicaland Q(y, x) arrowright x = y)) = w gdw Für alle d, e element U gilt: aus (d, e) element R und (e, d) element R folgt d = e, d. h. R ist antisymmetrisch (c) 2011 Prof. Dr. W. Hauenschild1 -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 433 Ziele: Beispiel zur Definition der Interpretation in der Vorlesung: * rekursive Anwendung der Interpretation am Beispiel erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.34 Beschränkung von Wertebereichen In der Prädikatenlogik kann die Interpretation von Variablen Werte aus dem gesamten Individuenbereich U annehmen (im Unterschied zu einem Wertebereich). Deshalb muss eine Einschränkung explizit als Relation formuliert werden. Beschränkung des Wertebereiches bei Allquantoren durch Implikation arrowright : "Für alle m element U gilt: aus m element M folgt Q(m, n)" oder abgekürzt "für alle m element M: Q(m, n)" als PL-Formel:für alle x (P(x) arrowright Q(x, y)) ausführliche Notation: abkürzende Notation: Beispiele: Für alle i element U gilt: aus i element {1, 2, 3, 4} folgt bi = a 2i für alle i element {1, 2, 3, 4}: bi = a 2i Für alle k element U gilt: aus kelement Iota N folgt a + k greaterequal a für alle k element Iota N: a + k greaterequal a Beschränkung des Wertebereiches bei Existenzquantoren durch Konjunktion logicaland : "Es gibt ein m element U, sodass m element M und Q(m, n) " oder abgekürzt "es gibt m element M: Q(m, n)" PL-Formel: es gibt x (P(x) logicaland Q(x, y)) Beispiele: Es gibt ein k element U, sodass k element Iota N und a * k = b es gibt k element Iota N: a * k = b Es gibt ein i element U, sodass i element {1, 2, 3, 4} und ai = x es gibt i element {1, 2, 3, 4}: ai = x (c) 2007 bei Prof. Dr. Uwe Kastens überarbeitet 2006 Prof.Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 434 Ziele: Prädikate präzisieren Wertebereiche in der Vorlesung: * Begründung der Implikation und der Konjunktion * Erläuterung der Beispiele nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.35 Beispiele für PL-Formeln und deren Interpretation (1) Die Variablen in Gleichungen konkreter Algebren sind durch Allquantoren gebunden: Axiom K3: pop (push (k, x)) minus >k (in der abstrakten Keller-Algebra) Gleichung: für alle a element Iota N * : für alle n element Iota N : remove (append (a, n)) = a (konkrete Algebra) PL-Formel: für alle k für alle x (P(k) logicaland S(x) arrowright h ( g (k, x)) = k) Interpretation: U = Iota N *union Iota N , Ifraktur (S) = Iota N , Ifraktur (P) = Iota N * Ifraktur (h) = remove: Iota N * arrowright Iota N *, Ifraktur (g) = append: Iota N * x Iota N arrowright Iota N * Es gilt: Ifraktur (für alle k für alle x (P(k) logicaland S(x) arrowright h( g (k, x)) = k))) = w gdw für alle a element Iota N *union Iota N : für alle n element Iota N *union Iota N : Ifraktur [k/a, x/n] (P(k) logicaland S(x) arrowright h ( g (k, x)) = k) = w gdw für alle a element Iota N *union Iota N : für alle n element Iota N *union Iota N : Aus a element Iota N * und n element Iota N folgt:remove (append(a,n)) = a gdw für alle a element Iota N *union Iota N : für alle n element Iota N : remove (append (a, n))= a (c) 2011 bei Prof. Dr. Wilfried Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 435 Ziele: Beispiel zur Definition der Interpretation in der Vorlesung: * rekursive Anwendung der Interpretation am Beispiel erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.36 Beispiele für PL-Formeln und deren Interpretation (2) Aus der Analysis: Eine Funktion a : Iota Narrowright Iota R , a(n) = an, heißt Nullfolge, wenn gilt für alle epsilon element Iota R+: es gibt n0 element Iota N: für alle n element Iota N mit n0 < n : | an | < epsilon Dreifache Schachtelung der Quantoren; Reihenfolge ist wichtig! PL-Formel alpha : für alle x(P1(x) arrowright es gibt y(P2(y) logicaland für alle z(P2(z) logicaland Q(y, z)) arrowright Q(h(z), x)))) Interpretation: U = Iota R, Ifraktur (P1) = Iota R+, Ifraktur (P2) = Iota N , Ifraktur (Q) = { (r, s) | (r, s) element Iota R+ xIota R+und r < s }, Ifraktur (h) : Iota N arrowright Iota R , Ifraktur (h) (i) = | ai | Es gilt: Ifraktur (alpha ) = w gdw an ist eine Nullfolge (c) 2007 bei Prof. Dr. Wilfried Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 436 Ziele: Beispiel zur Definition der Interpretation in der Vorlesung: * rekursive Anwendung der Interpretation am Beispiel erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.37 Beispiele für PL-Formeln und deren Interpretation (3) Aus der Informatik: Eine Folge a = (a1, ..., ak) element Iota Nk heißt monoton wachsend, wenn gilt für alle ielement {1, ..., k}: für alle j element {1, ..., k} mit i lessequal j gilt ai lessequal aj PL-Formel beta : für alle x(P(x) arrowright für alle y((P(y) logicaland Q(x, y)) arrowright Q(h(x), h(y)))) Interpretation: U = Iota N k union {1, ..., k}, Ifraktur (P) = {1, ..., k}, Ifraktur (Q) = { (m, n) element Iota N x Iota N | m lessequal n} Ifraktur (h) : {1, ..., k} arrowright Iota N , Ifraktur (h)(i) = ai Es gilt: Ifraktur (beta ) = w gdw an ist monoton wachsend Was bedeutet Ifraktur (P(x) logicaland für alle y(P(y) arrowright (Q(h(x), h(y)) logicaland (h(x) = h(y) arrowright Q(x, y))))) = w mit Ifraktur (x) = i, ielement {1, ..., k}, bei sonst unveränderter Interpretation? (c) 2007 bei Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 437 Ziele: Beispiel zur Definition der Interpretation in der Vorlesung: * rekursive Anwendung der Interpretation am Beispiel erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.38 Beispiel: Spezifikation des n-Damen-Problems gegeben: Kantenlänge n element Iota N eines n * n Schachbrettes 4 gesucht: Menge P zulässiger Platzierungen von jeweils n Damen 3 auf dem Schachbrett, so dass keine Dame eine andere nach Schachregeln schlägt: zi Sei Index := {1, ..., n} 2 P := { p | p = (z1, ..., zn) element Indexn logicaland zulässig (p) } 1 zi gibt die Zeilennummer der Dame in Spalte i an. j 1 2 3 4 Dabei bedeutet zulässig (p): für alle i element Index: für alle j element Index: i notequal j arrowright zi notequal zj logicaland | zi - zj | notequal | i - j | (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 438 Ziele: Spezifikation einer Aufgabe in der Vorlesung: Erläuterungen dazu -------------------------------------------------------------------------------- Mod-4.39 Erfüllbarkeit und logischer Schluss Die folgenden Begriffe sind in der Prädikatenlogik so definiert wie in der Aussagenlogik. Aber: Interpretationen der Prädikatenlogik sind komplexe Strukturen. Deshalb sind die Eigenschaften "erfüllbar" und "allgemeingültig" für prädikatenlogische Formeln nicht allgemein entscheidbar. * Wenn für eine Interpretation Ifraktur (alpha ) = w gilt, heißt Ifraktur auch ein Modell der Formel alpha . * Eine Formel alpha heißt erfüllbar, wenn es eine Interpretation Ifraktur gibt, so dass gilt Ifraktur (alpha ) = w, sonst ist sie widerspruchsvoll. * Eine Formel alpha heißt allgemeingültig oder Tautologie, wenn für alle Interpretationen von alpha gilt Ifraktur (alpha ) = w, sonst ist sie falsifizierbar. * Eine Formel alpha ist genau dann allgemeingültig, wenn logicalnot alpha widerspruchsvoll ist. * Zwei Formeln alpha und beta sind logisch äquivalent, in Zeichen: alpha equivalence beta , wenn sie für alle Interpretationen Ifraktur dasselbe Ergebnis haben: Ifraktur (alpha ) = Ifraktur (beta ) * Sei F eine Menge von Formeln und alpha eine Formel. Wenn für alle Interpretationen Ifraktur , die alle Formeln in F erfüllen, auch Ifraktur (alpha ) gilt, dann sagen wir"alpha folgt semantisch aus F" bzw. F |= alpha ; F |= alpha heißt auch logischer Schluss. (c) 2007 bei Prof. Dr. Uwe Kastens überarbeitet 2006 Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 439 Ziele: Analoge Begriffe wie in der Aussagenlogik in der Vorlesung: * gleiche Definition der Begriffe * Interpretation unterscheidet sich von der in der Aussagenlogik * Die Menge der Interpretationen kann i.a. nicht überprüft werden. nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.40 Äquivalente Umformung prädikatenlogischer Formeln Seien alpha und beta beliebige prädikatenlogische Formel. Dann gelten folgende Äquivalenzen: 1. Negation: logicalnot für alle x alpha equivalence es gibt x logicalnot alpha logicalnot es gibt x alpha equivalence für alle x logicalnot alpha 2. Wirkungsbereich der Quantoren verändern: Falls x in beta nicht frei vorkommt, gilt (für alle x alpha ) logicaland beta equivalence für alle x (alpha logicaland beta ) (für alle x alpha ) logicalor beta equivalence für alle x (alpha logicalor beta ) (es gibt x alpha ) logicaland beta equivalence es gibt x (alpha logicaland beta ) (es gibt x alpha ) logicalor beta equivalence es gibt x (alpha logicalor beta ) beta equivalence es gibt x beta beta equivalence für alle x beta 3. Quantoren zusammenfassen: (für alle x alpha logicaland für alle x beta ) equivalence für alle x (alpha logicaland beta ) (es gibt x alpha logicalor es gibt x beta ) equivalence es gibt x (alpha logicalor beta ) Folgende Formelpaare sind im allgemeinen nicht äquivalent: (für alle x alpha logicalor für alle x beta ) equivalence / für alle x (alpha logicalor beta ) (es gibt x alpha logicaland es gibt x beta ) equivalence / es gibt x (alpha logicaland beta ) 4. Quantoren vertauschen: für alle x für alle y alpha equivalence für alle y für alle x alpha es gibt x es gibt y alpha equivalence es gibt y es gibt x alpha (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 440 Ziele: Wichtige Äquivalenzen einprägen in der Vorlesung: * 1 - 4 begründen * Eine Äquivalenz beweisen * Beispiel für Umformungen nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.41 Beispiele für Äquivalenzen 1. Negation: formal Alle haben den Schuss gehört. für alle x gehört(x) negiert: Es gibt einen, der den Schuss nicht gehört hat. es gibt x logicalnot gehört(x) falsch negiert: Alle haben den Schuss nicht gehört. für alle x logicalnot gehört(x) logicalnot für alle i element Ind: ai < 10 (es gibt x P(x)) arrowright P(y) gdw logicalnot für alle i (i element Ind arrowright ai < 10) equivalence logicalnot (es gibt x P(x)) logicalor P(y) gdw es gibt i logicalnot (logicalnot i element Ind logicalor ai < 10) equivalence (für alle x logicalnot P(x)) logicalor P(y) gdw es gibt i ( i element Ind logicaland logicalnot ai < 10) equivalence für alle x (logicalnot P(x) logicalor P(y)) gdw es gibt i element Ind: ai greaterequal 10 equivalence für alle x (P(x) arrowright P(y)) 2. Zusammenfassung von Quantoren: Äquivalent: (für alle i element Ind: ai < 10) logicaland (für alle i element Ind: 0 < ai) gdw für alle i element Ind: (ai < 10 logicaland 0 < ai) Nicht äquivalent, vielmehr gilt nur: Aus (für alle i element Ind: ai < 10) logicalor (für alle i element Ind: 0 < ai) folgt für alle i element Ind: (ai < 10 logicalor 0 < ai) (c) 2010 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 441 Ziele: Beispiele für Mod-3.32 in der Vorlesung: * Schrittweise umformen * weitere Beispiele nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.42 Beispiel für Umformungen Die folgende prädikatenlogische Formel wird so umgeformt, dass alle Quantoren vorne (außen) stehen: logicalnot (es gibt x P(x, y) logicalor für alle z Q(z)) logicaland es gibt u f(a, u) = a DeMorgan equivalence (logicalnot es gibt x P(x, y) logicaland logicalnot für alle z Q(z)) logicaland es gibt u f(a, u) = a Negation von Quantorformeln (x, z) equivalence (für alle x logicalnot P(x, y) logicaland es gibt z logicalnot Q(z)) logicaland es gibt u f(a, u) = a Kommutativität equivalence es gibt u f(a, u) = a logicaland (für alle x logicalnot P(x, y) logicaland es gibt z logicalnot Q(z)) Wirkungsbereiche ausweiten (u, x) equivalence es gibt u (f(a, u) = a logicaland für alle x (logicalnot P(x, y) logicaland es gibt z logicalnot Q(z))) Kommutativität (2 mal) equivalence es gibt u (für alle x (es gibt z logicalnot Q(z) logicaland logicalnot P(x, y)) logicaland f(a, u) = a) Wirkungsbereich ausweiten (z) equivalence es gibt u (für alle x es gibt z (logicalnot Q(z) logicaland logicalnot P(x, y)) logicaland f(a, u) = a) Wirkungsbereiche ausweiten (x, z) equivalence es gibt u für alle x es gibt z (logicalnot Q(z) logicaland logicalnot P(x, y) logicaland f(a, u) = a) In diesem Beispiel hätten die Quantoren auch in anderer Reihenfolge enden können, wenn in anderer Reihenfolge umgeformt worden wäre. Das ist nicht allgemein so. (c) 2010 bei Prof. Dr. Uwe Kastens überarbeitet 2006 Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 442 Ziele: Äquivalenzen anwenden in der Vorlesung: Erläuterungen dazu * Anwendungsstellen zeigen, * jeder Schritt einzeln (PDF) -------------------------------------------------------------------------------- Mod-4.43 Normalformen *Definition: Eine PL-Formel alpha ist in Negationsnormalform (NNF) genau dann, wenn jedes Negationszeichen in alpha unmittelbar vor einer Primformel steht und alpha die Junktoren arrowright und arrowboth nicht enthält. *Definition: Eine PL-Formel alpha ist in pränexer Normalform (PNF) genau dann, wenn sie von der Form Q1x1 Q2x2 ... Qnxn beta ist, wobei Qi Quantoren sind und beta keine Quantoren enthält. *Satz: Zu jeder PL-Formel gibt es logisch äquivalente Formeln in Negationsnormalform bzw. in pränexer Normalform. (c) 2010 bei Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 443 Ziele: Normalformen kennen in der Vorlesung: Begriffe erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.44 Erzeugung der PNF Die Erzeugung der pränexen Normalform geschieht in zwei Schritten: 1. Konsistente Umbenennung der Variablen (siehe Folie 4.27) 2. Quantoren nach links mit Hilfe der folgenden Ersetzungsregeln (Äquivalenzen): a. Ersetze (für alle xalpha ) logicaland beta durch für alle x(alpha logicaland beta ) (wegen (1) kommt x nicht frei in beta vor) b. Ersetze (es gibt xalpha ) logicaland beta durch es gibt x(alpha logicaland beta ) c. Ersetze (für alle xalpha ) logicalor beta durch für alle x(alpha logicalor beta ) d. Ersetze (es gibt xalpha ) logicalor beta durch es gibt x(alpha logicalor beta ) e. Ersetze logicalnot für alle xalpha durch es gibt xlogicalnot alpha f. Ersetze logicalnot es gibt xalpha durch für alle xlogicalnot alpha (c) 2010 bei Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 444 Ziele: Regeln zur Erzeugung der PNF kennen in der Vorlesung: Am Beispiel erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.45 Komplexität der Prädikatenlogik erster Stufe * Es gibt für die Prädikatenlogik erster Stufe einen vollständigen, korrekten Kalkül zur Herleitung allgemeingültiger Formeln. * Die Prädikatenlogik ist unentscheidbar, d. h. es gibt kein Verfahren, das für eine beliebige PL-Formel feststellen kann, ob sie allgemeingültig ist. * Die Prädikatenlogik ist rekursiv aufzählbar, d. h. es gibt ein Verfahren, das für eine beliebige PL-Formel feststellen kann, ob sie allgemeingültig ist, das aber im negativen Fall nicht notwendig terminiert. * Die natürlichen Zahlen lassen sich in der Prädikatenlogik erster Stufe nicht modellieren. (c) 2007 bei Prof. Dr. W. Hauenschild -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 445 Ziele: Grundsätzliche Aussagen über PL kennen in der Vorlesung: Aussagen erläutern nachlesen: Kastens, Kleine Büning: Modellierung, Abschnitt 4.2 -------------------------------------------------------------------------------- Mod-4.46 Ausschnitt aus einer Spezifikation in Z Die Spezifikationssprache Z basiert auf typisierter Mengentheorie (Wertebereiche wie in Abschnitt 2) und verwendet Prädikatenlogik. Ausschnitt aus der Fallstudie "A Drinks Dispensing Machine" aus Deri Sheppard: An Introduction to Formal Specification with Z and VDM, McGraw-Hill, 1994, S. 271ff (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 446 Ziele: Ausschnitt aus einem größeren Beispiel in der Vorlesung: Erläuterungen zur * Sprache Z, * zur gestellten Aufgabe, * zum Ausschnit aus der Spezifikation --------------------------------------------------------------------------------