Info

Zusammenfassung auf Polybox Kontakt:

Lernmaterialien:

  1. Skript
  2. Übungen
  3. https://discmath.ch
  4. alte Prüfungen

Struktur:

  1. Pseudo-Kapitel
  2. Logik, Einführung in Beweise !!!
  3. Funktionen, Mengen, Relationen, Abzählbarkeiten
  4. Zahlentheorie
  5. Algebra
  6. (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


  1. Schritt: S und T definieren ungerade und ungerade

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

  1. passende Aussage
  2. Wir beweisen, dass wahr ist
  3. beweisen

Wiedersprichsbeweis

zeigen

  1. passende Aussage
  2. falsch beweisen
  3. annahme falsch, zeigen dass unter annahme wahr

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

  1. verschiedene Fälle, die eintreten
  2. beweisen, dass immer mindestens ein Fall eintritt
  3. 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
  1. Beweisenden Aussage formel zuordnen
  2. den schritten im proof pattern formel zuordnen
  3. zeigen

z.B. indirekter Beweis:


z.B. Prüfungsaufgabe

proof pattern:

  1. A or B true
  2. 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))
  1. Abschlusssatz: Da gilt nicht

Beweisen:

  • evtl. zahlenbeispiel
  • Lösungswege
    1. in logik umwandeln -> umformen -> zurück in Mengen
    2. theorem 3.4: direkt mit Mengen umformen
    3. : 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:
    1. totally defined:
      • alle Zahlen erreichbar
    2. well-defined:
      • nur ein ergebnis pro zahl
  • 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

  1. 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
  1. wir teilen die grössere Zahl durch die kleinere und notieren den Rest
  2. Wir wiederholen dies, bis eine der Zahlen 0 ist
  3. 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

free symbols:

PropLPred 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

  1. freien Symbole: -> mindestens sie müssen definiert werden
  2. 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: