2

The following boolean expression in CNF form

$$ (x \lor y) \land (x \lor \lnot z) $$

Has been mapped into the Karnaugh map below

\begin{array}{| c | c | c | c | c |} \hline - & yz & y\lnot z & \lnot y \lnot z & \lnot y z \\ \hline x & 1 & 1 & 1 & 1 \\ \hline \lnot x & 0 & 1 & 0 & 0 \\ \hline \end{array}

How can I get the DNF from this Karnaugh map?

olfek
  • 221

1 Answers1

1

Any covering that includes the 1s and nothing else will give you a correct DNF.

So you could do each of the 5 individually:

$$xyz \lor xyz' \lor xy'z' \lor xy'z \lor x'yz'$$

Or you could do the top left 2, top right 2, and bottom 1:

$$xy \lor xy' \lor x'yz'$$

Or you could do the entire top row and the entire second column:

$$x \lor yz'$$

Which is the minimal DNF.

DanielV
  • 23,556
  • Slightly off topic, but from the map, how would I derive the original CNF expression? – olfek Apr 13 '17 at 23:57
  • 1
    @sudoman Cover the zeros and negate it. So the bottom 2 corners are covered by $x'z$ and the bottom right is covered by $x'y'$, so $(x'z \lor x'y')'$ which is $(x \lor z')(x \lor y)$. – DanielV Apr 14 '17 at 01:04