Logic in Computer Science - Define inclusive XOR by induction

Question

What is the formal definition by induction for iterated exclusive or (XOR) from $i = 1$ to $n$. Thanks

This is the notation: $\bigoplus_{i=1}^n A_i$.

Answer 1

We define by induction of $n \geq 1$ the formula $\bigoplus_{i=1}^n A_i$ (given the formulas $A_1, \dots, A_n$):

• Base case ($n = 1$): $\bigoplus_{i=1}^1 A_i := A_1$.
• Inductive step: $\bigoplus_{i=1}^{n+1} A_i := (\bigoplus_{i=1}^n A_i) \oplus A_{n+1}$, where the second occurrence of $\oplus$ is the usual binary XOR operator.

Note that, since the binary $\oplus$ is associative, the inductive step can equivalently be defined as:

• Inductive step: $\bigoplus_{i=1}^{n+1} A_i := A_{1} \oplus (\bigoplus_{i=2}^{n+1} A_i) $.

Apart from the syntactical definition of $\bigoplus_{i=1}^n A_i$, its semantics is: $\bigoplus_{i=1}^n A_i$ is true if and only if an odd number of the $A_i$'s are true.