否定論理積(NAND)の完全性 (二元体上の写像)

$x=0,1$の場合をそれぞれ考えればよい.

数学的帰納法を用いて示す. 終域は$B$のもののみを考えれば十分で，終域が複数の$B$で構成されている, すなわち$B^m$のようになっている場合は，これから構成する$F_n^k\left({\mathit{x}}_n\right)$の$k$をそれぞれ適当に選べばよい.

$(\mathrm{i})$ 1変数の写像$B\to B$について.
1変数の写像で考えられるものは以下の$4$つ, $g_1\left(x\right),\dots ,g_4\left(x\right)$であり, $$\begin{align}
g_1(0)=0,\ & g_1(1)=0
\
g_2(0)=1,\ & g_2(1)=0
\
g_3(0)=0,\ & g_3(1)=1
\
g_4(0)=1,\ & g_4(1)=1\end{align}$$これを，\$x\in B\$を用いて表すと以下のようになる.$$\begin{align}
g_1(x) & =0
\
g_2(x) & =1+x
\
g_3(x) & =x
\
g_4(x) & =1\end{align}$$上の4つの写像を\$f\$と，\$x\in B\$を用いて構成する.$$\begin{align}
g_1(x) & ={f {\left( {f {\left( {f {\left( x,x \right)}},x \right)}},{f {\left( {f {\left( x,x \right)}},x \right)}} \right)}}
\
g_2(x) & =f(x,x)
\
g_3(x) & ={f {\left( {f {\left( x,x \right)}},{f {\left( x,x \right)}} \right)}}
\
g_4(x) & ={f {\left( {f {\left( x,x \right)}},x \right)}}\end{align}$$これが実際に$g_1,\dots ,g_4$の多項式を与えることは計算すれば確かめられる.
例えば, $f(x,x)=1+x\cdot x=1+x=g_2(x)$であることが確かめられるし，$g_1$については, $$\begin{align}
& {f {\left( {f {\left( {f {\left( x,x \right)}},x \right)}},{f {\left( {f {\left( x,x \right)}},x \right)}} \right)}}
\
& ={f {\left( {f {\left( 1+x,x \right)}},{f {\left( 1+x,x \right)}} \right)}}
\
& ={f {\left( 1+{\left( 1+x \right)}x,1+{\left( 1+x \right)}x \right)}}
\
& ={f {\left( 1,1 \right)}}
\
& =1+1\cdot1
\
& =0
\
& =g_1(x)\end{align}$$ となる. ($g_3,g_4$についても同様.)
よって, 1変数の写像は確かに$f$のみで表すことができる.

$(\mathrm{ii})$ $n$を自然数とし, $n$変数の写像$B^n\to B$が$f$のみで表せると仮定する.
このとき, 始域の元の組として考えられるものは$2^n$通り，各$n$個の組に対して, 終域の元として考えられるものは$2$通りあるから，相異なる写像は$2^{2n}$個存在することがわかる.$n$変数の写像を$1\le i\le 2^{2n},{\mathit{x}}_n\in B^n$として，$F_n^i\left({\mathit{x}}_n\right)$と表すことにする.

($\mathrm{iii}$) $n+1$変数の写像$B^{n+1}\to B$について.
簡単のために, 以下の2つの写像を$f$を用いて定義しておく.
$$\begin{align}
& {h_1 {\left( x,y \right)}}
\
& \coloneqq
{f {\left( {f {\left(
{f {\left( x,y \right)}}，{f {\left(
{f {\left( x,x \right)}}
，{f {\left( y,y \right)}}
\right)}}
\right)}}
，{f {\left(
{f {\left( x,y \right)}}，{f {\left(
{f {\left( x,x \right)}}，{f {\left( y,y \right)}}
\right)}}
\right)}}
\right)}}
\
& = x+y\end{align}$$$$\begin{align}
{h_2 {\left( x,y \right)}}
\coloneqq {f {\left( {f {\left( x,y \right)}},{f {\left( x,y \right)}} \right)}}=xy\end{align}$$(それぞれ排他的論理和, 論理積という.)
始域の元は，${\left( \bm{x}n,x{n+1} \right)}\in B^{n+1}$と表すことができる.
$B^{n+1}\to B$の写像のひとつ, ${F^k_{n+1} {\left( \bm{x}n,x{n+1} \right)}}$(但し,$1\leq k\leq 2^{2(n+1)}$)を,適当な$1\leq i,\ j\leq 2^{2n}$を用いて，$$\begin{align}
{F^k_{n+1} {\left( \bm{x}n,x{n+1} \right)}}\coloneqq & {h_1 {\left( {h_2 {\left( {F^i_n {\left( \bm{x}n \right)}},x{n+1} \right)}},{h_2 {\left( {F^j_n {\left( \bm{x}n \right)}},{f {\left( {x{n+1},x_{n+1}} \right)}} \right)}} \right)}}
\
=&{F^i_n {\left( \bm{x}n \right)}}\cdot x{n+1} + {F^i_n {\left( \bm{x}n \right)}}\cdot {\left( 1+x{n+1} \right)}\end{align}$$と定める.$n+1$変数写像の第$n+1$変数$x_{n+1}$として考えられるのは$x_{n+1}=0,1$のみである.

1. $x_{n+1}=0$のとき $$\begin{array}{r}{F}_{n+1}^k({\mathit{x}}_n,0)=F_n^j\left({\mathit{x}}_n\right)\end{array}$$ここで，左辺は第$n+1$変数を固定しているので$n$変数写像になっており，また, 右辺は$(\mathrm{ii})$の仮定から適当な$j$が存在して，任意の${\mathit{x}}_n$に対してこの等号を成立させる.

2. $x_{n+1}=1$のとき $$\begin{array}{r}{F}_{n+1}^k({\mathit{x}}_n,1)=F_n^i\left({\mathit{x}}_n\right)\end{array}$$こちらも, 左辺は$n$変数写像なので, 仮定$(\mathrm{ii})$により，適当な$i$が存在して，任意の${\mathit{x}}_n$に対してこの等号を成立させる.

これによって，任意の$({\mathit{x}}_n,x_{n+1})\in B^{n+1}$に対し，$F_{n+1}^k({\mathit{x}}_n,x_{n+1})$は$0$も$1$も取れる.

数学的帰納法により, 任意の$n$変数写像$B^n\to B$は, $f$のみで表すことができることが示された.