# Find minimal DNF and CNF of a logical expression $(A \implies C) \wedge \neg (B \wedge C \wedge D).$

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?

• 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. Aug 29, 2018 at 13:54
• 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. Aug 29, 2018 at 14:01
• For DNF, I get $G=(\neg A \land \neg C)\lor(\neg B \land C)\lor(C \land \neg D).$ Aug 29, 2018 at 14:08
• The wiki article on K-maps is pretty good. Please refer to that for a more full explanation. en.wikipedia.org/wiki/Karnaugh_map Aug 29, 2018 at 14:44
• You can use the negation of G plus DeMorgan to get the CNF, by the way. Aug 29, 2018 at 14:45

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.

• I tried it by msyself while you were writing this post and came to the same solution, thank you. Aug 29, 2018 at 16:18

$(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

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