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

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

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

$\mathrm{(i)}$ 1変数の写像$B\to B$について.
1変数の写像で考えられるものは以下の$4$つ, $g_1\pare{x},\ldots,g_4\pare{x}$であり, $$\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,\ldots,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\leq i\leq 2^{2n},\ \bm{x}_n\in B^n$として，${F^i_n {\left( \bm{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{align} {F^k_{n+1} {\left( \bm{x}_n,0 \right)}}={F^j_n {\left( \bm{x}_n \right)}}\end{align}$$ここで，左辺は第$n+1$変数を固定しているので$n$変数写像になっており，また, 右辺は$\mathrm{(ii)}$の仮定から適当な$j$が存在して，任意の$\bm{x}_n$に対してこの等号を成立させる.

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

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

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