Database Reference
In-Depth Information
3.3.6
Entscheidbarkeitsresultate
Mit den Begriffen der Korrektheit und Vollstandigkeit haben wir die wichtigste
Charakterisierung von Kalkulen festgelegt. Eine ganz andere Frage ist, ob es zu
einer gegebenen Logik uberhaupt Kalkule mit diesen Eigenschaften gibt. Dies hangt
naturlich von der Art der Logik ab. Ob es etwa einen Algorithmus gibt, der die Frage
nach der Erfullbarkeit oder Gultigkeit von Formeln einer Logik beantwortet, hangt
davon ab, ob diese Fragestellung fur die gegebene Logik uberhaupt entscheidbar ist.
Fur eine beliebige Menge M gilt:
M
ist
entscheidbar
gdw.
es gibt einen Algorithmus, der fur jedes x an-
gibt, ob x
∈
M oder x/
∈
M gilt.
M
ist
unentscheidbar
gdw.
M ist nicht entscheidbar.
M
ist
semi-entscheidbar
(
rekursiv aufzahlbar
)
gdw.
es gibt einen Algorithmus, der fur jedes x aus
der Menge M angibt, dass x
M gilt. (Insbe-
sondere muss der Algorithmus fur ein x nicht
aus M nicht unbedingt terminieren!)
Dabei bedeutet “Algorithmus” z.B. Turing-Maschine, Markov-Algorithmus etc.
∈
Ist F eine Formel in einer gegebenen Logik, so interessiert man sich in er-
ster Linie fur ihre Zugehorigkeit zu einer der in Abbildung 3.3 skizzierten Mengen.
Die Aussagenlogik (also der Spezialfall von PL1, in der keine Funktionssymbole,
keine Quantoren und keine Individuenvariablen und damit nur null-stellige Pradi-
katensymbole auftreten) ist entscheidbar. D.h. es gibt Algorithmen, die fur jede
aussagenlogische Formel entscheiden, ob sie allgemeingultig, erfullbar, falsifizierbar
oder unerfullbar ist. Beispielsweise lassen sich diese Fragen mit der Methode der
Wahrheitstafeln (s. Abschnitt 3.4.4) beantworten.
Das Allgemeingultigkeitsproblem der Pradikatenlogik 1. Stufe ist allerdings un-
entscheidbar; d.h. die Menge der allgemeingultigen PL1-Formeln ist nicht entscheid-
bar. Damit reißt die Kette der negativen Resultate zunachst nicht ab, denn auch die
anderen in Abbildung 3.3 skizzierten drei Teilmengen der PL1-Formeln sind nicht
entscheidbar, wie folgende Uberlegungen zeigen:
1. Die Menge der unerfullbaren PL1-Formeln ist unentscheidbar. (Wenn die Fra-
ge “Ist F unerfullbar?” entscheidbar ware, h
¨
attenwiraucheinEntschei-
dungsverfahren fur das Allgemeingultigkeitsproblem, da die Fragestellung “Ist
¬
F unerfullbar?” aquivalent zur Frage “Ist F allgemeingultig?” ist. Ein Ent-
scheidungsverfahren fur das Unerfullbarkeitsproblem wurde also ein Entschei-
dungsverfahren fur das Allgemeingultigkeitsproblem implizieren.)
2. Die Menge der falsifizierbaren PL1-Formeln ist unentscheidbar. (Wenn die-
se Menge entscheidbar ware, wurde dies wie folgt ein Entscheidungsverfah-
ren fur das Allgemeingultigkeitsproblem implizieren: Die Frage “Ist F allge-
meingultig?” wurde mit “ja” (bzw. mit “nein”) beantwortet, falls die Frage
“Ist F falsifizierbar?” verneint (bzw. bejaht) wird.)
