Google
 
Site navigation: [ Home | Theory | Java | About ]

Simplifying boolean expressions

4.2.4
Convert boolean expressions to simpler forms

 

Just like "normal" algebra and equally useful.

When parentheses (brackets) don't matter, they don't matter.

 

Somewhat similar to "multiplying out".

Makes sense to me (try a truth table to check!)

1 = true; 0 = false;

You can see this works by applying 3 then 4.

 

 

 

 

 

 

 

(NOT the individual terms. Change the sign. NOT the lot).

 

We often look for patterns that will allow the production of terms such as ( not x + x) which can then be eliminated.

This is a bit tedious and can be error prone.

 

 

Many students prefer to simplify via Karnaugh maps as it is a more visual approach.

 

 

A - sensor to detect lights left on.

B - Sensor to tell if car is left in gear

C - Sensor to detect of keys are still in ignition

P - the buzzer (alarm)

 

The truth table indicates all the possible combinations of inputs.

Notice it follows a set sequence - counts up in binary.

We are only interested in the cases where the output is a binary 1.

 

 

 

 

tautology (a)

 

Paired up 1 and 3, 2 and 4.

 

Eliminate terms in brackets using tautology (b)

Showing that this expression simplifies to A.

 

 

 

 

 

Next - an easier way?

Karnaugh Maps

 

On this page: [ expressions | using algebraic laws ]

Simplifying Expressions

The first and (for some students, most difficult) method of minimization is by use of algebra. Boolean algebra has 8 laws :

1. Commutative laws

        A + B = B + A         A . B = B . A

2. Associative laws

        A + (B + C) = (A + B) + C         A . (B . C) = (A . B) . C

3. Distributive laws

        A . (B + C) = (A . B) + (A . C)         A + (B . C) = (A + B) . (A + C)

4. Tautology laws

        (a)     A.A = A          A + A = A

        (b)     A + NOT A = 1     A . NOT A = 0

5. Absorption laws

        A + (A . B) = A         A . (A + B) = A

6. Common sense laws

        (a)     0 . A = 0     1 + A = 1

        (b)     1 . A = A     0 + A = A

        (c)     NOT 0 = 1   NOT 1 = 0

7. Double complement law

        NOT NOT A = A

8. De Morgan's law

        (NOT A + NOT B) = NOT (A . B)         (NOT A . NOT B) = NOT (A + B)

back to top

Using the laws

Given an expression, such as:

We can simplify it using the above laws.

using distributive law:

not X( not Y.Z + Y. not Z) + X( not Y.Z + Y. not Z)

associative:

( not X + X).( not Y.Z + Y. not Z)

gives         not Y.Z + Y not Z

In the context of IB problems on this topic, you will often be presented with a three-input device. For example:

Consider my car which complains by sounding a buzzer when I have left the lights on or left the car in gear (not in Park) and taken the keys out of the ignition:

diagram of car alarm system

truth table showing minterms

To simplify using algebraic laws we attempt to identify patterns which will eliminate terms. If I look at the first and third terms, for example, I see that it contains opposite A terms but that the B and not C are the same. Therefore I could eliminate A from this pair.

Similarly B can be eliminated from the second and third terms. However, either of these will leave me with a clumsy looking equation. Since I can see how to use the third term twice it can simply be aded again using the reverse of the tautology law:

              A + A = A

giving

not a b not c or a not b not c or a b not c or a b not c

now we can pair up:

b not c open bracket not a or a close bracket or a not C open bracket not b or b close bracket

and eliminate:

b not c or a not c

One more example for good measure:

reduction of a open bracket b or c close bracket or a open bracket not c or not b close bracket to a

back to top

related: [ Topic 4 home | previous: truth tables | next: Karnaugh maps ]

is also known as "minimization" since we are trying to reduce the number of variables (and therefore gates in a circuit).


 
The site is partly financed by advertising revenue, partly by online teaching activities and partly by donations. If you or your organisation feel these resouces have been useful to you, please consider a donation, $9.95 is suggested. Please report any issues with the site, such as broken links, via the feedback page, thanks.

Questions or problems related to this web site should be addressed to Richard Jones who asserts his right to be identified as the author and owner of these materials - unless otherwise indicated. Please feel free to use the material presented here and to create links to it for non-commercial purposes; an acknowledgement of the source is required by the Creative Commons licence. Use of materials from this site is conditional upon your having read the additional terms of use on the about page and the Creative Commons Licence. View privacy policy.

Creative Commons License


This work is licensed under a Creative Commons Attribution-NonCommercial-ShareAlike 2.5 License. © 2001 - 2009 Richard Jones, PO BOX 246, Cambridge, New Zealand;
This page was last modified: October 28, 2013