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

節 $\neg x_i\vee \neg x_{i+1}$ が真であることは「$x_i$ と $x_{i+1}$ がともに真ではない」ことと同値である。したがって $\phi$ を真にする割り当ては、$1,2,\dots ,10$ を円周上に並べたとき、隣り合う 2 つの変数が同時に真にならない割り当てである。

直線上の場合の個数. まず補助として、$m$ 個の変数 $y_1,\dots ,y_m$ について、${\bigwedge }_{j=1}^{m-1}(\neg y_j\vee \neg y_{j+1})$（巡回させない）を真にする割り当ての個数を $a_m$ とおく（$a_0=1$ とする）。$y_m$ が偽のときは残り $y_1,\dots ,y_{m-1}$ が同じ条件を満たせばよく $a_{m-1}$ 通り、$y_m$ が真のときは $y_{m-1}$ が偽に決まり、$y_1,\dots ,y_{m-2}$ が条件を満たせばよく $a_{m-2}$ 通り。よって
$$a_m=a_{m-1}+a_{m-2}(m\ge 2),a_0=1,a_1=2.$$
これから
$$a_2=3,a_3=5,a_4=8,a_5=13,a_6=21,a_7=34,a_8=55,a_9=89.$$

巡回の場合. $x_1$ の値で場合分けする。

$(1)$ $x_1$ が偽のとき：$x_1$ を含む節 $\neg x_{10}\vee \neg x_1$, $\neg x_1\vee \neg x_2$ は自動的に真になる。残る条件は $x_2,x_3,\dots ,x_{10}$（$9$ 個）が直線上で隣り合って同時に真にならないことなので、$a_9=89$ 通り。

$(2)$ $x_1$ が真のとき：$x_2$ と $x_{10}$ はともに偽に決まる。すると $x_2,x_{10}$ を含む節はすべて真になり、残る条件は $x_3,\dots ,x_9$（$7$ 個）が直線上で隣り合って同時に真にならないことなので、$a_7=34$ 通り。

以上より、求める個数は
$$89+34=123$$
である。

$\phi$ が真 $⟺$ 隣り合う（巡回的に）どの 2 変数も同時には真にならない。真となる変数の添字の集合は、10 頂点の閉路 $C_{10}$ の独立集合に対応する。

$C_n$ の独立集合の個数を $c_n$ とする。$x_n$ が偽なら残りは $n-1$ 頂点の路 $P_{n-1}$ の独立集合、$x_n$ が真なら $x_{n-1},x_1$ が偽で残りは $n-3$ 頂点の路 $P_{n-3}$ の独立集合である。$P_m$ の独立集合の個数を $p_m$ とすると $p_0=1,p_1=2,p_m=p_{m-1}+p_{m-2}$ なので、$p_2=3,p_3=5,p_4=8,p_5=13,p_6=21,p_7=34,p_8=55,p_9=89$。

よって $c_{10}=p_9+p_7=89+34=123$。

検算: $c_n$ はリュカ数 $L_n$ で、$L_1=1,L_2=3,L_3=4,L_4=7,L_5=11,L_6=18,L_7=29,L_8=47,L_9=76,L_{10}=123$ となり一致する。また真の個数 $k$ ごとに数えると、$k$ 個選ぶ方法は $\frac{10}{10-k}\left(\genfrac{}{}{0ex}{}{10-k}{k}\right)$ 通りで、$k=0,\dots ,5$ について $1,10,35,50,25,2$、合計 $123$。