Mengenlehre
Definition
Eine Zusammenfassung von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unserem Denkens zu einem Ganzen.
Notation
Sonderzeichen: ∈, ∉, ≡, ∀, ∃, ∅, ⋂, ⋃, ⋀ , ⋁, ¬, →, ↔
https://de.wikipedia.org/wiki/Unicodeblock_Mathematische_Operatoren
a ∈ M "A ist Element von M"
A = B <=> [∀x : x ∈ A <=> x ∈B ]
Darstellung durch Auflistung
M = {1; 2; 3; 4; 5}
Doppelte Aufzählung wird ignoriert
Die Reihenfolge ist egal
Beispiel:
M = {1; 2; 3; 8; 8} = {1; 2; 3; 3; 2; 8} = {1; 2; 3; 5}
∅ = Leere Menge
Unendliche Mengen
M = {3; 6; 9; 12; 15; 18;...}
Darstellung durch Eigenschaften
U = {x | P (x)} M ist die Menge aller x, die das Prädikat P(x) erfüllt.
Impliziert ein zugrundeliegendes Universum!
M = {x ∈ U | P (x)}
P(x): x ist gerade
U = Z
M = {x ∈ Z : P(x)} = Menge der geraden Zahlen
Sei M eine Menge dann ist Pow(M) oder Pot(M) oder Sonderzeichen das wie aussieht: P(M) die Potenzmenge von M
Pot (M) = die Menge aller Teilmengen von M
Beispiel: M = {1; 2; 3}
Pot(M) = {∅, {1}, {2}, {3}, {1; 2}, {2; 3}, {1; 3}, {1; 2; 3}, M}
Operationen auf Mengen
A, B = Mengen
Vereinigung
A ⋃ B "A vereinigt B"
= {x | x ∈ A ⋁ x ∈ B }
Schnitt
A ⋂ B "A geschnitten B"
= {x | x ∈ A ⋀ x ∈ B }
Differenz
A \ B "A minus B"
= {x | x ∈ A ⋀ x ∉ B }
Komplement
_
A "Komplement von A"
= { x ∉ A }
Sätze
Absorption
x ⋁ (x ⋀ y) ≡ x
Diese Identität gilt auch automatisch für Mengen!
M ⋃ (M ⋃ N) = M
{ x | x ∈ M ⋀ x ∈ N } ≡ { x | (x ∈ M) ⋁ (x ∈ M ⋀ x ∈ N) } ≡ { x | x ∈ M} ≡ M
Negation
¬ ( x ⋀ y ) ≡ ¬ x ⋁ ¬ y
_ _
A ⋂ B = A ⋃ B
//To be continued...
Mengen
09.10.12
A ist Teilmenge von B genau dann, wenn a ∈ A => a ∈ B
Notation: A ⊆ B, A ⊂ B
A ⊊ B <=> A ⊆ B ∧ A ≠ B
Teilmengenrelation ist transitiv
A ⊆ B ∧ B ⊆ C => A ⊆ C
Zwei Mengen A und B heißen desjunkt
A ∩ B = ∅
Satz: Seien A,B,C Mengen, dann gilt:
A ⋃ B = B ⋃ A
A ∩ B = B ∩ A Kommutativiität
(A ∩ B) ∩ C = A ∩ (B ∩ C)
(A ⋃ B) ⋃ C = A ⋃ (B ⋃ C) Assoziativität
A ∩ (B ⋃ C) = (A ∩ B) ⋃ (A ∩ C)
A ⋃ (B ∩ C) = (A ⋃ B) ∩ (A u C) Distributivität
A ⋃ A = A
A ∩ A = A Idempotenz
A ⋃ U = U
A ⋂ ∅ = ∅ Dominanz
A ⋃ ∅ = A
A ⋂ U = A Identität
A ⋃ (A ⋂ B) = A
A ⋂ (A ⋃ B) = A Absorption
_____ _ _
A ⋃ B = A ⋂ B
A ⋂ B = A ⋃ B de Morgan'sche Regel
_
A ⋃ A = U
A ⋂ A = ∅ _
//hier fehlt noch die doppelte Negation; = A
A \ B = A ⋂ B
09.10.12 (Nachmittag)
Beispiel
Satz
Sei M eine Menge mit n Elementen, dann ist Pot(M) (Potenzmenge) eine Menge mit 2^n Elementen.
Beweis mittels Induktion
M = ∅ Pot(M) = {∅}
M = { a } Pot(M) = {∅, {a} }
M = {a,b} Pot(M)= {∅,{a},{b},{a,b}}
=> Pot(M) verdoppelt sich, wenn wir ein Element zu M hinzufügen.
M = {a,b,c} Pot(M) = {∅,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}
P1 = {∅,{a},{b},{a,b}
P2 = {{c},{a,c},{b,c},{a,b,c}}
Wir definieren P1 = { x ∈ Pot(M) | c ∉ x }
P1 = { x ∈ Pot(M) | c ∈ x }
Induktionsanfang: (Den haben wir vorher schon gemacht)
Induktionsvoraussetzung: Satz gilt für Mengen der Größe k.
Induktionsbehauptung: Satz gilt für Mengen der Größe (k+1).
Induktionsschluss: P1, P2 wie oben definiert
P1 hat 2^k viele Elemente nach Induktionsvoraussetzung
denn P1=Pot(M\{c})
Es bleibt zu zeigen P1 und P2 haben gleich viele Elemente.
x ∈ P1 und sehen x ⋃ {c} ∈ P2
x ≠ y ∈ P1 dann gilt für x ⋃ {c} und y ⋃ {c}
diese beiden sind verschieden!!!
=> P2 hat mindestens so viele Elemente wie P1
//Lustige Zeichnung mit komischen Hinkelsteinen
Für jedes Element x ∈ P2 gilt, dass
y=x\{c} ∈ P1 und es gilt natürlich y ⋃ {c} (≤ oder =) x // WTF
=> Daraus folt, dass P1 und P2 gleich viele Elemente haben
Ferner ist P1⋂P2=∅
und es gilt Pot(M) hat 2^n Elemente aus P1, 2^k Elemente aus P2 also insgesamt 2^(k+1)
Darstellung von Mengen mit Venn-Diagrammen
Gegeben eine Menge ausgedrückt mit den üblchen Mengenoperratoren. Markieren sie die entsprechende Fläche im Venn-Diagramm.
_________
A ⋂ B, A ⋃ (B\C), ((A ⋃ B) ⋂ C))
_ _
(C ⋂ A) usw.
//Bilder
Bild 1:
A ⋂ B ⋂ C
Bild 2:
A⋂B
Bild 3:
((A⋃B)\C)⋃((B⋂C)\A)
Bild4:
C\(A⋃B)
Bild5:
C⋂(A⋃B)
Bild6:
(A⋂B)⋃(C⋂(A⋃B))
Bild7
(A⋂C)⋃(A⋂B)⋃(B⋂C)
impliziert, dass U=A⋃B⋃C
Sonderzeichen: ∈, ∉, ≡, ∀, ∃, ∅, ⋂, ⋃, ⋀ , ⋁, ¬, →, ↔, ☇, √, ∤, |, ≥, ≤, ≠
Übungen zu Mengen
Aufgabenteil 1
Aufgabe 1
B\(A⋂B)=B\A
Aufgabe 2
A\B
Aufgabe 3
B ⋂ A
Aufgabe 4
E⋂B
Aufgabe 5
[( C ⋂ E ) \ B] ⋃ [( C ⋂ B) \ E]
Aufgabenteil 2
Aufgabe 1
:
(A ⋂ E) = Bücher von A, die Kaminer gelesen hat.
Aufgabe 2
:
(B \ D) = Tolkien Bücher die ein Jahr nach dem Zeitpunkt "ein Jahr nach vor dem Erscheinen von Herr der Ringe" erschienen sind.
(B ⋂ D) = Tolkien Bücher, die mindestens ein Jahr vor dem Erscheinen von "Herr der Ringe" erschienen sind.
Aufgabe 3
:
(B ⋃ D) \ C = (Alle Bücher von Tolkien) und (alle Bücher, die mindestens ein Jahr vor "Herr der Ringe" erschienen sind, außer Kriminalromane)
= alle Bücher die von Tolkien geschrieben wurden oder ein Jahr vor "Herr der Ringe" erschienen sind. Die aber keine Kriminalromane sind.
Übung:
A ⋃ B = {