# Simplifying boolean expression to minimum CNF

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.

• Do you know Karnaugh map, or you want to prove it with Logical equivalence? – Manx Dec 10 '19 at 16:44
• Possibly I could simplify it to, $$(a \vee c \vee b )\wedge (a \vee \neg b \vee \neg d)$$ ? – Jude Molloy Dec 10 '19 at 16:58
• Not really, take $a\equiv\bot,b\equiv\bot,c\equiv\top,d\equiv\top$ have $(a∨c∨b)∧(a∨¬b∨¬d)\equiv\top$ and $(a∨c∨b)∧(c∨a)∧(a∨¬d)∧(¬b∨¬d)\equiv \bot$, which is counter example. – Manx Dec 10 '19 at 17:02
• I have also used a Karnaugh map to solve it although I got a different result. I should note that the question does not show the original expression. The original expression is, $$(a{\;\not\!\!\!\implies}b) \vee (c{\;\not\!\!\!\implies}d)\vee (a{\;\not\!\!\!\implies}d) \vee (b{\;\not\!\!\!\implies}d)$$ – Jude Molloy Dec 10 '19 at 17:03
• That not equivalent to your expression $(a∨c∨b)∧(c∨a)∧(a∨¬d)∧(¬b∨¬d)$, that's why you got a different result, take $a\equiv\bot,b\equiv\top,c\equiv\bot,d\equiv\bot$ gives $(a∨c∨b)∧(c∨a)∧(a∨¬d)∧(¬b∨¬d)\equiv\bot$ but your $(a\not⟹b)∨(c\not⟹d)∨(a\not⟹d)∨(b\not⟹d)$ $\equiv\top$ – Manx Dec 10 '19 at 17:09

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)$$.

\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.

\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}