計算理論・ラムダ計算の問題

$3$ 変数のブール関数とは写像 $f:\{0,1{\}}^3\to \{0,1\}$ のこととする。入力 $x_1,x_2,x_3$ をもつ基底 $B_2$ 上のブール回路を次のように定める。

• 回路は有向非巡回グラフで、入力ノード $x_1,x_2,x_3$ と、いくつかのゲートからなる（定数の入力ノードはもたない）。
• 各ゲートは $2$ 入力の任意のブール関数 $\{0,1{\}}^2\to \{0,1\}$（全 $16$ 個のどれでもよい）を計算し、その $2$ つの入力はそれより前にある入力ノードまたはゲートの出力である（$2$ つの入力が同じノードでもよい）。
• 回路のノード（入力ノードでもゲートでもよい）を $1$ つ選んで出力とし、そのノードが計算する関数を回路が計算する関数とする。
• 回路の大きさはゲートの個数とする。

$3$ 変数のブール関数 $f$ に対し、$f$ を計算する回路の大きさの最小値を $C(f)$ とする。$C(f)\le 2$ を満たす $3$ 変数のブール関数 $f$ の個数を求めよ。

入力変数を $x_1,x_2,x_3$ とするブール回路を考える。ゲートとしては 2 入力のブール関数 $\{0,1{\}}^2\to \{0,1\}$ をすべて（16 個。定数関数や片方の入力だけによる関数も含む）使ってよく、各ゲートの 2 つの入力には入力変数 $x_1,x_2,x_3$ またはそれより前のゲートの出力を（同じものを 2 回使うことも含めて）つなぐ。定数は入力として与えられない。回路の出力は、入力変数またはゲートのどれか 1 つの値とし、回路の大きさはゲートの個数とする。

ブール関数 $f:\{0,1{\}}^3\to \{0,1\}$ のうち、大きさ $2$ 以下の回路で計算できるものの個数を求めよ。

$n$ を正の整数とし、変数 $x_1,\dots ,x_n$ のブール回路を次のように定める。大きさ $s$（$s\ge 1$）の回路とは、ゲートの列 $g_1,g_2,\dots ,g_s$ であって、各ゲート $g_i$ が
- 種類 $\mathrm{AND}$, $\mathrm{OR}$, $\mathrm{NOT}$ のいずれか 1 つと、
- 入力として、$\mathrm{AND}$, $\mathrm{OR}$ のときは $x_1,\dots ,x_n,g_1,\dots ,g_{i-1}$ の中から選んだ順序付きの 2 つ組 $(u_i,v_i)$（$u_i=v_i$ も許す）、$\mathrm{NOT}$ のときは同じ候補の中から選んだ 1 つの $u_i$

をもつものとする。入力 $a\in \{0,1{\}}^n$ に対し、$x_j$ の値を $a_j$ とし、$g_1,g_2,\dots$ の順に、$g_i$ の値を $u_i,v_i$ の値の論理積・論理和、または $u_i$ の値の否定として定める。回路が計算する関数とは、$a$ に最後のゲート $g_s$ の値を対応させる関数 $\{0,1{\}}^n\to \{0,1\}$ のことである。

関数 $f:\{0,1{\}}^n\to \{0,1\}$ が変数 $x_j$ に依存するとは、第 $j$ 成分だけが異なる $a,a^{\prime }\in \{0,1{\}}^n$ で $f(a)\ne f(a^{\prime })$ となるものが存在することをいう。

$f$ がすべての変数 $x_1,\dots ,x_n$ に依存するとき、$f$ を計算するどの回路においても、種類が $\mathrm{AND}$ または $\mathrm{OR}$ であるゲートの個数は $n-1$ 以上であることを証明せよ。

$4$ 変数のブール関数とは写像 $f:\{0,1{\}}^4\to \{0,1\}$ のこととする。$a\in \{0,1\}$ に対して $\overline{a}=1-a$ とし、$x=(x_1,x_2,x_3,x_4)\in \{0,1{\}}^4$ に対して $\overline{x}=(\overline{x_1},\overline{x_2},\overline{x_3},\overline{x_4})$ とする。

$4$ 変数のブール関数 $f$ が自己双対であるとは、すべての $x\in \{0,1{\}}^4$ について
$$f(\overline{x})=\overline{f(x)}$$
が成り立つことをいう。自己双対な $4$ 変数のブール関数の個数を求めよ。

$\Sigma =\{0,1\}$ とし、${\Sigma }^{\ast }$ を空列 $\epsilon$ を含む $\Sigma$ 上の有限列全体、$|p|$ を列 $p$ の長さ、${\Sigma }^6$ を長さ $6$ の列全体とする。

部分関数 $V:{\Sigma }^{\ast }\to {\Sigma }^{\ast }$（定義されない入力があってもよい）を記述方式とよび、$x\in {\Sigma }^{\ast }$ に対して
$$C_V(x)=\min \{|p|:V(p)=x\}$$
と定める（$V(p)=x$ となる $p$ がなければ $C_V(x)=\infty$ とする）。

記述方式 $V$ をいろいろに選ぶとき、$C_V(x)\le 3$ をみたす $x\in {\Sigma }^6$ の個数のとりうる最大値を求めよ。