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

Question

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?

Answer 1

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.

Answer 2

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