UE 7 (-> Do 11.6.)

Mathematik fu
¨ r Informatiker 2 – SoSe 2015
Dr. Hartwig Bosse
Blatt 7
Abgabe: Do 11.06.’15, 14:05 Uhr
¨
Dies ist Version 1 dieses Ubungsblattes.
Hinweis: Bei den geforderten Beweisen geht es unter anderem um formale Korrektheit. Ein Beispiel
oder eine Zeichnung gen¨
ugen nicht.
Aufgabe 7.1
2 Punkte
Beweisen Sie dass f¨
ur Mengen A, B, C stets gilt: (A ∪ B) \ C = (A \ C) ∪ (B \ C).
• F¨
uhren Sie dabei zwei Einzelbeweise f¨
ur “⊆” und “⊇”.
• Begr¨
unden Sie bei jede Ihrer Umformungen mit einer Rechenregel im Skript, Version 3.0.
Aufgabe 7.2
4 Punkte
Seien A, B Mengen und P(A) bezeichne die Potenzmenge einer Menge A, d.h. P(A) ist die Menge, die
alle Teilmengen von A enth¨
alt.
Beweisen Sie: P(A ∩ B) = P(A) ∩ P(B)
Aufgabe 7.3
4 Punkte
Geben Sie f¨
ur die folgenden Relationen an ob sie jeweils . . .
i) reflexiv sind
oder nicht.
iii) transitiv sind
ii) symmetrisch sind oder nicht.
Beweisen Sie Ihre Aussagen die Transitivit¨at betreffend.
oder nicht.
a) Ra := {(n, m) ∈ N × N : (n teilt m)}
b) Rb := {(n, m) ∈ N × N : (n teilt m) oder (m teilt n)}
c) Sei K die Mengen aller Kreise in R2 .
Rc := {(g, h) ∈ K × K : g schneidet h}
(Zwei Kreise schneiden sich, wenn sie mindestens einen Punkt gemeinsam haben.)
Aufgabe 7.4
Es sei A := {(n, m) ∈ N × N : n = m − 7} eine Relation auf N.
¨
a) Geben Sie die (inklusionsm¨
aßig) kleinste Aquivalenzrealtion
R an, mit A ⊆ R.
¨
b) Wieviele echt verschiedene Aquivalenzklassen
hat R?
Tipp: Notieren oder zeichnen Sie A und R zun¨achst f¨
ur kleine m, n.
Homepage der Veranstaltung:
http://www.math.uni-frankfurt.de/~bosse/mafi
4 Punkte
Blatt 7
Mathematik fu
¨ r Informatiker 2 – SoSe 2015
Aufgabe 7.5 (Zusatzaufgabe).
2 Bonus-Punkte
Beim Teilen einer Zahl durch 13 kann ein Rest u
¨brigbleiben, z.B. gilt 29 = 2 · 13 + 3, der Rest ist hier 3.
F¨
ur m ∈ N mit Rest n beim Teilen durch 13 gilt: m = k · 13 + n mit k, n ∈ N und einem Rest 0 ≤ n < 13.
Nehmen Sie an, die Zahl a habe beim Teilen durch 13 den Rest 4 und b habe den Rest 3.
• Welchen Rest hat a + b bzw. a · b beim Teilen durch 13?
(. . . und wieso ist dies so?)
• Welche Reste h¨
atten sich ergeben wenn a und b beide beim Teilen durch 13 den Rest 4 h¨
atten?
Geben Sie jeweils einen Beweis f¨
ur Ihre Aussage an.
Homepage der Veranstaltung:
http://www.math.uni-frankfurt.de/~bosse/mafi

Download Report