Die Aussagenlogik ist in ihrer Modellierungskraft beschränkt. Wir erweitern diese Logik zur Prädikatenlogik erster Stufe. Zuerst machen wir uns mit der Definition und den Arbeiten, die sich daraus ergeben, vertraut und üben den Umgang mit dieser Logik. Dann sehen wir uns die Modelle und den zugehörigen Gültigkeitsbegriff an. Wo Modelle sind, sind Beweise nicht weit; sie werden eingeführt und studiert. Im Zentrum der Darstellung steht dann die Untersuchung von Korrektheit und Vollständigkeit, die wir naturgemäß in zwei Schritten durchführen. Beim Beweis der Vollständigkeit erweist sich die Lindenbaum-Tarski-Algebra als interessantes Werkzeug. Die Unentscheidbarkeit der Gültigkeitsrelation wird durch Reduktion auf das Postsche Korrespondenzproblem nachgewiesen. Zum Vergleich von Modellen werden Morphismen eingeführt.

错误:搜索内容不能为空,请输入英文关键词
错误:关键词超出字数限制,请精简
高级检索

Prädikatenlogik erster Stufe

  • Ernst-Erich Doberkat

摘要

Die Aussagenlogik ist in ihrer Modellierungskraft beschränkt. Wir erweitern diese Logik zur Prädikatenlogik erster Stufe. Zuerst machen wir uns mit der Definition und den Arbeiten, die sich daraus ergeben, vertraut und üben den Umgang mit dieser Logik. Dann sehen wir uns die Modelle und den zugehörigen Gültigkeitsbegriff an. Wo Modelle sind, sind Beweise nicht weit; sie werden eingeführt und studiert. Im Zentrum der Darstellung steht dann die Untersuchung von Korrektheit und Vollständigkeit, die wir naturgemäß in zwei Schritten durchführen. Beim Beweis der Vollständigkeit erweist sich die Lindenbaum-Tarski-Algebra als interessantes Werkzeug. Die Unentscheidbarkeit der Gültigkeitsrelation wird durch Reduktion auf das Postsche Korrespondenzproblem nachgewiesen. Zum Vergleich von Modellen werden Morphismen eingeführt.