8
$\begingroup$

I am new to Logical Inequalities. Please bear with me if I am inexplicably stupid.

The following is a Proven Equality:
$$AB + BC + CA = (A\oplus B)C + AB$$ I noticed that I cannot "cancel out" $AB$ from both sides of the identity, i.e.
$$BC + CA \neq (A\oplus B)C$$

In mathematical equations, we cancel out stuff all the time. For example,
$$X + 3 = Y + 3 \quad\implies\quad X = Y$$

Can this not be done with Logical Statements? Is there a reason why this is such a way?

$\endgroup$
1
  • 6
    $\begingroup$ Because in logic $+$ is disjuction, which is idempotent: $A+A=A$ for any $A$. So if we could cancel $A=0$, and everything is false. Idempotent operations are, in some sense, the opposite of invertible ones like arithmetical $+$. It is the invertibility that allows cancellation, canceling means applying the inverse on both sides. $\endgroup$
    – Conifold
    Commented May 24, 2020 at 22:38

4 Answers 4

Reset to default
8
$\begingroup$

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 $+$.

$\endgroup$
3
  • $\begingroup$ How does idempotence come into play for the set-algebraic $A \cup C = B \cup C \, \not\!\!\!\implies A = B$? $\endgroup$
    – md2perpe
    Commented May 24, 2020 at 23:23
  • 1
    $\begingroup$ @md2perpe - A simple way to see this is that the cancellation law $A+C = B + C \implies A = B$ holds if $A \cap C = \emptyset = B \cap C$. In this case, idempotence of $\cup$ cannot play any role. $\endgroup$
    – Taroccoesbrocco
    Commented May 24, 2020 at 23:42
  • $\begingroup$ Thanks for being clear in your explanation. The examples really helped! $\endgroup$
    – Hari Krishnan
    Commented May 25, 2020 at 0:47
3
$\begingroup$

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$.

$\endgroup$
2
$\begingroup$

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.

$\endgroup$
3
  • 2
    $\begingroup$ To be more precise, the problem is not the absence of a minus operation in a Boolean algebra. In set theory there is a minus operation but still you can't cancel out the same terms appearing in both side of an identity. The problem is idempotence of boolean $+$. Idempotence makes impossible to define a "minus operation" which is the inverse of $+$. $\endgroup$
    – Taroccoesbrocco
    Commented May 24, 2020 at 23:07
  • 1
    $\begingroup$ @Taroccoesbrocco. Idempotence is sufficient, but not necessary. $\endgroup$
    – md2perpe
    Commented May 24, 2020 at 23:24
  • $\begingroup$ I agree with you, idempotence is a sufficient, but not necessary, condition to make the cancellation law invalid. For instance, cross product is not idempotent but still the cancellation law doesn't hold. But here we are talking about boolean algebra and in this framework the fact that the cancellation law doesn't hold is essentially due to idempotence of boolean in $+$. $\endgroup$
    – Taroccoesbrocco
    Commented May 24, 2020 at 23:35
1
$\begingroup$

It is worth clarifying here: there is only one single rule at all times for equations: If $x=y$, then $f(x) = f(y)$, where $f$ is some mapping. Nothing more, nothing less.

What about cancellation? Isn't it true that, if $f(x) = x+ 3$, then $f(x)=f(y)$ implies $x = y$? Does this make a rule?

No. Forget it. What really happens behind this is that we define $g(x)=x-3$, so $g(f(x)) = x$. And we apply the one single rule and we get $g(f(x)) = g(f(y))$, which simplifies to $x=y$. Is that clear?

Now go ahead and find a function $g$ such that when composed with $f(x) = x \oplus A$ recovers $g(f(x))=x$. There is no such function. And this is why cancellation doesn't hold.

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .