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 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

Durchschnitt

Nur Elemente in beiden Mengen: $A\cap B$ $A \cap B := {x:x \in A \lor x \in B}$ 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

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/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:

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

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

Konjunktion

Nur W - W ist wirklich wahr.
Pasted image 20231015095216.png

Disjunktion

Nur F - F ist wirklich falsch.
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
Zusammengesetzte Aussagen:
![[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

Kontradiktionen

Wenn egal welcher Wert die Variablen haben, die Aussage immer Falsch ist. 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]]

Zusammenhang

Wirkung zwischen Implikation, Umkehrung und Kontraposition. Pasted image 20231015132716.png

Äquivalenz

Gegenseitige Implikation der Inhalte. Pasted image 20231015132832.png

Andere Schreibweise

Pasted image 20231015133602.png

Aussageformen

Zahlenmenge

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 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

Bijektion

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

Übersicht injektiv, surjektiv, bijektiv

Pasted image 20231024165003.png

Verkettung

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.