FANDOM


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

証明 編集

まず、nまでの引数を取る真理関数をf(x_1, x_2, .. x_n)と表現する。この時、この真理関数は2^nの真理表の行を持つ。

例えば、ここで三変数の真理関数g(x_1, x_2, x_2)を定義する。このとき、x_1, x_2, x_3

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

といったように、2 * 2 * 2 = 2^3の組み合わせを持つ。

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

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

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

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

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

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

補足 編集

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

広告ブロッカーが検出されました。


広告収入で運営されている無料サイトWikiaでは、このたび広告ブロッカーをご利用の方向けの変更が加わりました。

広告ブロッカーが改変されている場合、Wikiaにアクセスしていただくことができなくなっています。カスタム広告ブロッカーを解除してご利用ください。

FANDOMでも見てみる

おまかせWiki