数理論理学・集合論の問題

真理値割り当てを、真になる変数の添字の集合 $S\subseteq \{1,2,3,4\}$ と同一視する。論理式 $\phi$ の同値類は、$\phi$ を真にする割り当ての族 $\mathcal{F}\subseteq \mathcal{P}(\{1,2,3,4\})$ と 1 対 1 に対応する。

条件の言い換え

$(1)$ $\wedge ,\vee$ と変数だけの論理式は単調（変数の値を偽から真に変えても、論理式の値は真から偽に変わらない）であり、逆に定数でない単調なブール関数は、真にする極小な集合 $S$ ごとに ${\bigwedge }_{i\in S}{x}_i$ を作り、それらの $\vee$ をとれば $\wedge ,\vee$ だけで表せる。よって $(1)$ は「$\mathcal{F}$ が上に閉じていて（$S\in \mathcal{F},S\subseteq T\Rightarrow T\in \mathcal{F}$）、$\varnothing \notin \mathcal{F}$ かつ $\{1,2,3,4\}\in \mathcal{F}$」と同じである。

$(2)$ 割り当て $S$ での ${\phi }^{\ast }$ の値は、補集合 $S^c$ での $\phi$ の値に等しい。よって $(2)$ は「すべての $S$ について $S\in \mathcal{F}⟺S^c\notin \mathcal{F}$」、つまり各組 $\{S,S^c\}$ からちょうど一方が $\mathcal{F}$ に入ることと同じである。（このとき $\mathcal{F}$ は空でも全体でもないので、$(1)$ の定数でないという条件も自動的に満たされる。）

また、$(1)$ と $(2)$ のもとで $\mathcal{F}$ の任意の 2 元 $S,T$ は交わる。実際 $S\cap T=\varnothing$ なら $T\subseteq S^c$ で、上に閉じているから $S^c\in \mathcal{F}$ となり、$(2)$ に反する。

場合分け

補集合の組は $\{\varnothing ,\{1,2,3,4\}\}$、$\{\{i\},\{1,2,3,4\}\setminus \{i\}\}$（$i=1,\dots ,4$ の 4 組）、2 元集合どうしの 3 組 $\{12,34\},\{13,24\},\{14,23\}$ の計 8 組である（$12$ は $\{1,2\}$ を表す）。

(a) ある $i$ について $\{i\}\in \mathcal{F}$ のとき。上に閉じているので $i$ を含む集合 8 個はすべて $\mathcal{F}$ に入る。$\mathcal{F}$ は各組からちょうど 1 つ、計 8 個の元をもつので、$\mathcal{F}=\{S:i\in S\}$。これは $\phi \equiv x_i$ で、確かに $(1)(2)$ を満たす。$i$ の選び方で 4 個。

(b) どの $\{i\}$ も $\mathcal{F}$ に入らないとき。$(2)$ より 3 元集合 4 個はすべて $\mathcal{F}$ に入り、$\{1,2,3,4\}\in \mathcal{F}$、$\varnothing \notin \mathcal{F}$。残りは 2 元集合の 3 組から 1 つずつ選ぶ方法で、$2^3=8$ 通りある。どの選び方でも $\mathcal{F}$ は上に閉じている（2 元集合を含む集合は 2 元集合自身か 3 元以上の集合で、3 元以上はすべて $\mathcal{F}$ に入っている。1 元集合と空集合は $\mathcal{F}$ に入らないので、それらの上の集合について条件は生じない）。よって 8 個すべてが条件を満たす。具体的には、選んだ 3 つの 2 元集合は（異なる組からとるので）どの 2 つも交わり、
- 三角形型 $\{ij,ik,jk\}$（4 通り）：$\phi \equiv (x_i\wedge x_j)\vee (x_i\wedge x_k)\vee (x_j\wedge x_k)$（$x_i,x_j,x_k$ の多数決）
- 星型 $\{ij,ik,il\}$（4 通り）：$\phi \equiv (x_i\wedge (x_j\vee x_k\vee x_l))\vee (x_j\wedge x_k\wedge x_l)$

となり、$4+4=8$ 個である。

(a), (b) で得た $\mathcal{F}$ はすべて異なるので、同値類の個数は $4+8=12$。

(1) は、$\phi$ が $\wedge ,\vee$ と変数だけで書ける論理式（定数なし）と同値であること、すなわち真理値関数が単調（$x\le y$ なら $f(x)\le f(y)$）であり、かつ定数関数でないことと同値である（単調関数は $\wedge ,\vee$ と定数で書け、定数関数以外は定数なしで書ける）。
(2) は $f(\neg x)=\neg f(x)$、すなわち自己双対である。自己双対な関数は定数ではない。よって求めるものは、4 変数の単調かつ自己双対なブール関数の個数である。

分類する。
- 実際に依存する変数が 1 個: $x_i$ の 4 個。
- 依存する変数が 2 個: 自己双対かつ単調なものはない（$x\wedge y$, $x\vee y$ は自己双対でない）。0 個。
- 依存する変数が 3 個: 多数決 $\mathrm{maj}(x_i,x_j,x_k)$ で、3 変数の選び方 $\left(\genfrac{}{}{0ex}{}{4}{3}\right)=4$ 個（3 変数で単調自己双対かつ 3 変数すべてに依存するのは多数決のみ）。
- 4 変数すべてに依存: 重み $(2,1,1,1)$ のしきい値関数（合計 5、重み 3 以上で真）で、重み 2 の変数の選び方が 4 通りで 4 個。他に 4 変数すべてに依存する単調自己双対関数はない。

合計 $4+0+4+4=12$。これは単調自己双対関数の個数の既知の数列 $1,2,4,12,81,\dots$（$n=1,2,3,4,5$）の 4 項目とも一致する。

答えは 12。