Boolean Algebra - Boolean Expressions and the Digital Circuits

In the previous tutorial, various logic gates and their construction was discussed. In the tutorial – Boolean Logic Operations, it was discussed that how by performing logical operations on binary data, arithmetic operations can be executed. In a digital circuit, many logic gates are interconnected along with registers and memory elements to carry out a complex computation task. Any computational problem can be expressed as a boolean function or boolean expression.

A boolean expression takes into account the boolean variables (that can be seen as individual binary data sources) and represent mathematical relationship (in the form of addition and multiplication) between them. The mathematical operations like division and subtraction are executed by multiplication and addition itself. Like, subtraction can be implemented by addition with the complement and division can be implemented by multiplication of divisor by a factor and subtraction.

The boolean functions or expressions follow a set of mathematical rules which are collectively called boolean algebra. The various theorems of boolean algebra are helpful to minimize a boolean function. In order to design an optimized digital circuit (minimum number of logic gates to solve a specific computational problem), a boolean expression must be minimized. So, let us begin with basic theorems and postulates of boolean algebra.

Huntington Postulates –

Boolean Algebra was developed by George Boole in the year 1854. In 1904, E. V. Huntington formulated various postulates that must be satisfied by a boolean algebraic system. These postulates are as follow –

1) Closure – If a boolean expression involves certain variables that belong a set say S, then set S is closed with respect to a binary operator if for every pair of elements of S, the binary operator specifies rules to obtain a unique element of S. In other words, if a boolean function involves certain boolean variables, then the variables as well as the result of the boolean expression must belong to a common set of elements. Any boolean expression always follow closure with respect to binary addition (+ operator) and binary multiplication (. operator).

2) Identity – A set is said to have an identity element for an operator (like *) if there exists an element say e in the set such that e belongs the set and multiplication of e with any other element result into the same element i.e. if x also belongs to same set, then x*e = e*x = x. In a boolean system, the identity element with respect to binary addition is 0 as for any boolean variable say x, x + 0 = 0 + x = x. Similarly, the identity element with respect to binary multiplication is 1 as for any boolean variable say x, x.1 = 1.x = x.

3) Commutative – Any boolean expression is commutative with respect to binary addition as well as binary multiplication. Like if there are two boolean variables – x and y, then x + y = y + x. Similarly, x.y = y.x.

4) Associative – Any boolean expression is also associative with respect to binary addition as well as binary multiplication. Like if there are three boolean variables – x, y and z, then x + (y + z) = (x + y) + z. Similarly, x.(y.z) = (x.y).z.

5) Distributive – In boolean algebra, binary addition is distributive over binary multiplication and binary multiplication is distributive over binary addition. So, if there are three boolean variables – x, y and z, then x.(y + z) = (x.y) + (x.z). Similarly, x+(y.z) = (x+y). (x+z).

6) Inverse – The boolean algebra does not have additive or multiplicative inverse as there are no subtraction and division operations in boolean algebra. Though, any boolean element say x, has a complement x’ such that x + x’ = 1 and x.x’ = 0.

The associative law is not a Huntington postulate, but it is valid for boolean algebra. It should also be noted that boolean algebra has + operator distributive over . operator. This is different from laws in ordinary algebra. It is also worth noting that boolean algebra has complement but not inverse. The boolean algebra used in digital electronics is a two-valued boolean algebra. It is defined over a set say B which has only two elements – (0, 1). All the above mentioned postulates are valid in the two-valued boolean algebra as follow –

1) Closure – The result of any boolean expression is either 0 or 1. So, it follow closure law with respect to the set (0, 1).

2) Identity – The 0 is identity element with respect to binary addition as for any boolean variable say x, 0 + x = x + 0 = x. If x = 0, then 0 + 0 = 0 + 0 = 0. If x is 1, then 0 + 1 = 1 + 0 = 1. The 1 is identity element with respect to the binary multiplication as for any boolean variable say x, 1.x = x.1 = x. if x = 0, then 1.0 = 0.1 = 0. if x = 1, then 1.1 = 1.1 = 1.

3) Inverse – The complement of 0 is 1 and the complement of 1 is 0. On binary addition, 0 + 1 = 1 and on binary multiplication, 0.1 = 0. For any boolean variable say x, x + x’ = 1 and x.x’ = 0.

Principle of Duality –

Duality is an important property of boolean algebra. According to this property, any boolean expression, deducible by the postulates of boolean algebra (Huntington Postulates along with associative property), remains same if the operator and identity elements are interchanged. So, dual of a boolean expression can be obtained by interchanging AND and OR operators and replacing all 1’s by 0’s and 0’s by 1’s.

Boolean Theorems –

Any boolean expression is deducible by the following theorems –

Theorem 1 – For any boolean variable x, x + x = x and x.x = x. Suppose, if x = 0, then 0 + 0 = 0 and 0.0 = 0. If x = 1, then 1 + 1 = 1 and 1.1 = 1.

Theorem 2 – For any boolean variable x, x + 1 = 1 and x.0 = 0. Suppose, if x = 0, then 0 + 1 = 1 and 0.0 = 0. If x = 1, then 1 + 1 = 1 and 1.0 = 0.

Theorem 3 (Involution) – For any boolean variable x, (x’)’ = x. Suppose, x = 0, then (0′)’ = 1′ = 0. If x = 1, then (1′)’ = 0′ = 1.

Theorem 4 (associative) – For any boolean variables x, y and z, x + (y + z) = (x + y) + z and x . (y . z) = (x . y) . z.

Theorem 5 (DeMorgan Theorem) – This theorem states duality law for boolean algebra. For any boolean variables x and y, (x + y)’ = x’ . y’ and (x.y)’ = x’ + y’.

Theorem 6 (Absorption) – For any boolean variables x and y, x + (x . y) = x and x . (x + y) = x. This can be proved as follow –

x + (x . y) = (x . 1) + (x . y)

= x (1 + y)

= x . 1

= x

Similarly,

x . (x + y) = (x . x) + (x . y)

= x + (x . y)

= (x . 1) + (x . y)

= x (1 + y)

= x . 1

= x

Operator Precedence in Boolean Algebra –

The operator precedence in descending order in boolean algebra is as follow – 1) Parenthesis, 2) NOT, 3) AND and 4) OR. Any boolean expression is deduced from left to right and the highest precedence is of parenthesis (). Then NOT, AND and the lastly OR operator.

Boolean Function –

A boolean function is a boolean algebraic expression consisting of boolean variables (where each variable can have a value 0 or 1), boolean constants (that is 0 and 1) and boolean operators (like AND, OR, NOT). Any boolean function practically represents some computation on binary data. For example, let a boolean function say F be like –

F = x + y.z

Here x, y and z are boolean variables (binary data sources like binary cells from a register) which are related by the AND and OR operators in the above function. All the possible results of a boolean expression can be represented by a truth table. The truth table enlists all the possible combinations of the values of the boolean variables and compare it with the result of the boolean expression. Like for the above stated function, the following is the truth table –

Fig. 1: Truth table for a Boolean Function

A digital circuit for the above boolean function is nothing other than the interconnection of logic gates (AND, OR, NOT) with binary data sources (represented by boolean variables in the boolean function). The binary multiplication or dot operation between two variables is equivalent to connecting two binary sources as input of AND gate. The binary addition or plus operation between two variables is equivalent to connecting two binary sources as input of OR gate. The complement is equivalent to connecting a binary source to a NOT gate. So, the digital circuit for the above function will be as follow –

Fig. 2: Image showing Boolean Function converted to Logic Circuit

Complement of a Boolean Function –

The complement of a boolean function is obtained by interchanging all 0’s to 1’s and 1’s to 0’s and interchanging AND and OR operators. In a boolean function, the replacement of all 0’s by 1’s and all 1’s by 0’s is done by replacing the boolean variables by their complements. For example, the complement of the function stated above will be as follow –

If F = x + y.z, then

F’ = x’ . (y’ + z’)

Minterm and Maxterm –

A boolean variable can exit in either its normal form (like x) or in its complement form (like x’) in a boolean expression. If AND operation is done between two variables, say x and y, there can be four possible combinations – x.y, x.y’, x’.y and x’.y’. Each of these all possible products are called Minterm or standard product. Similarly, if OR operation is done between two variables, say x and y, then again there are four possible combinations – x + y, x + y’, x’ + y and x’ + y’. Each of these all possible sums are called Maxterm or standard sums.

For two variables, x and y, the following Minterms and Maxterms are possible –

Fig. 3: Table listing Minterms and Maxterms for two boolean variables

Similarly for three variables say x, y and z, the following Minterms and Maxterms are possible –

Fig. 4: Table listing Minterms and Maxterms for three boolean variables

For n variables, there can 2^n Minterms and 2^n Maxterms. An any boolean function can be expressed as sum of Minterms producing 1 for the function in the truth table or Product of Maxterms producing 0 for the function in the truth table provided the truth table for the function is known. For example, there be a function F, with the following truth table –Similarly for three variables say x, y and z, the following Minterms and Maxterms are possible –

Fig. 5: Truth Table for a three-variable boolean function

From the above truth table, the function F can be expressed as sum of Minterms producing 1 for the function in the truth table as follow –
F =x’yz + xy‘z’ + xy’z + xyz‘ + xyz = m3 + m4 + m5 + m6 + m7From the above truth table, the function F can be expressed as sum of Minterms producing 1 for the function in the truth table as follow –

Similarly, it can be expressed as product of Maxterms producing 0 for the function in the truth table as follow –

F = (x’ + y’ + z’) . (x’ + y’ + z) . (x’ + y + z’) = M0 . M1 . M2

A function expressed as sum of minterms or product of maxterms is said to be in its canonical form. As for n number of variables, there can be 2^n minterms and 2^n maxterms, the number of functions possible with n number of variables is 2^2n. So, for 2 boolean variables, there can be 4 minterms and 4 maxterms and total number of functions possible with them is 16. So, there can be 16 binary functions (binary operations) possible between two boolean variables or (binary sources).

By expressing a function in the form of Minterms and Maxterms, it can have two level implementation in logic gates. The two-level implementation is always preferred as it produces least amount of delay through the gates when signal propagates from input to output of the digital circuit.

In the next tutorial, learn about all the possible logical operations between two boolean variables. There are additional logical operations other than AND, OR and NOT. All the possible logical operations between two binary sources can be derived with the knowledge of boolean functions and theorems.