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?
Best Answer
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.