4
$\begingroup$

I was doing some homework for a course I'm taking at uni and came across an equality that I've yet to find anywhere online. I haven't located it on any enumerated lists of the properties of Boolean Algebra. Is this equality in any way significant? Why are certain properties of Boolean Algebra considered significant and others not? The equality is...

$\overline{(A\oplus \overline{B})}=(A\oplus B)$

Proof:

$\overline{(A\oplus \overline{B})} = \overline{((A\bullet B)+(\overline{A}\bullet \overline{B}))} = \overline{(A\bullet B)} \bullet \overline{(\overline{A} \bullet \overline{B})} = (\overline{A} + \overline{B}) \bullet (A + B) = (A\bullet \overline{A})+(\overline{A} \bullet B) + (\overline{B} \bullet A) + (\overline{B} \bullet B) = (\overline{A} \bullet B) + (\overline{B} \bullet A) = A \oplus B$

$\endgroup$
7
  • $\begingroup$ You made a mistake in the end(mistook $+$ for $\cdot$), if I understand your notations correctly (you should make them clearer in your post). $\endgroup$ Sep 16 '17 at 21:32
  • $\begingroup$ @Max I'm not sure I'm seeing what you're talking about. Here is a link for the truth table of the left-hand side of the equation and here is a truth table for the right-hand side of the equation. $\endgroup$
    – Zulfe
    Sep 16 '17 at 21:43
  • $\begingroup$ With $A=B$, wouldn't this yield $0=A$? I'm interpreting Oplus as "or", so maybe that's my problem. $\endgroup$
    – rschwieb
    Sep 16 '17 at 21:44
  • 1
    $\begingroup$ @rschwieb I believe $\oplus$ is exclusive or. (I had the same thought.) $\endgroup$ Sep 16 '17 at 21:44
  • 1
    $\begingroup$ Ultimately there's no deep reason why one basic identity is considered significant and another isn't. The main question is going to be, "How useful is this identity in proving results?" Commutativity gets used all the time; I've never seen this particular identity used for anything. This is of course a subjective distinction, but then there's never a claim that this wasn't subjective. $\endgroup$ Sep 16 '17 at 21:47
5
$\begingroup$

Since the Boolean statement $\bbox[gold,1pt]{(A\oplus B)}$ is true exactly when $\bbox[tan,2pt]{A\neq B}$, and $\bbox[gold,1pt]{(A\oplus\overline B)}$ exactly when $\bbox[tan,2pt]{A=B}$, therefore the identity $\bbox[gold,1pt]{\overline{(A\oplus\overline B)}=(A\oplus B)}$ holds because: $\bbox[tan,2pt]{\lnot (A=B)\iff (A\neq B)}$.

This is neither surprising nor useful enough to be considered significant the way the far more commonly used de Morgan's Dual Negation Rule is.   But still, keep it in mind.


Note on symbols:

  • $\oplus$ means "exclusive or" ($\veebar$),
  • $\bullet$ means "and" ($\land$),
  • $+$ means "or" ($\lor$), and
  • $\overline{\text{overline}}$ means "not" ($\lnot$).
$\endgroup$
1
  • $\begingroup$ I'm not sure the colour is really helping. Is the colour showing something? $\endgroup$ Sep 17 '17 at 16:09
0
$\begingroup$

Partial Answer, about why some properties may be considered important or not. To quote wikipedia about commutativity "The name is needed because there are operations, such as division and subtraction, that do not have it " so in short it may not be listed as a property of boolean algebra because it may be more general.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.