# CNF simplification

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 :)

• 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. – Manx Nov 26 '19 at 15:15
• en.wikipedia.org/wiki/Karnaugh_map – jwc845 Nov 26 '19 at 15:18
• Thanks for help :) – Raicha Nov 26 '19 at 15:28

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