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

論理式をモデルの集合（その式を真にする割り当ての集合）と同一視する。$x_1,x_2,x_3$ への割り当ては $(x_1,x_2,x_3)\in \{0,1{\}}^3$ の $2^3=8$ 通りで、論理的に同値な式は同じモデルの集合をもつ。逆に $\{0,1{\}}^3$ のどの部分集合も（選言標準形を作ることで）ある論理式のモデルの集合になる。よって同値類は $\{0,1{\}}^3$ の部分集合と 1 対 1 に対応する。

条件をモデルの集合で書き直す. $\alpha \to \beta$ がトートロジーであることは $\alpha \models \beta$、つまり $\mathrm{Mod}(\alpha )\subseteq \mathrm{Mod}(\beta )$ と同じである。$\phi =x_1\wedge x_2\wedge x_3$, $\chi =x_1\vee x_2$ とおくと、条件は
$$\mathrm{Mod}(\phi )\subseteq \mathrm{Mod}(\psi )\subseteq \mathrm{Mod}(\chi )$$
となる。

モデルの集合を求める.
- $\mathrm{Mod}(\phi )=\{(1,1,1)\}$ で、$|\mathrm{Mod}(\phi )|=1$。
- $x_1\vee x_2$ が偽になるのは $x_1=x_2=0$ のときだけで、$x_3$ は $0,1$ の 2 通りなので、偽になる割り当ては 2 通り。よって $|\mathrm{Mod}(\chi )|=8-2=6$。
- $(1,1,1)\in \mathrm{Mod}(\chi )$ なので $\mathrm{Mod}(\phi )\subseteq \mathrm{Mod}(\chi )$ である。

数える. $\mathrm{Mod}(\psi )$ は $(1,1,1)$ を必ず含み、$\mathrm{Mod}(\chi )$ の残りの $6-1=5$ 個の割り当てを含むか含まないかを自由に選べる。よって同値類の個数は
$$2^{|\mathrm{Mod}(\chi )|-|\mathrm{Mod}(\phi )|}=2^{6-1}=32$$

同値な論理式を同一視すると、$x_1,x_2,x_3$ の論理式の同値類は、真理値割り当て $\{0,1{\}}^3$（8 通り）上の真偽関数 $\psi :\{0,1{\}}^3\to \{0,1\}$ と 1 対 1 に対応する（全部で $2^8$ 個）。

条件 1: $(x_1\wedge x_2\wedge x_3)\to \psi$ がトートロジー。$x_1\wedge x_2\wedge x_3$ が真になる割り当ては $(1,1,1)$ のみで、そこで $\psi$ が真でなければならない。よって $\psi (1,1,1)=1$。それ以外の割り当てでは前件が偽で常に真なので制約なし。

条件 2: $\psi \to (x_1\vee x_2)$ がトートロジー。$x_1\vee x_2$ が偽になる割り当ては $x_1=x_2=0$ の $(0,0,0),(0,0,1)$ の 2 つで、そこでは $\psi$ が偽でなければならない。よって $\psi (0,0,0)=\psi (0,0,1)=0$。

2 つの条件で値が固定される割り当ては $(1,1,1)$（値 1）と $(0,0,0),(0,0,1)$（値 0）の計 3 つで、互いに異なり矛盾しない。残りの $8-3=5$ 個の割り当てでは $\psi$ の値は自由。

したがって求める個数は $2^5=32$。
検算: 条件を満たす $\psi$ は 2 つの命題 $x_1\vee x_2$ と $x_1\wedge x_2\wedge x_3$ の間 $x_1\wedge x_2\wedge x_3\models \psi \models x_1\vee x_2$ にある。$x_1\vee x_2$ の真になる割り当ては 6 個、$x_1\wedge x_2\wedge x_3$ のそれは 1 個で、その差は 5 個の割り当てなので $2^5=32$。