数学 Wiki
Advertisement

表現定理、または関数的完全性の定理とは、のみを結合子として含む論理式によって、n変数の真理関数における真理値の割り当てが全て表現できることを指す。

証明

まず、nまでの引数を取る真理関数をと表現する。この時、この真理関数はの真理表の行を持つ。

例えば、ここで三変数の真理関数を定義する。このとき、

  • {T, T, T}
  • {T, T, F}
  • {T, F, T} ..

といったように、の組み合わせを持つ。

問題は、n変数である真理関数fが取りうる全ての真理表の行を表現できればよい。ここでは、真をT、偽をFと表現する。

この真理関数fが取る真理表の行全体をCと定義し、任意の行をと表現する。二値原理においては、は必ず真理値T、またはFを取る。

そこで、まずにおいて、Tになりうる行をとする。このAの行に対応する原子式の組み合わせをで表現する。これらに対応する式をで結んだ場合、Aで対応させた論理式の値を変化させることなしに、式同士を結合させることができる。

上記によって、Tを含む真理表の行が表現できることがわかった。

残るは全ての真理表の行がFであった場合だが、この場合は矛盾する式を作れば良い。

従って、全ての真理関数における真理値の割り当てをで表現できる。

補足

しかし、この定理はが全ての真理関数の割り当てを行うための最低限の結合子ということを示さない。十全を参照せよ。

Advertisement