表現定理

表現定理、または関数的完全性の定理とは、$\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$が全ての真理関数の割り当てを行うための最低限の結合子ということを示さない。十全を参照せよ。