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

1. 同値類と真理集合の対応

真理値割り当て全体を $V=\{0,1{\}}^6$（$1$ が真）とし、論理式 $\theta$ に対して $\theta$ を真にする割り当ての集合（真理集合）を $S_{\theta }\subseteq V$ とする。$\theta ,{\theta }^{\prime }$ が同値であることは $S_{\theta }=S_{{\theta }^{\prime }}$ と同じである。また任意の部分集合 $T\subseteq V$ は、$T$ の各要素に対応する連言（リテラルの $\wedge$）を $\vee$ で結んだ選言標準形（$T=\varnothing$ なら $x_1\wedge \neg x_1$）の真理集合になる。よって同値類と $V$ の部分集合は 1 対 1 に対応する。

$\phi \to \psi$ がトートロジー $⟺S_{\phi }\subseteq S_{\psi }$、$\psi \to \chi$ がトートロジー $⟺S_{\psi }\subseteq S_{\chi }$ である。

2. $S_{\phi }\subseteq S_{\chi }$ の確認

割り当てを $0,1$ の長さ $6$ の列 $x_1{x}_2\cdots x_6$ と見ると、$S_{\phi }$ は「$0$ が 2 つ続かない列」、$S_{\chi }$ は「$0$ が 3 つ続かない列」の全体である。$00$ を含まなければ $000$ も含まないので $S_{\phi }\subseteq S_{\chi }$。したがって求める個数は $S_{\phi }\subseteq T\subseteq S_{\chi }$ となる $T$ の個数、すなわち $S_{\chi }\setminus S_{\phi }$ の部分集合の個数 $2^{|S_{\chi }|-|S_{\phi }|}$ である。

3. $|S_{\phi }|$ の計算

長さ $n$ で $00$ を含まない列の個数を $a_n$ とする。末尾が $1$ なら残りは長さ $n-1$ の任意の条件を満たす列、末尾が $0$ ならその前は $1$ で残りは長さ $n-2$ の列なので $a_n=a_{n-1}+a_{n-2}$。$a_1=2,a_2=3$ から
$$a_3=5,a_4=8,a_5=13,a_6=21.$$
よって $|S_{\phi }|=21$。

4. $|S_{\chi }|$ の計算

長さ $n$ で $000$ を含まない列の個数を $b_n$ とする。末尾が $1$, $10$, $100$ のどれかで場合分けすると $b_n=b_{n-1}+b_{n-2}+b_{n-3}$。$b_1=2,b_2=4,b_3=7$ から
$$b_4=7+4+2=13,b_5=13+7+4=24,b_6=24+13+7=44.$$
よって $|S_{\chi }|=44$。

5. 結論
$$2^{44-21}=2^{23}=8388608.$$

$x_1,\dots ,x_6$ だけを用いた論理式の同値類は、$\{0,1{\}}^6\to \{0,1\}$ の関数（ブール関数）と一対一に対応する（$\neg ,\wedge ,\vee$ で任意のブール関数が表せる）。$\phi \to \psi$ が恒真とは、$\phi$ を真にする割り当てでは $\psi$ も真、$\psi \to \chi$ が恒真とは、$\psi$ を真にする割り当てでは $\chi$ も真、ということである。$A=\{\phi \text{ が真になる割り当て}\}$、$B=\{\chi \text{ が真になる割り当て}\}$ とおくと、$A\subseteq B$ のとき、条件を満たす $\psi$ の真理値表は $A$ 上で真、$B$ の外で偽、$B\setminus A$ 上で自由であり、個数は $2^{|B|-|A|}$。

$A\subseteq B$ の確認: $\phi$ が真なら隣り合う 2 変数の少なくとも一方が真なので、連続する 3 変数の少なくとも一方も真であり、$\chi$ も真。

$|A|$: 長さ 6 の 0/1 列で「00」を含まないものの個数（偽を 0 とする）。長さ $n$ の個数 $a_n$ は $a_1=2,a_2=3,a_n=a_{n-1}+a_{n-2}$ より $a_3=5,a_4=8,a_5=13,a_6=21$。よって $|A|=21$。

$|B|$: 長さ 6 の 0/1 列で「000」を含まないものの個数 $b_n$ は $b_1=2,b_2=4,b_3=7$、$b_n=b_{n-1}+b_{n-2}+b_{n-3}$ より $b_4=13,b_5=24,b_6=44$。よって $|B|=44$（窓 $i=1,\dots ,4$ は位置 1〜6 の連続 3 つ組をすべて覆う）。

したがって $|B|-|A|=23$、同値類の個数は $2^{23}=8388608$。

検算: $b_4=13$ は長さ 4 の 16 通りから 000 を含む 0000,0001,1000 の 3 個を除いた数に一致する。