Parity function proofing for every n>=1 using only AND, OR, 0, and 1

Question

Consider the parity function: $F_n$($x_1$, $...$ ,$x_n$) $=$ $\oplus_{i=1}^n$$x_i$ where each $x_i$ is boolean. Prove that, for every $n \ge 1$, there is no way to compute $F_n$ using only AND and OR gates, and the constants 0 and 1.

Answer 1

Let $n\ge 2$.

We assume that there is an expression $\varphi$ that does the job, and arrive at a contradiction. Using distributivity, we can express $\varphi$ as $\psi$, where $\psi$ is in disjunctive normal form.

If $1$ occurs in one of the conjunctions that make up $\psi$, and one of the variables occurs in the conjunction, the $1$ can be removed. If $1$ is the only entry in the "conjunction," then $\psi$ is true for all assignments of truth values to the $x_i$. This means that $\psi$ cannot give the parity function.

If $0$ occurs in any conjunction, that conjunction can be removed, unless $0$ occurs in every conjunction, in which case again $\psi$ cannot give the parity function.

So we can assume that neither $0$ nor $1$ occurs in $\psi$. If every conjunction in $\psi$ uses every $x_i$, it is clear that $\psi$ does not give the parity function.

So one of the conjunctions contains a certain set $S$ of variable letters, and is missing say $x_1$. Then by assigning truth value $1$ to all the variable letters in $S$, we can make the conjunction (and hence $\psi$) true. We are free to assign truth value $0$ or $1$ to $x_1$. So $\psi$ gives truth value $1$ in a situation in which an odd number of the $x_i$ is true, and also in a situation where an even number of the $x_i$ are true. Thus $\psi$ cannot give the parity function.

Answer 2

Clearly $n \ge 2$, as for $n=1$, we have $F_1(x) = x \lor 0$.

Let me define a partial order $x \le y$ iff $x_i \le y_i$ for all $i$ (that is, $\land_i ( x_i \Rightarrow y_i)$).

I will call a function $\phi$ is non-decreasing if $x \le y$ implies $\phi(x) \le \phi(y)$.

The functions $x \mapsto x_i$, $x \mapsto \lor_i x_i$ and $x \mapsto \land_i x_i$ are easily seen to be non-decreasing.

The constant functions $x \mapsto 0$, $x \mapsto 1$ are also non-decreasing.

If the functions $\phi_i$ are non-decreasing, then $x \mapsto \lor_i \phi_i(x)$ and $x \mapsto \land_i \phi_i(x)$ are non-decreasing.

Hence it follows that any function built of $\land, \lor$ will be non-decreasing.

The function $x \mapsto F_n(x,1,0,...,0) = \lnot x$ is not non-decreasing, hence cannot be constructed from $\land, \lor$.