Hallo,
bekanntermassen ist die Prädikatenlogik 1. Stufe unentscheidbar.
Heisst das, dass ich keinen Algorithmus angeben kann, der bei Eingabe einer Prädikatenformel 1.Stufe in endlichen Schritten ausgibt, ob die Formel erfüllbar ist oder nicht ?
MfG,
Tris
Hallo,
zunächst ja - allerdings versteht man üblicherweise unter der „Unentscheidbarkeit der Prädikatenlogik“, daß die Allgemeingültigkeit bzw. die Beweisbarkeit von beliebigen prädikatenlogischen Aussagen unentscheidbar ist. Nun ist eine Formel F allgemeingültig, gdw. -F unerfüllbar (bzw. widersprüchlich) ist, d.h. auch das Unerfüllbarkeitsproblem ist unentscheidbar. Wg. -F unerfüllbar gdw. -F ist nicht erfüllbar folgt damit auch die Unentscheidbarkeit des Erfüllbarkeitsproblems.
Bewiesen wird das Allgemeingültigkeitsproblem üblicherweise durch Reduktion auf ein bekanntes unentscheidbares Problem, z.B. das Halteproblem. Es wird dabei eine Formel konstruiert, die das vermeintliche Entscheidungsverfahren für das Halteproblem kodiert und die gdw. allgemeingültig ist, wenn dieses Verfahren einen gegebenen Algorithmus als „terminierend“ einstuft. Wäre damit das Allgemeingültigkeitsproblem entscheidbar, dann auch das Halteproblem, was die Unentscheidbarkeit des Allgemeingültigkeitsproblem impliziert.
Gruss
Enno