Mathematische Aussagen und Formeln

#timestamp 2024-09-23

mathematische Aussagen ("Propositionen"): Aussagen, denen man eindeutig ein "Wahr" oder "Falsch" zuordnen kann (nach der Mathematik)

• $S,T,U$
• $S⟹T$
• $S\dot{⟹}T$ | Def: ($S⟹T$ wahr) und es gibt einen Beweisschritt, sodass T aus S wahr wird
• und, oder

Bsp:
$u=v\ast v$
$\dot{⟹}\text{Peter geht es gut}$ (... Beweisschritt)

Formeln: $A,B,C,D,\dots$

• $\wedge ,\vee ,\to ,\mathrm{\neg },⟺$
• $A\wedge B$ ist Formel
• $(A\wedge B)\to C$

Für $A=1,B=0,C=1$ ist $F=(A\wedge B)\to C$

$F\equiv G$ (immer Grund angeben) -> macht aus zwei Formeln Aussage

Bsp: Prove or disprove $F=((A\wedge \mathrm{\neg }C)\vee (\mathrm{\neg }A\wedge C))\equiv ((C\to A)\to (B\to (A\wedge \mathrm{\neg }C)))=g$

• nicht äquivalent bei 3x 0 ->
• Lösung: Consider the assignment of propositional symbols that appear in F or g ($A=0,B=0,C=0$). Then, F yields truth value 0 and g yields truth value 1. By definition, this means F and g are not equivalent.

$(F\equiv g)⟺(F\models G)\text{und}(F\models G)$ <- "und" verwendet, weil keine Formel

Umformungen (Äquivalenztransformation):
$A⟺B\equiv (A\to B)\wedge (B\to A)$
$A\wedge (B\vee C)\equiv (A\wedge B)\vee (A\wedge C)$ (dist. Gesetz)
$F\wedge \mathrm{\top }=F$
$F\wedge \mathrm{\perp }=\mathrm{\perp }$

#timestamp 2024-09-30

Wichtig: (Umformungen)

• Immer nur einen Schritt pro Umformung ändern
• z.B. $A\wedge B\wedge C$ 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

• $U=\mathbb{N}$
• $\mathrm{\forall }x(1\le x)$

Twin-Prime Conjecture

"es gibt unendlich viele "Primzahlen": p, q, sodass p-q=2

• $U=\mathbb{N}$
• 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

$S⟹T$

indirekter Beweis

$S⟹T$

1. $\mathrm{\neg }T⟹\mathrm{\neg }S$

1. Schritt: S und T definieren
   $S:a\ast b$ ungerade
   $T:a$ und $b$ ungerade

2. $T$ falsch $\dot{⟹}$ a oder b gerade

Wir nehmen o.B.d.A (ohne Beschränkung der Allgemeinheit) an, dass a gerade ist
$⟹a=2k$ für ein $k\in \mathbb{Z}$ (def. gerade Zahlen)
$\dot{⟹}ab=2(k\ast b)$ (da $ab=2kb=2(kb)$)
$\dot{⟹}a\ast b$ gerade (def. gerade Zahlen)
$\dot{⟹}S$ falsch

Somit ist die Aussage durch einen indirekten Beweis bewiesen.

Modus Ponens

$S$ zeigen

1. passende Aussage $R$
2. Wir beweisen, dass $R$ wahr ist
3. beweisen $R⟹S$

Wiedersprichsbeweis

$S$ zeigen

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

1. S und T definieren

$S:$ Es existiert keine $a,b\in \mathbb{Z}$, sodass $18a+6b=1$
$T:$ $\frac{1}{6}\in \mathbb{Z}$ (am Ende definieren)

$S$ falsch $\dot{⟹}$ Es existieren $a,b\in \mathbb{Z}$, sodass $18a+6b=1$
$\dot{⟹}3a+b=\frac{1}{6}$ (gleichung durch 6 teilen)
$\dot{⟹}3a+b\in \mathbb{Z}$ (da $a,b\in \mathbb{Z}$)
$\dot{⟹}\frac{1}{6}\in \mathbb{Z}$ (gleichung oben)
$\dot{⟹}T$ wahr (wiederspruch)

Wir haben einen Widerspruch und somit folgt, dass $S$ wahr ist.

Case distinction

$S$ zeigen

1. verschiedene Fälle, die eintreten
2. beweisen, dass immer mindestens ein Fall eintritt
3. jeden Fall beweisen

Soundness of proof pattern

• pattern sound, wenn damit nur wahre Aussagen zeigen können

1. Beweisenden Aussage formel $G$ zuordnen
2. den schritten im proof pattern formel $F$ zuordnen
3. zeigen $F\models G$

z.B. indirekter Beweis:

z.B. Prüfungsaufgabe

proof pattern:

1. A or B true
2. $B\to C$
3. $C$ is false

In the truth table we see that $A\vee B)\wedge (B\to C)\wedge \mathrm{\neg }C\models A$ is true, thus the proof pattern is sound.

2024-10-14

Mengenlehre

$\in$: für alle Einträge, die genauso in der Menge enthalten sind
$\in \widehat{=}$ ist in Menge

$\subseteq :$ für alle Mengen, von denen alle Einträge in der Menge enthalten sind
$\hat{\subseteq }=$ 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: $|P(A)|=2^{|A|}$
• für eine endliche Menge A gilt: $|A\times B|=|A|\times |B|$
• $|$ ist Kardinalität, d.h. die Anzahl Elemente

Bsp:

gleichheit von Mengen beweisen/wiederlegen

Bsp: Beweise oder widerlege
Für alle Mengen $A,B,C$ gilt: $(A\setminus B)\setminus C=A\setminus (B\setminus C)$

Wiederlegen:

• Gegenbeispiele (z.B. alle Mengen gleichsetzen $A=B=C=\{1\}$ oder Beispiel finden (Venn-diagram zeichnen))

1. $A=\{1,2\},B=\{2,3\},C=\{2\}$
2. $(A\setminus B)\setminus C=(\{1,2\}\setminus \{2,3\})\setminus \{2\}=\{1\}$
   $A\setminus (B\setminus C)=\dots$
3. Abschlusssatz: Da $\{1\}\ne \{1,2\}$ gilt $(A\setminus B)\setminus C=A\setminus (B\setminus C)$ nicht

Beweisen:

• evtl. zahlenbeispiel
• Lösungswege
  1. in logik umwandeln -> umformen -> zurück in Mengen
  2. theorem 3.4: direkt mit Mengen umformen
  3. $A=B$: $A\subseteq B$ und $B\subseteq A$ seperat beweisen:
     • $A\subseteq B⟺\mathrm{\forall }x(x\in A\to x\in B)$
     • $B\subseteq A⟺\mathrm{\forall }x(x\in B\to x\in A)$
     • Lemma 3.2: $(A\subseteq B)\wedge (B\subseteq A)\leftrightarrow A=B$

Bsp Lösungsweg 1
Beweise oder wiederlege:
Für alle Mengen $A,B,C$ gilt: $A\setminus (B\setminus C)=(A\setminus B)\cup (A\cap C)$

Seien $A,B,C$ beliebig:

Somit gilt $A\setminus (B\setminus C)=(A\setminus B)\cup (A\cap C)$ nach der Def. für Gleichheit für alle Mengen $A,B,C$.

2024-10-21

Relationen

• Eine Relation $\rho$ von einer Menge $A$ auf eine Menge $B$ ist eine Menge: $\rho \subseteq A\times B$

• $(i,j)\in \rho$ heist $i$ ist ein Relation zu $j$, man schreibt auch $i\rho j$

• auf Relation können wir somit Mengenoperatoren anwenden:

  • z.B. $\rho \cup \sigma =\{(a,b)|(a,b)\in \rho \vee (a,b)\in \sigma \}$

• Komposition: Für $\rho \subseteq A\times B,\sigma \subseteq B\times C$ ist die Komposition $\rho \circ \sigma =\{(a,b)|\mathrm{\exists }b(a,b)\in \rho \wedge (b,c)\in \sigma \}\subseteq A\times C$

Bsp:
$A=\{1,3,5\}$
$B=\{2,3\}$
$\le =\{(1,2),(1,3),(3,3)\}\subseteq A\times A$

$\rho =\{(1,3)\}\subseteq A\times B$
$\hat{\rho }=\{(3,1)\}\subseteq B\times A$
$\sigma =\{(1,5),(3,3),(5,5)\}$
$i{d}_A=\{(1,1),(3,3),(5,5)\}\subseteq A\times A$

$\le \cup \rho =\{(1,2),(1,3),(3,3),(3,2),(5,2),(5,3)\}$

Komposition:

Eigenschaften von Relationen

Wir betrachten eine Relation $\rho$ auf eine Menge $A$

• Reflexiv: Für alle $a\in A$ gilt: $a\rho a$
• Symmetrisch: Für alle $a,b\in A$ gilt: $a\rho b⟺b\rho a$
• Antisymmetrisch: Für alle $a,b\in A$ gilt: $a\rho b\wedge b\rho a⟹a=b$
• Transitiv: Für alle $a,b,c\in A$ gilt: $a\rho b\wedge b\rho c⟹a\rho c$

Äquivalenzrelation

ist

• reflexiv
• symmetrisch
• transitiv

notation: $\theta \subseteq A\times A$

Bsp: $a\theta b\leftrightarrow a{\equiv }_{3}b$

$A=\{1,2,3,4,5\}$
$\theta =\{(1,1),(1,4),(4,1),(4,4),(2,2),(2,5),(5,2),(5,5),(3,3)\}$
-> ist auch transitiv, weil nie erfüllt, siehe:
$5{\equiv }_{3}88{\equiv }_{3}14⟹5{\equiv }_{3}14$

Graph:

$\preccurlyeq \subseteq A\times A$
$(A,\preccurlyeq )$
$A=\{1,3,4,8,9\}$
$|=\{(2,2),(2,4),(4,8),(2,8),(4,4),(8,8),(3,3),(3,9),(9,9)\}$
-> antisymmetrisch
$a|b$

Equivalence relation proof:

• [[2024_10_21 17_48 Office Lens.pdf]]

Wir nehmen einen Teilmengenbeweis an

1. $\rho \circ \sigma \subseteq \rho \cup \sigma$

2. $\rho \cup \sigma \subseteq \rho \circ \sigma$

Sei $(a,c)\in \rho \cup \sigma$ (Fallunterscheidung)
1.Fall: $(a,c)\in \rho \dot{⟹}(a,c)\in \rho \wedge (c,c)\in \sigma$ ($\sigma$ reflexiv, da Äquiv.)
$\dot{⟹}(a,c)\in \rho \circ \sigma$ (Def $\circ$)

2.Fall: $(a,c)\in \sigma$
$(a,c)\in \sigma \dot{⟹}(a,a)\in \rho \wedge (a,c)\in \sigma$ ($\rho$ Reflexiv, da ÄQUIV.)
$\dot{⟹}(a,c)\in \rho \circ \sigma$

Da $\rho \circ \sigma \subseteq \rho \cup \sigma$ und $\rho \cup \sigma \subseteq \rho \circ \sigma$ ist $\rho \cup \sigma =\rho \circ \sigma$.

2024-10-28

5.5)c) Nachbesprechung

$\mathbb{Z}\times \mathbb{Z}\subseteq {\rho }^2$
${\rho }^2$

Hasse-Diagramme

• Wir betrachten Posets ($A,⪯$)
• Zwei Elemente $a,b$ sind vergleichbar, wenn $a⪯b$ oder $b⪯a$
• $a\in A$ ist minimales Element, wenn kein $b\in A$ mit $b\prec a$ existiert
  • (kein Pfad nach unten im Hasse Diagramm)
• $a\in A$ ist kleinstes Element, wenn $a⪯b$ für alle $b\in A$
  • (mit allen Elementen verbunden im Hasse-Diagramm, muss nicht existieren)

Funktionen

$f:\mathbb{Z}⟹\mathbb{Z}$

• von Domain $A$ zur Codomain $B$
  $f(x)=2x$
• Es muss gelten:
  1. $f$ totally defined: $\mathrm{\forall }a\in A\mathrm{\exists }b\in B:afb$
     • alle Zahlen erreichbar
  2. $f$ well-defined: $\mathrm{\forall }a\in A\mathrm{\forall }b,b^{\prime }\in B:(afb\wedge af{b}^{\prime }\to b=b^{\prime })$
     • nur ein ergebnis pro zahl
• Eigenschaften: Eine Funktion $f:A\to B$ ist
  • Inkektiv: Wenn $a\ne a^{\prime }$, dann gilt $f(a)\ne f(a^{\prime })$
  • Surjektiv: Für jedes $b\in B$ gilt $f(a)=b$ für ein $a\in A$
  • Bijektiv: injektiv und surjektiv

Bsp:

• injektiv

$a,a^{\prime }\in \mathbb{Z}$
$2a\ne 2a^{\prime }✓$

• surjektiv

$b\in \mathbb{Z}$
$2a=b$
$a=\frac{b}{2}$
-> funktionert nicht wenn $b=3$

Bsp

• nicht injektiv: (mehrere zahlen auf gleiches element im Codomain)
  
  $011{\ne }_{0}00$, aber $f(011)=f(00)$

• surjektiv, da $g(1)=1,g(01)=0$ -> jedes Element erreicht

Abzälbarkeit

$\mathbb{N},\mathbb{Z},\mathbb{R}$

• Wir wollen zeigen, dass eine Menge A abzählbar ist:
  • Wir definieren eine Funktion $f:A\to B$, wo $B$ eine abzählbare Menge ist (z.B. $\mathbb{N},\{0,1{\}}^{\ast }$)
  • Zeige, dass wirklich $f(a)\in B$ gilt für alle $a\in A$
  • Wir zeigen, dass diese Funktion injektiv ist

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

Aufgabe
Beweise oder widerlege

Wir definieren $g:S\to {\mathbb{N}}^{\ast }$. Nach Theorem 3.22 ist ${\mathbb{N}}^{\ast }$ abzћhlbar, da $\mathbb{N}$ abzählbar. Aus der Injektion $g$ folgt $S⪯{\mathbb{N}}^{\ast }$ und somit $S⪯\mathbb{N}$.

Sei $\delta \in S$
$g(f)=(f(0),f(1),f(2),\dots ,f(x_k))$
$f(y)=\delta (x_k)$ für alle $y\ge x_k$

Zeige $g(\delta )$ für alle $\delta \in S$
Sei $\delta \in S$ beliebig.
Da $f:\mathbb{N}\to \mathbb{N}$ ist $g(\delta )$ ein string aus natürlichen Zahlen und somit in ${\mathbb{N}}^{\ast }$

g injektiv:
$f\ne f^{\prime }⟹g(\delta )\ne g({\delta }^{\prime })$
$g(f)=g(f^{\prime })⟹f=f^{\prime }$

Sei $f,f^{\prime }$, sodass $g(f)\ne g(f^{\prime })$
Somit gilt $f(x)=f^{\prime }(x)$.
Für alle $y>x_k$ muss gelten $f(y)=f^{\prime }(y)$, da die FUnktiona b dort konstant sind.

Modulo rechnen

• $R_m(n)=$ der Rest, wenn wir n durch m teilen
  • Bsp: $R_5(13)=3$
• Für Addition und Multiplikation gilt:

• Formale Definition: $a{\equiv }_{m}b⟺m|(a-b)$
  • wichtig für beweise

Bsp

Bsp
$R_{31}(2^{1003})=R_{31}({32}^{200}\cdot 8)=R_{31}(1^{200}\cdot 8)=R_{31}(1\cdot 8)=8$

1. $2^x{\equiv }_{31}1$ oder $2^x{\equiv }_{31}-1$
2. $x=5:2^5=32{\equiv }_{31}1$
3. $2^{1003}=2^{1000}\cdot 2^3=2^{5^{2000}}\ast 2^3$

-> für diesen Aufgabentyp zählt nur die Lösung

Bsp
$5^3=125{\equiv }_9-1$

Number Theory

Thoerem 4.6 Jede natürliche Zahl kann eindeutig in ein Produkt aus Primzahlen zerlegt werden

• $gcd(a,b):$ grösster gemeinsamer Teiler von $a$ und $b$
• $lcm(a,b):$ kleinstes gemeinsames Vielfaches von $a$ und $b$

Bsp

Euklidischer Algorithmus

• Ziel: $gcd(a,b)$ 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 $gcd$

Bsp

=> $gcd=4$

-> relativ häufiger aufgabentyp an prüfung

Bsp
Zeige, dass keine $x,y\in \mathbb{Z}$ die folgende Gleichung erfüllen:

$R_m(x)=$
$R_m(y)=$

Wir betrachten $x,y$ mod $3$:
$x{\equiv }_{3}0\to x^3{\equiv }_{3}0\to x^3-x{\equiv }_{3}0$
$x{\equiv }_{3}1\to x^3{\equiv }_{3}1\to x^3-x{\equiv }_{3}0$
$x{\equiv }_{3}2\to x^3{\equiv }_{3}2\to x^3-x{\equiv }_{3}0$

$y{\equiv }_{3}0\to y^2{\equiv }_{3}0\to y^2+1{\equiv }_{3}1$
$y{\equiv }_{3}1\to y^2{\equiv }_{3}1\to y^2+1{\equiv }_{3}2$
$y{\equiv }_{3}2\to y^2{\equiv }_{3}2\to y^2+1{\equiv }_{3}2$

Da $R_3(x^3-x)=0$ und $R_3(y^2+1)\in \{1,2\}$ für alle $x,y\in \mathbb{Z}$ kann die Gleichung nicht gelten.

welches modulo benutzen -> ausprobieren

Ideal

• $(a)=\{ua|u\in \mathbb{Z}\}$
  • Bsp $(4)=\{\dots ,-4,0,4,8,\dots \}$
• $(a,b)=\{ua+vb|u,v\in \mathbb{Z}\}$
  • Bsp $(3,5)=\{\dots ,-5,-3,0,3,5,\dots \}$
  • Mengenbeweis, da Menge !!!

Multiplikative Inverse

hat nur eine Lösung genau dann wenn $gcd(a,m)=1$. Die Lösung ist einzigartig.
Die Lösung können wir mit dem erweiterten euklidischen Algorithmus berechnen.

Bsp
Berechne die multiplikative Inverse von $15$ modula $53$

-> 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 $0\le x\le M$, wobei $M=2\ast 5\ast 7=70$

Diffie-Hellman Protokoll

#timestamp 2024-11-11

2024-11-11

Algebra

Algebra: $⟨G,\ast ⟩$ für eine Menge $G$ und eine abgeschlossene Operation $\ast :G^k\to G$
Monoid $⟨M,\ast ,e⟩$

• $\ast$ ist assoziativ
• $e\in M$ ist neutrales element

Gruppe $⟨G,\ast ,\hat{},e⟩$

• G1 $\ast$ ist assoziativ
• G2: $e\in G$ ist neutrales Element
• G3 Jedes $a\in G$ hat ein inverses element

Eine Gruppe ist abelsch, wenn $\ast$ kommutativ

Subgroups

Für $H\subseteq G$ von $⟨G;\ast ,\hat{},e⟩$ is a subgroup of $G$ if $⟨H;\ast .\hat{},e⟩$, if

• $a\ast b\in H$ for all a,b
• $e\in H$
• $\hat{a}\in H$ forall $a\in H$

Lagrange: Die Ordnung einer Subgroup teilt die Ordnung der Gruppe

Morphisen

Ein Homomorphismus ist eine FUnktion $\psi :G\to H$ für zwei Gruppen $⟨G;\ast ,\hat{},e⟩$ und $⟨H,\star ,\sim ,e^{\prime }⟩$, die folgendes erfüllt:

Wenn diese Funktion zusätzlich bijektiv ist, ist es ein Isomorphismus. Mann schreibt dann $G\simeq H$

Isomorphismus beweisen

Zu beweisen: $G\simeq H$ für zwei Gruppen $⟨G;\ast ,\hat{},e⟩$ und $⟨H,\star ,\sim ,e^{\prime }⟩$

• Funktion $\psi :G\to H$ finden
• ...

Zyklische Gruppen

• Für eine Gruppe $G$ und ein $a\in G$ ist die Gruppe generiert von $a$:

• Einge Gruppe ist zyklisch, wenn es ein $g\in G$ gibt mit $⟨g⟩=G$

Zyklische Gruppen

Wir wollen einen Generator einer zyklischen Gruppe $G$ finden:

• Gruppenordnung $|G|$ berechnen
• Die Ordnung jedes Elements muss nun ein Teiler der Gruppenordnung sein
• Wenn für ein $g\in G$ gilt $ord(g)=|G|$, es ist ein Generator
• Somit finden wir die Generatoren durch Ausprobieren

Gruppenordnung $\widehat{=}$ anzahl Elemente
Ordnung von Elementen $\mathrm{\forall }a\in A:a^i=e$

Bsp

• $|{\mathbb{Z}}_{14}^{\ast }|=\phi (1\cdot 4)=\phi (2\cdot 7)=1\cdot 6=6$
• $=\phi (2\cdot 3^3)=1\cdot 2\cdot 3=18$
• $\phi (5^2\cdot 2\cdot 3^3)=(5-1)5\cdot (2-1)\cdot (3-1)3^2=4\cdot 5\cdot 2\cdot 3^2$

#timestamp 2024-11-18

Isomorphe und zyklische Gruppen - Übersicht

slides may be outdated
![[Übungsstunde 9.pdf]]

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

$a_0{x}^3+a_1{x}^2+\cdots +a_0$

Körper

see above

• kommutative Ring mit $F^{\ast }=F\setminus \{0\}$
• $⟨F,+,-,0,\ast {,}^{-1},1⟩$ mit
  • $⟨F,+,-,0⟩$ ist abelsche Gruppe
  • $⟨F,\ast {,}^{-1},1⟩$ ist abelsche Gruppe

${\mathbb{Z}}_p$ ist ein Körper genau dann wenn $p$ prim. Wir schreiben dann auch $GF(p)$.

2024-12-02

#timestamp 2024-12-02

![[Übungsstunde 11.pdf]]

Beweissysteme

• complete: zeigen, dass es für beliebiges $s\in S$ gültigen Beweis gibt
• nicht complete: gegenbeispiel

Bsp:
(kommt so nie vor)
$S=\mathbb{N},P=\mathbb{N}$
$\tau (s)=1⟺$ s ist keine Primzahl
$\varphi (s,p)=1⟺$ p|s mit $1<p$ und $p<s$
$\tau (6)=1$
$\varphi (6,2)=1$

Bsp
$S=P=\{0,1\}$
$\tau (s)=1$ für alle $s\in S$ (alle Aussagen sind wahr)
$\varphi (s,p)=0$ für alle $s\in S,p\in P$

-> muss nicht sound sein

2024-12-09

#timestamp 2024-12-09

Logic

forms: menge aller formeln

• Syntax: Alphabet $\mathrm{\Lambda }$, Forms $\subseteq$ ${\mathrm{\Lambda }}^{\ast }$
• Semantics: For $F=(f_1,\dots ,f_k)\in$ Forms
  • free$F\subseteq \{1,\dots ,k\}$
  • Interpretation $\mathcal{A}$ "assigns free symbols"
    • $\mathcal{A}$ suitable for $F$ if it assigns all free symbols in $F$.
  • $\sigma (F,\mathcal{A})\in \{0,1\}$ (write $\mathcal{A}(F)$ for $\sigma (F,\mathcal{A})$)

Bsp

Interpretation $\mathcal{A}$: $\mathcal{Z}\to \{0,1\}$, $\mathcal{Z}\subseteq$ atoms
z.b.
$A_1=\{(A,1),(B,0)\}$ -> nicht passend für $F_1$, weil $C$ nicht zugewiesen
$A_2=A_1\cup \{(C,0),(D,1)\}$ -> suitable for $F_1$

• mit def 6.16 auswerten

def 6.9 For $M\subseteq$ Forms, Interpretation $\mathcal{A}$ is a model for $M$ if $\sigma (F,\mathcal{A})=1$ for all $F\in M$ (write $\mathcal{A}\models M$)

def 6.10-13

• $F$ is satisfiable if $\mathcal{A}\models F$ for some interpretation $\mathcal{A}$.
• $F$ is tautology if $\mathcal{A}\models F$ for all interpretations $\mathcal{A}$.
• $F,G$ formulas. $G$ is log. consequence of $F$ (write $F\models G$), if for any $\mathcal{A}$ suitable for bot $F,G$:
  • $\mathcal{A}(F)=1⟹\mathcal{A}(G)=1$
• $F\equiv G⟺F\models G\wedge G\models F$

How do we prove:

• $F\models G$ | Take arb. $\mathcal{A}$ suitable for both. Show $\mathcal{A}(F)=1⟹\mathcal{A}(G)=1$
  • oft direkt, manchmal indirekt
• $F⊭G$ | Counterexample: find $\mathcal{A}$ suitable for both s.t. $\mathcal{A}(F)=1,\mathcal{A}(G)=0$
• $F\equiv G$ | Show $F\models G$ and $G\models F$
• $F\not\equiv G$ | Show $F⊭G$ or $G⊭F$
• $F$ is taut | Take arb. $\mathcal{A}$, show $\mathcal{A}(F)=1$
• $F$ is not a taut. | Construct $\mathcal{A}$ s.t. $\mathcal{A}(F)=0$
• $F$ is satisfiable | Construct $\mathcal{A}$ s.t. $\mathcal{A}(F)=1$
• $F$ is not satisifiable | Take arb. $\mathcal{A}$, show $\mathcal{A}(F)=0$

Pred. logic

• Syntax: $\mathrm{\Lambda }\supseteq \{x_i{\}}_{i\in \mathbb{N}}$, $\{f_i^{(k)}{\}}_{i,k\in \mathbb{N}}$, $\{P_i^{(k)}{\}}_{i,k\in \mathbb{N}}$ (vars, facts, predicates)
  • possibly free symbols
  • $k$ shows arity
  • wir quantifizieren nur über variablen ("first-order logic")
  • term variables are terms, $f_i^{(k)}(t_1,\dots ,t_k)$ are terms (for terms $t_1,\dots ,t_k$-> recursive def)
    • werden Universumswerte zugewiesen (siehe semantik)
  • forms: $p_i^{(k)}(t_1,\dots ,t_k)$, $F\wedge G$, $F\vee G$, $\mathrm{\neg }F$, $\mathrm{\exists }{x}_{i}F$, $\mathrm{\forall }{x}_{i}F$
    • for $F,G$ formulas, $t_1,\dots ,t_k$ terms, $x_i\in \{x_i{\}}_{i\in \mathbb{N}}$
    • werden Wahrheitswerte zugewiesen (siehe semantik)
  • Semantics: $\mathcal{A}=(U,\varphi ,\psi ,\xi )$
    • $U$: non-empty set (universe)
      • write $U^{\mathcal{A}}$
    • $\varphi$: ($f_i^{(k)}):U^k\to U$
      • write $f^{\mathcal{A}}$
    • $\psi$: $(P_i^{(k)}):U^K\to \{0,1\}$
      • write $P^{\mathcal{A}}$
    • $\xi :(x_i):U$
      • write $x_i^{\mathcal{A}}$

free symbols:

For terms $\mathcal{A}(x_i)=x_i^{\mathcal{A}}$, $A(f_i^{(k)}(t_1,\dots ,t_k))=\varphi (f_i^{(k)})(\mathcal{A}(t_1),\dots ,\mathcal{A}(t_k))$ (induktive def.)

• jeder variablen wird wert zugewiesen, Funktion/term wird dann auf diese Variablen angewendet

For formulas: $\mathcal{A}(P_i^{(k)}(t_1,\dots ,t_k))=\psi (P_i^{(k)})(\mathcal{A}(t_1),\dots ,\mathcal{A}(t_k))$

def 6.16

• $\mathcal{A}(F\wedge G)=1:⟺\mathcal{A}(F)=1$ und $\mathcal{A}(G)=1$
• $\mathcal{A}(F\vee G)=1:⟺\mathcal{A}(F)=1$ or $\mathcal{A}(G)=1$
• $\mathcal{A}(\mathrm{\neg }F)=1:⟺\mathcal{A}(F)=0$
• $\mathcal{A}(\mathrm{\forall }xF):⟺\{\begin{array}{ll}1& if{\mathcal{A}}_{[x\to u]}(F)=1\text{for all }u\in U^{\mathcal{A}}\\ 0& \text{else}\end{array}$
• $$\begin{gathered} \mathcal{A}( \\ existsxF):⟺\{\begin{array}{ll}1& if{\mathcal{A}}_{[x\to u]}(F)=1\text{for some }u\in U^{\mathcal{A}}\\ 0& \text{else}\end{array} \end{gathered}$$

where ${\mathcal{A}}_{[x\to u]}$ is the interpretation that is equal to $\mathcal{A}$ except that $x^{{\mathcal{A}}_{[x\to u]}}=u$

Bsp
einfache Prüfungsaufgabe
Find a model for $\mathrm{\forall }x(P(f(x),y))$

1. freien Symbole: $P,f,y$ -> mindestens sie müssen definiert werden
2. Universum wählen

Bsp (nicht eindeutig)