# Diskrete Mathematik

# 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.
[![Pasted image 20231014095256.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231014095256.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231014095256.png)
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 \} $
[![Pasted image 20231024101106.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231024101106.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231024101106.png)
## Durchschnitt
Nur Elemente in beiden Mengen:
$A\cap B$
$A \cap B := \{x:x \in A \lor x \in B\}$
[![Pasted image 20231024102057.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231024102057.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231024102057.png)
## 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 \}$
[![Pasted image 20231024102358.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231024102358.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231024102358.png)
## 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\}$
[![Pasted image 20231024102640.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231024102640.png)]
(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
[![Pasted image 20231024155838.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231024155838.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231024155838.png)

# 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.
[![Pasted image 20231015103058.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015103058.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015103058.png)
## Konjunktion
Nur W - W ist wirklich wahr.\
[![Pasted image 20231015095216.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015095216.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015095216.png)
## Disjunktion
Nur F - F ist wirklich falsch.\
[![Pasted image 20231015095329.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015095329.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015095329.png)
## 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
[![Pasted image 20231015100303.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015100303.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015100303.png)\
Zusammengesetzte Aussagen:\
[![![[Pasted image 20231015100429.png]]](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015100429.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015100429.png)
## 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.
[![Pasted image 20231015102549.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015102549.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015102549.png)
## Kontradiktionen
Wenn egal welcher Wert die Variablen haben, die Aussage immer Falsch ist.
[![Pasted image 20231015102706.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015102706.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015102706.png)
## 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.
[![![
[Pasted image 20231015132040.png]]](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015132040.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015132040.png)
### Zusammenhang
Wirkung zwischen Implikation, Umkehrung und Kontraposition.
[![Pasted image 20231015132716.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015132716.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015132716.png)
## Äquivalenz
Gegenseitige Implikation der Inhalte.
[![Pasted image 20231015132832.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015132832.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015132832.png)
### Andere Schreibweise
[![Pasted image 20231015133602.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015133602.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015133602.png)
# Aussageformen
## Zahlenmenge
[![Pasted image 20231015133147.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231015133147.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231015133147.png)
## 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})$
[![Pasted image 20231024164654.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231024164654.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231024164654.png)
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.
[![Pasted image 20231024164905.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231024164905.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231024164905.png)
## Bijektion
Wenn f injektiv und surjektiv ist. Jedes $y \in B$ besitzt genau ein Urbild.
[![Pasted image 20231024164944.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231024164944.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231024164944.png)
## Übersicht injektiv, surjektiv, bijektiv
[![Pasted image 20231024165003.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/pasted-image-20231024165003.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/pasted-image-20231024165003.png)
## Verkettung
[![image-1698216350447.png](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/scaled-1680-/image-1698216350447.png)](https://docs.lucanoahcaprez.ch/uploads/images/gallery/2023-10/image-1698216350447.png)
## 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.