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/ Cheatsheet-Vorlage:
Übungen
- Exercise 1 (@2024-09-27@18:00)
- Exercise 2 (@2024-10-03@18:00)
- Exercise 3 (@2024-10-10@18:00)
- Exercise 4 (@2024-10-17 18:00)
- Exercise 5 (@2024-10-24 18:00)
- Exercise 6 (@2024-10-31@18:00)
- Exercise 7 (@2024-11-07@18:00)
- Exercise 8 (@2024-11-14@18:00)
- Exercise 9 (@2024-11-21@18:00)
- Exercise 10 (@2024-11-28@18:00)
- Exercise 11 (@2024-12-05@18:00)
- email wegen Korrektur
- Exercise 12 (@2024-12-12 18:00)
- Exercise 13 (@2024-12-19 18:00)
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 ->
>5an Prüfung- (***)-aufgaben sind sehr Zeitintensiv -> erst am Schluss machen
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: 91 ist eine Primzahl Es gibt unendlich viele PZ. -> unendlich vermeiden, besser 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.
ist falsch (ist wahr)
Für jedes markierte Feld gibt es eine Belegung des Restfeldes L-Formen.
Aussage wahr für k*k Quadrat -> es reicht ein Gegenbeispiel, um die Aussage zu wiederlegen
nicht durch 3 teilbar -> oder
Theorem: (für jedes gilt)
Beweis:
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
-> kann nicht festgestellt werden, ob S wahr ist
Aussage: Jede gerade Zahl 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
.jpg)
BSP: Ärtztin 1: X hat entweder Masern oder (Windpocken und Lungenentzündung). X hat Masern X hat WP X hat LE
.jpg)
- 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 (immer wenn wahr ist, its wahr)
Formel vs Aussage
- Input: Formeln, Output: Formel
- : Input: Formeln, Output: Aussage
- Input: Formeln, Output: Aussage (?)
und (g.d.w) , aber nicht
timestamp 2024-09-25
.jpg)
logische Folgerung: -> wenn F, dann auch G (asymmetrisch)
Exkurs
Gibt es eine effizient Lösung für ein sat.-Problem (z.B. Schalftung oben)-> -vollständig
.jpg)
wenn Tautologie, dann -> Bsp: Skript 2.6.4
modus ponens S beweisen:
- Eine Aussage formulieren.
- beweisen
- beweisen
wieso funktioniert:
Lemma 2.1
- | Distributivgesetz
Bem: Es gibt Prioritätsregeln , man darf Klammern weglassen
Beweis durch Herleitung
.jpg)
Beweiskonzept
.jpg)
Beweissystem - gewünschte Eigenschaften: (siehe Kapitel 6)
- welchen Typ von Aussagen kann überprüft werden?
- kein Beweis für falsche Aussagen
- Beweis
Aussage: Beweis: (+1) (mult. mit 1, 1 ist negativ) (wahr)
Deshalb wahr
| Punkt, weil Folgerungsschritt
S beweisen:
Falsch:
- T ist wahr
und sind QZ.
.jpg)
Aussage: ist keine PZ. Beweis: ist nicht PZ ist nicht PZ (oder)
Bem: Nicht wird bewiesen, sondern es wird bewiesen, dass
.jpg)
Struktur: Aus etwas bewiesenem in Schritten Neues beweisen
2.4 Prädikatslogik
- (Universum, z.b. Zahlenmenge)
- (Prädikate)
- (Funktionen)
- (Konstanten)
- (Formel)
timestamp 2024-09-30
Bsp: Spezialfall: : -> (Infix-Notation) ->
Konstanten: Aussagen:
Formeln sind nicht wahr oder falsch
.jpg)
-> müssen nicht unbedingt Zahlen sein - es koennte irgendeine Struktur sein, solange +, = definiert ist - unteres beispiel: 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
.jpg)
komplexe Definition:
-> logische Folgerungen
Vertauschen: mehrere gleiche Quantoren () können vertauscht werden!
-> transitiv: wenn und , dann -> Vorteil von Formulierung: Allgemein
Bsp: = Menschen Prädikate:
Kommutativität:
Reihenfolge Quantoren spielt eine Rolle (!):
Bsp. Verwandschaftsregeln
-> man könnte Verwandschaft über mehrere Grade nur sehr komplex ausdrücken -> Logik hat auch gewisse Grenzen
timestamp 2024-10-07
2.6 Beweistechniken
timestamp 2024-10-02
Komposition von Implikationen:
und wahr, dann wahr
Lemma:
andere Regel und wahr, dann
Begründung:
Beweis von Implikationen
- Direkter Beweis von
Annahme: wahr Beweis: wahr (unter dieser Annahme)
Bsp: Quadrathzahl (QZ), dann QZ
Beweis:
- S:
- Indirekter Beweis von
Annahme: T Falsch
Beweise falsch (unter dieser Annahme)
Lemma:
Beweis:
| 0 | 0 | 1 | 1 |
| 0 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 1 | 1 | 1 | 1 |
Bsp: Behauptung: Wurzel von irrationaler Zahl ist irrational.
irrational irrational
Beweis:
Modus Ponens-Beweise
- Definiere
- Beweise wahr
- Beweise wahr
Lemma:
Bsp:
(*) Für gilt: ( und Primzahl )
( und Primzahl)
Bleibt zu beweisen: ist Primzahl.
Fallunterscheidung
(zum Beweis von S)
- Definiere
- Beweise: mindestens eine Aussage ist wahr
- Beweise: für alle wahr
Lemma: ()
k=1: Modus Ponens k=2:
Bsp: Punktierung eines 4x4 Schachbretts Für gibt es Überdecukung aller nicht markierter Felder
Beweis mittels Wiederspruch
- Definiere
- Beweise falsch
- Beweise: falsch falsch
Lemma: Alternative:
- ""
- ""
- Beweise wahr
Lemma:
(beide Lemmas sind äquivalent)
Bsp: irrational
Beweis:
teilt 2 teilt m 4 teilt 4 teilt 2 teilt 2 teilt n .
falsch
Existenzbeweise
Universum von Parametern für jeden
Ziel: wahr für ein Falls durch definiert, dann Ziel
ExB ist konstruktiv: Finde , sodass wahr. Bsp: Skriptum
Beweis mittels Gegenbeispiel
für Behauptung: ist nicht wahr für alle durch P(x) gegeben:
Bsp: Scriptum
Induktionwbeweise
()
Prinzip: ()
Prädikat (unär)
- Verankerung: Beweise wahr (bzw. wahr)
- Induktionsschritt: Beweise wahr
Theorem: Prädukat
3 Mengen, Funktionen
Russel’s Paradox:
ZF / ZFC Lösung:
- alles ist eine Menge
- Prädikat:
- definition ,

- Theorem
timestamp 2024-10-09
Bsp 3.4:
Wegen der Mengendefinition ist
Methods to prove that two sets are equal:
Lemma 3.1:
Are the sets equal?
Proof with contradiction: We assume (Lemma 3.1) The contradiction is
Note: All elements are also sets themselves. However, we will continue to use capital letters for sets and small letters for elements.
Def: is an empty set if
Lemma 3.5: There is only one empty set (often denoted as )
Lemma 3.6: for all (proof on page 58)
- attempt: (wrong, since sets are unordered)
- attempt: (not possible, since this notation is not possible for all pairs)
- attempt:
Lemma:
Lemma: Lemma: (transitivity)
Similiarly, we define the natural number
We could also define the plus operator…
3.2 Mengen, Mengenoperationen
3.2.9 Kartesian product
Def: kartesisches Produkt
3.2.8 Power set
Def:
Bsp:
logical definition of power set
3.2.4 Union and Intersection
The union of two sets is defined as
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):
- ()
- (verknüpfung)
Example 3.8: Let be all students at ETH, the set of courses and of professors
- (which studnet takes which course)
- (which course is teached by which professor)
- (which professor teaches which course)
Example 3.10
Note
relations are sets.
| properties of | Def. Formula | Set |
|---|---|---|
| reflexiv | für alle | |
| irreflexiv | für alle | |
| symmetrisch | ||
| antisymmetrisch | ||
| transitiv | ||
| Lemma 3.9 |
antisymmetrical:
todo What is ?
3.3.5 Composition of Relations
Lemma 3.8: Beweis:
3.4 Equivalence Relations
Relations that are reflexive, symmetric and transitive, e.g
timestamp 2024-10-16
Def equivalence relation
For an equivalence relation on a set and for , the set of elements of A that are equivalent to a is called the equivalence class of a and is denoted as
[a]_{\theta} \stackrel{def}{=}{ b\in A | b\theta a }
Example
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 of equivalence classes of an equivalence relation θ on A is a partition of A.
3.4.3
Reflexiv:
transitiv:
zu beweisen:
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

3.6 Functions
Warning
In DiscMat, is calculated in a different order depending wether it is used fro functions or relations
- for functions: first , then ()
- for relations: first , then ()
- injectivity:
- surjektivity:
timestamp 2024-10-23
Lemma 3.x:
\begin{align} f,g~\text{injektiv / surjektiv / bijektiv}\implies g\circ f~\text{injektiv /surjektiv / bijektiv} \ \end{align}
Beweis:
timestamp 2024-10-21
3.7 Countable and uncountable sets
timestamp 2024-10-23
3.7.1
Bernstein-Schröder-Theorem:
3.7.2
Die natürlichen Zahlen ist die niedrigste Unendlichkeitsstufe
3.7.3
- (injektion, keine bijektion)
Thorem 3.19
Cor. Theorem: (i) (ii) (iii)
Beweis von (iii): Sei Inkektion Suche: Eine Lösung:
3.7.4 Uncoutability of
() () !!!
Theorem: Beweis: Sei Injektion

4 Number Theory
und
Proof:
Struktur, in der diese Gesetze gelten
The Ring is a set where the following is true:
- there exists the element (neutral element for addition)
- there exists the element (neutral element for multiplication)
- addition:
- associativity, , , distributivity
- multiplication
Lemma: Für jedes gilt: Proof:
- Ring aller komplexen Zahlen mit ganzem Real-/Imaginärteil
- z.b. Multiplikation:
-> eigentlich addition von winkel und Längenbetrag
4.1.1 Number Theory as a Mathematical Discipline
Catalan conjecture:
for
4.4.2 Division mit Remainder
Theorem: dividieren mit Rest

4.2.3 Greatest common divisor
Definition 4.2
For integers and (not both ), an integer is called a greatest common divisor of and if divides both and and if every common divisor of and divides d, i.e., if
e.g.
-> refers only to the positive divisor
Lemma 4.2
Proof: Let be the set of all common divisors or . Then ueligotbored
Definition 4.4
The ideal generated by a,b (set of all linear combinations of a,b) is
similarly, the ideal of a single int is
e.g.
Lemma Corollary 4.5
e.g
4.3 Factorization into Primes
not relevant for exam (?)
4.5 Congruences and Modular Arithmetic
4.5.1 Modular Congruences
Example 4.9
Def: 4.8
->
timestamp 2024-10-30
Bem:
Lemma 3.14
4.5.2 Modular Arithmetic
Corollary:
works only if we are only interested in the remainder Example
todo: look up “Neunertest”
4.5.3 Multiplicative Inverses
Lemma 4.18 The congruence equation
has a solution . The solution is unique.
Proof of
4.5.4 The Chinese Remainder Theorem
Example

5
Bsp
| * | a | b | c |
|---|---|---|---|
| a | b | c | a |
| b | c | b | |
| c | a | b | c |
Bsp
- Assume 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:
Beweis:
5.2.3 Inverses and Groups
Lemma 5.2
Proof
Def 5.7 Group
A group is an algebra satisfying the following axioms:
- is associative.
- is a neutral element: for all .
- Every has an inverse element , i.e.
Bsp
Lemma 5.3
5.2.4 (Non-)minimality of the Group Axioms
**Lemma **
Proof:
5.2.5 Some examples of groups
| * | e | a |
|---|---|---|
| e | e | a |
| a | a | e |

- assoziativ, inverse, bijektion -> gruppe
- kleinste Gruppe (6 elemente), die nicht kommutativ ist
-> isomorph, da Neutralelement auf Diagonale
- nicht zyklisch (?)

Untergruppe aus Drehungen
- cyklische gruppe
- isomorph zu
- 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 groups is the algebra
where the operation is component-wise:
5.3.2 Group Homomorphisms
strukturerhaltende abbildung

homomorphism: isomprhism: homomorphism which is bijective automorphism: isomorphism to itself
Lemma 5.5 (i): (ii)
Proof of :
| n | (nicht isomorphe) Gruppen mit |
|---|---|
| 2 | |
| 3 | |
| 4 | |
| 5 | |
| 6 | ( nicht kommutativ) |
| 7 | (bei primzahlen gibt es immer nur zyklische Gruppe, addition mod7) |
| 8 | ( n.k., heisst auf wikipedia) |
| … | |
| Betrachte |
01,01,02,03
10,11,12,13
Betrachte
-> kommutativ -> isomorph zu , da
00->1 01->7 02->4 03->13
10->11 11->2 12->14 13->8
Bilden Untergruppen:
timestamp 2024-11-11
Repetition Example direct product, isomorphism
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:
subgroups:

5.3.4 The Order of Group Elements and of a Group
->
- not to be confused with: (number of elemente in G)
Lemma 5.6
finite group is finite
Example -> false, because is a monoid, not a group
Proof
5.3.5 Cyclic Groups
Definition 5.14
The group generated by is
Example
- is also true for groups:
- if a group is cyclic, it is also isomorph to
-> G is always cyclic
5.3.7 The Order of Subgroups
Theorem 5.8 (Lagrange)
Let be a finite group and a subgroup of , then
Proof:

Corollary 5.10 (extended)
5.3.8 The Group and Euler’s Function
Theorem: is a group
Corollary 5.14
5.4 Application: RSA Public-Key Encryption
5.4.1 -th Roots in a Group
Theorem 5.16
G is a bijektion
Proof
Idea behind RSA: mit
.jpg)
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) is a commutative group.
- (ii) is a monoid.
- (iii) for all a, b, c ∈ R (left and right distributive laws). A ring is called commutative if multiplication is commutative [21]
Lemma
Proof Sei beliebig W’beweis: Annahme
Proof (formal)
Example (z.B. )
- neuer Ring
- addition: NE der A. (0,0)
- multiplikation: NE der M.
-> ring-axiome überprüfen -> commutativity: ueligotbored
Proof of [21]
5.5.2 Units and the Multiplicative Group of a Ring
Example:
Def
Lemma
5.5.4 Zerodivisors and Integral Domains
Example -> not an integral domain (“Integritätsbereich”)
Definition 5.24.
An integral domain is a (nontrivial) commutative ring without zerodivisors: For all we have .
5.6.1 Factorization and Irreducible Polynomials
Example (ring with complex numbers)
- is irreducible
- is irreducible
- 2 is not irreducible
-> all prime numbers (?)
timestamp 2024-11-18
recap: Ring R Bsp:
- -> invertierbare gruppe, ähnlich
- -> polynome höheren Grades haben keine Inverse
- -> Körper
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
H-Ring:
- komplexe Zahlen sind Drehungen, Streckungen
- H-Ring: Drehungen, Streckungen im Raum
-> zwei-dimensionale Erweiterung -> vier-dimensionale Erweiterung (quadronionen) der reelen zahlen, Ring
- nicht kommutativ
Gruppe: (5. Gruppe mit 8 Elementen)
- nicht isomorph zu (jede Spiegelung hat + zwei )
- alle Elemente
-> 8-dimensionale Erweiterung noch möglich
- nur noch alternativ assoziativ
5.5.6 Fields
Theorem 5.24
A field is an integral domain (IB)
Proof: Einheit in Ring ist nicht NT ()
Theorem 5.23
we know: our goal this week: -> constructing new fields
Note: sind keine körper
5.6 Polynomials over a field ()
5.6.1 Factorization and Irreducible Polynomials

-> es gibt keine irreduziblen Polynome mit Grad
Teiler von -> ist teiler ()
-> nullstelle:
| 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 )
Bsp
todo Lemma: Wenn exponenten restklasse bilden
5.6.2
Bsp
()
vollständige division:

Wir wollen: wobei .
-> Zeigen: Lösung eindeutig, Rest < Grad 2
Bsp

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
- alle Elemente sind Einheiten (invertierbar) -> kann leicht faktorisiert werden
- faktorisiertungen interessanter
nicht-trivialen Fakt.: mit
Bsp komplexe Zahlen
- wenn Länge Wurzel Primzahl ist -> irreduzibel
Bsp
5.7 Polynomials as Functions
5.7.1 Polynomial Evaulations
Example 5.58
| 0 | 1 | 2 | 3 | 4 | |
|---|---|---|---|---|---|
| 1 | 1 | 3 | 4 | 1 | |
| 2 | 2 | 4 | 0 | 2 |
Lemma 5.28
5.7.2 Roots
Lemma 5.29 (im Körper )
Proof
Theorem 5.31 hat Nullstellen
Proof
5.7.3 Polynomial Interpolation
Bsp
-> z.B. Gauss-Elimination funktioniert, weil Körper ist
Lemma 5.32 Ein Polynom in mit Grad kann mit Stützstellen eindeutig interpoliert werden.
Proof:
5.8 Finite fields
5.8.1 The Ring
-> addition komponentenweise -> multiplikation wird grad grösser, modulo durchdividieren -> assoziativität, distributivität gilt -> Ring
-> Achtung:
F Körper F[x] Polynome über x neuer Ring
-> bei allen heisst Addition , Multiplikation (aber verschiedene Strukturen)
hat Lösung zeigen: hat Lösung Proof wobei wobei => => inverses (existiert nur wen )
-> all Polynome mit grad sind invertierbar -> Körper -> wobei (oder nur (?))
Körper mit gleich vielen Elementen sind Isomorph
Bsp irreduzibles Polynom
-> (neuer) Körper
timestamp 2024-11-25 wurde mit Aufzeichnung nachgeholt
recap chapter 5:
Fehler: hat 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
Bsp
LFSR (Linear-gekoppeltes Schieberegister)
Folge: (Länge 7)
Bei LFSR Länge
- elemente:
- 1en
- 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 -> nichttrivial
5.9 Application: Error-Correcting codes
binär-symmetrischer kanal

Wieso nur ungerade Anzahlen? -> Mehrheitsentscheidung
(Minimal)distanz soll möglichst gross sein
- hälfte der fehler kann korrigiert werden -> falls , kann fehler korrigieren
- hier: mindestens Distanz 4
- geht nicht durch ausprobieren
- parity bits: jedes der 7 bits als lin.komb. der 3 bits (modulo )
- (7,3) Code
- idee: mit matrizen als lin.komb. schreiben

Kodierfunktion ()
mit möglichst hoher .
distanz zwischen zwei Wörtern:
Eine Codierfunktion wählen, die zu nächstem Codewort dekodiert, falls empfangenes höchstens von Codewort entfernt liegt
5.9.3 Codes based on Polynomial Evaluation
wählen
Zwei beliebige Codeworte sind Auswertung von zwei verschiedenen Polynomen -> können nicht an stellen übereinstimmen -> können an höchstens nullstellen übereinstimmen -> mindestens an stellen verschieden ->
Bsp (224,192) Code in Praxis: oft k=24 (bytes), , -> um fehler zu vermeiden, wenn ortabhängig (z.b. cd-kratzer), werden bits verteilt + nochmals kodiert: , , -> 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
- truth function:
- verification function:
Bsp Sudoku:
- Aussage:
- Felder als string aufschreiben: (kann als bitstring geschrieben werden)
- Beweis:
2 Anforderungen:
Korr.: für alles:
- Falls für ein
- () (verwenden wir nicht)
Vollst.: für alles:
- umgekehrt
- ()
Proof system
quadruple
-> verifikation muss effizient sein
6.2.2 Examples
Example 6.4: ist Primzahl?
- (Faktorisierung)
- rekursiv alle Primfaktoren zeigen, dass sie primzahlen sind
- Generator g von finden
- ()
- …
duale Beweise:
- beweisverifikation kann extrem verschiedene Fromate annehmen
- verifikation kann ganz anderer Natur sein als gegenbeweise
- informal: (6) a wahr, b wahr -> (1) c wahr -> (4) d oder e wahr -> (3)/(5) z wahr -> z wahr
Regeln:
- Ziel: -> em Ende Formel herleiten
- -> schlussendlich logische Folgerung
ueligotbored -> falls jede Regel korrekt, wisse wir, 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
In der Aussagenlogik:
6.3.7 induktive definition wenn Formel, auch Formel ebenso
6.5.1 Syntax der Aussagenlogik atomare Formel: nennen wir -> wir definieren in zwei Schritten, weil nicht so formell, limitiert
Bsp
In der Prädikatlogik: Bsp
-> viel komplexere Syntax
- syntax ist nicht nur auf Logik beschränkt, e.g. arithm. Ausdrücke
Semantik
Logiksemantik definiert
- eine Funktion , welche freie Symbole definiert (was darf man benutzen)
- einer Formel , einer passenden Interpratation mit einer Funktion einen Wahrheitswert zuordnet
- man schreibt normalerweise
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
- domain (Wertebereich) von
- funktion , die jedem Symbol in einen Wert zuweist
eine interpretation ist passend, wenn jedes freie Symbol einen Wert zugewiesen bekommt
Bsp
-> ist passend
6.3.7 Bsp: in Aussagenlogik
Modell
Eine passende Interpretation, wo , ist ein Modell für
6.3.5
für alle zu und passende .
diese Gesetze gelten in jeder Logik
Bsp
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 gilt:
Lemma 6.3 logische Konsequenz Die Folgenden Formeln sind äquivalent:
Aussagen im Kontext der Logik:
- Theorie
- Aussagen über eine Formel
tautologie/unerfüllbar/…
- Aussage über eine Formel in einer konkreten Interpretation
“Wenn es in 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: 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 : |
konjunktive Normalform (CNF): alle 0 Zeilen mit :
-> nicht sonderlich kompakt -> vereinfachen mit Äquivalenzumformungen
timestamp 2024-12-04
wann ist eine Formel für eine Interpretation wahr?
Var.symbole: (wir schreiben statt index )
- konstanten: Funk.symbole: ( index, anzahl argumente) (wit schreiben , argumente implizit) Präd.symbole: (wie funktionen, wir verwenden )
Term: sind Terme, falls ist Term (induktiv definiert)
- gibt element aus Universum zurück
Bsp
Formel: falls Terme, dann atomare Formel
- gibt Wahrheitswert zurück
- logiksymbole: regeln aus der Aussagenlogik gelten auch hier
Bsp
.jpg)
Bsp 6.20
freie Symbole:
.jpg)
Def 6.34 Interpretation:
- u universum
- weist gewissen Funktionssymbolen eine konkrete Funktion zuordenet(unabhängig von Formel)
- ordnet Prädikatsymbolen funktionen zu
- weist variablen Wert zu (aus Universum)
: ; andere Interpretation
- Prädikate:
- Universum:
- Variablen:
Bsp
-
interpretation ist passend
-
Fallunterscheidung
- falls gerade: P(x) ist wahr
- falls ungerade: wahr =>
-
andere Interpretation
- interpretation ist passend
- um , müssen wir alle überprüfen
- um , müssen wir Gegenbsp. finden
- -> falsch => => ist keine Tautologie, da nicht in jeder Interpretation wahr
Def
- setzt Variablenwert von auf , wird überschrieben falls schon gesetzt
Def 6.36 Semantik
- dasselbe für Prädikate
Bsp
-> Tautologie (beweis: “ist klar” def 6.11)
(-> Universum darf nicht leer sein) -> beide formeln haben starken Zusammenhang, aber nicht gleich:
Lemma:
Bsp
Behauptung: Formel beansprucht Universum mit mindestens Elementen
Bsp
Formel beansprucht Universum mit unendlicher Grösse (1) über (2)(3), irreflexivität (2), transitivität (3) -> Modell: f: inkrementfunktion, U: , : grösser-funktiona
Bsp
-> unerfüllbar (P muss immer wahr ist, muss für ein x wahr sein, stimmt mit drittem teil nicht überein -> keine Interpretation)
Bsp
-> kann mit Semantik von Quantoren bewiesen werden, aber geht aber auch durch
timestamp 2024-12-09
recap
Für (Interpretation werden nicht quantorisiert -> ) passenden :
Def
(für eine beliebige Interpretation) proof könnte Prüfungsfrage sein
Bsp:
[bild]
Bsp
- 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 falsch (grösserer Freiheitsgrad)
- links ist abhängig von Interpretation von
- Beweis formal:
Bem
Lemma 6.7 beispiel äquivalenzen:
-> das in wird auf der rechten Seite in etwas anderes umbenannt -> hat keine Verbindung zum , e.g.
Proof:` aussagen, parametrisiert mit ist wahr für alle in UND ist wahr für alle in ( und ) ist wahr f.a. in -> lässt sich fast nicht mehr formalisieren
Bsp
- ist freie variable

6.6.8
Lemma 6.8
-> wobei die anderen = die normale Gleichheit im Universum ist
Gruppenaxiome (GA) daraus:
-> axiome stimmen in the interpretation der gruppe
Proof
- damals:
- heute:
6.6.7 normal form
Prenex form
A formula where all quantifiers ( or ) 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:

- Quantoren können vertauscht werden, da sie sich nur auf einen Teil der Formel beziehen
- Pränexform ist nicht eindeutig
-> man könnte theoretisch quantoren durch funktionen ersetzen -> ueligotbored
timestamp 2024-12-11
Bsp
-> erfüllbarkeitsäquivalent, nicht äquivalent oder logische Folgerung -> z.B. Unerfüllbarkeit wird durch
wieso?
- Annahme: ist modell
Im Skript würde man schreiben: : Wenn erfüllbar, ist erfüllbar -> interpretation muss nicht bei , gleich sein (auch wenn Universum wahrscheinlich gleich sein wird)
Bsp
- existenzquantoren hängen von allen vorherigen allquantoren ab
Bsp
- ist zwar äquivalent, aber nicht eine Pränexform
Theorem 6.12
-> theorem: bedeutet Tautologie (ohne Annahme) -> man könnte auch schreiben:

- die Quantoren können nicht vertauscht werden, da sie auf den gleichen Teilbaum verweisen (?)
- Beweis:
-> wir benutzen in schritt 2 einen statt , weil von abhängt
- mögliche Interpretation:
U = alle Mengen = 1
-> Russell’s Paradox
-> beschreibt auch barber paradox
Theorem 6.14
-> kann auch durch Theorem 6.12 beschrieben werden -> Cantor’s Diagonalisierungsargument ist gleich wie Russell’s Paradox
Theorem 6.15
Wegen Theorem 6.12
Bsp Logik ist immer eingeschränkt, z.B.
mann kann aber nicht ausdrücken
hier würde man gerne Funktionen quantisieren, geht aber nicht (second-order logic)
6.4 Kalküle
Ziel: aus Regeln (Menge von Formeln) neue Formel Herleiten
wobei N Bsp
F,G,H sind Platzhalter, die die Relationen erklären. (spezifische Form einer Herleitungsregel)
Ein Kalkü bestehet aus mehreren Regeln
wobei es aus der Formelmenge eine Herleitung zu im Kalkül gibt, falls man mit den bestehenden Formeln mit den Regeln herleiten kann -> heisst Hilbert-Kalkül (Hilbert-style Calculi)
Ein Kalkül ist korrekt, wenn eine Herleitung eine logische Konsequenz der bestehenden Formeln ist:
- stimmt nur, wenn alle Ausgangsformeln stimmen
Ein Kalkül ist vollständig
- der Beweis kann sehr lang, aber muss endlich sein
timestamp 2024-12-16
Bsp: korrekte Regeln Kalkül:
Eine Regel ist korrekt (), wenn .
- : da unerfüllbar, kann man auf alles schliessen -> Regel korrekt
- : nicht korrekt, da
- : keine Einschränkung bedeutet -> jede Interpretation ist Modell -> Tautologie
- nicht Tautologie -> Regel nicht korrekt
- : korrekt, da
Bsp: Prüfungsaufgabe 2022 Kalkül:
- alle drei Regeln sind korrekt
- Aufgabe: Herleiten:
- wegen Unerfüllbarkeit ist , aber es muss in Kalkül hergeleitet werden
- Überlegung:
- muss am Schluss kommen, um zu bekommen
- bei : wie bekomme ich , um mit bekommen zu können
korrektheit Hilbert-Kalkül
andere Kalküle Bsp syntaktisches Element ist nicht nicht Formelmengen, sondern Paar aus Formelmenge und Formel
korrektheit:
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 ,

-> Klauselmenge entspricht ganzer Äquivalenzklasse von Formeln
-
da Abstraktion:
-
Erfüllbarkeit von Klauselmenge:
- man kann so wählen, dass sie erfüllbar ist
- Bemerkung: -Problem
-
Unerfüllbarkeit:
- keine gute Beweismethode (es gibt nicht immer einen kurzen Beweis)
- zeigen: (?)
-> 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
d.h.
- man darf Klauselmengen beliebig kombinieren
[bild]
-> Unerfüllbarkeitsbeweis:
- leere Klauselmenge finden
- e.g.
-> das Resolutionskalkül besteht nur aus einer Regel!
-> Problem von Resolutionskalkül: Klauseln werden im Allgemeinen grösser
Bsp:
Klauseln:

Bei atomaren Formeln, wie viele Klauseln kann man schreiben?
- es gibt mögliche Literale (Formeln mit Negation)
- es gibt mögliche Klauseln, die hergeleitet werden können
- praktisch weniger, da es viele erfüllbare Klauseln gibt (e.g. )
nicht erlaubt:
timestamp 2024-12-18
recap für jede Logik gilt:
-> je mehr in angenommen wird, desto wahrscheinlicher gelingt Herleitung
Bsp Resolutionskalkül
- je mehr Klauseln es gibt, desto unwahrscheinlicher wird Erfüllbarkeit
- mit in der letzten Klausel wäre es nicht möglich, zu entfernen -> erfüllbar
[bild]
Def Sei Klauseln, Klauselmengen.
-> Man könnte im Resolutionskalkül beliebig neue Klauseln hinzufügen (allerdings nicht das Ziel)
Def 6.30 Resolutionsregel
wobei resolvent ist. Es ist die einzige Regel des Kalküls, d.h.
Lemma 6.5
Proof see script
Thorem 6.6
(A set M of formulas is unsatisfiable) unsatisfiable .
Proof : since has no model (is unsatisfiable)
: Verankerung:
Annahme: Für und beliebige , die enthält, gilt
Induktionsschritt: In einer Klauselmenge betrachten wir alle Klauseln, in denen , oder beide atomare Formeln vorkommen.
- Klauseln der Form sind immer erfüllbar
Sei eine Klauselmenge, wo .
- falls in Klausel, ist Klausel erfüllbar
- falls in Klausel, kann gestrichen werden
- Unerfüllbarkeit hängt nicht mehr von ab
-> eine Herleitung in , die auch in gültig ist ( kommt nicht vor) -> ist unerfüllbar -> eine Herleitung in , die in mit vorkommt -> keine an Ende von Herleitung
analoge Überlegung
Sei eine Klauselmenge, wo .
- falls in Klausel, ist Klausel erfüllbar
- falls in Klausel, kann gestrichen werden
- Unerfüllbarkeit hängt nicht mehr von ab
-> eine Herleitung in , die auch in gültig ist ( kommt nicht vor) -> ist unerfüllbar -> eine Herleitung in , die in mit vorkommt -> keine an Ende von Herleitung
=> cases:
- falls Herleitung zu aus oder existiert (oder in beiden), die in ohne existiert (und aus ohne ) -> unerfüllbar
- falls Herleitungen in aus bzw. immer bzw. haben, kann man die beiden Terme zu schreiben
Bem (Exkurs) Da beide Herleitungen () aufwendig sind, und noch evtl. kombiniert werden müssen,
timestamp 2025-09-27
FYI: https://grossack.site/2025/01/16/undergrad-divisibility-problems.html