Week 3 - Module 3 Boolean Algebra.pdf

CPE 6204 – Logic Circuits and Switching Theory 1 Boolean Algebra Module 3: Boolean Algebra Course Le...

CPE 6204 – Logic Circuits and Switching Theory 1 Boolean Algebra Module 3: Boolean Algebra Course Learning Outcomes: 1. Relate the basic operations and laws of Boolean algebra to circuits composed of logic gates. 2. Prove the theorems using postulates 3. Reduce Boolean expressions using the principles of Boolean algebra. 4. Produce the complement of a Boolean function. Boolean Algebra Boolean algebra is part of mathematics that deals with operations involving logical elements, variables and operators, as well as axioms and postulates. It is named after George Boole, an English mathematician, logician, and philosopher. In digital design, it forms part of the core concepts for simplifying logic circuits. Below are the basic theorems and properties of Boolean algebra. Table 1. Summary of Postulates and Theorems Postulate 1, Closure a. The structure is closed with respect to the operator, +¿. b. The structure is closed with respect to the operator, ⋅ Postulate 2, Identity Postulate 5, Complement a. x +0=x a. x + x' =1 b. x ⋅1=x b. x ⋅ x ' =0 Theorem 1 Theorem 2 a. x + x=x a. x +1=1 b. x ⋅ x= x b. x ⋅ 0=0 Theorem 3, Involution: Postulate 3, Commutative ' ' ( x ) =x a. x + y= y + x b. x ⋅ y= y ⋅ x Theorem 4, Associative Postulate 4, Distributive a. x + ( y + z )=( x + y ) + z a. x ( y + z ) =xy+ xz b. x ( yz )=( xy ) z b. x + yz=( x+ y)( x + z) Theorem 5, DeMorgan Theorem 6, Absorption a. ( x + y )' =x ' y ' a. x + xy=x b. ( xy )' =x ' + y ' b. x ( x + y )= x Source: Mano & Ciletti, Digital Design 6th Ed. Course Module  Table 2. Proving the Theorems Theorem 1(a): x + x=x Statement Justification x+x ¿ ( x + x ) ⋅1 Postulate 2(b) ¿ ( x + x ) ( x + x') Postulate 5(a) Postulate 4(b) ¿ x + xx ' Postulate 5(b) ¿ x +0 Postulate 2(a) ¿x Theorem 1(b): x ⋅ x= x Statement Justification x⋅ x ¿ xx +0 Postulate 2(a) ¿ xx + xx ' Postulate 5(b) ¿ x ( x + x' ) Postulate 4(a) ¿ x ⋅1 Postulate 5(a) Postulate 2(b) ¿x The postulates need no proof and are accepted as is; the theorems, however, do need to be proven. Table 2 illustrates how the given theorems can be proven using the postulates. The Duality Principle  Every algebraic expression that we can logically arrive at from the postulates of Boolean algebra are valid even when the operators and identity elements interchange. For example, we can see that Theorem 1(a) in Table 2 is a dual of Theorem 1(b), and vice versa. The steps for proving both theorems also happen to be duals of each other, as well Operator Precedence In evaluating Boolean expressions, we take note of the following operator precedence: 1. Parenthesis 2. NOT 3. AND 4. OR Example 1: ( x + y )' =x ' y ' For the right-hand expression, the variables are complemented first, then ANDed. In the left-hand side, the variables, which are inside the parentheses, are ORed first, then complemented. Boolean Functions  They are described by an algebraic expression consisting of binary variables, logic operations, and the constants 0 and 1 [ CITATION Man18 \l 13321 ].  Given binary variables, each with a specific value, the output of the function is either 1 or 0.  CPE 6204 – Logic Circuits and Switching Theory 3 Boolean Algebra  Boolean functions can be represented in three ways: (1) using a truth table, (2) described by an algebraic expression, (3) illustrated as a logic circuit diagram In the previous module, we have seen an example of a combinational circuit. It is composed of interconnected logic gates whose truth table we have also completed. We were also able to come up with its corresponding Boolean expression. At this point, it is good to note that there is only one way to represent a Boolean function in a truth table but may have more than one equivalent algebraic expression and circuit diagram. Example 2: The function f =x ' y ' z + x ' yz+ xy ' has 3 terms and 8 literals, which may be represented by the following logic circuit diagram: Figure 1. Circuit diagram for f =x ' y ' z + x ' yz + xy ' By manipulating a Boolean expression according to the rules of Boolean algebra, it is sometimes possible to obtain a simpler expression for the same function and thus reduce the number of gates in the circuit and the number of inputs to the gate [ CITATION Man18 \ l 13321 ]. We then reduce the function in the following manner: f1 ¿ x ' y ' z + x ' yz + xy ' ¿ x' z ( y'+ y )+ x y' ¿ x ' z (1 )+ xy ' f =f 1=x y ' + x ' z See how we have equated f and f 1. The principles behind simplification of Boolean expressions is like simplification of algebraic expressions. We can easily prove that f =f 1 Course Module using the truth table. The next page shows the truth tables for f and f 1, as well as the corresponding circuit diagram of f 1. The reduced expression gives us 2 terms and 4 literals. Figure 2. Reduction of f The circuit diagram now uses two 2-input AND gates, two inverters, and one 2-input OR gate, whereas the original diagram uses two 3-input AND gates, one 2-input AND gate, two inverters, and one 3-input OR gate. It may not seem much but if we try to implement the circuit with integrated circuits (ICs), we will see the reduced expression will use less wires. Table 3. The truth tables of f and f 1 x y z f x y Z f1 0 0 0 0 0 0 0 0 0 0 1 1 0 0 1 1 0 1 0 0 0 1 0 0 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 0 1 1 1 0 1 1 1 1 0 0 1 1 0 0 1 1 1 0 1 1 1 0 Complement of a Function We say that a function is complemented if its output f =1 changes to 0, or if f =0 changes to 1. We denote the complement of f by f '. It is easily achieved by appending an inverter at the final gate. Algebraically, we are not limited to complementing the entire expression. Applying DeMorgan’s theorems will enable us to incorporate simplification even with complemented functions. Example 3: Find the complement of a) F 1=x ' y z ' + x ' y ' z and b) F 2=x ( y ' z ' + yz) ' a) F '1 ¿( x ' y z ' + x' y ' z)' b) F 2 ' ¿ ( x ( y ' z ' + yz ) ) ' ¿( x ' y z ' )' (x ' y ' z) ' ¿ x ' + ( y ' z ' + yz ) ' ¿( x + y ' + z)( x + y + z ' ) ¿ x ' + ( ( y ' z ' ) ( yz )' )  CPE 6204 – Logic Circuits and Switching Theory 5 Boolean Algebra ¿ x ' + ( y + z ) ( y ' + z' ) It is also possible to obtain the complement of a function by taking the duals and simply complementing each literal. This method is easier, though more confusing where parentheses are concerned. The trick is to keep track of which variables are grouped together. References and Supplementary Materials Books and Journals 1. Mano, M. M., Ciletti, M.D. (2018). Digital Design: With an Introduction to the Verilog HDL, VHDL, and SystemVerilog (6th ed.). New Jersey: Pearson. 2. Harris, D.M, Harris, S.L. (2016). Digital Design and Computer Architecture: ARM Edition. Massachusetts: Elsevier Inc. 3. Roth, C.H. Jr., Kinney, L.L. (2014). Fundamentals of Logic Design (7th ed.). Connecticut: Cengage Learning Online Supplementary Reading Materials 1. Boolean Algebra, http://www.ee.surrey.ac.uk/Projects/Labview/boolalgebra/, Date Accessed: 02 October 2019 2. Boolean Expression Simplification, http://sandbox.mc.edu/~bennet/cs110/boolalg/simple.html, Date Accessed: 02 October 2019 Online Instructional Videos 1. Logic Simplification Examples Using Boolean Rules, https://youtu.be/59BbncMjL8I, Date Accessed: 02 October 2019 Course Module