Simplifying boolean expression to minimum CNF

Question

I have the boolean expression,

$$(a\not\to b)\lor(c\not\to d)\lor(a\not\to d)\lor(b\not\to d)$$

Can I simplify this to,

$$ (a \vee c \vee b ) \wedge (a \vee \neg d) \wedge (\neg b \vee \neg d) $$

I am trying to create the minimum CNF.

Answer 1

Hint:

The statement $(a∨c∨b)∧(a∨¬d)∧(¬b∨¬d)$ not equivalent to:$$(a∨c∨b)∧(c∨a)∧(a∨¬d)∧(¬b∨¬d)$$For the minimum CNF, you can draw a k-map, but use Logical equivalence is actually easier in this case, the idea is use Absorption law on $(a \lor c)\land(a\lor c\lor b)$.

Answer:

\begin{align}&(a∨c∨b)∧(c∨a)∧(a∨¬d)∧(¬b∨¬d)\\\equiv&(a∨c)∧(a∨c∨b)∧(a∨¬d)∧(¬b∨¬d)\tag*{Commutative law}\\\equiv&(a∨c)∧(a∨¬d)∧(¬b∨¬d)\tag*{Absorption law}\\\end{align}

---

Update:

Hint:

Use Logical equivalence to find minimum CNF for $(a\not\to b)\lor(c\not\to d)\lor(a\not\to d)\lor(b\not\to d)$, first use conditional equivalence to express the statement with only $\{\lor,\land,\neg\}$, then just try to apply Distributive law, see what would you get.

Answer:

\begin{align}&\neg(a\to b)\lor\neg(c\to d)\lor\neg(a\to d)\lor\neg(b\to d)\\\equiv&\neg(\neg a\lor b)\lor\neg(\neg c\lor d)\lor\neg(\neg a\lor d)\lor\neg(\neg b\lor d)\tag*{Conditional equiv}\\\equiv& (a\land\neg b)\lor(c\land\neg d)\lor(a\land\neg d)\lor(b\land\neg d)\tag*{De Morgan's law}\\\equiv& (a\land\neg b)\lor(\neg d\land c)\lor(\neg d\land a)\lor(\neg d\land b)\tag*{Commutative law}\\\equiv& (a\land\neg b)\lor(\neg d\land(c\lor a\lor b))\tag*{Distributive law}\\\equiv& ((a\land\neg b)\lor\neg d)\land(c\lor a\lor b)\tag*{Associative law}\\\equiv& (a\lor\neg d)\land(\neg b\lor\neg d)\land(c\lor a\lor b)\tag*{Distributive law}\\\end{align}