FANDOM


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

編集

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

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

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

証明 編集

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

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

補足 編集

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

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


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

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

FANDOMでも見てみる

おまかせWiki