# Similarity between integer and logical operations through parity

Lets observe the parity property of integers while adding them or multiplying. It's simple to notice that when we add two numbers, the parity of the result depends on parity of summands:

x   y   x+y
-----------
E   E    E
E   O    O
O   E    O
O   O    E


(Here "E" stands for "even", and "O" for "odd"). There is an obvious similarity with logical XOR function (when oddness is taken as True).

Ox  Oy    Ox xor Oy
-------------------
F   F        F
T   F        T
F   T        T
T   T        F


(Ox and Oy means "oddness of x" and "... of y" resp.)

And the same thing is with multiplication, as it behaves like logical conjunction (AND).

And now the question is: why?

-
This fact was noticed by George Boole, about a century and a half ago: suitable logical operators behave somewhat like the familiar addition and multiplication. Since then, the area called Boolean Algebra has grown tremendously, with many applications. Congratulations on noticing the phenomenon. –  André Nicolas Sep 24 '12 at 23:09
So it's all up to strong relation between logical operations and arithmetic ones? (Assuming the former as a somewhat basis of latter) –  Andrew D. Sep 24 '12 at 23:30
Well, it may be more that one uses logical operators that have a strong analogy to arithmetic ones. For example, all of propsitional logic could be founded on a couple of operators, like implication and something else, that had no clear analogue in ordinary "algebra." So maybe it is that we have a preference for familiar patterns, and choose those (if possible) to analyze new stuff. –  André Nicolas Sep 25 '12 at 0:14

There is an isomorphism between Boolean algebras and algebras over the fields $\{0,1\}$.

Therefore calculations of parity resemble, for a very good reason, to Boolean operations on the $\{T,F\}$ Boolean algebra which is often used in mathematics.

Note that multiplication $\bmod 2$ is very much like $\lor$ (or), if either one is even (true) then the result is even (true). Addition is slightly trickier, can you find the analogue? (Hint: It's not $\land$ (and) since both $\land$ and $\lor$ are distributive over one another, which is not true for $+,\cdot$ in a field).

-

If you replace $\top$ and $\bot$ with 1 and 0, as you noticed you can apply the rules of standard arithmetic. In fact you get a complete algebraic structure. $\bot$ is the neutral element with regards to $\lor$, $\top$ the neutral element with regards to $\land$. There also laws for combining $\lor$ and $\land$: A $\lor$ (B $\land$ C) = (A $\lor$ B) $\land$ (B $\lor$ C). See http://en.wikipedia.org/wiki/Boolean_algebra_(structure) for the full details.

Another observation you made is that subsets of $\mathbb{N}$ (or $\mathbb{Z}$), can have algebraic structures on their own. In higher algebra this is an reoccuring theme. For example prime numbers, as a subset of the natural numbers have all kinds of interesting properties. The odd and even numbers are studied in modular arithmetic. For example everybody knows that a clock has it's own arithmetic: 23 hours + 2 hour = 1 hour.

Algebra is the study of these related properties across all kinds of structures. This is not only true for logical operations (Boolean algebra), but for geometry as well (algebraic geometric). The fact that all these phenomena can be studied in a formal way is one of the most important insight of modern mathematics.

-
Thanks for short excursus about topic (exactly, in the definition of algebra). As of question: I thought, there exists some other than aritmetic explanation of this relationship, but it turns out that not. –  Andrew D. Sep 24 '12 at 23:52