Why does $AB + BC + CA = (A\oplus B)C + AB$ not imply $BC + CA = (A\oplus B)C$ in boolean algebra?

In general, in a Boolean algebra it is not true that if equal terms appear on both sides of an equivalence, then we may "cancel" them (cancellation law). In other words, \begin{align} A+C = B + C \,\not\!\!\!\implies A = B \end{align}

Indeed, consider the case where $A = 1 = C$ and $B = 0$. Then, $A + C = 1 + 1 = 1 = 0 + 1 = 1 = B$ but $A = 1 \neq 0 = B$.

You have the phenomenon in set theory, and essentially for the same reason. To see the analogy, consider the boolean $+$ (the logical "or") as the set union $\cup$. We have have that: \begin{align} A \cup C = B \cup C \, \not\!\!\!\implies A = B \end{align} Indeed, take $A = \{a\}$, $B = \{b\}$ and $C = \{a,b\}$, with $a \neq b$. Then, $A \cup C = \{a,b\} = B \cup C$ but $A = \{a\} \neq \{b\} = B$.

The deep reason is that boolean $+$, as well as set union $\cup$, is idempotent, differently than arithmetical $+$ in natural numbers. Idempotence means that $a + a = a$ for any $a$ in your domain. This is what happens with any $a \in \{0,1\}$ and boolean $+$, as well as with any set and set union $\cup$. Idempotence makes impossible to define a "minus operation" that is the inverse of the idempotent $+$.


This is why I don't write "$+$" for or, but rather for $\operatorname{Xor}$. The $\operatorname{Xor}$ (eXclusive or) operator is better behaved.

If you set $+$ to be $\operatorname{Xor}$, you get the equivalence you wanted : $$ \varphi + \psi = \varphi + \psi' \Longleftrightarrow \psi = \psi'$$

This is because every $\varphi$ has an inverse for $\operatorname{Xor}$, namely itself since $\varphi \operatorname{Xor} \varphi = 0$.


Boolean algebra has no minus operation since the equation $X + A = B$ has no unique solution. Consider the case $A=B=1.$ Then both $X=0$ and $X=1$ are solutions.

Tags:

Logic

Boolean Algebra

Propositional Calculus

Related

Does there exists a growing sequence of simple connected regular graphs of girth $k$ ($k \geq 5$) with uniformly bounded diameter? Finding $a_{1996}$ if $\prod_{n=1}^{1996}(1+nx^{3^n})= 1+a_1x^{k_1} + a_2x^{k_2} + \cdots + a_mx^{k_m}$ Conjecture about crossing paths in $n\times n$ grid: counterexample or ideas How many whole rectangles can you catch in a grid? Why am I getting the wrong answer when I factor an $i$ out of the integrand? Find all positive integers $n$ such that $\varphi(n)$ divides $n^2 + 3$ Prove that a function between metric spaces $(X,d_{X})$ and $(Y,d_{Y})$ is continuous iff the pre-image of open sets is open Is $\infty=\sqrt[\Omega]{\omega}$ actually a thing? Understanding Fraleigh's proof of: Every finite integral domain is a field Can we find $n$ such that $3061\cdot2^n +1$ is prime? Geometry problem involving a cyclic quadrilateral and power of a point theorem? how would you prove that polynomial functions are not exponential?

Recent Posts