小さな回路で計算できる関数

$4$ 変数のブール関数とは写像 $f:\{0,1{\}}^4\to \{0,1\}$ のこととする。入力 $x_1,x_2,x_3,x_4$ をもつブール回路を次のように定める。
- 回路は有向非巡回グラフで、$4$ つの入力ノード $x_1,x_2,x_3,x_4$ と、いくつかのゲートからなる。
- 各ゲートは $2$ 入力で、$16$ 個ある $2$ 変数ブール関数 $\{0,1{\}}^2\to \{0,1\}$ のどれを割り当ててもよい（定数関数や片方の入力だけによる関数も含む）。ゲートの $2$ つの入力は、入力ノードまたはそれより前のゲートであり、同じノードを $2$ つの入力に使ってもよい。
- ノードのうち $1$ つ（入力ノードでもゲートでもよい）を出力として指定し、その値を回路が計算する関数とする。
- 回路の大きさとは、ゲートの個数のことである。

大きさ $1$ 以下の回路で計算できる $4$ 変数のブール関数の個数を求めよ。

$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$ 以上であることを証明せよ。

$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$ 以下の回路で計算できるものの個数を求めよ。