0
$\begingroup$

I would like to know if it is possible to simplify the CNF equation. I have this equation - $$ (x_{1} \lor x_2 \lor \lnot x_3 \lor \lnot x_4) \land (x_1 \lor \lnot x_2 \lor x_3 \lor \lnot x_4) \land (x_1 \lor \lnot x_2 \lor \lnot x_3 \lor x_4) \land (x_1 \lor \lnot x_2 \lor \lnot x_3 \lor \lnot x_4) \land (\lnot x_1 \lor x_2 \lor x_3 \lor \lnot x_4) \land (\lnot x_1 \lor x_2 \lor \lnot x_3 \lor x_4) \land (\lnot x_1 \lor x_2 \lor \lnot x_3 \lor \lnot x_4) \land (\lnot x_1 \lor \lnot x_2 \lor x_3 \lor x_4) \land (\lnot x_1 \lor \lnot x_2 \lor x_3 \lor \lnot x_4) \land (\lnot x_1 \lor \lnot x_2 \lor \lnot x_3 \lor x_4) \land (\lnot x_1 \lor \lnot x_2 \lor \lnot x_3 \lor \lnot x_4) $$ Thanks for help :)

$\endgroup$
  • $\begingroup$ There are only $4$ varibles, you can try to use a k-map, after that maybe keep do the simplification with logical equivalence and you are done. $\endgroup$ – Manx Nov 26 '19 at 15:15
  • $\begingroup$ en.wikipedia.org/wiki/Karnaugh_map $\endgroup$ – jwc845 Nov 26 '19 at 15:18
  • $\begingroup$ Thanks for help :) $\endgroup$ – Raicha Nov 26 '19 at 15:28
1
$\begingroup$

$$\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&\color{red}1&\color{red}1&0&1\\ x_3'x_4&1&0&0&0\\ x_3x_4&0&0&0&0\\ x_3x_4'&1&0&0&0 \end{array}}\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&\color{orange}1&1&0&1\\ x_3'x_4&\color{orange}1&0&0&0\\ x_3x_4&0&0&0&0\\ x_3x_4'&1&0&0&0 \end{array}}\\\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&\color{blue}1&1&0&1\\ x_3'x_4&1&0&0&0\\ x_3x_4&0&0&0&0\\ x_3x_4'&\color{blue}1&0&0&0 \end{array}}\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&\color{lightgreen}1&1&0&\color{lightgreen}1\\ x_3'x_4&1&0&0&0\\ x_3x_4&0&0&0&0\\ x_3x_4'&1&0&0&0 \end{array}}$$ $$\color{red}{x_3'x_4'x_1'}+\color{orange}{x_1'x_2'x_3'}+\color{blue}{x_1'x_2'x_4'}+\color{lightgreen}{x_2'x_3'x_4'}\tag*{Minimal DNF}$$ $$\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&1&1&\color{red}0&1\\ x_3'x_4&1&0&\color{red}0&0\\ x_3x_4&0&0&\color{red}0&0\\ x_3x_4'&1&0&\color{red}0&0 \end{array}}\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&1&1&0&1\\ x_3'x_4&1&0&0&0\\ x_3x_4&\color{orange}0&\color{orange}0&\color{orange}0&\color{orange}0\\ x_3x_4'&1&0&0&0 \end{array}}\\\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&1&1&0&1\\ x_3'x_4&1&\color{blue}0&\color{blue}0&0\\ x_3x_4&0&\color{blue}0&\color{blue}0&0\\ x_3x_4'&1&0&0&0 \end{array}}\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&1&1&0&1\\ x_3'x_4&1&0&\color{lightgreen}0&\color{lightgreen}0\\ x_3x_4&0&0&\color{lightgreen}0&\color{lightgreen}0\\ x_3x_4'&1&0&0&0 \end{array}}\\\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&1&1&0&1\\ x_3'x_4&1&0&0&0\\ x_3x_4&0&\color{lightblue}0&\color{lightblue}0&0\\ x_3x_4'&1&\color{lightblue}0&\color{lightblue}0&0 \end{array}}\boxed{\begin{array}{ccccc} &x_1'x_2'&x_1'x_2&x_1x_2&x_1x_2'\\ x_3'x_4'&1&1&0&1\\ x_3'x_4&1&0&0&0\\ x_3x_4&0&0&\color{lightgrey}0&\color{lightgrey}0\\ x_3x_4'&1&0&\color{lightgrey}0&\color{lightgrey}0 \end{array}}$$ $$\begin{align} &\hspace{3ex}(\color{red}{x_1x_2})'(\color{orange}{x_3x_4})'(\color{blue}{x_2x_4})'(\color{lightgreen}{x_1x_4})'(\color{lightblue}{x_2x_3})'(\color{lightgrey}{x_1x_3})'\\ &=(x_1'+x_2')(x_3'+x_4')(x_2'+x_4')(x_1'+x_4')(x_2'+x_3')(x_1'+x_3')\tag*{Minimal CNF} \end{align}$$

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