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

Logik

Mind Map

Wahrheitstabellen der Junktoren

Wahrheitstabelle: Negation

$A$	$\neg A$
$\mathrm {F}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {F}$

Wahrheitstabelle: Konjunktion

$A$	$B$	$A\land B$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {W}$

Wahrheitstabelle: Disjunktion

$A$	$B$	$A\lor B$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {W}$

Wahrheitstabelle: Implikation

$A$	$B$	$A\Rightarrow B$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {W}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {W}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {W}$

Wahrheitstabelle: Äquivalenz

$A$	$B$	$A\Leftrightarrow B$
$\mathrm {F}$	$\mathrm {F}$	$\mathrm {W}$
$\mathrm {F}$	$\mathrm {W}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {F}$	$\mathrm {F}$
$\mathrm {W}$	$\mathrm {W}$	$\mathrm {W}$

Tautologien

Name der Umformungsregeln	Tautologie	Bedeutung
Assoziativgesetze	$(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.
	$(A\land B)\land C\Leftrightarrow A\land (B\land C)$
Kommutativgesetze	$(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.
	$(A\land B)\Leftrightarrow (B\land A)$
Distributivgesetze	$A\lor (B\land C)\Leftrightarrow (A\lor B)\land (A\lor C)$	Eine Disjunktion kann in eine Konjunktion reingezogen werden und umgekehrt.
	$A\land (B\lor C)\Leftrightarrow (A\land B)\lor (A\land C)$
Absorptionsgesetze	$A\land (A\lor B)\Leftrightarrow A$
	$A\lor (A\land B)\Leftrightarrow A$
Idempotenzgesetze	$A\land A\Leftrightarrow A$
	$A\lor A\Leftrightarrow A$
Gesetze vom ausgeschlossenen Dritten	$A\land \neg A\Leftrightarrow \mathrm {F}$
	$A\lor \neg A\Leftrightarrow \mathrm {W}$
Darstellung von Implikation und Äquivalenz	$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).
	$(A\Leftrightarrow B)\Leftrightarrow (A\Rightarrow B)\land (B\Rightarrow A)$
	$(A\Leftrightarrow B)\Leftrightarrow (\neg A\lor B)\land (A\lor \neg B)$
	$(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	$\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.
	$\neg (A\lor B)\Leftrightarrow \neg A\land \neg B$
	$\neg (A\Rightarrow B)\Leftrightarrow A\land \neg B$
	$\neg (A\Leftrightarrow B)\Leftrightarrow (\neg A\Leftrightarrow B)$
Negation quantifizierter Aussagen	$\neg (\forall x:\,A(x))\Leftrightarrow \exists x:\,\neg A(x)$
	$\neg (\forall x\in M:\,A(x))\Leftrightarrow \exists x\in M:\,\neg A(x)$
	$\neg (\exists x:\,A(x))\Leftrightarrow \forall x:\,\neg A(x)$
	$\neg (\exists x\in M:\,A(x))\Leftrightarrow \forall x\in M:\,\neg A(x)$
Gesetze mit „wahr“ und „falsch“	$A\land \mathrm {W} \Leftrightarrow A$
	$A\lor \mathrm {W} \Leftrightarrow \mathrm {W}$
	$A\land \mathrm {F} \Leftrightarrow \mathrm {F}$
	$A\lor \mathrm {F} \Leftrightarrow A$
Doppelte Verneinung	$\neg \neg A\Leftrightarrow A$	Doppelte Verneinung ist wieder die Ausgangsaussage.
Äquivalenzen zu quantifizierte Aussagen	$\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.
	$\left(\exists x:\,A(x)\right)\Leftrightarrow \neg \left(\forall x:\neg A(x)\right)$
	$\forall x:\,\forall y:\,A(x,y)\Leftrightarrow \forall y:\,\forall x:\,A(x,y)$	Allquantoren sind untereinander vertauschbar.
	$\exists x:\,\exists y:\,A(x,y)\Leftrightarrow \exists y:\,\exists x:\,A(x,y)$	Existenzquantoren sind untereinander vertauschbar.
	$\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.
	$\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	$\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.
	$\exists x:\,\left(A(x)\land B(x)\right)\Rightarrow \left(\exists x:\,A(x)\right)\land \left(\exists x:\,B(x)\right)$
	$\forall x:\,\left(A(x)\Rightarrow B(x)\right)\Rightarrow \left(\forall x:\,A(x)\Rightarrow \forall x:\,B(x)\right)$
	$\forall x:\,\left(A(x)\Leftrightarrow B(x)\right)\Rightarrow \left(\forall x:\,A(x)\Leftrightarrow \forall x:\,B(x)\right)$
	$\exists x:\,\forall y:\,A(x,y)\Rightarrow \forall y:\,\exists x:\,A(x,y)$

Vokabelliste

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

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

Umformungsregeln zur Negation

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

Beweis

Definition (Beweis)

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

Beweisarten

Direkter Beweis

${\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

${\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

${\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 $A\Rightarrow B$ zu beweisen, kann man alternativ auch die Implikation $\neg B\Rightarrow \neg A$ beweisen.

Vollständige Induktion

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

Mengenlehre

Mind Map

Verknüpfungen zwischen Mengen

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

Gesetzmäßigkeiten

Assoziativgesetze

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

Kommutativgesetze

• $A\cup B=B\cup A$
• $A\cap B=B\cap A$
• $A\,\triangle \,B=B\,\triangle \,A$

Distributivgesetze

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

Idempotenzgesetze

• $A\cap A=A$
• $A\cup A=A$

Absorptionsgesetze

• $A\cap (A\cup B)=A$
• $A\cup (A\cap B)=A$

De-Morgansche Regeln

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

Gesetzmäßigkeiten zur Differenz

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

Weitere Regeln

Im Folgenden sei $M$ die Grundmenge.

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

Relation

Mind Map

Eigenschaften homogener, binärer Relationen

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

Eigenschaft	Definition	Definition in formaler Schreibweise	Merkmale
reflexiv	Jedes Objekt der Grundmenge steht mit sich selbst in Relation.	$\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	$\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 $a$ in Relation mit dem Objekt $b$, dann steht auch $b$ in Relation mit $a$	$\forall a,b\in A:aRb\Rightarrow bRa$	Die Relationsmatrix ist symmetrisch zur Hauptdiagonale
antisymmetrisch	Zwei verschiedene Objekte $a$ und $b$ stehen nicht gegenseitig in Relation zueinander.	$\forall a,b\in A:aRb\land bRa\Rightarrow a=b$	Die Relationsmatrix ist komplementär zu Hauptdiagonale.
transitiv	Steht $a$ mit $b$ und $b$ mit $c$ in Relation, dann steht auch $a$ mit $c$ in Relation.	$\forall a,b,c\in A:aRb\land bRc\Rightarrow aRc$
linear	Für jeweils zwei Objekte $a$ und $b$ stehen $a$ mit $b$ und/oder $b$ mit $a$ in Relation.	$\forall a,b\in A:aRb\lor bRa$

Abbildung

Mind Map

Eigenschaften von Abbildungen

Die folgende Tabelle bezieht sich auf Abbildungen $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 $f(x_{1})=f(x_{2})$, dann ist $x_{1}=x_{2}$	$\forall x_{1},x_{2}\in D:f(x_{1})=f(x_{2})\Rightarrow x_{1}=x_{2}$ $\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.	$\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 $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	$\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	$\forall x,y\in A:x\circ y=y\circ x$

Mächtigkeit von Mengen

Mind Map

Summe und Produkt

Mind Map

Eigenschaften der Summen- und Produktschreibweise

Eigenschaften der Summe

Eigenschaft	Erklärung
$\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.
$\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.
$\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.
$\sum _{k=m}^{n}\lambda \cdot a(k)=\lambda \cdot \sum _{k=m}^{n}a(k)$	Konstantenregel: Konstanten können aus Summen rausgezogen werden.
$\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)$
$\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.
$\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
$\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.
$\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.
$\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.
$\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 $n-m+1$).
$\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)$
$\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

Mind Map

Rechenregeln

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