# simplify boolean function

I have tried to simplify a boolean function. Unfortunately it is wrong.

Question: Where is my mistake?

$f = x_4x_2 + \overline {(x_3 + x_2)x_2 \cdot 1} + x_2 x_0$

$f= x_4 x_2 + \overline {(x_3 + x_2) x_2} + x_2 x_0$

$f = x_4 x_2 + ( \overline{x_3} \overline{x_2}) + \overline {x_2} + x_2 x_0$

$f = \overline { \overline {x_4 x_2 + (\overline {x_3} \overline{x_2}) + \overline {x_2}+ x_2 x_0}}$

$f = \overline { \overline{x_4} + \overline{x_2} (x_3 + x_2) x_2 \overline{x_2} + x_0}$

$f = \overline{ \overline{x_4}+ \overline{x_0}}$

$f = x_4x_0$

The correct solution would be:

$f = \overline {x_2} + x_0 + x_4$

• in step 3 it should be x3x2 not x3+x2 – Vladimir Cravero Mar 4 '17 at 10:25
• The negation over x3x2 at line 3 is splitted in Android EESE application, but a single line in Samsung's default web browser. The real error is how your double negation is expanded after line 4. That double negation is totally unnecessary action. – user287001 Mar 4 '17 at 12:36

The error is in line 3. It should be like this:

$$\overline{(x_3+x_2)x_2} = \overline{(x_3+x_2)} + \overline{x_2} = \overline{x_3} \cdot \overline{x_2} + \overline{x_2} = \overline{x_2} (\overline{x_3} + 1) = \overline{x_2}$$

This gives you:

$$x_4x_2 + \overline{x_2} + x_2x_0 = x_2(x_4+x_0)+\overline{x_2}$$

To simplify this, we can write:

$$\overline{\overline{x_2(x_4+x_0)+\overline{x_2}}} = \overline{(\overline{x_2}+\overline{(x_4+x_0)}) \cdot x_2} = \overline{\overline{x_2}\cdot x_2 + \overline{(x_4+x_0)} \cdot x_2} =$$ $$= \overline{0+\overline{(x_4+x_0)} \cdot x_2} = (x_4 + x_0) + \overline{x_2}$$

which is equal to $x_4 + x_0 + \overline{x_2}$.

You can always write a simple C program to see where did you go wrong.

Here you go:

#include <stdio.h>
#include <stdint.h>

int main(void) {

uint8_t byte;

/* A number of all possible combinations.
For 5 variables it would be 0b11111 etc. */
uint8_t MAX = 0b1111;

printf("x4 x3 x2 x0 | f1 f2 f3  f\n");

for (byte=0; byte<=MAX; byte++)
{
/* Get individual bits (combinations) */
uint8_t x0 = (byte & (1<<0)) >> 0; /* my x0 is your x0 */
uint8_t x1 = (byte & (1<<1)) >> 1; /* my x1 is your x2 */
uint8_t x2 = (byte & (1<<2)) >> 2; /* my x2 is your x3 */
uint8_t x3 = (byte & (1<<3)) >> 3; /* my x3 is your x4 */

/* Logic functions */
uint8_t f1 = (x3 && x1) || !((x2 || x1) && x1 && 0b1) || (x1 && x0);
uint8_t f2 = (x3 && x1) || !((x2 || x1) && x1) || (x1 && x0);
uint8_t f3 = (x3 && x1) || !(x2 && x1) || (!x1) || (x1 && x0);

/* Final solution */
uint8_t f = (!x1) || x0 || x3;

/* Print truth table */
printf(" %d  %d  %d  %d |  %d  %d  %d  %d", x3, x2, x1, x0, f1, f2, f3, f);

/* Print wrong line indicator */
if ((f2!=f1) || (f3!=f1) || (f!=f1))
printf(" <");

printf("\n");

}

return 0;
}

• Why is $\overline{x_3} \cdot \overline{x_2} + \overline{x_2} = \overline{x_2}$? – jublikon Mar 4 '17 at 11:37
• Because $\overline{x_3} \cdot \overline{x_2} + \overline{x_2} = \overline{x_2} (\overline{x_3}+1)$, and $\overline{x_3} + 1$ is always true. – Marko Gulin Mar 4 '17 at 11:40
• One last question: $x_2(x_4+x_0)+\overline{x_2}$ Why is $x_2$ removed ? I thought that $x_2 + \overline {x_2} = 1$ and both $x_2$ negated and not negated should disappear – jublikon Mar 4 '17 at 11:44
• I've expanded my answer to include a more detailed explanation. I hope this helps! – Marko Gulin Mar 4 '17 at 11:59