Show Menu
Cheatography
  1. Home >
  2. Cheat Sheets >

Prädikatenlogik Theorie Cheat Sheet by

Logische Äquivalenz

Definition 2.7 [Logische Äquiva­lenz]
Zwei Formeln φ, ψ ∈ FO(S) heißen (logisch) äquiva­lent, gdw. für alle S-Inte­rpr­eta­tionen J gilt: J |= φ gdw. J |=ψ. In Symbolen: φ≡ψ.
Bem.: Logische Äquiva­lenzen der AL übertragen sich auf FO. Hinzu treten charak­ter­ist­ische logische Äquiva­lenzen im Zusamm­enhang mit Quantoren.

Z.B. die Dualität zwischen ∀ und ∃, die besagt dass für alle φ ∈ FO(S):

∃xφ ≡ ¬∀x¬φ,
∀xφ ≡ ¬∃x¬φ.

Erfüll­bar­kei­tsä­qui­valenz

Definition 2.10 Erfüll­bar­kei­tsä­qui­valenz
Formeln φ,φ′ heißen erfülb­ark­eit­säq­uiv­alent wenn gilt: φ erfüllbar gdw. φ′ erfülbar. Analog wird Erfüll­bar­kei­tsä­qui­valenz für Formel­mengen definiert.

Signaturen

Eine Signatur S ist eine Menge von Konsta­nten-, Funktions- und Relati­ons­sym­bolen, mit angege­benen Stelli­gke­iten. Spezialfa ̈lle: S ohne Funkti­ons­symbole : relati­onale Signatur; S ohne Relati­ons­symbole : funkti­onale Signatur.

S-Stru­kturen

Definition 1.1 [S-Str­ukt­uren]
Für Signatur S: Eine S-Struktur A = (A,cA,...,fA,...,RA,...) besteht aus ihrer Träger­menge A ≠ ∅ zusammen mit einer Interp­ret­ation der Symbole in S, d.h., für jedes Konsta­nte­nsymbol c ∈ S: ein ausgez­eic­hnetes Element cA ∈ A. für jedes n-stellige Funkti­ons­symbol f ∈ S: eine n-stellige Funktion fA : An→ A. für jedes n-stellige Relati­ons­symbol R ∈ S: eine n-stellige Relation RA ⊆ An.

S-Terme

Definition 1.3 [S-Terme] Die Menge der S-Terme, T(S) (mit Variab­len­menge V) ist induktiv erzeugt wie folgt:
• x∈T(S) für jede Variable x ∈ V.
• c ∈ T(S) für jedes Konsta­nte­nsymbol c ∈ S.
• ist f ∈ S ein n-stel­liges Funkti­ons­symbol, und sind t
1
, . . . , t
n
∈ T (S), so ist auch ft
1
...t
n
∈T(S).

T
n
(S) ⊆ T(S): die Mengen der Terme, in denen nur Variab­len­symbole aus V
n
= {x
1
, . . . , x
n
} vorkommen.

Speziell steht T
0
(S) für die Menge der Variab­len­-freien Terme (= ∅ wenn S keine Konstanten hat).

Allgem­ein­gül­tigkeit

Definition 2.6 [Allge­mei­ngü­lti­gkeit]
Eine Formel φ ∈ FO(S) heißt allgem­ein­gültig gdw. für alle S-Inte­rpr­eta­tionen J gilt: J |= φ.
 

Folger­ung­sbe­ziehung

Definition 2.5 [Folger­ung­sbe­ziehung]
φ |= ψ bzw. Φ |= ψ.
Für φ,ψ ∈ FO(S):
ψ ist eine logische Folgerung von φ, oder ψ folgt aus φ, in Symbolen φ |= ψ, gdw. für alle S-Inte­rpr­eta­tionen J gilt: J |= φ ⇒ J |= ψ.

Entspr­echend ist Φ |= ψ für Formel­mengen Φ definiert (ψ folgt aus Φ).

FO mit und ohne Gleichheit

Definition 2.11 [FO ohne Gleich­heit]
FO≠(S) ⊆ FO(S) ist aufgebaut wie FO aber ohne Termgl­eic­hheiten als atomare Formeln. Die Semantik von FO überträgt sich auf die Teillogik FO≠.
Bemerkung 2.13 Zu jeder Formel­menge Φ ⊆ FO(S) erhält man durch eine system­atische Überse­tzung in eine explizite Modell­ierung der Gleich­hei­tsr­elation durch eine neues Relati­ons­sysmbol ∼ eine erfülb­ark­eit­säq­uiv­alente Formel­menge Φ
∼
⊆ F0≠(S ∪ {∼}).

Termst­ruktur

Defintion 1.4 Termst­ruk­turen
Die Menge der S-Terme ist Träger einer S
F
-Struktur T = T (S), der Termst­ruktur (Herbra­nd-­Str­uktur) zu S, mit der folgenden natürl­ichen Interp­ret­ation der Konsta­nten- und Funkti­ons­symbole in S:
• für Konsta­nte­nsymbol c ∈ S:
cT := c ∈ T(S).
• für n-stel­liges Funkti­ons­symbol f ∈ S: f T: T(S)n → T(S)
(t
1
,...,t
n
) → ft
1
...t
n
.
Wenn S Konsta­nte­nsy­mbole hat, ist auch T
0
(S) Träger einer entspr­ech­enden Termst­ruktur T
0
(S) (eine Substr­uktur von T (S)).

Pränexe Normalform

Definition 3.1 [pränexe NF] FO-Formeln in pränexer Normalform sind von der Form Q
1
x
i
1
...Q
k
x
ik
ψ, wo k ∈ N, Q
i
∈ {∀, ∃} und ψ quanto­ren­frei. ψ heißt auch quanto­ren­freier Kern der Formel, Q
1
x
i1
. . . Q
k
x
i
k
ihr Quanto­ren­präfix.
Man braucht i.d.R. zusätz­liche Variab­len­sym­bole!
Satz 3.4 Jede FO-Formel ist äquivalent zu einer Formel in pränexer NF.
Beispiel 3.2 S = {E}, E 2-st. Relati­ons­-Sy­mbol. Die folgenden Äquiva­lenzen liefern auf der rechten Seite pränexe Formal­isi­eru­ngen:
∃y(Exy ∧ ∀x(Eyx → x = y)) ≡ ∃y∀z Exy ∧ (Eyz → z = y) ,
∃y∀xExy ∨ ¬∃yExy ≡ ∃y1∀y2∀y3 Ey2y1 ∨ ¬Exy3 .
  

Belegungen

Definition 1.5
[Beleg­ungen und Interp­ret­ati­onen]
Eine Funktion β: V → A heißt Belegung (für die x ∈ V) in der S-Struktur A = (A,...). Eine S-Struktur A und Belegung β zusammen bilden eine S-Inte­rpr­etation J = (A, β).

•Für t = x (x ∈ V Variable):
tJ:=β(x).
• Für t = c (c ∈ S Konsta­nte­nsymbol):
tJ:= cA.
• Für t = ft
1
...t
n
, mit n-stel­ligem Funkti­ons­symbol f ∈ S:
tJ := fA (t
1
J,...,t
n
J ).
Schrei­bweisen für Belegungen und Interp­ret­ationen auf Seite 6 FO Skript über Kapitel 2

Freie Variablen

Definition 2.2 [freie Variablen]
Induktive Definition der Menge der freien Variablen, frei(φ) ⊆ V, für φ ∈ FO(S):
Formeln ohne freie Variablen heißen Sätze.
Schrei­bwe­isen: FO
n
(S) := {φ ∈ FO(S): frei(φ) ⊆ V
n
}. Für φ ∈ FO
n
(S) schreiben wir auch φ = φ(x
1
, . . . , x 
n
) um die möglic­her­weise freien Variablen explizit anzude­uten.
frei(t
1
= t
2
) := var(t
1
) ∪ var(t
2
).
frei(Rt
1
. . . t 
n
) := var(t
1
) ∪ . . . ∪ var(t 
n
).
frei(¬φ) := frei(φ).
frei(φ ∧ ψ) = frei(φ ∨ ψ) := frei(φ) ∪ frei(ψ).
frei(∃xφ) = frei(∀xφ) := frei(φ) \ {x}.

Quanto­renrang

Definition 2.3 [Quant­ore­nrang]
Induktive Definition des Quanto­ren­rangs, qr(φ) ∈ N, für φ ∈ FO(S):
Formeln von Quanto­renrang 0 heißen quanto­ren­frei.
qr(φ) = 0 für atomares φ.
qr(¬φ) := qr(φ).
qr(φ ∧ ψ) = qr(φ ∨ ψ) := max(qr(φ), qr(ψ)).
qr(∃xφ) = qr(∀xφ) := qr(φ) + 1.

Semantik

Definition 2.4 [Semantik]
Für S-Inte­rpr­etation J = (A, β) und φ ∈ FO(S): J erfüllt φ gdw. φ J = 1. Schrei­bweise: J|= φ.
Für Formel­mengen Φ ⊆ AL(V) entspr­echend: J|= Φ gdw. J |= φ für alle φ ∈ Φ.
Die Relation |= heißt Modell­bez­iehung.

Herbrand

Satz 3.10 (Herbrand)
Sei Φ ⊆ FO
0
≠ (S) eine Menge von univer­sellen, gleich­hei­tsf­reien Sätzen. Dann sind äquiva­lent:
(i) Φ erfüllbar.
(ii) Φ hat ein Herbra­nd-­Modell H = ( T
0
(S), (RH)
R
∈
S
) |= Φ, dessen Träger­menge und Funktions- und Konsta­nte­nin­ter­pre­tat­ionen mit der Termst­ruktur T
0
(S) überei­nst­immen (H erweitert die S
F
-Struktur T
0
(S) lediglich um eine geeignete Interp­ret­ation der Relati­ons­symbole in S).
Definition 3.8 Eine Formel ist universell wenn sie aus atomaren und negiert atomaren Formeln allein mittels ∧, ∨ und ∀-Quan­toren aufgebaut ist.
Lemma 3.12 Sei Φ ⊆ FO
0
≠ (S) eine Menge von univer­sel­l-p­ränexen Sätzen. Dann sind äquiva­lent:
(i) Φ erfüllbar. (ii) [[Φ]]AL erfüllbar.
 

Erfülb­arkeit

• Φ ⊆ FO
0
(S) eine Satzmenge (ohne freie Variablen) ist. Man erhält eine zu einer Formel­menge erfüll­bar­kei­tsä­qui­valente Satzmenge, indem man neue Konsta­nte­nsy­mbole für alle freien Variablen substi­tuiert
• Φ ⊆ FO
0
≠ (S) gleich­hei­tsfrei ist. Eine explizite Modell­ierung der Gleich­hei­tsr­elation durch eine zusätz­liche Äquiva­len­zre­lation (siehe Bemerkung 2.13) führt zu erfüll­bar­kei­tsä­qui­val­enten Satzmengen ohne Gleich­heit.
• Φ ⊆ FO
0
≠ (S) aus univer­sel­l-p­rän­exen, gleich­hei­tsf­reien Sätzen besteht. Skolem­isi­erung liefert eine erfüll­bar­kei­tsä­qui­valente Satzmenge in univer­sel­l-p­ränexer Form.
• S mindestens ein Konsta­nte­nsymbol enthält, sodass T
0
(S) ≠ ∅ ist, und wir uns ggf. auf Herbra­nd-­Modelle von Φ ⊆ FO
0
≠ (S) zurück­ziehen können.
Φ erfüllbar ⇔ H |= Φ für eine
Herbra­nd-­Str­uktur H = T
0
(S),(RH)
R
∈
S
.

Kompak­the­itssatz (FO)

Satz 4.1 (Kompa­kth­eit­ssatz) Für jede Formel­menge Φ ⊆ FO sind äquiva­lent:
(i) Φ erfüllbar. (ii) Jede endliche Teilemenge Φ
0
⊆ Φ ist erfüllbar.
Korollar 4.2 Für jede Formel­menge Φ ⊆ FO und Formel ψ ∈ FO sind äquiva­lent:
(i) Φ |= ψ. (ii) Es existiert eine endliche Teilemenge Φ
0
⊆ Φ, sodass Φ
0
|= ψ.
Das Korollar folgt aus dem Satz über den Zusamm­enhang: Φ|=φ gdw. Φ ∪ {¬φ} unerfü­llbar.
 

Metadata

Comments

No comments yet. Add yours below!

Add a Comment

Your Comment

Please enter your name.

    Please enter your email address

      Please enter your Comment.

          More Cheat Sheets by tiziano123