Brauche Hilfe bei folgender Aufgabe. Danke im Voraus
In dieser Aufgabe befassen wir uns mit der Addition von Binärzahlen, die wir formalisieren wollen. Dabei bildet der Operator \( \oplus_{n}^{c}: Z_{2}^{n} \times Z_{2}^{n} \rightarrow Z_{2}^{n+1} \) zwei Wörter der Länge \( n \in \mathbb{N}_{0} \), die jeweils eine Binärzahl repräsentieren auf ein Wort der Länge \( n+1 \mathrm{ab} \), das die Summe beider Zahlen repräsentieren soll. Im Superskript wird dabei der Übertrag \( c \in Z_{2} \) aus vorangegangenen Addtionsschritten mitgeführt, so dass sich hinter \( \oplus_{n}^{c} \) eigentlich zwei Operationen \( \oplus_{n}^{0} \) und \( \oplus_{n}^{1} \) verbergen.
Wir betrachten nun die folgende induktive Definition für die durch \( \oplus_{n}^{c} \) beschriebenen Funktionen für beliebige \( c \in Z_{2}, n \in \mathbb{N}_{0} \) :
\( \begin{array}{c} \varepsilon \oplus_{0}^{c} \varepsilon=c \\ \forall v, w \in Z_{2}^{n} \forall \alpha, \beta \in Z_{2}: v \alpha \oplus_{n+1}^{c} w \beta=\left(v \oplus_{n}^{\gamma(\alpha, \beta, c)} w\right) \cdot \delta(\alpha, \beta, c) \end{array} \)
Dabei beschreibt
\( \delta: Z_{2} \times Z_{2} \times Z_{2} \rightarrow Z_{2},(x, y, z) \mapsto\left\{\begin{array}{l} 1, \text { wenn } N_{1}(x y z) \in\{1,3\} \\ 0, \text { wenn } N_{1}(x y z) \in\{0,2\} \end{array}\right. \)
die binäre Ergebnisziffer der niedrigsten Stelle, die aus Addition der drei Argumente hervorgeht, während der binäre Übertrag in die nächste Stelle durch die Funktion
\( \gamma: Z_{2} \times Z_{2} \times Z_{2} \rightarrow Z_{2},(x, y, z) \mapsto\left\{\begin{array}{l} 1, \text { wenn } N_{1}(x y z)>1 \\ 0, \text { wenn } N_{1}(x y z) \leq 1 \end{array}\right. \)
berechnet wird.
Wir wollen nun die Kommutativität von \( \oplus_{n}^{0} \) beweisen. Dabei gehen wir strukturiert vor. Zeigen Sie zuerst die beiden folgenden hilfreichen Lemmata:
i) \( \forall x, y, z \in Z_{2}: \delta(x, y, z)=\delta(y, x, z) \)
(d.h., \( \delta \) ist kommutativ in den ersten beiden Argumenten).
ii) \( \forall x, y, z \in Z_{2}: \gamma(x, y, z)=\gamma(y, x, z) \)
(d.h. \( \gamma \) ist kommutativ in den ersten beiden Argumenten).
Der Beweis der Kommutativität von \( \oplus_{n}^{0} \) hängt auch von der Kommutativität von \( \oplus_{n}^{1} \) ab. Daher wollen wir eine stärkere Behauptung beweisen, die auch die Kommutativität von \( \oplus_{n}^{0} \) impliziert.
iii) Beweisen Sie: \( \forall n \in \mathbb{N}_{0}, \forall c \in Z_{2}, \forall w, v \in Z_{2}^{n}: w \oplus_{n}^{c} v=v \oplus_{n}^{c} w \). Verwenden Sie dazu vollständige Induktion über die Wortlänge \( |w|=|v|=n \).