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?

$\endgroup$
10
  • 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, 2018 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, 2018 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, 2018 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, 2018 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, 2018 at 14:45

2 Answers 2

Reset to default
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.

$\endgroup$
1
  • $\begingroup$ I tried it by msyself while you were writing this post and came to the same solution, thank you. $\endgroup$
    – Doesbaddel
    Aug 29, 2018 at 16:18
1
$\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)$.

$\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.