When does Exclusive Or, ⊕, automatically become Inclusive Or?
Is X⊕ ¬X ≡ X ∨ ¬X ?
Anyways, without doing all the algebra and operations at the link below, how can I determine or see - by inspection - whether an Exclusive Or (⊕) can be simplified to an Inclusive Or? To wit, when does ⊕ imply Inclusive Or?
I am dodging algebra, as I am assuming that the poster (his name is poop man in the quote above) intuited that he can simplify the ⊕ in
(A ∧ ¬ B) ⊕ (¬ A ∧ C)
to an inclusive Or.
To wit, poop man started from intuition, then worked on the algebra. I'm assuming that he didn't dive head first into all that algebra, without any inkling or intuition whether he can simplify ⊕ into an inclusive-or.
2 answers
Your equivalence is rather silly since both sides are constants. More completely:
A and ¬A = 0
A nand ¬A = 1
A or ¬A = 1
A nor ¬A = 0
A xor ¬A = 1
You can just as well ask when XOR becomes NAND, or when AND becomes NOR, since they have the same values in the cases above. Or since
2 + 2 = 4
2 * 2 = 4
when does addition become multiplication?
Finding an instance where the result of two different operations happens to result in the same value doesn't mean much at all.
0 comment threads
Exclusive or ("one or the other, and not both") is the same as inclusive or ("one or the other, or both") when the operands are not both true.
Consider the truth tables:
| $A$ | $B$ | $A \oplus B$ | $A \lor B$ | $A \oplus B = A \lor B$ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 1 | 0 | 0 |
From this, we see that $A \oplus B = A \lor B \iff ¬(A \land B)$. We can test this condition against your two examples:
- \begin{align}¬(X \land ¬X) &\iff ¬0 \\&\iff 1\end{align}
- \begin{align}¬((A \land ¬B) \land (¬A \land C)) &\iff ¬(A \land ¬B \land ¬A \land C) \\&\iff ¬((A \land ¬A) \land ¬B \land C) \\&\iff ¬(0 \land ¬B \land C) \\&\iff ¬0 \\&\iff 1\end{align}
Therefore, the simplification is valid in both cases.
As observed by Olin Lathrop, we can perform the same calculation with other operations, to find the conditions under which they can be simplified to each other. This is not a particularly sophisticated trick, but it can be useful if you wish to avoid exhaustive case analysis.
0 comment threads
1 comment thread