# Thread: Boolean algebra Help

1. ## Boolean algebra Help

(a∧–b) ∨ (–b∧c) ∨ (–a∧c) = (a∧–b) ∨ (–a∧c)

How can I prove this,
I tried to use the distribution law for the first/last two terms, but it doesn't seem to work. Can anyone give me some hints?

Thanks a lot

2. i can't see the symbols... but an easy way to do it is to just make a truth table out of it. you only have 3 unknowns so you only have 8 different combinations to calculate.

3. Originally Posted by r0r0trog
i can't see the symbols... but an easy way to do it is to just make a truth table out of it. you only have 3 unknowns so you only have 8 different combinations to calculate.
I am asked to use show it using algebra rules, not the truth table
Thanks anyways.

4. well, as i said, i can't see your symbols... write them as AND, NAND, OR etc and i'll see what i can do.

5. (a AND –b) OR (–b AND c) AND (–a AND c) = (a AND –b) OR (–a AND c)

Thanks for trying to help

6. Originally Posted by wxyj
$\displaystyle \left(a\wedge \neg b\right)\vee\left(\neg b\wedge c\right)\wedge\left(\neg a\wedge c\right)=\left(a\wedge \neg b\right)\vee \left(\neg a \wedge c\right)$
Thanks for trying to help
If you will remember the algebra of sets is Boolean isomorphic to sentence logic. So, this is equivalent to showing that

$\displaystyle \left(A\cap B'\right)\cup\left(B'\cap C\right)\cap\left(A'\cap C\right)=\left(A\cap B'\right)\cup\left(A'\cap C\right)$

The left side is $\displaystyle \left(A\cap B'\right)\cup\left(B'\cap C\right)=\left(A\cap\left(B'\cap C\right)\right)\cup\left(B'\cap\left(B'\cap C\right)\right)=\left(A\cap B'\cap C\right)\cup\left(B'\cap C\right)$$\displaystyle =B'\cap C So the left side is \displaystyle \left(B'\cap C\right)\cap\left(A'\cap C\right)=B'\cap A'\cap C and the right side is \displaystyle \left(A\cap B'\right)\cup\left(A'\cap C\right)=\left(A'\cup\left(A\cap B'\right)\right)\cap\left(\left(C\cup\left(A\cap B'\right)\right)\right) which equals \displaystyle \left(\left(A'\cup A\right)\cap\left(A'\cap B'\right)\right)\cap\left(\left(C\cup A\right)\cap\left(C\cap B'\right)\right)=\left(A'\cap B'\right)\cap\left(C\cap A\cap B'\right) which gives...bleh. 7. Originally Posted by Drexel28 If you will remember the algebra of sets is Boolean isomorphic to sentence logic. So, this is equivalent to showing that \displaystyle \left(A\cap B'\right)\cup\left(B'\cap C\right)\cap\left(A'\cap C\right)=\left(A\cap B'\right)\cup\left(A'\cap C\right) The left side is \displaystyle \left(A\cap B'\right)\cup\left(B'\cap C\right)=\left(A\cap\left(B'\cap C\right)\right)\cup\left(B'\cap\left(B'\cap C\right)\right)=\left(A\cap B'\cap C\right)\cup\left(B'\cap C\right)$$\displaystyle =B'\cap C$

So the left side is $\displaystyle \left(B'\cap C\right)\cap\left(A'\cap C\right)=B'\cap A'\cap C$ and the right side is $\displaystyle \left(A\cap B'\right)\cup\left(A'\cap C\right)=\left(A'\cup\left(A\cap B'\right)\right)\cap\left(\left(C\cup\left(A\cap B'\right)\right)\right)$ which equals $\displaystyle \left(\left(A'\cup A\right)\cap\left(A'\cap B'\right)\right)\cap\left(\left(C\cup A\right)\cap\left(C\cap B'\right)\right)=\left(A'\cap B'\right)\cap\left(C\cap A\cap B'\right)$ which gives...bleh.
Thanks a million for the help. that really enlightens me

8. Originally Posted by wxyj
Thanks a million for the help. that really enlightens me
Really, what you should do is go along with what I said, but remember to replace the operators of set algebra with the appropriate sentence calculus ones.

9. (a /\ -b) \/ (-b /\ c) \/ (-a /\ c) = (a /\ -b) \/ (-a /\ c)
OK, here is what I did. First I checked using truth tables that the two sides are equal. I have not constructed the whole truth table but looked at when one side is false, which means that all disjuncts are false.

Next, it's easy to see that the left-hand side is the right-hand side plus one disjunct: (-b /\ c). So we should show that adding this disjunct does not change anything. If we show that (a /\ -b) \/ (-a /\ c) = (-b /\ c) \/ X for some X, then

(a /\ -b) \/ (-b /\ c) \/ (-a /\ c) = (-b /\ c) \/ X \/ (-b /\ c) = (-b /\ c) \/ X = (a /\ -b) \/ (-a /\ c)

To show that (a /\ -b) \/ (-a /\ c) = (-b /\ c) \/ X, we can use the fact that the representation of a function as a DNF where each disjunct has all prop. letters is unique. So one has to add c to the first disjunct on the left and b to the second one, as well as a to the right-hand side. This can be done by adding c \/ -c, b \/ -b and a \/ -a and using the distributive law.

10. Originally Posted by Drexel28
If you will remember the algebra of sets is Boolean isomorphic to sentence logic. So, this is equivalent to showing that

$\displaystyle \left(A\cap B'\right)\cup\left(B'\cap C\right)\cap\left(A'\cap C\right)=\left(A\cap B'\right)\cup\left(A'\cap C\right)$

The left side is $\displaystyle \left(A\cap B'\right)\cup\left(B'\cap C\right)=\left(A\cap\left(B'\cap C\right)\right)\cup\left(B'\cap\left(B'\cap C\right)\right)=\left(A\cap B'\cap C\right)\cup\left(B'\cap C\right)$$\displaystyle =B'\cap C$

So the left side is $\displaystyle \left(B'\cap C\right)\cap\left(A'\cap C\right)=B'\cap A'\cap C$ and the right side is $\displaystyle \left(A\cap B'\right)\cup\left(A'\cap C\right)=\left(A'\cup\left(A\cap B'\right)\right)\cap\left(\left(C\cup\left(A\cap B'\right)\right)\right)$ which equals $\displaystyle \left(\left(A'\cup A\right)\cap\left(A'\cap B'\right)\right)\cap\left(\left(C\cup A\right)\cap\left(C\cap B'\right)\right)=\left(A'\cap B'\right)\cap\left(C\cap A\cap B'\right)$ which gives...bleh.

Wait, I found a few errors, it should be all three disjunctions on the left, not two disjunctions and 1 conjunction.....
VVV not VV/\

11. Originally Posted by wxyj
Wait, I found a few errors, it should be all three disjunctions on the left, not two disjunctions and 1 conjunction.....
VVV not VV/\
Then...fix it? I don't mean to sound dismissive, but this is your homework. I surely am not in a logic course.

12. Originally Posted by Drexel28
Then...fix it? I don't mean to sound dismissive, but this is your homework. I surely am not in a logic course.
lols, I did. Just that realized the thing didn't work out as expected..