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

$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).$$

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

$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\}$ のこととし、$\{0,1\}$ を 2 元体 ${\mathbb{F}}_2$ と同一視する。各 $4$ 変数のブール関数 $f$ は、${\mathbb{F}}_2$ 上の多項式として
$$f(x_1,x_2,x_3,x_4)=\sum _{S\subseteq \{1,2,3,4\}}{a}_S\prod _{i\in S}{x}_i(a_S\in {\mathbb{F}}_2)$$
の形にただ 1 通りに表される（代数的標準形。$S=\varnothing$ のときの積は $1$ とする）。$a_S=1$ となる $S$ の要素の個数 $|S|$ の最大値を $f$ の次数とよぶ（恒等的に $0$ の関数の次数は $-\infty$ とする）。

次数がちょうど $2$ である $4$ 変数のブール関数の個数を求めよ。

原子型として $o$ ただ 1 つをもち、定数をもたない単純型付きラムダ計算（チャーチ流）を考える。型は $$\tau ::=o\mid (\tau \to \tau )$$ で生成される式とし、括弧の付け方（木としての形）が異なる型は異なる型とみなす。型 $\tau$ が住人をもつとは、型 $\tau$ の閉じた項（自由変数をもたない項）が存在することをいう。

矢印 $\to$ をちょうど $5$ 個含む型（したがって $o$ をちょうど $6$ 個含む型）のうち、住人をもつものの個数を求めよ。