Boolean Postulates and Laws

Chapter 2:

Boolean Algebra, Logic Gates and Minimization Techniques

Boolean Postulates and Laws

In 1854, George Boole introduced a systematic treatment of logic and developed for this purpose an algebraic system now called Boolean algebra.

Boolean algebra is a system of mathematical logic. It differs from both ordinary algebra and the binary number system.

1. Boolean Algebra Terminology

Variable : 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.

Constant : In expression Y = A + 1, the first term A is a variable and have value either a 1 or 0. The second term has a fixed value 1. So 1 is a constant here. The constant term may be 0 or 1.

Complement : 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 Ā. So if A = 1, Ā = 0 and if A = 0, Ā = 1. Sometimes a prime symbol (') is used to denote the complement. For example, the complement of A can be written as A'.

Literal : Each occurrence of a variable in Boolean function either in a complemented or an uncomplemented form is called a literal.

Boolean function : Boolean expressions are constructed by connecting the Boolean constants and variables with the Boolean operations. These Boolean expressions are also known as Boolean formulas. We use Boolean expressions to describe Boolean functions. For example, if the Boolean expression (A + ) C is used to describe the function f, then Boolean function is written as

f(A, B, C) = (A +) C or f = (A + ) C

2. Fundamental Postulates and Laws of Boolean Algebra

The postulates of a mathematical system form 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 given 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 identity 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)

• Associative property of + : A + (B + C) = (A + B) + C

• Associative property of • : (A • B) • C = A • (B • C)

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

• 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 Table. 2.1.1.

3. Basic Theorems

Table 2.1.2 lists the five basic theorems of Boolean algebra four of its postulates. The postulates and theorems are listed in pairs and designated by part (a) and part (b). One part may be obtained from the other by using principle of duality.