Diskrete Mathematik

• Mengenlehre
• Aussagenlogik
• Funktionen

Mengenlehre

Als Menge wird in der Mathematik ein abstraktes Objekt bezeichnet, das aus der Zusammenfassung einer Anzahl einzelner Objekte hervorgeht. Diese werden dann als die Elemente der Menge bezeichnet. Mengen: Grossbuchstaben; A, B, C, ... Elemente: Kleinbuchstaben; a, b, c, ... p∈A Negation: p∉A

Aufschreibearten

Alle Elemente auflisten: $A = {a, b, c, x, y, z}$ $B = {1,2,3,4}$ $C={1,2,a,b,c}$

Eigenschaften festlegen: $B={n:n \in \mathbb{Z} \land n > 5 }$ B ist die Menge der Elemente n; wofür gilt, n ist eine ganze Zahl grösser als 5.

Extensionalitätaxiom

Zwei Mengen A und B enthalten selbe Elemente. $A=B$ Negation: $A \not = B$

Leere Mengen

Bezechnung: $\emptyset$ ${ }$ Elemente der betrachteten Menge => Universalmenge

Teilmengen

A & B sind zwei Mengen Wenn alle Elemente von A auch in Element B: $A \subseteq B$ Falls keine Teilmenge: $A \not \subseteq B$

Vereinigung

Alle Elemente von A und B: $A \cup B$ $A \cup B := { x:x \in A \lor x \in B } $

Durchschnitt

Nur Elemente in beiden Mengen: $A\cap B$ $A \cap B := {x:x \in A \lor x \in B}$

Disjunktion

Wenn der Durchschnitt zweier Mengen A und B leer ist: $A \cap B = \emptyset$

Komplement

$A \subseteq U$ kann auch als $A^C$ geschrieben werden $A^C := { x:x \in U \lor x \not \in A }$

Differenz

Wenn Differenz zwischen A und B ist alles in A, was nicht zu B gehört: $A \backslash B$ $A \backslash B := {x:x \in A \land x \not \in B}$ [] (https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231024102640.png)

Potenzmenge

Alle Teilmengen eines Mengensystems: S = {1, 2} $P(S) = { \emptyset, {1}, {2}, {1,2} }$ N Elemente enthalten: $2^n$ Elemente.

Partition

Aufteilung in nicht leere Teilmengen, zB. Partition A von S -> ${A_{i}}$. Dabei gilt:

• Teilmengen $A_{i}$ verschieden von $\emptyset$
• Alle $A_{i}$ ergeben S
• Paarweise disjunktiv; $A_{i} \cap A_:{j} = \emptyset$, falls $i \not = j$

Geordnete Paare

Bei Elementen einer Menge spielt die Reihenfolge keine Rolle: ${a,b} = {b,a}$ Bei geordneten Paaren hingegen gilt die Reihenfolge zwingen. $(a, b) = (c, d)$ Diese sind nur dann gleich wenn: a = c und b = d

Kartesisches Produkt

Menge aller geordneten Paare (x, y) mit $x \in A$ und $y \in B$. Bezeichnung: $A \times B$ $A \times B := {(x,y): x \in A \land y \in B}$

n-Tupel

Bestehend aus n geordneten Elementen $(a_{1}, a_{2}, a_{c}, \dots, a_{n})$ Zwei n-Tupel sind genau dann gleich: $a_{1}=b_{1} \land a_{2} = b_{2} \land a_{3} = b_{3} \land \dots \land a_{n} = b_{n}$ Bei folgenden Mengen $A_{1}, A_{2}, ... ,A_{n}$ bezeichnen Mengen aller n-Tupel $(a_{1}, b_{2}, ..., c_{n})$ mit der folgenden Eigenschaft $a_{1} \in A_{1}, a_{2} \in A_{2}, ..., a_{n} \in A_{n}$ diese Menge $A_{1} \times A_{2} \times ... \times A_{n}$

Endliche Mengen

Endlich bedeutet, dass die Menge m (natürliche Zahl) verschiedene Elemente hat. Anderfalls ist die Menge unendlich. Bezeichnung der Anzahl Elemente der Mengen: $|A|$ Wenn A und B endliche Mengen sind, dann ist $A \cup B$ ebenfalls enldich: $|A\cup B| = |A|+|B|-|A\cap B|$

Einschluss-Ausschluss-Formeln

Aussagenlogik

In der Aussagenlogik versteht man unter einer Aussage einen sprachlichen oder formalen Ausdruck, dem man genau einen der beiden möglichen Wahrheitswerte (w: wahr, f: falsch) zuordnen kann.

Konjunktion

Nur W - W ist wirklich wahr.

Disjunktion

Nur F - F ist wirklich falsch.

Antivalenz / XOR

Nur dann wahr, wenn nur eins von $A \oplus B$ richtig ist

A	B	$A \oplus B$
W	W	F
W	F	W
F	W	W
F	F	F

Negation

Zusammengesetzte Aussagen:

Disjunktive Normalform

Wahrheitstabelle zu Aussage aufschlüsseln. Jede Teilaussage muss dabei wahr sein und kann dann mit den anderen Teilaussagen über eine Disjunktion verknüpft werden.

Kanonisch disjunktive Normalform

Jede Variable kommt genau einmal vor.

Tautologien

Wenn alle Werte der Aussage wahr sind, unabhängig von den Werten der Variablen.

Kontradiktionen

Wenn egal welcher Wert die Variablen haben, die Aussage immer Falsch ist.

Logische Äquivalenz

Wenn zwei Aussagen die exakt gleiche Wahrheitstabelle haben. P(A, B, ...) $\equiv$ Q(A, B, ...)

Implikation

Ein Element verursacht ein anderes. Wenn A dann folgt B.

Zusammenhang

Wirkung zwischen Implikation, Umkehrung und Kontraposition.

Äquivalenz

Gegenseitige Implikation der Inhalte.

Andere Schreibweise

Aussageformen

Zahlenmenge

Operanden

x $\in$ $\mathbb{R}$ -> Definitionsbereich der Variable x. 3|n -> n ist ein Teiler von 3.

Quantoren

$\forall$ -> Allquantor für alle Elemente. $\exists$ -> Existiert mindestens ein Element.

Negation Existentaussage

$\exists x \in D : P(x) \equiv \forall x \in D: \lnot P(x)$ Entsprechend kann es so umgekehrt werden: $\lnot(\exists x \in D : P(x)) \equiv \forall x \in D: \lnot P(x)$

Negation Allaussage

$\lnot(\forall x \in D: P(x)) \equiv \exists x \in D: \lnot P(x)$

Beweistechniken

Indirekter Beweis

Implikation ist logisch äquivalent zu Kontraposition: $A \implies B \equiv \lnot B \implies \lnot A$ Manchmal einfacher zum Beweisen ist die Kontraposition.

Beweis durch Widerspruch

Hypothese: $\lnot A \implies B$
Ergibt einen Wirderspurch mit der wahren Aussage: $\lnot A \implies \lnot B$

Aussagenlogik vs Mengenlehre

Aussage: $x \in A$

Mengenangabe: $A \cap B$

Funktionen

Eine Grösse y ist von einer anderen Grösse x abhängig. f(x) -> Bild von x

Urbild

Wenn $y \in B$ dann ist $x \in A$ mit f(x) = y. $y \in B$ kann kein, genau ein oder mehrere Urbilder haben.

Definitionsbereich

Menge A der Funktion f.

Zielbereich

Menge B der Funkction f.

Bild der Funktion f

Die Menge aller Elemente y denen ein x zugeordnet wird. $f(x) = f(A) = { f(x):x \in A } \subset B$ Bild von x unter der Funktion f.

Graph einer Funktion

Der Graph G(f) der Funktion f ist die Menge $G(f) = {(x, f(x)) : x \in A} \subset A \times B$

Abrundungsfunktion

Ordnet jeder reellen Zahl x die grösste ganze Zahl zu. -> 4.154 -> 4

Aufrundungsfunktion

Ordnet jeder reellen Zahl die kleinste ganze Zahl zu. -> 4.154 = 5

Injektion

x = f(x) ist injektiv wenn: $x_{1} \not = x_{2} \implies f(x_{1}) \not = f(x_{2})$ Jede Funktion schneidet nur einmal eine horizontale Gerade.

Surjektion

Falls jedes Element des Wertebereichs mindestens ein Urbild besitzt. Wenn jedes $y \in B$ ein $x\in A$ besitzt.

Bijektion

Wenn f injektiv und surjektiv ist. Jedes $y \in B$ besitzt genau ein Urbild.

Übersicht injektiv, surjektiv, bijektiv

Verkettung

Umkehrfunktion

Wenn f(x) eine biijektive Funktion ist, existiert zu jedem $y \in B$ genau ein $x \in A$ mit f(x) = y. Dies wird auch inverse Abbildung genannt.

Inverse Abbilung

$f(x) -> f^{-1}(x)$ Für jedes $x \in A$: $(f^{-1}\circ f) (x) = f^{-1}(f(x))=x$ Die Umkehrfunktion setzt die Änderungen der Funktion zurück. Wenn eine Funktion invertierbar ist, ist klar, dass sie bijektiv ist.

Mächtigkeit

Anzahl Elemente einer Menge. Gleichmächtig bedeutet |A| = |B|, wenn eine Bijektion zwischen A und B existiert.

Es gibt Teilmengen, die gleichmächtig zur gesamten Menge sind.

Eine Menge M heisst endlich & abzählbar, wenn es eine echte Teilmenge von M gibt, die sich bijektiv auf M abbilden lässt.

Die Menge der reellen Zahlen ist nicht mehr abzählbar: 0.24999... = 0.25 sind gleichmächtig. Das nennt man auch überabzählbar.