1
$\begingroup$

I am not getting the formula below from Conjunctive Normal Form into Disjunctive Normal Form. Can anybody help me to transform it into DNF?

$(A \lor B \lor C) \land (\neg A \lor \neg C) \land (\neg A \lor \neg B)$

$\endgroup$

1 Answer 1

2
$\begingroup$

$(A \lor B \lor C) \land (\neg A \lor \neg C) \land (\neg A \lor \neg B)\iff(A \lor B \lor C) \land (\neg A \lor (\neg C \land \neg B))$

Then use distributive law on $(A \lor B \lor C):$


$[(A \lor B \lor C) \color{blue}\land \neg A]\lor [(A \lor B \lor C) \color{blue}\land (\neg C \land \neg B)]$


Then you get $(\lnot A\land B)\lor(\lnot A\land C)\lor(A\land\lnot(B\lor C))...(\text{using again distributive law over the blue})$

$\implies (\lnot A\land B)\lor(\lnot A\land C)\lor(A\land\lnot B\land\lnot C)$

$\endgroup$
5
  • $\begingroup$ There is a parenthesis missing in line one at the end. I dont understand your use of distributive law. Can you please explain it more datailed that I can follow you? $\endgroup$ Commented Oct 21, 2018 at 11:20
  • $\begingroup$ @user3352632 I edited it, is it clearer now? $\endgroup$
    – user486983
    Commented Oct 21, 2018 at 13:46
  • $\begingroup$ The line you are ending with ... would be: [(¬A∧B)∨(¬A∧C)]∨[(A∧¬(B∨C)) ∨ (B∧¬(B∨C)) ∨ (C∧¬(B∨C)) ], right? Removing negation leads to: [(¬A∧B)∨(¬A∧C)]∨[(A∧(¬B∧¬C)) ∨ (B∧(¬B∧¬C)) ∨ (C∧(¬B∧¬C)) ], right? I don't understand how you come to: [(A∧(¬B∧¬C)) ∨ (B∧(¬B∧¬C)) ∨ (C∧(¬B∧¬C)) ] <=> (¬A∧B)∨(¬A∧C)∨(A∧¬B∧¬C) ? $\endgroup$ Commented Oct 21, 2018 at 17:04
  • $\begingroup$ @user3352632 I associated terms $A\lor B\lor C$ to $A\lor (B\lor C)$ $\endgroup$
    – user486983
    Commented Oct 21, 2018 at 20:02
  • $\begingroup$ Also yours $[(¬A∧B)∨(¬A∧C)]∨[(A∧(¬B∧¬C)) ∨ (B∧(¬B∧¬C)) ∨ (C∧(¬B∧¬C)) ]$ it's correct, and it's equivalent to mine because $(B∧(¬B∧¬C))\iff F\iff(C∧(¬B∧¬C))$ and $F \lor\ watherver\iff \ wathever$, where $F$ is a contradiction. $\endgroup$
    – user486983
    Commented Oct 21, 2018 at 20:06

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .