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$.
$\begingroup$
$\endgroup$
3
-
$\begingroup$ Please, use MathJax (i.e. LaTeX commands) for mathematical notaitons. $\endgroup$– TaroccoesbroccoCommented Mar 31, 2018 at 18:32
-
$\begingroup$ What do you want to define? The formula $\bigoplus_{i=2}^n A_i$ or its truth table? $\endgroup$– TaroccoesbroccoCommented Mar 31, 2018 at 18:41
-
$\begingroup$ The formula, except from i = 1. $\endgroup$– MiraclefruitCommented Mar 31, 2018 at 18:42
Add a comment
|
1 Answer
$\begingroup$
$\endgroup$
5
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.
answered Mar 31, 2018 at 18:55
-
$\begingroup$ The semantics you claim in the last paragraph does not agree with your recursive definition. The recursive definition makes $\bigoplus_i A_i$ true if and only if an odd number of the $A_i$s are true. $\endgroup$ Commented Mar 31, 2018 at 19:13
-
$\begingroup$ Are you sure that it's true when exact one of the terms is true? I would have thought it would be when an odd number of terms is true, that is 1+1+1=1 $\endgroup$– EddyCommented Mar 31, 2018 at 19:16
-
$\begingroup$ @HenningMakholm - Of course, you're right! I fixed it, thank you. $\endgroup$ Commented Mar 31, 2018 at 19:17
-
$\begingroup$ @Taroccoesbrocco thank you! I was having trouble defining this with the notations $\endgroup$ Commented Mar 31, 2018 at 19:29
-
1$\begingroup$ It is probably worth noting that there is nothing special about $\oplus$ happening here. This recursive definition works for any associative binary operation, e.g. $+$ and $\sum$. We can further extend it to the $n=0$ case if that operation has a unit which $\oplus$ does, namely falsity/$0$. $\endgroup$ Commented Apr 1, 2018 at 2:09