Lernmaterialien

Vorlesungsskript: [[DM24_LN_tablet.pdf]]
Aufgaben: https://dm.crypto.ethz.ch/ (UNAME: eth-kürzel, PWD: eth-main-pwd)
Website: https://crypto.ethz.ch/teaching/DM24/

Übungen

Übung	Lösung	Übung
[[exercise_file_1.pdf]]	[[20240925_DiskMat_Serie1.pdf]]
[[exercise_file_2.pdf]]	[[20241002_DiskMat_Serie2.pdf]]
[[exercise_file_3.pdf]]	[[20241002_DiskMat_Serie3.pdf]]
[[exercise_file_4.pdf]]	[[20241017_DiskMat_Serie4.pdf]]
[[exercise_file_5.pdf]]	[[20241024_DiskMat_Serie5.pdf]]
[[exercise_file_6.pdf]]	20241031_DiskMat_Serie6	pdf mit uncountable beweis
[[exercise_file_7.pdf]]	[[20241107_DiskMat_Serie7.pdf]]
[[exercise_file_8.pdf]]	[[20241114_DiskMat_Serie8.pdf]]
[[exercise_file_9.pdf]]	20241121_DiskMat_Serie9
[[exercise_file_10.pdf]]	20241127_DiskMat_Serie10
[[exercise_file_11.pdf]]	20241205_DiskMat_Serie11
[[exercise_file_12.pdf]]	20241211_DiskMat_Serie12	Alle Aussagenlogik-umformungen: link
[[exercise_file_13.pdf]]
		first-order logic calculator truth table generator

Prüfung

3 Stunden
Zusammenfassung erlaubt
4 Aufgaben:
- Mengen und Relationen, Zahlenthoerie (kurz), Algebra, Logik
- zu Kapitel 3,4,5,6 (und 2)
zudem multiple choice, evtl. Beweis
Noten
- 4 -> 40%
- 6 -> 80%
- linear: "normalerweise" 1 kaum zu erreichen
Prüfungssammlung: https://exams.vis.ethz.ch/category/DiskreteMathematik

Prawin

Kapitel 2,3,6 -> >5 an Prüfung
(***)-aufgaben sind sehr Zeitintensiv -> erst am Schluss machen

HS2024_DiskMat_Prüfung_HS23

1 Einführung

Diskret -> endliche Zustaende

Drei Fragen zu den Aussagen?

Ist die Aussage wohldefiniert?
Ist die Aussage wahr oder falsch?
Warum? -> Herleitung/Beweis

Bsp:
$S :$ 91 ist eine Primzahl
$T :$ Es gibt unendlich viele PZ. -> unendlich vermeiden, besser
$U :$ Im Schachspiel gibt es eine mindestens Gewinnstrategie für Weiss -> keine mathematische Aussage, weil Lösung nicht bekannt. -> Es gibt einen ersten Zug der Gewinnstrategie, sodass fuer jeden Zug von Schwarz es einen Zug von weiss gibt.

$S ⟹ T$

$S$ ist falsch (ist wahr)

Für jedes markierte Feld gibt es eine Belegung des Restfeldes L-Formen.

$P (K) ⟺^{d e f}$ Aussage wahr für k*k Quadrat
$P (3) = 0$
$P (2) = 1$
$P (4) = 1$
$P (5) = 0$ -> es reicht ein Gegenbeispiel, um die Aussage zu wiederlegen

$k^{2} - 1$ nicht durch 3 teilbar $⟹ P (k) = 0$
$k^{2} \equiv_{3} 1$ -> $k \equiv_{3} 1$ oder $k \equiv_{3} 2$
$P (3 n) = 0$

Theorem: (für jedes $k$ gilt) $P (k) = 1 ⟹ P (2 k) = 1$

Beweis:
2024_09_18 15_47 Office Lens.jpg|300
Aussage is von der Form einer Implikation.

Abstraktion
Wie kann eine Schokolade (4*6 quadrate) mit einer möglichst kleinen Anzahl brueche aufgeteilt werden?
Abstraktion: nur Kanten sind wichtig, nicht Schokolade/Quadratgroesse, ...
(-> Anzahl brueche ist 1 weniger als Stuecke)

2

2.3 Logik

#timestamp 2024-09-23
#read Skript S. 17-22, ohne 2.2

$S ⟹ T$
$T ⟹ U$
$U ⟹ S$
-> kann nicht festgestellt werden, ob S wahr ist

Aussage: Jede gerade Zahl $\geq$ 4 ist die Summe von 2 PZ.
-> Vermutung (nicht bewiesene Aussage)
- bewiesene Aussage: Theorem/Lemma
-> ist die Aussage relevant?

Def 2.1:

0,1 | Wahrheitswerte
A,B,C,D | Wahre/Falsche Aussagen

BSP: Ärtztin 1: X hat entweder Masern oder (Windpocken und Lungenentzündung).
$A :$ X hat Masern
$B :$ X hat WP
$C :$ X hat LE

\begin{aligned} F = A \lor (B \land C) \\ G = \neg B \lor (\neg A \land \neg C) \\ H = \neg A \lor (A \land B \land C) \end{aligned}

2024_09_23 16_18 Office Lens (2).jpg|400

$F \land G \equiv A \land \neg B$

logische Formel: ein korrekt geformter Ausdruck -> keine Aussage, sondern Funktion die jeder Variable alle möglichen Wahrheitswerte zuweisen
unerfüllbar: eine Formel, die immer 0 ist
allgemeingültig, Tautologie: eine Formel, die immer wahr (1) ist ( $⊨$ )
Aussage wahr oder falsch, ohne Logik
logische Konsequenz $A ⊨ B$ (immer wenn $A$ wahr ist, its $B$ wahr)

\begin{array}{r} F \land G ⊨ A \\ F \land G ⊨ \neg B \\ F \land G ⊨ \neg H \end{array}

Formel vs Aussage

$\to$ Input: Formeln, Output: Formel
$⊨$ : Input: Formeln, Output: Aussage
$\equiv$ Input: Formeln, Output: Aussage (?)

$F ⊨ G$ und $G ⊨ G$ (g.d.w) $⟺$ $F \equiv G$ , aber nicht $\equiv F \equiv G$
$F \equiv ⊥ ⟺ \neg F \equiv ⊤$

#timestamp 2024-09-25

2024_09_25 17_25 Office Lens (1).jpg

logische Folgerung: $F ⊨ G$ -> wenn F, dann auch G (asymmetrisch)

Exkurs

Gibt es eine effizient Lösung für ein sat.-Problem (z.B. Schalftung oben)-> $P - N P$ -vollständig

2024_09_25 17_25 Office Lens (2).jpg

wenn $F \to G$ Tautologie, dann $T ⊨ G$ -> Bsp: Skript 2.6.4

modus ponens
S beweisen:

Eine Aussage $R$ formulieren.
$R$ beweisen
$R ⟹ S$ beweisen

wieso funktioniert:

A \land (A \to B) ⊨ B

Lemma 2.1

$A \land B \equiv B \land A$
$\neg (A \land B) \equiv \neg A \lor \neg B$
$A \land (B \lor C) \equiv (A \land B) \lor (A \land C)$ | Distributivgesetz

Bem: Es gibt Prioritätsregeln , man darf Klammern weglassen

Beweis durch Herleitung

2024_09_25 17_25 Office Lens (3).jpg

Beweiskonzept

2024_09_25 17_25 Office Lens (4).jpg

Beweissystem - gewünschte Eigenschaften: (siehe Kapitel 6)

welchen Typ von Aussagen kann überprüft werden?
kein Beweis für falsche Aussagen
Beweis

Aussage: $1 < 0$
Beweis: $1 < 0 \dot{⟹} 2 < 1$ (+1)
$\dot{⟹} 2 > 1$ (mult. mit 1, 1 ist negativ) (wahr)

Deshalb $1 < 0$ wahr

$\dot{⟹}$ | Punkt, weil Folgerungsschritt

S beweisen:

Falsch:

$S ⟹ T$
T ist wahr

S \dot{⟹}

\dot{⟹}

\dot{⟹} T

$a$ und $b$ sind QZ.

2024_09_25 17_25 Office Lens (5).jpg

Aussage: $2^{143} - 1$ ist keine PZ.
Beweis: $n$ ist nicht PZ $⟹ 2^{n} - 1$ ist nicht PZ
(oder) $S ⟹ T$

Bem: Nicht $S$ wird bewiesen, sondern es wird bewiesen, dass $S ⟹ T$

2024_09_25 17_39 Office Lens (1).jpg

Struktur: Aus etwas bewiesenem in Schritten Neues beweisen

\begin{aligned} S & \dot{⟹} S_{1} \\ S_{2} \\ S_{2} & \dot{⟹} S_{3} \\ S_{1} & \dot{⟹} S_{4} \\ S_{1} & \dot{⟹} S_{5} \\ S_{3}, S_{4}, S_{5} & \dot{⟹} T \end{aligned}

2.4 Prädikatslogik

$U$ (Universum, z.b. Zahlenmenge)
$P (x, y), Q (x)$ (Prädikate)
$f (x, y)$ (Funktionen)
$a, b, c$ (Konstanten)
$\exists x Q (x)$ (Formel)
- $\forall x Q (x)$

#timestamp 2024-09-30

Bsp: Spezialfall: $U = N$ :
$p r i m e (x)$
$a d d (x, y)$ -> $x + y$ (Infix-Notation)
$mult (x, y)$
$less (x, y)$ -> $x < y$

Konstanten: $0, 1, 2$
Aussagen: $\forall x \exists y : l e s s (x, y)$

Formeln sind nicht wahr oder falsch

\begin{aligned} \forall x (0 \leq x) & wahr (Da Universum vorher definiert, hat Formel Wahrheitswert) \\ \exists x (2 \leq x) & wahr \\ \exists x (x \leq_{2}) \land \exists x (3 \leq x) & wahr (x sind zwei verschiedene Variablen (siehe Bild)) \end{aligned}

2024_09_30 16_20 Office Lens (1).jpg|500

\forall x (F \land G) \equiv \forall x F \land \forall x G

\begin{aligned} \forall x \underset{Q (x)}{\underset{⏟}{\exists y (x + y = 0)}} & für N falsch (Beweis: z.B. durch Gegenbeispiel) \end{aligned}

-> $x, y$ müssen nicht unbedingt Zahlen sein
- es koennte irgendeine Struktur sein, solange +, = definiert ist
- unteres beispiel: $x, y$ irgendetwas sein, solange vergleiche definiert sind (z.B. Matrizen, ...)

S: Es gibt eine kleinste Zahl
T: Es gibt nicht für jede Zahl eine (noch) kleinere

\begin{aligned} \exists x \forall y (x \leq y) & (S) \\ \neg \forall x \exists y (y < x) & (T) \\ \equiv & \exists x \neg \exists y (y < x) & Umformung (siehe Bild) \\ \equiv & \exists x \forall y \neg (y < x) \end{aligned}

2024_09_30 16_20 Office Lens (2).jpg|500

komplexe Definition:

\begin{aligned} p r i m e (x) \overset{d e f}{⟺} x > 1 \land \forall y \forall z ((x = y * z) \to (y = 1 \lor z = 1)) & x ist eine freie Variable \end{aligned}

\begin{aligned} \forall x (P (x) \to Q (x)) & ⊨ \forall P (x) \to \forall x Q (x) \\ \to & mit \to : Formel wäre Tautologie \end{aligned}

-> logische Folgerungen

Vertauschen: mehrere gleiche Quantoren ( $\forall x \forall y$ ) können vertauscht werden!

\begin{aligned} \forall x \forall y \forall z (P (x, y) \land P (y, z) \to P (x, z)) \\ ⊨ \\ \forall x \forall y \forall z \forall w (P (x, y) \land P (y, z) \land P (z, w) \to P (x, w)) \end{aligned}

-> transitiv: wenn $P (y, z)$ und $P (x, z)$ , dann $P (x, y)$
-> Vorteil von Formulierung: Allgemein

Bsp:
$U$ = Menschen
Prädikate:

$par (x, y)$
$child (x, y) \overset{d e f}{⟺} par (y, x)$
$gpar (x, y) \overset{d e f}{⟺} \exists z (p a r (x, z) \land p (z, y))$
$sibl (x, y) \overset{d e f}{⟺} \exists z (p (z, x) \land p (z, y)) \land x \neq y$

Kommutativität:

\begin{aligned} s i b l (x, y) \equiv s i b l (y, x) & Könnte auf logischer Stufe bewiesen werden \end{aligned}

Reihenfolge Quantoren spielt eine Rolle (!):

\begin{aligned} \forall x \exists y par (x, y) & jede person hat kinder \\ \exists x \forall y & es gibt person, die alle anderen menschen als ’par’ hat \\ \forall y \exists x & jede person hat eltern \\ \exists y \forall x & es gibt jemanden, der für alle Elternteil ist \end{aligned}

Bsp. Verwandschaftsregeln

\begin{aligned} \forall x \neg par (x, x) & Niemand ist Elternteil von sich selbst \\ \forall x \forall y \neg (p (x, y) \land p (y, x)) & Man ist nicht gegenseitig Elternteil \end{aligned}

-> man könnte Verwandschaft über mehrere Grade nur sehr komplex ausdrücken -> Logik hat auch gewisse Grenzen

#timestamp 2024-10-07

\begin{matrix}  \end{matrix} F = \forall x (P (x) \to \neg P (x)) \equiv \forall x \neg P (x)

\forall x \forall y \forall z ((P (x, y) \land P (y, z)) \to P (x, z))

\begin{aligned} \forall x ((x = 0) & \lor \exists y (x * y = 1)) \\ \neg (x = 0) & \to "" \\ \forall x (x \neq 0) & : \exists y (x * y = 1) \end{aligned}

\begin{aligned} F ist Tautologie & ⊨ F & F \equiv ⊤ \\ F ist unerfüllbar & F \equiv ⊥ & ⊨ \neg F \end{aligned}

2.6 Beweistechniken

#timestamp 2024-10-02

Komposition von Implikationen:

$S ⟹ T$ und $T ⟹ U$ wahr, dann $S ⟹ U$ wahr

Lemma:

(A \to B) \land (B \to C) ⊨ A \to C

andere Regel $S ⟹ T$ und $S ⟹ U$ wahr, dann $S ⟹ (T und U)$

Begründung:

(A \to B) \land (A \to C) ⊨ A \to (B \land C)

Beweis von Implikationen

Direkter Beweis von $S ⟹ T$

Annahme: $S$ wahr
Beweis: $T$ wahr (unter dieser Annahme)

Bsp: $a, b$ Quadrathzahl (QZ), dann $a * b$ QZ

Beweis:

S: $\exists u \exists v (a = u * u, b = v * v)$

\begin{aligned} \dot{⟹} a b = (u * u) (v * v) \\ \dot{⟹} a b = u * u * v * v \\ \dot{⟹} a b = u v * u v \\ \dot{⟹} a b = (u * v) * (u * v) \\ \dot{⟹} \exists m (a b = m m (m = u * v)) \\ \dot{⟹} a b QZ \end{aligned}

Indirekter Beweis von $S ⟹ T$

Annahme: T Falsch

Beweise $S$ falsch (unter dieser Annahme)

Lemma:

\neg B \to \neg A ⊨ A \to B

Beweis:

$A$	$B$	$\neg B \to \neg A$	$A \to B$
0	0	1	1
0	1	1	1
1	0	0	0
1	1	1	1

Bsp:
Behauptung: Wurzel von irrationaler Zahl $> 0$ ist irrational.

$S : x$ irrational
$T : \sqrt{x}$ irrational
$U = R > 0$

Beweis:

\begin{aligned} T falsch & \dot{⟹} \sqrt{x} rational \\ \dot{⟹} \sqrt{x} = \frac{m}{n} für gewisse ganze Zahlen \\ \dot{⟹} x = \frac{m^{2}}{n^{2}} (m,n in Z) \\ \dot{⟹} x = \frac{u}{v} (für u,v \in n Z) \\ \dot{⟹} x rational \\ \dot{⟹} s falsch \end{aligned}

Modus Ponens-Beweise

Definiere $R$
Beweise $R$ wahr
Beweise $R ⟹ S$ wahr

Lemma: $A \land (A \to B) ⊨ B$

Bsp: $2^{3000} \equiv_{3001} 1 ⟺ 2^{3000} - 1 = m * 3001 für ein m \in Z$

(*) Für $n \in N$ gilt: ( $n > 2$ und $n$ Primzahl $⟹ 2^{n - 1} \equiv_{n} 1$ )

( $3001 > 2$ und $3001$ Primzahl) $⟹ 2^{3000} \equiv_{3001} 1$

Bleibt zu beweisen: $3001$ ist Primzahl.

Fallunterscheidung

(zum Beweis von S)

Definiere $R_{1}, \dots, R_{k}$
Beweise: mindestens eine Aussage $R_{i}$ ist wahr
Beweise: für alle $i = 1, \dots, k$ $R_{i} ⟹ S$ wahr

Lemma: ( $(A_{1} \lor \dots \lor A_{k}) \land (A_{1} \to B) \land \dots \land (A_{k} \to B) ⊨ B$ )

k=1: Modus Ponens
k=2: $(A_{1} \lor A_{2}) \land (A_{1} \to B) \land (A_{2} \to B) ⊨ B$

Bsp:
$U =$ Punktierung eines 4x4 Schachbretts
$S :$ Für $P$ gibt es Überdecukung aller nicht markierter Felder

Beweis mittels Wiederspruch

Definiere $T$
Beweise $T$ falsch
Beweise: $S$ falsch $⟹ T$ falsch

Lemma: $(\neg A \to B) \land \neg B ⊨ A$
Alternative:

""
""
Beweise $S \lor T$ wahr

Lemma: $(A \lor B) \land \neg B ⊨ A$

(beide Lemmas sind äquivalent)

Bsp:
$S : \sqrt{2}$ irrational
$U \geq Z_{0}$

Beweis:

\begin{aligned} S falsch & $ \dot{⟺} \sqrt{2} rational \\ \dot{⟺} \exists m \exists n (\sqrt{2} = \frac{m}{n} \land g c d (m, n) = 1) \\ \dot{⟺} \exists m \exists n (m^{2} = 2 n^{2} \land g c d (m, n) = 1) \end{aligned}

$m^{2} = 2 n^{2} \dot{⟹} 2$ teilt $m^{2}$ $\underset{p r i m f a k t o r z e r l e g u n g}{\underset{⏟}{\dot{⟹}}}$ 2 teilt m
$\dot{⟹}$ 4 teilt $m^{2}$
$\dot{⟹}$ 4 teilt $2 n^{2}$
$\dot{⟹}$ 2 teilt $n^{2}$
$\dot{⟹}$ 2 teilt n
$\dot{⟹} g c d (m, n) \geq_{2}$ .

$S$ falsch $\dot{⟹} \underset{\dot{⟹} T wahr, Wiederspruch, da T offensichtlich falsch}{\underset{⏟}{\exists m \exists n (m^{2} = 2 n^{2} \land \underset{falsch für alle m,n}{\underset{⏟}{g c d (m, n) \geq 2 \land g c d (m, n) = 1}})}}$

Existenzbeweise

Universum $X$ von Parametern
$S_{x}$ für jeden $x \in X$

Ziel: $S_{x}$ wahr für ein $x \in X$
Falls $S_{x}$ durch $P (x)$ definiert, dann Ziel $\exists x P (x)$

ExB ist konstruktiv: Finde $a$ , sodass $S_{a}$ wahr.
Bsp: Skriptum

Beweis mittels Gegenbeispiel

$S_{x}$ für $x \in X$
Behauptung: $S_{x}$ ist nicht wahr für alle $x \in X$
$S_{x}$ durch P(x) gegeben: $\neg \forall x P (x) \equiv \exists x \neg P (x)$

Bsp: Scriptum

Induktionwbeweise

$\forall n P (n)$ ( $U = N$ )

Prinzip: $U = N$ ( ${k, k + 1, \dots}$ )

$P$ Prädikat (unär)

Verankerung: Beweise $P (1)$ wahr (bzw. $P (k)$ wahr)
Induktionsschritt: Beweise $P (n) ⟹ P (n + 1)$ wahr

Theorem: $U = N, P$ Prädukat
$P (0) \land \forall n (P (n) \to P (n + 1))$
$⟹ \forall n P (n)$

3 Mengen, Funktionen

\begin{aligned} A \subseteq A & möglich \\ A \in A & =""= \end{aligned}

Russel's Paradox:

\begin{array}{r} R \overset{d e f}{=} {A | A \notin A} \\ R \in R ⟹ R \notin R \\ R \notin R ⟹ R \in R \end{array}

ZF / ZFC Lösung:

alles ist eine Menge
Prädikat:

\begin{aligned} E (x, y) & x \in y \\ x \notin y \end{aligned}

definition $\in$ , $\subseteq$

\begin{array}{r} A = B \overset{d e f}{=} \forall x (x \in A \leftrightarrow x \in B) \\ A \subseteq B \overset{d e f}{=} \forall x (x \in A \to x \in B) \end{array}

2024_10_07 15_58 Office Lens.jpg|500

Theorem

\begin{array}{r} \neg \exists x E (x, x) \\ \neg \exists x (x \in x) \end{array}

#timestamp 2024-10-09

Bsp 3.4:

\begin{aligned} A & = {{\emptyset}} \\ B & = {{\emptyset}, {\emptyset, \emptyset}} = {{\emptyset}, {\emptyset}} = {{\emptyset}} \\ C & = {\emptyset, {\emptyset}} \\ D & = {\emptyset, {\emptyset, {\emptyset}}} \end{aligned}

\begin{array}{r} x \in {a, b} ⟺ x = a \lor x = b \\ \forall x (x \in {a, b} \leftrightarrow ((x = a) \lor (x = b))) \end{array}

Wegen der Mengendefinition ist

\begin{array}{r} A = B \\ C \in D \\ B \subseteq C \end{array}

Methods to prove that two sets are equal:

(A \subseteq B) \land (B \subseteq A)

Lemma 3.1: ${a} = {b} ⟹ a = b$

Are the sets equal?

{{\emptyset}} \neq {{{\emptyset}}}

Proof with contradiction: We assume (Lemma 3.1) $a \neq b ⟹ {a} \neq {b}$
The contradiction is

\begin{aligned} {{\emptyset}} = {{{\emptyset}}} & \dot{⟹} {\emptyset} = {{\emptyset}} & (Lemma 3.1) \\ \dot{⟹} \emptyset = {\emptyset} & (Lemma 3.1) \\ ⟹ Contradiction \end{aligned}

Note: All elements are also sets themselves. However, we will continue to use capital letters for sets and small letters for elements.

Def: $A$ is an empty set if $\forall x \neg (x \in A)$

Lemma 3.5: There is only one empty set (often denoted as $\emptyset$ )

Lemma 3.6: $\emptyset \subseteq A$ for all $A$ (proof on page 58)

\begin{aligned} {a, b} & = {b, a} \\ (a, b) = (c d) & ⟹ a = c \overset{und}{\land} b = d \end{aligned}

attempt: $(a, b) \overset{d e f}{=} {a, b}$ (wrong, since sets are unordered)
attempt: $(a, b) \overset{d e f}{=} {a, {b}}$ (not possible, since this notation is not possible for all pairs)
attempt: $(a, b) \overset{d e f}{=} {{a}, {a, b}}$

Lemma: ${{a}, {a, b}} = {{c}, {c, d}} ⟺ a = c \land b = d$

$a = b : (a, a) = {{a}}$

Lemma: $A = B ⟺ A \subseteq B und B \subseteq A$
Lemma: $A \subseteq B \land B \subseteq C ⟹ A \subseteq C$ (transitivity)

\begin{aligned} A \subseteq B \land B \subseteq C & \dot{⟺} \forall x (x \in A \to x \in B) \land \forall x (x \in B \to x \in C) & |Def von \subseteq, 2Mal \\ \dot{⟺} \forall x ((x \in A \to x \in B) \land (x \in B \to x \in C)) & | \forall x F \land \forall x G \equiv \forall x (F \land G) \\ \dot{⟹} \forall x (x \in A \to x \in C) & | ((F \to G) \land (G \to H) ⊨ (F \to H)) \\ \dot{⟹} A \subseteq C & | Def. von \subseteq \end{aligned}

Similiarly, we define the natural number

\begin{aligned} 0 & = \emptyset \\ 1 & = {\emptyset} \\ 2 & = 1 \cup {1} \\ s (n) & \overset{d e f}{=} n \cup {n} \\ | n | & = n \end{aligned}

We could also define the plus operator...

\begin{aligned} + \\ m + 0 = m \\ m + s (n) = s (m + n) \end{aligned}

3.2 Mengen, Mengenoperationen

3.2.9 Kartesian product

Def: kartesisches Produkt

\begin{aligned} A \times B = {(a, b) | a \in A \land b \in B} \\ R \times R \end{aligned}

3.2.8 Power set

Def: $P (A) \overset{d e f}{=} {S | S \subseteq A}$

Bsp:

\begin{aligned} P (\emptyset) & = {\emptyset} \neq \emptyset \\ P (\emptyset) & = {\emptyset, {\emptyset}} \\ P ({a, b}) & = {\emptyset, a, b, {a, b}} & (hopefully) \end{aligned}

logical definition of power set

\begin{aligned} x \in P (A) ⟺ x \subseteq A \\ \forall x \exists y \forall z (z \in y \leftrightarrow \underset{something is wrong here}{\underset{⏟}{\forall w (w \in x)}}) \\ \neg \exists u \forall x (x \in u) \end{aligned}

3.2.4 Union and Intersection

The union of two sets is defined as

A \cup B \overset{d e f}{=} {x | x \in A \lor x \in B}

3.3 Relations

3.3.1 Relation concept

binary relation, (A,B)-relation

A (binary) relation $ρ$ from a set A to a set B (also called an (A, B)-relation) is a subset of A × B. If A = B, then $ρ$ is called a relation on A.

Relations (examples):

$A = b = N$
$2 \leq 5$ ( $(2, 5) \in\leq$ )
$\hat{\leq} =\geq$
$\leq \circ \leq=\leq$ (verknüpfung)
$< \circ < \overset{?}{=} <$

Example 3.8:
Let $S$ be all students at ETH, $C$ the set of courses and $P$ of professors

$b e l = {s_{1}, c_{2}, \dots}$ (which studnet takes which course)
$\hat{u n t}$ (which course is teached by which professor)
$u n t$ (which professor teaches which course)
$courseat = bel \circ \hat{unt}$

\begin{aligned} \hat{ρ} \subseteq B \times A \\ \hat{ρ} \overset{d e f}{=} {(b, a) | (a, b) \in ρ} \\ b \hat{ρ} a ⟺ a ρ b \\ ρ \subseteq A \times B \\ σ \subseteq B \times C \\ ρ \circ σ = {(a, c) | \exists b \in B ((a, b) \in ρ \overset{"and" also possible}{\overset{⏞}{\land}} (b, c) \in σ)} \\ σ \circ ρ nicht sonderlich sinnvoll, da nicht gleiche menge \end{aligned}

Example 3.10

\begin{aligned} x ip y & \overset{d e f}{=} x ET of y & IsParent \\ \hat{ip} & = i c & IsChild \\ i p \circ i p & = i g p & IsGrandParent \\ (i c \circ i p) ∖ i d & = i h s & IsHalfSibling \\ i p \circ i g p & = i p \circ i p \circ i p = i p^{3} = i g p \circ i p \\ x \underset{ρ^{*} transitiver abschluss}{\underset{⏟}{(ρ \cup ρ^{2} \cup ρ^{3} \cup \dots)}} y \end{aligned}

Note

relations are sets.

properties of $ρ$	Def. Formula	Set
reflexiv	$a ρ a$ für alle $a$	$i d \subseteq ρ$
irreflexiv	$a ρ a$ für alle $a$	$ρ \cap i d = \emptyset$
symmetrisch	$a ρ b ⟺ b ρ a$	$\hat{ρ} = ρ$
antisymmetrisch	$a ρ a \land b ρ a ⟹ a = b$	$ρ \cap \hat{ρ} \subseteq i d$
transitiv	$a ρ b \land b ρ c ⟹ a ρ c$	$\underset{L e m m a 3.9}{\underset{⏟}{ρ^{2} \subseteq ρ}}$
Lemma 3.9

a ρ b \land b ρ c ⟹ a ρ c ⟺ ρ^{2} \subseteq ρ

antisymmetrical:

\begin{array}{r} a | b \\ | \circ | = | \end{array}

#todo What is $i d$ ?

3.3.5 Composition of Relations

Lemma 3.8: $\hat{ρ \circ σ} = \hat{σ} \circ \hat{ρ}$
Beweis:

\begin{aligned} a \hat{ρ σ} c & \dot{⟺} c ρ σ a & | Def von \hat{} \\ \dot{⟺} \exists b (c ρ b \land b σ a) & | Def von \circ \\ \dot{⟺} \exists b (b σ a \land c ρ b) & | Komm. von \land \\ \dot{⟺} \exists b (a \hat{σ} b \land b \hat{ρ} c) & | Def. von \hat{} \\ \dot{⟺} a \hat{σ} \hat{ρ} c & | Def. von \circ \end{aligned}

3.4 Equivalence Relations

Relations that are reflexive, symmetric and transitive, e.g
$a \equiv_{\overset{m}{7}} b$
$\equiv_{7} \cap \equiv_{5} = \equiv_{35}$

#timestamp 2024-10-16

Def equivalence relation

For an equivalence relation $θ$ on a set $A$ and for $a \in A$ , the set
of elements of A that are equivalent to a is called the equivalence class of a and is
denoted as $[a]_{θ}$

[a]_{θ} \overset{d e f}{=} {b \in A | b θ a}

Example
$Z : a \equiv_{m} b \overset{d e f}{⟺} m | (a - b)$

\begin{aligned} [a]_{\equiv_{m}} & = {\dots, a - 2 m, a - m, a, a + m, a + 2 m, \dots} \\ [0]_{\equiv_{3}} & = {\dots, - 6, - 3, 0, 3, 6, 9, \dots} \\ [1]_{\equiv_{3}} & = {\dots, - 5, - 2, 1, 4, 7 \dots} \end{aligned}

3.4.2

Remark: Since equivalence classes are not connected in between, they divide the set in different parts, called Partitions.

Theorem 3.11 The set $A / θ$ of equivalence classes of an equivalence relation θ on A is
a partition of A.

A / θ \overset{d e f}{=} {[a]_{θ} | a \in A}

3.4.3

(a, b) \sim (c, d) \overset{d e f}{=} a d = b c

Reflexiv:

\begin{aligned} (a, b) \sim (a, b) & \dot{⟺} \underset{is wahr}{\underset{⏟}{a b = b a}} & Def von \sim \\ Komm. von * \\ \dot{⟺} Ueli hatte keine Lust & im Skript \end{aligned}

transitiv:

\begin{aligned} Annahme & (a, b) \sim (c, d) & (1) \\ (c, d) \sim (e, f) & (2) \end{aligned}

zu beweisen:

\begin{aligned} (1), (2) ⟹ (a, b) \sim (e, f) & (S) \\ (1) & \dot{⟺} a d = b c & (3) & (Def von \sim) \\ (2) & \dot{⟹} c f = d e & (4) & ("") \\ (3), (4) & \dot{⟹} a d c f = b c d e & (5) & (Multiplikation ist eine Funktion) \\ (5) & \dot{⟹} a c f = b c e & (6) & d Kürzen, d \neq 0 \end{aligned}

3.5 Partial order Relations

Relations that are reflexive, antisymmetric and transitive

3.5.2 Hasse Diagrams

#todo Was bedeutet kanonisch?

3.5.3 Combinations of Posets and the Lexicographic Order

2024_10_21 15_27 Office Lens.jpg

3.6 Functions

Warning

In DiscMat, $f \circ g$ is calculated in a different order depending wether it is used fro functions or relations

for functions: $g \circ f \to$ first $f$ , then $g$ ( $g (f (a))$ )
for relations: $g \circ f \to$ first $g$ , then $f$ ( $f \to g$ )

injectivity: $a \neq a^{'} ⟹ f (a) \neq f (a^{'})$
surjektivity: $\forall b \in B \exists a \in A (f (a) = b)$

#timestamp 2024-10-23

Lemma 3.x:

$\begin{array}{r} f, g injektiv / surjektiv / bijektiv ⟹ g \circ f injektiv /surjektiv / bijektiv \end{array}$

Beweis:

\begin{aligned} a \neq a^{'} & \dot{⟹} f (a) \neq f (a^{'}) & (f ist inj.) \\ \dot{⟹} g (f (a)) \neq g (f (a^{'})) & (g ist inj.) \\ \dot{⟹} (g \circ f) (a) \neq (g \circ f) (a^{'}) & (Def von \circ) \\ \dot{⟹} g \circ f ist injektiv & (Def von inj.) \end{aligned}

\begin{aligned} A \sim B & \overset{d e f}{⟺} Es gibt Bij. A \to B \\ A ⪯ B & \overset{d e f}{⟺} Inj. \\ A ≺ B \end{aligned}

#timestamp 2024-10-21

3.7 Countable and uncountable sets

\begin{aligned} A \sim B & \overset{d e f}{=} Es gibt eine Bij. A \to B \\ A ≼ B & \overset{d e f}{=} Es gibt eine Inj. \\ A ≺ B & \overset{d e f}{=} Es gibt eine Bij. A \to C mit C \subseteq B \\ A ≼ N & A ist abzählbar \end{aligned}

#timestamp 2024-10-23

3.7.1

Bernstein-Schröder-Theorem:

A ⪯ B und B ⪯ A ⟹ A \sim B

3.7.2

Die natürlichen Zahlen $N$ ist die niedrigste Unendlichkeitsstufe

3.7.3

{0, 1}^{*} = {ϵ, 0, 1, 00, 01, 10, 11, 000, \dots}

{0, 1} * \sim N

$z (a)$
$z (0101) = 5$
$z^{'} (a) = z (1 | | a)$ (injektion, keine bijektion)

Thorem 3.19

\begin{aligned} N \times N & = N \\ {0, 1}^{*} \times {0, 1}^{*} & \sim {0, 1}^{*} \\ (a, b) \mapsto a | | b \end{aligned}

Cor. $A ⪯ N und B ⪯ N ⟹ A \times B ⪯ N$
Theorem:
(i) $A ⪯ N ⟹ A^{n} ⪯ N$
(ii)
(iii) $A^{*} ⪯ N$

Beweis von (iii):
Sei $f : A \to {0, 1}^{*}$
Inkektion $A^{*} \to ({0, 1}^{*})^{*} = (a_{1}, a_{2}, \dots \mapsto (f (a_{1}), \dots)$
Suche: $({0, 1}^{*})^{*} \to {0, 1}^{*}$
Eine Lösung: $(010, 10, 1101) \mapsto 00010011010011 \dots$

\begin{array}{r} 0 \mapsto 00 1 \mapsto 01, \mapsto 11 \end{array}

3.7.4 Uncoutability of ${0, 1}^{\infty}$

\begin{aligned} {0, 1}^{\infty} & N \to {0, 1} \\ {0, 1}^{*} \to {0, 1} \end{aligned}

( ${0, 1}^{\infty} ≻ {0, 1}^{*}$ )
( ${0, 1}^{\infty} ≁ {0, 1}^{*}$ ) !!!

Theorem: ${0, 1}^{*} ≻ N$
Beweis: Sei $f : N \to {0, 1}^{\infty}$ Injektion
$f (i) \overset{d e f}{=} β_{i, 0}, β_{i, 1}, β_{i, 2}, β_{i, 3}$
$\propto \overset{d e f}{=} {\overset{―}{β}}_{0, 0}, {\overset{―}{β}}_{1, 1}, \dots$

2024_10_23 15_55 Office Lens.jpg|200

\begin{aligned} N \times N \times N ≺ {0, 1}^{\infty} & \sim {0, 1}^{\infty} \times {0, 1}^{\infty} \\ {0, 1}^{\infty} \sim R & \sim R \times R \end{aligned}

4 Number Theory

$a | b$ und $a | c ⟹ a | (b + c)$

Proof:

\begin{aligned} a | b & \overset{d e f}{⟺} \exists x (b = a x) \\ b = a x \\ c = a y \\ \dot{⟹} a x + a y = b + c & (wegen Addition von funktionen) \\ \dot{⟹} a (x + y) = b + x & (Distr.gesetz) \\ \dot{⟹} a | (b + x) & (Def. von |) \end{aligned}

Struktur, in der diese Gesetze gelten

(R; +, -, 0, \cdot, 1)

The Ring is a set where the following is true:

there exists the $0$ element (neutral element for addition)
there exists the $1$ element (neutral element for multiplication)
addition:
- associativity, $(- a) + a = 0$ , $a + 0 = a$ , distributivity
multiplication
- #ueliGotBored

Lemma: Für jedes $a$ gilt: $a \cdot 0 = 0$
Proof:

\begin{aligned} a \cdot 0 & = 0 + a \cdot 0 & (0 + b = b \forall b) \\ = ((- a 0) + a 0) + a 0 & (associativity) \\ = (- a 0) + a 0 + a 0 & ((- b) + b = 0 \forall b) \\ = (- a 0) + a (0 + 0) & (DG.) \\ = (- a 0) + a 0 & (0 + 0 = 0) \\ = 0 & (wie 2) \end{aligned}

Z [i]

Ring aller komplexen Zahlen mit ganzem Real-/Imaginärteil
z.b. Multiplikation:

\begin{array}{r} (a + b i) (c + d i) = a c - b d + (a d + b c) i \end{array}

-> eigentlich addition von winkel und Längenbetrag

4.1.1 Number Theory as a Mathematical Discipline

Catalan conjecture:

y^{a} - x^{b} = 1

for $a, b > 1$

4.4.2 Division mit Remainder

Theorem: dividieren mit Rest

a = d q + r 0 \leq r < | d |

Pasted image 20241028145513.png|500

4.2.3 Greatest common divisor

Definition 4.2

For integers $a$ and $b$ (not both $0$ ), an integer $d$ is called a greatest common divisor of $a$ and $b$ if $d$ divides both $a$ and $b$ and if every common divisor of $a$ and $b$ divides d, i.e., if

d | a \land d | b \land \forall c ((c | a \land c | b) \to c | d)

e.g. $a = 30, b = 45$

{- 15, - 5, - 3, - 1, 1, 3, 5, \underset{g c d (a . b)}{\underset{⏟}{15}}}

-> $g c d$ refers only to the positive divisor

Lemma 4.2

gcd (m, n - q m) = g c d (m, n)

Proof: Let $A$ be the set of all common divisors or $m, n$ . Then #ueliGotBored

Definition 4.4

The ideal generated by a,b (set of all linear combinations of a,b) is

(a, b) \overset{d e f}{=} {u a + v b | u . v \in Z}

similarly, the ideal of a single int is

(a) = {u a | u \in Z}

e.g. $(10, 16) = {0, 10, 16, 26, 6, 4, 2, \dots} = (2)$

Lemma $(a, b) = \underset{g . g . T (a, b), weil negativ auch möglich}{\underset{⏟}{(d)}}$
Corollary 4.5

gcd (a, b) = u a + v b

e.g $a = 17, b = 7$
$(17, 7) = Z$

4.3 Factorization into Primes

not relevant for exam (?)

4.5 Congruences and Modular Arithmetic

4.5.1 Modular Congruences

Example 4.9

\underset{\equiv_{3} 2}{\underset{⏟}{x^{3} - x - 1}} = \underset{\equiv_{3} 0, 1}{\underset{⏟}{y^{2}}}

Def: 4.8

a \equiv_{m} b \overset{d e f}{⟺} m | (a - b)

$a \equiv_{m} b$
$c \equiv_{m} d$

-> $a + c \equiv_{m} b + d$

#timestamp 2024-10-30

Bem:

\begin{aligned} a \equiv_{m} b & \overset{d e f}{⟺} m | (a - b) \\ aber nicht hier verwendet: \\ a \mod b & (bedeutet eigentlich rest) \end{aligned}

Lemma 3.14

a \equiv_{m} b und c \equiv_{m} d ⟹ a + c \equiv_{m} b + d

4.5.2 Modular Arithmetic

Corollary:

R_{m} (f (a_{1}, \dots, a_{k})) = R_{m} (f (R_{m} (a_{1})), \dots, f (R_{m} (a_{k})))

works only if we are only interested in the remainder
Example

R_{13} (3^{100}) = R_{13} (\underset{1}{\underset{⏟}{(\underset{1}{\underset{⏟}{3^{3}}})^{33}}} 3) = 3

#todo: look up "Neunertest"

4.5.3 Multiplicative Inverses

Lemma 4.18 The congruence equation

a x \equiv_{m} 1

has a solution $x \in Z_{m} ⟺ gcd (a, m) = 1$ . The solution is unique.

Proof of $⟸$

\begin{aligned} gcd ((a, m)) & \dot{⟹} u a + v m = 1 & cor 4.5 \\ \dot{⟹} a u \equiv_{m} 1 & v m \equiv_{m} 0, lemm 4.14, komm von \cdot \\ \dot{⟹} a \cdot R_{m} (u) \equiv_{m} 1 \end{aligned}

4.5.4 The Chinese Remainder Theorem

Example
Pasted image 20241103165251.png|400

5

Bsp

\begin{aligned} < S; * > \\ < Z; +, -, 0 > \\ < Z; > \end{aligned}

*	a	b	c
a	b	c	a
b	c	b a	b
c	a	b	c

\begin{aligned} c * x & = x & c ist ein neutrales element \\ x * c & = c \\ (b * b) * a = b * a = c & \neq b = b * c = b * (b * a) & nicht kommutativ -> mittleres feld ändern \end{aligned}

Bsp

Assume $e$ exists and is a neutral element

*	e	a	b	c
e	e	a	b	c
a	a	e	c	b
b	b	c	e	a
c	c	b	a	e
-> associative, because
-> commutative

5.2 Monoids and Groups

5.2.1 Neutral element

Lemma 5.1:

\begin{array}{ll} e ist LNE \\ e^{'} ist RNE \end{array}} ⟹ e = e^{'}

Beweis:

\begin{aligned} e * e^{'} = e (e^{'} ist RNE) \\ e * e^{'} = e^{'} (e ist LNE) \\ ⟹ e = e^{'} \end{aligned}

5.2.3 Inverses and Groups

< M; *, e > monoid

Lemma 5.2

\begin{array}{ll} L I & b * a = e \\ R I & a * c = e \end{array}} \overset{Lemma}{⟹} b = c

Proof

\begin{aligned} b & = b * e & (e ist NE) \\ = b * (a * c) & () \\ = (b * a) * c & (Ass.) \\ = e * c & (Ass) \\ = e & (e NE) \end{aligned}

Def 5.7 Group

A group is an algebra $< G; *, \hat{,} e >$ satisfying the following axioms:

$*$ is associative.
$e$ is a neutral element: $a * e = e * a$ for all $a \in G$ .
Every $a \in G$ has an inverse element $\hat{a}$ , i.e. $a * \hat{a} = \hat{a} * a = e$

Bsp

\begin{aligned} < Q ∖ {0}; \cdot, (\cdot)^{- 1}, 1 > \\ < Z; +, -, 0 > \\ < Z_{m}; \oplus_{m}, ⊖_{m}, 0 > \\ < Z_{m}^{*}; ⊙_{m}, \hat{}, 1 > & Z_{p} \\ < Z_{15}^{*} \end{aligned}

\begin{aligned} G 1 & \forall x \forall y \forall z (x * y) * z = x * (y * z) \\ \forall x \forall y \forall z f (f (x, y), z) = f (x, f (y, z)) \\ G 2^{'} & \forall x \underset{G 2 := e * x}{\underset{⏟}{x * e}} = x \\ \forall x f (x, e) = x \\ G 3^{'} & \forall x \exists y \underset{G 3 : y * x}{\underset{⏟}{x * y}} = e \end{aligned}

Lemma 5.3

\begin{aligned} (i) & \hat{\hat{a}} = a \\ (i i) & \hat{a * b} = \hat{b} * \hat{a} \\ \dots \end{aligned}

5.2.4 (Non-)minimality of the Group Axioms

**Lemma **

{G 1, G 2^{'}, G 3^{'}} ⊨ G 3

Proof:

\begin{aligned} \hat{a} * a & = (\hat{a} * a) * e & G2’; note: e has been written right \\ = (\hat{a} * \underset{e}{\underset{⏟}{a) * (\hat{a}}} * \hat{\hat{a}}) \\ = \hat{a} * \hat{\hat{a}} \\ = \hat{a} * a \end{aligned}

5.2.5 Some examples of groups

*	e	a
e	e	a
a	a	e

\begin{aligned} < Z_{2}; \oplus_{2} > \\ Z_{3} \\ Z_{4} & Z_{2} \times Z_{2} \\ Z_{5} \end{aligned}

$S_{3}$

2024_11_04 15_57 Office Lens.jpg|300

assoziativ, inverse, bijektion -> gruppe
- kleinste Gruppe (6 elemente), die nicht kommutativ ist

< Z_{m}^{*}; ⊙_{m} >

Z_{m}^{*} = {1, 2, 3, 4}

Z_{5}^{*} ≃ Z_{4}

\begin{aligned} Z_{8}^{*} & = {1, 3, 5, 7} \\ Z_{8}^{*} & = Z_{2} \times Z_{2} \end{aligned}

-> $Z_{8}^{*}$ isomorph, da Neutralelement auf Diagonale

nicht zyklisch (?)

2024_11_06 14_59 Office Lens.jpg

Untergruppe aus Drehungen

cyklische gruppe
isomorph zu $Z_{4}$

$S_{◻} \subseteq S_{4}$

wir kriegen nicht alle Permutationen, weil räumliche nicht möglich sind (?)

-> anzahl Elemente einer Untergruppe ist Teiler der Gruppe

5.3 The structure of groups

5.3.1 Direct Product of groups

Definition 5.9. Direct product of grroups

The direct product of $n$ groups $< G_{1}; *_{1 >}, \dots, < G_{n}; *_{n} >$ is the algebra

< G_{1} \times \dots \times G_{n}; * >

where the operation $*$ is component-wise:

(a_{1}, \dots a_{n}) ⋆ (b_{1}, \dots, b_{n}) = (a_{1} * b_{1}, \dots, a_{n} * b_{n})

5.3.2 Group Homomorphisms

strukturerhaltende abbildung

2024_11_06 15_47 Office Lens.jpg|400

homomorphism:
isomprhism: homomorphism which is bijective
automorphism: isomorphism to itself

Lemma 5.5
$ψ : \underset{*}{\underset{⏟}{G}} \to \underset{⋄}{\underset{⏟}{H}}$
(i): $ψ (e) = e^{'}$
(ii) $ψ (\hat{a}) = {\hat{ψ (a)}}^{H}$

Proof of $(i)$ :

\begin{aligned} e^{'} & = ψ (e) ⋄ \hat{ψ (e)} & (G3 für H) \\ = ψ (e * e) ⋄ \hat{ψ (e)} & (G2’ für G) \\ = (ψ (e) ⋄ ψ (e)) ⋄ \hat{ψ (e)} & (Hom. def.) \\ = ψ (e) ⋄ (ψ (e) ⋄ \hat{ψ (e)}) & (G1 für H) \\ = ψ (e) ⋄ e^{'} & (G3 für H) \\ = ψ (e) & (G2 für H (?)) \end{aligned}

n	(nicht isomorphe) Gruppen $G$ mit $\| G \| = n$
2	$Z_{2}$
3	$Z_{3}$
4	$Z_{4}, Z_{2} \times Z_{2}$
5	$Z_{5}$
6	$Z_{6}, S_{3}$ ( $S_{3}$ nicht kommutativ)
7	$Z_{7}$ (bei primzahlen gibt es immer nur zyklische Gruppe, addition mod7)
8	$Z_{8}, Z_{2} \times Z_{4}, Z_{2} \times Z_{2} \times Z_{2}, S_{◻}, Q_{8}$ ( $S_{◻}, Q_{8}$ n.k., $S_{◻}$ heisst $D_{4}$ auf wikipedia)
...
Betrachte $Z_{2} \times Z_{4}$

01,01,02,03
10,11,12,13

Betrachte $Z_{15}^{*}$

{1, 2, 4, 7, 8, 11, 13, 14} (alle Teilerfremnden elemente von 15)

-> kommutativ
-> isomorph zu $Z_{2} \times Z_{4}$ , da

00->1  01->7 02->4  03->13
10->11 11->2 12->14 13->8

Bilden Untergruppen:

00, 10 00, 11, 02, 13 (Prüfen: zeigen, dass 1,2,4,8 mit modulo untergruppe bilden)

#timestamp 2024-11-11

Repetition
Example direct product, isomorphism
$⟨ Z_{2}, \oplus_{2} ⟩ \times ⟨ Z_{4}, \oplus_{4} ⟩$
$Z_{20}^{*} = {1, 3, 7, 9, 11, 13, 17, 19} (all element that are not divisible by 2,4,5)$

01 01 02 03
1  3  9  7  -> 3 (3^1=3, 3^2=9, 3^3=7, 3^4=1 -> cyclic)
10 11 12 13
11 13 19 17 ->

there is an isomorphism:

\begin{aligned} Z_{2} \times Z_{4} & \to Z_{20}^{*} \\ (0, 1) & \mapsto 3 \\ (1, 0) & \mapsto 11 \end{aligned}

subgroups:
2024_11_11 15_53 Office Lens.jpg|300

5.3.4 The Order of Group Elements and of a Group

\begin{aligned} G, & a^{0} = e \\ a^{n} = \underset{n m a l}{\underset{⏟}{a * a * \dots * a}} \\ a^{- 1} = \hat{a} \\ a^{m} * a^{n} = a^{m * n} & Z \to G (homomorphismus zu ganzen Zahlen) \end{aligned}

-> $o r d (a) = min {n \geq 1 | a^{n} = e}$

not to be confused with:
$| G |$ (number of elemente in G)

a^{n} = a^{R_{o r d (a)} (n)}

Lemma 5.6

finite group $G ⟹ o r d (a)$ is finite

Example
$⟨ Z_{12}; ⊙_{12} ⟩ 2, 4, 8, 4, 8, 4, 8, \dots$
-> false, because $⟨ Z_{12}, ⊙_{12} ⟩$ is a monoid, not a group

Proof

\begin{aligned} a^{r} & = a^{s} = b \\ a^{s - r} & = b * b^{- 1} = e & (because a^{- 1} = \hat{a}) \\ ⟹ o r d < \infty ◻ & (? why) \end{aligned}

5.3.5 Cyclic Groups

Definition 5.14

The group generated by $a$ is

⟨ a ⟩ = {a^{n} | n \in Z}

Example

$Z_{19}^{*} = ⟨ 2 ⟩, | Z_{19}^{*} | = 18$
is also true for $\infty$ groups:
$⟨ Z; + ⟩ = ⟨ 1 ⟩$
if a group is cyclic, it is also isomorph to $⟨ Z_{n}, \oplus_{n} ⟩$
$G = ⟨ G ⟩ ≃ ⟨ Z_{n}; \oplus_{n} ⟩$

$| G | = n | G | = p (p r i m)$
-> G is always cyclic

5.3.7 The Order of Subgroups

Theorem 5.8 (Lagrange)

Let $G$ be a finite group and $H$ a subgroup of $G$ , then

| H | divides | G |

Proof:
$G : \underset{* a = a}{\underset{⏟}{e}}, \underset{* a = a * h_{2}}{\underset{⏟}{h_{2}}}, \dots, \underset{* a = a * h_{| H |}}{\underset{⏟}{h_{| H |}}}$

\begin{aligned} H & : e, h_{2}, \dots, h_{| H |} \\ * a & : a, a * h_{2}, \dots, a * h_{| H |} \\ * b \end{aligned}

2024_11_11 14_43 Office Lens.jpg|300

Corollary 5.10 (extended)
$a^{o r d (a)} = e$
$a^{| G |} = e$
$| ⟨ a ⟩ | = o r d (a) = | G |$

5.3.8 The Group $Z_{m}^{*}$ and Euler’s Function

Theorem: $⟨ Z_{m}^{*}; ⊙_{m} ⟩$ is a group
$gcd (a, m) = 1 and gcd (b, m) = 1 ⟹ gcd (a b, m) = 1$

$| Z_{m}^{*} | = φ (m)$

$φ (15) = 8$
$φ (20) = 8$
$φ (12) = 4$
$φ (27) = 18$

\begin{aligned} m & = \prod_{i = 1}^{r} p_{i}^{e_{i}} \\ φ (m) & = \prod_{i = 1}^{r} \dots \\ φ (p_{i}^{e_{i}}) & = \overset{}{\overset{⏞}{p_{i}^{e_{i} - 1} (p_{i} - 1)}} \end{aligned}

Corollary 5.14
$a^{φ (m)} \equiv_{m} 1$
$a^{p - 1} \equiv_{p} 1 (where p is a prime, but also works for some other numbers)$

5.4 Application: RSA Public-Key Encryption

5.4.1 $e$ -th Roots in a Group

Theorem 5.16

$\begin{aligned} G : & x \mapsto x^{e} gcd (e, | G |) = 1 \\ y \mapsto y^{d} e d \equiv_{| G |} 1 \end{aligned}$

G is a bijektion

Proof

\begin{array}{r} (x^{e})^{d} = x^{e d} = x^{k | G | + 1} = (\underset{1}{\underset{⏟}{x^{| G |}}})^{k} x = x \end{array}

Idea behind RSA:
$Z_{m}^{*}$ mit $m = p * q | φ (m) = (p - 1) (q - 1)$

2024_11_11 15_53 Office Lens (1).jpg|500

#timestamp 2024-11-13

5.5 Rings and Fields

We now consider algebraic systems with two binary operations, usually called
addition and multiplication.

5.5.1 Definition of a Ring

Definition 5.18.

A ring 〈R; +, −, 0, ·, 1〉 is an algebra for which

(i) $⟨ R; x, -, 0 ⟩$ is a commutative group.
(ii) $⟨ R; \cdot, 1 ⟩$ is a monoid.
(iii) $a (b + c) = (a b) + (a c) and (b + c) a = (b a) + (c a)$ for all a, b, c ∈ R (left and right distributive laws).
A ring is called commutative if multiplication is commutative $(a b = b a)$ [21]

Lemma

\begin{aligned} 0 a & = 0 \\ (- a) b & = - (a b) \end{aligned}

$i v) 1 \neq 0 falls |R| \geq 2$

Proof
Sei $a \neq$ beliebig
$a \cdot 0 = 0 Lemma S.17 (i)$
W'beweis: Annahme $1 = 0$

\begin{aligned} \dot{⟹} a 0 \overset{weil 1=0}{=} a 1 \overset{1 ist NE}{=} a \\ \dot{⟹} a = 0 & W S \end{aligned}

Proof (formal)

\begin{aligned} a \neq_{0} & (1) \\ W B : & 1 = 0 & (2) \\ a \cdot 0 = 0 & (3) & (Lemma 5.17 (i)) \\ (2) ⟹ & a 0 = a 1 & (4) & (Multiplikation ist F.) \\ a 1 = a & (5) & (1 ist NE von *) \\ (3), (4), (5) \dot{⟹} & 0 = a & W S \end{aligned}

Example
$R$ (z.B. $Z, R$ )

neuer Ring
$(R \times R; + m \dots)$
addition: $(a, b) + (a^{'}, b^{'}) = (a + a^{'}, b + b^{'})$
NE der A. (0,0)
multiplikation: $(a, b) \cdot (a^{'}, b^{'}) = (a a^{'} \pm b b^{'}, a b^{'} \pm b a^{'}) \to interessanter mit - \to complexe Zahlen$
NE der M. $(1, 0)$

-> ring-axiome überprüfen
-> commutativity:
#ueliGotBored

Proof of [21]

\begin{aligned} (1 + 1) (a + b) & = 1 (a + b) + 1 (a + b) \\ = (a + b) + (a + b) \\ = a + b + a + b \\ = (1 + 1) a + (1 + 1) b \\ = 1 \cdot a + 1 \cdot a + 1 \cdot b + 1 \cdot b \\ = a + a + b + b \end{aligned}

5.5.2 Units and the Multiplicative Group of a Ring

Example:

\begin{aligned} R R^{*} \\ (a_{0}, a_{1}, a_{2}) \\ * (b_{0}, b_{1}, b_{2}, b_{3}) & = (f_{0}, f_{1}, f_{2}, f_{3}, \dots \\ f_{0} & = a_{0} b_{0} \\ f_{1} & = a_{0} b_{1} + a_{1} b_{0} \\ f_{2} & = a_{0} b_{2} + a_{1} b_{1} + a_{2} b_{0} \\ später im Skript & a_{2} x^{2} + a_{1} x + a_{0} & R [x] \end{aligned}

Def
$R^{*} = {u | u ist invertible}$

Lemma

\begin{aligned} R^{*} & u, v \in R^{*} ⟹ u v \in R^{*} \\ (u v)^{- 1} = v^{- 1} u^{- 1} \end{aligned}

5.5.4 Zerodivisors and Integral Domains

Example
$a \neq 0, b \neq 0 : a b = 0$
$Z_{20} : 8 ⊙_{15} 15 = 0$
-> not an integral domain ("Integritätsbereich")

Definition 5.24.

An integral domain $D$ is a (nontrivial) commutative ring without zerodivisors: For all $a, b \in D$ we have $a b = 0 ⟹ a = 0 \lor b = 0$ .

5.6.1 Factorization and Irreducible Polynomials

$Z_{5} [x]$
$(3 x + 2) (2 x + 4) = x^{2} + x + 3$
$Z_{2} [x]$
$\underset{irreducible polynom}{\underset{⏟}{(x^{2} + x + 1)}} (x + 1) = x^{3}$

Example (ring with complex numbers)

$3$ is irreducible
$2 + i$ is irreducible
2 is not irreducible

-> all prime numbers (?)

#timestamp 2024-11-18

recap:
Ring R
Bsp:

$Z, Z_{m}, R, C, R [x]$
$R [x] : (x + 1) + (x^{2} + 2 x + 3)$
$Z_{5} [x] : (2 x + 3) (3 x + 4) = x^{2} + 2 x + 2$
$R^{*}$ -> invertierbare gruppe, ähnlich $Z_{m}^{*}$
$R [x]^{*} = R^{*}$ -> polynome höheren Grades haben keine Inverse
$R^{*} = R ∖ {0}$ -> Körper $F$
$F$

Ein Polynom von grad n kann mit n+1 Stützstellen interpoliert werden
-> folgendes Polynom kann mit vier Stützstellen interpoliert werden (nur in Körpern!)
-> daraus kann S berechnet werden
Pasted image 20241118142853.png|300
H-Ring:

komplexe Zahlen sind Drehungen, Streckungen
H-Ring: Drehungen, Streckungen im Raum

$i^{2} = - 1$
-> zwei-dimensionale Erweiterung
$i^{2} = j^{2} = k^{2} = i j k = - 1$
$(a + b i + c j + d k)$
-> vier-dimensionale Erweiterung (quadronionen) der reelen zahlen, Ring

$H^{*} = H ∖ {0}$
nicht kommutativ

Gruppe: ${1, - 1, i, - i, j, - j, k, - k} = Q_{8}$ (5. Gruppe mit 8 Elementen)

nicht isomorph zu $D_{4}$ (jede Spiegelung hat $o r d = 2$ + zwei $o r d = 4$ )
$Q_{8}$ alle Elemente $o r d = 4$

-> 8-dimensionale Erweiterung noch möglich

nur noch alternativ assoziativ
- $a (a b) = (a a) b$
- $a (b b) = (a b) b$

5.5.6 Fields

Theorem 5.24

A field is an integral domain (IB)

Proof: Einheit in Ring ist nicht NT ()

\begin{aligned} u \in R^{*} & ⟹ (u v = 0 ⟹ v = 0) \\ \begin{array}{ll} u \in R^{*} \\ u v = 0 \end{array}} & ⟹ v = \underset{1}{\underset{⏟}{u^{- 1} \cdot u}} \cdot v = u^{- 1} \cdot 0 = 0 \end{aligned}

Theorem 5.23

$\overset{G F (p)}{\overset{⏞}{Z_{p} ist Körper}} ⟺ p prim$

we know:
$Z \to Z_{m} \to Z_{p} \to Körper$
our goal this week:
$F \to \underset{f i n i t e f i e l d}{\underset{⏟}{F [x]}} \to F [x]_{m (x)} \to F [x]_{p (x)} \to Körper \to F \to \dots$
-> constructing new fields

Note: $Z_{m}, F [x]_{m (x)}$ sind keine körper

5.6 Polynomials over a field ( $F [x]$ )

5.6.1 Factorization and Irreducible Polynomials

\begin{aligned} R [x] : & x^{2} + 3 x + 2 = (x + 1) (x + 2) \\ x^{2} + 1 & irreduzibel \\ x^{4} + 1 = (x^{2} + \sqrt{2} x + 1) (x^{2} - \sqrt{2} x + 1) \end{aligned}

Pasted image 20241118150227.png|300

-> es gibt keine irreduziblen Polynome mit Grad $> 2$

Teiler von $x^{2} + 3 x + 2$
-> $π x + π$ ist teiler ( $\frac{1}{π} x + \frac{2}{π}$ )

$gcd (x^{2} + 4 x + 3, x^{2} + 3 x + 2) = x + 1$

$\underset{Z_{5}}{\underset{⏟}{G F (5) [x]}} x^{3} + 4 x^{2} + 1$
-> nullstelle: $(x + 3) (\underset{f (x) i r r .}{\underset{⏟}{x^{2} + x + 2}})$

a	0	1	2	3	4
f(a)	2	4	3	4	2
-> keine Nullstelle -> irr.

Polynome (grad 2,3) sind irreduzibel, wenn keine Nullstelle,
stimmt nicht für grad 4 (wiehe Bsp oben $x^{4} + 1$ )

Bsp
$G F (2) [x] : x^{5} + x^{4} + 1 = (x^{2} + x + 1) (x^{3} + x + 1)$

#todo
Lemma: Wenn exponenten restklasse bilden

5.6.2

Bsp

\begin{aligned} G F (7) [x] : & (3 x^{4} +_x + 5) : (2 x^{2} + x + 1) = 5 x^{2} \\ \dots \end{aligned}

( $5 = \frac{3}{2} = 3 \cdot 2^{- 1} = 3 \cdot 4 = 5$ )

vollständige division:
Pasted image 20241118154525.png|600

Wir wollen:
$a (x) = b (x) q (x) + r (x)$
wobei $\deg (r (x)) < \deg (b (x))$ .

-> Zeigen: Lösung eindeutig, Rest < Grad 2

Bsp
$G F (2) [x] (x^{4} + x + 1) : (x^{2} + x + 1) =$

Zentrale idee: Division mit Rest eindeutig, mit Bedignung für Rest

bei reelen Zahlen betrag, hier

Ring müsste Integritätsbereich sein.

#timestamp 2024-11-20

$R$

alle Elemente sind Einheiten (invertierbar) -> kann leicht faktorisiert werden

$| R^{*} | "<<" | R |$

faktorisiertungen interessanter

nicht-trivialen Fakt.: $a = b \cdot c$ mit $b, c, \notin R^{*}$

Bsp komplexe Zahlen

$(1 + 3 i) = (1 + i) (2 + 1)$
wenn Länge Wurzel Primzahl ist -> irreduzibel

2024_11_20 14_57 Office Lens.jpg|300
$| Z [i]_{2 + i} | = 13$

$F [x] a (x) = b (x) q (x) + r (x)$
$\deg (r (x)) < \deg (m (x))$

$a (x) \equiv_{m (x)} r (x)$
$R_{m (x)} (a (x)) = r (x)$

Bsp $R [x]$
$R [x] : (5 x^{3} - 2 x + 1) : (3 x^{2} + 2) = \frac{5}{3} x (rest - \frac{16}{3} x + 1)$

5.7 Polynomials as Functions

5.7.1 Polynomial Evaulations

Example 5.58

\begin{aligned} G F (5) [x] : a (x) = 2 x^{3} + 3 x + & 1 \\ (mit Nullstelle:) & 2 \end{aligned}

$α$	0	1	2	3	4
$a (α)$	1	1	3	4	1
	2	2	4	0	2

Lemma 5.28
$a (α) + b (α) = (a + b) (α)$
$a (α) \cdot b (α) = (a \cdot b) (α)$

5.7.2 Roots

Lemma 5.29 (im Körper $F [x]$ )
$(x - α) | a (x) ⟺ a (α) = 0 (aussage, hat nicht mit ringen, etc. u tun)$

Proof

\begin{aligned} (⟹) a (x) & = (x - α) q (x) & (def |) \\ a (α) & = \underset{0}{\underset{⏟}{(α - α)}} q (α) = 0 \\ (⟸) a (x) & = (x - α) q (x) + \underset{c o n s t . = r}{\underset{⏟}{r (x)}} \\ \underset{0}{\underset{⏟}{a (α)}} & = \underset{0}{\underset{⏟}{(α - α)}} q (α) + r \\ ⟹ r = 0 \end{aligned}

Theorem 5.31
$F [x] a (x) \deg (a (x)) = d$
$a (x)$ hat $\leq d$ Nullstellen

Proof

\begin{aligned} a (x) hat NS α_{1}, \dots, a_{e} & e > d \\ \dot{⟹} (x - a_{i}) | a (x) & i = 1, \dots, e \\ \dot{⟹} \prod_{i = 1}^{e} (x - α_{i}) | a (x) \end{aligned}

5.7.3 Polynomial Interpolation

Bsp $G F (5) [x] : a (x) Grad \leq 2$
$a (x) = a_{2} x^{2} + a_{1}^{x} + a_{0}$

\begin{aligned} Gegeben : m \\ a (x) = a_{2} x^{2} + a_{1} x & + a_{0} \\ a (1) = 2, a (3) & = 1, a (4) = 4 \\ a_{2} + a_{2} + a_{0} & = 2 \\ 4 a_{2} + 3 a_{1} + a_{0} & = 1 \\ a_{2} + 4 a_{1} + a_{0} & = 4 \end{aligned}

-> z.B. Gauss-Elimination funktioniert, weil Körper ist

Lemma 5.32
Ein Polynom in $F [x]$ mit Grad $\leq d$ kann mit $d + 1$ Stützstellen eindeutig interpoliert werden.

Proof:

\begin{aligned} a (α_{1}) & = β_{1}, \dots, a (α_{d + 1}) = β_{d + 1} \\ u_{i} (x) & : u_{i} (α_{i}) = 1 \\ u_{i} (α_{j}) = 0 j \neq i \\ u_{i} (x) & = \frac{(x - α_{1}) \dots (x - α_{i - 1}) (x - α_{i + 1}) \dots (x - α_{d + 1})}{(α_{i} - α_{1}) \dots (α_{i} - α_{i - 1}) (α_{i} - α_{i + 1}) \dots (α_{i} - α_{d + 1})} & (unten nur Körperelemente mit grad d) \\ a (x) & = \sum_{k = 1}^{d + 1} β_{k} u_{k} (x) & (nur dort nicht null, wo k=i -> korrekte interpolation) \\ a (x) & - a^{'} (x) = b (x) \\ b (α_{i}) & = 0 & für alle a_{i}; i = 1, \dots, d + 1 \to d+1 NS \\ ⟹ a(x) eindeutig, da wegen theorem 5.31 nicht mglich \end{aligned}

5.8 Finite fields

5.8.1 The Ring $F [x]_{m (x)}$

\begin{aligned} F [x]_{\underset{grad d, modulo}{\underset{⏟}{m (x)}}} = {a (x) | \deg (a (x)) < d} \\ | F [x]_{m (x)} | = | F |^{d} \end{aligned}

-> addition komponentenweise
-> multiplikation wird grad grösser, modulo durchdividieren
-> assoziativität, distributivität gilt
-> Ring

-> Achtung:

F Körper
F[x] Polynome über x
$F [x]_{m (x)}$ neuer Ring

-> bei allen heisst Addition $+$ , Multiplikation $\cdot$ (aber verschiedene Strukturen)

$a b \equiv_{m} 1$ hat Lösung $⟺$ $gcd (a, m) = 1$
zeigen:
$a (x) b (x) \equiv_{m_{x}} 1$ hat Lösung $⟺ gcd (a (x), m (x)) = 1$
Proof
$(a, m) = (d)$ wobei $d = gcd (a, m)$
$(a (x), m (x)) = (d (x))$ wobei $d (x) = gcd (a (x), m (x))$
=> $a (x) u (x) + \underset{0 \equiv_{m (x)} 1}{\underset{⏟}{m (x) v (x)}} = 1$
=> $R_{m (x)} (u (x))$ inverses (existiert nur wen $gcd = 1$ )

-> all Polynome mit grad $< d$ sind invertierbar -> Körper
-> $G F (q^{d})$ wobei $q^{d} = | F |$ (oder nur $q$ (?))

Körper mit gleich vielen Elementen sind Isomorph

Bsp
$m (x)$ irreduzibles Polynom

$R [x]_{x^{2} + 1}$ -> (neuer) Körper

#timestamp 2024-11-25
wurde mit Aufzeichnung nachgeholt

recap chapter 5:

Pasted image 20241201113100.png
Fehler: hat $d$ NS.
-> verschiedene Polynome können höchstens an d-1 Nullstellen übereinstimmen
wichtig für fehler-korrigierende codes

5.8.2 Constructing Extension fields

Bsp

\begin{aligned} R [x]_{x^{2} + 1} \\ gcd (2 x + 3, x^{2} + 1) = 1 \\ (2 x + 3) (u x + v) = t (x^{2} + 1) + 1 \\ G F (2) [x]_{x^{3} + x + 1} \\ (x^{2})^{- 1} \\ x^{2} (u x^{2} + v x + w) = (s x + t) (x^{3} + x + 1) + 1 & 5 gleichungen, 5 var \end{aligned}

Bsp

\begin{aligned} G F (2) [x]_{x^{3} + x + 1} \\ 001 \\ x & 010 \\ x^{2} & 100 \\ x^{3} & = x + 1 & 011 \\ x^{4} & = x^{2} + x & 110 \\ x^{5} & = x^{2} + x + 1 & 111 \\ x^{6} & = x^{2} + 1 & 101 \\ x^{7} & = 1 & 001 \end{aligned}

LFSR (Linear-gekoppeltes Schieberegister)
Pasted image 20241201114107.png
Folge: $\underset{P e r i o d e}{\underset{⏟}{0010111}} 001$ (Länge 7)

Bei LFSR Länge $n$

elemente: $2^{n} - 1$
- $2^{n} - 1$ 1en
- $2^{n} - 1$ 0en

Bsp
Wenn Folge von LFSR moduliert ausgesendet wird, und von Planeten zurückgeworfen wird, kann man Distanz zu Planeten bestimmen (folge wiederholt sich, man kann verschiebung herauslesen -> mit Lichtgeschw. auch Distanz).
fun fact: flaches Spektrum -> spread spectrum

5.8.3 Some Facts About Finite Fields

nicht prüfungsrelevant

Es gibt endliche körper $\forall G F (p^{n})$ -> nichttrivial

5.9 Application: Error-Correcting codes

binär-symmetrischer kanal
Pasted image 20241201115823.png

\begin{aligned} \begin{array}{ll} 0 \to 000 \\ 1 \mapsto 111 \end{array}} & Fehler-WSK : ϵ^{3} + 32 e^{2} (ϵ - 1) \approx 3 ϵ^{2} \\ \begin{array}{ll} 0 \to 00000 \\ 1 \mapsto 11111 \end{array}} & ϵ^{5} + 5 \dots + (_{5}^{3}) ϵ^{3} (1 - ϵ) \approx 10 ϵ^{3} \\ \begin{array}{ll} 0 \to 0000000 \\ 1 \mapsto 1111111 \end{array}} & \approx (_{3}^{7}) ϵ^{4} \end{aligned}

Wieso nur ungerade Anzahlen? -> Mehrheitsentscheidung

(Minimal)distanz soll möglichst gross sein

hälfte der fehler kann korrigiert werden -> falls $d_{m i n} = 2 t + 1$ , kann $2 t$ fehler korrigieren
hier: mindestens Distanz 4
- geht nicht durch ausprobieren
- parity bits: jedes der 7 bits als lin.komb. der 3 bits (modulo $2$ )
  - (7,3) Code
  - idee: mit matrizen als lin.komb. schreiben

\begin{aligned} 000 \mapsto & 0000000 \\ 001 \mapsto & 0001111 \\ 010 \mapsto & 1111000 \\ 011 \mapsto \\ 100 \mapsto \\ 101 \mapsto \\ 110 \mapsto \\ 111 \mapsto \end{aligned}

Kodierfunktion ( $n > k$ )

E : A^{k} \to A^{n} : (a_{0}, a_{1}, \dots, a_{n}) \mapsto (c_{1}, \dots, c_{n - 1})

mit möglichst hoher $d_{m i n}$ .

D : A^{n} \to A^{k}

distanz $d$ zwischen zwei Wörtern:

d ((r_{0}, \dots, r_{n - 1}), E ((a_{0}, \dots, a_{k - 1})) \leq t ⟹ D ((r_{0}, \dots, r_{n - 1})) = (a_{0}, \dots, a_{k - 1})

Eine Codierfunktion wählen, die zu nächstem Codewort dekodiert, falls empfangenes höchstens $t$ von Codewort entfernt liegt

5.9.3 Codes based on Polynomial Evaluation

$α_{0}, a_{1}, \dots, a_{n - 1}$ wählen

E ((a_{0}, a_{1}, \dots, a_{k - 1})) = (a (α_{0}), \dots, a (α_{n - 1}))

$A = G F (q)$
$d_{m i n} = n - k + 1$
Zwei beliebige Codeworte sind Auswertung von zwei verschiedenen Polynomen -> können nicht an $k$ stellen übereinstimmen -> können an höchstens $k - 1$ nullstellen übereinstimmen -> mindestens an $n - k + 1$ stellen verschieden -> $d_{m i n}$

Bsp (224,192) Code
in Praxis: oft $G F (2^{8}) G F (256)$
k=24 (bytes), $n = 28$ , $d_{m i n} = n - k + 1 = 5$
-> um fehler zu vermeiden, wenn ortabhängig (z.b. cd-kratzer), werden bits verteilt + nochmals kodiert:
$k = 28$ , $n = 32$ , $d_{m i n} = 5$
-> #ueliGotBored

alles lineare codes -> kann als Matrixmultiplikation dargestellt werden

happy end: "algebra ist toll"

#timestamp 2024-11-27

6 Logic

6.1 Introduction

6.2 Proof systems

6.2.1 Definition

S aussagen, P beweise

\begin{aligned} S & = \sum^{*} & {0, 1}^{*} \\ P & = & {0, 1}^{*} \end{aligned}

truth function: $τ : S \to {0, 1}$
verification function: $ϕ : S \times P \to {0, 1}$

Bsp
Sudoku:

Aussage:
- Felder als string aufschreiben: $S = X X 7 X 1 X \dots$ (kann als bitstring geschrieben werden)
Beweis:
- $P =$

2 Anforderungen:

Korr.: für alles:

Falls $ϕ (s, p) = 1$ für ein $p ⟹ t (s) = 1$
( $\forall s (\exists p ϕ (s, p) \to τ (s))$ ) (verwenden wir nicht)

Vollst.: für alles:

umgekehrt
( $\forall s (\exists p ϕ (s, p) \leftarrow τ (s))$ )

Proof system

quadruple $Π = (S, P, τ, ϕ)$

\begin{aligned} N P & L = {s | τ (s) = 1} \\ P & x \in L \end{aligned}

-> verifikation muss effizient sein

6.2.2 Examples

Example 6.4:
ist $n$ Primzahl?

$n - 1 = p_{1} p_{2} \dots p_{k}$ (Faktorisierung)
rekursiv alle Primfaktoren zeigen, dass sie primzahlen sind
Generator g von $Z_{n}^{*}$ finden
- $g^{n - 1} \equiv_{n} 1$ ( $⟹ o r d (g) = n - 1$ )
- $g^{\frac{n - 1}{p_{i}}} ≢_{n} 1$
...

duale Beweise:

beweisverifikation kann extrem verschiedene Fromate annehmen
verifikation kann ganz anderer Natur sein als gegenbeweise

τ (s) = 1 ⟺ M ⊨ G

\begin{aligned} (1) & (A \lor Z) \to C & M ⊨ Z ? \\ (2) & B \to A \\ (3) & E \to Z \\ (4) & (A \land C) \to (D \lor E) \\ (5) & (D \land A) \to Z \\ (6) & (A \land B) \end{aligned}

informal: (6) a wahr, b wahr -> (1) c wahr -> (4) d oder e wahr -> (3)/(5) z wahr -> z wahr

Regeln:

Ziel: $M ⊢ G$ -> em Ende Formel herleiten
$M ⊢ G ⟹ M ⊨ G$ -> schlussendlich logische Folgerung

\begin{aligned} R_{1} : & F \land G ⊢ F & (B \land ⊤ = B) \\ R_{2} : & F ⊢ F \lor G \\ R_{3} : & {F, F \to G} ⊢ G & (modus ponens) \\ R_{4} : & {F, G} ⊢ F \land G \\ R_{5} : & {(F \land G) \to H, G} ⊢ F \to H & (B \land ⊤ = B) \\ R_{6} : & {F \to H, G \to H} ⊢ (F \lor G) \to H & (fallunterscheidung) \end{aligned}

\begin{aligned} (6) & ⊢_{R_{1}} A & (7) \\ (7) & ⊢_{R_{2}} A \lor Z & (8) \\ (8) (1) & ⊢_{R_{3}} C & (9) \\ (7) (9) & ⊢_{R_{4}} A \land C & (10) \\ (10) (4) & ⊢_{R_{3}} D \lor E & (11) \\ (5) (7) & ⊢_{R_{5}} D \to Z & (12) \\ \dots \end{aligned}

#ueliGotBored
-> falls jede Regel korrekt, wisse wir, $Z$ logische Folgerung, da Kalkül korrekt

-> normalerweise sind regeln im Beweissystem schon gegeben, hier "erfinden" wir sie

#timestamp 2024-12-02

6.3

Vergleich

Dieses Kapitel steht "über" der Logik $⟹$ wird in dieser Weise nicht in einem Logikbuch oder anderem Werk gefunden

Syntax

Der Syntax definiert ein Alphabet $Λ$ und definiert welche Notationen Formeln sind $f_{1}, f_{2}, \dots, f_{k} \in Λ^{*}$

In der Aussagenlogik:

6.3.7
induktive definition
wenn $F$ Formel, $\neg F$ auch Formel
ebenso $(F \land G), (F \lor G)$

6.5.1 Syntax der Aussagenlogik
atomare Formel: $A_{1}, A_{2}, \dots$ nennen wir $A, B, C, \dots$
-> wir definieren $A, B, C, \dots$ in zwei Schritten, weil nicht so formell, limitiert

Bsp

((A \land \neg B) \lor (B \land \neg C))

In der Prädikatlogik:
Bsp

\exists x \forall y (P (x, f (y)) \lor Q (x))

-> viel komplexere Syntax

syntax ist nicht nur auf Logik beschränkt, e.g. arithm. Ausdrücke

\begin{aligned} (a + b) (a - b) = (a \cdot a) - (b \cdot b) \\ {(,), +, -, \cdot, a, b, \dots} \end{aligned}

Semantik

Logiksemantik definiert

eine Funktion $f r e e$ , welche freie Symbole definiert (was darf man benutzen)
einer Formel $F$ , einer passenden Interpratation mit einer Funktion $σ$ einen Wahrheitswert zuordnet

σ (F, A) = 0 / 1

man schreibt normalerweise $A (F) = 0$

6.5.2
Semantik einer aussagenlogik
-> atomare formeln (frei vorkommende formeln)

semantik der prädikatenlogik
-> universum, prädikat, funktion
-> 6.6 + variablen, nicht durch Quantor gebunden

Symbole sind frei, wenn sie Interpretation verlangen

Interpretation

Eine Interpretation beinhaltet

set $Z \subseteq Λ$
domain (Wertebereich) von $Z$
funktion $A$ , die jedem Symbol in $Z$ einen Wert zuweist

eine interpretation ist passend, wenn jedes freie Symbol einen Wert zugewiesen bekommt

Bsp

\begin{aligned} ((A \land \neg B) \lor (B \land \neg C)) \\ A (A) & = 0 \\ A (B) & = 1 \\ A (C) & = 0 \\ A (D) & = 1 \end{aligned}

-> $A$ ist passend

6.3.7
Bsp: $σ$ in Aussagenlogik

A ((F \land G)) = 1 ⟺ A (F) = 1 und A (G) = 1

Modell

Eine passende Interpretation, wo $A (F) = 1$ , ist ein Modell für $F$

\begin{array}{r} A ⊨ F ⟺ A (F) = 1 ⟺ σ (F, A) = 1 \\ A ⊨ {F_{1}, F_{2}, F_{3}} \end{array}

6.3.5

F ⊨ G \overset{d e f}{⟺} A (F) = 1 ⟹ A (G) = 1

für alle zu $F$ und $G$ passende $A$ .

diese Gesetze gelten in jeder Logik

Bsp

\begin{aligned} A (\neg (F \land G)) = 0 & ⟺ A ((F \land G)) = 0 & (semantik der Negation) \\ ⟺ \dots \end{aligned}

erfüllbar $⟺$ wenn es Intepretation gibt, für die die Formel wahr ist
unerfüllbar $⟺$ wenn keine Interpretation gibt, für die die Formel wahr ist
tautologie $⟺$ wenn Formel für jede Interpretation wahr ist (wenn negation unerfüllbar)

Lemma 6.2: Für jede Formel $F$ gilt:

⊨ F ⟺ \neg F ⊨ ⊥

Lemma 6.3 logische Konsequenz
Die Folgenden Formeln sind äquivalent:

\begin{aligned} 1. & {F_{1}, \dots, F_{k}} ⊨ G \\ 2. & (F_{1} \land F_{2} \land \dots \land F_{k}) \to G ist Tautologie \\ 3. & {F_{1}, \dots, F_{k}, \neg G} ist unerfüllbar \end{aligned}

Aussagen im Kontext der Logik:

Theorie

\begin{aligned} T = Menge von Formeln \\ T ⊨ F \end{aligned}

Aussagen über eine Formel

tautologie/unerfüllbar/...

Aussage über eine Formel in einer konkreten Interpretation

"Wenn es in $N$ ist"...

Wie spricht man über Interpretation? -> kein Formaler Weg

Aussagen über die Logik

"Resolutionskalkül ist korrekt, vollständig"

in der Aussagenlogik:

6.5.4 Normalform

Literal: $A, B, \dots, \neg A, \neg B, \dots$
CNF / DNF
[bild]

Bsp

ABC	F
000	1
001	0
010	0
011	1
100	0
101	1
110	0
111	0
disjunktive Normalform (DNF): alle 1 Zeilen mit $\lor$ :

⟹ (\neg A \land \neg B \land \neg C) \lor (\neg A \land B \land C) \lor (A \land \neg B \land C)

konjunktive Normalform (CNF): alle 0 Zeilen mit $\land$ :

⟹ (A \lor B \lor \neg C) \land (\dots)

-> nicht sonderlich kompakt -> vereinfachen mit Äquivalenzumformungen

#timestamp 2024-12-04

wann ist eine Formel für eine Interpretation wahr?

δ (F, A) / A (F)

Var.symbole: $x_{i}$ (wir schreiben statt index $x . y . z . w$ )

konstanten: $k = 0 : a, b, c$
Funk.symbole: $f_{i}^{(k)}$ ( $i$ index, $k$ anzahl argumente) (wit schreiben $f, g, h$ , argumente implizit)
Präd.symbole: $P_{i}^{(k)}$ (wie funktionen, wir verwenden $P, Q, R$ )

Term: $x_{i}$ sind Terme, falls $f_{i}^{(k)}$ ist $f_{i}^{(k)} (t_{1}, \dots, t_{k})$ Term (induktiv definiert)

gibt element aus Universum zurück

Bsp

\begin{aligned} f (g (x), h (y, z)) ist Term \\ f (f (x), h (y, z)) falsch, da Stelligkeit von f unterschiedlich -> falsche Syntax \end{aligned}

Formel: falls $(t_{1}, \dots, t_{k})$ Terme, dann $p_{i}^{(k)} (t_{1}, \dots, t_{k})$ atomare Formel

gibt Wahrheitswert zurück
logiksymbole: regeln aus der Aussagenlogik gelten auch hier

\forall x F, \exists x F sind auch Formeln, auch wenn kein x in F

Bsp

\begin{array}{r} \forall x P (x) \land \forall x \exists y Q (x, f (y)) \end{array}

2024_12_04 14_38 Office Lens (1).jpg|300

\forall x (p (x) \land \forall x Q (x)) gut definiert, aber semantisch problematisch

P (\overset{―}{x}, \overset{―}{y}) \lor \exists x \forall y Q (x, y, \overset{―}{z}) \overset{―}{} : frei vorkommende Symbole

Bsp 6.20

\forall x (P (x) \lor P (f (x, a)))

freie Symbole: $P, f, a$
2024_12_04 14_38 Office Lens (2).jpg|300

Def 6.34
Interpretation: $A = (u, ϕ)$

u universum
$ϕ$ weist gewissen Funktionssymbolen eine konkrete Funktion zuordenet(unabhängig von Formel)
$ψ$ ordnet Prädikatsymbolen funktionen zu
$ξ$ weist variablen Wert zu (aus Universum)

$ϕ (f)$ : $f^{A}$ ; andere Interpretation $f^{B}$

Prädikate: $P^{A}$
Universum: $U^{A}$
Variablen: $x^{A} = 3$

Bsp

\begin{aligned} \forall x (P (x) \lor P (f (x, a))) = F \\ A : & U^{A} = N \\ a^{A} = 3 & not: ϕ (f) (a) = 3 \\ f^{A} = (x, y) \mapsto x + y & or f^{A} (x, y) = x + y \\ P^{A} (x) = 1 ⟺ x gerade \end{aligned}

interpretation ist passend
Fallunterscheidung
- falls $x$ gerade: P(x) ist wahr
- falls $x$ ungerade: $P (f (x, a))$ wahr
  => $A (F) = 1$
andere Interpretation $B$

\begin{aligned} B : & U^{B} = R \\ a^{B} = 2 \\ f^{B} (x, y) = x \cdot y \\ P^{B} (x) ⟺ x \geq 0 \end{aligned}

interpretation ist passend
um $B (x) = 1$ , müssen wir alle $x$ überprüfen
um $B (F) = 0$ , müssen wir Gegenbsp. finden
- $x = - 1$ -> falsch
  => $B (F) = 0$
  => $F$ ist keine Tautologie, da nicht in jeder Interpretation wahr

Def

A_{[x \to u]}

setzt Variablenwert von $x$ auf $u$ , wird überschrieben falls schon gesetzt

Def 6.36
Semantik

A (f (t_{1}, \dots, t_{k})) = f^{A} (A (t_{1}), \dots, A (t_{k}))

dasselbe für Prädikate

\begin{aligned} A (\forall x G) = {\begin{cases} 1 & falls A_{[x \to u]} (G) = 1 für alle u \\ 0 & else \end{cases} \end{aligned}

Bsp

\begin{aligned} P (x) \lor \neg P (x) \\ Interpretation: & U^{A}, P^{A}, x^{A} \end{aligned}

-> Tautologie (beweis: "ist klar" def 6.11)

\begin{aligned} \forall x (P (x) \lor \neg P (x)) \\ Interpretation: & U^{A}, P^{A}, no x^{A} \end{aligned}

(-> Universum darf nicht leer sein)
-> beide formeln haben starken Zusammenhang, aber nicht gleich:

Lemma:

⊨ F ⟺ ⊨ \forall x F

Bsp

F = \forall x P (x, x) \land \exists x \exists y \exists z (\neg P (x, y) \land \neg P (x, z) \land \neg P (y, z))

Behauptung: $A (F) = 1 ⟺ | U^{A} | \geq 3$
Formel beansprucht Universum mit mindestens $3$ Elementen

Bsp

{\forall x P (x, f (x)) \overset{\land}{\overset{⏞}{,}} \forall x \neg P (x, x), \forall x \forall y \forall z ((P (x . y), P (y, z)) \to P (x, z))}

Formel beansprucht Universum mit unendlicher Grösse (1) über (2)(3), irreflexivität (2), transitivität (3)
-> Modell: f: inkrementfunktion, U: $N$ , $P$ : grösser-funktiona

Bsp

\forall x P (x) \land \exists x (Q (x) \leftrightarrow \neg P (x))

-> unerfüllbar (P muss immer wahr ist, $Q$ muss für ein x wahr sein, stimmt mit drittem teil nicht überein -> keine Interpretation)

Bsp

\begin{aligned} \forall x F & \equiv \neg \exists x \neg F \\ \neg \forall x F & \equiv \exists x \neg F \end{aligned}

-> kann mit Semantik von Quantoren bewiesen werden, aber geht aber auch durch

#timestamp 2024-12-09

recap

{F_{1}, \dots, F_{k}} ⊨ G

Für $alle$ (Interpretation werden nicht quantorisiert -> $∀̸$ ) passenden $A$ :

A (F_{i}) = 1 für i = 1, \dots, k ⟹ A (G)

Def

{F, G} unerfüllbar ⟹ F ⊨ G

(für eine beliebige Interpretation)
proof könnte Prüfungsfrage sein

Bsp:

\exists x P (f (x)) = F

[bild]

\begin{aligned} A : U^{A} & = N \\ P^{A} & = "gerade" \\ f^{A} & = "increment 5" \end{aligned}

Bsp

\exists x P (f (x)) ⊨ \exists x P (x)

Aussage über zwei Formeln
proof könte Prüfungsafgabe sein
Beweis falsch: es gibt mindestens eine Interpretation, für welche links wahr und rechts falsch (Gegenbeispiel) -> trifft in diesem fall nicht zu, da rechte Formel grösseren Freiheitsgrad hat
Beweis wahr:
- rechts nur falsch, falls $P$ falsch (grösserer Freiheitsgrad)
- links ist abhängig von Interpretation von $f$
Beweis formal:

\begin{aligned} A_{[x \to u]} (P (f (x))) = P^{A} (f^{A} (u)) \\ A_{[x \to v]} (P (x)) = P^{A} (f^{A} (u)) & für v = f^{A} (u) \\ daher : \\ P^{A} (f^{A} (u)) = 1 ⟹ P^{A} (f^{A} (u)) = 1 \end{aligned}

Bem

\begin{aligned} σ (F, A) \dots σ (F^{'}, A^{'}), σ (F^{″}, A^{″}), \dots \\ σ (\forall x G, A) σ (G, A_{[x \to u]}) & für alle u in U \end{aligned}

Lemma 6.7
beispiel äquivalenzen:

8) (\forall x F) \land H \equiv \forall x (F \land H) (falls x nicht frei in H vorkommt)

-> das $x$ in $H$ wird auf der rechten Seite in etwas anderes umbenannt -> hat keine Verbindung zum $\forall x$ , e.g.

\begin{aligned} (\forall x F) \land \forall x P (x) \equiv \forall x (F \land (\forall x P (x))) & stimmt zwar \\ (\forall x F) \land \forall y P (y) \equiv \forall x (F \land (\forall y P (y))) & aber so verständlicher ("bereinigte Form") \end{aligned}

Proof:`
$S_{u}, T_{u}$ aussagen, parametrisiert mit $u$
$\oplus :$ $S_{u}$ ist wahr für alle $u$ in $U$ UND $T_{u}$ ist wahr für alle $u$ in $U ⟹$ ( $S_{u}$ und $T_{u}$ ) ist wahr f.a. $u$ in $U$
-> lässt sich fast nicht mehr formalisieren

\begin{aligned} A ((\forall x F) \land H) = 1 & ⟺ A (\forall x F) = 1 und A (H) = 1 & (sem. von \land) \\ A_{[x \to u]} (F) = 1 f.a. u und A_{[x \to u]} (H) = 1 & (sem. von \forall, auswertung H zu u ändert nichts) \\ ⟺ (A_{[x \to u]} (F) = 1 und A_{[x \to u]} (H) = 1) f.a. u & (\oplus) \\ ⟺ A_{[x \to u]} (F \land H) = 1 f.a. u & (\land) \\ ⟺ A (\forall x (F \land H)) = 1 & (\forall) \end{aligned}

Bsp

(\exists x P (x)) \to Q (y) \equiv \forall x (P (x) \to Q (y))

$y$ ist freie variable

2024_12_09 15_24 Office Lens.jpg

6.6.8
$F [x / t]$
$F = \forall x \exists y Q (x, y, z)$
$F [z / f (g (w), h (w))] =$

Lemma 6.8
$\forall x G \equiv \forall y G [x / y]$

$\forall x F ⊨ F [x / t]$

A ((t_{1} = t_{2})) = 1 ⟺ A (t_{1}) = A (t_{2})

-> wobei die anderen = die normale Gleichheit im Universum ist

Gruppenaxiome (GA) daraus:

\begin{aligned} G_{1} & \forall x \forall y \forall z (f (f (x, y) . z) = f (x, f (y, z))) \\ G_{2}^{'} & \forall x (f (x, a) = x) & (a ist neutralelement (?)) \\ G_{3}^{'} & \forall x (f (x, g (x)) = a) \\ G A & ⊨ \forall x (f (a, x) = x) \\ G A & ⊨ \forall x (f (g (x), x) = a) \end{aligned}

-> axiome stimmen in the interpretation der gruppe

Proof

damals: $\hat{b} * b = (\hat{b} * b) * a = \dots$
heute:

\begin{aligned} G 2^{'} & ⊨ f (f (g (w), w), a) = f (g (w), w) \\ ⊨ \forall w^{″} \\ ⊨ \dots \end{aligned}

#ueliGotBored

6.6.7 normal form

Prenex form

A formula where all quantifiers ( $\exists$ or $\forall$ ) are at the beginning of the formula is said to be in prenex form (deutsch Pränexform)

Theorem 6.10. For every formula there is an equivalent formula in prenex form.

form bereinigen:
2024_12_09 15_57 Office Lens.jpg|500

Quantoren können vertauscht werden, da sie sich nur auf einen Teil der Formel beziehen
Pränexform ist nicht eindeutig

\exists x P (x) P (f (x))

-> man könnte theoretisch quantoren durch funktionen ersetzen
-> #ueliGotBored

#timestamp 2024-12-11

Bsp

$\forall x \exists y F (x, y)$
$\forall x F (x, f (x))$
-> erfüllbarkeitsäquivalent, nicht äquivalent oder logische Folgerung
-> z.B. Unerfüllbarkeit wird durch

wieso?

Annahme: $A$ ist modell

\begin{aligned} A_{[x \to u] [y \to v]} (F (x, y)) = 1 \\ f (u) = v & möglich, da für alle u es immer ein v gibt \end{aligned}

Im Skript würde man schreiben: $G = F [y / f (x)]$ : Wenn $F$ erfüllbar, ist $G$ erfüllbar -> interpretation muss nicht bei $F$ , $G$ gleich sein (auch wenn Universum wahrscheinlich gleich sein wird)

Bsp

\begin{aligned} \forall s \exists t \forall x \forall y \exists z F (s, t, x, y, z) & (Pränexform) \\ \forall s \forall x \forall y F (s, f (s), x, y, g (s, x, y)) & (erfüllbarkeitsäquivalent, Skolem-Normalform) \end{aligned}

existenzquantoren hängen von allen vorherigen allquantoren ab

Bsp

\begin{aligned} \exists x P (x) \\ P (x) & (erfüllbarkeitsäquivalent) \\ P (a) & (da x konstant) \end{aligned}

$\neg \forall x \neg P (x)$ ist zwar äquivalent, aber nicht eine Pränexform

Theorem 6.12

\neg \exists x \forall y (P (y, x) \leftrightarrow \neg P (y, y))

-> theorem: bedeutet Tautologie (ohne Annahme)
-> man könnte auch schreiben: $⊨ \neg \exists x \forall y (P (y, x) \leftrightarrow \neg P (y, y))$

2024_12_11 14_49 Office Lens.jpg|300

die Quantoren können nicht vertauscht werden, da sie auf den gleichen Teilbaum verweisen (?)
Beweis:

\begin{aligned} A : U^{A}, P^{A}, u beliebig \\ A (P (u, u) \leftrightarrow P (u, u)) = 1 \\ ⟹ & A_{[x \to u] [y \to u]} (P (y, x) \leftrightarrow P (y, y)) = 1 & (Def. A_{[\dots]}) \\ ⟹ & A_{[x \to u]} (\exists y (P (y, x) \leftrightarrow P (y, y))) = 1 & (Sem. \exists) \\ ⟹ & A (\forall x \exists y (P (y, x) \leftrightarrow P (y, y))) = 1 \end{aligned}

-> wir benutzen in schritt 2 einen $\exists$ statt $\forall$ , weil $[y \to u]$ von $[x \to u]$ abhängt

mögliche Interpretation:

U = alle Mengen
$P (s, t)$ = 1 $⟺ s \in t$

-> Russell's Paradox

-> beschreibt auch barber paradox

Theorem 6.14

\begin{aligned} N ≺ {0, 1}^{\infty} \\ U = N \\ P (s, t) = 1 ⟺ s-te Bit in der t-ten Folge = 1 \end{aligned}

-> kann auch durch Theorem 6.12 beschrieben werden
-> Cantor's Diagonalisierungsargument ist gleich wie Russell's Paradox

Theorem 6.15

\begin{aligned} U & = {0, 1}^{*} \\ P (s, t) & = Output von Programm t für Input s. \end{aligned}

Wegen Theorem 6.12
$y \mapsto \neg P (y, y)$

Bsp
Logik ist immer eingeschränkt, z.B.

\forall w \forall x \exists y \exists z F (w, x, y, z)

mann kann aber nicht ausdrücken

\begin{aligned} \forall w \exists y \\ \forall x \exists z & F (\dots) \end{aligned}

hier würde man gerne Funktionen quantisieren, geht aber nicht (second-order logic)

\exists f \exists g \forall x \forall w F (w, x, f (w), g (x))

6.4 Kalküle

{H_{1}, H_{2}, \dots, H_{k}} H_{k + 1}}

Ziel: aus Regeln $H_{1}, \dots, H_{k}$ (Menge von Formeln) neue Formel Herleiten

N ⊢_{R} G

wobei N
Bsp

{F \to G, F \to H} ⊢_{R} F \to (G \land H)

F,G,H sind Platzhalter, die die Relationen erklären. (spezifische Form einer Herleitungsregel)

Ein Kalkü bestehet aus mehreren Regeln

K = {R_{1}, \dots, R_{s}}

wobei es aus der Formelmenge $M$ eine Herleitung zu $G$ im Kalkül gibt, falls man mit den bestehenden Formeln mit den Regeln $G$ herleiten kann
-> heisst Hilbert-Kalkül (Hilbert-style Calculi)

Ein Kalkül ist korrekt, wenn eine Herleitung eine logische Konsequenz der bestehenden Formeln ist:

M ⊢_{K} G ⟹ M ⊨ G

stimmt nur, wenn alle Ausgangsformeln stimmen

Ein Kalkül ist vollständig

M ⊢_{K} G ⟸ M ⊨ G

der Beweis kann sehr lang, aber muss endlich sein

#timestamp 2024-12-16

Bsp: korrekte Regeln
Kalkül:

\begin{aligned} {F, \neg F} & ⊢_{R_{1}} G \\ F \to G & ⊢_{R_{2}} G \\ \emptyset & ⊢_{R_{3}} (F \to G) \land (G \to F) \\ {F \lor G, \neg G} & ⊢_{R_{4}} F \lor H \end{aligned}

Eine Regel ist korrekt ( $R_{1}$ ), wenn ${F, \neg F} ⊨ G$ .

$R_{1}$ : da ${F, \neg F}$ unerfüllbar, kann man auf alles schliessen -> Regel korrekt
$R_{2}$ : nicht korrekt, da
$R_{3}$ : keine Einschränkung bedeutet -> jede Interpretation ist Modell -> Tautologie
- nicht Tautologie -> Regel nicht korrekt
$R_{4}$ : korrekt, da

Bsp: Prüfungsaufgabe 2022
Kalkül:

\begin{aligned} {F \to G, F} & ⊢_{R_{1}} G \\ \emptyset & ⊢_{R_{2}} F \to (G \to F) \\ \emptyset & ⊢_{R_{3}} (\neg F \to \neg G) \to ((\neg F \to G) \to F) \end{aligned}

alle drei Regeln sind korrekt
Aufgabe: Herleiten: ${A, \neg A} ⊢_{K} B$
- wegen Unerfüllbarkeit ist ${A, \neg A} ⊨ B$ , aber es muss in Kalkül hergeleitet werden
Überlegung:
- $R_{1}$ muss am Schluss kommen, um $B$ zu bekommen
- bei $5$ : wie bekomme ich $\neg B \to A$ , um mit $4$ $B$ bekommen zu können

\begin{aligned} \emptyset & ⊢_{R_{3}} (\neg B \to \neg A) \to ((\neg B \to A) \to B) & (1) \\ \emptyset & ⊢_{R_{2}} \neg A \to (\neg B \to \neg A) & (2) \\ {(2), \neg A} & ⊢_{R_{1}} \neg B \to \neg A & (3) \\ {(1), (3)} & ⊢_{R_{1}} (\neg B \to A) \to B & (4) \\ \emptyset & ⊢_{R_{2}} A \to (\neg B \to A) & (5) \\ {(5), A} & ⊢_{R_{1}} \neg B \to A & (6) \\ {(4), (6)} & ⊢_{R_{1}} B \end{aligned}

korrektheit Hilbert-Kalkül

\begin{aligned} M ⊢_{K} G & ⟹ M ⊨ G \\ ⟸ \end{aligned}

andere Kalküle
Bsp
syntaktisches Element ist nicht nicht Formelmengen, sondern Paar aus Formelmenge und Formel

(M, F) ⊢_{R} (M^{'}, F^{'})

korrektheit:

\begin{array}{r} (M, F) ⊢_{R} (M^{'}, F^{'}) \\ ⟹ \\ M ⊨ F ⟹ M^{'} ⊨ F^{'} \end{array}

6.5

6.5.7 Resolutionskalkül

konjuktive Normalform (CNF) (weiter oben schon behandelt)

Blätter sind Literale
"verundung" von "veroderungen"
veroderte Elemente: Klausel (Menge von Literalen)
- Reihenfolge daher nicht wichtig
Klauselmenge $K$ ,

2024_12_16 15_01 Office Lens.jpg|400

{A, \neg B, C} {\neg A, C, D} {\neg A, \neg D}

-> Klauselmenge entspricht ganzer Äquivalenzklasse von Formeln

da Abstraktion:
Erfüllbarkeit von Klauselmenge:
- man kann $A, B, C, D$ so wählen, dass sie erfüllbar ist $✓$
- Bemerkung: $s a t$ -Problem
Unerfüllbarkeit:
- keine gute Beweismethode (es gibt nicht immer einen kurzen Beweis)
- zeigen: $M \cup {\neg G}$ (?)

-> Unerfüllbarkeit ist interessanter, weil viel stärker

Negation von Tautologie

Regel von Resolutionskalkül

Falls in zwei Klauseln ein Literal negiert und nicht negiert vorkommt, kann man das Literal streichen und die Klauseln vereinigen

{{A, \neg B, C}, {\neg A, C, D}} ⊢_{r e s} {\neg B, C, D}

d.h.

{K_{1}, K_{2}} ⊢_{r e s} K

man darf Klauselmengen beliebig kombinieren

[bild]

-> Unerfüllbarkeitsbeweis:

leere Klauselmenge finden
e.g.

{{E}, {\neg E}} ⊢_{r e s} \emptyset

-> das Resolutionskalkül besteht nur aus einer Regel!

Res = {r e s}

-> Problem von Resolutionskalkül: Klauseln werden im Allgemeinen grösser

Bsp:

\begin{aligned} A \lor Z \to C & \equiv \neg (A \lor Z) \lor C \equiv (\neg A \land \neg Z) \lor C \equiv (\neg A \lor C) \land (\neg Z \lor C) \\ B \to A & \equiv \neg B \lor A \\ E \to Z & \equiv \neg E \lor Z \\ (A \land C) \to (D \lor E) & \equiv \neg (A \land C) \lor D \lor E \equiv \neg A \lor \neg C \lor D \lor E \\ D \land A \to Z \\ A \land B \end{aligned}

Klauseln:

{\neg A, C} {C, \neg Z} {A, \neg B} {\neg E, Z} {\neg A, \neg C, D, E} {\neg A, \neg D, Z} {A} {B} {\neg Z}

2024_12_16 15_50 Office Lens.jpg

Bei $n$ atomaren Formeln, wie viele Klauseln kann man schreiben?

es gibt $2^{n}$ mögliche Literale (Formeln mit Negation)
es gibt $4^{n}$ mögliche Klauseln, die hergeleitet werden können
- praktisch weniger, da es viele erfüllbare Klauseln gibt (e.g. ${A, \neg A}$ )

nicht erlaubt:

{A, \neg B}, {\neg A, B} ⊢_{r e s} \emptyset

#timestamp 2024-12-18

recap
für jede Logik gilt:

\begin{aligned} M ⊢_{K} F & ⟹ M ⊨ F \\ eigentlich: & ⟺ \end{aligned}

-> je mehr in $M$ angenommen wird, desto wahrscheinlicher gelingt Herleitung

Bsp Resolutionskalkül

je mehr Klauseln es gibt, desto unwahrscheinlicher wird Erfüllbarkeit
mit $A$ in der letzten Klausel wäre es nicht möglich, $A$ zu entfernen -> erfüllbar

[bild]

Def
Sei $K, K^{'}, \dots$ Klauseln, $K, K^{'}, \dots$ Klauselmengen.

\begin{aligned} K & ⊨ K \\ K & \subseteq K^{'} ⟹ K ⊨ K^{'} \\ K & \subseteq K^{'} ⟹ K^{'} ⊨ K \end{aligned}

-> Man könnte im Resolutionskalkül beliebig neue Klauseln hinzufügen (allerdings nicht das Ziel)

Def 6.30 Resolutionsregel

\begin{aligned} K_{1} K_{2} & ⊢_{r e s} K \\ {\dots, L} {\dots, \neg L} & ⊢_{r e s} {\dots} \end{aligned}

wobei $K$ resolvent ist. Es ist die einzige Regel des Kalküls, d.h.

Res = {r e s}

Lemma 6.5

K ⊢_{R e s} K ⟹ K ⊨ K

Proof
see script

Thorem 6.6

(A set M of formulas is unsatisfiable) $K$ unsatisfiable $⟺ K (M) ⊢_{r e s} \emptyset$ .

Proof
$⟸$ :
$K ⊢_{R e s} \emptyset ⟹ K ⊨ \emptyset$ since $\emptyset$ has no model (is unsatisfiable)

$⟹$ :
Verankerung: $\emptyset, {A_{1}}, {\neg A_{1}}, {A_{1}, \neg A_{1}}$

Annahme: Für $A_{1} \dots A_{n}$ und beliebige $K$ , die $A_{1} \dots A_{n}$ enthält, gilt

K unerfüllbar ⟹ K

Induktionsschritt:
In einer Klauselmenge $K$ betrachten wir alle Klauseln, in denen $A_{n + 1}$ , $\neg A_{n + 1}$ oder beide atomare Formeln vorkommen.

Klauseln der Form ${\dots, A_{n + 1}, \neg A_{n + 1}}$ sind immer erfüllbar

Sei $K_{0}$ eine Klauselmenge, wo $A_{n + 1} = 0$ .

falls $\neg A_{n + 1} = 1$ in Klausel, ist Klausel erfüllbar
falls $A_{n + 1} = 0$ in Klausel, kann $A_{n + 1}$ gestrichen werden
Unerfüllbarkeit hängt nicht mehr von $A_{n + 1}$ ab

K ist unerfüllbar für A_{n = 1} ⟺ K_{0} ist unerf.

-> eine Herleitung in $K_{0}$ , die auch in $K$ gültig ist ( $A_{n + 1}$ kommt nicht vor) -> $K$ ist unerfüllbar
-> eine Herleitung in $K_{0}$ , die in $K$ mit $A_{n + 1}$ vorkommt -> keine $\emptyset$ an Ende von Herleitung

analoge Überlegung

Sei $K_{1}$ eine Klauselmenge, wo $A_{n + 1} = 1$ .

falls $A_{n + 1} = 1$ in Klausel, ist Klausel erfüllbar
falls $\neg A_{n + 1} = 0$ in Klausel, kann $A_{n + 1}$ gestrichen werden
Unerfüllbarkeit hängt nicht mehr von $A_{n + 1}$ ab

K ist unerfüllbar für A_{n = 1} ⟺ K_{1} ist unerf.

-> eine Herleitung in $K_{1}$ , die auch in $K$ gültig ist ( $A_{n + 1}$ kommt nicht vor) -> $K$ ist unerfüllbar
-> eine Herleitung in $K_{1}$ , die in $K$ mit $\neg A_{n + 1}$ vorkommt -> keine $\emptyset$ an Ende von Herleitung

=> cases:

falls Herleitung zu $\emptyset$ aus $K_{0}$ oder $K_{1}$ existiert (oder in beiden), die in $K$ ohne $A_{n + 1}$ existiert (und aus $K_{1}$ ohne $\neg A_{n + 1}$ ) -> unerfüllbar
falls Herleitungen in $K$ aus $K_{0}$ bzw. $K_{1}$ immer $A_{n + 1}$ bzw. $\neg A_{n + 1}$ haben, kann man die beiden Terme zu $\emptyset$ schreiben

Bem (Exkurs)
Da beide Herleitungen ( $A_{n + 1} = 0, 1$ ) aufwendig sind, und noch evtl. kombiniert werden müssen,

\begin{aligned} UNSAT & \notin NP (?) \\ \in co-NP \\ SAT & \in NPC & (NP-complete) \\ 3 SAT & \in NPC \\ 2 SAT & \in P \end{aligned}

Übungen

Prüfung

1 Einführung

2

2.3 Logik

Beweiskonzept

2.4 Prädikatslogik

2.6 Beweistechniken

Komposition von Implikationen:

Beweis von Implikationen

Modus Ponens-Beweise

Fallunterscheidung

Beweis mittels Wiederspruch

Existenzbeweise

Beweis mittels Gegenbeispiel

Induktionwbeweise

3 Mengen, Funktionen

3.2 Mengen, Mengenoperationen

3.2.9 Kartesian product

3.2.8 Power set

3.2.4 Union and Intersection

3.3 Relations

3.3.1 Relation concept

3.3.5 Composition of Relations

3.4 Equivalence Relations

3.4.2

3.4.3

3.5 Partial order Relations

3.5.2 Hasse Diagrams

3.5.3 Combinations of Posets and the Lexicographic Order

3.6 Functions

3.7 Countable and uncountable sets

3.7.1

3.7.2

3.7.3

3.7.4 Uncoutability of {0,1}∞

4 Number Theory

4.1.1 Number Theory as a Mathematical Discipline

4.4.2 Division mit Remainder

4.2.3 Greatest common divisor

4.3 Factorization into Primes

4.5 Congruences and Modular Arithmetic

4.5.1 Modular Congruences

4.5.2 Modular Arithmetic

4.5.3 Multiplicative Inverses

4.5.4 The Chinese Remainder Theorem

5

5.2 Monoids and Groups

5.2.1 Neutral element

5.2.3 Inverses and Groups

5.2.4 (Non-)minimality of the Group Axioms

5.2.5 Some examples of groups

5.3 The structure of groups

5.3.1 Direct Product of groups

5.3.2 Group Homomorphisms

5.3.4 The Order of Group Elements and of a Group

5.3.5 Cyclic Groups

5.3.7 The Order of Subgroups

5.3.8 The Group Zm∗ and Euler’s Function

5.4 Application: RSA Public-Key Encryption

5.4.1 e-th Roots in a Group

5.5 Rings and Fields

5.5.1 Definition of a Ring

5.5.2 Units and the Multiplicative Group of a Ring

5.5.4 Zerodivisors and Integral Domains

5.6.1 Factorization and Irreducible Polynomials

5.5.6 Fields

5.6 Polynomials over a field (F[x])

5.6.1 Factorization and Irreducible Polynomials

5.6.2

Bsp GF(2)[x](x4+x+1):(x2+x+1)=

5.7 Polynomials as Functions

5.7.1 Polynomial Evaulations

5.7.2 Roots

5.7.3 Polynomial Interpolation

5.8 Finite fields

5.8.1 The Ring F[x]m(x)

5.8.2 Constructing Extension fields

5.8.3 Some Facts About Finite Fields

5.9 Application: Error-Correcting codes

3.7.4 Uncoutability of ${0, 1}^{\infty}$

5.3.8 The Group $Z_{m}^{*}$ and Euler’s Function

5.4.1 $e$ -th Roots in a Group

5.6 Polynomials over a field ( $F [x]$ )

Bsp
$G F (2) [x] (x^{4} + x + 1) : (x^{2} + x + 1) =$

5.8.1 The Ring $F [x]_{m (x)}$