Introduction to Boolean Algebra
These notes form an introduction to Boolean algebra and cover the knowledge required by the BCS HEQ Certificate Examinations. We explain what Boolean algebra is and how it is used to manipulate simple expressions. A separate article looks at truth tables and gates.
Boolean algebra is the algebra of logic (technically speaking, there are an infinite
number of Boolean algebras but computer scientists are normally concerned only with
the Boolean algebra of a two-
Boolean algebra is defined as a mathematical system with a set of elements whose values are either 0 or 1, together with a set of operators (and, or, negation), and a set of axioms or rules.
The Boolean operation + is called an OR operation. The ‘+’ symbol is used because the logical OR operator behaves rather like the arithmetic addition operator. Similarly, the Boolean logical AND operator is written as a dot because it behaves like the arithmetic multiplication operation.
In Boolean algebra (A + B)×(C + D) = A×C + A×D + B×C + B×D, which is exactly the same as in conventional algebra.
By the way, in virtually all books and articles, an expression like A×C + A×D + B×(C + B×D) would be written as AC + AD + B(C + BD) without the dot operator because (like the multiplication sign) it is assumed to exist between two adjacent terms. However, I have included it in all expressions here to remind students.
An important aspect of Boolean algebra is that it has strong similarities with the conventional algebra that you learn at school; in particular, operations are both associative and commutative; for example, A ×B×C×D = B×D×C×A (commutative law) and A + B + C + D = D + A + B + C (associative law). In other words, the order in which you perform the addition (logical OR) of variables is unimportant. The same is true for multiplication/logical AND.
Moreover, in Boolean algebra the dot (AND) operator takes precedence over the plus (OR) operator; for example, A + B×C is not the same as (A + B)×C just as 5 + 2 x 3 is not the same as (5 + 2) x 3.
Boolean algebra has two constants 1 and 0 (often called true and false). A constant does not change its value.
Each element in Boolean algebra has a complement; for example, the complement of X is often written as
Note that the complement of X is obtained by negating X.
However, since it is difficult to draw over-
The complement of 0 is 1; that is, 0’ = 1
The complement of 1 is 0; that is, 1’ = 0
The complement of a complement is the original value; that is, (X’)’ = X. Similarly, 1’’ = 1 and 0’’ = 0.
NOTE:
The terms complement, negate and invert are used interchangeably. We can talk about complementing X, inverting X, or negating X. Part of the reason for this state of affairs is that Boolean algebra was derived by mathematicians but implemented by engineers.
NOTE:
Boolean algebra defines only three operators: AND, OR, NOT. Conversely, there is no subtraction operation and there is no division. In conventional algebra, the expression A + B = A + C would be solved by saying
A + B = A + C
B = A + C – A. Therefore, B = C.
In Boolean algebra, if we have A + B = A + C, we cannot say that B = C because that would require subtraction which is not defined. Similarly, if we say that A×B = A + D, we cannot say B×(A – 1) = D and B = (A – 1)/D.
Postulates of Boolean Algebra
The fundamental postulates (axioms or rules) of Boolean algebra are:
1a. X + 0 = X Identity
1b. X×1 = X
2a X + X’ = 1 Complement
2b X×X’ = 0
3a X + Y = Y + X Commutative law
3b X×Y = Y×X
4a X + (Y + Z) = (X + Y) + Z Associative law
4b X× (Y×Z) = (X×Y) ×Z
5a X + (Y×Z) = (X + Y) ×(X + Z) Distributive law
5b X× (Y + Z) = (X×Y) + (X×Z)
Of these laws, only 5a is counter-
As well as these postulates, there are several theorems of Boolean algebra that can be derived directly from the postulates. These rules are given below and there are proofs in many textbooks and web articles. Students taking the BCS Certificate course do not need to know these formal proofs. The only requirement is to be able to use the theorems to simplify Boolean expressions. Note that in any of the theorems below, X can be replaced by its complement X’ and the theorem is still valid.
Theorem 1 X×0 = 0
Theorem 2 X + 1 = 1
Theorem 3 (X + Y)’ = X’×Y’
Theorem 4 (X×Y)’ = X’ + Y’
Theorem 5 X + X×Y = X
Theorem 6 X×(X + Y) = X
Theorem 7 X + X’×Y = X + Y
Theorem 8 X×(X’ + Y) = X×Y
Theorem 9 X×Y + X×Y’ = X
Theorem 10 (X + Y) ×(X + Y’) = X
You use these theorems by looking for patterns in a Boolean expression where variables in the expression you are simplifying can be replaced by X and Y, and one of the above theorems used. Consider the following example.
F = A×B×C + A’×B×C + A×B’×C + A×B×C’
To deal with this equation, we look for ways of rearranging and factoring the expression. Here, we immediately notice that the first two (leftmost) terms have a common factor B×C. Let’s take this out and see what happens.
F = B×C×(A + A’) + A×B’×C + A×B×C’
Note the term in parentheses. This is A + A’; that is, a value and its complement. From postulate 2a we state that A + A’ = 1. If we make this substitution we get:
F = B×C×(A + A’) + A×B’×C + A×B×C’ = B×C×(1) + A×B’×C + A×B×C’ = B×C + A×B’×C + A×B×C’
If we examine this expression, we can find three ways of re-
F = B×C + A×B’×C + A×B×C’ = C×(B + A×B’) + A×B×C’
Consider the B + A×B’ term. Can we simplify it? Yes – we can use theorem 7 to write B + A×B’ = B + A. Now we can continue with:
F = C×(B + A×B’) + A×B×C’ = C×(B + A) + A×B×C’ = B×C + A×C + A×B×C’
By the way, you can write the elements of products and sums in any order. However, I try and keep them in alphabetic order to make it easier for me to see factors; for example, I would write C×B as B×C. Both these terms are equivalent but sticking to alphabetical order reduces the chance of an error when you are dealing with expressions with many terms.
NOTE that when I am using variables to represent integers I write then in the order
D,C,B,A (rather than A,B,C,D). This is a personal preference and I do it because
it makes A the least-
Again, we can find three possible re-
We can factorise the first and third or the second and third terms. Let’s try taking out the B in the first and last terms:
F = B×C + A×C + A×B×C’ = B×(C + A×C’) + A×C
Note that we can now use theorem 7 again to get
F = B×(C + A) + A×C = B×C + A×B + A×C
At this stage, we cannot find any further simplification and the expression is now in its simplest form.
NOTE 1
There are many ways of writing down Boolean equations. However, all Boolean expressions can be expressed in one of two common formats. These are sum of products form and product of sums form. These two forms are often abbreviated to SoP and PoS, respectively.
A sum of products expression is in the form of the sum (logical OR) of a series of product (AND) terms. The following is a SoP expression:
F = B×C’×D + A×B’ + A’C×D
A sum of products expression can include a term that is a single element; for example;
F = B×D + A + A’×C×D
A product of sums expression is in the form of the product (logical AND) of a series of sum (OR) terms. The following is a PoS expression:
F = (A + B + C’)×(B + D’)×(A + C + D’)
As in the case of a sum of products, a product of sums can have a single variable as a component; for example:
F = (A + B + C’)×(B + D’)×D’
The following expression is in neither a SoP form not a PoS form. In general, such a mixed format is not normally used in textbook and articles.
F = (A + C’)×(B + D’)×(A + C + B×D’) + B×C’D + A’×C×D
NOTE 2
Computer scientists tend to develop their own ways of simplifying Boolean expressions. I usually multiply out bracketed terms before applying theorems. For example, I rarely use theorem 10, (X + Y)×(X + Y’) = X, because if I encountered (A + B)×(A + B’) I would write (A + B) ×(A + B’) = A×A + A×B’ + A×B + B×B’. Since A×A = A, we can write A×A + A×B’ + A×B + B×B’ = A + A×B’ + A×B + B×B’. Because, A + A×B = A, we can write
A + A×B’ + A×B + B×B’ = A + B.B’. Finally, B×B’ = 0, which leaves us with A + B.B’= A.
NOTE 3
Negation can be applied to an individual term or to an entire expression. Consider the following example:
F = B×C’×D + A×B’ + (A’×C.D)’
Let’s write this in overbar form for the sake of clarity.
F = B×C×D + A×B + A×C×D
When an entire expression is negated, you must use theorems 3 and 4 to evaluate the result. For example, (X + Y)’ is not equal to X’ + Y’. This is probably the most common mistake made by students. The second most common mistake is to say that A×B’ + A’×B = 1. No it is not! The expression A×B’ + A’ ×B cannot be simplified; indeed, it has a special name and is called the exclusive OR of A and B. This is often written A EOR B or A XOR B and it even had its own symbol: AÅB.
Theorems 3 and 4 are known collectively as deMorgan’s theorem which states ‘to negate an expression, complement its components and change products into sums and vice versa’. Consider the following example where we negate an expression with three product terms A, B×C’, D×E×F.
F = (A + B×C’ + D×E×F)’
In order to apply deMorgan’s theorem we must invert the elements and change the operators. The three elements are A, B×C, and D×E×F and the operators are all +. Therefore, we can write:
F = (A)’ × (B×C’)’ × (D×E×F)’
Note that we now have three negated elements. One is a simple variable. The other two, (B×C) and (D×E ×F) are expressions. So, we have to apply deMorgan’s theorem a second time to these elements. This gives:
F = A’ × (B’ + C) × (D’ + E’ + F’)
Examples of Boolean Simplification
Example 1: F = A + (B×A)’
The second component (B×A)’ is negated and we must use deMorgan’s theorem (B×A)’ = B’ + A’. We can now write
F = A + (B×A)’ = A + B’ + A’
Postulate 2a says that X + X’ = 1, therefore F = A + A’ + B’ = 1 + B’
Theorem 2 says that 1 + X’ = 1, therefore F = 1 + B’ = 1.
The final result is F = 1 which means that the expression is true and independent of variables A and B.
Note also that I have gone through this example step-
Example 2: F = (A + B) × (A + C)
F = A×A + A×C + A×B + B×C
Immediately you can see that we have A×A which is A and that any other product term containing A will be redundant. Consequently, we are left with:
F = A + B×C
Example 3: F = A’×B’×C + (A×B + A×C)’
Here we have a nonstandard format. This is in neither SoP or PoS form because we have a term that is negated. We have to use deMorgan’s theorem to remove the negation (complementation) of this term; that is,
(A×B + AC)’= (A×B)’ × (A×C)’
We’ve complemented the elements and changed the OR operator to and AND operator. However, we still have negated expressions. We have to continue.
(A×B + AC)’ = (A×B)’ × (A×C)’ = (A’ + B’) × (A’ + C’)
Now, negation is applied only to single variables and we can continue:
F = A’×B’×C + (A×B + A×C)’ = A’×B’×C + (A’ + B’) × (A’ + C’)
We can immediately simplify the product of the two sums, (A’ + B’) × (A’ + C’), to get A’ + B’×C’
F = A’×B’×C + (A’ + B’) × (A’ + C’) = A’×B’×C + A’ + B’×C’
We now have a sum of products expression. However, it is not in its most simple form. We can take the A’ out of the first two terms to get:
F = A’×B’×C + A’ + B’×C’ =
Since B’×C + 1 = 1, F = A’× (B’×C + 1) + B’×C’ = A’× (1) + B’×C’ = A’ + B’×C’
The final value is F = A’ + B’×C’ which is in its most simple form.