close

Вход

Забыли?

вход по аккаунту

ООО «ВОРОТА ТЮМЕНИ» АЛЮТЕХ Центр Тюмень Сервисный;pdf

код для вставкиСкачать
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№01
Aufgabe 1. Welche der folgenden Aussagen sind wahr?
1. Genau eine Behauptung auf dieser Liste ist falsch.
2. Genau zwei Behauptungen auf dieser Liste sind falsch.
3. Genau drei Behauptungen auf dieser Liste sind falsch.
4. Genau vier Behauptungen auf dieser Liste sind falsch.
5. Genau f¨
unf Behauptungen auf dieser Liste sind falsch.
6. Genau sechs Behauptungen auf dieser Liste sind falsch.
7. Genau sieben Behauptungen auf dieser Liste sind falsch.
8. Genau acht Behauptungen auf dieser Liste sind falsch.
9. Genau neun Behauptungen auf dieser Liste sind falsch.
10. Genau zehn Behauptungen auf dieser Liste sind falsch.
¨
Andert sich etwas, wenn die Bedingung “Genau” weggelassen wird?
Aufgabe 2. Inspektor D befragt drei Verd¨achtige – A, B und C – f¨
ur eine Tat. Er weiß,
daß genau eine der drei Personen schuld ist und jede Person einmal l¨
ugt und einmal die
Wahrheit sagt.
A sagt: Ich war es nicht. B hat es getan.
B sagt: Ich war es nicht. Ich weiß, daß C es getan hat.
C sagt: Ich war es nicht. B weiß nicht wer es war.
Ist eindeutig feststellbar, wer es getan hat? Wenn ja, wer war es?
Aufgabe 3. Auf einem entfernten Planeten sagen Mathematiker immer die Wahrheit und
Physiker immer die Unwahrheit. Untersuche die folgenden Situationen und stelle fest, wer
Mathematiker und wer Physiker ist.
(a) A sagt: “B ist ein Mathematiker.”
B sagt: “A ist kein Mathematiker.”
(b) A sagt: “B ist ein Mathematiker.”
B sagt: “A ist ein Physiker.”
Aufgabe 4. (a) Schreibe das gesamte griechische Alphabet eigenh¨andig (in Groß- und
Kleinschreibung).
¨
(b) L¨ose das Memoryspiel von der Internetseite der Ubung
in m¨oglichst kurzer Zeit.
(c) Benenne die folgenden Symbole und finde jeweils alle, die nicht im griechischen Alphabet vorkommen.
αβγ
①ξπζ ∅χωℵ
ϑηλϕκ℘ψ∈υv∂ θφδν µ
ABΓΛ∇MΥNΦΠΣTX
1
❳∆ΞEHKΩΨ
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№02
Aufgabe 5. Bestimme die Wahrheitstafeln der folgenden logischen Aussageformen und
stelle fest, ob sie ¨aquivalent sind.
(a) (¬A → B) → C
(b) ¬A → (B → C)
Aufgabe 6. Formalisiere folgende Aussagen mittels Aussagenlogik.
• Von A, B und C gilt genau eines.
• Von A, B und C gelten genau zwei.
• Von A, B und C gilt mindestens eines.
Aufgabe 7. Formalisiere die folgenden Schl¨
usse und stelle jeweils fest, ob sie korrekt
sind.
(a) Wer in der Stadt wohnt, darf keinen Diesel fahren. Siegfried f¨ahrt einen Diesel, daher
wohnt Siegfried nicht in der Stadt.
(b) Wenn die Begleitmusik stimmt, dann l¨aßt Uwe mit sich reden. Uwe l¨aßt nicht mit sich
reden, daher stimmt die Begleitmusik nicht.
(c) Wenn Josef gr¨oßer ist als Werner, dann ist Frank kleiner als Arnold. Wenn Josef und
Susi gleich groß sind, dann ist Josef gr¨oßer als Werner. Frank ist nicht kleiner als
Arnold, daher sind Josef und Susi nicht gleich groß.
(d) Wenn ich Kopfweh habe, bin ich nerv¨os. Wenn ich Kopfweh habe, brauche ich ein
Aspirin. Ich bin nerv¨os, also brauche ich ein Aspirin.
Aufgabe 8. Bestimme alle paarweise nicht-¨aquivalenten Aussageformen, die aus den
Variablen A und B sowie dem Junktor → (Implikation) aufgebaut werden k¨onnen.
Aufgabe 9. (a) Lies den Monolog des Mephistopheles (Verse 1908–1941 aus Goethes
Faust I ).
(b) Formalisiere die Verse 1928–1933 und bringe sie auf m¨oglichst kompakte Form. Letztere lauten:
Der Philosoph, der tritt herein
Und beweist Euch, es m¨
ußt so sein:
Das Erst w¨ar so, das Zweite so,
Und drum das Dritt’ und Vierte so;
Und wenn das Erst’ und Zweit’ nicht w¨ar,
Das Dritt’ und Viert’ w¨ar nimmermehr.
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№03
Aufgabe 10. Zeige durch Induktion, daß
n
n
3
k =
k=1
2
k
k=1
Aufgabe 11. Zeige anhand eines Beispiels, daß die Aussagen
P (a) → B
(P (a) → B)
und
a∈A
a∈A
im Allgemeinen nicht ¨aquivalent sind.
¨
Aufgabe 12. Sei A eine nichtleere Menge. Zeige die folgenden Aquivalenzen:
(a)
P (a) ∧ B
⇔
a∈A
(P (a) ∧ B)
a∈A
(b)
P (a)
a∈A
→B
⇔
(P (a) → B)
a∈A
Aufgabe 13. Sei A eine Menge mit n Elementen. Zeige, daß die Potenzmenge 2n Elemente
besitzt.
Aufgabe 14. Die symmetrische Differenz zweier Mengen wurde definiert als A B :=
{x : x ∈ A ∨˙ x ∈ B}. Zeige (anhand von Venndiagrammen und durch formale Logik):
(a) A (B C) = (A B) C
(b) A B = (A \ B) ∪ (B \ A)
(c) A B = (A ∪ B) \ (A ∩ B)
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№04
Aufgabe 15. Was ist falsch am folgenden Induktionsbeweis der Aussage:
“F¨
ur alle n ∈ N gilt: je n Punkte der Ebene liegen auf einer Geraden”.
Induktionsanfang: Die Aussage gilt f¨
ur n = 1 und n = 2.
Induktionsschritt: Angenommen, die Aussage ist f¨
ur n wahr. Seien P1 , P2 , . . . , Pn+1
Punkte. Nach Induktionsvoraussetzung liegen die Punkte P1 , P2 , . . . , Pn auf einer
Geraden g und P1 , P2 , . . . , Pn−1 , Pn+1 auf einer Geraden h. Da aber sowohl g als
auch h durch die Punkte P1 und P2 verlaufen, gilt g = h und P1 , P2 , . . . , Pn+1 liegen
auf einer Geraden.
Aufgabe 16. Untersuche, ob die folgenden Relationen R ⊆ A × A reflexiv, symmetrisch, transitiv, antisymmetrisch, konnex oder asymmetrisch sind. Welche Relationen
¨
¨
sind Aquivalenz-,
welche Ordnungsrelationen? Bestimme ggf. die Aquivalenzklassen
und
ein Repr¨asentantensystem.
(i) X = N0 , Relation: mRn ⇐⇒ ∃k ∈ N : k < m ∧ k < n.
(ii) X = R2 , Relation: (x1 , x2 )R(y1 , y2 ) ⇐⇒ x2 ≤ y2 .
(iii) X = R2 , Relation: (x1 , x2 )R(y1 , y2 ) ⇐⇒ x1 ≤ y1 ∧ x2 ≤ y2 .
(iv) X = {a, b, c}, R = {(a, a), (a, b), (b, a), (b, b), (c, c)}.
(v) X = N, Relation: xRy ⇐⇒ x − y = 2.
(vi) X beliebig, Relation: xRy ⇐⇒ x = y.
(vii) X = N, Relation: mRn ⇐⇒ 2 | (m · n).
¨
Aufgabe 17. Sei A = {1, 2, 3, 4}. Bilde die kleinste Aquivalenzrelation
auf A, die die
Elemente (1, 3) und (4, 3) enth¨alt.
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№05
Aufgabe 18. Sei X eine Menge und Z ⊆ P(X) eine Partition. Zeige, daß durch
x ∼ y : ⇐⇒
x∈A∧y ∈A
A∈Z
¨
eine Aquivalenzrelation
definiert wird, sodaß X/∼ = Z.
Aufgabe 19. Seien f : X → Y und g : Y → Z Abbildungen. Zeige:
(a) Wenn f und g injektiv sind, dann auch g ◦ f .
(b) Wenn f und g surjektiv sind, dann auch g ◦ f .
Gilt jeweils auch die Umkehrung? (Beweis oder Gegenbeispiel!).
Aufgabe 20. Seien X und Y Mengen und f : X → Y eine Funktion. Zeige, daß durch
x ∼ y : ⇐⇒ f (x) = f (y)
¨
eine Aquivalenzrelation
auf X definiert wird und daß die Funktion
f : X/∼ → Y
[x] → f (x)
wohldefiniert und injektiv ist.
Aufgabe 21. Sei X = {a, b, c}. Bestimme alle bijektiven Abbildungen f : X → X und
darunter alle Paare (f, g) sodaß f ◦ g = g ◦ f .
Aufgabe 22. Zeige, daß durch
(x, y) ∼ (u, v) : ⇐⇒ x − y = u − v
¨
eine Aquivalenzrelation
auf R2 definiert wird. Bestimme die Faktormenge R2 /∼ und interpretiere sie geometrisch.
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№06
Aufgabe 23. Wieviele ungerade Zahlen zwischen 1000 und 9999 haben lauter verschiedene Ziffern?
Aufgabe 24. Beweise durch kombinatorische Argumente:
2n
n
(a)
=2
+ n2
2
2
n
n−k
n
m
(b)
=
k
m−k
m
k
m
n
n−k
n
(c)
= 2m
k
m−k
m
k=0
Aufgabe 25. Auf wieviele Arten kann man k Personen auf n in einer Reihe stehende
St¨
uhle so verteilen, daß keine zwei direkt nebeneinander sitzen?
Aufgabe 26. An einem Turnier nehmen n Spieler teil und jeder tritt gegen jeden anderen
genau einmal an. F¨
ur einen Sieg erh¨alt ein Spieler 3 Punkte, f¨
ur ein Unentschieden 1
Punkt. Die Platzierung ergibt sich aus den erzielten Punkten, bei Punktgleichheit wird
gelost. Wie viele Punkte hat f¨
ur allgemeines k der k-Platzierte mindestens?
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№07
Aufgabe 27. Sei M eine Menge mit 6 Elementen und R ⊆ M × M eine symmetrische
Relation. Zeige, daß es stets 3 Elemente x, y, z ∈ M gibt, f¨
ur welche
{(x, y), (x, z), (y, z)} ⊆ R
oder
{(x, y), (x, z), (y, z)} ∩ R = ∅
gilt.
Aufgabe 28. Ein Fixpunkt einer Abbildung f : X → X ist ein Element x ∈ X, sodaß
f (x) = x. Bestimme die Anzahl der bijektiven Abbildungen f : X → X, die keinen
einzigen Fixpunkt besitzen, wobei |X| = n.
Hinweis: Inklusion-Exklusion.
Aufgabe 29. Seien X und Y Mengen mit |X| = n und |Y | = n − 3.
(a) Bestimme die Anzahl aller injektiven Funktionen von Y nach X.
(b) Zeige, daß die Anzahl aller surjektiven Funktionen von X nach Y gegeben ist durch
n!(n − 2)(n − 3)2
48
Aufgabe 30. Zeige, daß die Folge Bn der Anzahl der Mengenpartitionen einer n-elementigen
Menge die Rekursion
n
n
Bn+1 =
Bk
k
k=0
erf¨
ullt.
Aufgabe 31. Sei n = pk. Bestimme die Anzahl der Mengenpartitionen von {1, 2, . . . , n},
sodaß alle Klassen k Elemente enthalten.
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№08
Aufgabe 32. Auf wieviele unterschiedliche Arten kann man die Buchstaben des Wortes
ABRAKADABRA so anordnen, daß die doppelt vorkommenden Buchstaben nicht jeweils
alle nebeneinanderstehen (d.h., die beiden B und R voneinander getrennt und die f¨
unf A
nicht alle hintereinander)?
Aufgabe 33. Bestimme die Anzahl der k-elementigen Teilmengen der Menge {1, 2, . . . , n},
in denen keine zwei aufeinanderfolgenden Zahlen enthalten sind.
Aufgabe 34. Zeige, daß
n
mn =
Sn,k mk
k=0
Hinweis: Zu jeder Funktion f : X → Y gibt es eine surjektive Funktion f¯ : X → f (X).
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№09
Aufgabe 35. Berechne ggT(144, 89) mit dem euklidischen Algorithmus.
Aufgabe 36. Seien n1 , n2 , . . . , nk ∈ Z, nicht alle gleich 0. Zeige:
k
ai ni : a1 , a2 , . . . , ak ∈ Z} ∩ N)
ggT(n1 , n2 , . . . , nk ) = min({
i=1
Aufgabe 37. Seien a ≥ 2, m, n ∈ N. Zeige, daß ggT(am − 1, an − 1) = aggT(m,n) − 1.
Aufgabe 38. Seien a, b, c ∈ Z Zeige: Wenn a|bc und ggT(a, b) = 1, dann gilt a|c.
Aufgabe 39. Seien a, b, c ∈ Z mit (a, b) = (0, 0) und d = ggT(a, b). Wir betrachten die
Gleichung
ax + by = c
Zeige:
(a) Die Gleichung besitzt eine ganzzahlige L¨osung genau dann, wenn d|c.
(b) Sei (x0 , y0 ) eine L¨osung, dann haben alle anderen L¨osungen die Form (x0 +k db , y0 −k ad )
f¨
ur ein k ∈ Z.
Hinweis: Aufgabe 38.
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№10
Aufgabe 40. F¨
ur n ∈ N und p ∈ P sei vp (n) = max{k : pk |n}, dann gilt n =
Zeige:
(a) ggT(m, n) = p∈P pmin(vp (m),vp (n))
(b) kgV(m, n) = p∈P pmax(vp (m),vp (n))
(c) ggT(m, n) · kgV(m, n) = m · n
p∈P
pvp (n) .
Aufgabe 41. Zeige: Es gibt unendlich viele Primzahlen p mit p ≡ 3 mod 4.
Aufgabe 42. Zeige die Elferprobe: Eine Zahl n ∈ Z ist genau dann durch 11 teilbar,
wenn die alternierende Quersumme durch 11 teilbar ist, d.h., mit der Ziffernentwicklung
n=
ai 10i
ist n durch 11 teilbar genau dann, wenn
ai (−1)i
durch 11 teilbar ist.
Aufgabe 43. Sei p eine Primzahl. Wir erweitern die Funktion vp (n) = max{k : pk |n}
(f¨
ur n ∈ Z∗ := Z \ {0}; vp (0) := ∞) auf die rationalen Zahlen Q∗ := Q \ {0}, indem wir
setzen
= vp (m) − vp (n)
vp m
n
Zeige:
(a) vp ist wohldefiniert.
(b) vp (rs) = vp (r) + vp (s) f¨
ur alle r, s ∈ Q∗
(c) Sind r, s ∈ Q∗ und r + s = 0, dann ist vp (r + s) ≥ min(vp (r), vp (s)) mit Gleichheit,
wenn vp (r) = vp (s).
(d) F¨
ur r ∈ Q∗ gilt r ∈ Z genau dann, wenn vp (r) ≥ 0 f¨
ur alle p ∈ P.
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№11
Aufgabe 44. (a) Zeige:
a ≡ b mod m1
∧
a ≡ b mod m2
=⇒
a ≡ b mod m
wobei m = kgV(m1 , m2 ).
(b) Folgere daraus, daß die L¨osung des Kongruenzgleichungssystems
x ≡ c1 mod m1
x ≡ c2 mod m2
..
.
x ≡ cn mod mn
eindeutig ist modulo m = m1 m2 · · · mn , wenn ggT(mi , mj ) = 1 f¨
ur i = j.
Aufgabe 45. Berechne 231 mod 900.
Hinweis: Rechne modulo der Primfaktoren (900 = 4 · 9 · 25) und ermittle das Endresultat
mit dem chinesischen Restsatz.
Aufgabe 46. L¨ose, wenn m¨oglich, die folgenden Gleichungssysteme. Ist der chinesische
Restsatz anwendbar?
x ≡ 2 mod 3
x ≡ 1 mod 5
(a) x ≡ 2 mod 9
(b) x ≡ 3 mod 9
x ≡ 1 mod 10
x ≡ 2 mod 10
Aufgabe 47. Berechne ohne Taschenrechner in Z50
[3](2
Hinweis: Berechne zun¨achst 232 mod ϕ(50).
32 )
Diskrete Mathematik (NAWI)
WS2014
¨
Ubungsblatt
№12
Aufgabe 48. Zu einem Diffie-Hellman-Schl¨
usselaustausch seien folgende Daten bekannt:
g=3
m = 54
p = 113
n = 42
Bestimme wenn m¨oglich die geheimen Parameter a, b und den Schl¨
ussel r!
Aufgabe 49. Sei m = pq mit p, q ∈ P. Zeige, daß es f¨
ur beliebiges r mit ggT(r, ϕ(m)) = 1
ein s ∈ N gew¨ahlt werden kann, sodaß rs ≡ 1 mod ϕ(m).
Aufgabe 50. Von der Zahlenfolge
(455, 1001, 2666, 2305)
ist bekannt, daß sie mit dem RSA-Algorithmus mit o¨ffentlichem Schl¨
ussel
(m = 2701, r = 1111)
verschl¨
usselt wurde. Die Buchstaben sind mit der Konvention
aa 0 ba 26 . . . za 650
ab 1 bb 27 . . .
..
.
az 25 bz 51 . . .
zz 675
aus der Vorlesung kodiert.
Finde den privaten Schl¨
ussel s und entschl¨
ussle die Nachricht.
Hinweis: F¨
ur einen Teil der Berechnungen ist wahrscheinlich ein Computer erforderlich.
Aufgabe 51. Zeige, daß in einem ungerichteten Graphen G die Relation
x R y ⇐⇒ ∃ Weg von x nach y
¨
eine Aquivalenzrelation
ist. Welche Relation erh¨alt man, wenn man “Weg” durch “Pfad”
ersetzt?
Aufgabe 52. Zwei Graphen G1 und G2 heißen isomorph, wenn es eine bijektive Abbildung
f : V (G1 ) → V (G2 ) zwischen beiden Knotenmengen gibt, sodaß [x, y] ∈ E(G1 ) ⇐⇒
[f (x), f (y)] ∈ E(G2 ). Isomorphe Graphen werden miteinander identifiziert.
Bestimme alle nicht-isomorphen Graphen mit n = 2, 3, oder 4 Knoten (nicht-zusammenh¨angende Graphen miteingeschlossen).
Aufgabe 53. Die Gradfolge eines Graphen ist die Folge der Grade der einzelnen Knoten
in absteigender Ordnung. Ist es m¨oglich, Graphen (ohne Schleifen und Mehrfachkanten)
mit den folgenden Gradfolgen zu konstruieren?
(a) (3, 3, 3, 3)
(b) (1, 2, 3, 4)
(c) (3, 3, 3, 2, 1)
(d) (1, 1, 1, 1, 1)
1/--страниц
Пожаловаться на содержимое документа