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