Results 1 to 12 of 12

Math Help - Boolean algebra Help

  1. #1
    Newbie
    Joined
    Oct 2009
    Posts
    18

    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
    Follow Math Help Forum on Facebook and Google+

  2. #2
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    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.
    Follow Math Help Forum on Facebook and Google+

  3. #3
    Newbie
    Joined
    Oct 2009
    Posts
    18
    Quote Originally Posted by r0r0trog View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  4. #4
    Junior Member
    Joined
    Nov 2008
    Posts
    55
    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.
    Follow Math Help Forum on Facebook and Google+

  5. #5
    Newbie
    Joined
    Oct 2009
    Posts
    18
    (a AND –b) OR (–b AND c) AND (–a AND c) = (a AND –b) OR (–a AND c)

    Thanks for trying to help
    Follow Math Help Forum on Facebook and Google+

  6. #6
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by wxyj View Post
    \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.
    Follow Math Help Forum on Facebook and Google+

  7. #7
    Newbie
    Joined
    Oct 2009
    Posts
    18
    Quote Originally Posted by Drexel28 View Post
    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
    Follow Math Help Forum on Facebook and Google+

  8. #8
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by wxyj View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  9. #9
    MHF Contributor
    Joined
    Oct 2009
    Posts
    5,417
    Thanks
    718
    (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.
    Follow Math Help Forum on Facebook and Google+

  10. #10
    Newbie
    Joined
    Oct 2009
    Posts
    18
    Quote Originally Posted by Drexel28 View Post
    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/\
    Follow Math Help Forum on Facebook and Google+

  11. #11
    MHF Contributor Drexel28's Avatar
    Joined
    Nov 2009
    From
    Berkeley, California
    Posts
    4,563
    Thanks
    21
    Quote Originally Posted by wxyj View Post
    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.
    Follow Math Help Forum on Facebook and Google+

  12. #12
    Newbie
    Joined
    Oct 2009
    Posts
    18
    Quote Originally Posted by Drexel28 View Post
    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..
    Follow Math Help Forum on Facebook and Google+

Similar Math Help Forum Discussions

  1. [SOLVED] Boolean Algebra
    Posted in the Discrete Math Forum
    Replies: 13
    Last Post: December 7th 2010, 06:12 PM
  2. Boolean Algebra
    Posted in the Discrete Math Forum
    Replies: 1
    Last Post: September 28th 2010, 11:18 PM
  3. Boolean Algebra Help
    Posted in the Algebra Forum
    Replies: 1
    Last Post: March 3rd 2010, 04:16 AM
  4. Boolean Algebra
    Posted in the Advanced Algebra Forum
    Replies: 2
    Last Post: February 16th 2009, 08:46 AM
  5. boolean algebra
    Posted in the Discrete Math Forum
    Replies: 0
    Last Post: January 22nd 2009, 08:57 AM

Search Tags


/mathhelpforum @mathhelpforum