# Grundlagen der Mathematik: Zusammenfassung – Serlo „Mathe für Nicht-Freaks“

## Logik

### Wahrheitstabellen der Junktoren

Wahrheitstabelle: Negation
${\displaystyle A}$ ${\displaystyle \neg A}$
${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {W} }$
${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {F} }$
Wahrheitstabelle: Konjunktion
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\land B}$
${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {F} }$
${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {F} }$
${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {F} }$
${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$
Wahrheitstabelle: Disjunktion
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\lor B}$
${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {F} }$
${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$
${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {W} }$
${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$
Wahrheitstabelle: Implikation
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\Rightarrow B}$
${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {W} }$
${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$
${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {F} }$
${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$
Wahrheitstabelle: Äquivalenz
${\displaystyle A}$ ${\displaystyle B}$ ${\displaystyle A\Leftrightarrow B}$
${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {W} }$
${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {F} }$
${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {F} }$ ${\displaystyle \mathrm {F} }$
${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$ ${\displaystyle \mathrm {W} }$

### Tautologien

Name der Umformungsregeln Tautologie Bedeutung
Assoziativgesetze ${\displaystyle (A\lor B)\lor C\Leftrightarrow A\lor (B\lor C)}$ Bei der Disjunktion und bei der Konjunktion ist es egal, in welcher Weise die einzelnen Teilaussagen verknüpft werden.
${\displaystyle (A\land B)\land C\Leftrightarrow A\land (B\land C)}$
Kommutativgesetze ${\displaystyle (A\lor B)\Leftrightarrow (B\lor A)}$ Bei der Disjunktion und bei der Konjunktion ist es egal, in welcher Reihenfolge die einzelnen Teilaussagen verknüpft werden.
${\displaystyle (A\land B)\Leftrightarrow (B\land A)}$
Distributivgesetze ${\displaystyle A\lor (B\land C)\Leftrightarrow (A\lor B)\land (A\lor C)}$ Eine Disjunktion kann in eine Konjunktion reingezogen werden und umgekehrt.
${\displaystyle A\land (B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)}$
Absorptionsgesetze ${\displaystyle A\land (A\lor B)\Leftrightarrow A}$
${\displaystyle A\lor (A\land B)\Leftrightarrow A}$
Idempotenzgesetze ${\displaystyle A\land A\Leftrightarrow A}$
${\displaystyle A\lor A\Leftrightarrow A}$
Gesetze vom ausgeschlossenen Dritten ${\displaystyle A\land \neg A\Leftrightarrow \mathrm {F} }$
${\displaystyle A\lor \neg A\Leftrightarrow \mathrm {W} }$
Darstellung von Implikation und Äquivalenz ${\displaystyle A\Rightarrow B\Leftrightarrow \neg A\lor B}$ Mit Hilfe dieser Gesetze kann die Implikation und die Äquivalenz auf Aussagen mit anderen Junktoren zurückgeführt werden. So können bestimmte Aufgaben gelöst werden (wie: Finden sie die Negation der Implikation).
${\displaystyle (A\Leftrightarrow B)\Leftrightarrow (A\Rightarrow B)\land (B\Rightarrow A)}$
${\displaystyle (A\Leftrightarrow B)\Leftrightarrow (\neg A\lor B)\land (A\lor \neg B)}$
${\displaystyle (A\Rightarrow B)\Leftrightarrow (\neg B\Rightarrow \neg A)}$ Prinzip der Kontraposition (Diese Äquivalenz kann insbesondere für Beweise verwendet werden)
Negation von zusammengsetzten Aussagen ${\displaystyle \neg (A\land B)\Leftrightarrow \neg A\lor \neg B}$ Bei der Negation einer Und- bzw. Oder-Verknüpfung wird die Negation in die Klammer gesetzt und das entsprechende Symbol der Verknüpfung umgedreht.
${\displaystyle \neg (A\lor B)\Leftrightarrow \neg A\land \neg B}$
${\displaystyle \neg (A\Rightarrow B)\Leftrightarrow A\land \neg B}$
${\displaystyle \neg (A\Leftrightarrow B)\Leftrightarrow (\neg A\Leftrightarrow B)}$
Negation quantifizierter Aussagen ${\displaystyle \neg (\forall x:\,A(x))\Leftrightarrow \exists x:\,\neg A(x)}$
${\displaystyle \neg (\forall x\in M:\,A(x))\Leftrightarrow \exists x\in M:\,\neg A(x)}$
${\displaystyle \neg (\exists x:\,A(x))\Leftrightarrow \forall x:\,\neg A(x)}$
${\displaystyle \neg (\exists x\in M:\,A(x))\Leftrightarrow \forall x\in M:\,\neg A(x)}$
Gesetze mit „wahr“ und „falsch“ ${\displaystyle A\land \mathrm {W} \Leftrightarrow A}$
${\displaystyle A\lor \mathrm {W} \Leftrightarrow \mathrm {W} }$
${\displaystyle A\land \mathrm {F} \Leftrightarrow \mathrm {F} }$
${\displaystyle A\lor \mathrm {F} \Leftrightarrow A}$
Doppelte Verneinung ${\displaystyle \neg \neg A\Leftrightarrow A}$ Doppelte Verneinung ist wieder die Ausgangsaussage.
Äquivalenzen zu quantifizierte Aussagen ${\displaystyle \left(\forall x:\,A(x)\right)\Leftrightarrow \neg \left(\exists x:\neg A(x)\right)}$ Aussagen mit dem Allquantor können durch den Existenzquantor ausgedrückt werden und umgekehrt.
${\displaystyle \left(\exists x:\,A(x)\right)\Leftrightarrow \neg \left(\forall x:\neg A(x)\right)}$
${\displaystyle \forall x:\,\forall y:\,A(x,y)\Leftrightarrow \forall y:\,\forall x:\,A(x,y)}$ Allquantoren sind untereinander vertauschbar.
${\displaystyle \exists x:\,\exists y:\,A(x,y)\Leftrightarrow \exists y:\,\exists x:\,A(x,y)}$ Existenzquantoren sind untereinander vertauschbar.
${\displaystyle \left(\forall x:\,A(x)\right)\land \left(\forall x:\,B(x)\right)\Leftrightarrow \forall x:\,\left(A(x)\land B(x)\right)}$ Allquantoren können aus Konjunktionen rausgezogen werden.
${\displaystyle \left(\exists x:\,A(x)\right)\lor \left(\exists x:\,B(x)\right)\Leftrightarrow \exists x:\,\left(A(x)\lor B(x)\right)}$ Existenzquantoren können aus Disjunktionen rausgezogen werden.
Implikation zu quantifizierten Aussagen ${\displaystyle \left(\forall x:\,A(x)\right)\lor \left(\forall x:\,B(x)\right)\Rightarrow \forall x:\,\left(A(x)\lor B(x)\right)}$ Implikationen sind im Allgemeinen nicht umkehrbar.
${\displaystyle \exists x:\,\left(A(x)\land B(x)\right)\Rightarrow \left(\exists x:\,A(x)\right)\land \left(\exists x:\,B(x)\right)}$
${\displaystyle \forall x:\,\left(A(x)\Rightarrow B(x)\right)\Rightarrow \left(\forall x:\,A(x)\Rightarrow \forall x:\,B(x)\right)}$
${\displaystyle \forall x:\,\left(A(x)\Leftrightarrow B(x)\right)\Rightarrow \left(\forall x:\,A(x)\Leftrightarrow \forall x:\,B(x)\right)}$
${\displaystyle \exists x:\,\forall y:\,A(x,y)\Rightarrow \forall y:\,\exists x:\,A(x,y)}$

### Vokabelliste

natürliche Sprache formale Schreibweise
nicht ${\displaystyle A}$ ${\displaystyle \neg A}$
${\displaystyle A}$ und ${\displaystyle B}$ ${\displaystyle A\land B}$
${\displaystyle A}$ oder ${\displaystyle B}$ *) ${\displaystyle A\lor B}$
Wenn ${\displaystyle A}$, dann ${\displaystyle B}$ ${\displaystyle A\Rightarrow B}$
${\displaystyle B}$ dann, wenn ${\displaystyle A}$
Aus ${\displaystyle A}$ folgt ${\displaystyle B}$
${\displaystyle A}$ impliziert ${\displaystyle B}$
${\displaystyle A}$ ist hinreichend für ${\displaystyle B}$
${\displaystyle B}$ ist notwendig für ${\displaystyle A}$
Genau dann ${\displaystyle A}$, wenn ${\displaystyle B}$ ${\displaystyle A\Leftrightarrow B}$
Dann und nur dann ${\displaystyle A}$, wenn ${\displaystyle B}$
${\displaystyle A}$ ist gleichwertig mit ${\displaystyle B}$
${\displaystyle A}$ ist äquivalent zu ${\displaystyle B}$
${\displaystyle A}$ ist notwendig und hinreichend für ${\displaystyle B}$
Für alle ${\displaystyle x}$ ist ${\displaystyle A(x)}$ ${\displaystyle \forall x:\,A(x)}$
Jedes ${\displaystyle x}$ erfüllt ${\displaystyle A(x)}$
Es ist A(x) für alle ${\displaystyle x}$
Für alle ${\displaystyle x}$ aus ${\displaystyle M}$ ist ${\displaystyle A(x)}$ ${\displaystyle \forall x\in M:\,A(x)}$
Jedes ${\displaystyle x}$ der Menge ${\displaystyle M}$ erfüllt ${\displaystyle A(x)}$
Es ist A(x) für alle ${\displaystyle x\in M}$
Es gibt ein ${\displaystyle x}$ mit ${\displaystyle A(x)}$ ${\displaystyle \exists x:\,A(x)}$
Es existiert ein ${\displaystyle x}$, so dass ${\displaystyle A(x)}$ gilt
Für mindestens ein ${\displaystyle x}$ gilt ${\displaystyle A(x)}$
Es gibt ein ${\displaystyle x}$ aus ${\displaystyle M}$ mit ${\displaystyle A(x)}$ ${\displaystyle \exists x\in M:\,A(x)}$
Für mindestens ein ${\displaystyle x\in M}$ gilt ${\displaystyle A(x)}$
Es gibt genau ein ${\displaystyle x}$ mit ${\displaystyle A(x)}$ ${\displaystyle \exists !x:\,A(x)}$
Es existiert genau ein ${\displaystyle x}$, so dass ${\displaystyle A(x)}$ gilt
Für genau ein ${\displaystyle x}$ gilt ${\displaystyle A(x)}$
Es gibt genau ein ${\displaystyle x}$ aus ${\displaystyle M}$ mit ${\displaystyle A(x)}$ ${\displaystyle \exists !x\in M:\,A(x)}$
Für genau ein ${\displaystyle x\in M}$ gilt ${\displaystyle A(x)}$

*) Hier ist „oder“ als „und/oder“ zu verstehen

### Umformungsregeln zur Negation

zu bestimmende Negation umgeformte Aussage
${\displaystyle \neg (\neg A)}$ ${\displaystyle A}$
${\displaystyle \neg (A\land B)}$ ${\displaystyle (\neg A)\lor (\neg B)}$
${\displaystyle \neg (A\lor B)}$ ${\displaystyle (\neg A)\land (\neg B)}$
${\displaystyle \neg (A\Rightarrow B)}$ ${\displaystyle A\land (\neg B)}$
${\displaystyle \neg (A\Leftrightarrow B)}$ ${\displaystyle A\Leftrightarrow (\neg B)}$
${\displaystyle \neg (\forall x:\,A(x))}$ ${\displaystyle \exists x:\,\neg A(x)}$
${\displaystyle \neg (\forall x\in M:\,A(x))}$ ${\displaystyle \exists x\in M:\,\neg A(x)}$
${\displaystyle \neg (\exists x:\,A(x))}$ ${\displaystyle \forall x:\,\neg A(x)}$
${\displaystyle \neg (\exists x\in M:\,A(x))}$ ${\displaystyle \forall x\in M:\,\neg A(x)}$

## Beweis

Definition (Beweis)

Ein Beweis ist eine fehlerfreie Herleitung eines mathematischen Satzes ${\displaystyle S}$ aus Axiomen und bereits bewiesenen Aussagen.

### Beweisarten

#### Direkter Beweis

${\displaystyle {\begin{array}{c}{\text{Prämissen und Voraussetzungen von }}S\\{\color {Orange}|}\\{\color {Orange}{\text{logische}}}\\{\color {Orange}{\text{Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{Konklusion von }}S\end{array}}}$

#### Widerspruchsbeweis

${\displaystyle {\begin{array}{c}{\text{Widerspruchsannahme }}\neg S\\{\color {Orange}|}\\{\color {Orange}{\text{logische}}}\\{\color {Orange}{\text{Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{Widerspruch}}\end{array}}}$

### Beweismethoden

#### Vollständige Fallunterscheidung

${\displaystyle {\begin{array}{c}{\text{Prämissen}}\\[2ex]{\begin{array}{c}{\text{Fall }}F_{1}:\\{\color {Orange}|}\\{\color {Orange}{\text{logische}}}\\{\color {Orange}{\text{Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{zu beweisende Aussage}}\end{array}}{\begin{array}{c}{\text{Fall }}F_{2}:\\{\color {Orange}|}\\{\color {Orange}{\text{logische}}}\\{\color {Orange}{\text{Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{zu beweisende Aussage}}\end{array}}\ldots {\begin{array}{c}{\text{Fall }}F_{n}:\\{\color {Orange}|}\\{\color {Orange}{\text{logische}}}\\{\color {Orange}{\text{Schlussfolgerungen}}}\\{\color {Orange}\downarrow }\\{\text{zu beweisende Aussage}}\end{array}}\end{array}}}$

#### Beweis durch Kontraposition

Anstatt eine Implikation ${\displaystyle A\Rightarrow B}$ zu beweisen, kann man alternativ auch die Implikation ${\displaystyle \neg B\Rightarrow \neg A}$ beweisen.

#### Vollständige Induktion

Sei ${\displaystyle A(n)}$ eine Aussageform in der freien Variablen ${\displaystyle n\in \mathbb {N} }$. Sei ${\displaystyle A(1)}$ (oder ${\displaystyle A(0)}$) eine wahre Aussage (Induktionsanfang) und die Implikation ${\displaystyle A(k)\Rightarrow A(k+1)}$ für alle ${\displaystyle k\in \mathbb {N} }$ erfüllt (Induktionsschritt), dann ist die Aussageform allgemeingültig in ${\displaystyle \mathbb {N} }$.

## Mengenlehre

### Verknüpfungen zwischen Mengen

Name der Verknüpfung Schreibweise Aussprache Diagramm Definition
Durchschnitt ${\displaystyle A\cap B}$ ${\displaystyle A}$ geschnitten ${\displaystyle B}$ ${\displaystyle A\cap B}$ - die Menge aller Objekte, die sowohl in der Menge ${\displaystyle A}$ als auch in der Menge ${\displaystyle B}$ enthalten sind
Vereinigung ${\displaystyle A\cup B}$ ${\displaystyle A}$ vereinigt ${\displaystyle B}$ ${\displaystyle A\cup B}$ - die Menge aller Objekte, die in mindestens einer der Mengen ${\displaystyle A,B}$ enthalten sind
Differenz ${\displaystyle A\setminus B}$ ${\displaystyle A}$ ohne ${\displaystyle B}$ ${\displaystyle A\setminus B}$ - die Menge aller Objekte, die in der Menge ${\displaystyle A}$ enthalten sind und keine Elemente der Menge ${\displaystyle B}$ sind
Symmetrische Differenz ${\displaystyle A\,\triangle \,B}$ „symmetrische Differenz von ${\displaystyle A}$ und ${\displaystyle B}$ ${\displaystyle A\,\triangle \,B}$ - die Menge aller Objekte, die in genau einer der Mengen ${\displaystyle A}$ und ${\displaystyle B}$ enthalten sind
Komplement ${\displaystyle A^{\rm {C}}}$ „Komplement von ${\displaystyle A}$ ${\displaystyle A^{\rm {C}}}$ - die Menge aller Objekte (der Grundmenge), die keine Elemente von ${\displaystyle A}$ sind

### Gesetzmäßigkeiten

#### Assoziativgesetze

• ${\displaystyle \left(A\cup B\right)\cup C=A\cup \left(B\cup C\right)}$
• ${\displaystyle \left(A\cap B\right)\cap C=A\cap \left(B\cap C\right)}$
• ${\displaystyle \left(A\,\triangle \,B\right)\,\triangle \,C=A\,\triangle \,\left(B\,\triangle \,C\right)}$

#### Kommutativgesetze

• ${\displaystyle A\cup B=B\cup A}$
• ${\displaystyle A\cap B=B\cap A}$
• ${\displaystyle A\,\triangle \,B=B\,\triangle \,A}$

#### Distributivgesetze

• ${\displaystyle A\cap (B\cup C)=(A\cap B)\cup (A\cap C)}$
• ${\displaystyle A\cup (B\cap C)=(A\cup B)\cap (A\cup C)}$
• ${\displaystyle A\cap (B\,\triangle \,C)=(A\cap B)\,\triangle \,(A\cap C)}$

#### Idempotenzgesetze

• ${\displaystyle A\cap A=A}$
• ${\displaystyle A\cup A=A}$

### Absorptionsgesetze

• ${\displaystyle A\cap (A\cup B)=A}$
• ${\displaystyle A\cup (A\cap B)=A}$

#### De-Morgansche Regeln

• ${\displaystyle (A\cap B)^{\rm {C}}=A^{\rm {C}}\cup B^{\rm {C}}}$
• ${\displaystyle (A\cup B)^{\rm {C}}=A^{\rm {C}}\cap B^{\rm {C}}}$

#### Gesetzmäßigkeiten zur Differenz

• ${\displaystyle (A\setminus B)\setminus C=A\setminus (B\cup C)}$
• ${\displaystyle A\setminus (B\setminus C)=(A\setminus B)\cup (A\cap C)}$
• ${\displaystyle (A\cap B)\setminus C=(A\setminus C)\cap (B\setminus C)}$
• ${\displaystyle (A\cup B)\setminus C=(A\setminus C)\cup (B\setminus C)}$
• ${\displaystyle A\setminus (B\cap C)=(A\setminus B)\cup (A\setminus C)}$
• ${\displaystyle A\setminus (B\cup C)=(A\setminus B)\cap (A\setminus C)}$

#### Weitere Regeln

Im Folgenden sei ${\displaystyle M}$ die Grundmenge.

• ${\displaystyle \left(A^{\rm {C}}\right)^{\rm {C}}=A}$
• ${\displaystyle M^{\rm {C}}=\emptyset }$
• ${\displaystyle \emptyset ^{\rm {C}}=M}$
• ${\displaystyle A\cap A^{\rm {C}}=\emptyset }$
• ${\displaystyle A\cup A^{\rm {C}}=M}$
• ${\displaystyle A\cap M=A}$
• ${\displaystyle A\cup M=M}$
• ${\displaystyle A\cap \emptyset =\emptyset }$
• ${\displaystyle A\cup \emptyset =A}$
• ${\displaystyle A\,\triangle \,A=\emptyset }$
• ${\displaystyle A\,\triangle \,\emptyset =A}$

## Relation

### Eigenschaften homogener, binärer Relationen

Im Folgenden sei ${\displaystyle R}$ eine homogene Relation auf der Grundmenge ${\displaystyle A}$, also ${\displaystyle R\subseteq A\times A}$.

Eigenschaft Definition Definition in formaler Schreibweise Merkmale
reflexiv Jedes Objekt der Grundmenge steht mit sich selbst in Relation. ${\displaystyle \forall a\in A:aRa}$
• Im Pfeildiagramm ist jedes Objekt mit sich selbst verbunden.
• In der Relationsmatrix ist die Hauptdiagonale voll besetzt.
irreflexiv Es gibt kein Objekt, welches mit sich selbst in Relation steht ${\displaystyle \forall a\in A:\neg aRa}$
• Im Pfeildiagramm steht kein Objekt mit sich selbst in Relation
• In der Relationsmatrix ist die Hauptdiagonale komplett unbesetzt.
symmetrisch Steht ein Objekt ${\displaystyle a}$ in Relation mit dem Objekt ${\displaystyle b}$, dann steht auch ${\displaystyle b}$ in Relation mit ${\displaystyle a}$ ${\displaystyle \forall a,b\in A:aRb\Rightarrow bRa}$
• Die Relationsmatrix ist symmetrisch zur Hauptdiagonale
antisymmetrisch Zwei verschiedene Objekte ${\displaystyle a}$ und ${\displaystyle b}$ stehen nicht gegenseitig in Relation zueinander. ${\displaystyle \forall a,b\in A:aRb\land bRa\Rightarrow a=b}$
• Die Relationsmatrix ist komplementär zu Hauptdiagonale.
transitiv Steht ${\displaystyle a}$ mit ${\displaystyle b}$ und ${\displaystyle b}$ mit ${\displaystyle c}$ in Relation, dann steht auch ${\displaystyle a}$ mit ${\displaystyle c}$ in Relation. ${\displaystyle \forall a,b,c\in A:aRb\land bRc\Rightarrow aRc}$
linear Für jeweils zwei Objekte ${\displaystyle a}$ und ${\displaystyle b}$ stehen ${\displaystyle a}$ mit ${\displaystyle b}$ und/oder ${\displaystyle b}$ mit ${\displaystyle a}$ in Relation. ${\displaystyle \forall a,b\in A:aRb\lor bRa}$

## Abbildung

### Eigenschaften von Abbildungen

Die folgende Tabelle bezieht sich auf Abbildungen ${\displaystyle f:D\rightarrow Z}$.

Eigenschaft Definition Definition in formaler Schreibweise Beispiel
injektiv
• Verschiedene Argumente werden auf verschiedene Funktionswerte abgebildet.
• Jeder Funktionswert besitzt höchstens ein Urbild.
• Ist ${\displaystyle f(x_{1})=f(x_{2})}$, dann ist ${\displaystyle x_{1}=x_{2}}$
• ${\displaystyle \forall x_{1},x_{2}\in D:f(x_{1})=f(x_{2})\Rightarrow x_{1}=x_{2}}$
• ${\displaystyle \forall x_{1},x_{2}\in D:x_{1}\neq x_{2}\Rightarrow f(x_{1})\neq f(x_{2})}$

surjektiv
• Jeder Funktionswert wird mindestens einmal durch die Abbildung getroffen.
• Jeder Funktionswert besitzt mindestens ein Urbild.
• ${\displaystyle \forall y\in Z:\exists x\in D:y=f(x)}$

bijektiv bzw. umkehrbar
• Die Abbildung ist surjektiv und injektiv.
• Jeder Funktionswert besitzt genau ein Urbild.
• Es gibt für die Funktion eine Umkehrfunktion.

### Eigenschaften binärer Verknüpfungen

Die folgende Tabelle bezieht sich auf binäre Verknüpfungen auf der Grundmenge ${\displaystyle A}$.

Eigenschaft Definition Definition in formaler Schreibweise
assoziativ Werden mehrere Verknüpfungen hintereinander ausgeführt, ist die Reihenfolge, in welcher die einzelnen Verknüpfungen ausgerechnet werden, für das Ergebnis egal ${\displaystyle \forall x,y,z\in A:(x\circ y)\circ z=x\circ (y\circ z)}$
kommutativ Für das Ergebnis ist die Reihenfolge der Operanden egal ${\displaystyle \forall x,y\in A:x\circ y=y\circ x}$

## Summe und Produkt

### Eigenschaften der Summen- und Produktschreibweise

Eigenschaften der Summe
Eigenschaft Erklärung
${\displaystyle \sum _{k=m}^{n}a(k)=\sum _{l=m}^{n}a(l)}$ Indexumbennungsregel: Die Indizes können beliebig umbenannt werden, solange die neu eingeführte Laufvariable nicht in Konflikt mit einer bereits definierten Variable tritt.
${\displaystyle \sum _{k=m}^{n}a(k)=\sum _{k=m}^{l}a(k)+\sum _{k=l+1}^{n}a(k)}$ Summen können in zwei Summen aufgeteilt werden.
${\displaystyle \sum _{k=m}^{n+1}a(k)=\sum _{k=m}^{n}a(k)+a(n+1)}$ Spezialfall der obigen Eigenschaften bzw. Rekursionsschritt bei der rekursiven Definition der Summe.
${\displaystyle \sum _{k=m}^{n}\lambda \cdot a(k)=\lambda \cdot \sum _{k=m}^{n}a(k)}$ Konstantenregel: Konstanten können aus Summen rausgezogen werden.
${\displaystyle \sum _{k=m}^{n}\left(a(k)+b(k)\right)=\left(\sum _{k=m}^{n}a(k)\right)+\left(\sum _{k=m}^{n}b(k)\right)}$
${\displaystyle \sum _{l=r}^{s}\sum _{k=m}^{n}a(l,k)=\sum _{k=m}^{n}\sum _{l=r}^{s}a(l,k)}$ Allgemeines Kommutativgesetz: Die Reihenfolge der Summen bei Doppel- und damit auch bei Mehrfachsummen ist egal.
${\displaystyle \left(\sum _{k=m}^{n}a(k)\right)\cdot \left(\sum _{l=r}^{s}b(l)\right)=\sum _{k=m}^{n}\sum _{l=r}^{s}a(k)\cdot b(l)}$ Allgemeines Distributivgesetz
Eigenschaften des Produkts
Eigenschaft Erklärung
${\displaystyle \prod _{k=m}^{n}a(k)=\prod _{l=m}^{n}a(l)}$ Indexumbennungsregel: Die Indizes können beliebig umbenannt werden, solange die neu eingeführte Laufvariable nicht in Konflikt mit einer bereits definierten Variable tritt.
${\displaystyle \prod _{k=m}^{n}a(k)=\left(\prod _{k=m}^{l}a(k)\right)\cdot \left(\prod _{k=l+1}^{n}a(k)\right)}$ Produkte können in mehrere Produkte aufgeteilt werden.
${\displaystyle \prod _{k=m}^{n+1}a(k)=\prod _{k=m}^{n}a(k)\cdot a(n+1)}$ Spezialfall der obigen Eigenschaften bzw. Rekursionsschritt bei der rekursiven Definition des Produkts.
${\displaystyle \prod _{k=m}^{n}\lambda \cdot a(k)=\lambda ^{n-m+1}\cdot \prod _{k=m}^{n}a(k)}$ Konstantenregel: Konstanten können aus Produkten rausgezogen werden (Beachte den dabei entstehenden Exponenten ${\displaystyle n-m+1}$).
${\displaystyle \prod _{k=m}^{n}\left(a(k)\cdot b(k)\right)=\left(\prod _{k=m}^{n}a(k)\right)\cdot \left(\prod _{k=m}^{n}b(k)\right)}$
${\displaystyle \prod _{l=r}^{s}\prod _{k=m}^{n}a(l,k)=\prod _{k=m}^{n}\prod _{l=r}^{s}a(l,k)}$ Allgemeines Kommutativgesetz: Die Reihenfolge der Produkte bei Doppel- und damit auch bei Mehrfachprodukten ist egal.

## Binomialkoeffizient

### Rechenregeln

• ${\displaystyle {\binom {n}{0}}=1}$
• ${\displaystyle {\binom {n}{n}}=1}$
• ${\displaystyle {\binom {n}{k}}={\binom {n}{n-k}}}$
• ${\displaystyle k\cdot {\binom {n}{k}}=n\cdot {\binom {n-1}{k-1}}}$
• ${\displaystyle {\binom {n+1}{k+1}}={\binom {n}{k}}+{\binom {n}{k+1}}}$