0 Daumen
99 Aufrufe

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 \).


Avatar von

Ein anderes Problem?

Stell deine Frage

Willkommen bei der Stacklounge! Stell deine Frage einfach und kostenlos

x
Made by a lovely community