Invariante für das Zweierkomplement

Neue Frage »

regenbogen54 Auf diesen Beitrag antworten »
Invariante für das Zweierkomplement
Ich bin ein absoluter Laie was die beweisführung von mathematischen gleichungen betrifft und auch allgemein nicht der hellste. also bitte verzeiht falls meine fragen zu trivial gestellt sind-

ich habe folgende aufgabe erteilt bekommen:

In der Vorlesung wurde die Invariante für das n-Bit Zweierkomplement



vorgestellt.

Zeigen Sie die Korrektheit dieser invariante für alle natürlichen Zahlen aus dem Intervall



Hinweis: Nutzen Sie dabei die Definition des Zweierkomplements und überlegen Sie sich, wie Sie das Invertieren eines Bits mathematisch ausdrücken können.


Die vorlesungsfolie zu zweierkomplement habe ich mal als screenshot im anhang eingeblendet.

Das wäre super toll wenn mir jemand behilflich sein könnte. In der Vorlesung wurden bislang beweise nicht behandelt und ich habe gerade keinen blassen schimmer wie ich das machen soll. unglücklich

und was bedeutet bitte invarianz, invariante, invariante einfach ausgedrückt?
Steffen Bühler Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Willkommen im Matheboard!

Invarianz bedeutet Unveränderlichkeit. Hier ist damit die rechte Seite der zu beweisenden Gleichung gemeint, also das .

Denn es wird sich herausstellen, dass, egal welche n-stellige Dualzahl x Du auch nimmst: addierst Du das Zweierkomplement, wird immer herauskommen!

Schreib am besten zunächst die Zahl x in allgemeiner Summendarstellung hin. Die kennst Du ja, oder? Dann sehen wir weiter.

Viele Grüße
Steffen
regenbogen54 Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
danke, Sterffen das du dir die Zeit nimmst, mir zu helfen.



meinst du das etwa so?

stelligkeit, n-stellig - habe ich viel zu häufig jetzt zu lesen bekommen. was bedeutet das denn bitte? (einfach ausgedrückt) unglücklich
Steffen Bühler Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Zumindest das Summenzeichen meinte ich, ja. Allerdings noch etwas mehr...

Eine vierstellige Dezimalzahl ist z.B. die Zahl 4711. Sie hat vier Stellen. Die ganz rechte Stelle steht für die Einer, die daneben für die Zehner, dann die Hunderter und Tausender. Hier also die Summe aus 1 Einer, 1 Zehner, 7 Hunderter und 4 Tausender.

Als Summe eben . Kennst Du, oder?

Dann rüber ins duale Land. Da gibt es zwar nur Einsen und Nullen, aber auch hier gibt es vierstellige Zahlen, z.B. die 1001. Da wäre die Summendarstellung .

Nun formuliere das mal statt für 4 Stellen für n Stellen.

PS: lass Dir Zeit bis morgen, falls nicht jemand übernehmen will. Gute Nacht!
regenbogen54 Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Zitat:
Original von Steffen Bühler

Nun formuliere das mal statt für 4 Stellen für n Stellen.


ich habe jetzt lediglich die n über der summenformel eingefügt? ist das richtig?

.
Steffen Bühler Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Von 0 bis n sind es nicht n Stellen! Bei 4 Stellen liefen wir auch nur von 0 bis 3.

Außerdem müsstest Du jetzt alle a angeben, nicht nur vier. Das geht natürlich nicht, lass diese Koeffizienten also einfach weg, wir brauchen nur die Summe selbst.

Ansonsten siehe mein obiges PS.
 
 
regenbogen54 Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Zitat:
Original von Steffen Bühler
Von 0 bis n sind es nicht n Stellen! Bei 4 Stellen liefen wir auch nur von 0 bis 3.



verstehe ich gerade nicht. Bei 4 stellen wird von 0 bis 3 geliefert. Heißt doch auch das bei 6 stellen man von 0 bis 5 liefert. Wieso dann bitte nicht auch bei n stellen analog 0 bis n? Oder was sind konkret bitte "0 bis 3"? verwirrt
Elvis Auf diesen Beitrag antworten »

0 bis n kann man nicht liefern, wenn n=10000 oder 1000000000000 oder 2458455666448998766542345677 oder was auch immer ist.
regenbogen54 Auf diesen Beitrag antworten »

Zitat:
Original von Elvis
0 bis n kann man nicht liefern, wenn n=10000 oder 1000000000000 oder 2458455666448998766542345677 oder was auch immer ist.


dann vielleicht von n bis n+1'?

wieso kann man das nicht liefern. wenn n=10000 ist, würde es doch heißen das von 0 bis 10000 geliefert werden kann? verwirrt
Ulrich Ruhnau Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Zitat:
Original von regenbogen54
[I]In der Vorlesung wurde die Invariante für das n-Bit Zweierkomplement



vorgestellt.

Ich kann mich noch gut daran erinnern, wie ich mit 20 Jahren im Selbststudium Maschinensprache lernte auf einem Commodore-Pet. Im Zusammenhang mit Binärarithmetik lernte ich auch die Bedeutung des Zweierkomplimentes kennen. Man stellt das Zweierkompliment einer Zahl her, indem man im ersten Schritt durch eine Negation alle Bits umkippt. Dann wird noch 1 hinzuaddiert, damit man eine negative Zahl in Binärdarstellung erhält. Würde man nur die Bits umkippen, und dies zum ursprünglichen Wert addieren, hätte man nur Einsen. Wenn man jedoch 1 zur negierten Zahl hinzuaddiert, entsteht ein Wert, der mit der ursprünglichen Zahl addiert null ergibt. Die Eins als Übertrag fällt weg, weil 2^n mit n Bits nicht mehr darstellbar ist.
regenbogen54 Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Zitat:
Original von Ulrich Ruhnau
Zitat:
Original von regenbogen54
[I]In der Vorlesung wurde die Invariante für das n-Bit Zweierkomplement



vorgestellt.

Ich kann mich noch gut daran erinnern, wie ich mit 20 Jahren im Selbststudium Maschinensprache lernte auf einem Commodore-Pet. Im Zusammenhang mit Binärarithmetik lernte ich auch die Bedeutung des Zweierkomplimentes kennen. Man stellt das Zweierkompliment einer Zahl her, indem man im ersten Schritt durch eine Negation alle Bits umkippt. Dann wird noch 1 hinzuaddiert, damit man eine negative Zahl in Binärdarstellung erhält. Würde man nur die Bits umkippen, und dies zum ursprünglichen Wert addieren, hätte man nur Einsen. Wenn man jedoch 1 zur negierten Zahl hinzuaddiert, entsteht ein Wert, der mit der ursprünglichen Zahl addiert null ergibt. Die Eins als Übertrag fällt weg, weil 2^n mit n Bits nicht mehr darstellbar ist.


war das auf meinen letzten beitrag bezogen? verwirrt
regenbogen54 Auf diesen Beitrag antworten »

ich kriege es nicht hin. trotz grübeln. unglücklich
Steffen Bühler Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Zitat:
Original von regenbogen54
Bei 4 stellen wird von 0 bis 3 geliefert. Heißt doch auch das bei 6 stellen man von 0 bis 5 liefert. Wieso dann bitte nicht auch bei n stellen analog 0 bis n?


Liefern ist auch nett, aber eigentlich liefen die Zahlen. Augenzwinkern

Weil 3 eins weniger ist als 4. Und 5 ist eins weniger als 6. Preisfrage: was ist eins weniger als n?

Aber tröste Dich: ein Informatiker verzählt sich maximal um Eins.
regenbogen54 Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Zitat:
Original von Steffen Bühler
Zitat:
Original von regenbogen54
Bei 4 stellen wird von 0 bis 3 geliefert. Heißt doch auch das bei 6 stellen man von 0 bis 5 liefert. Wieso dann bitte nicht auch bei n stellen analog 0 bis n?



Weil 3 eins weniger ist als 4. Und 5 ist eins weniger als 6. Preisfrage: was ist eins weniger als n?



1-n? <---- (preisfrage bezogen)

also statt von 0, von 1 nach n?
Steffen Bühler Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Du musst mich nicht immer komplett zitieren, ich weiß, was ich geschrieben habe. Augenzwinkern

Das wäre eine Idee. Leider führt sie hier nicht zum Ziel, ich versuche es mal zu erklären.

Bleiben wir sicherheitshalber noch im Dezimalsystem, das ist vertrauter. Und schauen wir uns noch mal die 4711 an.

Diese Summendarstellung wurde nicht erfunden, um die Schüler zu ärgern! Sie stellt auch nichts Neues dar, sie beschreibt einfach das, was wir alle schon als Kinder kennen, mit Mathematik.

Denn, wie jedes Kind weiß, ohne drüber nachzudenken, ist . Es gibt hier also 4 Ziffern, eben 4/7/1/1, die nach diesem Schema verrechnet werden.

Die Summendarstellung soll das nun allgemein für beliebig viele Ziffern abgekürzt darstellen. Sonst müsste man nämlich umständlich erklären, das ganz hinten die Ziffer für die Einer steht, die links davon für die Zehner, die noch mal links davon für die Hunderter, also immer mal 10, bis zur ganz linken Ziffer, und alles addieren.

Eine große Erleichterung bieten hier nun die Zehnerpotenzen! Denn und so weiter. Dann bietet es sich doch förmlich an, der jeweiligen Hochzahl die Nummer der Ziffer zuzuordnen. Im 4711-Beispiel also ist , also drehen wir die Reihenfolge um und Ziffer 3 ist 4, Ziffer 2 ist 7, Ziffer 1 ist 1 und Ziffer 0 ist 1. Wenn wir jetzt noch statt z.B. Ziffer 3 einfach schreiben (Mathematiker sind furchtbar faul), kommen wir der Sache schon näher:

Mit den entsprechenden Werten für die vier Ziffern.

Denn jetzt ist das mit dem Summenzeichen ruckzuck hingeschrieben:

Und deshalb ist es günstiger, nicht von 1 bis n zu zählen, sondern von 0 bis...
regenbogen54 Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Hallo. Ich war leider gestern krank. Ich hoffe du bist noch über die Tage online.

Was meinst du bitte mit "wenn wir jetzt noch statt z.B Ziffer 3 einfach schreiben" Den letzten Teil habe ich leider nicht verstanden. und soll der letzte Satz von 0 bis ... die Aufgabe sein? Wink
Ulrich Ruhnau Auf diesen Beitrag antworten »

Zitat:
Original von regenbogen54
ich kriege es nicht hin. trotz grübeln. unglücklich

Angenommen, wir rechnen mit 1 Byte Genauigkeit (n=8) und wollen auf eine Addition zurückführen, d.h. wir rechnen . Dann bilden wir zuerst
und addieren anschließend:
Steffen Bühler Auf diesen Beitrag antworten »
RE: Invariante für das Zweierkomplement
Zitat:
Original von regenbogen54
Was meinst du bitte mit "wenn wir jetzt noch statt z.B Ziffer 3 einfach schreiben"

Dass wir statt dem langen „Ziffer 3“ das kurze schreiben.

Zitat:
Original von regenbogen54
soll der letzte Satz von 0 bis ... die Aufgabe sein?

Nein, dann geht es erst los. Wir müssen aber erst mal wissen, wo Gas und Bremse sind, bevor wir losfahren. Und die Summendarstellung ist genau das.
regenbogen54 Auf diesen Beitrag antworten »

das die summenformel eine verkürzte schreibweise ermöglichen soll war mir schon vorab eigenlich klar. allerdings weiß ich immer noch nicht wie ich das "ausdrücken" soll für meine aufgabe. verwirrt

n=8, also 0-8?
Steffen Bühler Auf diesen Beitrag antworten »

Nicht raten.

Für 2-stellige Zahlen geht es von 0 bis 1. Wir brauchen und .
Für 3-stellige Zahlen geht es von 0 bis 2. Wir brauchen , und .
Für 4-stellige Zahlen geht es von 0 bis 3. Wir brauchen , , und .
Wir brauchen also die Zehnerpotenzen bis zur Anzahl der Ziffern minus Eins.
Wenn diese Anzahl nun n genannt wird, brauchen wir die Zehnerpotenzen bis...
regenbogen54 Auf diesen Beitrag antworten »

fürs erste brauchen wir 10 und 99?
tut mir leid indem fall habe ich nicht den blassesten schimmer und muss halt raten. verwirrt

oder spielst dus auf binärzahl an? also wir brauchen 01 und 00?
Steffen Bühler Auf diesen Beitrag antworten »

Ich bin allmählich nicht mehr sicher, ob Du nicht doch ein Troll bist. Du besuchst eine Vorlesung auf der Uni, hast also Abi, somit auch Mathe bestanden und kannst mir nicht sagen, dass die Zahl n um Eins vermindert die Zahl n-1 ist.

Egal, dann nimm nun die allgemeine Summendarstellung einer Dualzahl und versuche mal gleich, das Zweierkomplement damit zu bilden.
regenbogen54 Auf diesen Beitrag antworten »

also mit verlaub: ich kann dir versichern ich bin gewiss kein troll. ich muss mich auch gerade entschuldigen, ich hatte die ganze zeit über das javascript ausgestellt weshalb ich die Latex ausdrücke gar nicht sehen konnte. Was du mir jetzt letzte Seite zeigen wolltest habe ich jetzt verstanden und eigentlich was ulrich oben zeigt, wusste ich ja auch schon zuvor. Bitziffern negieren bzw. invertieren.
Aber ich habe immer noch nicht den blassesten schimmer wie ich das so darstellen soll, das in der Summenformel die koeffizienten invertiert werden soll, falls du das meinst?

möglicherweise einfach die a_k negieren?

Steffen Bühler Auf diesen Beitrag antworten »

Ok, dann nehme ich das zurück. Ich hatte auch schon den Verdacht, dass Du das LaTeX nicht siehst, wollte auch schon was schreiben, dann fiel mir ein, dass Du ja selber schon Formeln gepostet hattest.

Genau, jetzt geht es ans Negieren, genauer ans Invertieren, das ist das Herzstück der Aufgabe.

Nur wirst Du es mit einem Minus davor nicht hinkriegen! Denn minus Null ist nicht Eins und minus Eins ist nicht Null.

Um weiterzukommen, brauchen wir jetzt aber eine Funktion, die aus Null eine Eins macht und umgekehrt. Die anderen Zahlen sind uns dabei egal, wir sind ja im Dualbereich.

Steht ja auch im Hinweis:
Zitat:
überlegen Sie sich, wie Sie das Invertieren eines Bits mathematisch ausdrücken können.


Wenn Du das geschafft hast, ist der Rest nicht mehr schwer.
Luftikus Auf diesen Beitrag antworten »

Vielleicht hilft angefügte Darstellung für 4 Bits.

zB.

3 + x = -1

x + 1 = -3

https://upload.wikimedia.org/wikipedia/c...2Komplement.svg
regenbogen54 Auf diesen Beitrag antworten »

für javascript musste ich leider jedes tab manuell zulassen. Heißt wenn eine sitzung endet bzw. ich das tab schließe und die seite erneut aufrufe, muss wieder javascript aktiviert werden. ich habe das aber jetzt für die seite zugelassen. entschuldigung.

kann man dann mit zwei variablen arbeiten für den fall 1, a-1 und für den fall 0, b+1 ?

edit oder kann man auch logische operatoren angeben wie z.B || oder &&?
Steffen Bühler Auf diesen Beitrag antworten »

Du meinst sowas wie


Das geht durchaus, wird aber vielleicht kompliziert, wenn Du nachher eine Zahl mit ihrem Zweierkomplement addieren musst, was für den Beweis benötigt wird.

Es geht einfacher! Besser überleg jetzt als nachher ins Schleudern zu kommen.

PS: Und Du brauchst noch nicht mal logische Operatoren, die beim Addieren ebenfalls verwirren.
regenbogen54 Auf diesen Beitrag antworten »

vielleicht mit den modulo? mit den resten als ergebnis? Wink

0 % 1 = 0 r1
1 % 1 = 1 r0
Steffen Bühler Auf diesen Beitrag antworten »

Wie gesagt, Du musst nachher addieren. Könnte dann schwierig werden.

Vielleicht aber auch nicht, probieren wir es mal.

Also: wir haben eine beliebige Dualzahl
Wie lautet die Summendarstellung des Zweierkomplements?
regenbogen54 Auf diesen Beitrag antworten »



so mit modulo?

oder kannst du mir bitte nicht die einfachere lösung zu summenformel für das zweierkomplement (inversion) verraten. Mir fällt sonst nur modulo und die falllösung ein.
Steffen Bühler Auf diesen Beitrag antworten »

Du summierst hier nur die Koeffizienten auf, die Zweierpotenzen müssen auch noch dazu! Außerdem hast Du hier nur den Ansatz zum Einserkomplement begonnen, für das Zweierkomplement fehlt noch ein entscheidender Schritt.

Modulo geht nicht, denn 0mod1=0 und 1mod1=1. Es geht wirklich mit den Grundrechenarten, überlege ein wenig. Das kriegst Du hin, betrachte es als Denksportaufgabe.

Zur Not verschieben wir die Überlegung zur Invertierung auf später und schreiben für die Invertierte von einfach erstmal .

Mach das doch mal, formuliere das korrekte Zweierkomplement und addiere es zur ursprünglichen Zahl.
regenbogen54 Auf diesen Beitrag antworten »

invertierung addieren mit der ursprünglichen zahl? also so? ich dachte lediglich die invertierung sei der entscheidene schritt?

Steffen Bühler Auf diesen Beitrag antworten »

Vielleicht hast Du meinen letzten Beitrag nicht vollständig gelesen:

Zitat:
Original von Steffen Bühler
Du summierst hier nur die Koeffizienten auf, die Zweierpotenzen müssen auch noch dazu! Außerdem hast Du hier nur den Ansatz zum Einserkomplement begonnen, für das Zweierkomplement fehlt noch ein entscheidender Schritt.
regenbogen54 Auf diesen Beitrag antworten »

also so?



edit:
Steffen Bühler Auf diesen Beitrag antworten »

Also noch mal:

Zitat:
Original von Steffen Bühler
wir haben eine beliebige Dualzahl
Wie lautet die Summendarstellung des Zweierkomplements?


Lies noch einmal genau, wie das Zweierkomplement gebildet wird. Und dann schreib es exakt hin. Addiert wird dann später.
regenbogen54 Auf diesen Beitrag antworten »

Zitat:
Original von Steffen Bühler
Also noch mal:

Zitat:
Original von Steffen Bühler
wir haben eine beliebige Dualzahl
Wie lautet die Summendarstellung des Zweierkomplements?


Lies noch einmal genau, wie das Zweierkomplement gebildet wird. Und dann schreib es exakt hin. Addiert wird dann später.


etwa so wie im skript auf der ausgangseite? Ich weiß es sonst nicht wie die summenformel im zusammenhang mit dem zweierkomplement dargestellt wird. Wikipedia zeigt auch nicht auf.




und



stellt doch die zweierpotenz dar oder etwa nicht?
Steffen Bühler Auf diesen Beitrag antworten »

Das Skript sagt doch: invertiere jede einzelne Ziffer der Dualzahl. Damit erhältst Du eine neue Dualzahl. Addiere Eins zu dieser neuen Dualzahl. Das ist dann das Zweierkomplement der ursprünglichen Zahl.

Nehmen wir mal wieder die gute alte 1001. Ziffern invertieren ergibt 0110. Eins addiert ergibt 0111.

1001 ist die Dezimalzahl 9. 0111 ist die Dezimalzahl 7. 7+9=16, und das ist . Da wir hier mit 4stelligen Dualzahlen gearbeitet haben, ist dieser Einzelfall bewiesen.

Aber Du musst es für alle vierstelligen Dualzahlen beweisen, und mehr noch, für alle Dualzahlen mit beliebig vielen Stellen. Das geht nur mit der Summendarstellung.

Verstehst Du die denn inzwischen? Wenn nicht, lies noch einmal genau durch, was ich alles geschrieben habe. Du musst damit klarkommen! Sag bitte genau, was unklar ist, es ist keine Schande. Vielleicht habt Ihr Summen damals in der Mittelstufe nur am Rande behandelt. Dann lernst Du es halt jetzt, dafür sind wir da.
regenbogen54 Auf diesen Beitrag antworten »

was heißt denn bitte der ursprünglichen zahl?

und wie soll ich die dualzahlen in der summenformel ausdrücken? alles was mir jetzt einfällt ist bloß die

ist die zweierpotenz mit der obergrenze n-1 nicht äquivalent zu der darstellung von (dualzahlen) n-beliebige stellen?
Steffen Bühler Auf diesen Beitrag antworten »

Die ursprüngliche Zahl ist die, von der das Zweierkomplement gebildet werden soll, in meinem Beispiel war das die 1001.

Dualzahlen in der Summendarstellung werden so ausgedrückt:



Dabei ist die Anzahl der Ziffern, also die Stellenzahl.

Die n einzelnen , also bis , sind die Ziffern der Dualzahl. Die sind also alle jeweils entweder 1 oder 0.

Um den Zahlenwert der Dualzahl zu berechnen, also herauszufinden, dass z.B. die Dualzahl 1001 den dezimalen Wert 9 hat, muss man nun jede einzelne Ziffer mit der dazugehörigen Zweierpotenz multiplizieren. Hier also 8+1=9.

Das alles muss Dir restlos klar sein, wenn Du die Aufgabe lösen willst! Es sollte auch in der Vorlesung behandelt worden sein, der Mittelstufenstoff kann ja nicht vorausgesetzt werden.

Und vorher können wir auch nicht weitermachen, denn wir würden aneinander vorbeireden.
regenbogen54 Auf diesen Beitrag antworten »

zur sicherheit frage ich das jetzt mal.

k wird bis n-1 dargestellt?

wieso steht am ende n-2 im exponenten bzw. im index?


mit welchem index bzw. exponenten fängt der vordere teil an. da hast du ja schon die zahlen eignesetzt.

also auch n-5, n-4, n-3, n-2 usw....? oder mit welchen n- fängt es an?

wenn nämlich das erste n= 0 ist, da k ja von 0 anfängt, dann würde es doch heißen n-1, also 0-1 = -1 im index bzw. exponenten??
Neue Frage »
Antworten »



Verwandte Themen

Die Beliebtesten »
Die Größten »
Die Neuesten »