Binärdarstellung < Analysis < Hochschule < Mathe < Vorhilfe
|
Hallo Zusammen,
| Aufgabe | | Zeigen Sie, daß die Binärdarstellung jeder natürlichen Zahl (auch 0) existiert, und eindeutig ist. |
Zur Existenz habe ich so argumentiert:
Sei $n [mm] \in \IN_0$. [/mm] Wir wollen zeigen, daß [m]\textstyle n = \sum_{i = 0}^k {a_i 2^i } ;\;a_i \in \left\{ {0,1} \right\}[/m] für ein bestimmtes $k [mm] \in \IN_0$ [/mm] gilt. Dazu stellen wir [mm] $n\!$ [/mm] als obere Summe dar und zwar durch folgenden Algorithmus:
[m]\begin{gathered}
{\texttt{summenDarstellung}}\left( n \right): \hfill \\
\quad {\texttt{if}}\left( {n = 2} \right): \hfill \\
\quad \quad {\texttt{multipliziere die so entstandenen geklammerten Summen}} \hfill \\
\quad \quad {\texttt{aus}}{\texttt{, so da{\ss} die }}2{\texttt{er}} - {\texttt{Potenzen }}{\texttt{``erhalten''}}{\texttt{ bleiben und wir}} \hfill \\
\quad \quad {\texttt{als Darstellung die obige Form }}{\textstyle\sum_{i = 0}^k {a_i 2^i}}{\texttt{ erhalten}}{\texttt{.}} \hfill \\
\quad \quad {\texttt{return }}{\textstyle\sum_{i = 0}^k {a_i 2^i}}\hfill \\
\quad {\texttt{if}}\left( {n\,{\texttt{gerade}}} \right): \hfill \\
\quad \quad {\texttt{stelle }}n\,{\texttt{als }}2^i z{\texttt{ dar für }}z,i \in \mathbb{N}_0 \hfill \\
\quad \quad {\texttt{summenDarstellung}}\left( z \right) \hfill \\
\quad {\texttt{else:}} \hfill \\
\quad \quad {\texttt{stelle }n\texttt{ als }}z + 2^0 {\texttt{ dar für }}z \in \mathbb{N}_0 \hfill \\
\quad \quad {\texttt{summenDarstellung}}\left( z \right) \hfill \\
\end{gathered}[/m]
Ich denke, daß dieser (rekursive) Algorithmus korrekt ist. Als Beweis für die Korrektheit sage ich, daß sich gerade und ungerade natürliche Zahlen auf dem Zahlenstrahl immer um 1 abwechseln, wodurch der Algorithmus jede Zahl entweder als Produkt mit einer 2 darstellen kann, oder aber er spaltet eine 1 ab und kann die "neue" Zahl dann ebenfalls als Produkt von 2 darstellen u.s.w. . Ich denke, es ist klar, daß wir durch diese Vorgehensweise irgendwann nur noch eine 2 zu betrachten haben und der Algorithmus terminiert.
Ich weiß im Moment nicht, wie man Eindeutigkeit und Existenz streng mathematisch beweisen könnte. Eigentlich müßte man hier irgendwie über eine Bijektion argumentieren, aber mir fällt es irgendwie leichter einen Algorithmus dazu anzugeben.
Vielen Dank!
Viele Grüße
Karl
|
|
| |
|
Zu Deinem Algorithmus sag' ich mal lieber nichts, weil ich da überhaupt keine Ahnung hab'.
Ich würde die Existenz per Induktion zeigen:
n=0 :
[mm] 0=0*2^{0}
[/mm]
n [mm] \to [/mm] n+1
Angenommen, es gibt für jede natürliche Zahl [mm] \le [/mm] n so eine Darstellung.
Betrachte jetzt n+1. Zu n+1 gibt es ein N [mm] \in \IN [/mm] mit [mm] n+1=2^{N}+r [/mm] mit
0 [mm] \le [/mm] r < [mm] 2^{N} \le [/mm] n+1. Also ist r [mm] \le [/mm] n und hat eine Darstellung als endliche Summe von Zweierpotenzen. ==> n+1 hat so eine Darstellung.
(Muß man gewiß schön aufschreiben und sich überlegen für r= 1+ [mm] \summe_{i=1}^{N-1}... [/mm] und für [mm] r=0+\summe_{i=1}^{N-1})
[/mm]
Für die Eindeutigkeit würde ich annehmen, daß es für ein n zwei verschiedene Darstellungen gibt und zeigen, daß die gleich sind.
Sei n= [mm] \summe_{i=0}^{N}a_{i}2^{i} [/mm] und n= [mm] \summe_{i=0}^{N}b _{i}2^{i} [/mm] und sei m der kleinste Index, für den sich die Koeffizienten unterscheiden. Dann ist (b [mm] _{m}-a_{m})=1
[/mm]
Betrachte die Differenz:
[mm] 0=\summe_{i=0}^{M}b _{i}2^{i} [/mm] - [mm] \summe_{i=0}^{N}a_{i}2^{i}=
[/mm]
[mm] =\summe_{i=0}^{M}(b _{i}-a_{i})2^{i}=\summe_{i=m}^{M}(b _{i}-a_{i})2^{i}=(b _{m}-a_{m})2^{m}+\summe_{i=m+1}^{M}(b _{i}-a_{i})2^{i}=2^{m}+\summe_{i=m+1}^{M}(b _{i}-a_{i})2^{i}=2^{m}(1+\summe_{i=m+1}^{M}(b _{i}-a_{i})2^{i-m})
[/mm]
[mm] ==>0=1+\summe_{i=m+1}^{M}(b _{i}-a_{i})2^{i-m}=1+\summe_{i=1}^{M}(b _{m+i}-a_{m+i})2^{i}=1+2\summe_{i=1}^{M}(b _{m+i}-a_{m+i})2^{i-1} [/mm] ==> 0 ist ungerade. Widerspruch. Also gibt es nicht zwei verschiedene Darstellungen.
Gruß v. Angela
|
|
|
| |
|
Hallo Angela,
Danke für deine Antwort! Ich habe leider noch ein Paar Verständnisprobleme was die Eindeutigkeit angeht. (Die Existenz scheine ich so nachzuvollziehen. Ich werde das dann nochmal selber versuchen.)
> [mm] \Rightarrow 0 = 1+\summe_{i=m+1}^{M}(b _{i}-a_{i})2^{i-m}=1+\summe_{i=1}^{M}(b _{m+i}-a_{m+i})2^{i}=1+2\summe_{i=1}^{M}(b _{m+i}-a_{m+i})2^{i-1} \Rightarrow 0[/mm] ist ungerade.
Wieso setzt Du hier gleich 0? Ich nehme an, weil Du als Ergebnis der Differenz gerade 0 rauskriegen willst, und dafür das zweite Produkt auf 0 kriegen mußt. Aber am Schluß folgerst Du dann irgendwie die 0:
> [mm]1+2\summe_{i=1}^{M}\left(b _{m+i}-a_{m+i}\right)2^{i-1} \Rightarrow 0[/mm]
Wieso darf man das hier?
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl!
> > [mm]\Rightarrow 0 = 1+\summe_{i=m+1}^{M}(b _{i}-a_{i})2^{i-m}=1+\summe_{i=1}^{M}(b _{m+i}-a_{m+i})2^{i}=1+2\summe_{i=1}^{M}(b _{m+i}-a_{m+i})2^{i-1} \Rightarrow 0[/mm]
> ist ungerade.
>
> Wieso setzt Du hier gleich 0?
Konntest Du diesem [mm] 0=\summe_{i=0}^{M}b _{i}2^{i} [/mm] - [mm] \summe_{i=0}^{N}a_{i}2^{i}=[...]=2^{m}(1+\summe_{i=m+1}^{M}(b _{i}-a_{i})2^{i-m})
[/mm]
in meinen vorherigen Ausführungen folgen?
Die Überlegung: wenn [mm] 2^{m} [/mm] mal "irgendwas" Null ist, muß "irgendwas"=0 sein. also [mm] 0=1+\summe_{i=m+1}^{M}(b _{i}-a_{i})2^{i-m}.
[/mm]
>Ich nehme an, weil Du als
> Ergebnis der Differenz gerade 0 rauskriegen willst, und
> dafür das zweite Produkt auf 0 kriegen mußt.
Ach, genau, das hast Du ja selbst richtig herausgefunden.
>Aber am Schluß
> folgerst Du dann irgendwie die 0:
>
> > [mm]1+2\summe_{i=1}^{M}\left(b _{m+i}-a_{m+i}\right)2^{i-1} \Rightarrow 0[/mm]
Nein, ich folgere "0 ist ungerade."
>
> Und wieso darf man das hier?
Weil ich eine Darstellung der null gefunden habe als 0=1+2*blabla.
Und weil 0 nicht ungerade ist, habe ich den erhofften Widerspruch.
Gruß v. Angela
|
|
|
| |
|
Hallo Angela,
> >Aber am Schluß
> > folgerst Du dann irgendwie die 0:
> >
> > > [mm]1+2\summe_{i=1}^{M}\left(b _{m+i}-a_{m+i}\right)2^{i-1} \Rightarrow 0[/mm]
>
> Nein, ich folgere "0 ist ungerade."
> >
> > Und wieso darf man das hier?
>
> Weil ich eine Darstellung der null gefunden habe als
> 0=1+2*blabla.
Dann muß [m]\textstyle\operatorname{blabla} = \sum_{i = 1}^M {\left( {b_{m + i} - a_{m + i} } \right)2^{i - 1} } = - \frac{1}{2}[/m] gelten, richtig? Aber wie sieht man hier, daß diese Summe [mm] $-\tfrac{1}{2}$ [/mm] ist?
> Und weil 0 nicht ungerade ist, habe ich den erhofften
> Widerspruch.
Bisher habe ich gedacht, der Widerspruch läge darin, daß wir nach der Subtraktion der beiden Summen überhaupt 0 rauskriegen (und nicht irgendeine andere natürliche Zahl). Der Widerspruch liegt doch darin, daß wir gerade 0 rauskriegen, obwohl wir davon ausgegangen sind, daß das nicht möglich ist.
Viele Grüße
Karl
|
|
|
| |
|
Hallo Karl,
ich versuche Dir jetzt zunächst einmal kurz die Idee meines Widerspruchs aufzuzeigen, ohne Rechnerei en detail:
Ich möchte zeigen, daß die Darstellung eindeutig ist.
Dazu nehme ich an, sie sei nicht eindeutig und führe dies zum Widerspruch.
Da sich bei "Zweideutigkeit" ein Widerspruch ergibt, kann die Darstellung nicht mehrdeutig sein. Also ist die Darstellung, sofern es eine gibt, eindeutig.
So, das war das Prinzip im Groben, für den Überblick.
Jetzt gehen wir etwas dichter heran.
Angenommen, ich hätte für n zwei Darstellungen A und B.
==> 0=n-n=A-B
==> ... ==> 0 ist ungerade.
Null ist aber nicht ungerade, also war meine Annahme, daß es für ein n zwei Darstellungen gibt, falsch.
Also gibt es für n höchstens eine Darstellung. Daß es eine gibt, wurde bei der Existenz gezeigt.
Wenden wir uns jetzt der ungeraden Null etwas genauer zu.
> > Nein, ich folgere "0 ist ungerade."
> > >
> > > Und wieso darf man das hier?
> >
> > Weil ich eine Darstellung der null gefunden habe als
> > 0=1+2*blabla.
>
> Aha, dann muß doch [m]\mathrm{blabla} = \sum\limits_{i = 1}^M {\left( {b_{m + i} - a_{m + i} } \right)2^{i - 1} } = - \frac{1}
> {2}[/m]
> gelten, richtig?
Wohl schon. Und ich bin mir sicher, daß man auch daraus einen Widerspruch erzeugen kann...
Aber wir wollen doch schnell fertig sein!
Fangen wir nochmal bei 0=1+2*blabla an. Wenn unser blabla eine ganze Zahl ist, ist 0 ungerade, einverstanden?
Jetzt gucken wir auf [m]\mathrm{blabla} = \sum\limits_{i = 1}^M {\left( {b_{m + i} - a_{m + i} } \right)2^{i - 1} } [/m] . Die a und b sind aus [mm] \IN [/mm] , und [mm] 2^{i - 1} [/mm] auch. Also ist blabla aus [mm] \IZ. [/mm]
Daher ist 0=1+2*blabla ungerade. Das ist der WIDERSPRUCH!!! 0 ist ja gar nicht ungerade! Alles folgte aus der irrigen Annahme, daß es zwei Darstellungen gibt. Also gibt es keine zwei Darstellungen.
> Aber wie sieht man denn hier, daß diese Summe [mm]-\tfrac{1}{2}[/mm] ist?
Das ist gut! Du willst ja einen Widerspruch. Wenn Dir also ein Grund einfällt, warum das keinesfalls [mm] $-\tfrac{1}{2}$ [/mm] sein kann, bist Du auf anderem Weg auch am Ziel...
Gruß v. Angela
|
|
|
| |
|
Hallo Angela,
Ich denke, ich habe den Widerspruch jetzt verstanden. 1+2*blabla ist ja gerade die Darstellung für eine ungerade Zahl und ich hab's nicht gesehen.
Aber eine Sache stört mich noch ... . Du hast ja selber gesagt, daß man auch zum Widerspruch kommen könnte, wenn man gezeigt hat, daß [mm] $\operatorname{blabla} [/mm] =: [mm] \xi [/mm] = [mm] -\tfrac{1}{2}$ [/mm] ist. Aber im ersten Widerspruch zeigst Du doch: [mm] $\xi \in \IZ$. [/mm] Ich finde diese Argumentationen deshalb irgendwie widersprüchlich. Dann müßte ja wegen der beiden Widersprüche [mm] $-\tfrac{1}{2} \in \IZ$ [/mm] gelten? Wieso schließen sich diese Argumentationen dann nicht gegenseitig aus?
Viele Grüße
Karl
|
|
|
| |
|
> Hallo Angela,
>
> Ich denke, ich habe den Widerspruch jetzt verstanden.
Mein erstes Erfolgserlebnis. Und der Tag ist noch soooooo lang!
> 1+2*blabla ist ja gerade die Darstellung für eine ungerade Zahl und ich hab's nicht gesehen.
>
> Aber eine Sache stört mich noch ... . Du hast ja selber
> gesagt, daß man auch zum Widerspruch kommen könnte, wenn
> man gezeigt hat, daß [mm]\operatorname{blabla} =: \xi = -\tfrac{1}{2}[/mm]
> ist. Aber im ersten Widerspruch zeigst Du doch: [mm]\xi \in \IZ[/mm].
Wunderbar, Du gibst Dir die Antwort selbst!!!!!
Du stellst fest [mm]\xi \in \IZ[/mm] und [mm]\mathrm \xi = -\bruch{1}{2}[/mm]. Da hast Du einen schönen, dicken Widerspruch. ==> es kann keine zwei Darstellungen geben. Alles bestens.
> ... Wieso schließen sich diese Argumentationen dann
> nicht gegenseitig aus?
Tun sie nicht. 1/2 ist keine ganze Zahl und Null ist nicht ungerade. Na und? Bei abstrusen Ideen kann man eben u.U. mehrere Widersprüche entdecken, und hier nähert sich die Mathematik dem Leben...
Falls Du nun wieder Erwarten immer noch verwirrt bist, mach es Dir einfach:
nimm einen der beiden Widersprüche und sei fröhlich.
Gruß v. Angela
|
|
|
| |
|
| Status: |
(Mitteilung) Reaktion unnötig  | | Datum: | 11:13 Mi 22.06.2005 | | Autor: | Karl_Pech |
Hallo Angela,
Danke für deine Hilfe!
Viele Grüße
Karl
![[user]](/images/smileys/user.gif "[user]")
|
|
|
|
