Show Menu
Cheatography

Prädikatenlogik Theorie Cheat Sheet by

Logische Äquivalenz

Defi­nition 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

Defi­nition 2.10 Erfüll­bar­kei­tsä­qui­val­enz
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

Defi­nition 1.1 [S-Str­ukt­uren]
Für Signatur S: Eine S-Struktur A = (A,c,...,­f,...,­R,...) 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

Defi­nition 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 t1, . . . , tn ∈ T (S), so ist auch ft1...tn ∈T(S).

Tn(S) ⊆ T(S): die Mengen der Terme, in denen nur Variab­len­symbole aus Vn = {x1, . . . , xn} vorkommen.

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

Allgem­ein­gül­tigkeit

Defi­nition 2.6 [Allge­mei­ngü­lti­gke­it]
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

Defi­nition 2.5 [Fol­ger­ung­sbe­zie­hung]
φ |= ψ 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

Defi­nition 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.
Beme­rkung 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

Defi­ntion 1.4 Termst­ruk­turen
Die Menge der S-Terme ist Träger einer SF-S­truktur T = T (S), der Termst­ruktur (Her­bra­nd-­Str­ukt­ur) 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)
(t1,...,­tn) → ft1 ...tn.
Wenn S Konsta­nte­nsy­mbole hat, ist auch T0(S) Träger einer entspr­ech­enden Termst­ruktur T0(S) (eine Substr­uktur von T (S)).

Pränexe Normalform

Defi­nition 3.1 [pränexe NF] FO-F­ormeln in pränexer Normalform sind von der Form Q1x­i1 ...Qxik ψ, wo k ∈ N, Qi ∈ {∀, ∃} und ψ quan­tor­enf­rei. ψ heißt auch quanto­ren­freier Kern der Formel, Q1xi1 . . . Qk xik 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

Defi­nition 1.5
[Bel­egungen 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 Variab­le):
tJ:=­β(x).
• Für t = c (c ∈ S Konsta­nte­nsy­mbo­l):
tJ:= cA.
• Für t = ft1 ...tn, mit n-stel­ligem Funkti­ons­symbol f ∈ S:
tJ := fA (t1­J,...,­t­nJ ).
Schrei­bweisen für Belegungen und Interp­ret­ationen auf Seite 6 FO Skript über Kapitel 2

Freie Variablen

Defi­nition 2.2 [freie Variab­len]
Induktive Definition der Menge der freien Variablen, frei(φ) ⊆ V, für φ ∈ FO(S):
Formeln ohne freie Variablen heißen Sätze.
Schr­eib­weisen: FOn(S) := {φ ∈ FO(S): frei(φ) ⊆ Vn}. Für φ ∈ FOn(S) schreiben wir auch φ = φ(x1, . . . , x n) um die möglic­her­weise freien Variablen explizit anzude­uten.
frei(t1 = t2) := var(t1) ∪ var(t2).
frei(Rt1 . . . t n) := var(t1) ∪ . . . ∪ var(t n).
frei(¬φ) := frei(φ).
frei(φ ∧ ψ) = frei(φ ∨ ψ) := frei(φ) ∪ frei(ψ).
frei(∃xφ) = frei(∀xφ) := frei(φ) \ {x}.

Quanto­renrang

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

Semantik

Defi­nition 2.4 [Seman­tik]
Für S-Inte­rpr­etation J = (A, β) und φ ∈ FO(S): J erfüllt φ gdw. φ J = 1. Schr­eib­weise: 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 (Herbr­and)
Sei Φ ⊆ FO0≠ (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 = ( T0(S), (RHR­∈S) |= Φ, dessen Träger­menge und Funktions- und Konsta­nte­nin­ter­pre­tat­ionen mit der Termst­ruktur T0(S) überei­nst­immen (H erweitert die SF-S­truktur T0(S) lediglich um eine geeignete Interp­ret­ation der Relati­ons­symbole in S).
Defi­nition 3.8 Eine Formel ist univ­ers­ell wenn sie aus atomaren und negiert atomaren Formeln allein mittels ∧, ∨ und ∀-Quan­toren aufgebaut ist.
Lemma 3.12 Sei Φ ⊆ FO0≠ (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

• Φ ⊆ FO0(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
• Φ ⊆ FO0≠ (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.
• Φ ⊆ FO0≠ (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 T0(S) ≠ ∅ ist, und wir uns ggf. auf Herbra­nd-­Modelle von Φ ⊆ FO0≠ (S) zurück­ziehen können.
Φ erfüllbar ⇔ H |= Φ für eine
Herbra­nd-­Str­uktur H = T0(S­),(­R)­RS .

Kompak­the­itssatz (FO)

Satz 4.1 (Kompa­kth­eit­ssa­tz) 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ü­llb­ar.

Help Us Go Positive!

We offset our carbon usage with Ecologi. Click the link below to help us!

We offset our carbon footprint via Ecologi
 

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