3

I am having serious problems whenever I try to convert a formula to CNF/DNF. My main problem is that I do not know how to simplify the formula in the end, so even though I apply the rules in a correct way and reach the end of the question, being unable to simplify (absorb etc.) and get the correct result kills me.

This is the Question Let X be a propositional logic formula, you have to find the formula in DNF and CNF that are logically equivalent to X.

((a → b) ∧ (b → c)) ∨ ((a ∧ b) → ¬c)

My 'solution';

((a → b) ∧ (b → c)) ∨ ((a ∧ b) → ¬c)

((¬a ∨ b) ∧ (¬b ∨ c)) ∨ (¬(a ∧ b) ∨ ¬c)

((¬a ∨ b) ∧ (¬b ∨ c)) ∨ (¬a ∨ ¬b ∨ ¬c) : At this stage I do not know what to do next.

Help would be great, thanks.

Brabordi
  • 31
  • Use distributive property – dani_s Jan 10 '14 at 06:09
  • There is not one "formula in DNF and CNF that are logically equivalent to X" , there are two different formulas: 1) "the formula in DNF that is logically equivalent to X" and 2) "the formula in CNF that is logically equivalent to X" . they even look different maybe this is allready enough to solve the problem GOOD LUCK – Willemien Jan 10 '14 at 23:08

3 Answers3

6

Formulas cannot generally be converted between CNF and DNF without the occasional exponential blowup in size. However, the easiest technique I know of to do the conversion is to use Karnaugh maps.

$$((a \rightarrow b) \land (b \rightarrow c)) \lor ((a \land b) \rightarrow \lnot c)$$

$$\begin {array} {c|c|c|c|c|} c\, ab & 00 & 01 & 11 & 10 \\ \hline 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 1 & 1 \\ \hline \end{array}$$

Well it's a tautology, who knew.

$$((\lnot a \lor b) \land (\lnot b \lor c)) \lor (\lnot (a \land b) \lor \lnot c)$$

Distribute and demorgans like your life depends on it.

$$(\bar a \bar b \lor \bar a c \lor b \bar b \lor bc) \lor (\bar a \lor \bar b \lor \bar c)$$

$$\bar a \bar b \lor \bar a c \lor b \bar b \lor bc \lor \bar a \lor \bar b \lor \bar c$$

$$(\bar a \lor \bar a \bar b \lor \bar a c) \lor (bc \lor \bar b \lor \bar c)$$

$$\bar a \lor \text{true}$$

$$\text{true}$$

It is a tautology...not a great example for learning karnaugh maps.

DanielV
  • 23,556
0

There is an easy way of doing this. Draw a truth table for the given expression. Then try to get DNF and CNF. This link might help you

Praveen Dinelka
  • 119
0

Let us find a DNF equivalent to $$((\neg a \vee b) \wedge (\neg b \vee c)) \vee (\neg a\vee \neg b\vee \neg c)$$

First, we use the distributive property: for all $A,B,C$, we have $(A\vee B)\wedge C \Leftrightarrow (A\wedge C) \vee (B\wedge C)$. We apply this with $A := \neg a$, $B:=b$, $C:=(\neg b\vee c)$, which yields: $$(\neg a \wedge (\neg b\vee c)) \vee (b \wedge (\neg b \vee c)) \vee \neg a\vee \neg b\vee \neg c$$

and we apply distributivity again in the first two disjuncts, which gives $$(\neg a \wedge \neg b) \vee (\neg a\wedge c) \vee (b \wedge \neg b) \vee (b\wedge c) \vee \neg a\vee \neg b\vee \neg c$$

Note that $b\wedge \neg b$ is always false, hence you can erase it without changing the meaning of the formula, which finally gives $$(\neg a \wedge \neg b) \vee (\neg a\wedge c) \vee (b\wedge c) \vee \neg a\vee \neg b\vee \neg c$$

I let you do the CNF case on your own. Here you have to use the distributivity in another way: $$(A\wedge B) \vee C \Leftrightarrow (A\vee C) \wedge (B\vee C)$$

zarathustra
  • 4,891
  • 1
    efux, if you think there are errors, please point them out in a comment. Do not just edit and expect someone else to verify. – Mårten W Jul 01 '16 at 11:49