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

$7$ 変数のブール関数とは写像 $f:\{0,1{\}}^7\to \{0,1\}$ のこととする。$7$ 変数のブール関数 $f$ で、次の 2 つの条件をともに満たすものの個数を求めよ。

$(1)$（巡回不変性）すべての $(x_1,\dots ,x_7)\in \{0,1{\}}^7$ に対して $$f(x_1,x_2,\dots ,x_7)=f(x_2,x_3,\dots ,x_7,x_1).$$

$(2)$（自己双対性）すべての $(x_1,\dots ,x_7)\in \{0,1{\}}^7$ に対して $$f(1-x_1,1-x_2,\dots ,1-x_7)=1-f(x_1,x_2,\dots ,x_7).$$

$n$ を正の整数とし、$n$ 変数のブール関数とは写像 $f:\{0,1{\}}^n\to \{0,1\}$ のこととする。$f$ が第 $i$ 変数に本質的に依存するとは、ある $a_1,\dots ,a_{i-1},a_{i+1},\dots ,a_n\in \{0,1\}$ が存在して
$$f(a_1,\dots ,a_{i-1},0,a_{i+1},\dots ,a_n)\ne f(a_1,\dots ,a_{i-1},1,a_{i+1},\dots ,a_n)$$
となることをいう。

3 変数のブール関数 $f:\{0,1{\}}^3\to \{0,1\}$ のうち、3 つの変数 $x_1,x_2,x_3$ のすべてに本質的に依存するものの個数を求めよ。

$\mathbb{N}=\{0,1,2,\dots \}$（$0$ を含む）とし、関数 $B:\mathbb{N}\times \mathbb{N}\to \mathbb{N}$ を、すべての $m,n\in \mathbb{N}$ について次の式で定める。
$$B(0,n)=n+2,$$
$$B(m+1,0)=B(m,1),$$
$$B(m+1,n+1)=B(m,B(m+1,n)).$$
$B(2,3)$ の値を求めよ。

$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$ 変数のブール関数の個数を求めよ。

$\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$ の個数のとりうる最大値を求めよ。