Database Reference
In-Depth Information
3. Die Menge der erfullbaren PL1-Formeln ist unentscheidbar. (Dies folgt analog
zu der Uberlegung unter 2., da die Komplementarmenge der unerfullbaren
Formeln unentscheidbar ist.)
Als positive Ergebnisse haben wir:
•
Die Menge der allgemeingultigen PL1-Formeln ist semi-entscheidbar (rekursiv
aufzahlbar).
•
Die Menge der unerfullbaren PL1-Formeln ist semi-entscheidbar.
Fur die jeweils komplementaren Formelmengen gilt dies aber nicht:
•
Die Menge der falsifizierbaren PL1-Formeln ist nicht rekursiv aufzahlbar.
•
Die Menge der erfullbaren PL1-Formeln ist nicht rekursiv aufzahlbar.
Da wir das Problem der semantischen Folgerung auf das Gultigkeitsproblem
oder auch auf das Unerfullbarkeitsproblem zuruckfuhren konnen, bedeutet dies, dass
die Frage, ob in der Pradikatenlogik 1. Stufe eine semantische Folgerung
F
|
= G
gilt, nur semi-entscheidbar, aber nicht entscheidbar ist.
3.4
Logische Grundlagen: Aussagenlogik
In diesem Abschnitt wollen wir die Grundlagen der klassischen Aussagenlogik kurz
zusammenfassen, wobei wir die Terminologie benutzen, wie wir sie fur allgemeine
logische Systeme eingefuhrt haben.
3.4.1
Syntax
Definition 3.22 (Aussagenlogische Signatur)
Eine
aussagenlogische Signatur
Σ ist eine Menge von Bezeichnern, genannt
Aussagenvariablen
.
Definition 3.23 (Aussagenlogische Formeln)
Fur eine aussagenlogische Si-
gnatur Σ wird die Menge
Formel
(Σ) der aussagenlogischen Formeln wie folgt gebil-
det:
1. Eine
atomare Formel
ist eine aussagenlogische Formel, die nur aus einer Aus-
sagenvariablen besteht.
2. Falls A und B aussagenlogische Formeln sind, dann sind auch die folgenden
Konstrukte aussagenlogische Formeln, wobei die darin auftretenden Operati-
onssymbole ¬, ∧ etc.
Junktoren
heißen:
(
¬
A)
Negation
“nicht A”
(A
∧
B)
Konjunktion
“A und B”
(A
∨
B)
Disjunktion
“A oder B”
(A
⇒
B)
Implikation
“wenn A,dannB”
Koimplikation, Aquivalenz
(A
⇔
B)
“A genau dann, wenn B”
