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 -> >5 an Prüfung
  • (***)-aufgaben sind sehr Zeitintensiv -> erst am Schluss machen

1 Einführung

Diskret -> endliche Zustaende

Drei Fragen zu den Aussagen?

  1. Ist die Aussage wohldefiniert?
  2. Ist die Aussage wahr oder falsch?
  3. 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

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

  • 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

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

wenn Tautologie, dann -> Bsp: Skript 2.6.4


modus ponens S beweisen:

  1. Eine Aussage formulieren.
  2. beweisen
  3. beweisen

wieso funktioniert:


Lemma 2.1

  • | Distributivgesetz

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


Beweis durch Herleitung


Beweiskonzept

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:

  1. T ist wahr

und sind QZ.


Aussage: ist keine PZ. Beweis: ist nicht PZ ist nicht PZ (oder)

Bem: Nicht wird bewiesen, sondern es wird bewiesen, dass

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


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

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

  1. Direkter Beweis von

Annahme: wahr Beweis: wahr (unter dieser Annahme)


Bsp: Quadrathzahl (QZ), dann QZ

Beweis:

  • S:

  1. Indirekter Beweis von

Annahme: T Falsch

Beweise falsch (unter dieser Annahme)

Lemma:

Beweis:

0011
0111
1000
1111

Bsp: Behauptung: Wurzel von irrationaler Zahl ist irrational.

irrational irrational

Beweis:

Modus Ponens-Beweise

  1. Definiere
  2. Beweise wahr
  3. Beweise wahr

Lemma:

Bsp:

(*) Für gilt: ( und Primzahl )

( und Primzahl)

Bleibt zu beweisen: ist Primzahl.

Fallunterscheidung

(zum Beweis von S)

  1. Definiere
  2. Beweise: mindestens eine Aussage ist wahr
  3. 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

  1. Definiere
  2. Beweise falsch
  3. Beweise: falsch falsch

Lemma: Alternative:

  1. ""
  2. ""
  3. 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)

  1. Verankerung: Beweise wahr (bzw. wahr)
  2. 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)

  1. attempt: (wrong, since sets are unordered)
  2. attempt: (not possible, since this notation is not possible for all pairs)
  3. 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. FormulaSet
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

*abc
abca
bcb ab
cabc

Bsp

  • Assume exists and is a neutral element
*eabc
eeabc
aaecb
bbcea
ccbae
-> 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:

  1. is associative.
  2. is a neutral element: for all .
  3. 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

*ea
eea
aae

  • 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

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:

a01234
f(a)24342
-> 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

01234
11341
22402

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:

  1. Theorie
  1. Aussagen über eine Formel

tautologie/unerfüllbar/…

  1. Aussage über eine Formel in einer konkreten Interpretation

“Wenn es in ist”…

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

  1. Aussagen über die Logik

“Resolutionskalkül ist korrekt, vollständig”


in der Aussagenlogik:


6.5.4 Normalform

Literal: CNF / DNF [bild]

Bsp

ABCF
0001
0010
0100
0111
1000
1011
1100
1110
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

Bsp 6.20

freie Symbole:


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:

ueligotbored

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