Summary - 2021-11-23

Aussagenlogik

Bindung: $\neg, \wedge, \vee, \Rightarrow, \Leftrightarrow$

Distributivgesetzt: $A \wedge (B \vee C) \Leftrightarrow (A \wedge B) \vee (A \wedge C)$
Der Morgen: $\neg(A\vee B) \Leftrightarrow \neg A \wedge \neg B$
Implikation: $A \Rightarrow B \Leftrightarrow \neg A \vee B$
Kontraposition: $A \Rightarrow B \Leftrightarrow \neg B \Rightarrow \neg A$
Äquivalenz $(A \Leftrightarrow B) \Leftrightarrow (A \Rightarrow B) \wedge (B \Rightarrow A) \Leftrightarrow (\neg A \vee B) \wedge (\neg B \vee A)$

Direkten Beweis
So veralgemeinern, dass der einte der Term gleich dem anderen Term ist
Beweis durch Widerspruch
Anstatt zu zeigen, dass die Aussage A immer wahr ist, wird bewiessen, dass A niemals falsch ist.
Beweis durch (Gegen-) Beispiel
Wenn beweissen werden soll, dass etwas immer korrekt oder immer falsch ist, kann mit ein korrekten, bzw. falschem Beispiel gezeigt werden, dass die Aussage falsch ist
Beweis durch Kontraposition
Es gillt die Aussage von der Form $A \Rightarrow B \Leftrightarrow \neg B \Rightarrow \neg A$
Äquivalenz
Da eine Äquivalenz $(A \Leftrightarrow B) \Leftrightarrow (A \Rightarrow B \wedge B \Rightarrow A)$ ist, kann einfach das zweitere bewiessen werden.

Begriff	Erklärung
Gülltig oder Wahr	Bei einer spezifischen Belegung wahr
Allgemeingülltig	Bei allen Belegungen wahr
Erfüllbar	mind. eine Belegung ist erfüllbar
Unerfüllbar	immer falsch
Wiederlegbar	mind. einmal falsch; nicht umbedingt immer falsch
Literale	$\neg a \text{ oder } a$
Negotions Normalform (NNF)	Keine Implikationen und alle$\neg$ in Literale
Disjunktive Normalform (DNF)	Form:$(L_1 \wedge L_2 \wedge ...)\vee (L_3 \wedge L_4) \vee ...$
Konjuktive Normalform (KNF)	Form:$L_1 \vee L_2 \vee ...) \wedge (L_3 \vee L_4)\wedge ...$
Funktional Vollständig	Menge von Logischen Verknüpfungen, welche die Funktionen$\vee, \wedge, \neg, \rightarrow$ darstellen können

Begriff	Erklärung
Natürliche Zahlen ($\N$)	$[0; \infty]$
Ganze Zahlen ($\Z$)	$[-\infty;\infty]$
Rationale Zahlen ($\mathbb Q$)	Alle Zahlen, darstellbar durch einen Bruch
Reele Zahlen ($\R$)	Alle Zahlen mit einem Komma ($\pi$, $e$, 2.32, 2, ...)
Intervallschreibweisse	Ist immer im Zahlenbereich$\R$
Teilmenge ($X \subseteq Y$)	$\forall x (x \in X \Rightarrow x \in Y)$ / X ist eine Teilmenge von Y, X=Y kann auch sein
Echte Teilmenge ($X \subsetneq Y$)	$X \subseteq Y \wedge X \neq Y$ / X ist eine Teilmenge von Y, X kann nicht Y sein
Potenzmenge ($\mathcal P(X)$)	Menge aller Teilmenge ($\mathcal P(\{0, 1\})=\{\emptyset, \{0\}, \{1\}, \{0, 1\} \}$. Die Mächtigkeit ist $\mathcal P(A)=2^{ \vert A \vert} $
Partition	Eine Menge von Teilmengen von A, welche nicht leer sind ($\bigcup_{i\in I}P_i=A$)
Kardinalität/Mächtigkeit	Anzahl Elemente in Menge
Schnittmenge ($X \cap Y$)	Alle Elemente, welch ein beiden enthalten sind
Vereinigung ($X \cup Y$)	Alle Elemente von beiden Mengen
Komplement ($X\setminus Y)$	Alle Elemente aus X, welche nicht in Y vorkommen ($X \cap \bar Y$)
(nicht paarweise) Disjunkte Mengen	Zwei Mengen teilen keine Elemente
paarwweise Disjunkte Mengen	Alle Mengen teilen keine Elemente
Abzählbare Menge	Wenn eine surjektive Funktion $F: \N \rightarrow X$ existiert
Überabzählbare Menge	Wenn es keine surjektive Funktion $F: \N \rightarrow X$ existiert

Begriff	Erklärung
Injektiv (linkseindeutig)	Wenn zu jedem y höchsten ein x gibt
Surjektiv (rechtstotal)	Wenn es zu jedem y mindestens ein x gibt
Bijektive Funktion	Eine Funktion, welche injektiv und surjktiv ist (
Homogene Relation	$A=B, R\subseteq A\times A$
Äquivalenzrelationen	Eine reflexive, symmetrische und transitive Relation, in welcher alle Elemente zu einander eine Beziehung haben
$x\equiv_5y $	$(x - y) \text{ ist ein vielfaches von 5}$

Begriff	Erklärung
Natürliche Zahlen (\(\N\))	\([0; \infty]\)
Ganze Zahlen (\(\Z\))	\([-\infty;\infty]\)
Rationale Zahlen (\(\mathbb Q\))	Alle Zahlen, darstellbar durch einen Bruch
Reele Zahlen (\(\R\))	Alle Zahlen mit einem Komma (\(\pi\), \(e\), 2.32, 2, ...)
Intervallschreibweisse	Ist immer im Zahlenbereich\(\R\)
Teilmenge (\(X \subseteq Y\))	\(\forall x (x \in X \Rightarrow x \in Y)\) / X ist eine Teilmenge von Y, X=Y kann auch sein
Echte Teilmenge (\(X \subsetneq Y\))	\(X \subseteq Y \wedge X \neq Y\) / X ist eine Teilmenge von Y, X kann nicht Y sein
Potenzmenge (\(\mathcal P(X)\))	Menge aller Teilmenge (\(\mathcal P(\{0, 1\})=\{\emptyset, \{0\}, \{1\}, \{0, 1\} \}\). Die Mächtigkeit ist $\mathcal P(A)=2^{ \vert A \vert} $
Partition	Eine Menge von Teilmengen von A, welche nicht leer sind (\(\bigcup_{i\in I}P_i=A\))
Kardinalität/Mächtigkeit	Anzahl Elemente in Menge
Schnittmenge (\(X \cap Y\))	Alle Elemente, welch ein beiden enthalten sind
Vereinigung (\(X \cup Y\))	Alle Elemente von beiden Mengen
Komplement (\(X\setminus Y)\)	Alle Elemente aus X, welche nicht in Y vorkommen (\(X \cap \bar Y\))
(nicht paarweise) Disjunkte Mengen	Zwei Mengen teilen keine Elemente
paarwweise Disjunkte Mengen	Alle Mengen teilen keine Elemente
Abzählbare Menge	Wenn eine surjektive Funktion \(F: \N \rightarrow X\) existiert
Überabzählbare Menge	Wenn es keine surjektive Funktion \(F: \N \rightarrow X\) existiert