Logic formula satisfied when number of positive boolean-variables in a list is even

Question

Having a list of boolean variables $(x_1, x_2, ..., x_n)$

I wonder if it would be possible to create a boolean logical formula (using and, or, not) that returns true if the number of true values in the variable list is even?

Example

$P([0,0,1,1,1]) = false$

$P([1,0,1,0,0]) = true$

Thanks

Answer 1

Use $\lnot (x_1 \oplus x_2 \oplus \dots \oplus x_n)$ where $\oplus$ is the XOR operation.

Answer 2

This can be achieved with the following formula :

$$\phi(x_1,\dots,x_n) := \bigvee_{A \subseteq \{1;\dots,n\}, \,|A| \textrm{ even}} \Big(\bigwedge_{i\in A} x_i \wedge \bigwedge_{i\notin A} \neg x_i\Big)$$

Answer 3

You can do

$$\neg x_1 \leftrightarrow \neg x_2 \leftrightarrow ... \leftrightarrow \neg x_n$$

The $\leftrightarrow$ is associative, and hence you can have a 'generalized biconditional' that can take any number of terms. And, it is easy to show that such a generalized biconditional is true if and only if an even number of its terms are false.