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

$\phi$ が真であるための条件は次の $4$ つが同時に成り立つことである。

• $(1)$ $x_1,x_2,x_3$ の少なくとも $1$ つが真
• $(2)$ $x_1$ と $x_2$ は同時に真でない
• $(3)$ $x_4$ が真なら $x_1$ も真
• $(4)$ $x_5$ が真なら $x_3$ も真

$x_1$ の値で場合分けする（$1$ を真、$0$ を偽と書く）。

$x_1=1$ のとき. $(2)$ より $x_2=0$。$(1)$ は自動的に成り立ち、$(3)$ も成り立つので $x_4$ は $2$ 通り。$x_3$ は自由で、
- $x_3=1$ なら $(4)$ より $x_5$ は $2$ 通り、
- $x_3=0$ なら $(4)$ より $x_5=0$ の $1$ 通り。

よって $2\times (2+1)=6$ 通り。

$x_1=0$ のとき. $(3)$ より $x_4=0$。$(1)$ より $(x_2,x_3)$ は $(1,0),(0,1),(1,1)$ の $3$ 通り（$(2)$ は自動的に成り立つ）。$x_5$ は $x_3=0$ のとき $1$ 通り、$x_3=1$ のとき $2$ 通りなので、$1+2+2=5$ 通り。

合計は $6+5=11$ 通りである。

$\neg (x_1\wedge x_2)$ より $(x_1,x_2)$ は $(1,0),(0,1),(0,0)$ のいずれか。それぞれ数える。$(x_3,x_5)$ について $x_5\to x_3$ を満たす組は $(1,1),(1,0),(0,0)$ の3通り（$x_3=1$ なら $x_5$ は任意の2通り、$x_3=0$ なら $x_5=0$ の1通り）。

(i) $(x_1,x_2)=(1,0)$：$x_1\vee x_2\vee x_3$ は真。$x_4\to x_1$ は $x_1=1$ なので常に真で $x_4$ は2通り。$(x_3,x_5)$ は3通り。計 $2\times 3=6$。

(ii) $(x_1,x_2)=(0,1)$：$x_1\vee x_2\vee x_3$ は真。$x_4\to x_1$ は $x_1=0$ なので $x_4=0$ の1通り。$(x_3,x_5)$ は3通り。計 $1\times 3=3$。

(iii) $(x_1,x_2)=(0,0)$：$x_1\vee x_2\vee x_3$ が真になるには $x_3=1$。$x_4=0$ の1通り、$x_5$ は任意で2通り。計 $2$。

合計 $6+3+2=11$。

検算：$x_3$ の値で分けると、$x_3=1$ のとき $x_1\vee x_2\vee x_3$ と $x_5\to x_3$ は真で、$\neg (x_1\wedge x_2)\wedge (x_4\to x_1)$ を満たす $(x_1,x_2,x_4)$ は $(1,0,0),(1,0,1),(0,1,0),(0,0,0)$ の4通り、$x_5$ は2通りで8。$x_3=0$ のとき $x_5=0$、$x_1\vee x_2$ が必要で $(1,0,0),(1,0,1),(0,1,0)$ の3通りで3。合計 $8+3=11$ で一致。