0
$\begingroup$

I want to find the minimal CNF and DNF for the following expression: $$(A \implies C) \wedge \neg (B \wedge C \wedge D).$$ I've created a truth table:

\begin{array}{| c | c | c | c | c | c | c |} \hline A & B & C & D & \underbrace{A \implies B}_{E} & \underbrace{\neg (B \wedge C \wedge D)}_{F} & \underbrace{E \wedge F}_{G} \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ \hline 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ \hline 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ \hline 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline \end{array}

DNF: $ G = (\neg A \wedge \neg B \wedge \neg C \wedge \neg D) \vee (\neg A \wedge B \wedge \neg C \wedge \neg D) \vee (\neg A \wedge \neg B \wedge C \wedge \neg D) \vee (\neg A \wedge B \wedge \neg C \wedge D) \vee (\neg A \wedge B \wedge C \wedge \neg D) \vee ( A \wedge B \wedge C \wedge \neg D) \vee ( A \wedge \neg B \wedge \neg C \wedge D) \vee (\neg A \wedge B \wedge \neg C \wedge D) \vee (\neg A \wedge \neg B \wedge C \wedge \neg D) \vee ( A \wedge B \wedge C \wedge D) $

To shorten that, I will simplify the expression by deleting redundant expressions:

$ G=(\neg A \wedge \neg B \wedge \neg C \wedge \neg D) \vee (\neg A \wedge B \wedge \neg C \wedge \neg D) \vee (\neg A \wedge \neg B \wedge C \wedge \neg D) \vee (\neg A \wedge B \wedge \neg C \wedge D) \vee (\neg A \wedge B \wedge C \wedge \neg D) \vee ( A \wedge B \wedge C \wedge \neg D) \vee ( A \wedge \neg B \wedge \neg C \wedge D) \vee ( A \wedge B \wedge C \wedge D) $
$\vdots$
minimal DNF: $\dots$
Same procedure for CNF

CNF:
$G_2=(\neg A \vee B \vee C \vee D) \wedge (\neg A \vee \neg B \vee C \vee D) \wedge \dots \wedge (\neg A \vee \neg B \vee \neg C \vee \neg D)$
$\vdots$

How do I find the minimal CNF and CNF more easily? I could simplify those expressions like I showed above, but this is really time consuming. Is there a way to do this more efficient? If so, could you please explain in detail, how you solved the task?

|cite|improve this question
$\endgroup$
  • 2
    $\begingroup$ For up to 4 variables, and for finding DNF, you probably can't do better than a Karnaugh map. Don't know about CNF, though. $\endgroup$ – Adrian Keister Aug 29 '18 at 13:54
  • 1
    $\begingroup$ Recall that $(A\implies C)\equiv(A\lor\neg C).$ The Karnaugh map relies on Gray Code order, so that you're changing as few bits as possible, going from one row or column to the next. Then you can circle maximal sets of True's to get the minimal expression in DNF. $\endgroup$ – Adrian Keister Aug 29 '18 at 14:01
  • 1
    $\begingroup$ For DNF, I get $G=(\neg A \land \neg C)\lor(\neg B \land C)\lor(C \land \neg D).$ $\endgroup$ – Adrian Keister Aug 29 '18 at 14:08
  • 1
    $\begingroup$ The wiki article on K-maps is pretty good. Please refer to that for a more full explanation. en.wikipedia.org/wiki/Karnaugh_map $\endgroup$ – Adrian Keister Aug 29 '18 at 14:44
  • 1
    $\begingroup$ You can use the negation of G plus DeMorgan to get the CNF, by the way. $\endgroup$ – Adrian Keister Aug 29 '18 at 14:45
1
$\begingroup$

I'll do my best to type up the K-maps in MathJax. For DNF, you just go with $G$ as follows: $$ \begin{array}{c|c|c|c|c|} AB &00 &01 &11 &10 \\ \hline CD \\ \hline 00 &1 &1 &0 &0 \\ \hline 01 &1 &1 &0 &0 \\ \hline 11 &1 &0 &0 &1 \\ \hline 10 &1 &1 &1 &1 \\ \hline \end{array} $$ From this, we see that $G=(\neg A \land \neg C)\lor(\neg B\land C)\lor(C \land \neg D)$ is the minimal DNF. For CNF, we work with $\neg G$ as follows: $$ \begin{array}{c|c|c|c|c|} AB &00 &01 &11 &10 \\ \hline CD \\ \hline 00 &0 &0 &1 &1 \\ \hline 01 &0 &0 &1 &1 \\ \hline 11 &0 &1 &1 &0 \\ \hline 10 &0 &0 &0 &0 \\ \hline \end{array} $$ From this, we get that $\neg G=(A\land \neg C)\lor(B\land C\land D),$ and therefore $G=(\neg A\lor C)\land(\neg B\land \neg C\land \neg D)$ for CNF.

|cite|improve this answer
$\endgroup$
  • $\begingroup$ I tried it by msyself while you were writing this post and came to the same solution, thank you. $\endgroup$ – Doesbaddel Aug 29 '18 at 16:18
0
$\begingroup$

$(A \implies C) \wedge \neg (B \wedge C \wedge D).$

Truth table:

\begin{array}{| c | c | c | c | c | c | c |} \hline A & B & C & D & > \underbrace{A \implies B}_{E} & \underbrace{\neg (B \wedge C \wedge D)}_{F} & \underbrace{E \wedge F}_{G} \\ \hline 0 & 0 & 0 & 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 0 & 0 & 1 & 0 \\ \hline 0 & 1 & 0 & 0 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 0 & 0 & 1 & 0 \\ \hline 0 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 0 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 0 & 1 & 1 & 1 \\ \hline 1 & 1 & 1 & 0 & 1 & 1 & 1 \\ \hline 0 & 0 & 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 0 & 1 & 0 & 1 & 0 \\ \hline 0 & 1 & 0 & 1 & 1 & 1 & 1 \\ \hline 1 & 1 & 0 & 1 & 0 & 1 & 0 \\ \hline 0 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 1 & 0 & 1 & 1 & 1 & 1 & 1 \\ \hline 0 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline 1 & 1 & 1 & 1 & 1 & 0 & 0 \\ \hline \end{array}

In order to fill the Karnaugh Map, you'll need to search for all the given combinations of "Trues" in your Truth Table. Thanks to AdrianKeister for pointing out. Fill in all the gaps and extract the minimal DNF by circling all $2^k$ fields, that contain the number 1.

Karnaugh map: \begin{array}{| c | c | c |c | c | c |}\hline C & C & \neg C & \neg C \\ \hline \neg D& D & D & \neg D \\ \hline \color{yellow}{1} & \color{blue}{1} & 0 & 0 & \neg B & A\\ \hline \color{darkorange}{1} & 0 & 0 & 0 & B & A\\ \hline \color{darkorange}{1} & 0 & \color{red}{1} & \color{red}{1} & B & \neg A \\ \hline \color{yellow}{1} & \color{blue}{1} & \color{red}{1} & \color{red}{1} & \neg B & \neg A\\ \hline \end{array} Numbers in similar colors are circled. The color yellow should indicate, that two circles are overlapping each other.

The DNF is $G=(C \wedge \neg D) \vee (C \wedge \neg B) \vee (\neg A \wedge \neg C)$ or

like Adrian Keister already mentioned:

$G=(\neg A \land \neg C)\lor(\neg B \land C)\lor(C \land \neg D)$

If you want to receive the CNF, you will need to mark all $2^k$ fields that contain 0:

Karnaugh map: \begin{array}{| c | c | c |c | c | c |}\hline C & C & \neg C & \neg C \\ \hline \neg D& D & D & \neg D \\ \hline 1 & 1 & \color{blue}{0} & \color{blue}{0} & \neg B & A\\ \hline 1 & \color{red}{0} & \color{blue}{0} & \color{blue}{0} & B & A \\ \hline 1 & \color{red}{0} & 1 & 1 & B & \neg A \\ \hline 1 & 1 & 1 & 1 & \neg B & \neg A\\ \hline \end{array}

For CNF you will get $G_2=(\neg A \vee C) \wedge (\neg B \wedge C \wedge \neg D)$.

|cite|improve this answer
$\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.