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

Welcome to MSE. Please use MathJax (for more details see https://math.meta.stackexchange.com/questions/5020/mathjax-basic-tutorial-and-quick-reference ) — nmasanta, Nov 22 '19 at 17:25

score 1 · Accepted Answer · answered Nov 22 '19 at 17:33

1

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

answered Nov 22 '19 at 17:33

JMP

21,771

Nice idea, I like it. – Olivier Roche Nov 22 '19 at 17:36

Olivier Roche · Answer 2 · 2019-11-22T17:50:29.583

0

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)$$

edited Nov 22 '19 at 17:50

answered Nov 22 '19 at 17:34

Olivier Roche

5,319
9
16

score 0 · Answer 3 · answered Nov 22 '19 at 18:14

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.

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

3 Answers3