Algebraische Strukturen und Prädikatenlogik
Def: Eine Gruppe besteht aus einer Trägemenge G und einer binären Operation *: GxG->G
(G1) ∀a€G ∀b€G ∀c€G (a*b)*c=a*(b*c) Assoziativgesetz
(G2) ∃e€G ∀a€G a*e =a =e*a e ist neutrales Element
(G3) ∀a€G ∃!a€G a*a! =e =a!*a a! ist das zu a inverse Element
Wenn zusätzlich ∀a,b€G a*b=b*a, dann spricht man von einer Kommutativen (abelschen) Gruppe
Nur (G1) -> Halbgruppe
Nur (G1) und (G2) -> Monoid
Beispiele: (ℕ,+), (ℕ,*) sind Monoide
(ℤ,+) ist Gruppe
(ℤ,*) ist Monoid
((Q,+), (|R,+) sind Gruppen
((Q\{0},*),(|R\{0},*) sind Gruppen
(|B, ^) ist ein Monoid mit e = 1
(|B,⊕) ist Gruppe mit e =0
ℤ_d={0,1,...,d-1} +_d ist Addition modulo d
ist Gruppe e=0 a!={d-a falls a≠0; 0 sonst
Schlussfolgerung aus den Gruppenaxiomen
in jeder Gruppe ist das neutrale Element eindeutig
Beweis: Angenommen e und e' erfüllen (G2)
zu zeigen e=e'
Betrachte e*e'= e' (G2) für e
e*e' =e (G2) für e'
In einer Gruppe ist für jedes a €G das inverse Element eindeutig
Beweis: Angenommen a! und a~ erfüllen (G3) für a
zu zeigen a!=a~
Betrachte a! * (a*a~)=a!*e |(G3) für a~
=a! |(G2)
a! *(a*a~)=(a!*a)*a~ |(G1)
=e*a~ |(G3) für a!
=a~
a~=a! => Eindeutigkeit
In Gruppen kann man rechts- und linksseitig kürzen, d.h.
a*c=b*c =>a=b
a*b=a*c => b=c
Beweis:
sei a*c=b*c |*c!
(a*c)*c!=(b*c)*c! |(G1)
a*(c*c!)=b*(c*c!) |(G3)
a*e=b*e |(G2)
a=b
Verbände
Ein Verband ist eine Halbordnung , so dass jede endliche Teilmenge ein Supremum und ein Infinum besitzt
Beschreibung mit Mitteln der Prädikatenlogik
Ein Verband besteht aus einer Trägermenge L mit einer Relation ≤ ⊆LxL und eine binäre Funktion inf, sup: LxL->L und den folgenden Eigenschaften:
(L1) ∀x€L x<=x
(L2)∀x,y,z€L x<=< ^ y<=z ->x<=z
(L3) ∀ x,y€L x<=y ^ y <=x -> x=y
(L4) ∀x,y€L (x<=sup(x,y)) ^(y<=sup(x,y)) ^ ∀z(x<=z y<=z -> sup(x,y)<=z))
(L5) ∀x,y€L (inf(x,y) <= x ^ inf(x,y) <= y)^ ∀z(z<=x ^ z<= y -> z<= inf(x,y)))
12.02.2013
Klausur: 21.02.
Ort: in der Arnimallee 22 im Großen Hörsaal und Hörsaal A
Hilfsmittel: 1 Seite (einseitig, min Schriftgröße 10), keine Taschenrechner
für alle Erstbeleger: wenn Prüfung bestanden und Freiversuch=E-Mail an Kriegel schreiben
Attest bei Nichtbesuch, sonst 5,0
Elementare Sprachen
Alphabet einer elementaren Sprache besteht aus:
- Variablenmenge Var={x1,x2,3,....} und x, y, z für beliebige Vertreter aus Var
- Menge von logischen Symbolen: ¬, ⋀, ⋁, ∀, ∃ und das Zeichen = für die Identische Relation in der Struktur
- nichtlogische Signatur besteht aus
- Konstantensymbole: a, b, c
- Funktionssymbole: f, g, h
- Prädikatsymbole: P, R
- wobei jedes Funktionssymbol f die Gestalt f[k;i], mit i Index zur Nummerierung und k Stelligkeit der Funktion
- (insb k=2 ->binäre Operation
- k=0 -> Konstantensymbol)
- und jedes Prädikatsymbol hat die Form P[k;i], wobei i zur Nummerierung dient und k die Stelligkeit beschreibt (k=2 ->binäre Relation)
Syntax
1) Terme (induktive Definition)
jede Variable und jedes Konstantensymbol ist ein Term (Primterm)
Ist f=f[k;i] ein Funktionssymbol und t_1,....,t_k Terme, dann ist auch f(t_1,....,t_k) ein Term
Es gelten die Sätze und der eir eindeutigen Dastellung und die Terminduktion (strukturelle Induktion):
Wenn f(t_1,...,t_k)=g(s_1,....,s_m) => f=g und k=m und t_1=s_1 und... und t_k=s_m
Gilt eine Aussage für alle Primterm und folgt aus der Gültigkeit der Aussage für t_1,t_2,...,t_k auch die Gültigkeit für f(t_1,....,t_k), dann gilt die Aussage für alle Terme
2) Formeln (Induktive Definition)
Sind t1 und t2 Terme dann ist t1=t2 eine Formel
Ist P=P[k;i] ein Prädikatssymbol und t_1,....,t_k Terme, dann ist P(t_1,....,t_k) eine Formel
Sind F und G Formeln, dann sind auch ¬F, F ^ G, sowie F v G Formeln
(weitere Definitionen, z.B. F->G für (¬F v G))
Ist F Formel und x€Var, dann sind auch ∀x F und ∃x F Formeln
Sprachen der 1. Stufe (= elementare Sprachen) erlauben nur Quantifizierung über Variablen. Quantifizierung über Teilmengen oder Funktionen führt zu Sprachen der 2. Stufe.
freie und gebundene Variablen
Für Terme werden Subterme und Variablen definiert:
Ist x€Var, dann St(x)={x} var(x)={x}
Ist a Konstantensymbol St(a)={a} var(a)=∅
Ist f=f[k,i] Funktionssymbol und t_1,....,t_k Terme, dann gilt St(f(t_1,....,t_k))=St(t_1) u St(t_2) u .... u St(t_k) u {f(t_1,....,t_k)} var (f(t_1,....,t_k))=var(t_1) u ... u var(t_k)
Variable und freie Variable in Formeln
Sind t1 und t2 Terme, dann ist var(t1=t2)=frei(t1=t2)=var(t1) u var(t2)
Ist P=P[k,i] Prädikatssymbol und t_1,....,t_k Terme, dann ist var(P(t_1,....,t_k))= var(t1) u .... u var(t_k)
Sind F und G Formeln, dann gilt
var(¬F)=var(F)
frei(¬F)=frei(F)
var(F ^ G)=var(F v G)=var(F) u var(G)
frei(F ^ G)=frei(F v G)=frei(F) u frei(G)
Ist F Formel und x€Var, dann ist
var(∀x F)=var(∃xF)=var(F)
frei(∀x F)=frei(∃x F)=(var(F))\{x}
Formeln ohne freie Variable werden Aussagen genannt
Beispiele:
1) Gruppenaxiome: Funktionssymbol f=f[2;1] für Operation *(siehe Oben)
(G1) ∀x ∀y ∀z f(f(x,y),z)=f(x(f(y,z)))
(G2) ∃e ∀x (f(e,x)=x ^ f(x,e)=x)
(G3) ∀x ∃y (f(x,y)=e ^ f(y,x)=e)
besser: e Konstantensymbol und g=f[1;2] für das inverse Element
(G1) wie vorher
(G2) ∀x(f(x,e)=x ^ f(e,x)=x)
(G3) ∀x(f(x,g(x))=e ^ f(g(x),x)=e)
2)∀x x=f(x,x) und ∀x ∀y x=y sowie ¬∀y ∀x f(x,y)=f(y,x) sind Aussagen, dh. frei()=∅
3) frei((∀x ¬x=a) ^ ∀y y=f(x,z))={x,z}
frei(∀x (¬x=a ^ ∀y y=f(x,z)))={z}
Regeln für Klammersetzung:
= hat größte Bindungstärke
gefolgt von∀, ∃
gefolgt von ¬, ⋀, ⋁
Quantorenfolgen werden rechtssassoziativ geklammert
∀x ∃y x=z v ∀z ¬x=f(y,z)
(∀x (∃y (x=z))) v (∀z (¬(x=f(y,z))))
14.02.2013
L: nichtlogische Signatur
L={a, b,....,f, g,...., P, R,....} |Konstantensymbole, Funktionssymbole, Prädikatsymbole
L-Terme
x_1,x_2,.... ,a,b
f(t_1,....,t_k) wenn f = f[k;i]
L-Formeln
t_1=t_2
P(t_1,....,t_k) wenn P=P[k;i]
¬F, F ⋀ G, F ⋁ G
∀xF, ∃xF
Semantik
Def: eine L-Struktur A besteht aus einer Menge A und Realisierung für die Symbole aus L, d.h. c^A € A für alle Konstantensymbole c aus L
f^A: Ax... A -> für alle Funktionssymbole f=f[k,i]
k-mal
P^A: Ax...xA -> |B |B={0,1}
für alle P=P[k;i] aus L
Def: Ein L-Modell besteht aus einer L-Struktur A und einer Variablenbelegung ω:Var->A
kurz M=(A,ω)
Auswertung von Termen für ein Modell M
M=(A,ω)
M(x_i)=ω(x_i)
M(a)=a^A
t=f(t_1,...,t_k)
M(t)=f^A (M(t_1),....,M(t_k))
Auswertung von Formeln:
M(t_1=t_2)={1 falls M(t_1)=M(t_2) in A; 0 sonst
M(P(t_1,...,t_k))=P^A (M(t_1),....,M(t_k))
M(!F)=!(M(F))
M(F ^ G)=M(F) ^ M(G)
M(F v G)=M(F) v M(G)
Was ist mit ∀x F, ∃x F?
Sei M_[x/d] das Modell, das mit M übereinstimmt bis auf ω(x), wo nun ω(x)=d gesetzt wird
M(∀x F)= {1 falls M_[x/d] (F)=1 für alle d€A; 0 sonst
M(∃x F)= {1 falls M_[x/d] (F)=1 für ein d€A; 1 sonst
Achtung: Ersetzung x/d betrifft nur die freien Variablen von x
Beispiel: F=∀x (x=a v ∀x !(x=a))
Struktur: A=ℤ a^A=5
Modell: ω(x)=4 Was ist M(F)?
F=∀x G wobei G=∀x (x=a v ∀x !(x=a)) |H=(x=a) J=∀x (!x=a)
M(J)=0 weil M_[x/5](J)=0
M(H)=0
M(G)=0v0=0
M(F)=0 weil M_[x/4] (G)=0 |=M
Notationen
F,G L-Formeln, X L-Formelmenge
A L-Struktur, M L-Modell
F ist gültig in M oder M erfüllt F, wenn M(F)=1 Notation M |= F
F und G sind logisch äquivalent, wenn M |= F genau dann, wenn M |= G für alle L-Modelle M
M erfüllt die Formelmenge X, wenn M |= F für alle F€X
F bzw. X sind erfüllbar, wenn es ein erfüllendes Modell M für F bzw. X
F gilt in A, wenn (A,ω)(F)=1 für alle Belegungen ω:Var -> A
F folgt aus X, wenn für alle Modelle M mit M |= X, dass M |= F
Kann man entscheiden, ob eine L-Formel erfüllbar ist, d.h. ob ein Modell M existiert, so dass M |= F?
Antwort: Nein, algorithmisch nicht entscheidbar
(aber semientscheidbar)
Weg über Standardformen
Normalformen
Satz: Für beliebige Formeln F,G gilt:
(1) !∀x F =∃x !F !∃x F=∀x !F
(2) ∀x F ^ ∀x G=∀x (F ^ G) ∃x F v ∃x G= ∃x(F v G)
(3) ∀x ∀y F= ∀y ∀x F ∃x ∃y=∃y ∃x F
Ist G formel mit x∉ Frei(G), dann
(4) ∀xF ^ F =∀x (F ^ G) ∀x F v G = ∀x(F v G)
(5) ∃x F ^ G= ∃x (F ^ G) ∃x F v G= ∀x(FvG)
Substitution
Def: F eine Formel, x€Var, t ein Term, dann bezeichnet F[x/t] die aus F entstehende Formel, wenn jedes freie Auftreten von x durch t ersetzt wird.
Anwendungen:
F=G => F[x/t]=G[x/t] für beliebige x,t
ist F=∀x G oder F'=∃x G und y eine Variable, die nicht in G vorkommt, dann gilt F=∀y G[x/y] bzw F'=∃y G[x/y]
->gebundene Umbenennung
Durch wiederholte Anwendung der gebundenen Umbenennung, kann jede Formel F umgewandelt werden in eine Formel G, in der alle Quantoren verschiedenen Variablen haben und keine Variable frei und gebunden vorkommt -> bereinigte Form
Def: F ist in Prämexform, wenn F die folgende Gestallt hat
F=Q_1 x1 Q_2 x2 Q3_3 x3.....Q_k x_k G
wobei Q_1,...Q_k€{∀, ∃} und G quantorenfrei ist
BPF=Bereinigt Prämexform
Satz: Jede Formel F kann äquivalent in BPF umgewandelt werden.
Beweis mit Induktion über Formelaufbau
IA: Primformeln t_1=t_2 oder P(t_1,....,t_k)
sind in BPF
IS:
F hat die Form !F_1 und F_1 in BPF
F=!(Q_1 x_1....Q_k x_k G)
F=!Q_1 x_1 ....!Q_k x_k !G nach (1) |!∀->∃, !∃->∀
F=F_1 ^ F_2 (analog F_1 v F_2)
und F_1, F_2 in BPF
F_1=Q_1 x_1.....Q_1 x_k G1
F_2=Q'_1 x'_1 ....Q'_m x'_m G2
Umbenennung in F_2, so dass Variablenmengen disjunkt sind Q'_1 y_1....Q'_m y_m G2[x'_1/y_1....x'_m/y_m]
F=Q_1 x_1 ..... Q_k x_k Q'_1 y_1 ..... Q'_m y_m(G1 ^ G2)'
F=∀x G und G in BPF
Umbenennung in G falls dort Qx auftaucht
danach F=∀x G' ist in BPF
Def: Eine Formel F in BPF ist eine Skolemformel (in Skolem-Form), wenn in F keine Existenzquantoren vorkommen
Eleminierung durch folgende Methode:
Betrachte F von links nach rechts bis zum ersten ∃-Quantor
∀x_1 ∀x_2 ....∀x_k ∃x_(k+1) G wobei k=0 sen kann
führe in L ein neues Funktionssymbol f ein, das k-stellig ist
Ersetze F durch ∀x_1 ∀x_2 ....∀x_k G[x_(k+1)/f(x_1,....,x_k)]
Wiederhole das bis alle ∃-Quantoren eliminiert sind
Sonderzeichen: √, ∤, |, ≥, ≤, ∑, ⊕, ≠, , ○, ⚡, Σ, π, ✓, ∞, ρ
≡, ∈, ∉, ∀, ∃, ∅, ⋂, ⋃, ∪, ⊂, ⊃, ⊆, ⊇, ⋀, ⋁, ¬, ≈
⇒, ⇔, ⟼, ↤, ☇, →, ↔, ↓, /,\
Ā, Ē, Ū, Ō, Ω, ɸ, ω, τ, ℕ, ℤ, α, β, γ, δ, ε, ⌈,⌉, ⌊,⌋