画像に書かれた3つの数理論理学の問題を解く問題です。各問題は、ある論理式とその否定が別の論理式と同値であることを示すものです。 問題1: $\neg(\exists x \text{ s.t. } (P(x) \land Q(x))) \equiv \forall x, (P(x) \Rightarrow (\neg Q(x)))$ 問題2: $\neg(\exists x \text{ s.t. } (P(x) \land Q(x) \Rightarrow R(x))) \equiv \forall x, (P(x) \land Q(x) \land (\neg R(x)))$ 問題3: $\neg(\forall x, (P(x) \Rightarrow (Q(x) \land R(x)))) \equiv \exists x \text{ s.t. } ((P(x) \land (\neg Q(x)) \lor (\neg R(x))))$

1. 問題の内容

画像に書かれた3つの数理論理学の問題を解く問題です。各問題は、ある論理式とその否定が別の論理式と同値であることを示すものです。

問題1: $\neg(\exists x \text{ s.t. } (P(x) \land Q(x))) \equiv \forall x, (P(x) \Rightarrow (\neg Q(x)))$

問題2: $\neg(\exists x \text{ s.t. } (P(x) \land Q(x) \Rightarrow R(x))) \equiv \forall x, (P(x) \land Q(x) \land (\neg R(x)))$

問題3: $\neg(\forall x, (P(x) \Rightarrow (Q(x) \land R(x)))) \equiv \exists x \text{ s.t. } ((P(x) \land (\neg Q(x)) \lor (\neg R(x))))$

2. 解き方の手順

それぞれの問題について、左辺から右辺を導く手順を示します。

問題1:

$\neg(\exists x \text{ s.t. } (P(x) \land Q(x)))$ (左辺)

$\equiv \forall x, \neg(P(x) \land Q(x))$ (量限定子の否定)

$\equiv \forall x, (\neg P(x) \lor \neg Q(x))$ (ド・モルガンの法則)

$\equiv \forall x, (P(x) \Rightarrow \neg Q(x))$ (含意の定義: $A \Rightarrow B \equiv \neg A \lor B$)

(右辺)

問題2:

$\neg(\exists x \text{ s.t. } (P(x) \land Q(x) \Rightarrow R(x)))$ (左辺)

$\equiv \forall x, \neg((P(x) \land Q(x)) \Rightarrow R(x))$ (量限定子の否定)

$\equiv \forall x, \neg(\neg(P(x) \land Q(x)) \lor R(x))$ (含意の定義)

$\equiv \forall x, ((P(x) \land Q(x)) \land \neg R(x))$ (ド・モルガンの法則)

$\equiv \forall x, (P(x) \land Q(x) \land \neg R(x))$ (結合律)

(右辺)

注記: 画像の2番目の等号は誤りです。

問題3:

$\neg(\forall x, (P(x) \Rightarrow (Q(x) \land R(x))))$ (左辺)

$\equiv \exists x, \neg(P(x) \Rightarrow (Q(x) \land R(x)))$ (量限定子の否定)

$\equiv \exists x, \neg(\neg P(x) \lor (Q(x) \land R(x)))$ (含意の定義)

$\equiv \exists x, (P(x) \land \neg(Q(x) \land R(x)))$ (ド・モルガンの法則)

$\equiv \exists x, (P(x) \land (\neg Q(x) \lor \neg R(x)))$ (ド・モルガンの法則)

$\equiv \exists x \text{ s.t. } (P(x) \land (\neg Q(x) \lor \neg R(x)))$

(右辺)

3. 最終的な答え

問題1: $\neg(\exists x \text{ s.t. } (P(x) \land Q(x))) \equiv \forall x, (P(x) \Rightarrow (\neg Q(x)))$

問題2: $\neg(\exists x \text{ s.t. } (P(x) \land Q(x) \Rightarrow R(x))) \equiv \forall x, (P(x) \land Q(x) \land (\neg R(x)))$

問題3: $\neg(\forall x, (P(x) \Rightarrow (Q(x) \land R(x)))) \equiv \exists x \text{ s.t. } (P(x) \land (\neg Q(x) \lor \neg R(x)))$