0
$\begingroup$

I need to prove or disprove that in any Boolean algebra: if $a+ab=b$ then $a=b=1$ or $a=b=0$.

I build the following truth table: $$ \begin{array}{|c|c|c|} \hline a & b & a+ab \\ \hline 0 & 0 & 0 \\ \hline 0 & 1 & 0 \\ \hline 1 & 0 & 1 \\ \hline 1 & 1 & 1 \\ \hline \end{array} $$ So it does looks like that theorem is true. Can I prove it with algebra? if not, How should I prove it?

Edit: You guys proved it for the binary Boolean algebra. The theorem is for every Boolean algebra (I just gave an example for binary). How can I prove it for every Boolean algebra?

$\endgroup$
2
  • $\begingroup$ Yes, the statement holds in the two-element Boolean algebra. But that's not what the exercise is asking. $\endgroup$
    – egreg
    Oct 1 '18 at 13:59
  • $\begingroup$ Look into any Boolean algebra with more than two elements (for example the four-element Boolean algebra) and check what happens if $a=b$ but they are neither $0$ nor $1$. $\endgroup$ Oct 1 '18 at 13:59
0
$\begingroup$

$a + ab = b \iff a(1+b) = b \iff a = b$

$\endgroup$
0
$\begingroup$

Adding $b+1$ to both sides of $a+ab=b$, you get $$ \require{cancel} ab+a+b+1=\underbrace{\cancel{b+b}}_{=2b=0}+1 $$ (recall a Boolean ring has characteristic 2). Thus $(1+a)(1+b)=1$. This only holds if $1+a=1+b=1$, i.e., $a=b=0$.

$\endgroup$
3
  • $\begingroup$ Looks like you're using the wrong interpretation of addition, which would make the question wrong too. In the question, as in classical logic, $+$ denotes disjunction, not XOR. $\endgroup$
    – user21820
    Oct 1 '18 at 15:15
  • $\begingroup$ Sensible people always write $\vee$ when they mean disjunction or lattice join. If $+$ means disjunction (which is illogical) then there is no point in performing the "+ab", and any a=b in any Boolean algebra works, not just =0 or =1. $\endgroup$ Oct 1 '18 at 15:24
  • $\begingroup$ Well, many introductory texts use "$+$" for disjunction in classical boolean algebra. Whether we like it or not, it is the norm at lower levels, not "$\lor$". As for "no point", many exercises have no point. Anyway, it's up to the asker to decide whether your answer is useful or not. I was just pointing out that you're not interpreting "$+$" in the question in the intended manner (as is clear from the truth-table). If you take offense with my use of "wrong" in my comment, please understand that I did not mean that your interpretation is mathematically wrong or inferior, just different. $\endgroup$
    – user21820
    Oct 1 '18 at 15:50

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.