Help - Simplifying Boolean Expressions

[sniko]

Hey,

I have a computing A-Level exam on the 13th of January and i cant get my head around Simplifying Boolean Expressions, anyway, here is a question from a past paper, if you wouldn't mind telling me how to do it, it would be much appreciated.

Many Thanks

sniko

[Djkanna]

Maybe these can help you understand.

http://www.allaboutcircuits.com/vol_4/chpt_7/5.html

http://sandbox.mc.edu/~bennet/cs110/boolalg/simple.html

[sniko]

Thanks, but i really dont have a algebra background, so i really dont understand all the A's and B's

[Zeggy]

A and B are either true (1) or false (0) values.

So for example, the expression A OR B will return true if either A or B are true.

These are the same expressions in an if statement in PHP: if (A || B) { //expression returns true } else { //false returned }

To express the outcomes of an expression, you can use a truth table: http://en.wikipedia.org/wiki/Truth_table

In your example:

A dot B is dot product so you multiply the A and B values together. If both values are true, then it's 1 * 1 = 1 = true. If a value is zero then it's 1 * 0 = 0 = false. If both values are zero then it's 0 * 0 = 0 = false.

So that part of the expression returns true only if A and B are both true.

That line above the A dot B means you take the inverse. True => false, false => true. So now the expression so far returns false only if A and B are both true, otherwise it returns true.

The next part confuses me because I've never used the + symbol in logic (just like you've probably never used the + symbol exclusively in an if statement). I'm going to assume it's the same as an OR because it makes sense: 0+0=0, 0+1=1, 1+0=1, 1+1=1.

So next, there are two simple ways to simplify the expression. You could make a truth table of the overall expression - what's the outcome if A is true and B is false, etc., and find some easier expression that fits that truth table. This is kind of a hit and miss though, and requires intuition.

The other way is to split up the expression into smaller parts (like I did above) and go through the individual expressions, and see if you can simplify them one at a time, and eventually combine them.

If you have notes, you may be able to find a list of rules for simplifying an expression. These are pretty common, such as NOT A OR NOT B => NOT(A OR B) or A -> B => (NOT A) OR B.

The NOT symbol is ¬, and all the others also have symbols, but you should be able to find them on the wikipedia article. My keyboard can't type them out here :P

[sniko]

Okay, thanks a bunch Zeggy

[Spudinski]

Just a question: Where do you guys have to learn these things? I have maths on a matric level and I have never seen this before.

Is it strictly to programming theory, or what?

[BrowserGamesFactory]

You see that at school, starting at the age of 14-15 iirc , nickson is younger so he might glue better a year on it

[Nickson]

This is pure math, programming uses this math to solve programming issues, but anything can be solved by just using math... and there is a lot more math as that too.

 

@ BGF: I recall getting that sort of math too around that age, in more as math classes too (since I followed a scientific program). But I know I recently saw it again at 18, first year of uni-college. Basically a fast crash course. Same with a lot of other stuff (like p => q, something of equivalents, pure letter-based-math), but sadly I do not know the correct names in english.

 

BTW: Simplified answer is always true (1)

Simplified:

step 1) inverse of a product is the inverse of both values in an OR (sum) and thus inverse of A*B + A becomes inverse A + inverse B + A

step 2) inverse A + A = 1 and thus our expression becomes 1 + B

step 3) it doesn't matter what the value of B is since 1 OR something is always 1 and thus always true

 

Directly calculated:

Each line below is a description on how you can calculate this, each line is separate and has it's own value in a truth table (You can check this by making a simple truth table, 2 vars means 4 possible outcomes)

Outcome 1

A = true, B = true

If A is true (1), the outcome will always be true since, in the original expression, you have x + A too.

Outcome 2

A = true, B = false

If A is true (1), the outcome will always be true since, in the original expression, you have x + A too.

Outcome 3

A = false, B = true

If A is false (0) and B is true (1), the partial expression returns false ( A * B = 0 * 1 = 0), but since you take the inverse it will be true (1)

The end result will be 1 + A which always equals true

Outcome 4

A = false, B = false

If both A and B are false (0), the outcome will also be true (1), because 0*0=0 but you take the inverse, so it's 1, 1 + A will always be true

[Zeggy]

It's called propositional calculus or propositional logic. It has ties with set theory, philosophy, computer science and maybe more.

Comp sci usage examples are sql queries (set theory) and artificial intelligence (specific facts => theorem based on facts => deduce more facts)

It's useful for proofs, theorems and inference.

I'm not really sure if it's strictly taught in only computer science courses since it's got applications in many fields.

[Nickson]

Here in Belgium, any mathematical or scientific related education in their humaniora should get these kind of math. Computer science and the a likes get it for sure.