Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Say,

$$A = C \lor (C\land D) = C \land(1\lor D) = C$$ $$A = C \lor (C\land D) = (C\lor D)\land(C\lor C) = C\land(C\lor D)$$

Now, the part I don't understand here is if we equate we get:

$$C \land (1\lor D) = C \land (C \lor D)$$

Which would imply: $$C = 1$$

I have a feeling you can't equate like that in boolean algebra, but I'm not sure. Could anyone explain this result.

Thanks

share|improve this question
    
Are you adding hypotheses to Boolean Algebra? How do you get the first equality there? –  Doug Spoonwood Aug 28 '11 at 2:30
    
@ Doug Spoonwood, It's a bit more intuitive if I use + for OR and . for AND. You then get $$A=C+C.D=C(1+D)=C$$ (the factorisation works just like normal algebra). If I OR any number with 1 or (TRUE) the result will be 1. Similarly, if I AND any number with 1 I get that number and the 1 'vanishes', resulting in the first equality. –  ajnatural Aug 28 '11 at 2:43
    
@ajnatural: That's because addition and multiplication of numbers have cancellation properties that are not enjoyed by the operators of a Boolean algebra. This is the point Ted is making in his answer. –  Zhen Lin Aug 28 '11 at 3:39
    
@ajnatural That's not what I meant. Sure, "c+c.d=c", if that's understood right. I meant how do you get "a=c+c.d"... or why are you writing that? –  Doug Spoonwood Aug 28 '11 at 4:13
    
@ajnatural More specially, why have you introduced the variable "a" here as the very first thing? –  Doug Spoonwood Aug 28 '11 at 4:15

3 Answers 3

up vote 4 down vote accepted

I don't really understand what you did in the first line (the second line looks like an application of the distributive laws for boolean algebra), but in any case, it looks like you're trying to "cancel" from both sides of an equation involving $\land$ and $\lor$. You can't do that. To take an even simpler example: Both $A = A \land A$ and $A = A \land 1$ are true. Equating, you get $$A \land A = A \land 1.$$ Everything okay so far. But you can't proceed from here to "cancel" $A$ from both sides to get $A=1$. A cancellation is usually justified by the presence of an inverse operation (e.g. the inverse of addition is subtraction, so we can subtract $a$ from both sides of $a+b=a+c$ to get $b=c$). There's no inverse for $\land$ or $\lor$ in Boolean algebra.

share|improve this answer
    
With regard to the first equality have a look at the comments on the question. Also, I thought of it more as 'equating matching coefficients' for example as you would do with the real and imaginary parts of a complex number or the coefficients of a polynomial, although from the responses I don't think this is possible in boolean algebra. –  ajnatural Aug 28 '11 at 2:48
1  
It's not even possible in ordinary algebra. 2+5=3+4 but you can't "equate matching coefficients" to conclude that 2=3 or 5=4. It's only possible under very special certain circumstances, like the ones you mention. –  Ted Aug 28 '11 at 4:54

The reason it doesn't imply $C=1$ is because if $C=0$ you can't divide by $C$.


The symbols in the OP have changed so the above might not look so natural of a response anymore. The basic idea is that if $C$ is FALSE, we have

$$\mathrm{FALSE} \land(\bullet)=\mathrm{FALSE}\land (\circ)$$

which is trivially true no matter what $\bullet$ or $\circ$ are, so you can't deduce any relationship between them, no more than you can between $x$ and $y$ in the equation

$$0\cdot x = 0\cdot y$$

On the other hand, if $C$ is TRUE, you can divide it out, which gives $C=\mathrm{TRUE}$ as originally deduced, as should be expected.

share|improve this answer

Here's another way to think about this, and Boolean Algebra. In my opinion, it's much more intuitive and much more useful. Forget about Boolean unionization "OR" as "addition" and Boolean intersection "AND" as "multiplication". Unfortunately, some book and perhaps even your teacher probably tried to explain it to you in terms of some multiplication and addition, and this interpretation can actually get traced back to Boole himself, but I digress. Sure, Boolean intersection behaves just like ordinary multiplication on {0, 1}, but, as I feel sure you know, Boolean unionization simply doesn't behave like ordinary addition on {0, 1}, since $$ (1 \lor 1)=1 $$. So, keep that in mind and that (1+1)=2 if you perhaps revert back to thinking about Boolean algebra in terms of ordinary addition and multiplication. But, of course, I suspect you want some way to think about Boolean Algebra concretely... so here goes...

Think of Boolean intersection as taking the minimum function, and think of Boolean unionization as taking the maximum function. The minimum function behaves exactly like Boolean intersection on {0, 1}, and the maximum function behaves exactly like Boolean unionization on {0, 1}. Now, you simply can't cancel things out here under this interpretation either, and it's much simpler than thinking in terms of multiplication or addition.

share|improve this answer

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

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