Logik höherer Stufe

Erweiterung der Prädikatenlogik erster Stufe
(Weitergeleitet von Stufenlogik)

Unter Logik höherer Stufe (englisch Higher-Order Logic, HOL), auch Stufenlogik, versteht man eine Erweiterung der Prädikatenlogik erster Stufe. Sie basiert auf dem typisierten Lambda-Kalkül und geht auf Alonzo Churchs Theory of Simple Types zurück.

Entwickelt um 1940 als ein Versuch der Formalisierung der Logik in der Principia Mathematica von Whitehead und Russell, ist sie von Leon Henkin und Peter Andrews eingehend untersucht worden. Anfang der 1970er Jahre wurden nicht-klassische Versionen der Logik höherer Stufe entwickelt, die die Grundlage der modernen Typtheorie (Per Martin-Löf, Jean-Yves Girard) und Beweistheorie (Jean-Yves Girard, Gérard Huet, Robert Harper, Furio Honsell) bilden. Da die Logik höherer Stufe sowohl mächtig als auch relativ einfach auf einem Computer zu implementieren ist, wurden in letzter Zeit einige Theorembeweiser hierfür entwickelt, die gleichermaßen für die Mathematik als auch für die Informatik von Interesse sind.

Siehe auch

Bearbeiten

Literatur

Bearbeiten
  • Peter B. Andrews: An Introduction to Mathematical Logic and Type Theory: To Truth through Proof. Academic Press, 1986.
  • J. Lambek, P.J Scott: Introduction To Higher Order Categorical Logic, Cambridge University Press, Cambridge, UK, 1986. Online (Memento vom 5. Juli 2007 im Internet Archive)
Bearbeiten