4
$\begingroup$

I have a formula

$(L\Leftrightarrow (A\vee J))$

and I am to turn it into DNF and CNF. When I use de Morgan rules and so on, the formula looks like

$(L\Rightarrow (A\vee J))\wedge ((A\vee J)\Rightarrow L)$

$(\lnot L\vee (A\vee J))\wedge ((\lnot A\wedge \lnot J)\vee L)$

the CNF is pretty easy its

$(\lnot L \vee A\vee J)\wedge (L\vee \lnot A)\wedge (L\vee \lnot J)$

But how can I make DNF out of this formula?

$\endgroup$
  • $\begingroup$ Do you mean "KNF" (as in the title) or "CNF" (Conjunctive Normal Form, as in the text)? $\endgroup$ – Rory Daulton Jan 1 '16 at 14:35
  • $\begingroup$ sorry its CNF ( but in my national language its KNF :) ) $\endgroup$ – trolkura Jan 1 '16 at 14:43
  • 1
    $\begingroup$ Do a Karnaugh map. Collect fullest lines/squares first. $\endgroup$ – Alex Jan 1 '16 at 15:02
  • 1
    $\begingroup$ See maths.usyd.edu.au/u/don/courses/math1904/lect11.pdf $\endgroup$ – Alex Jan 1 '16 at 15:03
  • $\begingroup$ i have tried it with Karnaugh maps , but didnt get the right result , could you elaborate? I havent found anything usefull in that pdf $\endgroup$ – trolkura Jan 1 '16 at 18:49
0
$\begingroup$

A simple way to calculate a DNF logically equivalent to the formula $L \Leftrightarrow (A \lor J)$ is to look at its truth table and "build" the formula corresponding to the "disjunction" of the rows for which $L \Leftrightarrow (A \lor J)$ is true.

$\begin{array}{ccccc} A & J & L & A \lor J & L \Leftrightarrow (A \lor J) \\ \mathtt{t} & \mathtt{t} & \mathtt{t} & \mathtt{t} & \mathtt{t} \\ \mathtt{t} & \mathtt{t} & \mathtt{f} & \mathtt{t} & \mathtt{f} \\ \mathtt{t} & \mathtt{f} & \mathtt{t} & \mathtt{t} & \mathtt{t} \\ \mathtt{t} & \mathtt{f} & \mathtt{f} & \mathtt{t} & \mathtt{f} \\ \mathtt{f} & \mathtt{t} & \mathtt{t} & \mathtt{t} & \mathtt{t} \\ \mathtt{f} & \mathtt{t} & \mathtt{f} & \mathtt{t} & \mathtt{f} \\ \mathtt{f} & \mathtt{f} & \mathtt{t} & \mathtt{f} & \mathtt{f} \\ \mathtt{f} & \mathtt{f} & \mathtt{f} & \mathtt{f} & \mathtt{t} \\ \end{array}$

The formula $L \Leftrightarrow (A \lor J)$ is true at rows 1 (which corresponds to the formula $A \land J \land L$), row 3 (which corresponds to the formula $A \land \lnot J \land L$), row 5 (which corresponds to the formula $\lnot A \land J \land L$), and row 8 (which corresponds to the formula $\lnot A \land \lnot J \land \lnot L$). Hence, a DNF logically equivalent to $L \Leftrightarrow (A \lor J)$ is \begin{equation*} (A \land J \land L) \lor (A \land \lnot J \land L) \lor (\lnot A \land J \land L) \lor (\lnot A \land \lnot J \land \lnot L). \end{equation*}

$\endgroup$

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.