Dismiss Notice
Join Physics Forums Today!
The friendliest, high quality science and math community on the planet! Everyone who loves science is here!

Boolean Algebra - Simplifying to two different expressions

  1. Jan 18, 2017 #1
    For the expression:
    (B and C) or (not B and not C) or (A and (not B) and not C)
    I get two different answers depending on the order I do the simplification.

    1. If I factor C out of the first and third terms I get (B and C) or (A and C) or (not B and not C)
    2. If I factor not B out of the second and third terms I get (B and C) or (A and not B) or (not B and not C)

    The second version is wrong according to several people and the Wolfram Boolean calculator but I can't see my mistake. Here are the steps.
    (B and C) or (not B and not C) or (A and (not B) and not C) ; problem as stated
    (B and C) or ((not B) and (not C or (C and A)) ; factored out (not B)
    (not C or (C and A)) becomes (not C or A)
    (B and C) or ((not B) and (not C or A))
    (B and C) or (not B and not C) or (not B and A) ; distribute (not B).

    Can anyone point out my error?
     
  2. jcsd
  3. Jan 18, 2017 #2

    Filip Larsen

    User Avatar
    Gold Member

    Welcome to PF!

    I think a "not C" got turned into a "C" from your first to second line.
     
  4. Jan 18, 2017 #3

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    The third factor is a subset of the second, so with an OR it is superfluous:

    If Y is a subset of X then:

    X OR Y = X

    In any case, both your answers look wrong to me. E.g. A and C should be excluded, but in both your answers it is included.
     
  5. Jan 18, 2017 #4
    Can you elaborate a little more? I'm not seeing your point.
     
  6. Jan 18, 2017 #5

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    First, one test of whether you have the correct answer is to test the case A AND C (but NOT B).

    B AND C fails

    NOT B AND NOT C fails

    A AND NOT B AND NOT C fails

    So, the case A AND C (but NOT B) must fail the overall test (I'm not sure what terminology you want to use, but hopefully this is clear enough).

    Yet, in your two possible answers this case passes the middle test, so passes the overall test. So, both your answers are wrong.

    In terms of simplification If A AND NOT B AND NOT C, then NOT B AND NOT C. So, anything that passes the third test must already have passed the second. Put another way, A AND NOT B AND NOT C is a subset of NOT B AND NOT C.

    However you look at it, the third test can be omitted without changing the overall test.

    And that gives you the answer directly.
     
  7. Jan 19, 2017 #6

    Stephen Tashi

    User Avatar
    Science Advisor

    As Filip Larsen indicated
    you should have gotten
    (B and C) or ( (not B) and ( not C or (A and not C) ))
     
  8. Jan 19, 2017 #7
    PeroK, Thanks for the input but I do not understand the Test/Pass/Fail terminology. In case there are different ways of looking at these types of problems this is a digital electronics circuit where A, B and C are input signals (logical 1 or 0, yes/no, true/false) and the AND and ORs are logic gates. The expression would be set equal to some output signal (=x) that takes on a value of 1 or 0 based on the logical combination of the input values. Answer 1 is correct as I have confirmed it using a Wolfram Boolean calculator.

    All: Argghhh. I wrote the last term wrong (the last not C should have been C). Here is the proper statement in an easier to read form (*=and, +=or, ~=not):
    (B * C) + (~B * ~C) + (A * ~B * C) ; problem correctly stated
    (B * C) + ((~B) * (~C + (A * C)) ; factored out ~B from last two terms
    (~C + (C*A)) becomes (~C or A) ; According to one of the Boolean algebra rules​
    (B * C) + ((~B) * (~C + A))
    (B * C) + (~B * ~C) + (~B * A) ; distribute (not B).

    THe confirmed correct answer is
    (B * C) + (~B * ~C)+ (A * C)

    Sorry for my error stating the problem initially, I'm a little new to this.
     
  9. Jan 19, 2017 #8

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    Answer 1 is the correct answer to a different problem from the one you originally stated! If you change the problem you generally change the correct answer!

    Note that the last term in your expression is now precisely the A AND C AND NOT B case that I highlighted as being out of sync with your possible answers!

    If you learn a bit of logic, you shouldn't have to check this with Wolfram! You can check it yourself o_O
     
  10. Jan 19, 2017 #9
    Answer 1 is the correct answer to the problem as correctly stated.

    There is no "fail". There is a truth table based on the values of B and C which can each take on values 1 or 0 for 4 possible combinations (00, 01, 10, 11). NOT B simply changes an input of 0 to 1 or an input of 1 to 0 (it's a toggle). ~B*~C means that if BOTH B=0 AND C=0 the output would be 1, all other cases the output is 0.

    This is the truth table for x = ~B*~C
    B | C | ~B | ~C | x = ~B*~C
    0 | 0 | 1 | 1 | 1 ; B = 0 so notB =1 C =0 so notC = 1, ~B * ~ C means x = 1 iff BOTH B and C are zero (~B and ~C are both 1).
    0 | 1 | 1 | 0 | 0 ; In all the other cases one or both of ~B, ~C results in a 0 so x=0
    1 | 0 | 0 | 1 | 0
    1 | 1 | 0 | 0 | 0

    The rules should allow me to simplify a complex Boolean algebra statement to its simplest form thus finding an equivalent circuit with fewer components. And just like in regular algebra I should be able to apply the rules in any order and get the same result. For some reason I get a different answer if I start by factoring out C from the first and third term than if I factor ~B out of the last two terms.

    Not helpful dude! I am here precisely to try to "learn a bit of logic". Maybe I came to the wrong place for actual help.
     
  11. Jan 19, 2017 #10

    Stephen Tashi

    User Avatar
    Science Advisor

    The two answers are logically equivalent, Your answer is not wrong.

    Answer 1: ## (B * C) + (\lnot B * \lnot C)+ (A * C)##
    Answer 2: ## (B * C) + (\lnot B * \lnot C) + (\lnot B * A) ##

    The only way an expression of the form ##(B*C) + (\lnot B* \lnot C) + X ## can be False is if ##B## and ##C## have opposite truth values. In that case the expression has the form ## 0 + X ##. If we assume ##B## and ##C## have opposite truth values then ## 0 + (A*C)## and ##0 + ( \lnot B*A)## have the same truth value.

    To derive Answer 1:
    ## (B * C) + ( \lnot B * \lnot C) + (A * \lnot B * C) = (B*C) + ( A*\lnot B*C) + (\lnot B*\lnot C) ##
    ## = C* (B + (A*\lnot B)) + (\lnot B*\lnot C)##
    ## = C*( B + A) + (\lnot B*\lnot C)##
    ## = (C*B) + (C*A) + (\lnot B*\lnot C) ##
    ## = (B*C) + (\lnot B*\lnot C) + (A*C) ##

    Finding the steps to go from Answer 2 to Answer 1 looks like a challenging problem. Of course, we could could go from Answer 2 backwards to the original problem and the forwards to Answer 1 - if we knew about the original problem!
     
  12. Jan 19, 2017 #11

    PeroK

    User Avatar
    Science Advisor
    Homework Helper
    Gold Member

    If several people trying to help on a problem you've mistyped isn't enough, then I'm not sure where you'll do better.
     
  13. Jan 19, 2017 #12
    I KNEW it had something to do with those 2 terms. I just couldn't figure out how to prove it. I just put together the whole truth table and it checks. There is only one place in the table where AC or A Not B change the result and it is on the same row. I was convinced that there was a mistake or that there HAD to be an algebraic method to get from one to the other and I guess that is not always the case.

    Thank you!
     
  14. Jan 20, 2017 #13

    FactChecker

    User Avatar
    Science Advisor
    Gold Member

    In fairly simple cases like this (with only 3 boolean variables), it is easy to make a Venn diagram to check your work. While making a Venn diagram, you would probably notice that the third term in the original post is already included in the second term. That would have helped you spot the typo in the original post.

    PS. When you see a typo like that, you might want to go back and put an edit note in the original post about the error. That will reduce confusion when people try to help you.
     
Know someone interested in this topic? Share this thread via Reddit, Google+, Twitter, or Facebook

Have something to add?
Draft saved Draft deleted



Similar Discussions: Boolean Algebra - Simplifying to two different expressions
  1. Hashtable for booleans? (Replies: 18)

Loading...