はてなブックマーク

ゲーデルと論理プログラミング ━━━━━━━━━━━━━━ 1. はじめに K. Godelは数学と論理学の世界に数多くの業績を残したが，その中でもとく に大きなものは，形式的体系の演繹についての完全性定理と不完全性定理，そ して集合論における業績である。ここで紹介するのは，形式的体系についての Godel の２つの定理と論理プログラミングとの関係である。両者の組合せに意 外性を感じる読者もいらっしゃるかもしれないが，論理プログラミングは形式 的体系の定理証明技術をもとにつくられたものであり，２つは深く結びついて いる。 Godel の定理の詳細については別に譲るとして，ここではまずコンピュータ での定理証明の歴史と導出原理を概観し，Horn論理と論理プログラミング，と くにその代表的なものとしてのPrologを述べ，そしてPrologでの対象言語とメ タ言語との関わりから，不完全性定理が