Boolean Algebra - Simplifying to two different expressions

• Charles Henderson
In summary, the expression (B and C) or (not B and not C) or (A and (not B) and not C) can have two different results depending on the order in which the factors are factored out.
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?

Welcome to PF!

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

Charles Henderson said:
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.

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

Charles Henderson said:
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.

Charles Henderson said:
(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) ))

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

(B * C) + (~B * ~C)+ (A * C)

Sorry for my error stating the problem initially, I'm a little new to this.

Charles Henderson said:
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

PeroK said:
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.

PeroK said:
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.

PeroK said:
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.

Charles Henderson said:
(B * C) + (~B * ~C) + (A * ~B * C) ; problem correctly stated

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

(B * C) + (~B * ~C)+ (A * C)

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.

## (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!

Charles Henderson said:
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.

FactChecker
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!

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.

1. What is Boolean Algebra?

Boolean Algebra is a branch of mathematics and computer science that deals with logic and logical operations. It uses variables, logical operators, and logical statements to represent and analyze logical operations.

2. What is the purpose of simplifying Boolean expressions?

The main purpose of simplifying Boolean expressions is to reduce the complexity of logical operations and make the expressions easier to understand and evaluate. Simplification also helps in reducing the number of gates and circuits required for implementing logical operations in digital systems.

3. How do you simplify a Boolean expression?

To simplify a Boolean expression, you can use different laws and theorems of Boolean Algebra, such as the distributive law, De Morgan's law, and Boolean identities. You can also use Karnaugh maps and truth tables to find the simplest form of an expression.

4. What are the benefits of simplifying a Boolean expression?

Simplifying a Boolean expression has several benefits, including reducing the complexity of logical operations, minimizing the number of gates and circuits required for implementation, and improving the efficiency and performance of logical systems.

5. Can a Boolean expression be simplified to two different forms?

Yes, a Boolean expression can be simplified to two different forms. This is because there are different sets of laws and theorems in Boolean Algebra that can be used to simplify an expression. However, both forms will be equivalent and will produce the same output for a given set of inputs.

• Programming and Computer Science
Replies
9
Views
2K
• Introductory Physics Homework Help
Replies
4
Views
494
• Programming and Computer Science
Replies
23
Views
2K
• General Math
Replies
19
Views
2K
• Programming and Computer Science
Replies
1
Views
1K
• Programming and Computer Science
Replies
2
Views
1K
• Precalculus Mathematics Homework Help
Replies
7
Views
1K
• Quantum Physics
Replies
5
Views
1K
• Introductory Physics Homework Help
Replies
10
Views
235
• Calculus
Replies
5
Views
336