# Computer Science XI

## Boolean algebra

Boolean algebra is a mathematical discipline that is used for designing digital circuits in a digital computer. It describes the relation between inputs and outputs of a digital circuit. The name Boolean algebra has been given in honor of an English
mathematician George Boole who proposed the basic principles of this algebra. As with any algebra, Boolean algebra makes use of variables and operations (functions). A Boolean variable is a variable having only two possible values such as, true or false, or as, 1 or 0. The basic logical operations are AND, OR and NOT, which are
symbolically represented by dot, plus sign, and by over bar / single apostrophe. Example: A AND B = A . B A OR B = A + B NOT A = A’ )or A( A Boolean expression is a combination of Boolean variables, Boolean
Constants and the above logical operators. All possible operations in Boolean algebra can be created from these basic logical operators. There are no negative or fractional numbers in Boolean algebra. The operation AND yields true (binary value 1) if and only if both of its operands are true. The operation OR yields true if either or both of its operands are true. The unary operation NOT inverts the value of its operand. The basic logical operations can be defined in a form known as Truth Table, which is a list of all possible input values and the output response for each input combination. 2.12.1 Boolean operators )functions( AND operator The AND operator is defined in Boolean algebra by the use of the dot (.)
operator. It is similar to multiplication in ordinary algebra. The AND operator combines two or more input variables so that the output is true only if all the inputs are true. The truth table for a 2-input AND operator is shown as follows: A B Y 0 0 0 0 1 0 1 0 0 1 1 1
36
The above 2-input AND operation is expressed as: Y = A . B OR operator The plus sign is used to indicate the OR operator. The OR operator combines two or more input variables so that the output is true if at least one input is true. The truth table for a 2-input OR operator is shown as follows: A B Y 0 0 0 0 1 1 1 0 1 1 1 1 The above 2-input OR operation is expressed as: Y = A + B NOT operator The NOT operator has one input and one output. The input is either true or false, and the output is always the opposite, that is, the NOT operator inverts the input. The truth table for a NOT operator where A is the input variable and Y is the output is shown below:
A Y 0 1 1 0 The NOT operator is represented algebraically by the Boolean expression: Y = A Example: Consider the Boolean equation: D = A + (B . C) D is equal to 1 (true) if A is 1 or if (B . C) is 1, that is, B = 0 and C = 1. Otherwise D is equal to 0 (false). The basic logic functions AND, OR, and NOT can also be combined to make other logic operators. NAND operator The NAND is the combination of NOT and AND. The NAND is generated by
inverting the output of an AND operator. The algebraic expression of the NAND function is: Y = A . B
37
The NAND function truth table is shown below: A B Y 0 0 1 0 1 1 1 0 1 1 1 0 A NAND B = NOT (A AND B) NOR operator The NOR is the combination of NOT and OR. The NOR is generated by inverting the output of an OR operator. The algebraic expression of the NOR function is: Y = A + B The NOR function truth table is shown below: A B Y 0 0 1 0 1 0 1 0 0 1 1 0 A NOR B = NOT (A OR B) 2.12.2 Laws of Boolean algebra Boolean algebra helps to simplify Boolean expressions in order to minimize the number of logic gates in a digital circuit. You will study about logic gates in the forthcoming chapter. This chapter focuses on the theorems of Boolean algebra for manipulating the Boolean expressions in order to simplify them. Boolean Identities Laws of Complementation The term complement simply means to change 1s to 0s and 0s to 1s. Theorem 1 : If A = 0, then A = 1 Theorem 2 : If A = 1, then A = 0 Theorem 3 : The complement to complement of A is A itself. A = A Basic properties of AND operator Theorem 4 : A . 1 = A
38
If A equals 0 and the other input is 1, the output is 0. If A equals 1 and the other input is 1, the output is 1. Thus the output is always equal to the A input. Theorem 5 : A . 0 = 0 As one input is always 0, irrespective of A, the output is always 0. Theorem 6 : A . A = A The output is always equal to the A input. Theorem 7 : A . A = 0 Regardless of the value of A, the output is 0. Basic properties of OR operator Theorem 8 : A + 1 = 1 If A equals 0 and the other input is 1, the output is 1. If A equals 1 and the other input is 1, the output is 1. Thus the output is always equal to 1 regardless of what value A takes on. Theorem 9 : A + 0 = A The output assumes the value of A. Theorem 10 : A + A = A The output is always equal to the A input. Theorem 11 : A + A = 1 Regardless of the value of A, the output is 1. 2.12.3 Simplification of Boolean expressions Before seeing the important theorems used in the simplification of Boolean expressions, some Boolean mathematical concepts need to be understood. Literal A literal is the appearance of a variable or its complement in a Boolean
expression. Product Term A product term in a Boolean expression is a term where one or more literals are connected by AND operators. A single literal is also a product term. Example: AB, AC, A C, and E are the product terms.
39
Minterm A minterm is a product term, which includes all possible variables either complemented or uncomplemented. In a Boolean expression of 3 variables, x, y, and z, the terms xyz, x yz, and x y z are minterms. But x y is not a minterm. Minterm is also called as a standard product term. Sum term A sum term in a Boolean expression is a term where one or more literals are connected by OR operators. Example: A + B + D Maxterm A maxterm is a sum term in a Boolean expression, which includes all possible variables in true or complement form. In a Boolean expression of 3 variables, x, y, and z, the terms x + y + z, and x + y + z are the maxterms. Maxterm is also called as
standard sum term. Sum-of-products )SOP( A sum of products expression is a type of Boolean expression where one or more product terms are connected by OR operators. Example: A + A B + A B C In an expression of 3 variables, A, B, and C, the expression ABC + A B C +
A B C is also called as a canonical sum or sum of standard product terms or sum of minterms. Product-of-sums )POS( Product of sums is a type of Boolean expression where several sum terms are connected by AND operators. Example: (A + B) (A + B) (A + B) A canonical product or product of standard sum terms is a product of sums expression where all the terms are maxterms. The above example is a canonical product in a Boolean expression of two variables A and B. Theorem 12: Commutative Law A mathematical operation is commutative if it can be applied to its operands in any order without affecting the result. Addition and multiplication operations are commutative.
40
Example: A + B = B + A AB = BA Subtraction is not commutative: A - B ≠ B - A There is no subtraction operation in Boolean algebra. Theorem 13: Associative Law A mathematical operation is associative if its operands can be grouped in any order without affecting the result. In other words, the order in which one does the OR operation does not affect the result. (A + B) + C = A + (B+C) = (A + C) + B Similarly, the order in which one does the AND operation does not affect the result. (AB)C = A(BC) = (AC)B Theorem 14: Distributive Law The distributive property allows us to distribute an AND across several OR
functions. Example: A(B+C) = AB + AC The following distributive law is worth noting because it differs from what we would find in ordinary algebra. A + (B . C) = (A + B) . (A + C) The simplest way to prove the above theorem is to produce a truth table for both the right hand side (RHS) and the left hand side (LHS) expressions and show that they are equal. A B C BC LHS A + B A + C RHS 0 0 0 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 0 1 0 1 0 1 0 0 0 1 0 0 0 1 0 0 0 1 1 1 1 1 0 0 1 1 1 1 1 1 0 1 0 1 1 1 1 1 0 0 0 1 1 1 1 1
41
Minimum Sum of Products A minimum sum of products expression is one of those Sum of Products expressions for a Boolean expression that has the fewest number of terms. Consider the following Boolean Expression: A B C + A B C + A B C + A B C + A B C Using Associativity Law = ( A B C + A B C) + (A B C + A B C) + A B C = ( A B (C + C) + A B (C + C) + A B C Using Theorem 11 = A B (1) + A B (1) + ABC Using Theorem 4 = A B + A B + ABC The above expression is in the minimum sum of products form. The given Boolean expression can be rewritten as follows using theorem 10. A B C + A B C + A B C + A B C + A B C + A B C (A B C + A B C = A B C) = (A B C + A B C) + (A B C + A B C) + (A B C + A B C) = A B (C + C) + A B (C + C) + A C(B + B) = A B + A B + A C The same Boolean expression can be simplified into many minimum sum of products form. Examples: Simplify the following Boolean Expression A B C + A B C Let x = A B and y = C The above Boolean expression becomes x y + x y = x(y + y) = x = A B
42
Prove that A + A B = A + B According to Distributive Law A + A B = (A + A) (A + B) = 1 · (A + B) = A + B Simplify the following Boolean Expression A B C + A B C + A B C + A B C = A C (B + B) + A B C + A B C = A C + A B C + A B C = A (C + BC) + A B C = A (C + B)(C + C) + A B C = A (C + B) + A B C = A C + A B + A B C (one minimal form) In the given Boolean Expression, if the second and third terms are grouped, it will give A B C + (A B C + A B C) + A B C = A B C + A B(C + C) + A B C = A B C + A B + A B C = B C (A + A) + A B = B C + A B (most minimal form) 2.12.4 DeMorgan’s Theorems Theorem 15: A + B = A B Theorem 16: AB = A + B The above identities are the most powerful identities used in Boolean algebra. By constructing the truth tables, the above identities can be proved easily. Example: Given Boolean function f(A,B,C,D) = D A B + A B + D A C, Find the complement of the Boolean function f (A,B,C,D) = D A B + A B + D A C Apply DeMorgan’s Law (theorem 15) = (D A B) (A B) (D A C)
43
Apply DeMorgan’s Law (theorem 16) = (D + A + B)(A + B)(D + A + C) In the above problem, the given Boolean function is in the sum of products form and its complement is in the product of sums form. The DeMorgan’s theorem says that any logical binary expression remains unchanged if we,  change all varibales to their complements  change all AND operations to OR operations  change all OR operations to AND operations  take the complement of the entire expression A practical operational way to look at DeMorgan’s theorem is that the inversion of an expression may be broken at anypoint and the operation at that point replaced by its oppostie ( i.e., AND replaced by OR or vice versa).