Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I/Vorlesung 15/kontrolle

In dieser Vorlesung besprechen wir, wie sich im Dezimalsystem der Nachfolger, die Größergleichrelation und die Addition darstellen.

Der Nachfolger und die Ordnung im Dezimalsystem

Zuerst bemerken wir, dass das übliche Zählen (Einerstelle um ${}1$ erhöhen und eventuell mit den höheren Ziffern verarbeiten), das wir auch in der fünften Vorlesung als eine Zählmöglichkeit erwähnt hatten, korrekt ist. Dies ist eine zwar einfache, aber dennoch durchzuführende Überlegung, da für uns eine Ziffernfolge nicht durch die Reihenfolge im Zählprozess festgelegt ist, sondern über die Interpretation als gemischte Darstellung mit Summen, Produkten und Potenzen.

Bemerkung   Bemerkung 15.1 ändern

Das Dezimalsystem im Sinne eines Zählsystems, das die Dedekind-Peano-Axiome erfüllt, hat erstmal nichts mit Summe, Produkt, Potenzen zu tun, sondern ist allein durch die folgende Struktur (Menge mit Zählvorschrift) gegeben. Die Elemente sind von der Form

$a_{\ell }a_{\ell -1}\ldots a_{2}a_{1}a_{0},$

also einfach endliche geordnete Tupel von Ziffern (Ziffernfolgen) aus der Menge ${}\{0,1,2,3,4,5,6,7,8,9\}$. Dabei ist ${}0$ das Startelement. Der Zählvorgang wird durch den folgenden dezimalen Zähl-Algorithmus beschrieben.

1. Für einstellige Ziffern ${}\neq 9$ ist der Nachfolger gemäß der Reihenfolge ${}\{0,1,2,3,4,5,6,7,8,9\}$ festgelegt (dies ist das kleine Einsnacheins).
2. Für beliebige Zahlen im Zehnersystem mit einer letzten Ziffer ${}\neq 9$ ist der Nachfolger diejenige Ziffernfolge, bei der die letzte Ziffer durch den Nachfolger ersetzt wird und alle anderen Ziffern unverändert übernommen werden.
3. Für beliebige Zahlen im Zehnersystem mit einer Neun als letzter Ziffer sind sämtliche zusammenhängenden Neunen von hinten durch Nullen zu ersetzen und die von hinten erste von ${}9$ verschiedene Ziffer durch ihren Nachfolger zu ersetzen, die übrigen Ziffern bleiben gleich (wenn die Zahl ausschließlich aus Neunen besteht, ist dies so zu verstehen, dass man sich davor eine ${}0$ dazudenkt).

Lemma Lemma 15.2 ändern

Das Nachfolgernehmen im Dezimalsystem (gemischtes Dezimaldarstellungssystem)

stimmt mit dem Zählvorgang im Sinne von Bemerkung 15.1 (Dezimalzählsystem) überein.

Beweis

Wir gehen vom Dezimalsystem im Sinne einer gemischten Darstellung (Stellenwertsystem) aus und müssen zeigen, dass dort das Nachfolgernehmen, also die Addition mit ${}1$, die gleiche Wirkungsweise besitzt wie der Zählalgorithmus. Der Nachfolger einer im Dezimalsystem gegebenen natürlichen Zahl

${}n=a_{0}+a_{1}10+a_{2}10^{2}+\cdots +a_{\ell }10^{\ell }\,$

ist einfach

${\left(a_{0}+1\right)}+a_{1}10+a_{2}10^{2}+\cdots +a_{\ell }10^{\ell }.$

Aus diesem Ausdruck lässt sich aber noch nicht unmittelbar die Dezimaldarstellung dieser Zahl ablesen, da der Einerkoeffizient nicht unbedingt ${}\leq 9$ sein muss. Wenn ${}a_{0}\leq 8$ ist, so ist

${}a_{0}+1\leq 9\,$

und die Dezimalentwicklung des Nachfolgers liegt unmittelbar vor. Wenn hingegen ${}a_{0}=9$ ist, so geht es um die Zahl

${}{\begin{aligned}n+1&=(9+1)+a_{1}10+a_{2}10^{2}+\cdots +a_{\ell }10^{\ell }\\&=10+a_{1}10+a_{2}10^{2}+\cdots +a_{\ell }10^{\ell }\\&=(a_{1}+1)\cdot 10+a_{2}10^{2}+\cdots +a_{\ell }10^{\ell }.\end{aligned}}$

Erneut gilt, dass bei ${}a_{1}\leq 8$ die Dezimalentwicklung vorliegt, bei ${}a_{1}=9$ muss man wie zuvor weitermachen. Wenn die hintersten (niedrigststelligen) ${}s$ Ziffern ${}a_{0},\ldots ,a_{s-1}$ gleich ${}9$ sind und

${}a_{s}\neq 9\,$

(was den Fall einschließt, dass ${}n$ genau ${}s$ Ziffern hat, in welchem Fall ${}a_{s}$ als ${}0$ zu interpretieren ist), so erhält man den Nachfolger, indem man diese ${}s$ Neunen durch Nullen ersetzt und ${}a_{s}$ um ${}1$ erhöht. Es liegt also die Wirkungsweise des Zählalgorithmus vor.

$\Box$

Korollar Korollar 15.3 ändern

Es sei ${}k\in \mathbb {N} _{+}$. Eine natürliche Zahl ist genau dann ${}<10^{k}$,

wenn sie im Zehnersystem aus maximal ${}k$ Ziffern besteht.

Beweis

Dies folgt aus Lemma 15.2, da es für den Zählprozess klar ist, dass längere Ziffernfolgen größer sind (im Zählprozess später dran kommen).

$\Box$

Korollar Korollar 15.4 ändern

Es seien

${}m=a_{0}+a_{1}10+a_{2}10^{2}+\cdots +a_{k-1}10^{k-1}\,$

und

${}n=b_{0}+b_{1}10+b_{2}10^{2}+\cdots +b_{\ell -1}10^{\ell -1}\,$

zwei natürliche Zahlen im Zehnersystem (also mit ${}0\leq a_{i},b_{i}\leq 9$).

Dann ist

${}m>n\,$

genau dann, wenn

${}k>\ell \,$

oder wenn ${}k=\ell$ ist und wenn es ein ${}s$, ${}0\leq s<k$, derart gibt, dass

$a_{k-1}=b_{k-1},\ldots ,a_{s+1}=b_{s+1},a_{s}>b_{s}$

ist.

Beweis

Dies folgt aus Lemma 15.2. Vom Zählprozess her ist es klar, dass längere Ziffernfolgen größer sind. Bei gleichlangen Ziffernfolgen und übereinstimmender Anfangssequenz entscheidet die nächste Ziffer, welche Zahl im Zählprozess später dran kommt.

$\Box$

Schriftliches Addieren

Da sich die Addition zweier natürlicher Zahlen aus den Dedekind-Peano-Axiomen ergibt, gibt es in jeder Beschreibung der natürlichen Zahlen genau eine Möglichkeit, zu addieren. Ob diese algorithmisch geschickt oder kompliziert ist, hängt wesentlich von der gewählten Beschreibung ab. Wenn man durch Strichfolgen gegebene Zahlen miteinander addiert, so hängt man einfach die beiden Strichfolgen aneinander. Dies ist auf den ersten Blick ein sehr einfacher Vorgang. Wenn man es aber ernsthaft schriftlich durchführen möchte, so sieht man, dass es extrem mühsam ist, da man jeden Strich der einen Strichfolge einzeln an die andere anhängen muss.

Das schriftliche Addieren zweier natürlicher Zahlen im Zehnersystem ist aus der Schule bekannt. Man schreibt die beiden Zahlen untereinander so, dass die Einerpositionen übereinander stehen und addiert dann die beiden passenden Ziffern (im Sinne des kleinen Einundeins) von hinten nach vorne. Wenn das Ergebnis kleiner als ${}10$ ist, schreibt man diese Zahl hin und rückt nach links. Wenn das Ergebnis größer oder gleich ${}10$ ist, so schreibt man die Einerziffer dieser Summe an der Stelle hin und hat in der links liegenden Stelle einen zusätzlichen Übertrag von ${}1$ mitzuberücksichtigen. Dies ist insgesamt ein rekursives Verfahren, das wir kurz festhalten.

Verfahren  

Das schriftliche Addieren ${}m+n$ zweier natürlicher Zahlen, die im Dezimalsystem als

$m=a_{0}+a_{1}10+a_{2}10^{2}+\cdots +a_{k}10^{k}\,\,{\text{ und }}\,\,n=b_{0}+b_{1}10+b_{2}10^{2}+\cdots +b_{k}10^{k}$

gegeben sind (wobei auch vordere Nullen erlaubt sind), funktioniert folgendermaßen. Man berechnet die Dezimalziffern ${}c_{i}$ des Ergebnisses und die Überträge ${}d_{i+1}$ (mit dem Startwert ${}d_{0}=0$) sukzessive durch

${}c_{i}={\begin{cases}a_{i}+b_{i}+d_{i}\,,{\text{ falls }}a_{i}+b_{i}+d_{i}<10\,,\\a_{i}+b_{i}+d_{i}-10\,,{\text{ falls }}a_{i}+b_{i}+d_{i}\geq 10\,,\end{cases}}\,$

und

${}d_{i+1}={\begin{cases}0\,,{\text{ falls }}a_{i}+b_{i}+d_{i}<10\,,\\1\,,{\text{ falls }}a_{i}+b_{i}+d_{i}\geq 10\,.\end{cases}}\,$

Die Dezimaldarstellung der Summe ${}m+n$ ist ${}c_{k+1}c_{k}\ldots c_{2}c_{1}c_{0}$ (wobei ${}c_{k+1}=0$ sein kann). Es gilt stets

${}a_{i}+b_{i}+d_{i}=d_{i+1}10+c_{i}\,.$

Warum ist dieser Algorithmus richtig, warum liefert er das korrekte Ergebnis? Die Gewöhnung an dieses Verfahren verleitet dazu, diese Frage nicht ernst zu nehmen bzw. nicht zu verstehen. Das eben beschriebene schriftliche Addieren ist nicht die Definition der Addition, sondern eine algorithmische Ausführung der Addition in einem bestimmten Beschreibungssystem (nämlich dem Dezimalsystem) für die natürlichen Zahlen.

Der Ausgangspunkt der Addition der natürlichen Zahlen liegt in der disjunkten Vereinigung von endlichen Mengen, wir haben die Addition über die Nachfolgerabbildung eingeführt und bereits in Satz 8.14 gezeigt, dass sie mit dem Vereinigungskonzept übereinstimmt. Warum stimmt auch das schriftliche Addieren damit überein? Konkret: Man hat zwei Mengen ${}A$ und ${}B$ an Äpfeln und bestimmt für beide Mengen ihre Anzahl im Zehnersystem: diese seien ${}m$ und ${}n$. Dann schüttet man die Mengen zusammen, erhält die Menge ${}C=A\cup B$ und bestimmt für diese Menge die Anzahl im Zehnersystem: diese sei ${}k$. Warum kommt, wenn man die Zahlen ${}m$ und ${}n$ im Zehnersystem schriftlich addiert, ausgerechnet ${}k$ heraus?

Die beiden Zahlen seien als ${}m=a_{r}10^{r}+a_{r-1}10^{r-1}+\cdots +a_{2}10^{2}+a_{1}10+a_{0}$ und ${}n=b_{s}10^{s}+b_{s-1}10^{s-1}+\cdots +b_{2}10^{2}+b_{1}10+b_{0}$ gegeben, wobei die Ziffern alle zwischen ${}0$ und ${}9$ seien. Es sei ${}r\geq s$ und wir können sogar annehmen, dass ${}r=s$ ist, indem wir fehlende Ziffern in der zweiten Dezimalentwicklung durch Nullen auffüllen. Dann ist

${\left(a_{r}10^{r}+a_{r-1}10^{r-1}+\cdots +a_{2}10^{2}+a_{1}10+a_{0}\right)}+{\left(b_{r}10^{r}+b_{r-1}10^{r-1}+\cdots +b_{2}10^{2}+b_{1}10+b_{0}\right)}={\left(a_{r}+b_{r}\right)}10^{r}+{\left(a_{r-1}+b_{r-1}\right)}10^{r-1}+\cdots +{\left(a_{2}+b_{2}\right)}10^{2}+{\left(a_{1}+b_{1}\right)}10+{\left(a_{0}+b_{0}\right)}\,.$

Dies beruht auf dem Assoziativgesetz der Addition und dem Distributivgesetz. Achtung! Dieses Ergebnis ist nicht in der Dezimaldarstellung, da die vor den Zehnerpotenzen ${}10^{i}$ stehenden Zahlen ${}a_{i}+b_{i}$ nicht unbedingt kleiner als ${}10$ sein müssen. Man kann an dieser Stelle Bemerkung 14.5 anwenden und zu den „größeren“ Ziffern nach oben schaufeln. Dies ist aber nicht das Verfahren des schriftlichen Addierens.

Satz Satz 15.6 ändern

Das schriftliche Addieren im Zehnersystem ist korrekt.

Beweis

Die beiden Zahlen seien

$m=a_{0}+a_{1}10+a_{2}10^{2}+\cdots +a_{k}10^{k}\,\,{\text{ und }}\,\,n=b_{0}+b_{1}10+b_{2}10^{2}+\cdots +b_{k}10^{k},$

wobei wir eventuell auch vordere Nullen erlauben. Wir beweisen die Aussage durch Induktion über ${}k$. Bei ${}k=0$ handelt es sich um einstellige Zahlen und der Algorithmus ist korrekt. Hierzu macht man eine Fallunterscheidung abhängig davon, ob ${}a_{0}+b_{0}<10$ ist oder nicht. Es sei die Aussage nun für beliebige Zahlen, die beide maximal ${}k+1$ Ziffern haben, bewiesen, und seien zwei maximal ${}k+2$-stellige Zahlen gegeben. Es ist

${}{\begin{aligned}m+n&=\sum _{i=0}^{k+1}a_{i}10^{i}+\sum _{i=0}^{k+1}b_{i}10^{i}\\&=a_{k+1}10^{k+1}+\sum _{i=0}^{k}a_{i}10^{i}+b_{k+1}10^{k+1}+\sum _{i=0}^{k}b_{i}10^{i}\\&={\left(a_{k+1}+b_{k+1}\right)}10^{k+1}+\underbrace {\sum _{i=0}^{k}a_{i}10^{i}} _{=m'}+\underbrace {\sum _{i=0}^{k}b_{i}10^{i}} _{=n'}.\end{aligned}}$

Es seien ${}c_{i},d_{i}$ die durch den für ${}m$ und ${}n$ in Verfahren 15.5 beschriebenen Algorithmus festgelegten Zahlen. Die entsprechenden Zahlen für ${}m'$ und ${}n'$ stimmen damit bis auf eventuell ${}c_{k+1},c_{k+2},d_{k+2}$ überein, da diese nur von den Ziffern bis einschließlich ${}a_{k}$ und ${}b_{k}$ abhängen. Für ${}m'+n'$ bezeichnen wir mit ${}c_{k+1}'$ die entsprechende Ziffer, und zwar ist ${}c_{k+1}'=d_{k+1}$. Nach Induktionsvoraussetzung ist die Summe der beiden hinteren Summanden gleich

$\sum _{i=0}^{k}c_{i}10^{i}+c_{k+1}'10^{k+1}.$

Die Gesamtsumme ist somit gleich

${}{\begin{aligned}m+n&={\left(a_{k+1}+b_{k+1}\right)}10^{k+1}+c_{k+1}'10^{k+1}+\sum _{i=0}^{k}c_{i}10^{i}\\&={\left(a_{k+1}+b_{k+1}+c_{k+1}'\right)}10^{k+1}+\sum _{i=0}^{k}c_{i}10^{i}\\&={\left(a_{k+1}+b_{k+1}+d_{k+1}\right)}10^{k+1}+\sum _{i=0}^{k}c_{i}10^{i}\\&=c_{k+2}10^{k+2}+c_{k+1}10^{k+1}+\sum _{i=0}^{k}c_{i}10^{i}\\&=\sum _{i=0}^{k+2}c_{i}10^{i}.\end{aligned}}$

$\Box$

Beispiel Referenznummer erstellen

Wir erläutern den Induktionsschritt im Beweis zu Satz 15.6 anhand eines Beispiels. Wir wollen ${}62973+87515$ berechnen. Im Beweis wird diese Rechnung mit der Rechnung ${}2973+7515$ in Bezug gesetzt, es wird also die vordere Ziffer weggelassen und die Wirkungsweise des Algorithmus für die beiden Zahlenpaare wird verglichen. Die hinteren Ziffern ${}c_{0},c_{1},c_{2},c_{3}$ und die Überträge ${}d_{0},d_{1},d_{2},d_{3},d_{4}$ stimmen überein (und deshalb werden sie in der Bezeichnung auch nicht unterschieden). Für die kürzere Rechnung ist ${}c'_{4}=1$ und ${}d'_{5}=c'_{5}=0$ (letztere Zahlen kommen gar nicht vor), für die längere Rechnung ist aber ${}c_{4}=5$, ${}d_{5}=1$ und ${}c_{5}=1$.

Die Korrektheit des schriftlichen Addierens überträgt sich auf die Addition mehrerer Summanden in der Dezimaldarstellung. Man summiert wieder ziffernweise und schreibt die letzte Ziffer der Summe an der entsprechenden Stelle hin, ebenso den Übertrag. Dieser kann jetzt allerdings (ab zwölf Summanden) sogar größergleich ${}100$ sein, in diesem Fall muss man die Zehnerziffer wie zuvor um eins nach links schreiben und die Hunderterstelle um zwei nach links. Grundsätzlich kann man auch eine Summe mit beliebig vielen Summanden dadurch errechnen, dass man je zwei Summanden zusammenaddiert und somit die Anzahl der Summanden sukzessive verringert, doch ist das viel komplizierter.

Bemerkung   Referenznummer erstellen

Unter einem Algorithmus versteht man ein durch bestimmte Regeln festgelegtes (deterministisches) Verfahren, mit dem man in endlich vielen Schritten zu einem Ergebnis kommt. Ein Algorithmus bezieht sich auf eine Menge von möglichen Eingaben (Input) und liefert eine Ausgabe, das Ergebnis (Output). Ein Algorithmus berechnet den Wert einer Abbildung (einschließlich einer Verknüpfung), überprüft, ob eine Relation zwischen Elementen vorliegt oder nicht, findet die Lösung zu einer Gleichung. Die Regeln sind präzise Handlungsanweisungen und müssen alle möglichen Fälle abdecken. Ein Algorithmus kann prinzipiell durch eine Maschine durchgeführt werden.

Im Grundkurs werden wir die folgenden Algorithmen behandelt: Schriftliches Zählen (Nachfolgernehmen), schriftliches Vergleichen, schriftliches Addieren, schriftliches Multiplizieren, schriftliches Subtrahieren, schriftliches Dividieren (in einem Stellenwertsystem), der euklidische Algorithmus zur Bestimmung des größten gemeinsamen Teilers, das Gaußsche Eliminationsverfahren zur Lösung linearer Gleichungssysteme, das Invertierungsverfahren für Matrizen, das Heron-Verfahren.

Folgende Punkte sind charakteristisch für einen Algorithmus.

1. Es gibt eine relativ kleine Zahl von Einzelschritten, auf die im Durchlauf des Algorithmus immer wieder Bezug genommen wird.
2. Die Einzelschritte verwenden eine endliche Liste von gespeicherten elementaren Teilergebnissen (Datenbank).
3. Es muss irgendwie verbucht werden, auf welche Stelle sich der Einzelschritt bzw. dessen Ergebnis bezieht (Nummerierung, Indizierung, Anordnung).
4. Die Einzelschritte verwenden Fallunterscheidung, entlang welcher sich das Verfahren verzweigt.
5. Es werden Hilfszahlen zwischengespeichert und verwendet.

Beispielsweise werden im Additionsalgorithmus immer wieder zwei einstellige Zahlen miteinander addiert, dabei wird auf das kleine Einsundeins Bezug genommen und die Endziffer dieser Teilrechnung wird an der richtigen Stelle notiert. Die Weiterverarbeitung hängt davon ab, ob diese Einzelsummen kleiner als ${}10$ oder darüber sind, es werden Überträge notiert.

Bemerkung   Referenznummer erstellen

Von der Beschreibung eines Algorithmus, d.h. der präzisen Festlegung der einzelnen auszuführenden Rechenschritte, ist die Begründung für die Korrektheit des Algorithmus zu unterscheiden. Mit Korrektheit meint man, dass der Algorithmus wirklich das leistet, was er verspricht, also dass beispielsweise das schriftliche Additionsverfahren wirklich die beiden Zahlen addiert. Für diesen Nachweis braucht man einen mathematischen Beweis, der sowohl auf die zu berechnende mathematische Struktur (die Addition) als auch auf die Festlegungen des Algorithmus Bezug nimmt.

Ein wichtiger Aspekt bei vielen Algorithmen, der bei einem solchen Beweis hilft, ist ein Invarianzprinzip. Bei einem Algorithmus werden typischerweise mehrere Zwischenergebnisse berechnet und weiterverarbeitet. Insbesondere bei rekursiven Definitionen und bei der maschinellen Durchführung werden Zwischenergebnisse auch überschrieben. Dennoch ist zu jedem Zeitpunkt des Ablaufes die volle Information in einer bestimmten Weise in den Zwischenergebnissen repräsentiert. Wenn man beipielsweise zwei zehnstellige Zahlen schriftlich addiert, und die hinteren fünf Endziffern der Summe und den letzten Übertrag schon berechnet hat, so kann man die hinteren Endziffern der Summanden vergessen. Die Information, was berechnet werden soll, steckt vollständig (invariant) in den vorderen Ziffern der Summanden, den hinteren Ziffern der Summe und dem einen Übertrag drin.

Fußnoten