將命題公式轉換爲連接標準形式（CNF）

Question

我試圖將以下兩個公式縮減爲連接形式。

我一直在使用一般的方法/公式，但我覺得它缺少重要的步驟，我做對了嗎？ https://en.wikipedia.org/wiki/Conjunctive_normal_form

Answer 1

你的第一次轉型是正確的，但你的第二個結果（而正確的轉換）是不是在CNF。此外，你正在轉向RHS公式的轉換 - 一旦你簡化它，你會得到最初的（！A和（B或C））。

要實現CNF，請將分配「乘法」應用於LHS和RHS公式，以便您的最外面的運算符變爲連詞，然後簡化內部項。請注意，這種向CNF的轉換可能會導致公式的指數增長。

要減少步驟數量，還可以通過刪除多餘（非最小）項來簡化DNF中的公式。例如。 「！A和B」是多餘的，因爲你也有「！A」，並且它們的分解簡化爲「！A」。