Mathematik für Informatik 1

Definition

Eine exakte Definition führt einen neuen Begriff oder ein neues Symbol so ein, dass man überall da, wo der Begriff oder das Symbol auftaucht, ihn oder es durch die definierende Beschreibung ersetzen könnte, ohne dass sich die Aussage inhaltlich ändert. Bei mathematischen Objekten werden die definierenden Eigenschaften auch gerne Axiome genannt.

Wenn ein einzelnes Objekt definiert wird (z. B. die Zahl $5$ als Nachfolger der Zahl $4$ ), dann bedeutet dies, dass einem bereits benennbaren Objekt ein neuer Name gegeben wird. Nach solch einer Definition gilt also eine Gleichheit zwischen dem durch den neuen Namen benannten Objekt und dem durch den alten Namen bezeichneten Objekt. Manchmal wird eine solche Definition in Formelschreibweise einfach durch diese Gleichung wiedergegeben; oft wird irgendwie auf den definitorischen Charakter hingewiesen, z. B. durch einen Doppelpunkt auf der zu definierenden Seite, also $5 ≔ 4 + 1$ oder $4 + 1 ≕ 5$ (dies ist eine eine aus der Informatik übernommenen, also recht neue Schreibweise). Andere verbreitete Versionen sind $5 =_{df} 4 + 1$ und $5 \equiv 4 + 1$ .

Wenn eine Relation definiert wird, wird dadurch eine Äquivalenz aufgestellt, z. B. zwischen der Aussage $A$ „die natürliche Zahl $m$ teilt die natürliche Zahl $n$ “ und der Aussage $B$ „ $m$ und $n$ sind natürliche Zahlen und es gibt eine natürliche Zahl $k$ mit $k \cdot m = n$ “. Hierfür gibt es die analoge Schreibweise der „definierenden ¨Aquivalenz“ $A : \Leftrightarrow B$ . Wenn klar ist, dass es sich um eine Definition handelt, spart man sich umgangssprachlich gerne das ”genau dann“ und sagt zum Beispiel „eine natürliche Zahl $m$ teilt eine natürliche Zahl $n$ , wenn es eine natürliche Zahl $k$ mit $k \cdot m = n$ gibt“ und versteht dies so, dass solch eine Definition immer umfassend sein soll, dass es also keine anderen Umstände gibt, unter denen eine natürliche Zahl eine andere teilt.

Daneben gibt es eine Art „beschreibende Definition“ (in der nicht-axiomatischen Mathematik), welche Eigenschaften von Objekten nahelegt, ohne sie genau festzulegen, und die keine exakte Definition ist. So zum Bespiel „Ein Punkt ist, was keine Teile hat“ bei Euklid oder „Unter einer ‚Menge‘ verstehen wir jede Zusammenfassung $M$ von bestimmten wohlunterschiedenen Objekten unserer Anschauung oder unseres Denkens (welche die ‚Elemente‘ von $M$ genannt werden) zu einem Ganzen“ bei Cantor.

Satz

Satz oder Proposition für ein mathematisches Ergebnis mit eigenständigem Interesse. Besonders wichtige Ergebnisse werden auch mit Hauptsatz oder Theorem bezeichnet (wobei die Abgrenzung oft unscharf ist und manche Autoren diesen Unterschied auch gar nicht machen). Wichtige Sätze tragen oft Namen („Hauptsatz der Differential- und Integralrechnung“, „Hilberts Nullstellensatz“, „Satz von Fubini“, …). Bei ganz großen Mathematikern (Euler, Gauß, …) ist die Zuordnung allerdings nicht immer eindeutig.

Lemma

Als Lemma oder Hilfssatz werden Zwischenergebnisse bezeichnet, die in mehreren Beweisen gebraucht werden oder der Übersichtlichkeit halber aus größeren Beweisen ausgegliedert werden. Daneben gibt es auch Lemmata mit Namen (Zorn’sches Lemma, Hensels Lemma, Lemma von Gauß, …). Dies sind zumeist Ergebnisse, die sich für die Entwicklung einer ganzen Theorie als grundlegend erwiesen haben (der Name „Lemma“ ist dann als Ehrenbezeichnung zu verstehen).

Korollar

Als Folgerung oder Korollar aus einem Satz wird ein Ergebnis bezeichnet, welches keinen eigenständigen Beweis mehr braucht, sondern dessen Gültigkeit sofort oder fast sofort aus dem vorher bewiesenen Satz eingesehen wird.

Beweis

Ein mathematischer Satz wird erst dann als gültig angesehen, wenn er bewiesen ist. In der Theorie gibt es eine exakte Definition davon, was ein Beweis ist, nämlich eine Abfolge von mathematischen Aussagen, die

entweder Axiome sind
oder Aussagen sind, die bereits bewiesen sind oder als bewiesen gelten
oder Aussagen sind, die aus vorherigen Aussagen in der Beweiskette durch einen korrekten logischen Schluss folgen. Hierfür dürfen nur gewisse, fest vorgegebene korrekte Schlussweisen verwendet werden.

In der Praxis kann man aber nur ganz einfache Beweise wirklich in dieser Form ausführen; zu komplizierteren Sätzen käme man aus Zeitgründen nicht und weil diese Art des Beweisens todlangweilig wäre. Stattdessen erlaubt man sich „größere“ Schritte, die aber nachvollziehbar sein müssen.

Was nun als „nachvollziehbar“ angesehen wird, hängt sehr von der Situation ab. In der Praxis gibt es somit keine klaren Kriterien dafür, was ein gültiger Beweis ist. Man könnte vielleicht sagen, dass ein akzeptierter Beweis dann vorliegt, wenn die relevanten Personen davon überzeugt sind, dass man ihn in die oben beschriebene theoretische Form eines Beweises bringen könnte. Ob ein Beweis akzeptiert wird oder nicht, hängt also davon ab, wer ihn vorlegt und wer ihn beurteilt. Insbesondere wird man von Anfänger:innen mehr und ausführlichere Zwischenschritte verlangen als von etablierten Mathematiker:innen; ebenso wird man in einer Vorlesung anders beweisen als in einem Fachartikel.

Einen Beweis muss man außerdem verteidigen können: Wenn jemand einen Beweisschritt anzweifelt (und sei es nur aus didaktischen Gründen), dann muss man in der Lage sein, immer feinere Zwischenschritte einfügen zu können, letztendlich bis auf die Ebene des theoretischen Beweisbegriffs hinab.

Diese Definitionen basieren auf dem Skript von Markus Junker der Albert-Ludwigs-Universität Freibug, Kapitel 4 „Mathematische Terminologie“, welches insbesondere für weitere Begriffe einen Blick wert ist.

Grundlagen

Mathematische Logik

Eine Aussage ist ein umgangssprachlicher Satz, der entweder wahr (1) oder falsch (0) ist.

Alle Studenten sind schlau … ist eine Aussage.
Herzlichen Glückwunsch … ist keine Aussage.

Ein Ausdruck der Form „ $x + 7 = 28$ “ ist eine Aussageform, die zu einer wahren oder falschen Aussage wird, wenn $x$ durch eine konkrete Zahl substituiert wird.

Aussagen $a, b, c, \dots$ können durch folgende Junktoren

$\neg$: nicht
$\land$: und
$\lor$: oder
$\to$: folgt
$\leftrightarrow$: äquivalent

verknüpft werden. Wir vereinbaren dabei:

$a$	$b$	$\neg a$	$a \land b$	$a \lor b$	$a \to b$	$a \leftrightarrow b$
$0$	$0$	$1$	$0$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$1$	$1$	$0$	$1$	$1$	$1$	$1$

Hierbei können $a, b$ selbst Verknüpfungen von Aussagen sein.

Äquivalente Ausdrücke sind solche mit gleicher Wahrheitstafel, wie zum Beispiel $a \to b$ und $\neg a \lor b$ , im Zusammenhang

(a \to b) \equiv (\neg a \lor b)

denn wir ermitteln

$a$	$b$	$\neg a$	$\neg a \lor b$	$a \to b$
$0$	$0$	$1$	$1$	$1$
$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$1$	$1$

Es gelten die Distributivgesetze der Aussagenlogik

\begin{matrix} a \land (b \lor c) & \equiv & (a \land b) \lor (a \land c) \\ a \lor (b \land c) & \equiv & (a \lor b) \land (a \lor c) \end{matrix}

sowie die de Morganschen Regeln der Aussagenlogik

\begin{matrix} \neg (a \land b) & \equiv & \neg a \lor \neg b \\ \neg (a \lor b) & \equiv & \neg a \land \neg b \end{matrix}

TODO/Übungsblatt

Eine Tautologie ist eine Aussage, die für jede Belegung ihrer freien Variablen stets wahr ist.

Satz vom ausgeschlossenen Dritten: $a \lor \neg a$
Satz vom Widerspruch: $\neg (a \land \neg a)$
Satz von der doppelten Verneinung: $\neg (\neg a) \to a$
Satz von der Kontraposition: $(a \to b) \leftrightarrow (\neg b \to \neg a)$

Sei nun $X$ eine „Menge“ von Elementen/Variablen. Ist $x$ Element von $X$ , so schreiben wir $x \in X$ . Wir führen folgende Quantoren ein:

Allquantor	$\forall x \in X$	„für alle Elemente $x$ aus $X$ “
Existenzquantor	$\exists x \in X$	„es gibt ein Element $x$ aus $X$ “

Eine Funktion

f : Ω \to ℝ

, die in einem Punkt

x_{0} \in Ω

stetig ist, genügt nach Definition

\forall ε > 0 \exists δ (ε) > 0 \forall x \in Ω (| x - x_{0} | < δ (ε) \to | f (x) - f (x_{0}) | < ε)

Quantoren werden wie folgt negiert ( $p (x)$ bedeute eine Aussage

\begin{matrix} \neg \forall x p (x) & \equiv & \exists x \neg p (x) \\ \neg \exists x p (x) & \equiv & \forall x \neg p (x) \end{matrix}

Als Übung werden wir die Definition der Stetigkeit aus dem letzten Beispiel negieren. TODO

Mengenlehre

Eine Menge $M$ charakterisieren wir auf zwei Arten:

entweder durch Angabe ihrer Elementen $m_{1}, m_{2}, \dots$ , im Zusammenhang $M = {m_{1}, m_{2}, \dots}$ wobei die Reihenfolge der Elemente nicht wichtig ist und Elemente nicht mehrfach angegeben werden,
oder durch die Angabe einer definierenden Eingenschaft $p (x)$ , das heißt $M = {x \in X : p (x)}$

Die Menge $M = {1}$ besitzt $1$ als einziges Element.
Die Menge $M = {1, {1}}$ besitzt die Elemente $1$ und ${1}$ .
Es ist ${x \in ℝ : x^{2} = 2} = {\sqrt{2}, - \sqrt{2}}$ .
Es ist ${n \in ℕ : 2^{n} < n^{2}} = {3}$ .

Es existiert genau eine leere Menge $\emptyset$ , die überhaupt kein Element enthält. Sie ist Teilmenge jeder Menge. Insbesondere ist $\emptyset = {x \in X : p (x)}$ falls $p (x)$ für kein $x \in X$ wahr ist. Jede andere Menge besitzt wenigstens ein Element.

Es seien $A, B$ zwei beliebige Mengen. Wir setzen

$A = B$ ,	falls $x \in A \leftrightarrow x \in B$	„ $A$ gleich $B$ “
$A \subset B$ ,	falls $x \in A \to x \in B$	„ $A$ Teilmenge $B$ “
$A ⊊ B$ ,	falls $A \subset B$ und $A \neq B$	„ $A$ echte Teilmenge $B$ “

Beachte also:

A = B

genau dann, wenn

A \subset B

und

B \subset A

Weiter setzen wir

Vereinigung: $A \cup B ≔ {x : x \in A \lor x \in B}$
Durchschnitt: $A \cap B ≔ {x : x \in A \land x \in B}$
Differenz: $A ∖ B ≔ {x : x \in A \land x \notin B}$

Es gelten die Distributivgesetze der Mengenlehre

\begin{matrix} A \cap (B \cup C) & = & (A \cap B) \cup (B \cap C) \\ A \cup (B \cap C) & = & (A \cup B) \cap (B \cup C) \end{matrix}

ist ferner

X

eine „Obermenge“ von

A, B

mit

A, B \subset X

, so gelten die de Morganschen Regeln der Mengenlehre

\begin{matrix} X ∖ (A \cup B) & = & (X ∖ A) \cap (X ∖ B) \\ X ∖ (A \cap B) & = & (X ∖ A) \cup (X ∖ B) \end{matrix}

Wir zeigen die erste Behauptung:

\begin{matrix} x \in A \cap (B \cup C) & \to & x \in A & \land & x \in B \cup C \\ \to & x \in A & \land & (x \in B \lor x \in C) & Definition: Vereinigung \\ \to & (x \in A \land x \in B) & \lor & (x \in A \land x \in C) & Distributivgesetze der Mengenlehre \\ \to & (x \in A \cap B) & \lor & (x \in A \cap C) & Definition: Durchschnitt \\ \to & x \in(A \cap B) & \cup & (A \cap C) & Definition: Vereinigung \end{matrix}

Hierbei kann aber

x \in A \cap (B \cup C)

beliebig gewöhlt werden, dass heißt es folgt

A \cap (B \cup C) = (A \cap B) \cup (B \cap C)

Die umgekehrte Inklusion

A \cup (B \cap C) = (A \cup B) \cap (B \cup C)

zeigt man analog. Es folgt die Behauptung. q.e.d.

Wir betrachten nun Abbildungen zwischen Mengen.

Eine Abbildung

f : A \to B

heißt

surjektiv,: wenn zu jedem $b \in B$ ein $a \in A$ existiert mit $f (a) = b$
injektiv,: wenn die Gleichung $f (a) = b$ zu $b \in B$ höchstens eine (oder auch gar keine) Lösung besitzt
bijektiv,: wenn sie sujektiv und injektiv ist.

Eine bijektive Abbildung $f : A \to B$ ordnet jedem $a \in A$ genau ein $b \in B$ zu, und umgekehrt existiert zu jedem $b \in B$ genau ein $a \in A$ mit $f (a) = b$ .

Es existiert also die Inverse $f^{- 1} : B \to A$ mit den Eigenschaften

$f^{- 1} \circ f (a) ≔ f^{- 1} (f (a)) = a$	für alle $a \in A$
$f \circ f^{- 1} (b) ≔ f (f^{- 1} (b)) = b$	für alle $b \in B$

Zwei Mengen

A

und

B

heißen gleichmächtig, wenn es eine Bijektion (bijektive Abbildung)

f : A \to B

gibt.

Es sind

A = {1, 2}

und

B = {x, y}

gleichmächtig mit der Bijektion

f : A \to B

vermöge

\begin{matrix} f (1) = x & f^{- 1} (x) = 1 \\ f (2) = y & f^{- 1} (y) = 2 \end{matrix}

Die Mengen

{1, 2}

und

{x, y, z}

sind nicht gleichmächtig.

Unter der Potenzmenge

𝒫 (A)

einer Menge

A

verstehen wir die Menge aller Teilmengen von

A

Zur Potenzmenge gehören insbesondere auch die leere Menge $\emptyset$ und $A$ selbst.

Es ist

𝒫 ({1, 2}) = {\emptyset, {1}, {2}, {1, 2}}

Es sei

A

eine endliche Menge mit

n > 0

Elementen, also etwa

A = {a_{1}, a_{2}, \dots, a_{n}}

. Dann gilt

| 𝒫 (A) | = 2^{n} > n

für die Zahl der Elemente von

𝒫 (A)

Nach einem Satz von Cantor gilt sogar allgemein, dass $𝒫 (M)$ stets „mächtiger“ ist, als eine beliebige Menge $M$ .

Zahlenbereiche

Die reellen Zahlen

Sie kennen die folgenden Zahlenbereiche

$ℕ$ - natürliche Zahlen: $0, 1, 2, 3, 4, \dots$
$ℤ$ - ganze Zahlen: $\dots, - 4, - 3, - 2, - 1, 0, 1, 2, 3, 4, \dots$
$ℚ$ - rationale Zahlen: $ℕ, ℤ, - \frac{3}{2}, \frac{1}{4}, \frac{2}{2}, \dots$
$ℝ$ - reelle Zahlen: $ℕ, ℤ, ℚ, e, π, \dots$

Wir wollen die Rechenregeln in $ℝ$ wiederholen.

Regeln der Addition

Kommutativgesetz der Addition: $x + y = y + x$ für alle $x, y \in ℝ$
Assoziativgesetz der Addition: $(x + y) + z = x + (y + z) = x + y + z$ für alle $x, y, z \in ℝ$
Neutrales Element der Addition: Es gibt genau eine $0 \in ℝ$ mit $x + 0 = x$ für alle $x \in ℝ$ .
Inverses Element der Addition: Zu jedem $x \in ℝ$ gibt es genau ein $- x \in ℝ$ mit $x + (- x) = 0$ .

Im Falle des Inversen Elements der Addition schreiben wir

x + (- x) = x - x

Regeln der Multiplikation

Kommutativgesetz der Multiplikation: $x \cdot y = y \cdot x$ für alle $x, y \in ℝ$
Assoziativgesetz der Multiplikation: $(x \cdot y) \cdot z = x \cdot (y \cdot z) = x \cdot y \cdot z$ für alle $x, y, z \in ℝ$
Neutrales Element der Multiplikation: Es gibt genau eine $1 \in ℝ ∖ {0}$ mit $x \cdot 1 = x$ für alle $x \in ℝ$ .
Inverses Element der Multiplikation: Zu jedem $x \in ℝ ∖ {0}$ gibt es genau ein $x^{- 1} \in ℝ$ mit $x \cdot x^{- 1} = 1$ .

Beim Inversen Element der Multiplikation schreiben wir

x^{- 1} = \frac{1}{x}

Distributivgesetz

x \cdot (y + z) = x \cdot y + x \cdot z

für alle

x, y, z \in ℝ

Hierzu kann man unter anderem folgende weitere Regeln ableiten:

$a$	$b$	$\neg a$	$a \land b$	$a \lor b$	$a \to b$	$a \leftrightarrow b$
$0$	$0$	$1$	$0$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$1$	$1$	$0$	$1$	$1$	$1$	$1$

$a$	$b$	$\neg a$	$\neg a \lor b$	$a \to b$
$0$	$0$	$1$	$1$	$1$
$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$1$	$1$

$a$	$b$	$\neg a$	$a \land b$	$a \lor b$	$a \to b$	$a \leftrightarrow b$
$0$	$0$	$1$	$0$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$1$	$1$	$0$	$1$	$1$	$1$	$1$

$a$	$b$	$\neg a$	$\neg a \lor b$	$a \to b$
$0$	$0$	$1$	$1$	$1$
$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$1$	$1$

$a$	$b$	$\neg a$	$a \land b$	$a \lor b$	$a \to b$	$a \leftrightarrow b$
$0$	$0$	$1$	$0$	$0$	$1$	$1$
$0$	$1$	$1$	$0$	$1$	$1$	$0$
$1$	$0$	$0$	$0$	$1$	$0$	$0$
$1$	$1$	$0$	$1$	$1$	$1$	$1$

$a$	$b$	$\neg a$	$\neg a \lor b$	$a \to b$
$0$	$0$	$1$	$1$	$1$
$0$	$1$	$1$	$1$	$1$
$1$	$0$	$0$	$0$	$0$
$1$	$1$	$0$	$1$	$1$