Introduction to Boolean Algebra
Boolean algebra is a branch of algebra where the values of variables can only be
true or
false (often denoted by 1 and 0 respectfully). We use boolean algebra in circuits, general two-valued logic (such as in mathematics), and boolean operations.
Boolean Algebra Operations
There are multiple operations in boolean algebra, but the ones we will focus on are
AND and
OR. We denote
AND through multiplication (ex:
AB) and we denote
OR through addition (ex:
A+B). These operations follow the
commutative property, meaning that the order in which we place the operands does not matter.
Truth-Tables
Whenever we have a boolean expression, we can express it as a function. Similar to
F(x) we can express a two variable function:
F(AB), where we can say our domain is
A B. Since our input values can only be
true/
false, we can create a truth-table that will show all possible cases with their inputs to the function and the result. Let's take a look at a simple two variable expression, and see how the logic gates
AND and
OR work.
Expression:
F(AB)=AB
| A |
B |
F(AB) |
| 0 |
0 |
0 |
| 0 |
1 |
0 |
| 1 |
0 |
0 |
| 1 |
1 |
1 |
Expression:
F(AB)=A+B
| A |
B |
F(A+B) |
| 0 |
0 |
0 |
| 0 |
1 |
1 |
| 1 |
0 |
1 |
| 1 |
1 |
1 |
Negation
Negation is a simple concept, as you simply flip the bit. We denote not by a line over the number, or by using
', for example
A'B, which we would read as
A not B .
Example Expression
Let's do an example and look at the truth-table for:
F(ABCD)=AB'C+BD+CD+D
| A |
B |
C |
D |
F(ABCD) |
| 0 |
0 |
0 |
0 |
0 |
| 0 |
0 |
0 |
1 |
1 |
| 0 |
0 |
1 |
0 |
0 |
| 0 |
0 |
1 |
1 |
1 |
| 0 |
1 |
0 |
0 |
0 |
| 0 |
1 |
0 |
1 |
1 |
| 0 |
1 |
1 |
0 |
0 |
| 0 |
1 |
1 |
1 |
1 |
| 1 |
0 |
0 |
0 |
0 |
| 1 |
0 |
0 |
1 |
1 |
| 1 |
0 |
1 |
0 |
1 |
| 1 |
0 |
1 |
1 |
1 |
| 1 |
1 |
0 |
0 |
0 |
| 1 |
1 |
0 |
1 |
1 |
| 1 |
1 |
1 |
0 |
0 |
| 1 |
1 |
1 |
1 |
1 |
Truth-Table Explanation & SOP Expressions
We first notice from the expression
F(ABCD) that the domain of the expression is
ABCD, so we have four variables. We then simulate all possible combinations of binary codes, in order of ascending binary value, so a total of
2^N-1, where
N is the number of variables. We then evalute each expression, taking note of the logic gates. On the right side, we have our expression result when inputted into the function. This type of expression is called
sum of product because we are summing the product of functions. The interesting property of SOP (sum of product) expressions is that if one term is true, the expression becomes true because
1+1=1 and
1+0=1. This technique becomes powerful in both Karnaugh Maps and simplifying expressions by hand.
NAND and XOR Logic Gates
There also two more logic gates that were not mentioned yet, but are not used in logic gates, and these include NAND and XOR logic gates. Also note that NOT is also considered a logic gate. Like the name suggests, NAND is
not and and XOR would be the same as OR but
1XOR1=0.