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

難易度 2大学院の講義の演習問題レベル大学院数学数理論理学・集合論

命題変数 $x_{1}, x_{2}, x_{3}, x_{4}$ だけを用いた命題論理の論理式を考える（結合子は $\neg, \land, \lor, \to$ を用いる）。2 つの論理式は、 $x_{1}, \dots, x_{4}$ へのすべての真理値割り当て（ $2^{4} = 16$ 通り）で同じ真理値をとるとき同値であるという。また、論理式 $φ$ に現れる $x_{3}$ と $x_{4}$ を同時に入れ替えて得られる論理式を $φ^{σ}$ と書く。

次の 4 つの条件をすべて満たす論理式 $φ$ を考える。

(1) $(x_{1} \land x_{2}) \to φ$ はトートロジーである。

(2) $φ \to (x_{1} \lor x_{2} \lor x_{3})$ はトートロジーである。

(3) $φ$ と $φ^{σ}$ は同値である。

(4) $φ$ を真にする真理値割り当て（充足割り当て）はちょうど $8$ 個である。

このような論理式 $φ$ は、同値なものを同一視すると何個あるか。

この問題で使うもの

論理的同値・論理的帰結と同値類の個数（説明と入口の問題）
真理値表と充足割り当ての個数（説明と入口の問題）
組合せ（説明と入口の問題）

この問題を解けるようになるまで（32 技能）

算数中学高校大学大学院

読み込み中…

右端（太枠）がこの問題で使う技能です。左へドラッグすると、さらに前の前提をさかのぼれます。技能を押すと、そこまでの道筋が光ります。

一覧で見る（前提が先）

ヒント

行き詰まったら、上から順に 1 つずつ開いてください。

ヒント 1

同値類は真理値関数 $f : {0, 1}^{4} \to {0, 1}$ と 1 対 1 に対応します。各条件を「どの割り当てで $f$ の値が強制されるか」に言い換えましょう。

ヒント 2

条件 (3) は $f (a, b, c, d) = f (a, b, d, c)$ を意味します。これと条件 (2) を組み合わせると、 $(0, 0, 1, 0)$ での値も決まります。残りの割り当てを $c, d$ の入れ替えで移り合う組（軌道）に分けましょう。

ヒント 3

強制的に真になる割り当ては $4$ 個です。自由な軌道は大きさ $1$ のものが $5$ 個、大きさ $2$ のものが $2$ 個あります。これらから合計 $4$ 個の割り当てを真にする選び方を数えます。

答えと解説

答えを見る

26

結果を記録する（このブラウザにだけ保存されます）:

解説を読む

論理式を同値なもので同一視したものは、真理値関数 $f : {0, 1}^{4} \to {0, 1}$ （ $1$ が真、 $0$ が偽）と 1 対 1 に対応する。 ${\neg, \land, \lor}$ は関数的に完全なので、どの $f$ もある論理式で表される。したがって、条件を満たす $f$ の個数を数えればよい。割り当てを $(a, b, c, d) = (x_{1}, x_{2}, x_{3}, x_{4})$ の値で表す。

条件の言い換え

(1) は「 $a = b = 1$ ならば $f (a, b, c, d) = 1$ 」と同値。よって $f (1, 1, c, d) = 1$ （4 個の割り当て）が強制される。
(2) は「 $a = b = c = 0$ ならば $f = 0$ 」と同値。よって $f (0, 0, 0, 0) = f (0, 0, 0, 1) = 0$ 。
(3) は、すべての $(a, b, c, d)$ で $f (a, b, c, d) = f (a, b, d, c)$ となることと同値。

(3) による追加の制約

(3) より $f (0, 0, 1, 0) = f (0, 0, 0, 1) = 0$ となり、 $(0, 0, 1, 0)$ も偽に強制される。また、 $(0, 0, 0, 0)$ は入れ替えで自分自身に移るので新たな制約は生じない。一方、(1) で真に強制される割り当ての集合 ${(1, 1, c, d)}$ は $c, d$ の入れ替えで閉じている。よって、真に強制される割り当てと偽に強制される割り当ては重ならず、(1)〜(3) は矛盾しない。

自由に決められる部分

残る割り当てを、 $c, d$ の入れ替えで移り合う組（軌道）に分ける。 $f$ は各軌道の上で一定である。

$(a, b) = (0, 1)$ のとき： ${(0, 1, 0, 0)}$ , ${(0, 1, 1, 1)}$ , ${(0, 1, 0, 1), (0, 1, 1, 0)}$ 。大きさは $1, 1, 2$ 。
$(a, b) = (1, 0)$ のとき：同様に大きさ $1, 1, 2$ の 3 つ。
$(a, b) = (0, 0)$ のとき：残るのは ${(0, 0, 1, 1)}$ だけで、大きさは $1$ 。

したがって、自由な軌道は大きさ $1$ のものが $5$ 個、大きさ $2$ のものが $2$ 個である。各軌道で真にするか偽にするかを独立に選べ、それ以外の割り当てでは値が強制されている。

充足割り当ての個数の条件 (4)

強制的に真になる割り当てが $4$ 個ある。よって、自由な軌道から合計 $8 - 4 = 4$ 個の割り当てを真にする選び方を数えればよい。真にする大きさ $2$ の軌道の個数を $k$ とすると、次のようになる。

$k = 0$ ：大きさ $1$ の軌道から $4$ 個選ぶので $(4 5) = 5$ 通り。
$k = 1$ ：大きさ $2$ の軌道の選び方が $2$ 通り、大きさ $1$ の軌道から $2$ 個選ぶのが $(2 5) = 10$ 通り。よって $2 \cdot 10 = 20$ 通り。
$k = 2$ ：大きさ $1$ の軌道は選ばないので $(0 5) = 1$ 通り。

合計は $5 + 20 + 1 = 26$ である。

母関数で確かめると、 $(1 + t)^{5} (1 + t^{2})^{2}$ の $t^{4}$ の係数は $(4 5) + 2 (2 5) + (0 5) = 26$ となり、一致する。

答えは $26$ 個である。

別解

論理式を、 $x_{1}, \dots, x_{4}$ への 16 通りの割り当てのうち真になるものの集合 $S$ とみなす。同値な論理式は同じ $S$ に対応し、どの $S$ にも対応する論理式がある。したがって $S$ の個数を数えればよい。

(1) より、 $x_{1} = x_{2} = 1$ の 4 個の割り当ては必ず $S$ に含まれる。

(2) より、 $x_{1} = x_{2} = x_{3} = 0$ の 2 個の割り当て、すなわち $(0, 0, 0, 0)$ と $(0, 0, 0, 1)$ は $S$ に含まれない。

(3) より、 $S$ は $x_{3}, x_{4}$ の入れ替えで不変である。 $(0, 0, 1, 0)$ を入れ替えると $(0, 0, 0, 1)$ になるが、これは $S$ に含まれない。よって $(0, 0, 1, 0)$ も $S$ に含まれない。

(4) より $∣ S ∣ = 8$ なので、すでに入ると決まっている 4 個のほかに、あと 4 個を選ぶ必要がある。

自由に選べる割り当ては次の 9 個である。
- $(x_{1}, x_{2}) = (1, 0)$ のとき、 $(x_{3}, x_{4})$ の 4 通り。
- $(x_{1}, x_{2}) = (0, 1)$ のとき、 $(x_{3}, x_{4})$ の 4 通り。
- $(0, 0, 1, 1)$ の 1 個。

これらを入れ替えの軌道に分ける。
- 大きさ 1 の軌道は 5 個ある。 $(1, 0, 0, 0)$ , $(1, 0, 1, 1)$ , $(0, 1, 0, 0)$ , $(0, 1, 1, 1)$ , $(0, 0, 1, 1)$ である。
- 大きさ 2 の軌道は 2 個ある。 ${(1, 0, 0, 1), (1, 0, 1, 0)}$ と ${(0, 1, 0, 1), (0, 1, 1, 0)}$ である。

$S$ は軌道の和集合で、追加する割り当ての合計が 4 個になる。大きさ 2 の軌道を $k$ 個選ぶとすると、大きさ 1 の軌道を $4 - 2 k$ 個選ぶことになる。
- $k = 0$ : $(4 5) = 5$
- $k = 1$ : $2 \cdot (2 5) = 20$
- $k = 2$ : $(2 2) \cdot (0 5) = 1$

合計は $5 + 20 + 1 = 26$ である。

この問題の確認

AI が作成した問題です。公開前に次の確認を行いました。

別の AI が答えを見ずに 3 回解き、3 回とも同じ答えになりました
プログラムで答えを計算し直し、一致を確認しました
AI の査読で、条件・解説・表記を確認しました
答えの正しさについて慎重に扱うべき点が見つからなかったため、自動で公開しました

確認の方法について

間違いを報告する

この問題の誤り・分かりにくい点・難易度や学年のずれを知らせる