Boolean Functions
A Boolean function is an expression formed with binary variables (variables that takes the value of 0 or 1), the two binary operators OR and AND, and unary operator NOT, parentheses, and an equal sign. For the given value of the variables, the function can be either 0 or 1.
- Boolean function represented as an algebraic expression: Consider Boolean function F1 = xyz’. Function F is equal to 1 if x=1, y=1 and z=0; otherwise F1 =0. Other examples are: F2 = x + y’z, F3 =x’y’z + x’yz + xy’, F4 = xy’ + x’z etc.
- The boolean function represented in a truth table: The number of rows in the truth table is 2n, where n is the number of binary variables in the function, The 1’s and 0’s combinations for each row is easily obtained from the binary numbers by counting from 0 to 2n – 1.
A Boolean function may be transformed from an algebraic expression into a logic diagram composed of AND, OR, and NOT gates. The implementation of the four functions introduced in the previous discussion is shown below:
Algebraic manipulation and simplification of Boolean function
- A literal is a primed or unprimed (i.e. complemented or un-complemented) variable. When a Boolean function is implemented with logic gates, each literal in the function designates an input to a gate, and each term is implemented with a gate.
- The minimization of the number of literals and the number of terms results in a circuit with less equipment. It is not always possible to minimize both simultaneously; usually, further criteria must be available. At the moment, we shall narrow the minimization criterion to literal minimization. We shall discuss other criteria in unit 3.
- The number of literals in a Boolean function can be minimized by algebraic manipulations. Unfortunately, there are no specific rules to follow that will guarantee the final answer. The only method available is a cut-and-try procedure employing the postulates, the basic theorems, and any other manipulation method that becomes familiar with use. The following examples illustrate this procedure.
Simplify the following Boolean functions to a minimum number of literals.
- x + x ‘y = (x + x ‘)(x + y) = 1.(x + y) = x + y
- x(x’ + y) = xx’ + xy = 0 + xy = xy
- x’y’z + x’yz + xy’ = x’z(y’ + y) + xy = x’z + xy
- xy + x’ z + yz = xy + x’ z + yz (x + x’)
= xy + x’z + xyz + x’yz
= xy(1 + z) + x’z(1 + y)
= xy + x’z
- (x + y)(x’ + z)(y + z) = (x + y)(x’ + z) by duality from function 4.
The Complement of a function
The complement of a function F is F’ and is obtained from an interchange of 0’s for 1’s and 1’s for 0’s in the value of F. The complement of a function may be derived algebraically through DeMorgan’s theorem. DeMorgan’s theorems can be extended to three or more variables. The three-variable form of the first DeMorgan’s theorem is derived below.
(A + B + C)’ = (A + X)’ let B + C = X
= A’X’ (DeMorgan)
= A’· (B + C)’ substitute B + C = X
= A’.(B ‘C’) (DeMorgan)
= A’B’C’ (associative)
DeMorgan’s theorems for any number of variables resemble in form the two-variable case and can be derived by successive substitutions similar to the method used in the above derivation. These theorems can be generalized as follows:
(A + B + C + D + … + F)’ = A’B’C’D’… F’
(ABCD … F)’ = A’ + B’ + C’ + D’ + … + F’
Algebraic manipulation and simplification of a Boolean function
- A literal is a primed or unprimed (i.e. complemented or un-complemented) variable. When a Boolean function is implemented with logic gates, each literal in the function designates an input to a gate, and each term is implemented with a gate.
- The minimization of the number of literals and the number of terms results in a circuit with less equipment. It is not always possible to minimize both simultaneously; usually, further criteria must be available. At the moment, we shall narrow the minimization criterion to literal minimization. We shall discuss other criteria in unit 3.
- The number of literals in a Boolean function can be minimized by algebraic manipulations. Unfortunately, there are no specific rules to follow that will guarantee the final answer. The only method available is a cut-and-try procedure employing the postulates, the basic theorems, and any other manipulation method that becomes familiar with use. The following examples illustrate this procedure.
Simplify the following Boolean functions to a minimum number of literals.
- x + x ‘y = (x + x ‘)(x + y) = 1.(x + y) = x + y
- x(x’ + y) = xx’ + xy = 0 + xy = xy
- x’y’z + x’yz + xy’ = x’z(y’ + y) + xy = x’z + xy
- xy + x’ z + yz = xy + x’ z + yz (x + x’)
= xy + x’z + xyz + x’yz
= xy(1 + z) + x’z(1 + y)
= xy + x’z
- (x + y)(x’ + z)(y + z) = (x + y)(x’ + z) by duality from function 4.
A Complement of a function
The complement of a function F is F’ and is obtained from an interchange of 0’s for 1’s and 1’s for 0’s in the value of F. The complement of a function may be derived algebraically through DeMorgan’s theorem. DeMorgan’s theorems can be extended to three or more variables. The three-variable form of the first DeMorgan’s theorem is derived below.
(A + B + C)’ = (A + X)’ let B + C = X
= A’X’ (DeMorgan)
= A’· (B + C)’ substitute B + C = X
= A’.(B’C’) (DeMorgan)
= A’B’C’ (associative)
DeMorgan’s theorems for any number of variables resemble in form the two variable case and can be derived by successive substitutions similar to the method used in the above derivation. These theorems can be generalized as follows:
(A + B + C + D + … + F)’ = A’B’C’D’… F’
(ABCD … F)’ = A’ + B’ + C’ + D’ + … + F’
You may also like the basic theorems & properties of boolean algebra.
Leave a Reply