Boolean algebra is a type of algebra commonly used when dealing with digital logic.[1]
Recall that regular algebra has variables, which can hold any real number, and that operations such as addition, multiplication, subtraction and division can be performed on these variables. In the same way, Boolean algebra has variables, but these variables can only be set to the logical constants true and false.
Suppose we have two variables called X and Y. The three fundamental operations which can act on these variables in Boolean algebra are:
These operations can be combined to form complicated logical statements.
Naturally, computers and other pieces of electronics don't understand the notion of "true" or "false". However, digital circuits can be controlled by sending voltage through parts of the circuit, turning those parts of the circuit on and off. When a digital circuit component receives a high-voltage input (typically 3.3 or 5 volts[2]), it treats the input as a logical true value. Likewise, when the component receives a low-voltage (0 volt) input, it treats it as a logical false.
A truth table is a table which contains the results of applying a given logical expression to a set of logical variables. Truth tables are useful because they allow people to both prove that a given logical expression is mathematically correct, and to simplify complicated Boolean expressions.
Here are the truth tables for the fundamental operators in Boolean algebra:
AND
| A | B | A AND B |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
OR
| A | B | A OR B |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
NOT
| A | NOT A |
| 0 | 1 |
| 1 | 0 |
Below are some common laws that can be used to simplify and manipulate Boolean expressions. Remember that:
| Commutative Law: | AB = BA |
| A + B = B + A | |
| Associative Law: | ( A + B ) + C = A + ( B + C ) |
| Distributive Law: | A( B + C ) = AB + AC |
| De Morgan's Laws: | ( A + B )’ = A’B’ |
| ( AB )’ = A’ + B’ | |
| Double Negation: | A = (A')' |
A Karnaugh map, or K-map, is a technique used to quickly simplify Boolean algebra into a form that minimizes the amount of logical gates used when the algebraic expression is implemented.[3]
In order to generate a K-map, start with the truth table for the given Boolean expression. Suppose we have a truth table as follows:
| A | B | C | D | Output |
| 0 | 0 | 0 | 0 | 0 |
| 0 | 0 | 0 | 1 | 0 |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 | 0 |
| 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 1 | 1 | 1 | 0 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 0 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
| 1 | 1 | 0 | 1 | 0 |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 1 | 1 | 1 | 0 |
To convert this table into a K-map, we first want to split the variables into roughly equal halves. Each half is going to comprise the axis of a new table, on which we will draw a K-map. Let's take AB as one axis of our new table, and CD as the other axis.
Write out every possible combination of the variables on each axis as follows. (Note that we reverse the order of 11 and 10 - this is a notation known as Gray code, which allows us to use K-maps.) Then write the output of the combination of the variables inside the K-map - reference the image below.
After drawing the table in this format, begin circling groups of 1s according to the following guidelines:
Then, by looking at the circles you have made, you can quickly see that (in this case) the expression returns a logical true only when C is true and D is false, or when A is true and B is false. Thus a simplified Boolean expression for the given truth table would be Z = AB' + CD'.