Mod-2.1 2 Modellierung mit Wertebereichen In der Modellierung von Systemen, Aufgaben, Lösungen kommen Objekte unterschiedlicher Art und Zusammensetzung vor. Für Teile des Modells wird angegeben, aus welchem Wertebereich sie stammen, aber noch offen gelassen, welchen Wert sie haben. Beispiel: Gegeben 3 Karten aus einem Kartenspiel; welche ist die höchste? Die Beschreibung des Modells wird präzisiert durch Angabe der Wertebereiche, aus denen die Objekte, Konstanten, Werte von Variablen, Eingaben, Ausgaben, Lösungen, usw. stammen. Wertebereich: eine Menge gleichartiger Werte Wertebereiche werden aus Mengen und Strukturen darüber gebildet. Beispiel: Modellierung von Kartenspielen Wertebereich einige Elemente daraus KartenSymbole := {7, 8, 9, 10, Bube, Dame, König, Ass} 8 Dame KartenArten := {Kreuz, Pik, Herz, Karo} Pik Karten := KartenArten multiply KartenSymbole (Kreuz, 8) (Herz, Dame) Menge aller Paare aus KartenArten und KartenSymbole (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 201 Ziele: Beschreibung von Wertebereichen motivieren in der Vorlesung: Erläuterungen dazu * präzise Angabe von Wertebereichen, * Informationsgehalt untersuchen Verständnisfragen: Karten eines Kartenspieles werden auf 2 Spieler verteilt. Beschreiben Sie den Wertebereich einer solchen Verteilung in Worten. -------------------------------------------------------------------------------- Mod - 2.2 Übersicht über Begriffe Wertebereich: eine Menge gleichartiger Werte Grundlegender Kalkül: Mengenlehre (halbformal); Mengen und Mengenoperationen Strukturen über Mengen zur Bildung zusammengesetzter Wertebereiche *Potenzmengen *kartesische Produkte, Tupel *Folgen *Relationen *Funktionen *disjunkte Vereinigungen Verwendung des Kalküls: Modellierung von Strukturen und Zusammenhängen Grundlage für alle anderen formalen Kalküle abstrakte Grundlage für Typen in Programmiersprachen (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 202 Ziele: Übersicht zu diesem Abschnitt in der Vorlesung: Rolle der Mengen und Strukturen darüber; Hinweise auf Bezüge zu * anderen Kalkülen, * Datentypen in Programmiersprachen -------------------------------------------------------------------------------- Mod - 2.3 Einführendes Beispiel Internationale Arbeitsgruppen Bei der UNO sollen Arbeitsgruppen aus Delegierten der drei Nationen A, B und C gebildet werden. Jede Nation hat vier Delegierte. Jede Gruppe besteht aus drei Personen, eine aus jeder Nation. Die Sprachen der drei Nationen sind verschieden; wir nennen sie auch A, B, C. Die Mitglieder jeder Arbeitsgruppe sollen eine gemeinsame Sprache sprechen. aus [T. Scheurer S. 155] Internationale Arbeitsgruppen Bei der UNO sollen Arbeitsgruppen aus Delegierten der drei Nationen A, B und C gebildet werden. Jede Nation hat vier Delegierte. Jede Gruppe besteht aus drei Personen, eine aus jeder Nation. Die Sprachen der drei Nationen sind verschieden; wir nennen sie auch A, B, C. Die Mitglieder jeder Arbeitsgruppe sollen eine gemeinsame Sprache sprechen. aus [T. Scheurer S. 155] (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 203 Ziele: Definition von Wertebereichen motivieren in der Vorlesung: * Erläuterung der Aufgabe * Präzise Modellierung interessiert hier - nicht Verfahren, um Lösungen zu finden. * Modellierung auf der nächsten Folie -------------------------------------------------------------------------------- Mod - 2.4 Wertebereiche für das Beispiel Beschreibung formale Angaben Menge der Nationen Nationen := {A, B, C} Indexmenge zur Unterscheidung der Delegierten Ind := {1, 2, 3, 4} ein Delegierter modelliert durch ein Paar (a, i) mit a element Nationen, i element Ind Wertebereich der Delegierten Delegierte := Nationen multiply Ind Wertebereich der Arbeitsgruppen 3-Tupel, kartesischesProdukt AGn := {(A, i)arrowvertex i element Ind} multiply {(B, j)arrowvertex j element Ind} multiply {(C, k)arrowvertex k element Ind} Wertebereich für Teilmengen von Sprachen SprachMengen := Pow (Nationen) Pow (M) ist die Potenzmenge von M Eine Funktion Sp gibt an, welche Sprachen ein Delegierter spricht: Sp element DSpricht Wertebereich solcher Funktionen DSpricht := Delegierte -> SprachMengen Wertebereich der gemeinsamen Sprachen einer AG Wertebereich AGSpricht := AGn -> SprachMengen GemSp ist eine Funktion daraus GemSp element AGSpricht N := M bedeutet "Der Name N ist definiert als M". (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 204 Ziele: Beispiele im Zusammenhang sehen in der Vorlesung: * Vorschau auf Anwendung des Kalküls, * informelle Erläuterungen, * Werte aus den Wertebereichen angeben Verständnisfragen: * Geben Sie zu jedem der Wertebereiche einen konkreten Wert als Beispiel an. -------------------------------------------------------------------------------- Mod - 2.5 2.1 Mengen Menge: Zusammenfassung von verschiedenen Objekten, den Elementen der Menge M. a ist Element aus M wird notiert a element M. Definition von Mengen durch * Aufzählen der Elemente (extensional): M := {1, 4, 9, 16, 25} * Angabe einer Bedingung (intensional): M := { a arrowvertex a element Iota N, a ist Quadratzahl und a lessequal 30} allgemein: M := { a | P (a) } wobei P (a) eine Aussage über a ist, die wahr oder falsch sein kann. Mengen können endlich (z. B. {1, 4, 9, 16, 25}) oder nicht-endlich sein (z. B. { a arrowvertex a element Iota N, a ist Quadratzahl }) Die leere Menge wird { } oder emptyset geschrieben. Die Anzahl der Elemente einer Menge M heißt die Kardinalität von M, geschriebenarrowvertex M arrowvertex oder Card(M) (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 205 Ziele: Definition von Mengen verstehen in der Vorlesung: * Beispiele zu den Eigenschaften. * Hier informelle Definition des Mengenbegriffs; axiomatische Mengenlehre definiert ihn strenger. Verständnisfragen: * Geben Sie Beispiele jeweils für unterschiedliche intensionale und für unterschiedliche extensionale Definitionen derselben Menge. * Vergleichen Sie den Mengenbegriff mit dem aus Mathe I. * Geben Sie Mengen an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod - 2.5a Eigenschaften von Mengen Wichtige grundsätzliche Eigenschaften von Mengen: * Alle Elemente einer Menge sind verschieden. * Die Elemente einer Menge sind nicht geordnet. * Dieselbe Menge kann auf verschiedene Weisen notiert werden: { 1, 2, 3, 4 } { i | ielement Iota N, 0 < i < 5 } { 1, 1, 2, 2, 3, 4 } { 2, 4, 1, 3 } Mengen können aus atomaren oder zusammengesetzten Elementen gebildet werden, z. B. nur atomare Elemente: { 1, 2, 3, 4 } { rot, gelb, blau } { Kreuz, Pik, Herz, Karo } { 1 } Menge von Paaren: { (Pik, 10), (Herz, Dame) } Menge von Mengen: { {rot, blau}, {blau}, emptyset } { emptyset } Die Existenz von atomaren Objekten des jeweiligen Modellierungsbereiches wird vorausgesetzt, z. B. die natürlichen Zahlen, Arten und Werte von Spielkarten. Eine Menge kann auch verschiedenartige Elemente enthalten, z. B. {1, (Pik, 10), rot, 9} aber nicht bei der Modellierung mit Wertebereichen: hier sollen alle Elemente eines Wertebereiches gleichartig sein. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 205a Ziele: Definition von Mengen verstehen in der Vorlesung: * Beispiele zu den Eigenschaften. * Hier informelle Definition des Mengenbegriffs; axiomatische Mengenlehre definiert ihn strenger. Verständnisfragen: * Geben Sie Beispiele jeweils für unterschiedliche intensionale und für unterschiedliche extensionale Definitionen derselben Menge. * Vergleichen Sie den Mengenbegriff mit dem aus Mathe I. * Geben Sie Mengen an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod - 2.5r Russels Paradoxon Man muss prinzipiell entscheiden können, ob ein Wert a Element einer Menge M ist, "a element M?" Russels Paradoxon: Sei P die Menge aller Mengen, die sich nicht selbst als Element enthalten, also P := { x | x notelement x}. Dann führt die Frage "Ist P Element von P?" zum Widerspruch. Um solche Anomalien auszuschließen, geben wir in intensionalen Mengendefinitionen an, aus welchem größeren, schon definierten Wertebereich die Elemente stammen: M := {a arrowvertex a element Iota N, a ist Quadratzahl und a lessequal 30} hier also "a element Iota N". Damit tatsächlich entschieden werden kann, welche Elemente M enthält, muss die Bedingung über a (hier "a ist Quadratzahl und a lessequal 30") entscheidbar sein. Diese Einschränkungen schließen nicht aus, Mengen rekursiv zu definieren, z. B. Sonnensystem := {Sonne} union { x | x element Himmelskörper, x umkreist y, y element Sonnensystem } (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 205r Ziele: Intensionale Definitionen können widersprülich sein in der Vorlesung: * Paradoxon erläutern. * Beispiel: "Der Barbier rasiert alle Männer des Dorfes, die sich nicht selbst rasieren." Ist er Element dieser Menge? -------------------------------------------------------------------------------- Mod - 2.6 Mengenoperationen Teilmenge von M reflexsubset N aus a element M folgt a element N echte Teilmenge von M propersubset N M reflexsubset N und M notequal N Vereinigung M union N := {x arrowvertex x element M oder x element N} Durchschnitt M intersection N := {x arrowvertex x element M und x element N} Differenz M \ N := {x arrowvertex x element M und x notelement N} M und N sind disjunkt genau dann, wenn gilt M intersection N = emptyset (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 206 Ziele: Vorstellung der Mengenoperatoren in der Vorlesung: * Hinweis auf algebraische Gesetze; werden hier nicht vertieft Verständnisfragen: * Schlagen Sie die algebraischen Gesetze der Mengenoperatoren nach. -------------------------------------------------------------------------------- Mod - 2.7 2.2 Potenzmengen Potenzmenge (powerset) einer Grundmenge U ist die Menge aller Teilmengen von U, geschrieben Pow (U) oder weierstrass (U). Pow (U) := {M | M reflexsubset U} Kardinalität: arrowvertex Pow (U)arrowvertex = 2n wenn arrowvertex Uarrowvertex = n Beispiele: Grundmenge U1 := {a, b} Potenzmenge Pow (U1) = {emptyset , {a}, {b}, {a, b}} Grundmenge U2 := {1, 2, 3} Pow (U2) = { emptyset , {1}, {2}, {3}, {1,2}, {1,3}, {2,3}, {1,2,3} } Wenn die Werte Teilmengen von U sind, ist ihr Wertebereich die Potenzmenge von U. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 207 Ziele: Potenzmenge als Wertebereich verstehen in der Vorlesung: * Kardinalität begründen * Beispiele, * Wert - Wertebereich; Menge - Potenzmenge * Aufgabe mit Lösungsmenge Verständnisfragen: * Begründen sie die Kardinalitätsformel. * Geben Sie Potenzmengen an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod - 2.7a Modellierung mit Potenzmengen Beispiel 2.1: Wertebereich der Sprachen, die ein Delegierter spricht SprachMengen := Pow (Nationen), {A, B} element SprachMengen Modellierungstechnik: Menge von Lösungen statt einer Lösung Manche Aufgaben haben nicht immer genau eine Lösung, sondern je nach Daten mehrere oder keine Lösung. Dann kann man nach der Menge aller Lösungen fragen. Der Wertebereich der Antwort ist die Potenzmenge des Wertebereiches der Lösungen. Vergleiche auch Mengentyp in Pascal: type Sprachen = set of {A, B, C}; var spricht: Sprachen; spricht := {A, B}; (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 207a Ziele: Potenzmenge als Wertebereich verstehen in der Vorlesung: * Kardinalität begründen * Beispiele, * Wert - Wertebereich; Menge - Potenzmenge * Aufgabe mit Lösungsmenge Verständnisfragen: * Begründen sie die Kardinalitätsformel. * Geben Sie Potenzmengen an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod - 2.8 2.3 Kartesische Produkte Kartesisches Produkt der Mengen M und N: Menge aller geordneten Paare mit erster Komponente aus M und zweiter Komponente aus N M multiply N := {z | z = (x, y) und x element M und y element N} oder kürzer M multiply N := {(x, y) | x element M und y element N} Enthält alle Kombinationen von Werten aus M und N. Falls M = emptyset oder N = emptyset , ist M multiply N = emptyset . z. B. Delegierte := Nation multiply Ind = { (A, 1), (A, 2),..., (B, 1), (B, 2), .... } Verallgemeinert zu n-Tupeln (n>1, geordnet): M1 multiply M2 multiply ellipsis multiply Mn := {(a1, a2, ellipsis , an) | ai element Mi und i element I} mit I := {1, ellipsis ,n} und n > 1 z. B. Daten := Tage multiply Monate multiply Jahre, (24, 10, 2011) element Daten Folgende Wertebereiche sind verschieden. Ihre Elemente haben unterschiedliche Struktur: (a, b, c) element A multiply B multiply C ((a, b), c) element (A multiply B) multiply C Notation bei gleichen Mengen Mi : M multiply M multiply ellipsis multiply M = Mn mit n > 1 Beispiel: Wertebereich der Ergebnisse 3-maligen Würfelns: DreiWürfe := {1, 2, 3, 4, 5, 6}3 Kardinalität: | M1 multiply M2 multiply ellipsis multiply Mn | = Pi i element I |Mi| mit I = {1,..., n} mit n > 1 (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 208 Ziele: Zusammengesetzte Wertebereiche verstehen in der Vorlesung: Erläuterungen dazu * Ordnung der Komponenten ist wichtig. * Beispiel für geschachtelte Tupel Verständnisfragen: * Was ist der Unterschied zwischen Nation x Ind x SprachMengen und (Nation x Ind) x SprachMengen? * Welches ist besser im Sinne von Beispiel 2.1? * Geben Sie kartesische Produkte an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod-2.8a 2.4 Disjunkte Vereinigung Die allgemeine disjunkte Vereinigung fasst n Wertebereiche (Mengen) A1, A2, ...Ai, ..., An zu einem vereinigten Wertebereich V zusammen, wobei i element I := {1, ..., n}. Die Herkunft der Elemente aus Ai wird in den Paaren von V gekennzeichnet: V := { (i, ai) | ai element Ai } Die erste Komponente der Paare ist eine Kennzeichenkomponente (engl. tag field). Die Ai brauchen nicht paarweise disjunkt zu sein. Kardinalität: |V| = iSigma element I |Ai| Anwendungsmuster: V ist ein allgemeinerer Wertebereich, er abstrahiert von den spezielleren A i Beispiele: Geschäftspartner := { (Kunde, Siemens), (Kunde, Benteler), (Kunde, Unity), (Lieferant, Orga), (Lieferant, Siemens)} mit Kunden := {Siemens, Benteler, Unity} Lieferanten := {Orga, Siemens} Ind := {Kunde, Lieferant} Buchstaben := {a, b, ..., z} Ziffern := {0, 1, ..., 9} Ind := {Buchstabe, Ziffer} Zeichen = { (Buchstabe, b) | b element Buchstaben} union { (Ziffer, z) | z element Ziffern} (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 208a Ziele: Kennzeichnung von Werten in der Vorlesung: * Rolle des Kennzeichenfeldes * Klassifikation von Wertebereichen * Vergleich mit Varianten-Records in Pascal Verständnisfragen: Geben Sie Wertebereiche mit disjunkten Vereinigungen an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod-2.8b 2.5 Folgen Endliche Folgen von Elementen aus A: Sei A0 := { epsilon } die Menge, die nur die leere Folge über A, epsilon bzw. (), enthält, A1 := { (a) | a element A} die Menge einelementiger Folgen über A, An mit n > 1 die Menge der n-Tupel über A, dann ist A+ := { x | x element Ai und i greaterequal 1 } die Menge der nicht-leeren Folgen beliebiger Länge über A und A* := A+ union A0 die Menge von Folgen über A, die auch die leere Folge enthält. Folgen notieren wir wie Tupel, d. h. (a1, ..., an) element A+ für n greaterequal 1 und ai element A; () element A* Beispiele: (1, 1, 2, 5, 5, 10, 20) element Iota N+ (m, o, d, e, l, l) element Buchstaben+ neueAufträge := Auftrag* gezogeneKarten := Karten* (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 208b Ziele: Folgen gleichartiger Elemente in der Vorlesung: Erläuterungen dazu * 1-Tupel und 0-Tupel sind auf Folie Mod2.8 nicht als kartesische Produkte definiert. Deshalb werden hier leere und einelementige Folgen definiert. * + und * Notation erläutern * weitere Beispiele * Verwendung der leeren Folge Verständnisfragen: * Aus einer Folge natürlicher Zahlen sollen die geraden Zahlen gestrichen werden. Aus welchem Wertebereich stammt das Ergebnis? * Geben Sie Folgen an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod - 2.9 2.6 Relationen Relationen sind Teilmengen aus kartesischen Produkten. n-stellige Relation: R reflexsubset M1 multiply M2 multiply ellipsis multiply Mn mit n > 1 R ist also eine Menge von n-Tupeln. Wertebereich von R: R element Pow (M1 multiply M2 multiply ellipsis multiply Mn) Eine 1-stellige Relation R über einer Menge M ist eine Teilmenge von M, also Relement Pow (M). Eine Relation R definiert eine Aussage über Tupel. Wir sagen auch: "Eine Relation R gilt für die Tupel, die R enthält." Beispiele: Relation lessequal reflexsubset Iota Nmultiply Iota N ein Element daraus: (27, 42) element lessequal also gilt 27 lessequal 42 NationenKleiner := {(A, C), (C, B), (A, B)} reflexsubset Nationen2 Menüs22-10 := {(Lauchsuppe, Putenbraten, Eisbecher), (Lauchsuppe, Kalbsteak, Ananas), (Salat, Omelett, Ananas)} Menüs22-10 reflexsubset Vorspeisen multiply Hauptgerichte multiply Desserts mit Vorspeisen := {Lauchsuppe, Salat, ...}; Hauptgerichte := {Putenbraten, Kalbsteak, Omelett, ...} Desserts := {Eisbecher, Ananas, Schokoladenpudding, ...} (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 209 Ziele: Allgemeine Relationen verstehen in der Vorlesung: * Erläuterungen dazu * Zusammenhang zwischen Relationen und Aussagen über Tupel. Verständnisfragen: * Geben Sie Beispiele für Relationen zwischen Werten aus unterschiedlichen Wertebereichen. * Geben Sie Relationen und ihre Wertebereiche an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod - 2.9a Kardinalität, Schreibweisen Der Wertebereich Pow (M1 multiply M2 multiply ellipsis multiply Mn) hat die Kardinalität Pi |Pow (M1 multiply M2 multiply ellipsis multiply Mn)| = 2 i element I |Mi|, falls alle Mi endlich sind. Pi d.h. es gibt 2i element I |Mi| verschiedene Relationen in dem Wertebereich. Intensionale Definition einer Relation: GültigeDaten reflexsubset Daten = Tage multiply Monate multiply Jahre GültigeDaten := { (t, m, j) | t, m, j element Iota N, mlessequal 12, (melement {1,3,5,7,8,10,12} logicaland t lessequal 31) logicalor (melement {4,6,9,11} logicaland t lessequal 30) logicalor (m = 2 logicaland t lessequal 29 logicaland Schaltjahr (j)) logicalor (m = 2 logicaland t lessequal 28 logicaland logicalnot Schaltjahr (j))} (24, 10, 2011), (29, 2, 2012) element GültigeDaten, (31, 4, 2010) notelement GültigeDaten alternative Schreibweisen für Elemente aus Relationen: R(a) für a element R, z. B. GültigeDaten(24, 10, 2011) bei 2-stelligen Relationen auch mit Operatoren: x R y für (x, y) element R, z. B. x lessequal y , a notequal b , p arrowright q (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 209a Ziele: Allgemeine Relationen verstehen in der Vorlesung: * Erläuterungen dazu * Zusammenhang zwischen Relationen und Aussagen über Tupel. Verständnisfragen: * Geben Sie Beispiele für Relationen zwischen Werten aus unterschiedlichen Wertebereichen. * Geben Sie Relationen und ihre Wertebereiche an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod - 2.10 Eigenschaften 2-stelliger Relationen Für zweistellige Relationen R reflexsubset M multiply M mit M notequal emptyset sind folgende Begriffe definiert: * reflexiv, wenn für alle x element M gilt: x R x; * irreflexiv, wenn für kein x element M gilt: x R x; * symmetrisch, wenn für alle x, y element M gilt: aus x R y folgt y R x; * antisymmetrisch, wenn für alle x, y element M gilt: aus x R y und y R x folgt x = y; * asymmetrisch, wenn für alle x, y element M gilt: aus x R y folgt, y R x gilt nicht; * transitiv, wenn für alle x, y, z element M gilt: aus x R y und y R z folgt x R z; * total, wenn für alle x, y element M gilt: x R y oder y R x; Hinweise zum Anwenden der Definitionen (genauer in Kap. 4.1, 4.2): 1. "x R y" bedeutet "(x, y) element R" 2. "für alle x element M gilt ...": der gesamte Wertebereich M muss geprüft werden 3. "für alle x, y element M gilt ...": alle Paare von Werten aus M prüfen, auch solche mit x = y 4. "A oder B" ist wahr, wenn mindestens eins von beiden wahr ist 5. "aus A folgt B" ist gleichwertig zu "(nicht A) oder B". (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 210 Ziele: Definitionen verstehen und einprägen in der Vorlesung: * Die Form der Definitionen wird erläutert. * Das Prüfen der Definitionen wird an Relationen mit kleiner Menge M = {A, B, C} erläutert. * Im Buch "Modellierung" ist auf den Seiten 36 und 37 die Eigenschaft "alternative Relation" falsch definiert, bzw. erklärt. Zur Korrektur ersetze man in den Definitionen 2.10 und 2.12 sowie in der Tabelle auf Seite 37 oben den Begriff "alternativ" durch "total". Verständnisfragen: * Konstruieren Sie zu jeder Eigenschaft eine Relation R über M = {A, B, C}, die die Eigenschaft nicht erfüllt. Beschreiben Sie R in Worten. -------------------------------------------------------------------------------- Mod - 2.10a Beispiele für Eigenschaften 2-stelliger Relationen sei M = { A, B, C } Eigenschaft ist z.B. erfüllt von R = ... z.B. nicht erfüllt von R = ... reflexiv {(A,A), (B,B), (C,C), (A,B)} {(A,A), (B,C)} irreflexiv {(A,B)} {(A,A)} symmetrisch {(A,B), (B,A), (C,C)} {(A,B)} antisymmetrisch {(A,B), (C,C)} {(A,B), (B,A)} asymmetrisch {(A,B), (C,A)} {(A,B), (B,A)} oder {(C,C)} transitiv {(A,B), (B,C), (A,C)} {(A,B), (B,C)} total {(A,A), (B,B), (C,C), {(A,A), (A,B), (A,C)} (A,B), (B,C), (A,C), (C,B)} {(A,B), (A,C), (C,B), (C,C)} A B als gerichteter Graph: (siehe Kap. 5) C (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 210a Ziele: Eigenschaften am Beispiel prüfen in der Vorlesung: Einige Beispiele werden erläutert. -------------------------------------------------------------------------------- Mod - 2.10c Ordnungsrelationen Eine zweistellige Relationen R reflexsubset M multiply M ist eine * partielle Ordnung oder Halbordnung, wenn R reflexiv, antisymmetrisch und transitiv ist; * strenge Ordnung oder strenge Halbordnung, wenn R irreflexiv und transitiv ist; * Quasiordnung, wenn R reflexiv und transitiv ist; * totale oder lineare Ordnung, wenn R eine totale Halbordnung ist, also total, (reflexiv,) antisymmetrisch und transitiv; * Äquivalenzrelation, wenn R reflexiv, symmetrisch und transitiv ist. Aussagen zu diesen Definitionen 1. Alle solche Ordnungsrelationen sind transitiv. 2. Ist R eine totale Ordnung, dann ist R auch eine Halbordnung und eine Quasiordnung. 3. Nur für totale Ordnungen wird gefordert, dass alle Elemente aus M "vergleichbar" sind (total). 4. Enthält R "Zyklen über verschiedene Elemente", z.B. (a, b), (b, a) element R mit a notequal b, dann ist R weder eine Halbordnung, strenge Halbordnung, noch eine totale Ordnung. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 210c Ziele: Definition der Ordnungsrelationen verstehen in der Vorlesung: * Die Definitionen werden erläutert. * Die Definitionen wird an Relationen mit kleiner Menge M = {A, B, C} sowie an < und <= über N geprüft erläutert. Verständnisfragen: * Beschreiben Sie den Unterschied zwischen Halbordnung und totaler Ordnung. Geben Sie ein Beispiel dazu an. -------------------------------------------------------------------------------- Mod - 2.10d Beispiele für Ordnungsrelationen sei M = {A, B, C}, eqM := {(A,B), (B,A), (A,A), (B,B), (C,C)} B ist die Menge aller Funktionen, die von D auf B abbilden. Es gilt D -> B reflexsubset Pow (D multiply B). D -> B enthält als Elemente alle Mengen von Paaren über D multiply B, die Funktionen sind. Statt f element D -> B sagt man auch f hat die Signatur D -> B oder kurz f: D -> B Schreibweisen für (x, y) element f auch y = f (x) oder f (x) = y oder x f y Die Menge aller Paare (x, y) element f heißt Graph von f. Eine Funktion f element D -> B heißt n-stellig, wenn der Definitionsbereich D ein Wertebereich von n-Tupeln ist, n > 1; 1-stellig, wenn D nicht als kartesisches Produkt strukturiert ist und nicht leer ist. Man spricht auch von 0-stelligen Funktionen, wenn D der leere Wertebereich ist; 0-stellige Funktionen sind konstante Funktionen für jeweils einen festen Wert b = f(); man kann sie allerdings nicht als Menge von Paaren angeben. (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 211 Ziele: Grundbegriffe von Funktionen verstehen in der Vorlesung: * Begriffe an Beispielen erläutern * unterscheiden: Funktion, ihre Definition, der Wertebereich, aus dem sie stammt Achtung! unterschiedliche Verwendung von Begriffen: * hier: Der Wertebereich D -> B ist die Menge aller Funktionen, die von D auf B abbilden. * hier: Die Funktion f: D -> B hat den Bildbereich B. * Mathe I: Der Wertebereich einer Funktion f: D -> B ist B * Goos: Der Bildbereich einer Funktion f: D -> B ist Bild(f) = B . (Werde ich hier nicht verwenden.) * Mathe I: Das Bild von f ist die Menge der Werte, auf die f abbildet. Verständnisfragen: Geben Sie Funktionen und ihre Wertebereiche an, die sie für die Modellierung des Getränkeautomaten benötigen. -------------------------------------------------------------------------------- Mod - 2.11b Beispiele für Funktionen Funktion aus dem Wertebereich not := {(w, f), (f, w)} Bool -> Bool id := {(w,w), (f, f)} Bool -> Bool oder := {((w,w),w), ((w,f),w), ((f,w),w), ((f,f),f)} Bool multiply Bool -> Bool Quadrat := {(a, b) | a, b element Iota N und b = a*a} Iota N -> Iota N ggt := {((a,b),c) | a, b, c element Iota N und c ist größter Iota N multiply Iota N -> Iota N gemeinsamer Teiler von a und b} Sp := {((A, 1), {A,B}), ((B, 2), {B})} Delegierte -> SprachMengen (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 211b Ziele: Beispiele zu Funktionen in der Vorlesung: Beispiele erläutern -------------------------------------------------------------------------------- Mod - 2.12 Eigenschaften von Funktionen Eine Funktion f : D -> B heißt * total, wenn es für jedes x element D ein Paar (x, y) element f gibt, * partiell, wenn nicht verlangt wird, dass f für alle x element D definiert ist, * surjektiv, wenn es zu jedem y element B ein Paar (x, y) element f gibt, * injektiv, wenn es zu jedem y element B höchstens ein Paar (x, y) element f gibt, * bijektiv, wenn f surjektiv und injektiv ist. Kardinalität des Wertebereiches, aus dem Funktionen stammen | D -> B | = (| B |+1)|D| Anzahl der totalen Funktionen in | D -> B | ist | B ||D| ... falls D und B endlich sind. Anzahl der Möglichkeiten für unterschiedliche Funktionen mit dieser Signatur z. B. |{A, B, C} -> {w, f}| = 33 = 27 insgesamt; 23= 8 totale Funktionen in |{A, B, C} -> {w, f}| (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 212 Ziele: Begriffe einprägen in der Vorlesung: Erläuterungen dazu * Begriffe erläutern * Graphiken dazu * Kardinalität begründen Verständnisfragen: * Charakterisieren Sie die Eigenschaften graphisch. -------------------------------------------------------------------------------- Mod - 2.13 Spezielle Funktionen Identitätsfunktion idM : M -> M mit idM := { (x, x) | x element M } Charakteristische Funktion chi M einer Menge M reflexsubset U, mit der Trägermenge U gibt für jedes Element der Trägermenge U an, ob es in M enthalten ist: chi M : U -> Bool mit chi M := { (x, b) | x element U und b = (xelement M)} chi M ist eine totale Funktion Funktionen mit dem Bildbereich Bool heißen Prädikate. z. B. <= : (Iota N0 multiply Iota N0) -> Bool (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 213 Ziele: Spezielle Anwendungsmuster in der Vorlesung: * Zusammenhang zu Relationen erläutern. * Beispiele für charakteristische Funktionen und Multimengen angeben. Verständnisfragen: * Geben Sie weitere Anwendungen für solche Funktionen an. -------------------------------------------------------------------------------- Mod - 2.13a Funktionen zur Modellierung von mehrfachen Vorkommen In sogenannte Multimengen (engl. bags) können einige Werte mehrfach vorkommen. Es ist relevant, wieoft jeder Wert vorkommt. Das mehrfache Vorkommen von Werten in einer Multimenge modellieren wir mit einer Funktion: b: V -> Iota N0gibt für jeden Wert aus V an, wie oft er vorkommt, z. B. geldBeutel element EUMünzen -> Iota N0 mit geldBeutel := {(1,3), (2, 0), (5,0), (10, 2), (20, 4), (50, 1), (100, 3), (200, 2)} (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 213a Ziele: Spezielle Anwendungsmuster in der Vorlesung: * Zusammenhang zu Relationen erläutern. * Beispiele für charakteristische Funktionen und Multimengen angeben. Verständnisfragen: * Geben Sie weitere Anwendungen für solche Funktionen an. -------------------------------------------------------------------------------- Mod - 2.13b Funktionen auf Indexmengen Indexmengen dienen zur Unterscheidung von Objekten des Modellbereiches z. B. Ind = {1, ..., n}, KartenSymbole := {7, 8, 9, 10, Bube, Dame, König, Ass} Funktionen auf Indexmengen modellieren ... das Auftreten von Werten in Folgen: Beispiel: eine Folge F := (w, e, l, l, e) Indexmenge dazu FPositionen := {1, 2, 3, 4, 5} Werte in der Folge FWerte := {w, e, l} Auftreten von Werten in der Folge FAuftreten := {(1, w), (2, e), (3, l), (4, l), (5, e)} Wertebereich FAuftreten element FPositionen -> FWerte Zuordnungen zwischen Mengen: z. B. Gepäckstücke ihren Eigentümern zuordnen durch ein Funktionenpaar Marke1 element Ind -> Gepäckstücke (injektiv) Marke2 element Ind -> Eigentümer 434343 4343 43 4343 42 23 11 11 42 23 (c) 2011 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 213b Ziele: Zwei Modellierungschemata in der Vorlesung: * Unterschied: "Werte, die (irgendwo) auftreten", "verschiedene Auftreten eines Wertes". * Zuordnen durch Markieren mit der gleichen Marke, Verständnisfragen: * Warum muss Marke1 injektiv sein, Marke2 aber nicht? * Geben Sie weitere Anwendungen für Funktionen mit Indexmengen an. -------------------------------------------------------------------------------- Mod-2.14a Hinweise zum Modellieren mit Wertebereichen * Erst Grundmengen festlegen, dann Strukturen darüber bilden. * Typische Elemente eines Wertebereiches angeben - der Wertebereich ist eine Menge davon. * Wertebereichen ausdruckskräftige Namen geben. * Zusammengesetzte Wertebereiche schrittweise aufbauen (oder zerlegen). * Entwürfe prüfen: Wertebereiche in Worten erklären. * Nur gleichartige Elemente in einem Wertebereich. * Mengen, Tupel und Folgen beliebiger Länge nicht verwechseln. * Alle Klammern haben Bedeutung - zusätzliche verändern das Modell. (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 214a Ziele: Modellierungsfehler vermeiden in der Vorlesung: Erläuterungen dazu an typischen Fehlern Übungsaufgaben: Untersuchen Sie: * Welche Aspekte des Getränkeautomaten können Sie mit Mengen als Wertebereichen gut Modellieren? * Für welche Aspekte eignet sich der Kalkül nicht so gut. -------------------------------------------------------------------------------- Mod-2.14b Wertebereiche zur Modellierung des Getränkeautomaten Folgende Aspekte des Getränkeautomaten können durch Wertebereiche Modelliert werden: * Getränkevarianten * Vorrat an Getränken und Zutaten * Vorrat an Wechselgeld * Eingeworfene Münzen * Betätigte Wahltasten * Anzeige des Automaten * Zustand des Automaten * weitere Aspekte ... (c) 2007 bei Prof. Dr. Uwe Kastens -------------------------------------------------------------------------------- Vorlesung Modellierung WS 2011/12 / Folie 214b Ziele: Anregung zur Modellierung des Getränkeautomaten in der Vorlesung: Erläuterungen dazu --------------------------------------------------------------------------------