Laws of Boolean Algebra

Boolean Algebra can be thought of as a subset or variant of ordinary Elementary Algebra. The numbers and variables in Boolean Algebra are just 0 and 1. That is, any variable, any expression, can eventually by evaluated to either 0 or 1. Example,

A
AB
A+C
A(D+EF)+BC

Note that since we are dealing with the set {0,1} here, so additions and multiplications are not the same as ordinary algebraic additions and multiplications. The addition sign denotes logical OR, and the multiplication sign denotes logical AND. There is an additional operator - the inverter, which denotes logical complement. The 'bar' over the variable is denoted by the single quotation mark:

not(A) = A'

There are differences between Boolean Algebra and Elementary Algebra in terms of the operations and laws, but a large number of laws are common to both. Example,

Commutative:

AB = BA
A+B = B+A

Distributive:

A(B+C) = AB + AC

Some common "laws" of Boolean Algebra

Most of these are not actually laws, but can be readily derived from the fundamentals. Students often misunderstood/forget how they are derived.

AND

A.0 = 0
A.1 = A
A.A = A
A.A' = 0

OR

A+0 = A
A+1 = 1
A+A = A
A+A' = 1

These are not laws/rules but basics derived from the definitions of AND and OR gate. Students who do not understand these should refer back to fundamental of AND and OR gates, their respective truth tables etc. When one input is connected to signal A, and the other input connected to 0/1/A/A', what is the output?

For example, A.A' = 0 can be seen from the AND gate's truth table:

A	B	Out=A.B
0	0	0
0	1	0
1	0	0
1	1	1

In this case, B = A', and it means we need only look at rows 2 and 3, where the two inputs are complement of each other. In both cases, the output is 0. Hence A.A' = 0.


Absorption

A+(A')B = A + B

This "law" can be proven using the following "law":

A+AB = A(1+B) = A

Hence, we replace A by the complicated version (A+AB) and factorize out B. The term (A + A')=1. Hence we have

A+(A')B = A + AB + (A')B = A + (A + A')B = A + B

Similarly,

A' + AB = A' + B

DeMorgan's Theorem

(A+B)' = A' . B'
(AB)' = A' + B'

Handling Boolean Expressions

When marking papers, I often come across mistakes on handling boolean expressions, especially those which involve the use of DeMorgan's Theorem. Students often overlook the importance of brackets, say, when changing from (A . B)' to (A' + B'). For example:





Strictly speaking, this step is already wrong!

The problem of omitting the brackets results in this kind of error.











Another example of omitting the brackets, resulting in wrong factorization.

Almost identical mistake as the one above!










This one made a mistake in factorization, even when brackets are used


Careless mistake.





Another common mistake is inconsistency when applying DeMorgan's Theorem. In the following example, the student is able to apply the theorem correctly fro single variable term, eg.

(B' . D)' = B + D'

but when it comes to a product term of 2 variables, it was neglected.








Up to here, it is still correct.

The term (C' . D) should be taken as a whole, i.e. with a bar across the whole product term.

Relating Truth Table, Boolean Expression, and Logic Circuit

Many students have difficulties relating the 3 of them together. Basically, they are interrelated. The truth table, as the name suggests, describes the input conditions under which the output is true, i.e. output = 1. From the truth table, a boolean expression can be written for the output in terms of the input variables. For every line (or row) in the truth table where the output = 1, a product term can be written from the input conditions. The final expression is then a sum of the product terms. Having the boolean expression, we can then draw the logic circuit associated with the output.

Take for example, the XOR gate. The truth table for the XOR function is defined as:


Hence, from the truth table, there are 2 lines (or rows) where output = 1:

when (A=0 and B=1) or when (A=1 and B=0).

Hence, we can write the boolean expression for the output as

Output = (A' . B) + (A . B')

where A' denotes A_bar, or A complement/inverted, and B' denotes B_bar. This form of expression is called Sum-Of-Product (SOP) expression.

The logic circuit for the XOR function is:



Notice we have defined a special symbol for the XOR function.

Given one of the three, you be able to derive the other two. Remember, they are interrelated:

1. Truth Table
2. Boolean Expression
3. Logic Circuit

An interesting website: Logic Gate Flash Animation

Digital Fundamentals Lecture Topics

Digital Fundamentals 1

Topic 1: Introductory Digital Concepts
Topic 2: Logic Gates
Topic 3: Boolean Algebra & Logic Simplification
Topic 4: Combinational Logic
Topic 5: Functional Blocks
Topic 6: Latches & Flip-flops
Topic 7: Number Systems

Digital Fundamentals 2

Topic 1: Introduction to Sequential Logic Circuits
Topic 2: Registers
Topic 3: Counters
Topic 4: Memory Devices
Topic 5: Conversion Between Digital and Analog Signals
Topic 6: IC Technology