Discrete math assignment

[nicca]

Hello! I'd be really happy if someone helps
I have the following assignment:

In the table is given a binary function of three variables


Write and implement in the MS Excel environment formulas in the functional set (AND, OR, NOT) and in a basis (1, AND, XOR) to perform f(x)

I've tried various ways to do this but it still doesn't work.

The professor has given these two tables as examples...



The only thing I managed to do was f(x) =OR(AND(NOT(F4);F5;F6;NOT(F7);F8;F9;NOT(F10);F11)) but I'm pretty sure that this isn't one of the wanted formulas.

 

[MaxWong]

We can try to brute force the answer as follows: use [imath]\neg[/imath] for not, [imath]\wedge[/imath] for and, [imath]\vee[/imath] for or and [imath]\oplus[/imath] for xor. Since the function only gives 1 for (x1, x2, x3) = (0, 0, 1), (0, 1, 0), (1, 0, 0), (1, 0, 1), (1, 1, 1), the function is:

[math] \begin{array}{rcl} f(x) &=& (\neg x_1 \wedge \neg x_2 \wedge x_3) \vee (\neg x_1 \wedge x_2 \wedge \neg x_3) \vee (x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (x_1\wedge\neg x_2 \wedge x_3) \vee (x_1 \wedge x_2\wedge x_3) \end{array} [/math]
I hope you see what I was doing there: Each pair of parentheses corresponds to one case where f(x) would give 1. We then simplify the function so it isn't that long:

[math] \begin{array}{rcl} f(x) &=& (\neg x_1 \wedge \neg x_2 \wedge x_3) \vee (\neg x_1 \wedge x_2 \wedge \neg x_3) \vee (x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (x_1\wedge\neg x_2 \wedge x_3) \vee (x_1 \wedge x_2\wedge x_3)\\ &=& (\neg x_1 \wedge \neg x_2 \wedge x_3) \vee (\neg x_1 \wedge x_2 \wedge \neg x_3) \vee (x_1 \wedge \neg x_2 \wedge \neg x_3) \vee (x_1 \wedge x_3) \end{array} [/math]
To convert this to a form with (1, AND, XOR), simply note that the first three terms is equivalent to [imath](x_1 \wedge x_2 \wedge x_3) \oplus x_1 \oplus x_2 \oplus x_3[/imath]. (You can verify it using a truth table, or find it because [imath]x_1 \oplus x_2 \oplus x_3[/imath] will give 1 when the number of 1 among [imath]x_1, x_2, x_3[/imath] is odd-numbered, then you exclude the case that all of them are 1 by taking the xor of the result of the previous step with [imath]x_1 \wedge x_2 \wedge x_3[/imath]).

So
[math] \begin{array}{rcl} f(x) &=& ((x_1 \wedge x_2 \wedge x_3) \oplus x_1 \oplus x_2 \oplus x_3) \vee (x_1 \wedge x_3) \end{array} [/math]
But note that the when first operand of the [imath]\vee[/imath] gives 1, the second must give 0 and vice versa. Because of this, we can replace [imath]\vee[/imath] by [imath]\oplus[/imath] without changing the value of the expression.

[math] \begin{array}{rcl} f(x) &=& (x_1 \wedge x_2 \wedge x_3) \oplus x_1 \oplus x_2 \oplus x_3 \oplus (x_1 \wedge x_3) \end{array} [/math]