Is it possible to convert boolean operations to addition/multiplication modulo $2$?

Question

I mean, is it possible to convert AND OR NOT to simple algebraic expressions?

If it's not possible, how do you prove it?

Answer 1

I would assume that the "boolean operations" you mentioned are "boolean functions", i.e. functions of the form $f:\{0, 1\}^{k} \to \{0, 1\}$. Any boolean function can be expressed as a combination of NAND gates (which is called functional completeness of NAND gate), and we have $\mathrm{NAND}(x, y) = 1 - xy$, so it is possible.

Answer 2

Sure, classic Boolean logic is equivalent to operations on $\mathbb Z_2$. You might be aware that $\land,\mathrm{xor}$ similar to $\cup,\triangle$ on sets create the structure of a ring.

But there is up to isomorphy only one ring with to elements, which is $\mathbb Z_2$. In fact we can easily see $\land\sim +$ and $\mathrm{xor} \sim \cdot$: $a+b = 1$ exactly if either $a=1$ or $b=1$ but not both. $a\cdot b = 1$ exactly if $a=1$ and $b=1$.

Furthermore we can also easily see that $\lnot$ corresponds to $+1$.

This suffices to express any other possible logical operation:

$a\lor b = \lnot(\lnot a \land \lnot b) \sim 1 + ((1+a)(1+b)) = ab + a + b \sim (a\land b) \,\mathrm{xor}\, a \,\mathrm{xor}\, b $

$a\rightarrow b = \lnot a \lor b \sim (1+a)b + (1+a) + b = ab + a + 1$

and so on.