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.
Best Answer
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.