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

Aus Wikiversity
Zur Navigation springen Zur Suche springen

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 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  

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

also einfach endliche geordnete Tupel von Ziffern (Ziffernfolgen) aus der Menge . Dabei ist das Startelement. Der Zählvorgang wird durch den folgenden dezimalen Zähl-Algorithmus beschrieben.

  1. Für einstellige Ziffern ist der Nachfolger gemäß der Reihenfolge festgelegt (dies ist das kleine Einsnacheins).
  2. Für beliebige Zahlen im Zehnersystem mit einer letzten Ziffer 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 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 dazudenkt).




Lemma  

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 , die gleiche Wirkungsweise besitzt wie der Zählalgorithmus. Der Nachfolger einer im Dezimalsystem gegebenen natürlichen Zahl

ist einfach

Aus diesem Ausdruck lässt sich aber noch nicht unmittelbar die Dezimaldarstellung dieser Zahl ablesen, da der Einerkoeffizient nicht unbedingt sein muss. Wenn ist, so ist

und die Dezimalentwicklung des Nachfolgers liegt unmittelbar vor. Wenn hingegen ist, so geht es um die Zahl

Erneut gilt, dass bei die Dezimalentwicklung vorliegt, bei muss man wie zuvor weitermachen. Wenn die hintersten (niedrigststelligen) Ziffern gleich sind und

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




Korollar  

Sei . Eine natürliche Zahl ist genau dann ,

wenn sie im Zehnersystem aus maximal 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).




Korollar  

Es seien

und

zwei natürliche Zahlen im Zehnersystem (also mit ).

Dann ist

genau dann, wenn

oder wenn ist und wenn es ein , , derart gibt, dass

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 im Zählprozess später dran kommt.



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 ist, schreibt man diese Zahl hin und rückt nach links. Wenn das Ergebnis größer oder gleich ist, so schreibt man die Einerziffer dieser Summe an der Stelle hin und hat in der links liegenden Stelle einen zusätzlichen Übertrag von mitzuberücksichtigen. Dies ist insgesamt ein rekursives Verfahren, das wir kurz festhalten.


Verfahren  

Das schriftliche Addieren zweier natürlicher Zahlen, die im Dezimalsystem als

gegeben sind (wobei auch vordere Nullen erlaubt sind), funktioniert folgendermaßen. Man berechnet die Dezimalziffern[1] des Ergebnisses und die Überträge (mit dem Startwert ) sukzessive durch

und[2]

Die Dezimaldarstellung der Summe ist (wobei sein kann).

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 und an Äpfeln und bestimmt für beide Mengen ihre Anzahl im Zehnersystem: diese seien und . Dann schüttet man die Mengen zusammen, erhält die Menge und bestimmt für diese Menge die Anzahl im Zehnersystem: diese sei . Warum kommt, wenn man die Zahlen und im Zehnersystem schriftlich addiert, ausgerechnet heraus?

Die zwei Zahlen seien als und gegeben, wobei die Ziffern alle zwischen und seien. Es sei und wir können sogar annehmen, dass ist, indem wir fehlende Ziffern in der zweiten Dezimalentwicklung durch Nullen auffüllen. Dann ist

Dies beruht auf dem Assoziativgesetz der Addition und dem Distributivgesetz. Achtung! Dieses Ergebnis ist nicht in der Dezimaldarstellung, da die vor den Zehnerpotenzen stehenden Zahlen nicht unbedingt kleiner als 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  

Das schriftliche Addieren im Zehnersystem ist korrekt.

Beweis  

Die beiden Zahlen seien

wobei wir eventuell auch vordere Nullen erlauben. Wir beweisen die Aussage durch Induktion über . Bei handelt es sich um einstellige Zahlen und der Algorithmus ist korrekt. Hierzu macht man eine Fallunterscheidung abhängig davon, ob ist oder nicht. Sei die Aussage nun für beliebige Zahlen, die beide maximal Ziffern haben, bewiesen, und seien zwei maximal -stellige Zahlen gegeben. Es ist

Es seien die durch den für und in Verfahren 15.5 beschriebenen Algorithmus festgelegten Zahlen. Die entsprechenden Zahlen für und stimmen damit bis auf eventuell überein, da diese nur von den Ziffern bis einschließlich und abhängen. Für bezeichnen wir mit die entsprechende Ziffer, und zwar ist . Nach Induktionsvoraussetzung ist die Summe der beiden hinteren Summanden gleich

Die Gesamtsumme ist somit gleich



Beispiel  

Wir erläutern den Induktionsschritt im Beweis zu Satz 15.6 anhand eines Beispiels. Wir wollen berechnen. Im Beweis wird diese Rechnung mit der Rechnung 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 und die Überträge stimmen überein (und deshalb werden sie in der Bezeichnung auch nicht unterschieden). Für die kürzere Rechnung ist und (letztere Zahlen kommen gar nicht vor), für die längere Rechnung ist aber , und .


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 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  

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[3] Zählen[4] (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 oder darüber sind, es werden Überträge notiert.


Bemerkung  

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
  1. In der üblichen schriftlichen Durchführung dieses Algorithmus wird diese Indizierung implizit durch die Stellung der Ziffern ausgedrückt.
  2. Die Überträge werden mit dem Index derjenigen Stelle versehen, wo sie verarbeitet werden, nicht, wo sie entstehen.
  3. Es ist kein Zufall, dass man hier von schriftlich spricht, obwohl es für die Wirkungsweise der Verfahren selbst unerheblich ist, ob sie im Kopf, auf einem Papier oder in einer Maschine durchgeführt werden. Der explizite Einsatz eines Algorithmus lohnt sich erst dann, wenn die Aufgabe eine gewisse Komplexität besitzt, die ohne schriftliche Hilfsmittel das menschliche Speichervermögen übersteigt. Unter halbschriftlichem Rechnen versteht man übrigens Verfahren, bei denen die Rechnungen zwar durch schriftliche Notizen unterstützt werden, aber ohne dass ein Algorithmus systematisch durchlauft wird.
  4. Dieses Zählen kann man auch gut mündlich durchführen.


<< | Kurs:Grundkurs Mathematik (Osnabrück 2018-2019)/Teil I | >>

PDF-Version dieser Vorlesung

Arbeitsblatt zur Vorlesung (PDF)