Question about recursive formula for carry bit in modular addition mod $2^n$

Question

I am reading a paper and there authors defined recursively the carry bit of modular addition $\mod 2^n$. Specifically, suppose we are summing $x+y=z \mod 2^n$ and suppose $C[i]$ is the carry bit of the i-th bit in $x+y$ then $C[i+1]=x[i]\cdot y[i] \oplus(x[i]\oplus y[i])\cdot C[i]$. My question is how they reach this formula? here in Section 3 other paper with the same definition.

Answer 1

The resulting carry is $1$ exactly if at least two of the three inputs $x$, $y$, and $c$ are $1$. This is expressed by $$(x \wedge y)\vee(x \wedge c) \vee (y \wedge c).$$ Now use the following identities on the ring $\mathbb Z \pmod 2$. For any $a$ and $b$: $$\begin{eqnarray} a+a &=& 0 \\ a^2 &=& a \\ a \vee b &=& a+b+ab \\ a \wedge b &=& ab \end{eqnarray}$$

It turns out that the boolean expression above reduces to the surprisingly similar expression $$xy + xc + yc$$ which can be factored to get the requested expression $$xy + (x + y)c.$$