論理回路の完備性・完全性について

論理回路の完備性・完全性(completeness)について
 いまいち理解がすっきりしなかったのでうんうん考えていた。これは論理学における関数の完全性の概念と同じ。{AND∧,OR∨,NOT¬}の演算子のみで任意の数の引数をとる全ての論理関数を構成できるというもの。complete setについては、and/or/notを示してから、これがこれに書き換えられるよ〜と言えばおっけい。nandだけとか。

・まず、論理学の本(戸田山『論理学をつくる』)に書いてあった証明から。構成的な証明。
 N項の引数で戻り値が1になるような引数の組み合わせすべてについて積が1になるように、選言標準形を作る。たとえば3つの引数PQRについて、{(1,0,1),(0,1,1),(0,0,1)}の戻り値が1となり他の5つの組の戻り値が0となるような関数Fは、NOTを¬A=A'のように書くことにして、F(P,Q,R) = (PQ'R)+(P'QR)+(P'Q'R)となる。戻り値がすべて0の場合は、F(P,Q,R) = PP'+QQ'+RR'のようにする。以上のように構成すれば、任意の論理関数を演算子AND, OR, NOTのみで表現することができる。

論理回路の資料(追記:論理演算 | UTokyo OpenCourseWare たぶんこれ)の方は帰納法で証明を書いてた。
 1. 引数がひとつ(X1とする)の論理関数で戻り値がX1,X1'となるようなものはAND, NOT, ORの演算子で構成できる。F1(X1) = X1, F1(X1) = X1'の2つである。
 2. 引数がm個(X1,...,Xmとする)のすべての論理関数がAND, OR, NOTで構成できると仮定する。この仮定のもとで、m+1個の引数をとるすべての論理関数がAND, OR, NOTで表現できることを示す。
 引数がm個の任意の論理関数Fm_1とFm_2について、Fm_1に対してはm+1番目の入力としてXm+1、Fm_2に対して同様にXm+1'を固定し積をとる。そして2つを和でつなぐ。すなわち、
 Fm+1 = Fm_1 * Xm+1 + Fm_2 * Xm+1' (Xm+1∈{0,1})
 とする。仮定よりFm_1,Fm_2はAND, OR, NOTで構成されているので、Fm+1もAND, OR, NOTで構成されている。
 (任意の2つを選んでるからわかりづらいけど、重複もありで、Xm+1∈{0,1}だから逆もカバーしている。m個の引数をとるすべての論理関数の集合の中から重複ありで2つを選んで上記の式からm+1個の引数の論理関数を作る、という操作をすべての(m個引数の関数の)組み合わせについて行なえば、m+1個の引数のすべての論理関数を要素に持つような集合が構成できる、ということになる)。
 ちなみに上記の式を1から繰り返すたびに分配則で選言標準形に直しながら操作していけば、同じ式になるんだと思う。ちゃんと考えてないから怪しいけどたぶんそう。
 論理回路だと出力が1つ以上の場合も考えなくちゃいけないが、それは単に割り当てを考えるだけなので問題ないはず。