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:
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: √, ∤, |, ≥, ≤, ∑, ⊕, ≠, , ○, ⚡, Σ, π, ✓, ∞, ρ
≡, ∈, ∉, ∀, ∃, ∅, ⋂, ⋃, ∪, ⊂, ⊃, ⊆, ⊇, ⋀, ⋁, ¬, ≈
⇒, ⇔, ⟼, ↤, ☇, →, ↔, ↓, /,\
Ā, Ē, Ū, Ō, Ω,  ɸ, ω, τ, ℕ, ℤ, α, β, γ, δ, ε, ⌈,⌉, ⌊,⌋