## LESSON 18. Boolean Algebra-Fundamental postulate-Demorgan’s theorem.

BOOLEAN ALGEBRA AND THEOREMS

Introduction

In 1854, George Boole introduced a systematic treatment of logic and developed for this purpose an algebraic system now called Boolean Algebra. In 1938 C.E. Shannon introduced a two-valued Boolean algebra called switching algebra. Boolean algebra is a system of mathematical logic. It differs from both ordinary algebra and the binary number system. As an illustration, in Boolean, 1 + 1 = 1, in binary arithmetic the result is 10. Thus although there are similarities, Boolean algebra is a unique system.

• The symbol which represent an arbitrary elements of an Boolean algebra is known as variable. Any single variable or a function of several variables can have either a 1 or 0 value. For example, in expression Y = A + BC, variables A, B and C can have either a 1 or 0 value, and function Y also can have either a 1 or 0 value; however its value depends on the value of Boolean expression.
•  A complement of a variable is represented by a “bar” over the letter. For example, the complement of a variable A will be denoted by

Sometimes a prime symbol (‘) is used to denote the complement. For example, the complement of A can be written as A’.

• The logical AND operator of two variables is represented either by writing a dot (·) between two variables, such as A · B or by simply writing two variables, such as AB. Similarly, AND operation between three variables can be represented as A·B·C or ABC.
• The logical OR operator of two variables is represented by writing a ‘+’ sign  between the two variables such as A+B. Similarly, OR operation between three variables can be represented as A+B+C.

Fundamental Postulates of Boolean Algebra

The postulates of a mathematical system from the basic assumption from which it is possible to deduce the theorems, laws and properties of the system. Boolean algebra is formulated by a defined set of elements, together with two binary operators,  + and ·, provided that the following postulates are satisfied.

• Closure (a) : Closure with respect to the operator +

When two binary elements are operated by operator + the result is a unique binary element.

•   Closure (b) : Closure with respect to the operator · (dot)

When two binary elements are operated by operator · (dot)  the result is a unique binary element.

•  An identity element with respect to +, designated by 0:

A+ 0 = 0 + A = A

•  An identify element with respect to (·) , designated by 1: A · 1 = 1 · A = A

•  Commutative with respect to + : A + B = B + A

•  Commutative with respect to · : A · B = B · A

•  Distributive property of · over + :

A · (B + C) = (A·B) + (A·C)

•  Distributive property of + over · :

A + (B · C) = (A + B) · (A + C)

•  For every binary element, there exists complement element. For example, if A is an element, we have A    is a complement of A. i.e., if A = 0,  A    = 1 and if

•  There exists at least two elements, say A and B in the set of binary elements such that  A ≠ B.

From the above discussion we can summarize the postulates of Boolean algebra as shown in the following table 18.1

Table 18.1  Fundamental postulates of Boolean algebra

Laws of Boolean Algebra

Three of basic laws of Boolean algebra: the commulative laws, associative laws, and the distributive law.

Commulative laws

LAW 1: A + B = B + A : This states that the order in which the variables are ORed makes no difference in the output. The truth tables are identical. Therefore, A OR B is same as B OR A.

Table 18.2 Truth table for commutative law for OR gates

LAW 2: AB = BA :

The commutative law of multiplication states that the order in which the variables are AND ed makes no difference in the output. The truth tables are identical. Therefore, A AND B is same as B AND A.

Table 18.2 Truth table for commutative law for AND gates

It is important to note that the commutative laws can be extended to any number of variables. For example, since A + B = B + A, it follows that A + B + C = B + A + C, and since A + C = C + A, it is true that B + A + C = B + C + A. Similarly,

ABCD = BACD = BADC = ABDC, and so on.

Associate Laws

Law 1: A + (B +C) = (A + B) + C:

This law states that in the ORing of several variables, the result is the same regardless of the grouping of the variables. For three variables, A OR B ORed with C is the same as A ORed with B OR C.

Truth Table for associative law for OR gates

Law 2 : (AB) C = A (BC):

The associative law of multiplication states that it makes no difference in what order the variables are grouped when ANDing several variables. For three variables, A AND B ANDed with C is the same as A ANDed with B and C.

Truth Table for associative law for AND gates

Distributive Law:

Law: A (B+C) = AB + AC :

The distributive law states that ORing several variables and ANDing the result with a single variable is equivalent to ANDing the result with a single variable with each of the several variables and then ORing the products.

It is important to note that the distributive property is often used in reverse; i.e., given AB + AC, we replace it by its equivalent, A (B+C). As in ordinary algebra, this process is called factoring. We factored A out of the expression AB + AC.

DeMorgan’s Theorems

DeMorgan suggested two theorems that form an important part of Boolean algebra. In the equation form, they are:

The complement of a product is equal to the sum of complements. This is illustrated by following truth table.

TRUTH TABLE

The component of a sum is equal to the product of the complements. The truth Table illustrates this law.

TRUTH TABLE