Boolean algebra Help

**wxyj** · January 10th 2010, 03:56 PM

(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

**r0r0trog** · January 10th 2010, 04:58 PM

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.

**wxyj** · January 10th 2010, 05:53 PM

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.

**r0r0trog** · January 10th 2010, 05:55 PM

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.

**wxyj** · January 10th 2010, 07:05 PM

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

Thanks for trying to help

**Drexel28** · January 10th 2010, 08:05 PM

Originally Posted by wxyj

$\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

$\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 $\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)$ $=B'\cap C$

So the left side is $\left(B'\cap C\right)\cap\left(A'\cap C\right)=B'\cap A'\cap C$ and the right side is $\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 $\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.

**wxyj** · January 10th 2010, 09:20 PM

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

$\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 $\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)$ $=B'\cap C$

So the left side is $\left(B'\cap C\right)\cap\left(A'\cap C\right)=B'\cap A'\cap C$ and the right side is $\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 $\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

**Drexel28** · January 10th 2010, 09:23 PM

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.

**emakarov** · January 11th 2010, 01:51 AM

(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.

**wxyj** · January 11th 2010, 11:43 AM

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

$\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 $\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)$ $=B'\cap C$

So the left side is $\left(B'\cap C\right)\cap\left(A'\cap C\right)=B'\cap A'\cap C$ and the right side is $\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 $\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/\

**Drexel28** · January 11th 2010, 12:38 PM

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.

**wxyj** · January 11th 2010, 01:15 PM

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..

Thread: Boolean algebra Help

LinkBack

Thread Tools

Display

Boolean algebra Help

Similar Math Help Forum Discussions

[SOLVED] Boolean Algebra

Boolean Algebra

Boolean Algebra Help

Boolean Algebra

boolean algebra

Search Tags