studyklar
LAG · Übungsblatt 2 · Aufgabe 3

Binärwörter als Vektorraum

Ein Binärwort der Länge nn ist eine Folge von nn Nullen und Einsen, etwa (1,0,1,1)(1, 0, 1, 1). Die Aufgabe macht aus allen diesen Wörtern einen Vektorraum: Wir legen fest, wie man zwei Wörter addiert und wie man ein Wort mit einer Zahl multipliziert. Danach weisen wir alle Regeln eines Vektorraums einzeln nach. Mit Weiter geht es Schritt für Schritt voran. Ein Klick auf einen Schritt springt direkt dorthin.

Die Aufgabe

3. Aufgabe. Sei MM die Menge aller n-Tupel M=Z2nM = \mathbb{Z}_2^n. Dann sind die Elemente von MM alle Binärkombinationen der Länge nn. Die Menge MM soll zum Vektorraum „befördert“ werden. Dazu wird sie, wie aus der Theorie bekannt, mit einer geeigneten Addition versehen zunächst zur Abelschen Gruppe „angehoben“. Ferner wird ihr eine geeignete Skalarmultiplikation auf einem passenden Zahlenkörper anheim gestellt.

  1. Geben Sie eine geeignete Addition an.
  2. Geben Sie eine geeignete Skalarmultiplikation und den zugehörigen Zahlenkörper KK an.
  3. Zeigen Sie, dass mit a) und b) die Menge MM ein Vektorraum VV ist.

In eigenen Worten: MM enthält alle Wörter aus nn Nullen und Einsen. Für n=4n = 4 sind das 24=162^4 = 16 Wörter, von (0,0,0,0)(0, 0, 0, 0) bis (1,1,1,1)(1, 1, 1, 1). Ein n-Tupel ist eine geordnete Liste aus nn Einträgen. Z2n\mathbb{Z}_2^n heißt: nn Einträge, jeder aus Z2={0,1}\mathbb{Z}_2 = \{0, 1\}.

Gesucht ist zuerst eine Addition, die zwei Wörter wieder zu einem Wort macht (a). Dann eine Multiplikation mit Zahlen, den Skalaren, und die Menge KK, aus der die Skalare kommen (b). KK muss ein Körper sein, also eine Zahlenmenge, in der man addieren, subtrahieren, multiplizieren und durch alles außer 0 teilen kann. Zuletzt ist zu beweisen, dass damit alle Vektorraum-Regeln gelten (c).

„Befördert“ und „angehoben“ meinen: Die Menge bekommt Rechenarten dazu. Eine abelsche Gruppe ist eine Menge mit einer Addition, die bestimmte Regeln erfüllt (Teil c zählt sie auf). „Anheim gestellt“ heißt hier: dazugegeben.

So gehen wir vor:

  1. a) In jeder Stelle modulo 2 addieren, also mit 1 + 1 = 0.
  2. b) Als Körper K=Z2K = \mathbb{Z}_2 nehmen und jede Stelle modulo 2 multiplizieren.
  3. c) Erst zeigen, dass Z2\mathbb{Z}_2 ein Körper ist. Dann jedes Axiom G1 bis G5 und S1 bis S4 für beliebige Wörter beweisen.

Rechnen in ℤ₂: modulo 2

Addition in ℤ₂: gewöhnlich addieren, Rest bei Division durch 2
0+0=0,0+1=1,1+0=1,1+1=2 mod 2=00 + 0 = 0, \quad 0 + 1 = 1, \quad 1 + 0 = 1, \quad 1 + 1 = 2 \bmod 2 = 0
++01
001
110

Die Einträge eines Worts sind 0 oder 1. Addiert man gewöhnlich, wird 1+1=21 + 1 = 2. Die 2 ist aber kein erlaubter Eintrag. Darum rechnet man modulo 2: erst gewöhnlich rechnen, dann den Rest bei Division durch 2 nehmen. Aus 2 wird so 0, denn 2=1⋅2+02 = 1 \cdot 2 + 0.

Die Menge Z2={0,1}\mathbb{Z}_2 = \{0, 1\} mit diesem Rechnen heißt Z2\mathbb{Z}_2 (sprich „Z zwei“). Die Tafel steht im Lösungsweg und in der Grafik. Wer Informatik kennt: Das ist genau XOR, das exklusive Oder.

Aus Ü2 A2 („Der Vektorraum ℤ₃ × ℤ₃: Rechnen mit Resten“): Dort wird modulo 3 gerechnet: gewöhnlich rechnen, dann den Rest bei Division durch 3 nehmen, etwa 2+2=4=1⋅3+12 + 2 = 4 = 1 \cdot 3 + 1, also 2+2=12 + 2 = 1.

Wörter Stelle für Stelle addieren

Die Addition auf M (Antwort zu a)
a+b:=(a1+b1, a2+b2, …, an+bn),ai+bi modulo 2a + b := (a_1 + b_1,\ a_2 + b_2,\ \ldots,\ a_n + b_n), \qquad a_i + b_i \text{ modulo } 2
Beispiel mit n = 4
(1,0,1,1)+(0,1,1,0)=(1+0, 0+1, 1+1, 1+0)=(1,1,0,1)(1, 0, 1, 1) + (0, 1, 1, 0) = (1 + 0,\ 0 + 1,\ 1 + 1,\ 1 + 0) = (1, 1, 0, 1)

Zwei Wörter a=(a1,a2,…,an)a = (a_1, a_2, \ldots, a_n) und b=(b1,b2,…,bn)b = (b_1, b_2, \ldots, b_n) addiert man komponentenweise: erste Stelle plus erste Stelle, zweite plus zweite und so weiter. Jede dieser Additionen ist die Addition aus Z2\mathbb{Z}_2 vom Schritt davor. aia_i heißt die ii-te Komponente (Stelle) von aa.

Warum ist das „geeignet“? Jede Stelle des Ergebnisses ist wieder 0 oder 1, denn die Tafel enthält nur 0 und 1. Das Ergebnis hat nn Stellen. Also ist a+ba + b wieder ein Wort aus MM. Ob auch alle anderen Regeln gelten, prüft Teil c.

Noch 17 Schritte bis zum Ergebnis
Den ganzen Lösungsweg sehen Studierende und Lehrende der HS KL. Registriere dich mit deiner Adresse @stud.hs-kl.de oder @hs-kl.de, dann geht es hier direkt weiter.
Registrieren

Beispielwörter

n = 4, a = 1011, b = 0110, c = 1100

Abbildung 1Beispielwörter

n = 4, a = 1011, b = 0110, c = 1100

a
1
0
1
1
b
0
1
1
0
a + b
1
1
0
1
1 · a
1
0
1
1
Legendeberechnetgrau: gegebena + b und 1 · a für die Beispielwörter: Ergebnisse hervorgehoben.