Mathe

Mit dem Symbol ℕ bezeichnen wir die natürlichen Zahlen. Hierunter verstehen wir alle positiven ganzen Zahlen, also 1, 2, 3, 4, 5, 6, …. Sie wissen bereits aus der Schule, dass es hiervon unendlich viele gibt.

Mit dem Symbol ℕ0 bezeichnen wir die natürlichen Zahlen inklusive der Null, also 0, 1, 2, 3, ….

Mit dem Symbol ℤ bezeichnen wir die ganzen Zahlen. Hierunter verstehen wir alle negativen ganzen Zahlen, alle positiven ganzen Zahlen und die Null, also …, −3, −2, −1, 0, 1, 2, 3, ….

Mit dem Symbol ℚ bezeichnen wir die rationalen Zahlen. Hierunter verstehen wir alle Zahlen, die sich als Bruch p/q mit einer ganzen Zahl p und einer ganzen Zahl q ≠ 0 darstellen lassen.

Mit dem Symbol ℝ bezeichnen wir die reellen Zahlen. Dies umfasst alle bisher genannten Zahlen, also sowohl die ganzen Zahlen als auch sämtliche Zahlen mit Nachkommastellen.

Mit dem Symbol ℝ+ bezeichnen wir die nichtnegativen reellen Zahlen, also alle reellen Zahlen, die größer oder gleich Null sind.

Eine Zahl ist gerade, falls sie die Struktur 2k hat bzw. ungerade, falls die Zahl die Struktur 2k+1 hat.

Sowohl in der Mathematik als auch in der Informatik arbeitet man häufig mit Variablen. Hierbei handelt es sich um Platzhalter, die bestimmte Werte annehmen können. Der Name dieser Variablen kann in der Regel frei gewählt werden. Häufig verwendet man dafür Kleinbuchstaben wie z. B. x, y, z, i oder j, aber auch Großbuchstaben oder Bezeichner mit mehr als einem Zeichen sind möglich. Häufig benutzt man auch Buchstaben aus dem griechischen Alphabet.

Der Wertebereich einer Variablen bestimmt, welche Werte diese Variable annehmen kann. Um auszudrücken, dass eine Variable x nur Zahlen einer bestimmten Zahlenmenge speichern kann, verwenden wir die Notation x ∈ M, wobei M für eine der oben genannten Zahlenmengen steht. Ausgesprochen wird dies als „x (ist) Element (aus) M“. Wir können z. B. mit x ∈ ℕ ausdrücken, dass x eine natürliche Zahl darstellt. Die Schreibweise x ∈ ℝ würde beispielsweise bedeuten, dass x eine reelle Zahl ist.

= zeigt die Gleichheit

≠ zeigt die Ungleichheit

:= weißt einen Wert zu “definitionsgemäß gleich”

∧ und

∨ oder

Bei direkten Beweisen beginnen wir mit bestimmten Voraussetzungen und leiten daraus schrittweise die Behauptung her. Wir zeigen die Richtigkeit der zu beweisenden Aussage dabei direkt. Mathematisch ausgedrückt haben direkte Beweise somit die Form A ⇒ B, wobei A die Voraussetzungen sind und B die Aussage darstellt, die bewiesen werden soll. Der Implikationspfeil ⇒ bedeutet dabei, dass B aus A folgt. Man spricht dies „A impliziert B“ oder „aus A folgt B“ oder „wenn A, dann B“ aus.

Gelegentlich ist es schwierig, für eine Behauptung B einen direkten Beweis der Form A ⇒ B zu finden. Manchmal kann es einfacher sein, die Aussage durch einen Widerspruch zu beweisen. Man spricht dabei auch von indirekten Beweisen. Hierzu geht man wie folgt vor: Es gelte die Voraussetzung A und man nimmt an, B sei falsch. Im Beweis zeigt man nun, dass die Annahme B sei falsch nicht stimmen kann. Daraus folgt, dass B richtig sein muss. Beweise durch Widerspruch basieren somit auf den Gesetzen der Logik. Sie stützen sich darauf, dass aus einer wahren Aussage A niemals eine falsche Aussage B folgen kann.

Eine weitere beliebte Beweismethode ist der Beweis durch Kontraposition. Dieser Ansatz basiert auf den Gesetzen der Logik. Anstatt eine Aussage der Form A ⇒ B zu beweisen, führt man einen Beweis für den negierten Ausdruck. Das bedeutet, man zeigt nicht, dass aus der Aussage A die Aussage B folgt, sondern stattdessen, dass aus der Aussage „nicht B“ die Aussage „nicht A“ folgt. Die Kontraposition, formal geschrieben als ¬B ⇒ ¬A, ist logisch äquivalent zu A ⇒ B und gelegentlich leichter zu beweisen als die ursprüngliche Aussage. Bei Beweisen durch Kontraposition nimmt man also an, dass ¬B gilt, und folgert daraus die Richtigkeit von ¬A.

Ein Beweis durch Ringschluss zeigt die Äquivalenz mehrerer Aussagen, ohne jede mögliche Implikation einzeln beweisen zu müssen.

Idee:

Statt alle Richtungen zwischen den Aussagen A1,A2,A3.... zu beweisen, zeigt man nur eine kreisförmige Kette von Implikationen: A1 ⇒ A2, A2 ⇒ A3, A3 ⇒ A1

Warum funktioniert das?

Weil man durch das Folgen der Implikationen jede Aussage aus jeder anderen herleiten kann.Beispiel: A3 folgt über A3 ⇒ A1 ⇒ A2 die Aussage A2

Vorteil: Der Aufwand bleibt gering, selbst wenn viele Aussagen beteiligt sind, da man nur eine geschlossene Implikationskette beweisen muss.

Die vollständige Induktion ist ein Verfahren, um Aussagen für alle natürlichen Zahlen zu beweisen. Sie funktioniert wie ein Domino-Effekt und besteht aus zwei Schritten:

1. Induktionsanfang

Man zeigt, dass die Aussage für den Startwert m gilt: A(m) ist wahr.

1. Induktionsschritt

Man nimmt an, dass die Aussage für ein beliebiges n ≥ m gilt (Induktionsvoraussetzung) und zeigt dann:A(n) 0⇒ A(n+1).

Warum funktioniert das?

• Aus der Wahrheit von A(m) folgt A(m+1).

• Daraus folgt A(m+2).

• Und so weiter für alle n ≥ m

• So beweist man die Aussage für unendlich viele Zahlen, ohne jede einzeln betrachten zu müssen.