0
$\begingroup$

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

  • 0
    Sorry, should have explained better. That was an example of the concept I was trying to understand, it was meant more as Say, A = C + CD.... you get this result and that result and if I equate them I get...etc.2011-08-28

3 Answers 3

4

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.

  • 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.2011-08-28
2

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.

1

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.