条件つきブール関数の数え上げ

$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$ を正の整数とし、$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$ のすべてに本質的に依存するものの個数を求めよ。

$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\}$ のこととし、$\{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$ 変数のブール関数の個数を求めよ。

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

変数 $x_1,x_2,x_3,x_4$ を用いる論理式を、次の規則で帰納的に定める。

• 各 $x_i$ $(1\le i\le 4)$ は論理式である。
• $\phi ,\psi$ が論理式ならば、$\neg \phi$、$(\phi \wedge \psi )$、$(\phi \vee \psi )$ も論理式である。

定数記号 $0,1$ は用いない。論理式に $x_1,x_2,x_3,x_4$ を代入すると、写像 $\{0,1{\}}^4\to \{0,1\}$ が定まる。現れない変数には依存しない関数とみなす。

各変数 $x_i$ の出現回数がどれも高々 $1$ 回である論理式を、リードワンス論理式とよぶ。写像 $f:\{0,1{\}}^4\to \{0,1\}$ のうち、あるリードワンス論理式で表されるものの個数を求めよ。

命題変数 $x_1,x_2,x_3,x_4$ だけを用いた命題論理の論理式を考える（結合子は $\neg ,\wedge ,\vee ,\to$ とし、定数 $\top ,\perp$ は用いない）。2 つの論理式は、$x_1,\dots ,x_4$ へのすべての真理値割り当てで同じ真理値をとるとき同値であるという。

論理式 $\phi$ に対し、$\phi$ の中の $x_i$ をすべて $\neg x_i$（$i=1,2,3,4$）に同時に置き換えた論理式を ${\phi }^{\ast }$ とする。次の 2 条件をともに満たす論理式 $\phi$ を考える。

$(1)$ $\phi$ は、結合子 $\wedge ,\vee$ と命題変数 $x_1,\dots ,x_4$ だけを用いた（$\neg ,\to$ を用いない）ある論理式と同値である。

$(2)$ $\neg \phi$ と ${\phi }^{\ast }$ は同値である。

このような論理式 $\phi$ の同値類は何個あるか。