十全

十全 (adequate) である、あるいは関数的に完全である (functionally complete) とは、ある結合子によって全ての真理関数の真理値割り当てが表現できることを指す。

例

表現定理を参照せよ。このとき、$\lnot, \land, \lor$は十全であった。だが、同様に

• $\lnot ,\lor$
• $\lnot, \land$
• $\lnot ,\to$

だけで十全にすることが可能である。

証明

$\lnot, \land, \lor$はお互いに論理的同値にすることができる(選言, 連言, 条件法を参照せよ)。そして、お互いに書き換えることができるということは、それだけで表現することが可能であることを同時に意味する。

表現定理によって、既に$\lnot, \land, \lor$だけで、全ての真理関数の真理値の割り当てが表現できることが証明されている。このとき、例えば$\lor$を$\and$に書き換えれば、$\lnot, \land$だけで十全になる。

補足

2変数の真理関数において、一つの結合子だけで十全になる例は、否定論理積および否定論理和があることがわかっている。この具体的な内容についてはシェーファー関数を参照せよ。