0
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Do you know Karnaugh map, or you want to prove it with Logical equivalence? $\endgroup$ – Manx Dec 10 '19 at 16:44
  • $\begingroup$ Possibly I could simplify it to, $$ (a \vee c \vee b )\wedge (a \vee \neg b \vee \neg d) $$ ? $\endgroup$ – Jude Molloy Dec 10 '19 at 16:58
  • 1
    $\begingroup$ 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. $\endgroup$ – Manx Dec 10 '19 at 17:02
  • $\begingroup$ 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)$$ $\endgroup$ – Jude Molloy Dec 10 '19 at 17:03
  • 1
    $\begingroup$ 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$ $\endgroup$ – Manx Dec 10 '19 at 17:09
1
$\begingroup$

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}

$\endgroup$
  • $\begingroup$ Thank you. That helped a lot. :) $\endgroup$ – Jude Molloy Dec 10 '19 at 18:15

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.