Chr. Nelius  Mathematik für Informatiker I (WS 2000/01)  Musterlösungen

Übungsblatt 1

Aufgabe 1

In dieser Aufgabe werden weitere Regeln für das Rechnen mit Ungleichungen aufgestellt. Beim Beweis dürfen nur solche Regeln benutzt werden, die in der Vorlesung als Grundregeln aufgestellt oder darauf basierend bewiesen wurden. Andere Regeln, die (vielleicht noch aus der Schulzeit) bekannt sind, dürfen nicht benutzt werden.

(a) Behauptung: 0 < x < y ⟹ x^{−1} > y^{−1} > 0

Beweis. 0 < x < y bedeutet 0 < x und x < y. Da < transitiv ist, folgt insbesondere auch 0 < y. Als ersten Schritt beweisen wir: x > 0 ⟹ x^{−1} > 0. Dazu gehen wir indirekt vor: Annahme: x^{−1} ≤ 0. (1) Da x > 0 ist, können wir wegen O_{M}) die Ungleichung (1) mit x multiplizieren.

x^{−1} ≤ 0 | · x ⟹ 1 = x^{−1} x ≤ 0 · x = 0 ⟹ 1 ≤ 0 Dies ist aber ein Widerspruch, da 1 > 0 gilt. Folglich ist die Annahme falsch und unsere erste Behauptung bewiesen. Wegen x^{−1} > 0 folgt mit (1.8a) ii):

x < y | · x^{−1} ⟹ x · x^{−1} < y · x^{−1} ⟹ 1 < y · x^{−1} Nach dem ersten Schritt gilt auch y^{−1} > 0, so daß wir wieder mit (1.8a) ii) schließen können.

1 < yx^{−1} | · y^{−1} ⟹ y^{−1} = y^{−1} · 1 < y^{−1} (yx^{−1} ) = (y^{−1} y)x^{−1} = 1 · x^{−1} = x^{−1} Also gilt y^{−1} < x^{−1} , und das war zu zeigen.

Bemerkung: Die Voraussetzung 0 < x < y ist erforderlich: −3 < −2, aber −1/3 > −1/2 Fazit: Geht man in einer Ungleichung zwischen positiven reellen Zahlen zu den inversen Elementen über, so dreht sich das Ungleichheitszeichen um.

(b) Behauptung: x < y ∧ w < z ⟹ x + w < y + z.

Beweis. Die folgenden Überlegungen basieren auf (1.8a), i) und iii):

\begin{matrix}x < y | + w ⟹ x + w < y + w \\ w < z | + y ⟹ y + w < y + z \end{matrix} \} ⟹ x + w < y + z

Damit ist die Behauptung bewiesen.

Fazit: Strikte Ungleichungen dürfen addiert werden.

(c) Behauptung: x ≥ 0, y ≥ 0, x^{2} ≤ y^{2} ⟹ x ≤ y

Beweis. 1. Fall: x = 0 oder y = 0. Hier folgt die Behauptung unmittelbar. Die Voraussetzung im 1. Fall ist von der Form A ∨ B. Die Negation hiervon ist dann ¬A ∧ ¬B (Regel von de Morgan). Also:

2. Fall: x > 0 und y > 0. Wir führen einen indirekten Beweis. Die Negation der Behauptung x ≤ y ist dann x > y. Wir benutzen wieder (1.8). Annahme: x > y.

\begin{matrix}x > y | · x ⟹ x^{2} = x · x > y · x \\ x > y | · y ⟹ y · x > y · y = y^{2} \end{matrix} \} ⟹ x^{2} > y^{2}

Damit erhalten wie einen Widerspruch zu unserer Voraussetzung x^{2} ≤ y^{2}.

Bemerkung: Die Voraussetzung x ≥ 0, y ≥ 0 ist erforderlich: Für x = −3 und y = −4 gilt zwar x^{2} = (−3)^{2} = 9 ≤ 16 = (−4)^{2} = y^{2}, aber x = −3 > −4 = y.

Fazit: Aus einer Ungleichung zwischen nichtnegativen Zahlen darf auf beiden Seiten die Wurzel gezogen werden (dies entspricht dem Übergang von x^{2} nach x):

x ≥ 0, y ≥ 0, x ≤ y ⟹ \sqrt{x}≤ \sqrt{y}.

(d) Behauptung: 0 < x < y ⟹ x^{2} < y^{2}

Beweis. Wir führen wieder einen indirekten Beweis: Annahme: x^{2} ≥ y^{2} (Dies ist die Negation von x^{2} < y^{2}) Nach dem Aufgabenteil c) (wir dürfen dieses Ergebnis jetzt benutzen, da wir es gerade bewiesen haben!) folgt x ≥ y im Widerspruch zu unserer Voraussetzung x < y.

Bemerkung: Die Voraussetzung 0 < x < y ist erforderlich: Es gilt zwar −3 < −2, aber (−3)^{2} = 9 > 4 = (−2)^{2}. Fazit: Eine Ungleichung zwischen positiven reellen Zahlen darf quadriert werden.

Aufgabe 2

(a) Zu zeigen: Für alle x ∈ ℝ gilt: ⌊−x⌋ = −⌈x⌉

Beweis. Setze m:= ⌊−x⌋ . Dann ist nach Satz (1.10) m ≤ −x < m + 1 . Multiplikation mit −1 liefert −m ≥ x > −(m + 1) = −m − 1 . Nach Satz (1.11) ist dann −m = ⌈x⌉ . ⟹ ⌊−x⌋ = m = −⌈x⌉ .

(b) Zu zeigen: Für alle x ∈ ℝ,n ∈ ℤ gilt: ⌊x + n⌋ = ⌊x⌋+ n .

Beweis. Setze m:= ⌊x + n⌋, dann ist nach (1.10) m ≤ x + n < m + 1 . Durch Addition von −n erhält man m − n ≤ x < m − n + 1 . Also ist m − n = ⌊x⌋ und somit ⌊x + n⌋ − n = m − n = ⌊x⌋ . Addition von nauf beiden Seiten liefert schließlich ⌊x + n⌋ = ⌊x⌋+ n .

(c) Behauptung: Die Formel ⌊n · x⌋= ⌊x⌋· n ist nicht für alle x ∈ ℝ,n ∈ ℤ richtig.

Beweis. Gegenbeispiel: n = 5,x = \frac{1}{2} :

⌊5 · \frac{1}{2}⌋= ⌊ \frac{5}{2}⌋ = 2
5 · ⌊ \frac{1}{2}⌋= 5 · 0 = 0

Aber 0 ≠ 2 , also ⌊5 · \frac{1}{2}⌋≠ 5 · ⌊\frac{1}{2}⌋.

(d) Zu zeigen: Für a,b ∈ ℝ gilt: Die Anzahl der ganzen Zahlen in ]a,b[ist ⌈b⌉− ⌊a⌋− 1 .

Beweis. Zunächst ein kleines Bild zur Veranschaulichung des Aussage für a = 2.2, b = 10.7 :

2  3  4  5  6  7  8  9  10 11 a  b \begin{matrix} \\ ⌊a⌋ \end{matrix}  \begin{matrix} \\ ⌈b⌉ \end{matrix}

Sei n ∈]a,b[eine ganze Zahl. Es gilt

a < n ⟹ ⌊a⌋≤ a < n ⟹ ⌊a⌋+ 1 ≤ n
n < b ⟹ n < b ≤ ⌈b⌉⟹ n ≤ ⌈b⌉− 1

und damit ⌊a⌋+ 1 ≤ n ≤ ⌈b⌉− 1. (2) Seien x,y ∈ ℤ mit x ≤ y. Die Anzahl der ganzen Zahlen im abgeschlossenen Intervall [x,y]ist y − x + 1 ; denn: x + 0,x + 1,x + 2,... ,x + (y − x) ∈ [x,y] sind alle ganzen Zahlen in [x,y].

Mit (2) folgt für die Anzahl der ganzen Zahlen in ]a,b[:

⌈b⌉− 1 − (⌊a⌋+ 1) + 1 = ⌈b⌉− 1 − ⌊a⌋− 1 + 1 = \underline{⌈b⌉− ⌊a⌋− 1} .

Aufgabe 3

Gesucht ist die Zahl der Bits (= Stellen, die jeweils 0 oder 1 sein können), die benötigt werden, um n = 76543210 darzustellen. Nach (1.13) ist die Zahl der Binärstellen von n gleich ⌊log_{2}(n)⌋+ 1 . (Dabei ist log_{2}(n) = \frac{ln(n)}{ln(2)} , wobei lnder natürliche Logarithmus, also zur Basis e = 2.71828... , ist.) Wir erhalten ⌊log_{2}(n)⌋+ 1 = ⌊26.18977107...⌋+ 1 = 26 + 1 = 27, benötigen also 27 Stellen, um nbinär darzustellen.

n = (76543210)_{10} = (100100011111111010011101010)_{2}

Übungsblatt 2

Aufgabe 4

Zu zeigen: Für x ∈ ℝ gilt: ⌈x⌉− ⌊x⌋= \{ \begin{matrix}1 & falls x ∉ ℤ \\ 0 & sonst. \end{matrix}

Beweis. 1. Fall: x ∈ ℤ. Dann ist ⌊x⌋= ⌈x⌉= x und somit ⌈x⌉− ⌊x⌋= 0 .

2. Fall: x ∉ ℤ. Nach (1.11) gilt n = ⌈x⌉⟺ n − 1 < x ≤ n . Wegen x ∉ ℤ, muß n ≠ x gelten, und die Ungleichung verschärft sich zu n − 1 < x < n . Addition von 1 liefert n < x + 1 < n + 1 , nach (1.10) und Übungsaufgabe 2c folgt n = ⌊x + 1⌋ = ⌊x⌋+ 1 . Also ist ⌊x⌋= ⌈x⌉+ 1 ⟹ ⌈x⌉− ⌊x⌋= 1 .

Aufgabe 5

Zu zeigen: Die Dreiecksungleichung |x + y| ≤ |x|+ |y| .

Beweis. 1. Fall: x + y ≥ 0 . Dann ist |x + y| = x + y ≤ |x|+ |y| . Die letzte Ungleichung folgt aus x ≤ |x| und y ≤ |y| (1.15d).

2. Fall: x + y < 0 . Nach der Definition von |·| gilt jetzt |x + y| = −(x + y) = (−x) + (−y) ≤ |−x|+ |−y| = |x|+ |y|.

Hier haben wir (1.15d) und (1.15c) benutzt. Wir haben also gezeigt:

Für alle x,y ∈ ℝ : |x + y| ≤ |x|+ |y|.

Aufgabe 6

Zu zeigen: P ∧ Q ⟹ P ist allgemeingültig, also (P ∧ Q ⟹ P) ⟺ W .

Beweis. Wir stellen die Wahrheitstafel für P ∧ Q ⟹ P auf:

\begin{matrix}P & Q & P ∧ Q & P ∧ Q ⟹ P \\ W & W & W & W \\ W & F & F & W \\ F & W & F & W \\ F & F & F & W \end{matrix}

und sehen, daß die Formel für alle Belegungen von P und Q wahr ist. Und so kann man das formal nachrechnen:

((P ∧ Q) ⟹ P) ⟺ ¬(P ∧ Q) ∨ P  nach (2.4c)
⟺ (¬P ∨ ¬Q) ∨ P  nach (2.3f)
⟺ (¬P ∨ P) ∨ (¬Q)  nach (2.3d,e)
⟺ W ∨ (¬Q)  nach (2.3a)
⟺ W  nach Definition von ∨

Wir erhalten also auch hier (P ∧ Q ⟹ P) ⟺ W .

Aufgabe 7

Das Symbol | wird auch nand genannt, also nicht und. (a)

\begin{matrix}A & B & ¬(A ∧ B) \\ W & W & F \\ W & F & W \\ F & W & W \\ F & F & W \end{matrix}

(b) (i) Zu zeigen: A|Aist logisch äquivalent zu ¬A, also A|A ⟺ ¬A

Beweis. A|A ⟺ ¬(A ∧ A) ⟺ ¬A , denn A ∧ A ⟺ A .

(ii) Zu zeigen: (A|B)|(A|B) ⟺ A ∧ B .

Beweis. (A|B)|(A|B) ⟺^{(i)} ¬(A|B) ⟺^{Def.} ¬¬(A ∧ B) ⟺ A ∧ B .

(c) Gesucht ist eine zu (A ⟹ B) äquivalente Formel, in der nur | vorkommt. Wir wissen (A ⟹ B) ⟺ (¬A ∨ B) . Die Formel für | liefert uns

(A|B) ⟺ ¬(A ∧ B) ⟺ (¬A ∨ ¬B). Um die richtige Formel zu erhalten, müssen wir also noch B negieren. Nach Teil b(i) dieser Aufgabe kann dies durch (B|B)erreicht werden, und wir erhalten:

(A|(B|B)) ⟺^{Def.} ¬(A ∧ (B|B)) ⟺^{b(ii)} ¬(A ∧ ¬B) ⟺ (¬A ∨ B) ⟺ (A ⟹ B).

Aufgabe 8

Es ist das Archimedische Axiom mit Hilfe von Quantoren zu formulieren:

∀x ∈ ℝ ∃n ∈ ℕ : n > x Die Negation liefert:

∃x ∈ ℝ ∀n ∈ ℕ : n ≤ x man sieht, daß die Quantoren “umklappen”, und die Aussage (rechts von “:”) negiert wird.

Übungsblatt 3

Aufgabe 9

(a) Die Menge der Buchstaben des Wortes “Mathematik” ist {M,a,t,h,e,m,i,k}oder – wenn man Groß-/Kleinschreibung nicht berücksichtigt –: {m,a,t,h,e,i,k}. Wie man sieht, kommt ein Element in einer Menge nur einmal vor. Dabei spielt die Reihenfolge der Buchstaben in der Menge keine Rolle.

(b) Gesucht ist eine intensionale Darstellung der Menge M = {1,2,4,8,16,32,...}, also mit Hilfe eines geeigneten Prädikates. Man sieht leicht, daß die Elemente von M gerade die Zweierpotenzen sind: 1 = 2^{0}, 2 = 2^{1}, 4 = 2^{2}, ... . Damit erhält man M = {x x ∈ ℕ,∃n ∈ ℕ_{0} : x = 2^{n} } .

(c) Seien M, Nund Pdie Mengen der gazzahligen Vielfachen von 6, 8 bzw. 48. Gesucht sind Beschreibungen der Mengen mit Prädikaten.

M= {x x ∈ ℤ ∧ ∃k ∈ ℤ: x = k · 6}
N= {y y ∈ ℤ ∧ ∃k ∈ ℤ: y = k · 8}
P= {z z ∈ ℤ ∧ ∃k ∈ ℤ: z = k · 48 }

Es gilt M ∩ N ≠ P, denn 24 = 4 · 6 = 3 · 8 ∈ M ∩ N , aber 24 ∉ P.

Aufgabe 10

(a)

M  N P N ∩ P  M\(N ∩ P)  M  N P M\P M\N  (M\N) ∪ (M\P)

(b) Zu zeigen: M\(N ∩ P) = (M\N) ∪ (M\P).

Beweis. Um die Gleichheit zu zeigen, muß folgendes nachgerechnet werden:

∀x: x ∈ M\(N ∩ P) ⟺ x ∈ (M\N) ∪ (M\P). Dazu betrachten wir ein beliebiges x:

x ∈ M\(N ∩ P)⟺ x ∈ M ∧ x ∉ (N ∩ P)  (Definition von \)
⟺ x ∈ M ∧ ¬(x ∈ N ∧ x ∈ P)
⟺ x ∈ M ∧ (x ∉ N ∨ x ∉ P)  (de Morgan)
⟺ (x ∈ M ∧ x ∉ N) ∨ (x ∈ M ∧ x ∉ P)  (Distributivgesetz)
⟺ x ∈ (M\N) ∨ x ∈ (M\P)
⟺ x ∈ (M\N) ∪ (M\P)

Aufgabe 11

(a) Die Veranschaulichung von M\(M\N):

M\(M\N) M\N M  N

Die Vermutung: M\(M\N) = M ∩ N.

(b) Zu zeigen: M\(M\N) = M ∩ N. Beweis. Wir betrachten ein beliebiges Element x:

x ∈ M\(M\N)⟺ x ∈ M ∧ ¬x ∈ (M\N)  (Definition von \)
⟺ x ∈ M ∧ ¬(x ∈ M ∧ x ∉ N)
⟺ x ∈ M ∧ (x ∉ M ∨ x ∈ N)  (de Morgan)
⟺ (\underbrace{x ∈ M ∧ x ∉ M}_{⟺F}) ∨ (x ∈ M ∧ x ∈ N)  (Distributivgesetz)
⟺ x ∈ M ∧ x ∈ N  (F ∨ A ⟺ A)
⟺ x ∈ M ∩ N  (Definition von ∩)

Aufgabe 12

Sei M = {1,2}, gesucht ist P(P(M)). Zunächst bestimmen wir P(M) = {∅,{1},{2},{1,2}}, und erhalten:

P(P(M)) = {∅, {∅}, {{1}}, {{2}}, {{1,2}},

{∅,{1}}, {∅,{2}}, {∅,{1,2}}, {{1},{2}}, {{1},{1,2}}, {{2},{1,2}}, {∅,{1},{2}}, {∅,{1,2},{2}}, {∅,{1},{1,2}}, {{1},{2},{1,2}},

{∅,{1},{2},{1,2}} }

Es sind genau 16 Elemente.

Aufgabe 13

Gegeben sind die zwei Mengen

U:= {(x,y) (x,y) ∈ ℤ × ℤ, 20 ≤ x ≤ 40, 10 ≤ y ≤ 20 }
V:= {(x,y) (x,y) ∈ ℤ × ℤ, 30 ≤ x ≤ 50, 5 ≤ y ≤ 15 }

(a) Zunächst eine graphische Veranschaulichung:

[figure: 20; 40; 50; 10; 20; U; V; U ∩ V; U\V]

Wie man schon an der Graphik sieht, ist V ⊈ U, z.B. ist (50,5) ∈ V, aber (50,5) ∉ U. Die Menge U kann dargestellt werden als:

U = {20,21,22,... ,39,40} × {10,11,12,... ,19,20} und man sieht, daß U 21 · 11 = 321 Elemente hat.

(b) Die Schnittmenge berechnet sich – wie man an der Graphik schon sieht – zu U ∩ V = {(x,y) (x,y) ∈ ℤ × ℤ, 30 ≤ x ≤ 40, 10 ≤ y ≤ 15 }.

Analog ist die Differenzmenge:

U\V ={(x,y) (x,y) ∈ ℤ × ℤ, 20 ≤ x ≤ 30, 10 ≤ y ≤ 20 }
∪ {(x,y) (x,y) ∈ ℤ × ℤ, 30 ≤ x ≤ 40, 15 ≤ y ≤ 20 }.

Übungsblatt 4

Aufgabe 14

Wir betrachten die Relation R ⊆ ℕ × ℕ , die für (m,n),(m′,n′) ∈ ℕ × ℕ definiert ist durch: (m,n)R(m′,n′) :⟺ m ≤ m′∧ n ≤ n′. (3)

(a) Zu zeigen: Rist eine partielle Ordnung auf ℕ × ℕ .

Beweis. Reflexivität: Sei also (m,n) ∈ ℕ × ℕ beliebig gewählt. Dann gilt m ≤ m ∧ n ≤ n , da ≤ reflexiv ist. Also ist wegen (3) (m,n)R(m,n), und damit ist Rreflexiv. Antisymmetrie: Seien (m,n), (m′,n′) ∈ ℕ × ℕ mit (m,n)R(m′,n′)und (m′,n′)R(m,n). Das heißt doch nach (3), daß

m ≤ m′∧ n ≤ n′und m′≤ m ∧ n′≤ n. Da aber ≤ antisymmetrisch ist, folgen m = m′ und n = n′. Zusammengefaßt heißt das: (m,n)R(m′,n′) ∧ (m′,n′)R(m,n) ⟹ m = m′∧ n = n′⟹ (m,n) = (m′,n′) . Das ist aber genau die Definition von antisymmetrisch. Transitivität: Seien (m,n), (m′,n′),(m′′,n′′) ∈ ℕ × ℕ beliebig mit (m,n)R(m′,n′) und (m′,n′)R(m′′,n′′). Dann gelten nach (3):

m ≤ m′∧ n ≤ n′und m′≤ m′′∧ n′≤ n′′. Da ≤ transitiv ist, folgen m ≤ m′′ und n ≤ n′′. Also (m,n)R(n′′,m′′). Wir haben also gezeigt: (m,n)R(m′,n′) ∧ (m′,n′)R(m′′,n′′) ⟹ (m,n)R(n′′,m′′). Damit ist Rtransitiv. Aus den Eigenschaften reflexiv, antisymmetrisch und transitiv folgt, daß R eine partielle Ordnungsrelation ist.

Behauptung: Rist nicht linear.

Beweis. Linearität heißt ∀(m,n),(m′,n′) ∈ ℕ × ℕ : (m,n)R(m′,n′) ∨ (m′,n′)R(m,n) . Es reicht also ein Gegenbeispiel anzugeben: Es gilt (1,2) R̸(2,1) und (2,1) R̸(1,2). Also ist Rnicht linear.

(b) Zu M := {∅,{5},{6},{1,3},{2,3},{1,2,3},{1,3,4},{2,3,4}} ist das Hasse-Diagramm bezüglich der Relation ⊆ aufzustellen:

[figure: ^{•{1,3,4}}; ^{•{1,2,3}}; ^{•{2,3,4}}; ^{{5}•}; ^{•{1,3}}; ^{•{2,3}}; ^{•{6}}; •; ∅]

Wie man sieht, ist ∅ das kleinste Element der Menge, denn ∀x ∈ M : ∅ ⊆ x. Damit ist ∅ auch das einzige minimale Element. Es gibt kein größtes Element; denn ∀x ∈ M ∃y ∈ M : y ⊈ x. Die maximalen Elemente in (M,⊆) sind: {5}, {6}, {1,2,3}, {1,3,4}, {2,3,4}. (M,⊆) ist nicht linear geordnet, denn z.B. {1,3} ⊈ {2,3} und {2,3} ⊈ {1,3} .

Aufgabe 15

Die Relation Rist auf der Menge M = {a,b,c,d,e} durch die untenstehende Tabelle definiert:

\begin{matrix}R & a & b & c & d & e \\ a & 1 & 0 & 1 & 0 & 1 \\ b & 0 & 1 & 0 & 1 & 0 \\ c & 1 & 0 & 1 & 0 & 1 \\ d & 0 & 1 & 0 & 1 & 0 \\ e & 1 & 0 & 1 & 0 & 1 \end{matrix}

(a) Zu zeigen: Rist eine Äquivalenzrelation auf M.

Beweis. Reflexivität: Es gilt ∀x ∈ M : xRx, da in der Hauptdiagonalen nur 1en stehen. Symmetrie: Es gilt ∀x,y ∈ M : xRy ⟹ yRx, da die Tabelle symmetrisch zur Hauptdiagonalen ist. Transitivität: Behauptung: ∀x,y,z ∈ R : xRy ∧ yRx ⟹ xRy. Die Behauptung ist aufgrund der Reflexivität und Symmetrie von Rrichtig, wenn mindestens zwei der x,y,zgleich sind. Es bleibt also der Fall paarweise verschiedener x,y,zzu betrachten. Wir listen nun alle x,y,zauf, für die xRy ∧ yRzgelten kann:

\begin{matrix}x & y & z & xRz & x & y & z & xRz & x & y & z & xRz & x & y & z & xRz \\ a & c & e & 1 & c & e & a & 1 & a & e & c & 1 & d & b & − & − \\ b & d & − & − & e & a & c & 1 & c & a & e & 1 & e & c & a & 1 \end{matrix}

Wie man sieht, ist die Transitivität offensichtlich erfüllt.

(b) Gesucht sind die Äquivalenzklassen [x]_{R}von allen Elementen x ∈ M. Definiert sind die Äquivalenzklassen durch [x]_{R}= {y y ∈ M,xRy}.

[a]_{R}= {a,c,e}  [b]_{R}= {b,d}
[c]_{R}= {a,c,e}  [d]_{R}= {b,d}
[e]_{R}= {a,c,e}  +

Wie man sofort sieht, gelten [a]_{R}= [c]_{R}= [d]_{R}und [b]_{R}= [c]_{R}. Damit ist M/R = {[a]_{R},[b]_{R}} = {{a,c,e}, {b,d}}.

Aufgabe 16

Auf der Menge M = {a,b,c,d} soll eine Relation Rdefiniert werden, die reflexiv und symmetrisch, aber nicht transitiv ist. Dazu definieren wir

\begin{matrix}R & a & b & c & d \\ a & 1 & 1 & 0 & 1 \\ b & 1 & 1 & 1 & 1 \\ c & 0 & 1 & 1 & 1 \\ d & 1 & 1 & 1 & 1 \end{matrix}

R ist reflexiv, da auf der Hauptdiagonalen nur 1en stehen. R ist symmetrisch, da die Tabelle symmetrisch zur Hauptdiagonalen ist. Rist nicht transitiv, denn aRb ∧ bRc, aber a R̸c.

Aufgabe 17

Die Relation Rauf der Menge ℝ × ℝ ist definiert durch:

(x,y)R(x′,y′) :⟺ x − x′= y − y′.

(a) Zu zeigen: Rist eine Äquivalenzrelation auf ℝ × ℝ .

Beweis. Reflexivität: x − x = 0 = y − y ⟹ (x,y)R(x,y) . Symmetrie: (x,y)R(x′,y′) ⟹ x − x′= y − y′ . Multipliziert man diese Gleichung mit (−1) , so erhält man −(x − x′) = −(y − y′) ⟹ x′− x = y′− y ⟹ (x′,y′)R(x,y) . Transitivität: Es gelte, (x,y)R(x′,y′)und (x′,y′)R(x′′,y′′). Damit gelten x − x′= y − y′ und x′− x′′= y′− y′′ . Addiert man beide Gleichungen, so erhält man

\underbrace{(x − x′) + (x′− x′′)}_{=x−x′′} = \underbrace{(y − y′) + (y′− y′′)}_{y−y′′}.

also (x,y)R(x′′,y′′).

(b) Gesucht sind die Äquivalenzklassen von (0,0) und (2,5).

[(0,0)]_{R}= {(x,y) (x,y) ∈ ℝ × ℝ,(x,y)R(0,0)}
= {(x,y) (x,y) ∈ ℝ × ℝ,x − 0 = y − 0 }
= {(x,y) (x,y) ∈ ℝ × ℝ,x = y }
= {(x,x) x ∈ ℝ}
= Δ_{R}⊆ ℝ × ℝ und
[(2,5)]_{R}= {(x,y) (x,y) ∈ ℝ × ℝ,(x,y)R(2,5)}
= {(x,y) (x,y) ∈ ℝ × ℝ,x − 2 = y − 5 }
= {(x,y) (x,y) ∈ ℝ × ℝ,x + 3 = y }
= {(x,x + 3) x ∈ ℝ} ⊆ ℝ × ℝ

Wie man sieht, ist [(0,0)]_{R}eine Gerade durch (0,0) mit Steigung 1. [(2,5)]_{R}ist eine Gerade durch (2,5) mit Steigung 1. Grafische Veranschaulichung:

[figure: •(2,5); •; (0,0); [2,5]_{R}; [0,0]_{R}]

Übungsblatt 5

Aufgabe 18

(a) Sei M eine Menge und Z ⊆ P(M) eine Zerlegung von M. Die Relation Rsei für x,y ∈ M definiert durch: xRy:⟺ ∃Z ∈ Z : x ∈ Z ∧ y ∈ Z .

(i) Zu zeigen: Rist eine Äquivalenzrelation auf M.

Beweis. Wir fassen zunächst die Eigenschaften einer Zerlegung zusammen:

1. ∀Z ∈ Z : Z ⊆ M und Z ≠ 0 ,

2. ∀Z,Z′∈ Z : Z ≠ Z′⟹ Z ∩ Z′= ∅ ,

3. M = ⋃ _{Z∈Z} Z.

Reflexivität: Sei x ∈ M beliebig. Dann ist nach 3. x ∈ ⋃ _{Z∈Z} Z und somit x ∈ Z′ für ein Z′∈ Z. Und damit ist x ∈ Z′∧ x ∈ Z′, also xRx. Symmetrie: Seien x,y ∈ M mit xRybeliebig. Dann gibt es nach Definition ein Z′∈ Z mit x ∈ Z′∧ y ∈ Z′. Da ∧ kommutativ ist, folgt y ∈ Z′∧ x ∈ Z′ und somit yRx. Transitivität: Seien x,y,z ∈ M beliebig mit xRyund yRz. Dann gilt: (∃Z ∈ Z : x ∈ Z ∧ y ∈ Z) und (∃Z′∈ Z : y ∈ Z′∧ z ∈ Z′) . Damit ist y ∈ Z ∩ Z′ und nach 2. folgt Z = Z′. Also x ∈ Z ∧ z ∈ Z und damit xRz.

(ii) Gesucht ist die Äquivalenzklasse eines beliebigen Elements. Für x ∈ M ist [x]_{R}= {y y ∈ M, yRx} = {y y ∈ M, ∃Z ∈ Z : x ∈ Z ∧ y ∈ Z } . Wie man aus 2. sieht, gibt es genau ein Z′∈ Z mit x ∈ Z′. Behauptung: [x]_{R}= Z′mit diesem Z′.

Beweis. “⊆ ”: Ist y ∈ [x]_{R}, so gilt xRy ⟹ ∃Z ∈ Z : x ∈ Z ∧ y ∈ Z , damit ist Z = Z′ und y ∈ Z′. “⊇ ”: Gelten y ∈ Z′∧ x ∈ Z′, so gilt yRxund damit y ∈ [x]_{R}.

(b) Gesucht sind alle Äquivalenzrelationen auf M = {a,b,c,d}. Ist Reine Äquivalenzrelation auf M, so ist nach (4.10) M/Reine Zerlegung von M. Umgekehrt bestimmt nach (a) jede Zerlegung Z eine Äquivalenzrelation auf M, deren Äquivalenzklassen gerade die Elemente von Z sind. Um alle Äquivalenzrelationen auf M zu bestimmen, braucht man daher nur alle möglichen Zerlegungen von M zu finden:

|Z| Zerlegungen  #Zerlegungen
1 M  1
2 \begin{matrix}\{\{a\},\{b,c,d\}\}, \{\{b\},\{a,c,d\}\}, \{\{c\},\{a,b,d\}\}, \\ \{\{d\},\{a,b,c\}\} \end{matrix}  4
{{a,b},{c,d}}, {{a,c},{b,d}}, {{a,d},{b,c}}  3
3 \begin{matrix}\{\{a\},\{b\},\{c,d\}\}, \{\{a\},\{c\},\{b,d\}\}, \{\{a\},\{d\},\{b,c\}\}, \\ \{\{b\},\{c\},\{a,d\}\}, \{\{b\},\{d\},\{a,c\}\}, \{\{c\},\{d\},\{a,b\}\} \end{matrix}  6
4 {{a},{b},{c},{d}}  1
Summe  15

Aufgabe 19

(a) Die Abbildung f : {a,b,c,d,e} → {1,2,3,4,5,6,7} ist definiert durch

\begin{matrix}a ↦ 2 & b ↦ 5 & c ↦ 7 \\ d ↦ 3 & e ↦ 5. \end{matrix}

Gesucht ist zu U := {b,c,d,e} die Bildmenge f(U):

f(U) = {f(x) x ∈ U} = {f(b),f(c),f(d),f(e)} = {3,5,7}, zu V := {3,4,5} die Urbildmenge f^{−1} (V):

f^{−1} (V) = {x x ∈ M,f(x) ∈ V} = {x x ∈ M,f(x) ∈ {3,4,5}} = {b,d,e} und zu V′:= {1,2} die Urbildmenge f^{−1} (V′):

f^{−1} (V′) = {x x ∈ M,f(x) ∈ V′} = {x x ∈ M,f(x) ∈ {1,2}} = {a}.

(b) Die Abbildung g: ℤ → ℤ ist definiert durch g(z) = z^{2} für alle z ∈ ℤ. Weiter sind U := {−2,1,0,1,2,3} und V := {−1,3,4,5,9} .

g(U)= {g(−2),g(1),g(0),g(1),g(2),g(3)} = {0,1,4,9}
g^{−1} (U)= {x x ∈ ℤ,g(x) ∈ V} = {−3,−2,2,3}

Aufgabe 20

Gegeben sind die zwei Abbildungen

\begin{matrix}f : ℝ × ℝ & −→ & ℝ & g: ℝ & −→ & ℝ \\ (r,s) & ⟼→ & r − s & x & ⟼→ & x^{3}− x + 1 \end{matrix}

(i) Zu berechnen:

(g ∘ f)((5,2)) = g(f((5,2)) = g(5 − 2) = g(3) = 25
(g ∘ f)((2,5)) = g(f((2,5)) = g(2 − 5) = g(−3) = −24

(ii) Behauptung: (f ∘ g)(2) kann nicht berechnet werden.

Beweis. Die Hintereinanderausführung (f ∘ g) ist nicht definiert, da die Wertemenge ℝ von g nicht mit dem Definitionsbereich ℝ × ℝ von f übereinstimmt.

Aufgabe 21

(a) Behauptung: f : ℕ → ℕ , n ↦ n + 5 ist injektiv aber nicht surjektiv.

Beweis. Injektivität: Sind n,n′∈ ℕ mit f(n) = f(n′) , so gilt n + 5 = n′+ 5 und damit n = n′. Surjektivität: 4 ∈ ℕ besitzt kein Urbild unter f . Annahme: Es gibt ein n ∈ ℕ mit f(n) = 4 = n + 5 . Dann ist n = −1 ∈ ℕ . Dies ist aber ein Widerspruch, da −1 ∉ ℕ .

(b) Behauptung: g: ℝ × ℝ → ℝ , (x,y) ↦ x − y ist surjektiv aber nicht injektiv.

Beweis. Injektivität: Es sind (2,1),(3,2) ∈ ℝ × ℝ und (2,1) ≠ (3,2) . Aber g(2,1) = 2 − 1 = 1 = 3 − 2 = g(3,2) . Damit ist g nicht injektiv. Surjektivität: Sei x ∈ ℝ beliebig, dann ist (x,0) ∈ ℝ × ℝ und g(x,0) = x − 0 = x . Wir können also zu jedem x ∈ ℝ ein Urbild finden. Damit ist g surjektiv.

Übungsblatt 6

Aufgabe 22

Es sei G ⊆ ℕ die Menge der geraden natürlichen Zahlen.

(a) Zu zeigen: G ⊂ ℕ. (Manchmal auch G ⊊ ℕgeschrieben)

Beweis. G ⊂ ℕ heißt ja: G ⊆ ℕ und G ≠ ℕ. Wir haben 1 ∈ ℕ, aber 1 ∉ G. Also kann nicht ℕ = G gelten.

(b) Zu zeigen: Die Abbildung f : ℕ −→ G, n ⟼→ 2 · n ist injektiv und surjektiv (und damit bijektiv).

Beweis. Injektivität: Wir wollen zeigen: ∀n,n′∈ ℕ : f(n) = f(n′) ⟹ n = n′ . Seien also n,n′∈ ℕ mit f(n) = f(n′) beliebig, dann ist 2 · n = 2 · n′und damit n = n′. Surjektivität: Wir wollen zeigen ∀n ∈ G∃m ∈ ℕ : f(m) = n . Sei also n ∈ G beliebig. Dann hat ndie Form 2 · mmit einem m ∈ ℕ, da ngerade. Also ist f(m) = 2 · m = n.

(c) Gesucht ist die Umkehrabbildung g: G −→ ℕ mit f ∘ g = id_{G} und g ∘ f = id_{ℕ} . Behauptung: g: G −→ ℕ,n ⟼→ \frac{n}{2} ist die Umkehrabbildung.

Beweis. Zunächst sind alle n ∈ G gerade und damit ist \frac{n}{2} ∈ ℕ und es gelten: ∀n ∈ ℕ : (g ∘ f)(n) = g(2n) = \frac{2n}{2} = n und ∀n ∈ G : (f ∘ g)(n) = f(\frac{n}{2}) = 2 · \frac{n}{2} = n und damit f ∘ g = id_{G} und g ∘ f = id_{ℕ} .

Aufgabe 23, Caesar

Zunächst setzen wir A:= {A,B,C,D, ...,X,Y,Z} das Alphabet. Die Abbildung φ: A −→ A ist definiert durch:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
| | | | | | | | | | | | | | | | | | | | | | | | | |
D E F G H I J K L M N O P Q R S T U V W X Y Z A B C

(a) Wie sich aus obiger Tabelle ergibt: φ(X) = A,φ(Y) = B,φ(Z) = C .

(b) Wir wenden auf jeden Buchstaben der Worte Veni Vidi Vici die Abbildung φ an und erhalten: YHQLYLGLYLFL.

(c) Aus der obigen Definition von φ ist ersichtlich, daß jedes Element aus A genau ein Urbild unter φ hat. Also ist φ bijektiv. Die Entschlüsselungsfunktion φ^{−1} weist jedem Element von A sein Urbild unter φ zu:

A B C D E F G H I J K L M N O P Q R S T U V W X Y Z
| | | | | | | | | | | | | | | | | | | | | | | | | |
X Y Z A B C D E F G H I J K L M N O P Q R S T U V W

(d) Wende auf jeden Buchtaben des Geheimtextes “GDVLVWHLQIDFK” die Abbildung φ^{−1} an. Dann erhält man: DASISTEINFACH ≃ DAS IST EINFACH.

Aufgabe 24

Es ist durch Induktion zu zeigen:

(a) Für n ∈ ℕ bezeichne s_{n} die Summe aller ungeraden natürlichen Zahlen von 1 bis 2n − 1 . Suche eine Formal für s_{n} in Abhängigkeit von nund beweise diese durch vollständige Induktion. Beobachtung: s_{1} = 1, s_{2} = 4, s_{3} = 9, s_{4} = 14,... Behauptung: s_{n} = n^{2} .

Beweis. Induktionsanfang, n = 1 : s_{1} = 1 = 1^{2} , also ist die Behauptung für n = 1 richtig. Induktionsvoraussetzung: Die Formel gelte für eine bestimmte natürliche Zahl n ∈ ℕ, also s_{n} = n^{2} . Induktionsbehauptung: s_{n+1} = (n + 1)^{2} . Induktionsschritt:

s_{n+1} = 1 + 3 + 5 + ··· + (2n − 1) + (2n + 1) = s_{n}+ (2n + 1)

=^{IV} n^{2}+ (2n + 1) = n^{2}+ 2n + 1 = (n + 1)^{2}.

(b) Für n ∈ ℕ sei t_{n}:= 1 · 2 + 2 · 3 + ··· + n · (n + 1) . Zu zeigen: ∀n ∈ ℕ : t_{n} = \frac{1}{3}n(n + 1)(n + 2) .

Beweis. Induktionsanfang, n = 1 : t_{1} = 1(1 + 1) = 2 = \frac{1}{3}1(1 + 1)(1 + 2) . Also ist die Behauptung für n = 1 richtig. Induktionsvoraussetzung: Die Formel gelte für eine bestimmte natürliche Zahl n ∈ ℕ, also t_{n} = \frac{1}{3}n(n + 1)(n + 2) . Induktionsbehauptung: t_{n+1} = \frac{1}{3}(n + 1)(n + 2)(n + 3) . Induktionsschritt:

t_{n+1} = 1 · 2 + 2 · 3 + ··· + n(n + 1) + (n + 1)(n + 2) = t_{n}+ (n + 1)(n + 2)

=^{IV} \frac{1}{3}n(n + 1)(n + 2) + (n + 1)(n + 2) = (\frac{1}{3}n + 1)((n + 1)(n + 2))

= \frac{1}{3}(n + 3)(n + 1)(n + 2) = \frac{1}{3}(n + 1)(n + 2)(n + 3).

Übungsblatt 7

Aufgabe 25

Die Alle Autos haben die gleiche Farbe-Aufgabe. Wir setzen P(n) :⟺ je n Autos haben die gleiche Farbe. Um die Behauptung der Aufgabenstellung zu zeigen, müßte ein Induktionsbeweis folgendermaßen vorgehen: Induktionsanfang: P(1), also ein Auto hat die gleich Farbe wie es selbst. Induktionsschluß: ∀n ∈ ℕ : P(n) ⟹ P(n + 1) , aber die Argumentation aus der Aufgabenstellung versagt für den Fall n = 2 , da es zwei Autos mit verschiedenen Farben gibt.

Aufgabe 26

Gesucht ist eine Rekursionsgleichung für

a_{n}:= |{x x ∈ {0,1}^{n}, in x kommen keine aufeinanderfolgenden Nullen vor}|. Bis n = 5 geben wir die Zahlen explizit an: n = 1 : 1,0, also a_{1} = 2 . n = 2 : 01,10,11, also a_{2} = 3 . n = 3 : 010,110,011,101,111, also a_{3} = 5 = 2 + 3 . n = 4 : 0110,1010,1110,0101,1101,0111,1011,1111, also a_{4} = 8 = 5 + 3 . n = 5 : 01101,10101,11101,01011,11011,01111,10111,11111,01010,11010,01110,

10110,11110, also a_{5} = 13 = 8 + 5 So kommen wir zu dem Verdacht: ∀n ≥ 3 : a_{n} = a_{n−1} + a_{n−2} , den wir beweisen wollen. Dazu definieren wir zunächst: Eine n-Folge x ∈ {0,1}^{n} heißt zulässig, wenn keine aufeinanderfolgenden Glieder Null sind.

Beweis. Jede n-Folge x ∈ {0,1}^{n} endet entweder mit Null oder mit Eins. Wir haben also zwei Fälle:

1. Fall: Folge endet mit 1, Dann bilden die Glieder davor eine zulässige (n − 1) -Folge, davon gibt es a_{n−1} viele.

2. Fall: Folge endet mit 0, dann darf die Stelle davor nicht 0 sein, also endet die Folge auf 10. Die Glieder davor müssen eine zulässige (n − 2) -Folge sein, davon gibt es a_{n−2} viele.

Damit haben wir die Rekursionsgleichung

a_{1} = 2, a_{2} = 3, a_{n+2} = a_{n+1} + a_{n} für alle n ∈ ℕ bewiesen. Diese Gleichung entspricht der der Fibonacci-Zahlen mit den Anfangswerten F_{3} = a_{1} = 2, F_{4} = a_{2} = 3 und damit a_{n} = F_{n+2} .

Aufgabe 27

Die Zahlen b_{n}, n ∈ ℕ seien rekursiv definiert durch b_{0} := 1, b_{1} := 2, b_{n}:= 2b_{n−1} − b_{n−2} für n ≥ 2 . Die ersten sieben Zahlen sind:

b_{0} = 1, b_{1} = 2, b_{2} = 3, b_{3} = 4, b_{4} = 5, b_{5} = 6, b_{6} = 7, b_{7} = 8. Gesucht ist jetzt eine Formel für die b_{n}. Unsere Vermutung ist: b_{n} = n + 1 für n ≥ 2 .

Beweis. Induktionsanfang: n = 2 : b_{2} = 3 = 2 + 1 und n = 3 : b_{3} = 4 = 3 + 1 . Induktionsvoraussetzung: Sei n ≥ 4 beliebig und die Behauptung richtig für n − 1 und n − 2 , also

b_{n−1} = n und b_{n−2} = n − 1.

Induktionsbehauptung: b_{n} = n + 1 . Induktionsschluß: b_{n} =^{Def.} 2b_{n−1} − b_{n−2} =^{(IV)} 2(n) − (n − 1) = 2n − n + 1 = n + 1 .

Beachte: Da b_{4} = 2b_{3}− b_{2} muß der Induktionsanfang für n = 2 und n = 3 geführt werden. Im Induktionsschluß zeigt man dann “P(n − 1) ∧ P(n − 2) ⟹ P(n) .”

Aufgabe 28 (Türme von Hanoi)

Zunächst vereinbaren wir die Schreibweise A −→^{k} Bfür: Die k-te Scheibe wird von Anach B gelegt. Das Spiel mit einer Scheibe braucht trivialerweise genau einen Zug.

(1) Wir spielen jetzt mit zwei Scheiben: A −→^{1} B, A −→^{2} C, B −→^{1} Cund brauchen drei Züge.

(2) Mit drei Scheiben: A −→^{1} C, A −→^{2} B, C −→^{1} B, A −→^{3} C, B −→^{1} A, B −→^{2} C, A −→^{1} C

und brauchen sieben Züge.

(3) Nach dem dritten Zug haben wir die Situation, eine Scheibe nach Säule C verlagern zu müssen, sowie das Spiel mit zwei Scheiben von B nach C. In den ersten Drei Schritten haben wir das Spiel mit zwei Scheiben von Anach Bgespielt.

(4) Wir wissen s_{1} = 1 und vermuten s_{n} = 2s_{n−1} + 1 für n ≥ 2 .

Beweis. Induktionsanfang: s_{2} = 3 = 2 · 1 + 1 = 2 · s_{1}+ 1 . Induktionsvoraussetzung: Für ein beliebiges n ≥ 2 gelte s_{n} = 2s_{n−1} + 1 . Induktionbehauptung: s_{n+1} = 2s_{n}+ 1 Induktionsschritt: Wir spielen das Spiel mit n + 1 Scheiben. Die oberen n Scheiben lassen sich nach Induktionsvoraussetzung in s_{n} Zügen von Anach Blegen. Dann wird die n + 1 te Scheibe nach C gelegt, und in weiten s_{n} Zügen der Stapel mit n Scheiben von B nach C. Insgesamt erhalten wir so s_{n+1} = s_{n}+ 1 + s_{n} = 2 · s_{n}+ 1 Züge.

(5) Gesucht ist eine geschlossene Formel für s_{n}, also eine Formel, die nich nicht auf s_{n−1} abstützt. Dazu berechnen wir zunächst einige s_{n} explizit:

s_{1} = 1 = 2 − 1 = 2^{1}− 1, s_{2} = 3 = 4 − 1 = 2^{2}− 1,

s_{3} = 7 = 8 − 1 = 2^{3}− 1, s_{4} = 15 = 16 − 1 = 2^{4}− 1, ...

und gelangen so zu der Vermutung s_{n} = 2^{n}− 1 für alle n ≥ 1 .

Beweis. Induktionsanfang s.o. Induktionsvoraussetzung: Für ein ℕ ∋ n ≥ 2 gelte s_{n} = 2^{n}− 1 . Induktionsbehauptung: s_{n+1} = 2^{n+1} − 1 . Induktionsschritt: s_{n+1} = 2 · s_{n}+ 1 =^{IV} 2 · (2^{n−1} − 1) + 1 = 2 · 2^{n−1} − 2 + 1 = 2^{n}− 1

Übungsblatt 8

Aufgabe 29

(a) Zu berechnen: ∑ _{k=0}^{5} k\binom{5}{k}

∑_{k=0}^{5} k\binom{5}{k} = 0\binom{5}{0} + 1\binom{5}{1} + 2\binom{5}{2} + 3\binom{5}{3} + 4\binom{5}{4} + 5\binom{5}{5}

mit 1 = \binom{5}{5} = \binom{5}{0} , 5 = \binom{5}{1} = \binom{5}{5 − 1} = \binom{5}{4} , 10 = \binom{5}{2} = \binom{5}{3}

= 0 · 1 + 1 · 5 + 2 · 10 + 3 · 10 + 4 · 5 + 5 · 1 = 80

(b) Gesucht ist der Koeffizient von x^{14} in dem Ausdruck (1 − 2x^{2})^{10} . Nach dem binomischen Satz (7.11) gilt

(1 − 2x^{2})^{10} = ∑_{k=0}^{10} \binom{10}{k} 1^{10−k}(−2x^{2})^{k} = ∑_{k=0}^{10} \binom{10}{k} (−2x^{2})^{k}.

Den gesuchten Koeffizienten enthält man demzufolge für k = 7:

\binom{10}{7} (−2)^{7} = −\binom{10}{7} 2^{7} = −\binom{10}{3} 2^{7} = −\frac{10 · 9 · 8}{1 · 2 · 3}· 2^{7} = −120 · 2^{7} = −15360

Aufgabe 30

(a) Zu berechnen: ∑ _{k=0}^{n}(−1)^{k}\binom{n}{k} für n ∈ ℕ_{0}. Nach bem binomischen Lehrsatz ist (x + y)^{n} = ∑ _{k=0}^{n} \binom{n}{k}x^{n−k}y^{k} für alle x,y ∈ ℝ und n ∈ ℕ_{0}. Setze nun x:= 1, y:= −1 , und erhalte

∑_{k=0}^{n}(−1)^{k}\binom{n}{k} = ∑_{k=0}^{n} \binom{n}{k} 1^{n−k}(−1)^{k} = (1 + (−1))^{n} = 0^{n}

= \{ \begin{matrix}1 & für n = 0 \\ 0 & für n ≥ 1 \end{matrix} .

(b) Sei M eine endliche Menge mit n ≥ 1 Elementen. Setze

g_{n}:= Anzahl der Teilmengen von M, die gerade Elementzahl haben,
u_{n}:= Anzahl der Teilmengen von M, die ungerade Elementzahl haben.

Zu zeigen: g_{n} = u_{n}.

Beweis. Nach Satz (7.9) ist \binom{n}{k} die Anzahl der k-elementigen Teilmengen einer n-elementigen Menge, d.h.

g_{n} = ∑_{k=0,k gerade}^{n} \binom{n}{k} ,

u_{n}= ∑_{k=0,k ungerade}^{n} \binom{n}{k} .

Weiterhin gilt (−1)^{k} = \{ \begin{matrix}1 & k gerade \\ −1 & k ungerade \end{matrix} .

Aus (a) folgt für n ≥ 1 :

0 = ∑_{k=0}^{n}(−1)^{k}\binom{n}{k} = ∑_{k=0,k gerade}^{n} \binom{n}{k} + ∑_{k=0,k ungerade}^{n}(−1)\binom{n}{k}

= ∑_{k=0,k gerade}^{n} \binom{n}{k} − ∑_{k=0,k ungerade}^{n} \binom{n}{k} = g_{n}− u_{n}

Daraus folgt g_{n} = u_{n}.

Aufgabe 31

Sei M eine endliche Menge mit n Elementen, M = {x_{1},... ,x_{n}}. Gesucht ist die Anzahl z_{n} der Möglichkeiten, M als disjunkte Vereinigung zweier nichtleerer Teilmengen darzustellen. Für 2,3 und 4 geben wir die Möglichkeiten explizit an: n = 2 : {{x_{1}},{x_{2}}}, also z_{2} = 1 . n = 3 : {{x_{1},x_{2}},{x_{3}}}, {{x_{2},x_{3}},{x_{1}}}, {{x_{1},x_{3}},{x_{2}}} , also z_{3} = 3 . n = 4 : Eine 2-Zerlegung von M kann aus einer ein- und einer dreielementigen Teilmenge oder aus zwei zweielementigen Teimengen bestehen: Mit paarweise verschiedenen i,j,k,l ∈ {1,2,3,4} gibt es für

{{x_{i}},{x_{j},x_{k},x_{l}}}vier Möglichkeiten und für
{{x_{i},x_{j}},{x_{k},x_{l}}}drei Möglichkeiten, denn {{x_{i},x_{j}},{x_{k},x_{l}}} = {{x_{k},x_{l}},{x_{i},x_{j}}}

und damit ist z_{4} = 7 . Sei nun n ≥ 2 beliebig, gesucht ist die Anzahl der Zerlegungen von M, also die Anzahl der Mengen

{U,V }, U,V ⊆ M, mit U ≠ ∅ ∧ V ≠ ∅ ∧ U ∪ V = M ∧ U ∩ V = ∅.

Daraus folgt V = M\U. Da U,V beide nichtleer und damit ungleich M sein müssen, gibt es für U insgesamt 2^{n}− 2 Möglichkeiten. Wegen M\(M\U) = U liefern aber U und M\U = V dieselben Zerlegungen, d.h.

z_{n} = \frac{1}{2}(2^{n}− 1) = 2^{n−1} − 1 für alle n ≥ 1.

Aufgabe 32

Es sei M eine endliche Menge und T ⊆ M eine Teilmenge von M.

(a) Zu zeigen: Aus |T |= |M| folgt T = M.

Beweis. M = T ∪ (M\T) ⟹ [(7.4b)]|M|= |T |+ |M\T| ⟹ [|T |= |M| n.V.]|M\T| = 0 und damit ist M\T = ∅, also liegt jedes Element aus M auch in T, d.h. M ⊆ T. Nach Voraussetzung ist aber auch T ⊆ M und damit T = M.

(b) Die Voraussetzung, daß Mendlich sein muß, ist nicht verzichtbar, denn ℕ ⊆ ℤ, |ℕ| = |ℤ| aber ℤ ∋ −1 ∉ ℕ , also ℕ ≠ ℤ .

(c) Es seien M,NMengen und f : M → N eine injektive Abbildung. Zu zeigen: |f(M)| = |M|. (Das gilt auch wenn M nicht endlich ist.)

Beweis. f definiert eine bijektive Abbildung g: M → f(M) , x ↦ f(x). Da f injektiv ist, ist auch g injektiv, nach Definition von f(M) ist g auch surjektiv, also ist g bijektiv. Also M ∼ f(M) und somit |M|= |f(M)| . (Hier wird nirgendwo benutzt, daß M endlich ist.)

(d) Seien M,N endliche Mengen mit |M|= |N|. Zu zeigen: jede injektive Abbildung f : M → N ist bijektiv.

Beweis. Zu zeigen ist, daß f surjektiv ist, also f(M) = N . Es gilt f(M) ⊆ N mit |f(M)| =^{(c)} |M| =^{Vor.} |N|. Nach (a) folgt f(M) = N .

(e) Die Eigenschaft der Endlichkeit von N und M ist nicht verzichtbar, denn f : ℕ → ℕ , n ↦ n + 5 ist injektiv aber nicht surjektiv (siehe Übungsaufgabe 21a) und |ℕ| = ∞ .

Übungsblatt ⋆9⋆

Aufgabe 33 (Weihnachtsmann)

(a) Wieviele Möglichkeiten hat der Weihnachtsmann, einem lieben Studenten vier Geschenke aus einer Liste von 30 zu schenken? Gesucht ist die Anzahl der vierelementigen Teilmengen einer 30-elementigen Menge, wir müssen das Lotto-Problem lösen. Es gibt also \binom{30}{4} Möglichkeiten.

(b) Wieviele Möglichkeiten hat der Weihnachtsmann, seine acht Rentiere anzuspannen, wenn der rotnasige Rudi immer vorne rechts stehen soll? Da Rudis Position immer vorgegeben ist, kann der Weihnachtsmann nur noch die Positionen der anderen sieben Rentiere variieren. Er hat also sieben Plätze und sieben Rentiere, und damit 7! Möglichkeiten.

(c) Der Weihnachtsmann besucht 30 Studenten, und gibt jedem fleißigen Studenten ein Geschenk, jedem faulen keins. Wieviele Geschenkverteilszenarien sind denkbar? Wir kodieren faule Studenten kanonisch als “0”, fleißige als “1”. Damit wird jedes Szenario eindeutig durch eine 30-stellige Binärfolge dargestellt. Hiervon gibt es genau 2^{30} Stück.

(d) Wieviele kürzeste Wege gibt es vom Weihnachtsmann zum Schlitten? Wir sehen uns zunächst einige kürzeste Wege an:

[figure: Weihnachtsmann; Schlitten]

Der Weihnachtsmann kann jedesmal ein Straßenstück nach oben (O) oder nach rechts (R) bis zur nächsten Kreuzung gehen. Bewegungen nach links oder unten sind nicht möglich, denn sie würden einen Umweg bedeuten. Auf jedem kürzesten Weg geht er also acht mal nach rechts und acht mal nach oben. Jeder solche Weg ist durch ein 16 Zeichen langes Wort aus acht mal Ound acht mal Reindeutig beschrieben. Nach Satz (8.4) gibt es hiervon gerade

\binom{16}{8, 8} = \frac{16!}{8! · 8!} = \frac{16!}{8! · (16 − 8)!} = \binom{16}{8} = 12870

viele.

(e) Wieviele Möglichkeiten hat Kevins Schwester, sich zehn Leckereien von einem Teller mit jeweils mindestens zehn Mandarinen, Nüssen und Plätzchen zu nehmen?

Es werden zehn Teile auf die drei Kästen M (Mandarinen), N (Nüsse) und P (Plätzchen) verteilt, d.h. es handelt sich um eine Kombination mit Wiederholung ohne Berücksichtigung der Reihenfolge. Nach Satz (8.13) ist deren Anzahl

C_{W}(3,10) = \binom{3 − 1 + 10}{10} = \binom{12}{10} = \binom{12}{2} = 66.

Aufgabe 34

Auf der Menge A = {a,b,c,... ,y,z} der Buchstaben des Alphabets ist durch die übliche Reihenfolge der Buchstaben eine linerae Ordnung ⪯ definiert (z.B. gilt a ⪯ a, c ⪯ r aber y ⪯̸ n). Wir nennen ein Wort w = w_{1}w_{2}...w_{k} aus den Buchstaben w_{1},... ,w_{k} ∈ A monoton steigend, wenn gilt: ∀i,j ∈ {1,2,...k} : i < j. ⟹ w_{i} ⪯ w_{j}. Es bezeichne a_{k} die Anzahl der monoton steigenden Wörter der Länge k

(a) Gesucht ist a_{k} für k = 1,2,3 jeweils durch explizite Überlegung. Für k = 1 ist klar, daß jedes Wort der Länge eins monoton steigend ist, es gilt also a_{k} = 26 . Für k = 2 bilden wir alle monoton steigenden Wörter, nach Anfangsbuchstaben sortiert:

\begin{matrix}aa, ab, ac, ... ,az & 26 \\ bb, bc, ... ,bz & 25 \\ cc, ... ,cz & 24 \\ ... & ⋮ \\ yy, yz & 2 \\ zz & 1 \end{matrix}

Wir haben also a_{2} = 26 + 25 + ...+ 2 + 1 = ∑ _{i=1}^{26} i = \frac{26·27}{2} . Für k = 3 erhalten wir die Tabelle

\begin{matrix}aaa, aab, aac, ... ,azz & \frac{26·27}{2} \\ bbb, bbc, ... ,bzz & \frac{25·26}{2} \\ ccc, ... ,czz & \frac{24·25}{2} \\ ... & ⋮ \\ zzz & 1 \end{matrix}

Monoton steigende Wörter der Länge drei mit Anfangsbuchstaben a gibt es genau a_{2} viele, mit Anfangsbuchstaben bgenau so viele, wie es monoton steigende Wörter der Länge zwei aus den Buchstaben b,c,... ,zgibt usw.

Damit erhalten wir: a_{3} = ∑ _{i=1}^{26} \frac{i(i+1)}{2} = \frac{1}{2} ∑ _{i=1}^{26} i(i + 1) =^{Aufg. 24b} \frac{26·27·28}{2·3} .

(b) Gesucht ist eine allgemeine Formel für a_{k} für beliebige k ∈ ℕ. Da es bei einer k-Multimenge nicht auf die Reihenfolge der Elemente ankommt, wird jede k-Multimenge, die aus den Buchstaben von A gebildet werden kann, durch ein eindeutig bestimmtes, monoton steigendes Wort beschrieben. Also ist die Anzahl a_{k} der monoton steigenden Wörter aus k Buchstaben vob A gleich der Anzahl der k-Multimengen aus 26 Elementen. Folglich ist nach (8.13):

a_{k} = C_{W}(26,k) = \binom{26 − 1 + k}{k} = \binom{25 + k}{k} .

Für k = 1,2,3 erhalten wir in Übereinstimmung mit (a):

a_{1} = \binom{25 + 1}{1} = \binom{26}{1} = 26
a_{2} = \binom{25 + 2}{2} = \binom{27}{2} = \frac{26 · 27}{2}
a_{3} = \binom{25 + 3}{3} = \binom{28}{3} = \frac{26 · 27 · 28}{2 · 3}.

Übungsblatt 10

Aufgabe 35

Gesucht ist die Wahrscheinlickkeit, daß ein zufälliges Paar (a,b) ∈ {1,... ,10} × {1,... ,10} aus zwei teilerfremden Zahlen a,bbesteht. Zunächst definieren wir

M:= {1,... ,10} × {1,... ,10},
N:= {(a,b) (a,b) ∈ M, ggT(a,b) = 1}.

Die gesuchte Wahrscheinlichkeit ist dann W = \frac{|N|}{|M|}. Um die Mächtigkeit von N zu bestimmen, berechnen wir folgende Werte für a = 1,... ,10 :

s_{a} = |{x x ∈ {1,... ,10}, ggT(a,x) = 1}|. indem wir die Mengen einfach abzählen und erhalten:

\begin{matrix}s_{1} = 10 & s_{2} = 5 & s_{3} = 7 & s_{4} = 5 & s_{5} = 8 \\ s_{6} = 3 & s_{7} = 9 & s_{8} = 5 & s_{9} = 7 & s_{10} = 4 \end{matrix}

Nun ist |N|= a_{1}+ a_{2}+ ...+ a_{10} = 63 und die gesuchte Wahrscheinlichkeit

W = \frac{|N|}{|M|} = \frac{63}{100} = 0.63 = 63%.

Aufgabe 36

Ein Bauer im Lippischen^{1} besitzt einen rechteckigen Acker. Dieser ist 143 Meter lang und 77 Meter breit. Besagter Bauer will diesen Acker rundherum einzäunen. Dazu will er so wenig Pfähle wie möglich verwenden. Alle Pfähle sollen denselben Abstand zueinander haben; hierbei sind nur ganze Meter als Abstand zulässig! Aus Stabilitätsgründen muss an jeder Ecke ein Pfahl eingeschlagen werden. Wieviele Pfähle braucht der Bauer mindestens?

Sei a der Abstand zweier aufeinanderfolgender Pfähle. Nach Aufgabenstellung muß a ∈ ℕ gelten. Da die Pfähle alle gleichen Abstand haben, muß gelten

\begin{matrix}a · s = 77 \\ a · t = 143 \end{matrix} \} ⟹ a 77 ∧ a 143,

da a maximal sein soll, muß also a = ggT(77,143) gelten. Wir benutzen den Euklidischen Algorithmus, um den ggT zu berechnen:

143 = 1 · 77 + 66
77 = 1 · 66 + 11
66 = 6 · 11 + 0  ⟹ 11 = ggT(143,77).

Nun berechnen wir noch s = \frac{77}{a} = \frac{77}{11} = 7 und t = \frac{143}{a} = \frac{143}{11} = 13 . Die Gesamtzahl der benötigten Pfosten ist also 2 · s + 2 · t = 40.

1Die Fragestellung ist auch ohne die Voraussetzung im Lippischen möglich.

Aufgabe 37 (RSA)

(1) Warum sind p = 37 und q = 29 Primzahlen? Durch testen aller Primzahlen kleiner als ⌊\sqrt{p}⌋ bzw. ⌊\sqrt{q}⌋ liefert, daß p,q keine echten Teiler haben.

(2) N = p · q = 37 · 29 = 1073 und M = (p − 1) · (q − 1) = 36 · 29 = 1008 . (3&4) Wähle e = 275 zufällig mit 1 < e < M = 1008 , gesucht ist nun e^{−1} (mod M), dieses wird mit dem Erweiterten Euklidischen Algorithmus berechnet, mit dem wir auch ggT(e,M) = 1 überprüfen.

\begin{aligned}1008 & = 3 · 275 + 183 \\ 275 & = 1 · 183 + 92 \\ 183 & = 1 · 92 + 91 \\ 92 & = 1 · 91 + 1 \\ 91 & = 91 · 1 + 0 \\ ⟹ ggT(1008,275) = 1 \end{aligned}  \begin{matrix}k & 0 & 1 & 2 & 3 & 4 & 5 & 6 \\ r_{k} & 1008 & 275 & 183 & 92 & 91 & 1 & 0 \\ q_{k} & — & 3 & 1 & 1 & 1 & 91 \\ x_{k} & 1 & 0 & 1 & −1 & 2 & −3 \\ y_{k} & 0 & 1 & −3 & 4 & −7 & 11 \end{matrix} ; ⟹ 1 = (−3) · 1008 + 11 · 275 ; ⟹ 11 · 275 ≡ 1 (mod 1)008

So setzen wir d := 11 und erhalten (e,N)als öffentlichen und (d,N)als privaten Schlüssel.

(5) Jetzt soll die verschlüsselte Nachricht y = 1006 entschlüsselt werden: Wir wissen y ≡ m^{275}modN, wobei m die geheime Nachricht ist. Zur Entschlüsselung berechnen wir m = y^{d} = 1006^{11} (mod 1)073 . Dies liefert m = 123. Bemerkung: Um 1006^{11} zu berechnen, benutzen wir die Methode des sukzessiven Quadrierens:

1006^{2} = 1012036 (mod N) = 197
1006^{4} = 197^{2} = 38809 (mod N) = 181
1006^{8} = 181^{2} = 32761 (mod N) = 571
1006^{10} = 571 · 197 = 112487 (mod N) = 895
1006^{11} = 895 · 1006 = 900370 (mod N) = 123

Aufgabe 38

Wandle die Dezimalzahlen a = 141 und b = 152 in Zahlen zur Basis 4 um, addiere und multipliziere diese Zahlen in der Darstellung zur Basis 4 und überprüfe die Ergebnisse, indem du sie wieder in Dezimalzahlen umwandelst und mit den Dezimalzahlen a + b bzw. a · b vergleichst. Zunächst bestimmen wir also nun die Darstellung von a und bzur Basis 4:

\begin{aligned}141 & = 35 · 4 + 1 \\ 35 & = 8 · 4 + 3 \\ 8 & = 2 · 4 + 0 \\ 2 & = 0 · 4 + 2 \\ ⟹ a & = (2031)_{4} \end{aligned}  \begin{aligned}152 & = 38 · 4 + 0 \\ 38 & = 9 · 4 + 2 \\ 9 & = 2 · 4 + 1 \\ 2 & = 0 · 4 + 2 \\ ⟹ b & = (2120)_{4} \end{aligned}

Nun berechnen wir Summe und Produkt:

(2031)_{4} + (2120)_{4} (10211)_{4}  \begin{matrix}(2031)_{4} & ·(2120)_{4} \\ (101220)_{4} \\ (2031 )_{4} \\ (10122 )_{4} \\ (11032320)_{4} \end{matrix}

Die Ergebnisse rechnen wir nun mit Hilfe des Horner-Schemas in die Dezimaldarstellung um:

1 0 2 1  1
4 — 4 16 72 292
1 4 18 73 293
1 1 0 3 2 3 2 0
4 — 4 20 80 332 1336 5356 21432
1 5 20 83 334 1339 5358 21432

Also ist (10211)_{4} = 293 = 141 + 152 , (11032320)_{4} = 21432 = 141 · 152 und unsere Rechnungen waren korrekt.

Übungsblatt 11

Aufgabe 39

(a) Zu zeigen: Jede natürlich Zahl n ∈ ℕ, die weder von 2 noch von 3 geteilt wird. läßt sich n in der Form n = 6k + 1 oder n = 6k − 1 mit einem geeigneten k ∈ ℕ darstellen.

Beweis. Teilt man n mit Rest r durch 6, also n = k · 6 + r so gilt r ∈ {0,... ,5}. Wir betrachten nun die folgenden Fälle: r = 0 ⟹ n = 6 · k ⟹ 2 n ∧ 3 n , Widerspruch zur Voraussetzung. r = 2 ⟹ n = 6 · k + 2 = 2(3 · k + 1) ⟹ 2 n , Widerspruch zur Voraussetzung. r = 3 ⟹ n = 6 · k + 3 = 3(2 · k + 1) ⟹ 3 n , Widerspruch zur Voraussetzung. r = 4 ⟹ n = 6 · k + 4 = 2(3 · k + 2) ⟹ 2 n , Widerspruch zur Voraussetzung. Also können nur 1 und 5 als Reste auftreten, es gilt mit geeignetem k ∈ ℕ_{0}: r = 1 ⟹ n = 6 · k + 1 bzw. r = 5 ⟹ n = 6 · k + 5 = n = 6(k + 1) + 1 .

(b) Zu zeigen: Ist p eine Primzahl, so ist p ≡ ±1 (mod 6) .

Beweis durch Kontraposition. Ist p ≢ ±1 (mod 6) , so folgt nach (a), daß 3 p oder 2 p, also ist p keine Primzahl.

(c) Gesucht ist ein k ∈ ℕ für das 6k + 1 und 6k − 1 keine Primzahlen sind. Für k = 20 gilt 2k − 1 = 119 = 7 · 17 und 2k + 1 = 121 = 11 · 11 . Wir sehen also, daß die Umhkehrung von (b) nicht gilt.

Aufgabe 40

Betrachte den folgenden Algorithmus für ungerade n ∈ ℕ:

1. x ← ⌊\sqrt{n}⌋

2. while (\sqrt{x^{2}− n} ist kein Quadrat in ℕ) do

3. x ← x + 1

4. Antworte “x ± \sqrt{x^{2}− n} sind zueinander komplementäre Teiler von n”

(a) Warum werden in 2. wirklich Teiler von ngefunden? Ist \sqrt{x^{2}− n} ∈ ℕ_{0} , so sind auch x + \sqrt{x^{2}− n}, x − \sqrt{x^{2}− n} ∈ ℕ_{0} . Bilden wir nun das Produkt, so erhalten wir

(x − \sqrt{x^{2}− n}) · (x + \sqrt{x^{2}− n}) = x^{2}− (\sqrt{x^{2}− n})^{2} = x^{2}− (x^{2}− n) = n.

(b) Warum bricht das Verfahren spätestens bei x = \frac{n+1}{2} ab? Da nnach Voraussetzung ungerade sein soll, ist n + 1 gerade und \frac{n+1}{2} ∈ ℕ. Ist x = \frac{n+1}{2} , so gilt

x^{2}− n = ( \frac{n + 1}{2} ) ^{2}− n = \frac{1}{4}(n^{2}+ 2n + 1) − n = \frac{1}{4}(n^{2}+ 2n + 1 − 4n)
= \frac{1}{4}(n^{2}− 2n + 1) = \frac{1}{4}(n − 1)^{2} = ( \frac{n − 1}{2} ) ^{2}, Quadratzahl

Also bricht das Verfahren spätestens bei x = \frac{n+1}{2} ab.

(c) Was bedeutet es für n, wenn das Verfahren erst für x = \frac{n+1}{2} abbricht? Nach (b) gilt dann

n= ( \frac{n + 1}{2} ) ^{2}− ( \frac{n − 1}{2} ) ^{2} = ( \frac{n + 1}{2} − \frac{n − 1}{2} ) · ( \frac{n + 1}{2} + \frac{n − 1}{2} )

= \frac{n + 1 − n + 1}{2} · \frac{n + 1 + n − 1}{2} = \frac{2}{2} · \frac{2n}{2} = 1 · n

Es kann also keine Teiler außer 1 und ngeben, da diese vorher gefunden worden wären, ist also n ≥ 3 , so ist neine Primzahl.

(d) Es ist ein Teiler von n:= 96133 zu berechnen: Wir haben also x = ⌊\sqrt{96133}⌋= 310 und führen den Algorithmus durch:

\begin{matrix}x & x^{2}− n & Quadrat? \\ 310 & −33 & − \\ 311 & 588 & − \\ 312 & 1211 & − \\ 313 & 1836 & − \\ 314 & 2463 & − \\ 315 & 3092 & − \\ 316 & 3723 & − \\ 317 & 4356 & 66^{2} \end{matrix}

Also x^{2}− n = 66^{2} . Damit haben wir n = x^{2}− 66^{2} = (x − 66)(x + 66) = (317 − 66)(317 + 66) = 251 · 383.

Aufgabe 41

Sei p ∈ ℕ eine Primzahl. Zu zeigen: ∀k ∈ \{1,... ,p − 1\} : p \binom{p}{k} .

Beweis. Wir haben \binom{p}{k} = \frac{p!}{k!(p−k)!} ⟹ \binom{p}{k}k!(p − k)! = p! = p · (p − 1)! . D.h. p teilt den Ausdruck \binom{p}{k} · k! · (p − k)!. Da p prim ist, teilt nach (9.27b) p also mindenstens einen der drei Faktoren. Also p \binom{p}{k} ∨ p k! ∨ p (p − k)! . Wir nehman an p k!, dann haben wir wieder nach (9.27b) p 1 · 2··· k, und p teilt ein l ∈ {1,... ,k}. Damit p ≤ l ≤ k < p , was ein Widerspruch ist. Nun nehmen wir an p (p − k)! , dann teilt p nach (9.27b) ein l ∈ {1,... ,p − k} . Damit p ≤ l ≤ (p − k) ≤ (p − 1) , was ein Widerspruch ist. Da die letzten beiden Fälle unmöglich sind, folgt die Behauptung p \binom{p}{k}.

Aufgabe 42

Für die natürliche Zahl n haben wir die Darstellung n = (a_{r}a_{r−1} ...a_{1}a_{0})_{7} mit a_{k} ∈ {0,1,... ,6} ∀k bzüglich der Basis 7, also

n = a_{r}7^{r}+ a_{r−1} 7^{r−1} + ...+ a_{1}7 + a_{0}.

Weiter bezeichne Q_{7}(n) := ∑ _{k=0}^{r} a_{k} die Quersumme und Q_{7}^{alt}(n) := ∑ _{k=0}^{r}(−1)^{k}a_{k} die alternierende Quersumme von n.

(a) Zu zeigen: (i) Q_{7}(n) ≡ n (mod 3), (ii) Q_{7}^{alt}(n) ≡ n (mod 4).

Beweis. (i) Aus 7 ≡ 1 (mod 3) folgt nach (9.37c) ∀k ∈ ℕ : 7^{k} ≡ 1 (mod 3) . Nach (9.37b) folgt dann ∀k ∈ {0,1,... ,r} : a_{k}7^{k} ≡ a_{k} (mod 3) und damit ist

n ≡ ∑_{k=0}^{r} a_{k}7^{k} ≡ ∑_{k=0}^{r} a_{k} ≡ Q_{7}(n) (mod 3).

(ii) Wir wissen 7 ≡ −1 (mod 4) , daraus folgt nach (9.37c) 7^{k} ≡ (−1)^{k} (mod 4) für alle k ∈ ℕ_{0}. Wie in (i) ist also ∀k ∈ {0,1,... ,r} : a_{k}7^{k} ≡ a_{k}(−1)^{k} (mod 4) . Damit bekommen wir

n ≡ ∑_{k=0}^{r} a_{k}7^{k} ≡ ∑_{k=0}^{r} a_{k}(−1)^{k} ≡ Q_{7}^{alt}a_{k} (mod 4).

(b) Aus (a) ist herzuleiten: (i) 3 | n ⟺ 3 | Q_{7}(n), (ii) 4 | n ⟺ 4 | Q_{7}^{alt}(n).

Beweis. (i) 3 n ⟺ n ≡ 0 (mod 3) ⟺^{(a)} Q_{7}(n) ≡ 0 (mod 3) ⟺ 3 Q_{7}(n) .

(ii) 4 n ⟺ n ≡ 0 (mod 4) ⟺^{(a)} Q_{7}^{alt}(n) ≡ 0 (mod 4) ⟺ 4 Q_{7}^{alt}(n) .

Übungsblatt 12

Aufgabe 43

Zu zeigen: Für jede Primzahl p ∈ ℕ und alle ganzen Zahlen a,b ∈ ℤ ist (a + b)^{p} ≡ a^{p}+ b^{p} (mod p) .

Beweis. Nach Satz (9.42) gilt für alle x ∈ ℤ: x^{p} ≡ x (mod p), falls p prim. Nun gilt

a^{p} ≡ a (mod p)
+  b^{p} ≡ b (mod p)
a^{p}+ b^{p} ≡ a + b (mod p)

und außerdem ist nach Satz (9.42): (a + b)^{p} ≡ a + b (mod p) . Da ≡ eine Äquivalenzrelation und insbes. transitiv ist, gilt a^{p}+ b^{p} ≡ (a + b)^{p} (mod p) .

Aufgabe 44

Gesucht sind die beiden letzten Ziffern der Dezimaldarstellung von a:= 123456789^{4921} . Besitzt a die Dezimaldarstellung a = a_{n}a_{n−1} ...a_{2}a_{1}a_{0})_{10} , so ist a ≡ (a_{1}a_{0})_{10} (mod 100) . Also brechnen wir a ≡ 89 (mod 100) . Da 89 und 100 teilerfremd sind, gilt nach dem Satz von Euler (9.44): 89^{φ(100)} ≡ 1 (mod 100) . Wir müssen nun φ(100), also die Anzahl der Zahlen aus {1,... ,100} berechnen, die zu 100 teilerfremd sind. Sei also 1 ≤ k ≤ 100 und ggT(100,k) = 1. Da 100 = 2^{2}· 5^{2} muß also gelten 2∤kund 5∤k. Also muß k eine ungerade Zahl sein – davon gibt es 50 zwischen 1 und 100. Jede fünfte davon wird aber von 5 geteilt, so daß 40 Zahlen mit den gewünschten Eigenschaften übrigbleiben. Also φ(100) = 40 .

Folglich gilt 89^{40} ≡ 1 (mod 100) . Wir können den Exponenten 4912 schreiben als 4921 = 123 · 40 + 1 . Demnach ist

a^{4921} ≡ 89^{4921} ≡ \underbrace{(89^{40})}_{≡1}^{123}·89 ≡ 1^{123}· 89 ≡ 89 (mod 100).

Aufgabe 45

Seien a = 2767198,b = 1716495 . Es ist der ggT(a,b)zu berechnen.

(a) Durch den Euklidischen Algorithmus:

2767198 = 1 · 1716495 + 1050703
1716495 = 1 · 1050703 + 665792
1050703 = 1 · 665792 + 384911
665792 = 1 · 384911 + 104030
384911 = 1 · 280881 + 104030
280881 = 2 · 104030 + 72821
104030 = 1 · 72821 + 31209
72821 = 2 · 31209 + 10403
31209 = 3 · 10403 + 0

Damit ist ggT(a,b) = 10403 .

(b) Das Sieb des Eratosthenes: Wir steichen aus der Liste der Zahlen von 2 bis 400 alle echten Vielfachen der Zahl 2, dann von 3,5,7,... bis die nächste, noch nicht gestrichene Zahl größer als ⌊\sqrt{400}⌋= 20 ist. Es bleiben alle 78 Primzahlen kleinergleich 400 übrig:

2, 3, 5, 7, 11, 13, 17, 19, 23, 29, 31, 37, 41, 43, 47, 53, 59, 61, 67, 71, 73, 79, 83, 89, 97, 101, 103, 107, 109, 113, 127, 131, 137, 139, 149, 151, 157, 163, 167, 173, 179, 181, 191, 193, 197, 199, 211, 223, 227, 229, 233, 239, 241, 251, 257, 263, 269, 271, 277, 281, 283, 293, 307, 311, 313, 317, 331, 337, 347, 349, 353, 359, 367, 373, 379, 383, 389, 397

(c) ggT-Berechnung durch Primfaktorzerlegung: Wir teilen a und bsukzessive durch alle Primzahlen kleiner als 400:

\begin{aligned}a & = 2767198 \\ a_{1} & = 2767198/2 = 1383599 \\ a_{2} & = 1383599/7 = 197657 \\ a_{3} & = 197657/19 = 10403 \\ a_{4} & = 10403/101 = 103 \\ ⟹ a & = 2 · 7 · 19 · 101 · 103 \end{aligned}  \begin{aligned}b & = 1716495 \\ b_{1} & = 1716495/3 = 572165 \\ b_{2} & = 572165/5 = 114433 \\ b_{3} & = 114433/11 = 10403 \\ b_{4} & = 10403/101 = 103 \\ ⟹ a & = 3 · 5 · 11 · 101 · 103 \end{aligned}

Die Primfaktoren, die in a und b auftauchen sind 101, 103. Damit ist ggT(a,b) = 101 · 103 = 10403 .

Aufgabe 46

(a) ( \begin{matrix}1 & 2 \\ 3 & 4 \end{matrix}) + ( \begin{matrix}1 \\ −1 \end{matrix} ) ist nicht definiert, da die Matrizen unterschiedliche Formate haben.

(b) ( \begin{matrix}[1]_{5} & [3]_{5} & [7]_{5} \\ [0]_{5} & [2]_{5} & [6]_{5} \end{matrix}) + ( \begin{matrix}[3]_{5} & [2]_{5} & [6]_{5} \\ [12]_{5} & [−3]_{5} & [1]_{5} \end{matrix}) = ( \begin{matrix}[4]_{5} & [0]_{5} & [3]_{5} \\ [2]_{5} & [4]_{5} & [2]_{5} \end{matrix})

(c) ( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix}) · ( \begin{matrix}4 & 5 \\ 6 & 8 \\ 7 & 9 \end{matrix}) = ( \begin{matrix}37 & 48 \\ 88 & 114 \end{matrix})

(d) ( \begin{matrix}4 & 5 \\ 6 & 8 \\ 7 & 9 \end{matrix}) · ( \begin{matrix}1 & 2 & 3 \\ 4 & 5 & 6 \end{matrix}) = ( \begin{matrix}24 & 33 & 42 \\ 38 & 52 & 66 \\ 43 & 59 & 75 \end{matrix})

(e) ( \begin{matrix}1 & 2 \\ 5 & 6 \end{matrix}) · ( \begin{matrix}4 & 5 \\ 6 & 8 \\ 7 & 9 \end{matrix}) ist nicht definiert, da die Spaltenzahl (2) des ersten Faktors nicht mit der Zeilenzahl des zweiten Faktors (3) übereinstimmt.

(f) ( \begin{matrix}[15]_{7} & [14]_{7} \\ [35]_{7} & [−13]_{7} \end{matrix}) · ( \begin{matrix}[9]_{7} & [25]_{7} \\ [5]_{7} & [93]_{7} \end{matrix}) = ( \begin{matrix}[2]_{7} & [4]_{7} \\ [5]_{7} & [2]_{7} \end{matrix})

Übungsblatt 13

Aufgabe 47

Gegeben ist die Menge M = {1,2,3,4,5,6}.

(a) Gesucht ist die Adjazenzmatrix zu ≤ auf M. A = (a_{ij}) ∈ M_{6}(ℝ) mit a_{ij} = \{ \begin{matrix}1 & i ≤ j, \\ 0 & sonst. \end{matrix}

A = ( \begin{matrix}1 & 1 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 1 & 1 & 1 \\ 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 \\ 0 & 0 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 0 & 0 & 1 \end{matrix})

(b) Gesucht ist die Relation auf M, die die folgende Adjazenzmatrix hat:

( \begin{matrix}0 & 1 & 1 & 1 & 1 & 1 \\ 1 & 0 & 1 & 1 & 1 & 1 \\ 1 & 1 & 0 & 1 & 1 & 1 \\ 1 & 1 & 1 & 0 & 1 & 1 \\ 1 & 1 & 1 & 1 & 0 & 1 \\ 1 & 1 & 1 & 1 & 1 & 0 \end{matrix})

Es gilt hier offensichtlich ∀x,y ∈ M : xRy ⟺ a_{xy}= 1 ⟺ x ≠ y , also ist ≠ die gesuchte Relation.

Aufgabe 48

Es sei Reine Relation auf der Menge M = {1,... ,n}, n ∈ ℕ , mit A_{R}= (a_{ij}) ∈ M_{n}(ℝ) als Adjazenzmatrix.

(a) Zu zeigen: Rreflexiv ⟺ ∀i ∈ M : a_{ii} = 1 .

Beweis. Rreflexiv ⟺ ∀i ∈ M : iRi ⟺ ∀i ∈ M : a_{ii} = 1 .

(b) Zu zeigen: Rsymmetrisch ⟺ A_{R} ist symmetrisch.

Beweis. “⟹ ” Sei also R symmetrisch. Dann gilt ∀i,k ∈ M : iRk ⟹ kRi und damit ∀i,k ∈ M : a_{ik} = 1 ⟹ a_{ki} = 1 . Analog gilt ∀i,k ∈ M : i R̸k ⟹ k R̸i und damit ∀i,k ∈ M : a_{ik} = 0 ⟹ a_{ki} = 0 .

“⇐ ” Sei A_{R}symmetrisch, also ∀i,k ∈ M : a_{ki} = a_{ki} . Dann gilt

∀i,k ∈ M : a_{ik} = 1 ⟹ a_{ki} = 1 ⟺ iRk ⟹ kRi, also Rsymmetrisch.

(c) Zu zeigen: Rtransitiv ⟺ ∀i,k,l ∈ M : a_{ik}· a_{kl} ≤ a_{il} .

Beweis. “⟹ ” Sei R transitiv und i,k,l ∈ M beliebig. Sind a_{ik} = a_{kl} = 0 , so ist a_{ik}· a_{kl} = 0. Seien a_{ik} = a_{kl} = 1 , dann gilt iRk ∧ kRl und wegen der Transitivität von Rauch iRl und damit a_{il} = 1 ⟹ a_{ik}· a_{kl} = 1 ≤ 1 = a_{il} . “⇐ ” Es gelte iRkund kRlfür i,k,l ∈ M. Dann ist a_{ik} = a_{kl} = 1 und somit muß für a_{il} = 1 gelten. Also ist iRlund Rist transitiv.

(d) Zu zeigen: Für die zu Rinverse Relation R^{−1} gilt A_{R^{−1}} =^{t}A_{R}.

Beweis. Nach Definition der inversen Relation gilt ∀i,k ∈ M : iR^{−1} k ⟺ kRi . Seien nun A_{R^{−1}} = (b_{ik}) und ^{t}A_{R}= (a_{ki}) die darstellenden Matrizen. Für alle i,k ∈ M gilt b_{ik} = 1 ⟺ iR^{−1} k ⟺ kRi ⟺ a_{ki} = 1. Entsprechend gilt auch b_{ik} = 0 ⟺ a_{ki} = 0 . Also ∀i,k ∈ M : b_{ik} = a_{ki} und damit A_{R^{−1}} =^{t}A_{R}.

Aufgabe 49

Wir haben A = ( \begin{matrix}2 & −1 & 1 \\ −3 & 4 & −3 \\ −5 & 4 & −3 \end{matrix} ) , B = ( \begin{matrix}1 & −1 & 1 \\ −3 & 3 & −3 \\ −5 & 5 & −5 \end{matrix} ) ∈ M_{3}(ℝ) .

(a) Wir berechnen A · B = B · A = 0(die Nullmatrix), A · A = A,

E_{12}· A = ( \begin{matrix}0 & 1 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix}) · A = ( \begin{matrix}−3 & −4 & −3 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{matrix} ) und

E_{32}· A = ( \begin{matrix}0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 1 & 0 \end{matrix}) · A = ( \begin{matrix}0 & −1 & 0 \\ 0 & −3 & 0 \\ 0 & −4 & 0 \end{matrix}) .

(b) Behauptung: A,Bsind nicht invertierbar.

Beweis durch Widerspruch. Annahme: A ist invertierbar, also existiert ein A^{−1} mit A · A^{−1} = A^{−1} · A = E_{3}. Dann gilt aber auch

A^{−1} · \underbrace{(A · B)}_{=0}= \underbrace{(A^{−1} · A)}_{=E_{3}}·B = B,

also B = 0 — Widerspruch. Durch analoge Argumentation erhält man, daß Bnicht invertierbar ist.

(c) Behauptung: ∀n ∈ ℕ : A^{n} = A.

Beweis durch Induktion. Induktionsanfang: n = 1 A^{1} = A Induktionsvoraussetzung: Für ein beliebiges n ∈ ℕ gilt A^{n} = A. Induktionsbehauptung: A^{n+1} = A. Induktionsschritt: A^{n+1} = A · A^{n} =^{IV} A · A = A .

Aufgabe 50

Sei C := \{ ( \begin{matrix}a & −b \\ b & a \end{matrix} ) a,b ∈ ℝ\} ⊆ M_{2}(ℝ).

(a) Zu zeigen: Die Nullmatrix und die zweireihige Einheitsmatrix gehören zu C, C ist abgeschlossen unter Matrizenaddition und -multiplikation.

Beweis. Wegen 0 = 0 und 0 = −0 sowie 1 = 1 und 0 = −0 gehören die Nullmatrix und die zweireihige Einheitsmatrix zu C.

Seien A:= ( \begin{matrix}a & −b \\ b & a \end{matrix} ) , B:= ( \begin{matrix}c & −d \\ d & c \end{matrix} ) ∈ C . Dann ist A + B = ( \begin{matrix}(a + c) & −(b + d) \\ (b + d) & (a + c) \end{matrix} ) ∈ C .

Außerdem ist A · B = ( \begin{matrix}(ac − bd) & −(ad + bc) \\ (ad + bc) & (ac − bd) \end{matrix} ) ∈ C.

(b) Zu zeigen: A = ( \begin{matrix}1 & −2 \\ 2 & 1 \end{matrix} ) ∈ C ist invertierbar und A^{−1} ∈ C.

Beweis. Gesucht ist B = ( \begin{matrix}u & x \\ v & y \end{matrix}) ∈ C mit A · B = E_{2}. Also müssen wir die Gleichungssysteme

A( \begin{matrix}u \\ v \end{matrix}) = ( \begin{matrix}1 \\ 0 \end{matrix}) und A( \begin{matrix}x \\ y \end{matrix}) = ( \begin{matrix}0 \\ 1 \end{matrix}) lösen. Dies liefert uns B = ( − \frac{2}{5}  \frac{1}{5}^{\frac{1}{5}  \frac{2}{5}}) ∈ C .

Wann ist eine allgemeine Matrix ( \begin{matrix}a & −b \\ b & a \end{matrix} ) ∈ C invertierbar?

Im Allgemeinen gilt: Ainvertierbar ⟺ detA ≠ 0 ⟺ a^{2}+ b^{2} ≠ 0 , also wenn a ≠ 0 oder b ≠ 0 gilt. Es gilt dann A^{−1} = \frac{1}{a^{2}+b^{2}} · ( \begin{matrix}a & b \\ −b & a \end{matrix}) ∈ C. (Determinanten müssen wir noch nicht kennen!)

(c) Zu zeigen: Es gibt Matrix I ∈ C mit I^{2}+ E_{2} = 0 .

Beweis. Setze I := ( \begin{matrix}0 & −1 \\ 1 & 0 \end{matrix} ) . Dann ist I ∈ C und es gilt I^{2} = ( \begin{matrix}−1 & 0 \\ 0 & −1 \end{matrix} ) = −E_{2} und damit

I^{2}+ E_{2} = 0 .

Übungsblatt 14

Aufgabe 51

Seien A = ( \begin{matrix}1 & 0 & 1 \\ −1 & 2 & 1 \\ 0 & 1 & 2 \end{matrix}) ∈ M_{3}(ℝ) und b = ( \begin{matrix}2 \\ 1 \\ 1 \end{matrix}) ∈ ℝ^{3} .

(a) Zu zeigen: Aist invertierbar. Berechne außerdem A^{−1}. Wir versuchen zunächst, A^{−1} zu berechnen:

A  E_{3}  b

1 0 1 1 0 0 2 A_{21}(1) −1 2 1 0 1 0 1

0 1 2 0 0 1 1 1 0 1 1 0 0 2 V_{23} 0 2 2 1 1 0 3

0 1 2 0 0 1 1 1 0 1 1 0 0 2 A_{23}(−2) 0 1 2 0 0 1 1

0 2 2 1 1 0 3 A_{13}( \frac{1}{2}) 1 0 1 1 0 0 2 A_{23}(1) 0 1 2 0 0 1 1

0 0 −2 1 1 −2 1

A  E_{3}  b
1 0  0  \frac{3}{2}  \frac{1}{2} −1 \frac{5}{2}
0 1  0 1  1 −1 2
D_{3}(− \frac{1}{2}) 0 0 −2 1  1 −2 1
1 0  0  \frac{3}{2}  \frac{1}{2} −1 \frac{5}{2}
0 1  0 1  1 −1 2
0 0  1 − \frac{1}{2} − \frac{1}{2}  1 − \frac{1}{2}
T (A)  A^{−1}  0

Wegen T (A) = E_{3}ist nach Satz (10.27) Ainvertierbar, A^{−1} wurde in der dritten Spalte berechnet.

(b) Gesucht sind alle Lösungen xdes linearen Gleichungssystems A · x = b. Wir wissen Lös(A,b) = Lös(T (A),c)mit c = ( \frac{5}{2} ; 2 ; − \frac{1}{2} ) wie es in Teil (a) berechnet wurde. T (A) · x = cist genau dann erfüllt wenn x = c = ( \frac{5}{2} ; 2 ; − \frac{1}{2} ) , denn T (A)ist ja gerade die Einheitsmatrix. Dies liefert uns Lös(A,b) = Lös(T (A),c) = \{( \frac{5}{2} ; 2 ; − \frac{1}{2} ) \}.

(c) Kann es ein c ∈ ℝ^{3} geben, so daß A · x = cnicht lösbar ist? Nein. Sei c ∈ ℝ^{3} beliebig. Dann ist A^{−1} · ceine Lösung des LGSs, denn

A · (A^{−1} c) = (A · A^{−1} )c = E_{3}· c = c.

(d) Stelle die Matrix Aals ein Produkt von Elementarmatrizen dar. Wie wir in (a) gesehen haben, gilt

\underbrace{D_{3}( −\frac{1}{2}) · A_{23}(1) · A_{13}( \frac{1}{2}) · A_{32}(−2) · V_{23}· A_{21}(1)}_{=:G} ·A = G · A = T (A) = E_{3}

und damit

A = G^{−1} · T (A) = G^{−1} · E_{3} = G^{−1}

= ( D_{3}( −\frac{1}{2}) · A_{23}(1) · A_{13}( \frac{1}{2}) · A_{32}(−2) · V_{23}· A_{21}(1))^{−1}

= A_{21}(1)^{−1} · V_{23}^{−1} · A_{32}(−2)^{−1} · A_{13}( \frac{1}{2}) ^{−1} · A_{23}(1)^{−1} · D_{3}( −\frac{1}{2}) ^{−1}

= A_{21}(−1) · V_{23}· A_{32}(2) · A_{13}( −\frac{1}{2}) · A_{23}(−1) · D_{3}(−2)

Aufgabe 52

Seien A:= ( \begin{matrix}1 & 0 & 1 & 1 & −1 \\ 2 & 1 & −1 & 1 & 0 \\ 3 & 1 & 0 & 2 & −1 \\ 1 & 1 & 0 & 0 & 0 \end{matrix} ) ∈ M_{4,5}(ℝ) und b = ( \begin{matrix}2 \\ 0 \\ 2 \\ 0 \end{matrix}) ,b′= ( \begin{matrix}1 \\ 0 \\ 2 \\ 0 \end{matrix}) ∈ ℝ^{4} .

Gesucht sind die Lösungsmengen von A · x = bund A · x = b′.

Wir benutzen den Gauss-Algorithmus:

A  b b′
1 0 1 1 −1 2 1
2 1 −1 1 0 0 0
3 1 0 2 −1 2 2
1 1 0 0 0 0 0

↓ Elementare Zeilenumformungen ↓

1 0 0 1 − \frac{1}{2} 1 0
0 1 0 −1 \frac{1}{2} −1 0
0 0 1 0 − \frac{1}{2} 1 0
0 0 0 0 0 0 1
T (A)  c c′

Nun lösen wir das LGS T (A) · x = c:

x_{1}  +x_{4} −\frac{1}{2}x_{5} =  1
x_{2}  −x_{4} +\frac{1}{2}x_{5} =  −1
x_{3}  −\frac{1}{2}x_{5} =  1
setze x_{4} = r ∈ ℝ und x_{5} = 5 ∈ ℝ beliebig.

und wir erhalten:

x_{3}= 1 + \frac{1}{2}s
x_{2}= −1 + r − \frac{1}{2}s
x_{1}= 1 − r + \frac{1}{2}s

und damit

Lös(A,b)= \{ ( \begin{matrix}1 − r + \frac{1}{2}s \\ −1 + r − \frac{1}{2}s \\ 1 + \frac{1}{2}s \\ r \\ s \end{matrix} ) |r,s ∈ ℝ\} .

Das LGS T (A) · x = c′ist nicht lösbar, da sonst 0 = 1 folgen würde. Also ist Lös(A,b′) = ∅.

Aufgabe 53

Zu lösen ist das LGS ( \begin{matrix}1 & 0 & 2 \\ 0 & 1 & 3 \\ 1 & 1 & 0 \end{matrix}) · x = ( \begin{matrix}3 \\ 4 \\ 2 \end{matrix}) über ℤ_{5}. Hierbei stehen die Zahlen für die entspre-

chenden Restklassen modulo 5. Modulo 5 gelten insbesondere 2 · 3 = 4 · 4 = 1, also 2^{−1} = 3, 3^{−1} = 2, 4^{−1} = 4 . Nun führen wir den Gauss-Algorithmus wie gewohnt durch:

A  b

1 0 2 3 0 1 3 4 1 1 0 2 1 0 2 3 0 1 3 4 0 1 3 4 1 0 2 3 0 1 3 4 0 0 0 0

Wir setzen x_{3} = r ∈ ℤ_{5} beliebig und erhalten

x_{3}= r
x_{2}= 4 + 2r
x_{1}= 3 + 3r

und damit

Lös(A,b)= \{ ( \begin{matrix}3 + 3r \\ 4 + 2r \\ r \end{matrix} ) |r ∈ ℤ_{5}\}

= \{( \begin{matrix}3 \\ 4 \\ 0 \end{matrix}) ,( \begin{matrix}1 \\ 1 \\ 1 \end{matrix}) ,( \begin{matrix}4 \\ 3 \\ 2 \end{matrix}) ,( \begin{matrix}2 \\ 0 \\ 3 \end{matrix}) ,( \begin{matrix}0 \\ 2 \\ 4 \end{matrix}) \}

Es gibt also genau 5 Lösungen.

Aufgabe 54

Moderne Kommunikationsgeräte (wie z.B. Handies, Satelliten, CD-Player) arbeiten digital, d.h., alle Daten werden als Folge von 0 und 1 (sog. Bitströmen) dargestellt. Ein Problem ist dabei das Erkennen von Übertragungsfehlern, d.h. statt des gesendeten Bits a kommt das Bit 1 − a an. Solche Probleme werden in der Codierungstheorie behandelt. Dazu nutzt man lineare Gleichungssysteme und Matrizen.

1. Die einfachste Art, einen Fehler zu erkennen, ist, ein Bit a dreimal zu schicken, also aaa statt a. Drei Bits x_{1}x_{2}x_{3} werden dann vom Empfänger als Einheit gelesen. Das Wort ist richtig empfangen worden, wenn gilt

x_{2} = x_{3} und x_{1} = x_{3}. (4)

Schreiben Sie diese Gleichungen in eine Matrixschreibweise vom Typ

H · ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \end{matrix} )

um, wobei alle Einträge modulo 2 gerechnet werden, da sie Bits darstellen! Bestimmen Sie die Menge aller Lösungen des Gleichungssystems (4) in ℤ_{2}. Die Elemente dieser Lösungsmenge sind 3-Bit-Worte x_{1}x_{2}x_{3} und werden Worte des Codes genannt.

Lösung: Durch Umformen erhält man

\begin{matrix}0 · x_{0}+ & 1 · x_{2}+ & (−1) · x_{3}= & 0 \\ 1 · x_{0}+ & 0 · x_{2}+ & (−1) · x_{3}= & 0 \end{matrix} , und damit H = ( \begin{matrix}0 & 1 & 1 \\ 1 & 0 & 1 \end{matrix} ) .

Dabei zu beachten: −1 ≡ 1 mod2. Diese Matrix ist bereits in Treppenform, wenn man die beiden Zeilen tauscht. Als Lösungen ergeben sich^{t}(0,0,0) (bei Wahl x_{3} = 0) und^{t}(1,1,1) (bei Wahl x_{3} = 1). Der Code umfasst also die Worte^{t}(0,0,0) und^{t}(1,1,1).

2. Kommt nun ein Wort an, dass kein Wort des Codes ist, so wird es korrigiert. Das geschieht wie folgt: zwei Bits sind gleich, ein Bit ist davon verschieden. Das ursprüngliche Bit ist dann gleich dem Wert, der zweimal vorkommt. Bsp: empfangen 101, dann ist das ursprünglich gesendete Bit 1. Wie lautet also der ursprünglich gesendete Bitstrom, wenn man folgende 3-Bit-Folge empfängt?

101 111 001 010 110 001 100 Lösung: Fehler sind aufgetreten in allen 3-Tupeln außer dem zweiten:

empfangen: 101 111 001 010 110 001 100
korrigiert : 111 111 000 000 111 000 000
Bitstrom :  1 1 0 0 1 0 0.

3. Das Problem ist: statt ursprünglich ein Bit werden nun 3 Bit gesendet, d.h., die Nachricht wird um den Faktor 3 aufgebläht. Mit sogenannten Hamming-Codes kann man einen kleineren Faktor erreichen. Man sendet immer 4 Bits x_{1},x_{2},x_{3},x_{4} und fügt drei Kontrollbits y_{1},y_{2},y_{3} hinzu. Ein Codewort ist dann ein 7-Bit-Wort x_{1}x_{2}x_{3}x_{4}y_{1}y_{2}y_{3}, das folgendes Gleichungssystem erfüllt:

( \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ) · ( \begin{matrix}x_{1} \\ x_{2} \\ x_{3} \\ x_{4} \\ y_{1} \\ y_{2} \\ y_{3} \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) . (5)

In der i-ten Spalte der Matrix steht also gerade die Zahl i in binärer Schreibweise (^{t}(0,0,1) steht also für binär (001), d.h. 1)! Codieren Sie alle 4-Bit-Worte x_{1}x_{2}x_{3}x_{4} mit diesem Code, indem Sie y_{1},y_{2},y_{3} bestimmen, so dass ^{t}(x_{1},x_{2},x_{3},x_{4},y_{1},y_{2},y_{3}) eine Lösung von (5) ist.

Lösung: Durch die Matrixschreibweise ist folgendes Gleichungssystem gegeben

\begin{matrix}0·x_{1}+ & 0·x_{2}+ & 0·x_{3}+ & 1·x_{4}+ & 1·y_{1}+ & 1·y_{2}+ & 1·y_{3} = 0 \\ 0·x_{1}+ & 1·x_{2}+ & 1·x_{3}+ & 0·x_{4}+ & 0·y_{1}+ & 1·y_{2}+ & 1·y_{3} = 0 \\ 1·x_{1}+ & 0·x_{2}+ & 1·x_{3}+ & 0·x_{4}+ & 1·y_{1}+ & 0·y_{2}+ & 1·y_{3} = 0 \end{matrix},

dass man nach y_{1},y_{2},y_{3} umformt:

\begin{matrix}y_{1}= & & x_{2} & +x_{3} & +x_{4} \\ y_{2}= & x_{1} & & +x_{3} & +x_{4} \\ y_{3}= & x_{1} & +x_{2} & & +x_{4} \end{matrix} .

Dann ergeben sich folgende Codeworte:

\begin{matrix}x_{1} & x_{2} & x_{3} & x_{4} & y_{1} & y_{2} & y_{3} \\ 0 & 0 & 0 & 0 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 & 1 & 0 & 1 \\ 0 & 0 & 1 & 0 & 1 & 1 & 0 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 0 & 1 & 0 & 1 & 0 \\ 0 & 0 & 1 & 1 & 0 & 0 & 1 \\ 0 & 1 & 1 & 1 & 1 & 0 & 0 \end{matrix}  \begin{matrix}x_{1} & x_{2} & x_{3} & x_{4} & y_{1} & y_{2} & y_{3} \\ 1 & 0 & 0 & 0 & 0 & 1 & 1 \\ 1 & 1 & 0 & 0 & 1 & 1 & 0 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \\ 1 & 1 & 1 & 0 & 0 & 0 & 0 \\ 1 & 0 & 0 & 1 & 1 & 0 & 0 \\ 1 & 1 & 0 & 1 & 0 & 0 & 1 \\ 1 & 0 & 1 & 1 & 0 & 1 & 0 \\ 1 & 1 & 1 & 1 & 1 & 1 & 1 \end{matrix}

4. Zeigen Sie: Addiert man zwei Codeworte a,b ∈ ℤ_{2}^{7}, so ist das Wort c = a + b auch ein Codewort, d.h. eine Lösung von (5).

Lösung: Seien a,b ∈ ℤ_{2}^{7} zwei Lösungsvektoren des Gleichungssystems. Wir schreiben für die Matrix einfach H ∈ M_{3,7}(ℤ_{2}). Dann gilt: H · a = 0 und H · b = 0, also

H · (a + b) = H · a + H · b = 0 + 0 = 0, d.h. auch a + b ist wieder eine Lösung.(Vgl. Satz (10.37)).

5. Man kann die fehlerhafte Übertragung des i-ten Bits (1 ≤ i ≤ 7) beim Codewort a = t(x_{1},x_{2},x_{3},x_{4},y_{1},y_{2},y_{3}) wie folgt in Formeln darstellen: man addiert den Einheitsvektor e_{i} ∈ ℤ_{2}^{7} (in Zeile i steht eine 1, sonst 0) zu a. Zeigen Sie: Multipliziert man die Matrix aus (5) von rechts mit a + e_{i}, so ist die Lösung gerade der Vektor, der transponiert die Binärdarstellung von i ist.

Lösung: Sei e_{i} =^{t}(0,... ,0,1,0,... ,0) der Einheitsvektor, der in der i-ten Zeile (1 ≤ i ≤ 7) eine 1 enthält. Dann gilt für einen Lösungsvektor a ∈ ℤ_{2}^{7} gerade:

H · (a + e_{i}) = H · a + H · e_{i} = 0 + H · e_{i} = H_{i}, wobei H_{i} die i-te Spalte von H bezeichnet. Die Matrix H ist aber so konstruiert, dass in der i-ten Spalte gerade die Zahl i binär codiert steht.

6. Man erhält also die ursprünglichen Bits zurück, indem man jeden 7-stelligen empfangenen Bit-Vektor von rechts an die Matrix aus (5) multipliziert. Ist das Ergebnis ^{t}(0,0,0), so ist das empfangene Wort korrekt, und man nimmt die ersten vier Bit als ursprüngliche Nachricht. Andernfalls erhält man als Ergebnis den Index des falsch übertragenen Bits. Dieses Bit korrigiert man: aus 0 mache 1 bzw. aus 1 wird 0. Dann nimmt man die ersten vier Bit als ursprüngliche Nachricht. Wie lautet also die ursprünglich gesendete Folge von 4 Bits, wenn man folgende 7-Bit-Folge empfängt?

t(0,1,1,0,0,1,1) ^{t}(0,1,1,0,1,0,1)

Lösung: Die Decodierung des ersten Vektors ergibt:

( \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ) · ( \begin{matrix}0 \\ 1 \\ 1 \\ 0 \\ 0 \\ 1 \\ 1 \end{matrix} ) = ( \begin{matrix}0 \\ 0 \\ 0 \end{matrix} ) ,

d.h. der Vektor wurde fehlerfrei übertragen, die ursprünglichen vier Bits lauten: 0110. Für den zweiten Vektor haben wir aber:

( \begin{matrix}0 & 0 & 0 & 1 & 1 & 1 & 1 \\ 0 & 1 & 1 & 0 & 0 & 1 & 1 \\ 1 & 0 & 1 & 0 & 1 & 0 & 1 \end{matrix} ) · ( \begin{matrix}0 \\ 1 \\ 1 \\ 0 \\ 1 \\ 0 \\ 1 \end{matrix} ) = ( \begin{matrix}0 \\ 1 \\ 1 \end{matrix} ) ,

d.h. das dritte Bit ist fehlerhaft. Korrigiert lautet der Vektor (0,1,0,0,1,0,1), also wurde ursprünglich 0100 gesendet.

7. Um welchen Faktor wird die ursprüngliche Nachricht bei diesem Hamming-Code aufgebläht?

Lösung: Statt 4 Bit werden 7 Bit gesendet, also wird die Nachricht um den Faktor \frac{7}{4} = 1.75 < 2 aufgebläht.