XOR < Algor.+Datenstr. < Theoretische Inform. < Hochschule < Informatik < Vorhilfe
|
| Status: |
(Frage) beantwortet  | | Datum: | 13:46 Sa 06.02.2010 | | Autor: | etoxxl |
| Aufgabe | Beweise, dass die durch f gegebene Abbildung den Wertebereich von int bijektiv auf sich selbst abbildet.
int f(int x) {
int i;
for(i=0;i<16;i++) x^=i;
return x;
}
|
Mein Lösungsansatz ist:
Zu zeigen:
(x ^ 0) ^ 1 ) ^ 2 ) ^ ... ) ^ 15 = x
Angenommen die Behauptung
(x ^ 0) ^ 1 ) ^ 2 ) ^ ...) ^ 15 = x
ist richtig:
XOR Verknüpfung von rechts mit der Reihenfolge 15,..,0:
(x ^ 0) ^ 1) ^ 2) ^ ...) ^ 15) ^ 15 = x ^ 15
(=) (x ^ 0) ^ 1) ^ 2) ^ ...) ^ 14 = x ^ 15
...
(=) x = (x ^ 15) ^ 14) ^ ...) ^ 0
=> (x ^ 0) ^ 1) ^ 2) ^ ...) ^ 15 = (x ^ 15) ^ 14) ^ ...) ^ 0
XOR ist assoziativ, also ist das eine wahre aussage
und damit wird x auf x abgebiltet und f(x)=x ist bijetiv.
Ist die Argumentation so ok?
|
|
| |
|
| Status: |
(Antwort) fertig  | | Datum: | 19:25 Sa 06.02.2010 | | Autor: | felixf |
Hallo!
> Beweise, dass die durch f gegebene Abbildung den
> Wertebereich von int bijektiv auf sich selbst abbildet.
>
> int f(int x) {
> int i;
> for(i=0;i<16;i++) x^=i;
> return x;
> }
>
> Mein Lösungsansatz ist:
>
> Zu zeigen:
> (x ^ 0) ^ 1 ) ^ 2 ) ^ ... ) ^ 15 = x
Dies ist hier der Fall. Es wuerde allerdings auch reichen zu zeigen, dass $f [mm] \circ [/mm] f$ die Identitaet ist, also dass fuer alle $x$ gilt $f(f(x)) = x$. Daraus folgt, dass $f$ bijektiv ist.
> Angenommen die Behauptung
> (x ^ 0) ^ 1 ) ^ 2 ) ^ ...) ^ 15 = x
> ist richtig:
Damit solltest du keinen Beweis anfangen. Du musst doch gerade zeigen, dass dies stimmt.
> XOR Verknüpfung von rechts mit der Reihenfolge 15,..,0:
> (x ^ 0) ^ 1) ^ 2) ^ ...) ^ 15) ^ 15 = x ^ 15
> (=) (x ^ 0) ^ 1) ^ 2) ^ ...) ^ 14 = x ^ 15
> ...
> (=) x = (x ^ 15) ^ 14) ^ ...) ^ 0
Ok.
> => (x ^ 0) ^ 1) ^ 2) ^ ...) ^ 15 = (x ^ 15) ^ 14) ^ ...)
> ^ 0
Ja, aber was bringt dir das?
> XOR ist assoziativ, also ist das eine wahre aussage
Du hast aus einer Aussage, deren Wahrheitsgehalt du nicht kennst (bzw. die du zeigen willst), eine wahre Aussage gefolgert. So what? Damit hast du gar nichts gezeigt.
Benutze doch mal die Assoziativitaet, um f(x) = x ^ (0 ^ 1 ^ 2 ^ ... ^ 15) zu zeigen. Dann rechne 0 ^ 1 ^ ... ^ 15 aus. Ist dies 0, so steht da f(x) = x ^ 0 = x.
LG Felix
|
|
|
|
