萩谷 昌己:論理と計算 |
作成日:2013-02-12 最終更新日: |
形式論理と計算可能性に関する基礎的な概念を紹介する。
同じ著者の別の本では、真面目に勉強した。その別の本では 「ここまで勉強しなければ、本を買った意味がない」と序文で言い切っていたからである。 毎朝ちびちびと勉強した。しかし、この本ではそこまで厳しいことは言っていない。 この本もいつか、勉強してみたい。
Wang のアルゴリズムという、トートロジ判定アルゴリズムが紹介されている。 実装してみようとしたが行き詰っている。実装できたら紹介したい。
`f(x,y)` を原始帰納的関数とする。
`{ x in NN | EE y(f(x, y) = 0) }`
と定義される集合は帰納的に可算である。このように定義される集合を`Σ_1`集合という。 また、
`{ x in NN | AA y(f(x, y) = 0) }`
と定義される⊃を `Π_1`集合という。
ここではどちらも添字が1であるが、これを自然数 n について拡張することができる。 そうすると、`Σ_n`集合や`Π_n`集合ができる。そして、`Σ_n`集合でも`Π_n`集合でもある集合を、 `Δ_n`集合という。さらに、`Σ_n`集合、`Π_n`集合、`Δ_n`集合についての関係について、 算術的階層というものが考えられる。というところでこの章は終わっている。 算術的階層を考えることの意味については書かれていない。 残念である。
数式表示には、MathJaxを使っている。
発行日 | 1993 年 6月 8日 |
発行元 | 岩波書店 |
定 価 | 3495円(税別) |
サイズ | |
ISBN | 4-00-010513-2 |
備 考 | 3分冊合計の金額 |
NDC |
まりんきょ学問所 > 数学の部屋 > 数学の本 > 萩谷 昌己:論理と計算