Info
Zusammenfassung auf Polybox Kontakt:
- barski
- email: pbarski@student.ethz.ch
- discord: phil1331
- notizen: https://polybox.ethz.ch/index.php/s/p0Ws9UqWdadlGkQ
- Dan Philipp
- norizen: https://n.ethz.ch/~philippda/
- cheatsheet: https://n.ethz.ch/~philippda/DiskMath_Spick
- alle Übungsstunden: Übungsstunden_mit_Lösungen.pdf
Lernmaterialien:
- Skript
- Übungen
- https://discmath.ch
- alte Prüfungen
Struktur:
- Pseudo-Kapitel
- Logik, Einführung in Beweise !!!
- Funktionen, Mengen, Relationen, Abzählbarkeiten
- Zahlentheorie
- Algebra
- (Rigorose) Logik
Mathematische Aussagen und Formeln
timestamp 2024-09-23
mathematische Aussagen (“Propositionen”): Aussagen, denen man eindeutig ein “Wahr” oder “Falsch” zuordnen kann (nach der Mathematik)
- | Def: ( wahr) und es gibt einen Beweisschritt, sodass T aus S wahr wird
- und, oder
Bsp: (… Beweisschritt)
Formeln:
- ist Formel
Für ist
(immer Grund angeben) -> macht aus zwei Formeln Aussage
Bsp: Prove or disprove
- nicht äquivalent bei 3x 0 ->
- Lösung: Consider the assignment of propositional symbols that appear in F or g (). Then, F yields truth value 0 and g yields truth value 1. By definition, this means F and g are not equivalent.
<- “und” verwendet, weil keine Formel
Umformungen (Äquivalenztransformation): (dist. Gesetz)
timestamp 2024-09-30
Wichtig: (Umformungen)
- Immer nur einen Schritt pro Umformung ändern
- z.B. ist nicht erlaubt, da nicht definiert
Prädikatenlogik / First-Order Logic
Prädikate:
Formeln:
Interpretation:
- Universum, Zuweisung (variablen, prädikate, …)
Alle natürlichen Zahlen sind grösser gleich a
Twin-Prime Conjecture
“es gibt unendlich viele “Primzahlen”: p, q, sodass p-q=2
- prime (p)
Äquivalenzumformung
2024-10-07
- prove/disprove answer structure (@2024-10-07@16:00)
- How to solve 3.5)b) (@2025-01-03 16:09)
- How to solve 3.6)b) (@2024-10-08 17:53)
if -> normalerweise Implikation
direkter Beweis
indirekter Beweis
-
Schritt: S und T definieren ungerade und ungerade
-
falsch a oder b gerade
Wir nehmen o.B.d.A (ohne Beschränkung der Allgemeinheit) an, dass a gerade ist für ein (def. gerade Zahlen) (da ) gerade (def. gerade Zahlen) falsch
Somit ist die Aussage durch einen indirekten Beweis bewiesen.
Modus Ponens
zeigen
- passende Aussage
- Wir beweisen, dass wahr ist
- beweisen
Wiedersprichsbeweis
zeigen
- passende Aussage
- falsch beweisen
- annahme falsch, zeigen dass unter annahme wahr
- S und T definieren
Note
T soll eine unabhängig von S falsche Aussage sein
Es existiert keine , sodass (am Ende definieren)
falsch Es existieren , sodass (gleichung durch 6 teilen) (da ) (gleichung oben) wahr (wiederspruch)
Wir haben einen Widerspruch und somit folgt, dass wahr ist.
Case distinction
zeigen
- verschiedene Fälle, die eintreten
- beweisen, dass immer mindestens ein Fall eintritt
- jeden Fall beweisen
Tip
teilbarkeit durch drei: -> rest Betrachten (modulo ())
- es gibt nur drei fälle: n, n+1, n+2
Soundness of proof pattern
- pattern
sound, wenn damit nur wahre Aussagen zeigen können
- Beweisenden Aussage formel zuordnen
- den schritten im proof pattern formel zuordnen
- zeigen
z.B. indirekter Beweis:
z.B. Prüfungsaufgabe
proof pattern:
- A or B true
- is false

In the truth table we see that is true, thus the proof pattern is sound.
2024-10-14
Warning
statt schreiben
Mengenlehre
: für alle Einträge, die genauso in der Menge enthalten sind ist in Menge
für alle Mengen, von denen alle Einträge in der Menge enthalten sind hat gleichen Inhalt wie andere Menge
- jede Menge is Teilmenge von sich selbst
- eine Leere Menge ist immer eine Teilmenge, aber nicht immer ein Element
- für eine endliche Menge A gilt:
- für eine endliche Menge A gilt:
- ist Kardinalität, d.h. die Anzahl Elemente
Bsp:
gleichheit von Mengen beweisen/wiederlegen
Bsp: Beweise oder widerlege Für alle Mengen gilt:
Wiederlegen:
- Gegenbeispiele (z.B. alle Mengen gleichsetzen oder Beispiel finden (Venn-diagram zeichnen))
- Abschlusssatz: Da gilt nicht
Beweisen:
- evtl. zahlenbeispiel
- Lösungswege
- in logik umwandeln -> umformen -> zurück in Mengen
- theorem 3.4: direkt mit Mengen umformen
- : und seperat beweisen:
- Lemma 3.2:
Bsp Lösungsweg 1 Beweise oder wiederlege: Für alle Mengen gilt:
Seien beliebig:
Somit gilt nach der Def. für Gleichheit für alle Mengen .
Note
Folgerungsschritte gelten in beide Richtungen. (Der erste schritt ist keine äquivalenzumformung da definition verwendet wird, um logikformel zu bekommen, danach auch äquivalenzumformung möglich zu schreiben)
2024-10-21
Relationen
-
Eine Relation von einer Menge auf eine Menge ist eine Menge:
-
heist ist ein Relation zu , man schreibt auch
-
auf Relation können wir somit Mengenoperatoren anwenden:
- z.B.
-
Komposition: Für ist die Komposition
Bsp:
Komposition:
Eigenschaften von Relationen
Wir betrachten eine Relation auf eine Menge
- Reflexiv: Für alle gilt:
- Symmetrisch: Für alle gilt:
- Antisymmetrisch: Für alle gilt:
- Transitiv: Für alle gilt:
Note
Zu relationen gibt es immer eine Prüfungsaufgabe
Äquivalenzrelation
ist
- reflexiv
- symmetrisch
- transitiv
notation:
Bsp:
-> ist auch transitiv, weil nie erfüllt, siehe:
Graph:

-> antisymmetrisch
Equivalence relation proof:
Wir nehmen einen Teilmengenbeweis an
Sei (Fallunterscheidung) 1.Fall: ( reflexiv, da Äquiv.) (Def )
2.Fall: ( Reflexiv, da ÄQUIV.)
Da und ist .
2024-10-28
5.5)c) Nachbesprechung
Hasse-Diagramme
- Wir betrachten Posets ()
- Zwei Elemente sind vergleichbar, wenn oder
- ist minimales Element, wenn kein mit existiert
- (kein Pfad nach unten im Hasse Diagramm)
- ist kleinstes Element, wenn für alle
- (mit allen Elementen verbunden im Hasse-Diagramm, muss nicht existieren)
Funktionen
- von Domain zur Codomain
- Es muss gelten:
- totally defined:
- alle Zahlen erreichbar
- well-defined:
- nur ein ergebnis pro zahl
- totally defined:
- Eigenschaften: Eine Funktion ist
- Inkektiv: Wenn , dann gilt
- Surjektiv: Für jedes gilt für ein
- Bijektiv: injektiv und surjektiv
Bsp:
- injektiv
- surjektiv
-> funktionert nicht wenn
Bsp
-
nicht injektiv: (mehrere zahlen auf gleiches element im Codomain)
, aber -
surjektiv, da -> jedes Element erreicht
Abzälbarkeit
- Wir wollen zeigen, dass eine Menge A abzählbar ist:
- Wir definieren eine Funktion , wo eine abzählbare Menge ist (z.B. )
- Zeige, dass wirklich gilt für alle
- Wir zeigen, dass diese Funktion injektiv ist

Note
eine solche Aufgabe kommt normalerweise an Prüfung, gibt viele Punkte
2024-11-04
Nachbeschrepchung Bonus
- keline Begründunge, warum eine Injektion zu finden die uncountability beweist
- alle Schritte genau asführen
- Achtet auf die Domain/Codomain der FUntionen in
Aufgabe Beweise oder widerlege
Wir definieren . Nach Theorem 3.22 ist abzћhlbar, da abzählbar. Aus der Injektion folgt und somit .
Sei für alle
Zeige für alle Sei beliebig. Da ist ein string aus natürlichen Zahlen und somit in
g injektiv:
Sei , sodass Somit gilt . Für alle muss gelten , da die FUnktiona b dort konstant sind.
Modulo rechnen
- der Rest, wenn wir n durch m teilen
- Bsp:
- Für Addition und Multiplikation gilt:
- Formale Definition:
- wichtig für beweise
Bsp
Bsp
- oder
-> für diesen Aufgabentyp zählt nur die Lösung
Bsp
Number Theory
Thoerem 4.6 Jede natürliche Zahl kann eindeutig in ein Produkt aus Primzahlen zerlegt werden
- grösster gemeinsamer Teiler von und
- kleinstes gemeinsames Vielfaches von und
Bsp
Euklidischer Algorithmus
- Ziel: berechnen
- wir teilen die grössere Zahl durch die kleinere und notieren den Rest
- Wir wiederholen dies, bis eine der Zahlen 0 ist
- Die andere Zahl ist dann der
Bsp
=>
-> relativ häufiger aufgabentyp an prüfung
Bsp Zeige, dass keine die folgende Gleichung erfüllen:
Wir betrachten mod :
Da und für alle kann die Gleichung nicht gelten.
welches modulo benutzen -> ausprobieren
Ideal
-
- Bsp
-
- Bsp
- Mengenbeweis, da Menge !!!
Multiplikative Inverse
hat nur eine Lösung genau dann wenn . Die Lösung ist einzigartig. Die Lösung können wir mit dem erweiterten euklidischen Algorithmus berechnen.
Bsp Berechne die multiplikative Inverse von modula
-> euklidischer Algorithmus
Chinese Remainder Theorem
Wir haben mehrere modulare Kongruenzen mit einem x, das wir suchen:
Wichtig: Die Moduli (2,5,7) müssen paarweise teilerfremd sein. Dann gilt: Es gibt eine eindeutige Lösung für x mit , wobei
Diffie-Hellman Protokoll
Note
Funktionsweise des Protokolls auf das Cheatsheet aufschreiben
timestamp 2024-11-11
2024-11-11
Algebra
Algebra: für eine Menge und eine abgeschlossene Operation Monoid
- ist assoziativ
- ist neutrales element
Gruppe
- G1 ist assoziativ
- G2: ist neutrales Element
- G3 Jedes hat ein inverses element
Eine Gruppe ist abelsch, wenn kommutativ
Subgroups
Für von is a subgroup of if , if
- for all a,b
- forall
Lagrange: Die Ordnung einer Subgroup teilt die Ordnung der Gruppe
Morphisen
Ein Homomorphismus ist eine FUnktion für zwei Gruppen und , die folgendes erfüllt:
Wenn diese Funktion zusätzlich bijektiv ist, ist es ein Isomorphismus. Mann schreibt dann
Isomorphismus beweisen
Zu beweisen: für zwei Gruppen und
- Funktion finden
- …
Zyklische Gruppen
- Für eine Gruppe und ein ist die Gruppe generiert von :
- Einge Gruppe ist zyklisch, wenn es ein gibt mit
Zyklische Gruppen
Wir wollen einen Generator einer zyklischen Gruppe finden:
- Gruppenordnung berechnen
- Die Ordnung jedes Elements muss nun ein Teiler der Gruppenordnung sein
- Wenn für ein gilt , es ist ein Generator
- Somit finden wir die Generatoren durch Ausprobieren
Gruppenordnung anzahl Elemente Ordnung von Elementen
Trick
Bsp
timestamp 2024-11-18
Isomorphe und zyklische Gruppen - Übersicht
slides may be outdated
Tabelle zyklische Gruppen aufschreiben auf Cheatsheet
Einheiten und Nullteiler
see above
- für endliche Gruppen gilt: Jedes Element ist entweder Einheit, Nullteiler oder 0.
(Einheiten: Alle Teilerfremden Elemente (?))
Polynome in Ringen
see above
Körper
see above
- kommutative Ring mit
- mit
- ist abelsche Gruppe
- ist abelsche Gruppe
ist ein Körper genau dann wenn prim. Wir schreiben dann auch .
2024-12-02
timestamp 2024-12-02
Beweissysteme
- complete: zeigen, dass es für beliebiges gültigen Beweis gibt
- nicht complete: gegenbeispiel
Bsp: (kommt so nie vor) s ist keine Primzahl p|s mit und
Bsp für alle (alle Aussagen sind wahr) für alle
-> muss nicht sound sein
2024-12-09
timestamp 2024-12-09
Logic
forms: menge aller formeln
- Syntax: Alphabet , Forms
- Semantics: For Forms
- free
- Interpretation “assigns free symbols”
- suitable for if it assigns all free symbols in .
- (write for )
Bsp
Interpretation : , atoms z.b. -> nicht passend für , weil nicht zugewiesen -> suitable for
- mit def 6.16 auswerten
def 6.9 For Forms, Interpretation is a model for if for all (write )
def 6.10-13
- is satisfiable if for some interpretation .
- is tautology if for all interpretations .
- formulas. is log. consequence of (write ), if for any suitable for bot :
How do we prove:
- | Take arb. suitable for both. Show
- oft direkt, manchmal indirekt
- | Counterexample: find suitable for both s.t.
- | Show and
- | Show or
- is taut | Take arb. , show
- is not a taut. | Construct s.t.
- is satisfiable | Construct s.t.
- is not satisifiable | Take arb. , show
Pred. logic
- Syntax: , , (vars, facts, predicates)
- possibly free symbols
- shows arity
- wir quantifizieren nur über variablen (“first-order logic”)
- term variables are terms, are terms (for terms -> recursive def)
- werden Universumswerte zugewiesen (siehe semantik)
- forms: , , , , ,
- for formulas, terms,
- werden Wahrheitswerte zugewiesen (siehe semantik)
- Semantics:
- : non-empty set (universe)
- write
- : (
- write
- :
- write
-
- write
- : non-empty set (universe)
free symbols:
| PropL | Pred L |
|---|---|
| atoms (atomic formulas) | and unbound |
| assigns to atoms | -> P is unbound, x is bound, y is unbound (freie variable) |
| -> is unbound, second is unbount, first is bound |
For terms , (induktive def.)
- jeder variablen wird wert zugewiesen, Funktion/term wird dann auf diese Variablen angewendet
For formulas:
def 6.16
- und
- or
where is the interpretation that is equal to except that
Bsp einfache Prüfungsaufgabe Find a model for
- freien Symbole: -> mindestens sie müssen definiert werden
- Universum wählen
Bsp (nicht eindeutig)
- verify (in der Prüfung nur kurze Begründung):
-> def. einsetzen
Bsp Prove for any formula that .
Let be an arbitrary interpretation that is suitable for both sides. Assume .
todo: why is step 2 incorrect for ?
Bsp Prove: .
Let be an arb. int. suit. for both sides. Assume
- case 1: appears free in : since is suitable for , is defined.
- implies
- case 2: doesn’t appear free in : (nicht frei oder kommt gar nicht vor)
- Then for any
- implies
in either case, “ ( -> stimmt, )
Note
In diesen beweisen kommt Fallunterscheidung um freie Variablen oft vor -> aufpassen! wenn wir nicht wissen, ob freie variable vorkommt, immer case distinction machen
Bsp Disprove: For any formula F:
We disprove the claim by giving a counterexample : Let
Then , since . On the other hand, since
- for some
2024-12-16
Resolutionskalkül
Bsp
…
- nur einmal anwenden möglich -> nur möglich: