# Example of a boolean function

Is there an example of real polynomial representation of a Boolean function with $4$ variables whose polynomial degree is $2$ that depends on $4$ variables?

• $a\text{ and }b \:\: \text{ xor } \:\: c\text{ and }d \;\;\;\;\;\;\;$ – user12859 Jan 13 '15 at 6:01
• $a\hspace{-0.03 in}\cdot \hspace{-0.03 in}b \; + \; c\hspace{-0.03 in}\cdot \hspace{-0.03 in}d \;\;\;\;$ – user12859 Jan 13 '15 at 6:08
• $a=b=c=d=1$ gives $2$ as value. This cannot be right as Boolean function have $0/1$ value. – Bread Winner Jan 13 '15 at 6:09
• GF(2) $\;$ – user12859 Jan 13 '15 at 6:10
• Corrected question to real polynomial. – Bread Winner Jan 13 '15 at 6:11

## 1 Answer

Yes. Using the convention that inputs and outputs are $\pm 1$, then the function is $$\frac{a(x+y)+b(x-y)}{2}.$$ You could have found this function using exhaustive search – there are only $2^{16}$ functions on $4$ variables.

• Is there a computer program which does this trick? – Bread Winner Jan 13 '15 at 22:45
• Yes, a computer program which you write. I actually wrote it once, which is how I found this function in the first place. – Yuval Filmus Jan 13 '15 at 22:46
• Interesting so some examples could be found by brute force. – Bread Winner Jan 13 '15 at 22:47