萩谷　昌己：論理と計算

概要

形式論理と計算可能性に関する基礎的な概念を紹介する。

感想

同じ著者のソフトウェア科学のための論理学では、真面目に勉強した。厳しいことが書かれていたからだ。 しかし、この本ではそこまで厳しいことは言っていない。 この本もいつか、再度勉強してみたい。

第1章　集合と論理

Wang のアルゴリズムという、トートロジ判定アルゴリズムが紹介されている。 実装してみようとしたが行き詰っている。実装できたら紹介したい。

後記：同じ著者のソフトウェア科学のための論理学では LISP プログラムがある。（2025/02/26）

第2章　計算可能性

`f(x,y)` を原始帰納的関数とする。

`{ x in NN | EE y(f(x, y) = 0) }`

と定義される集合は帰納的に可算である。このように定義される集合を`Σ_1`集合という。 また、

`{ x in NN | AA y(f(x, y) = 0) }`

と定義される⊃を `Π_1`集合という。

ここではどちらも添字が１であるが、これを自然数 n について拡張することができる。 そうすると、`Σ_n`集合や`Π_n`集合ができる。そして、`Σ_n`集合でも`Π_n`集合でもある集合を、 `Δ_n`集合という。さらに、`Σ_n`集合、`Π_n`集合、`Δ_n`集合についての関係について、 算術的階層というものが考えられる。というところでこの章は終わっている。 算術的階層を考えることの意味については書かれていない。 残念である。

数式

数式表示には、MathJaxを使っている。

書誌情報

まりんきょ学問所 ＞ 数学の部屋 ＞ 数学の本 ＞ 萩谷　昌己：論理と計算