0

この文を CNF に変換するのに苦労しています。

(A ∨ B) ⇔ (C ∧ D)。

私はすでに二条件消去論理規則を使用して⇔を消去しようとしました。

(A ∨ B) → (C ∧ D) ∧ (C ∧ D) → (A ∨ B)。

次に、含意消去論理規則で → を消去しました。今私が持っています

¬(A ∨ B) ∨ (C ∧ D) ∧ ¬(C ∧ D) ∨ (A ∨ B)。

私はここでかなり立ち往生しています。私の教授は、文を減らすために分布規則を使用する必要があると言います。分配性ルールの要件に一致するものを見つけることができないようです。そのため、私が知らない論理ルールを実行する前に、分配ルールを使用できないようです。

ここで何が欠けていますか？スタック オーバーフローは、CNF への変換を再開するのに役立ちますか?

4

1 に答える 1

0

次の表現で始めました。

  • (A ∨ B) ⇔ (C ∧ D)。

最初のいくつかの手順を実行しようとしました。ここでは、明確かつ正確にするために括弧を追加しました。

  • [(A ∨ B) → (C ∧ D)] ∧ [(C ∧ D) → (A ∨ B)]. (⇔の定義による)
  • [¬(A ∨ B) ∨ (C ∧ D)] ∧ [¬(C ∧ D) ∨ (A ∨ B)]. (→の定義による)

ド・モルガンの否定法則を ¬(A ∨ B) と ¬(C ∧ D) に適用します。

  • [(¬A ∧ ¬B) ∨ (C ∧ D)] ∧ [(¬C ∨ ¬D) ∨ (A ∨ B)].

右半分を簡約する：

  • [(¬A ∧ ¬B) ∨ (C ∧ D)] ∧ [¬C ∨ ¬D ∨ A ∨ B].

∧ 上の ∨ の分配法則は、X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z) と述べています。

X = (¬A ∧ ¬B)、Y = C、Z = D として、左半分に法則を適用します。

  • [((¬A ∧ ¬B) ∨ C) ∧ ((¬A ∧ ¬B) ∨ D)] ∧ [¬C ∨ ¬D ∨ A ∨ B].

左半分の 2 つの部分式に分配法則を適用します。

  • [[(¬A ∨ C) ∧ (¬B ∨ C)] ∧ [(¬A ∨ D) ∧ (¬B ∨ D)]] ∧ [¬C ∨ ¬D ∨ A ∨ B].

∧ は結合的かつ可換であるため、余分な括弧を削除します。

  • (¬A ∨ C) ∧ (¬B ∨ C) ∧ (¬A ∨ D) ∧ (¬B ∨ D) ∧ [¬C ∨ ¬D ∨ A ∨ B].

変数を並べ替えると、連言正規形 (CNF)の最終式が得られます。

  • (¬A ∨ C) ∧ (¬A ∨ D) ∧ (¬B ∨ C) ∧ (¬B ∨ D) ∧ (A ∨ B ∨ ¬C ∨ ¬D)。
于 2016-04-03T17:37:47.370 に答える