CODEWITHSUNDEEP
mathlogicconjunctive-normal-formboolean-algebra
Silence
Silence

Reputation: 83

Convert this logic sentence to Conjunctive Normal Form

I am struggling to convert this sentence to CNF:

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

I have already tried to use the Biconditional elimination logic rule to eliminate the ⇔.

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

Then I eliminated the → with the Implication elimination logic rule. Now I have

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

I am pretty much stuck here. My professor says I should use Distributivity rule to reduce the sentence. I can't seem to find anything that matches the requirements of Distributivity rule. So, I can't seem to use Distributivity rule before doing some logical rule that I do not know of.

What am I missing here? Can Stack Overflow help me to resume the conversion to CNF?

Upvotes: 0

Views: 6875

Answers (1)

Nayuki
Nayuki

Reputation: 18533

You began with the expression:

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

You tried to perform the first few steps. Here I added brackets to be clear and correct:

  • [(A ∨ B) → (C ∧ D)] ∧ [(C ∧ D) → (A ∨ B)]. (by definition of ⇔)
  • [¬(A ∨ B) ∨ (C ∧ D)] ∧ [¬(C ∧ D) ∨ (A ∨ B)]. (by definition of →)

Apply the De Morgan negation law to ¬(A ∨ B) and ¬(C ∧ D):

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

Simplify the right half:

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

The distributive law for ∨ over ∧ states that: X ∨ (Y ∧ Z) ⇔ (X ∨ Y) ∧ (X ∨ Z).

We apply the law to the left half, with X = (¬A ∧ ¬B), Y = C, Z = D:

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

Apply the distributive law to two subexpressions in the left half:

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

Remove the extra brackets because ∧ is associative and commutative:

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

Rearrange the variables, and we have our final formula in conjunctive normal form (CNF):

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

Upvotes: 0

Related Questions