96
Methodenlehre Logik, Mengen, Relationen Klaus Frieler Musikwissenschaftliches Institut Universität Hamburg 17.11.2009

Logik, Mengen, Relationen

Embed Size (px)

DESCRIPTION

Der Titel sagt alles. Aussagenlogik, Prädikatenlogik, Mengen und Relationen im Schnelldurchlauf für den eiligen Lerner

Citation preview

  • 1. Methodenlehre Logik, Mengen, Relationen Klaus Frieler Musikwissenschaftliches Institut Universitt Hamburg17.11.2009

2. Aussagenlogik Die Aussagenlogik beschreibt die Wahrheitsfunktionen von zusammengesetzten Aussagen Die Aussagenlogik sagt nichts ber die Wahrheit atomarer Aussagen. Atomare Aussagen knnen durch Junktoren (=Verbindern) zu neuen Aussagen verbunden werden Die klassische Aussagenlogik geht von zwei mglichen Wahrheitswerten aus: Wahr (true, T, W, 1) oder Falsch (false, F, 0) (Zweiwertigkeit) Menge der Wahrheitswerte = {W , F } 3. Aussagenlogik Die Aussagenlogik beschreibt die Wahrheitsfunktionen von zusammengesetzten Aussagen Die Aussagenlogik sagt nichts ber die Wahrheit atomarer Aussagen. Atomare Aussagen knnen durch Junktoren (=Verbindern) zu neuen Aussagen verbunden werden Die klassische Aussagenlogik geht von zwei mglichen Wahrheitswerten aus: Wahr (true, T, W, 1) oder Falsch (false, F, 0) (Zweiwertigkeit) Menge der Wahrheitswerte = {W , F } 4. Aussagenlogik Die Aussagenlogik beschreibt die Wahrheitsfunktionen von zusammengesetzten Aussagen Die Aussagenlogik sagt nichts ber die Wahrheit atomarer Aussagen. Atomare Aussagen knnen durch Junktoren (=Verbindern) zu neuen Aussagen verbunden werden Die klassische Aussagenlogik geht von zwei mglichen Wahrheitswerten aus: Wahr (true, T, W, 1) oder Falsch (false, F, 0) (Zweiwertigkeit) Menge der Wahrheitswerte = {W , F } 5. Aussagenlogik Die Aussagenlogik beschreibt die Wahrheitsfunktionen von zusammengesetzten Aussagen Die Aussagenlogik sagt nichts ber die Wahrheit atomarer Aussagen. Atomare Aussagen knnen durch Junktoren (=Verbindern) zu neuen Aussagen verbunden werden Die klassische Aussagenlogik geht von zwei mglichen Wahrheitswerten aus: Wahr (true, T, W, 1) oder Falsch (false, F, 0) (Zweiwertigkeit) Menge der Wahrheitswerte = {W , F } 6. Aussagenlogik Die Aussagenlogik beschreibt die Wahrheitsfunktionen von zusammengesetzten Aussagen Die Aussagenlogik sagt nichts ber die Wahrheit atomarer Aussagen. Atomare Aussagen knnen durch Junktoren (=Verbindern) zu neuen Aussagen verbunden werden Die klassische Aussagenlogik geht von zwei mglichen Wahrheitswerten aus: Wahr (true, T, W, 1) oder Falsch (false, F, 0) (Zweiwertigkeit) Menge der Wahrheitswerte = {W , F } 7. Aussagenlogik Die klassische Aussagenlogik besitzt 5 klassische Junktoren Negation, Konjunktion, Disjunktion, materiale Implikation (Subjunktion, Konditional), Bikonditional Junktoren sind einstellige (Negation) oder zweistellige Funktionen der Wahrheitswerte in die Wahrheitswerte f1 : f2 : Traditionell und am einfachsten durch Wahrheitstafeln darstellt 8. Aussagenlogik Die klassische Aussagenlogik besitzt 5 klassische Junktoren Negation, Konjunktion, Disjunktion, materiale Implikation (Subjunktion, Konditional), Bikonditional Junktoren sind einstellige (Negation) oder zweistellige Funktionen der Wahrheitswerte in die Wahrheitswerte f1 : f2 : Traditionell und am einfachsten durch Wahrheitstafeln darstellt 9. Aussagenlogik Die klassische Aussagenlogik besitzt 5 klassische Junktoren Negation, Konjunktion, Disjunktion, materiale Implikation (Subjunktion, Konditional), Bikonditional Junktoren sind einstellige (Negation) oder zweistellige Funktionen der Wahrheitswerte in die Wahrheitswerte f1 : f2 : Traditionell und am einfachsten durch Wahrheitstafeln darstellt 10. Aussagenlogik Der Wahrheitswert (P) von zusammengesetztenAussagen ergibt sich aus den Wahrheitswerten derEinzelaussagen und den Funktionswerten der beteiligtenJunktoren (Extensionalitt) Zwei Aussagen P, Q heien quivalent (P Q, P = Q),wenn sie bei jeder Interpretation denselben Wahrheitswertergeben 11. Aussagenlogik Der Wahrheitswert (P) von zusammengesetztenAussagen ergibt sich aus den Wahrheitswerten derEinzelaussagen und den Funktionswerten der beteiligtenJunktoren (Extensionalitt) Zwei Aussagen P, Q heien quivalent (P Q, P = Q),wenn sie bei jeder Interpretation denselben Wahrheitswertergeben 12. Aussagenlogik Negation (P): Umkehrung des WahrheitswertesW= FF = W Idempotent: P = P Beispiel: P = 2147483647 ist eine Primzahl, P = 2147483647 ist keine Primzahl 13. Aussagenlogik Negation (P): Umkehrung des WahrheitswertesW= FF = W Idempotent: P = P Beispiel: P = 2147483647 ist eine Primzahl, P = 2147483647 ist keine Primzahl 14. Aussagenlogik Negation (P): Umkehrung des WahrheitswertesW= FF = W Idempotent: P = P Beispiel: P = 2147483647 ist eine Primzahl, P = 2147483647 ist keine Primzahl 15. Aussagenlogik Konjunktion (P Q): Umgangsprachlich und. Wahr, wenn beide Aussagen wahr sind W F W W FF F F Kommutativ und Assoziativ: P Q = Q P, (P Q) R = P (Q R) Beispiel: P = 4 ist eine gerade Zahl (W), Q =4 ist eine Primzahl (F), P Q = 4 ist eine gerade Primzahl (F) 16. Aussagenlogik Konjunktion (P Q): Umgangsprachlich und. Wahr, wenn beide Aussagen wahr sind W F W W FF F F Kommutativ und Assoziativ: P Q = Q P, (P Q) R = P (Q R) Beispiel: P = 4 ist eine gerade Zahl (W), Q =4 ist eine Primzahl (F), P Q = 4 ist eine gerade Primzahl (F) 17. Aussagenlogik Konjunktion (P Q): Umgangsprachlich und. Wahr, wenn beide Aussagen wahr sind W F W W FF F F Kommutativ und Assoziativ: P Q = Q P, (P Q) R = P (Q R) Beispiel: P = 4 ist eine gerade Zahl (W), Q =4 ist eine Primzahl (F), P Q = 4 ist eine gerade Primzahl (F) 18. Aussagenlogik Disjunktion (P Q): Umgangsprachlich oder. Wahr, wenn mindesten eine der Aussagen wahr ist (nicht entweder- oder!) W F W W W F W F Kommutativ und Assoziativ: P Q = Q P, (P Q) R = P (Q R) Beispiel: P = 4 ist eine gerade Zahl (W), Q =4 ist eine Primzahl (F), P Q = 4 ist eine Primzahl oder 4 ist gerade (W) 19. Aussagenlogik Disjunktion (P Q): Umgangsprachlich oder. Wahr, wenn mindesten eine der Aussagen wahr ist (nicht entweder- oder!) W F W W W F W F Kommutativ und Assoziativ: P Q = Q P, (P Q) R = P (Q R) Beispiel: P = 4 ist eine gerade Zahl (W), Q =4 ist eine Primzahl (F), P Q = 4 ist eine Primzahl oder 4 ist gerade (W) 20. Aussagenlogik Disjunktion (P Q): Umgangsprachlich oder. Wahr, wenn mindesten eine der Aussagen wahr ist (nicht entweder- oder!) W F W W W F W F Kommutativ und Assoziativ: P Q = Q P, (P Q) R = P (Q R) Beispiel: P = 4 ist eine gerade Zahl (W), Q =4 ist eine Primzahl (F), P Q = 4 ist eine Primzahl oder 4 ist gerade (W) 21. Aussagenlogik Konditional, materiale Implikation (P Q): Umgangsprachlich (schon) wenn - dann. Falsch, wenn aus einer wahren Aussagen etwas Falsches folgt.PQ PQWWWWFFFWWex falso sequitur quodlibetFFWex falso sequitur quodlibet Nicht assoziativ, nicht kommutativ. Beispiel: P = Es regnet, Q =Die Strae ist nass, P Q = Wenn es regnet, dann ist die Strae nass 22. Aussagenlogik Konditional, materiale Implikation (P Q): Umgangsprachlich (schon) wenn - dann. Falsch, wenn aus einer wahren Aussagen etwas Falsches folgt.PQ PQWWWWFFFWWex falso sequitur quodlibetFFWex falso sequitur quodlibet Nicht assoziativ, nicht kommutativ. Beispiel: P = Es regnet, Q =Die Strae ist nass, P Q = Wenn es regnet, dann ist die Strae nass 23. Aussagenlogik Konditional, materiale Implikation (P Q): Umgangsprachlich (schon) wenn - dann. Falsch, wenn aus einer wahren Aussagen etwas Falsches folgt.PQ PQWWWWFFFWWex falso sequitur quodlibetFFWex falso sequitur quodlibet Nicht assoziativ, nicht kommutativ. Beispiel: P = Es regnet, Q =Die Strae ist nass, P Q = Wenn es regnet, dann ist die Strae nass 24. Aussagenlogik Bikonditional (P Q): Umgangsprachlich genau wenn - dann. P Q P Q Q P PQPQWW WWF FFW FFF W Kommutativ und assoziativ Beispiel: P = x besitzt nur sich selbst und 1 als Teiler, Q =x ist eine Primzahl, P Q = x ist genau dann eine Primzahl, wenn es nur sich selbst und 1 als Teiler besitzt 25. Aussagenlogik Bikonditional (P Q): Umgangsprachlich genau wenn - dann. P Q P Q Q P PQPQWW WWF FFW FFF W Kommutativ und assoziativ Beispiel: P = x besitzt nur sich selbst und 1 als Teiler, Q =x ist eine Primzahl, P Q = x ist genau dann eine Primzahl, wenn es nur sich selbst und 1 als Teiler besitzt 26. Aussagenlogik Bikonditional (P Q): Umgangsprachlich genau wenn - dann. P Q P Q Q P PQPQWW WWF FFW FFF W Kommutativ und assoziativ Beispiel: P = x besitzt nur sich selbst und 1 als Teiler, Q =x ist eine Primzahl, P Q = x ist genau dann eine Primzahl, wenn es nur sich selbst und 1 als Teiler besitzt 27. Aussagenlogik Tautologie: Logische Form, die immer Wahr ist, unabhngig vom Wahrheitswert der Aussagen, z. B. P P (Satz vom ausgeschlossenen Dritten, tertium non datur )P P P P WF W F WW 28. Aussagenlogik Widerspruch: Logische Form, die immer Falsch ist, unabhngig vom Wahrheitswert der Aussagen, z. B. P P (Verneinung des Satz vom Widerspruch)PP P P W FF FW F Paradoxon: Logische Form, der kein (sinnvoller) Wahrheitswert zugeordnet werden kann (in der einfachen klassischen Aussagenlogik nicht mglich, da dort jeder Satz einen Wahrheitswert haben muss. Erscheint bei Selbstreferentialitt, z. B. in der Prdikatenlogik 2. Stufe) 29. Aussagenlogik Widerspruch: Logische Form, die immer Falsch ist, unabhngig vom Wahrheitswert der Aussagen, z. B. P P (Verneinung des Satz vom Widerspruch)PP P P W FF FW F Paradoxon: Logische Form, der kein (sinnvoller) Wahrheitswert zugeordnet werden kann (in der einfachen klassischen Aussagenlogik nicht mglich, da dort jeder Satz einen Wahrheitswert haben muss. Erscheint bei Selbstreferentialitt, z. B. in der Prdikatenlogik 2. Stufe) 30. Aussagenlogik Es gelten die de Morganschen Gesetze (P Q) = (P Q)(P Q) = (P Q) Distributivgesetze(P Q) R = (P R) (Q R) (P Q) R = (P R) (Q R) Absorptionsgesetze P (P Q) = PP (P Q) = P 31. Aussagenlogik Es gelten die de Morganschen Gesetze (P Q) = (P Q)(P Q) = (P Q) Distributivgesetze(P Q) R = (P R) (Q R) (P Q) R = (P R) (Q R) Absorptionsgesetze P (P Q) = PP (P Q) = P 32. Aussagenlogik Es gelten die de Morganschen Gesetze (P Q) = (P Q)(P Q) = (P Q) Distributivgesetze(P Q) R = (P R) (Q R) (P Q) R = (P R) (Q R) Absorptionsgesetze P (P Q) = PP (P Q) = P 33. Aussagenlogik Junktoren lassen sich durch durch andere Junktoren ausdrcken, z. B. de Morgansche Gesetze. Fr die Aussagenlogik reicht in der Tat ein einziger Junktor, z. B. Nicht-Oder (NOR, P Q := (P Q), Peirce-Funktion).P = P PP Q = (P Q) (P Q)P Q = (P P) (Q Q) 34. Aussagenlogik Junktoren lassen sich durch durch andere Junktoren ausdrcken, z. B. de Morgansche Gesetze. Fr die Aussagenlogik reicht in der Tat ein einziger Junktor, z. B. Nicht-Oder (NOR, P Q := (P Q), Peirce-Funktion).P = P PP Q = (P Q) (P Q)P Q = (P P) (Q Q) 35. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 36. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 37. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 38. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 39. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 40. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 41. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 42. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 43. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 44. Prdikatenlogik In der Prdikatenlogik betrachtet man auch die innere Struktur von Aussagen Prdikatenlogik 1. Stufe: Quantorenlogik Elemente: Variablen: x, y, z (v. a. gebundene Variable) Konstanten: a, b, c (v. a.freie Variable) Aussagen: P, Q, R Aussageformen: Funktionen von Variablen, z. B. F(x) Junktoren , , , , (Allquantor, Fr alle ) (Existenzquantor, Es gibt (mindestens) ein") 45. Prdikatenlogik - Schreib- und Sprechweisen x : F (x) bedeutet Fr alle x gilt die Aussage F(x) x : F (x) bedeutet Es gibt ein x fr das die Aussage F(x) gilt Dies sind wiederum Aussagen, die die Wahrheitswerte Wahr und Falsch annehmen knnen. Der Wertebereich fr gebunde Variablen ist ein meist nicht explizit angegebenes Universum. 46. Prdikatenlogik - Schreib- und Sprechweisen x : F (x) bedeutet Fr alle x gilt die Aussage F(x) x : F (x) bedeutet Es gibt ein x fr das die Aussage F(x) gilt Dies sind wiederum Aussagen, die die Wahrheitswerte Wahr und Falsch annehmen knnen. Der Wertebereich fr gebunde Variablen ist ein meist nicht explizit angegebenes Universum. 47. Prdikatenlogik - Schreib- und Sprechweisen x : F (x) bedeutet Fr alle x gilt die Aussage F(x) x : F (x) bedeutet Es gibt ein x fr das die Aussage F(x) gilt Dies sind wiederum Aussagen, die die Wahrheitswerte Wahr und Falsch annehmen knnen. Der Wertebereich fr gebunde Variablen ist ein meist nicht explizit angegebenes Universum. 48. Prdikatenlogik - Schreib- und Sprechweisen Das x in x : F (x) ist eine an die Quantoren gebundene Variable. In x : x y ist x gebunden, y frei, d. h. der ganze Term ist eine Aussageform G(y ). Jeder Quantor hat eine Reichweite bis zum Ende der Formel, bzw. einer Klammer. (Achtung: Es gibt auch andere Konventionen.) Zwei Quantoren in einem Term knnen also nicht denselben Variablennamen verwenden. Bsp.: In x, y : (F (x) G(y )) H(y ) ist das zweite y gebundene Variable, in (x, y : (F (x) G(y )) H(y ) ist es frei. 49. Prdikatenlogik - Schreib- und Sprechweisen Das x in x : F (x) ist eine an die Quantoren gebundene Variable. In x : x y ist x gebunden, y frei, d. h. der ganze Term ist eine Aussageform G(y ). Jeder Quantor hat eine Reichweite bis zum Ende der Formel, bzw. einer Klammer. (Achtung: Es gibt auch andere Konventionen.) Zwei Quantoren in einem Term knnen also nicht denselben Variablennamen verwenden. Bsp.: In x, y : (F (x) G(y )) H(y ) ist das zweite y gebundene Variable, in (x, y : (F (x) G(y )) H(y ) ist es frei. 50. Prdikatenlogik - Schreib- und Sprechweisen Das x in x : F (x) ist eine an die Quantoren gebundene Variable. In x : x y ist x gebunden, y frei, d. h. der ganze Term ist eine Aussageform G(y ). Jeder Quantor hat eine Reichweite bis zum Ende der Formel, bzw. einer Klammer. (Achtung: Es gibt auch andere Konventionen.) Zwei Quantoren in einem Term knnen also nicht denselben Variablennamen verwenden. Bsp.: In x, y : (F (x) G(y )) H(y ) ist das zweite y gebundene Variable, in (x, y : (F (x) G(y )) H(y ) ist es frei. 51. Prdikatenlogik - Schreib- und Sprechweisen Das x in x : F (x) ist eine an die Quantoren gebundene Variable. In x : x y ist x gebunden, y frei, d. h. der ganze Term ist eine Aussageform G(y ). Jeder Quantor hat eine Reichweite bis zum Ende der Formel, bzw. einer Klammer. (Achtung: Es gibt auch andere Konventionen.) Zwei Quantoren in einem Term knnen also nicht denselben Variablennamen verwenden. Bsp.: In x, y : (F (x) G(y )) H(y ) ist das zweite y gebundene Variable, in (x, y : (F (x) G(y )) H(y ) ist es frei. 52. Prdikatenlogik Beispiel: Alle Menschen sind sterblich. Sokrates ist ein Mensch. Also ist Sokrates ist sterblich Deniere F (x) = x ist ein Mensch, G(x) = x ist sterblich x : F (x) G(x) (Sprich: Fr alle x gilt: F(x) impliziert G(x) oder Wenn x ein Mensch ist, ist x sterblich) Spezialisierung: a = Sokrates, (F (a)) = W (G(a)) = W 53. Prdikatenlogik Beispiel: Alle Menschen sind sterblich. Sokrates ist ein Mensch. Also ist Sokrates ist sterblich Deniere F (x) = x ist ein Mensch, G(x) = x ist sterblich x : F (x) G(x) (Sprich: Fr alle x gilt: F(x) impliziert G(x) oder Wenn x ein Mensch ist, ist x sterblich) Spezialisierung: a = Sokrates, (F (a)) = W (G(a)) = W 54. Prdikatenlogik Beispiel: Alle Menschen sind sterblich. Sokrates ist ein Mensch. Also ist Sokrates ist sterblich Deniere F (x) = x ist ein Mensch, G(x) = x ist sterblich x : F (x) G(x) (Sprich: Fr alle x gilt: F(x) impliziert G(x) oder Wenn x ein Mensch ist, ist x sterblich) Spezialisierung: a = Sokrates, (F (a)) = W (G(a)) = W 55. Prdikatenlogik Beispiel: Alle Menschen sind sterblich. Sokrates ist ein Mensch. Also ist Sokrates ist sterblich Deniere F (x) = x ist ein Mensch, G(x) = x ist sterblich x : F (x) G(x) (Sprich: Fr alle x gilt: F(x) impliziert G(x) oder Wenn x ein Mensch ist, ist x sterblich) Spezialisierung: a = Sokrates, (F (a)) = W (G(a)) = W 56. Prdikatenlogik - Einige Regeln x : F (x) x : F (x) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) = y x : F (x, y ) x : F (x) x : F (x) x : F (x) x : F (x) x : (F (x) G(x)) (x : F (x)) (x : G(x)) x : (F (x) G(x)) (x : F (x)) (x : G(x)) 57. Prdikatenlogik - Einige Regeln x : F (x) x : F (x) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) = y x : F (x, y ) x : F (x) x : F (x) x : F (x) x : F (x) x : (F (x) G(x)) (x : F (x)) (x : G(x)) x : (F (x) G(x)) (x : F (x)) (x : G(x)) 58. Prdikatenlogik - Einige Regeln x : F (x) x : F (x) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) = y x : F (x, y ) x : F (x) x : F (x) x : F (x) x : F (x) x : (F (x) G(x)) (x : F (x)) (x : G(x)) x : (F (x) G(x)) (x : F (x)) (x : G(x)) 59. Prdikatenlogik - Einige Regeln x : F (x) x : F (x) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) = y x : F (x, y ) x : F (x) x : F (x) x : F (x) x : F (x) x : (F (x) G(x)) (x : F (x)) (x : G(x)) x : (F (x) G(x)) (x : F (x)) (x : G(x)) 60. Prdikatenlogik - Einige Regeln x : F (x) x : F (x) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) = y x : F (x, y ) x : F (x) x : F (x) x : F (x) x : F (x) x : (F (x) G(x)) (x : F (x)) (x : G(x)) x : (F (x) G(x)) (x : F (x)) (x : G(x)) 61. Prdikatenlogik - Einige Regeln x : F (x) x : F (x) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) = y x : F (x, y ) x : F (x) x : F (x) x : F (x) x : F (x) x : (F (x) G(x)) (x : F (x)) (x : G(x)) x : (F (x) G(x)) (x : F (x)) (x : G(x)) 62. Prdikatenlogik - Einige Regeln x : F (x) x : F (x) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) = y x : F (x, y ) x : F (x) x : F (x) x : F (x) x : F (x) x : (F (x) G(x)) (x : F (x)) (x : G(x)) x : (F (x) G(x)) (x : F (x)) (x : G(x)) 63. Prdikatenlogik - Einige Regeln x : F (x) x : F (x) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) = y x : F (x, y ) x : F (x) x : F (x) x : F (x) x : F (x) x : (F (x) G(x)) (x : F (x)) (x : G(x)) x : (F (x) G(x)) (x : F (x)) (x : G(x)) 64. Prdikatenlogik - Einige Regeln x : F (x) x : F (x) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) y x : F (x, y ) xy : F (x, y ) = y x : F (x, y ) x : F (x) x : F (x) x : F (x) x : F (x) x : (F (x) G(x)) (x : F (x)) (x : G(x)) x : (F (x) G(x)) (x : F (x)) (x : G(x)) 65. Mengenlehre Unter einer Menge verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten m unserer Anschauung oder unseres Denkens (welche die Elemente von M genannt werden) zu einem Ganzen (Cantor, 1895) Doch: Die Menge aller Mengen, die sich nicht selbst enthalten (Russelsche Antinomie) 66. Mengenlehre Unter einer Menge verstehen wir jede Zusammenfassung M von bestimmten wohlunterschiedenen Objekten m unserer Anschauung oder unseres Denkens (welche die Elemente von M genannt werden) zu einem Ganzen (Cantor, 1895) Doch: Die Menge aller Mengen, die sich nicht selbst enthalten (Russelsche Antinomie) 67. Mengenlehre Grundlegendes Prdikat ist das Elementprdikat , z. B. 1N Menge werden mit geschweiften Klammern geschrieben. Elemente knnen aufgezhlt werden, z. B. M = {1, Auto, Hugo, 10003, . . . } Bildung von Mengen durch Prdikate. Sei D eine Denitionsmenge und P ein Prdikat, dann kann man eine Menge durch M = {x D|P(x)} denieren Trifft die Aussage P(x) auf kein Element zu, hat man die leere Menge 68. Mengenlehre Grundlegendes Prdikat ist das Elementprdikat , z. B. 1N Menge werden mit geschweiften Klammern geschrieben. Elemente knnen aufgezhlt werden, z. B. M = {1, Auto, Hugo, 10003, . . . } Bildung von Mengen durch Prdikate. Sei D eine Denitionsmenge und P ein Prdikat, dann kann man eine Menge durch M = {x D|P(x)} denieren Trifft die Aussage P(x) auf kein Element zu, hat man die leere Menge 69. Mengenlehre Grundlegendes Prdikat ist das Elementprdikat , z. B. 1N Menge werden mit geschweiften Klammern geschrieben. Elemente knnen aufgezhlt werden, z. B. M = {1, Auto, Hugo, 10003, . . . } Bildung von Mengen durch Prdikate. Sei D eine Denitionsmenge und P ein Prdikat, dann kann man eine Menge durch M = {x D|P(x)} denieren Trifft die Aussage P(x) auf kein Element zu, hat man die leere Menge 70. Mengenlehre Grundlegendes Prdikat ist das Elementprdikat , z. B. 1N Menge werden mit geschweiften Klammern geschrieben. Elemente knnen aufgezhlt werden, z. B. M = {1, Auto, Hugo, 10003, . . . } Bildung von Mengen durch Prdikate. Sei D eine Denitionsmenge und P ein Prdikat, dann kann man eine Menge durch M = {x D|P(x)} denieren Trifft die Aussage P(x) auf kein Element zu, hat man die leere Menge 71. Mengenlehre Zwei Mengen heien gleich, wenn sie dieselben Elemente enthalten Die Anzahl der Elemente einer Menge M, ist die Mchtigkeit der Menge, notiert |M| Teilmenge: M N x : (x M x N) Echte Teilmenge: MN =M N M =N 72. Mengenlehre Zwei Mengen heien gleich, wenn sie dieselben Elemente enthalten Die Anzahl der Elemente einer Menge M, ist die Mchtigkeit der Menge, notiert |M| Teilmenge: M N x : (x M x N) Echte Teilmenge: MN =M N M =N 73. Mengenlehre Zwei Mengen heien gleich, wenn sie dieselben Elemente enthalten Die Anzahl der Elemente einer Menge M, ist die Mchtigkeit der Menge, notiert |M| Teilmenge: M N x : (x M x N) Echte Teilmenge: MN =M N M =N 74. Mengenlehre Zwei Mengen heien gleich, wenn sie dieselben Elemente enthalten Die Anzahl der Elemente einer Menge M, ist die Mchtigkeit der Menge, notiert |M| Teilmenge: M N x : (x M x N) Echte Teilmenge: MN =M N M =N 75. Mengenlehre Mengenoperationen Schnittmenge: M N = {x|x M x N} Vereinigungsmenge: M N = {x|x M x N} Differenzmenge: MN = {x|x M x N} / Potenzmenge: (M) = {N|N M} Kartesisches Produkt: M N = {(x, y )|x M x N} 76. Mengenlehre Mengenoperationen Schnittmenge: M N = {x|x M x N} Vereinigungsmenge: M N = {x|x M x N} Differenzmenge: MN = {x|x M x N} / Potenzmenge: (M) = {N|N M} Kartesisches Produkt: M N = {(x, y )|x M x N} 77. Mengenlehre Mengenoperationen Schnittmenge: M N = {x|x M x N} Vereinigungsmenge: M N = {x|x M x N} Differenzmenge: MN = {x|x M x N} / Potenzmenge: (M) = {N|N M} Kartesisches Produkt: M N = {(x, y )|x M x N} 78. Mengenlehre Mengenoperationen Schnittmenge: M N = {x|x M x N} Vereinigungsmenge: M N = {x|x M x N} Differenzmenge: MN = {x|x M x N} / Potenzmenge: (M) = {N|N M} Kartesisches Produkt: M N = {(x, y )|x M x N} 79. Mengenlehre Mengenoperationen Schnittmenge: M N = {x|x M x N} Vereinigungsmenge: M N = {x|x M x N} Differenzmenge: MN = {x|x M x N} / Potenzmenge: (M) = {N|N M} Kartesisches Produkt: M N = {(x, y )|x M x N} 80. Mengenlehre Mengenoperationen Schnittmenge: M N = {x|x M x N} Vereinigungsmenge: M N = {x|x M x N} Differenzmenge: MN = {x|x M x N} / Potenzmenge: (M) = {N|N M} Kartesisches Produkt: M N = {(x, y )|x M x N} 81. Mengenlehre Vereinung und Schnitt von Mengen sind assoziativ, kommutativ und distributiv A B = B A, A B = B A (Kommutativgesetz) A (B C) = (A B) C, A (B C) = (A B) C (Assoziativgesetz) A (B C) = (A B) (A C), A (B C) = (A B) (A C) (Distributivgesetz) 82. Mengenlehre Vereinung und Schnitt von Mengen sind assoziativ, kommutativ und distributiv A B = B A, A B = B A (Kommutativgesetz) A (B C) = (A B) C, A (B C) = (A B) C (Assoziativgesetz) A (B C) = (A B) (A C), A (B C) = (A B) (A C) (Distributivgesetz) 83. Mengenlehre Vereinung und Schnitt von Mengen sind assoziativ, kommutativ und distributiv A B = B A, A B = B A (Kommutativgesetz) A (B C) = (A B) C, A (B C) = (A B) C (Assoziativgesetz) A (B C) = (A B) (A C), A (B C) = (A B) (A C) (Distributivgesetz) 84. Mengenlehre Vereinung und Schnitt von Mengen sind assoziativ, kommutativ und distributiv A B = B A, A B = B A (Kommutativgesetz) A (B C) = (A B) C, A (B C) = (A B) C (Assoziativgesetz) A (B C) = (A B) (A C), A (B C) = (A B) (A C) (Distributivgesetz) 85. Relationen und Funktionen Eine Relation R zwischen zwei Mengen ist eine Teilmenge des Kartesischen Produktes R M N Eine quivalenzrelation ist eine Relation R M M, fr die gilt x M (x, x) R (Reexiv) (x, y ) R (y , x) R (Symmetrisch) (x, y ) R (y , z) R (x, z) R (Transitiv) 86. Relationen und Funktionen Eine Relation R zwischen zwei Mengen ist eine Teilmenge des Kartesischen Produktes R M N Eine quivalenzrelation ist eine Relation R M M, fr die gilt x M (x, x) R (Reexiv) (x, y ) R (y , x) R (Symmetrisch) (x, y ) R (y , z) R (x, z) R (Transitiv) 87. Relationen und Funktionen Eine Relation R zwischen zwei Mengen ist eine Teilmenge des Kartesischen Produktes R M N Eine quivalenzrelation ist eine Relation R M M, fr die gilt x M (x, x) R (Reexiv) (x, y ) R (y , x) R (Symmetrisch) (x, y ) R (y , z) R (x, z) R (Transitiv) 88. Relationen und Funktionen Eine Relation R zwischen zwei Mengen ist eine Teilmenge des Kartesischen Produktes R M N Eine quivalenzrelation ist eine Relation R M M, fr die gilt x M (x, x) R (Reexiv) (x, y ) R (y , x) R (Symmetrisch) (x, y ) R (y , z) R (x, z) R (Transitiv) 89. Relationen und Funktionen Eine Relation R zwischen zwei Mengen ist eine Teilmenge des Kartesischen Produktes R M N Eine quivalenzrelation ist eine Relation R M M, fr die gilt x M (x, x) R (Reexiv) (x, y ) R (y , x) R (Symmetrisch) (x, y ) R (y , z) R (x, z) R (Transitiv) 90. Relationen und Funktionen Eine Relation F X Y heit Funktion, falls jedem Element aus X genau ein Element aus Y zugeordnet wird: (x, y ) F (x, z) F y = z SchreibweiseF :X Yx y X heit Denitionsbereich, Y Wertebereich, F (X ) Bild von F. Funktionsgraph: (F ) = {(x, F (x)) M N} 91. Relationen und Funktionen Eine Relation F X Y heit Funktion, falls jedem Element aus X genau ein Element aus Y zugeordnet wird: (x, y ) F (x, z) F y = z SchreibweiseF :X Yx y X heit Denitionsbereich, Y Wertebereich, F (X ) Bild von F. Funktionsgraph: (F ) = {(x, F (x)) M N} 92. Relationen und Funktionen Eine Relation F X Y heit Funktion, falls jedem Element aus X genau ein Element aus Y zugeordnet wird: (x, y ) F (x, z) F y = z SchreibweiseF :X Yx y X heit Denitionsbereich, Y Wertebereich, F (X ) Bild von F. Funktionsgraph: (F ) = {(x, F (x)) M N} 93. Relationen und Funktionen Eine Relation F X Y heit Funktion, falls jedem Element aus X genau ein Element aus Y zugeordnet wird: (x, y ) F (x, z) F y = z SchreibweiseF :X Yx y X heit Denitionsbereich, Y Wertebereich, F (X ) Bild von F. Funktionsgraph: (F ) = {(x, F (x)) M N} 94. Relationen und Funktionen Eine Funktion heit injektiv, falls jedes Element aus M ein anderes Element aus N zugeordnet wird. F (x) = F (y ) x = y Eine Funktion heit surjektiv, falls der Wertebereich ausgeschpft wird. y Y x X : F (x) = y Eine Funktion heit bijektiv, falls sie injektiv und surjektiv ist. Es existiert eine eineindeutige Beziehung zwischen den Mengen. Dann gibt es eine Umkehrfunktion F 1 : Y X mit F 1 (F (x)) = x 95. Relationen und Funktionen Eine Funktion heit injektiv, falls jedes Element aus M ein anderes Element aus N zugeordnet wird. F (x) = F (y ) x = y Eine Funktion heit surjektiv, falls der Wertebereich ausgeschpft wird. y Y x X : F (x) = y Eine Funktion heit bijektiv, falls sie injektiv und surjektiv ist. Es existiert eine eineindeutige Beziehung zwischen den Mengen. Dann gibt es eine Umkehrfunktion F 1 : Y X mit F 1 (F (x)) = x 96. Relationen und Funktionen Eine Funktion heit injektiv, falls jedes Element aus M ein anderes Element aus N zugeordnet wird. F (x) = F (y ) x = y Eine Funktion heit surjektiv, falls der Wertebereich ausgeschpft wird. y Y x X : F (x) = y Eine Funktion heit bijektiv, falls sie injektiv und surjektiv ist. Es existiert eine eineindeutige Beziehung zwischen den Mengen. Dann gibt es eine Umkehrfunktion F 1 : Y X mit F 1 (F (x)) = x