Boolean Algebra - Simplifying to two different expressions

[Charles Henderson]

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?

 

[Filip Larsen]

Welcome to PF!

I think a "not C" got turned into a "C" from your first to second line.

 

[PeroK]

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?

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.

 

[Charles Henderson]

Can you elaborate a little more? I'm not seeing your point.

 

[PeroK]

Can you elaborate a little more? I'm not seeing your point.

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.

 

[Stephen Tashi]

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

As Filip Larsen indicated
you should have gotten
(B and C) or ( (not B) and ( not C or (A and not C) ))

 

[Charles Henderson]

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.

 

[PeroK]

Answer 1 is correct as I have confirmed it using a Wolfram Boolean calculator.

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

 

[Charles Henderson]

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!

Answer 1 is the correct answer to the problem as correctly stated.

B AND C fails

NOT B AND NOT C fails

A AND NOT B AND NOT C fails

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.

If you learn a bit of logic, you shouldn't have to check this with Wolfram! You can check it yourself

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.

 

[Stephen Tashi]

(B * C) + (~B * ~C) + (A * ~B * C) ; problem correctly stated

(B * C) + (~B * ~C) + (~B * A) ; distribute (not B).

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

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!

 

[PeroK]

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.

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.

 

[Charles Henderson]

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!

 

[FactChecker]

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.