1) (Simplification using Boolean Algebra - 10 points) Using the laws of Boolean algebra, and not by using truth tables, prove or disprove the following: a) (X+Y) (X+Y) = X b) (X) (X+Y) = X c) (X) (X+Y) = X d) (X +Y) (X + Z) = XZ + XY. By the way, we have studied this function in class. What is it? e) X Y Z+X Y = X Y+ X Z 2) (10 points) Simplify the following expressions as much as possible: a) (r + y)(+y)(r +5)(F+ g) b) T(7+ Z)(x + y+ ) c) A B (D+TD) + B(A+ ACD) d) r y+y z+7 z. 3) (3-var XOR/XNOR - 15 points) In class, we have analyzed the Exclusive-OR (XOR) function of two variables: f(a, b), which is represented as f a e b = ab + a'b. Similarly, the XNOR function of two variables, g(a, b) =a@b= a@b= a' + ab. You will now analyze the 3-variable XOR/XNOR functions: Take the 3-variable function f(a, b, c) = aeb@c. This function is really the XOR(a, b, c). Write down the truth-table, the ON-set minterms and obtajn a simplified sum-of-product (SOP) form expression for %3D the function. (Does there exist any simplification of this SOP form?] Now consider the 3-variable function f(a, b, e) a@bec. Think about it as a NOT of XOR(a, b, c). Obtain its minimized SOP form. [Again, does there exist any SOP form simplification?] abe (ab)ie= a(b5c). Construct the truth-table for this function, and derive the minimal SOP form for the function. Is f%= Now consider the function S(a,b, c)= aLTe. Think of / as f abe - a e bee? By the way, XOR/XNOR functions have many interesting properties; one of which you are asked to = ab. prove (or disprove): f(a, b) = 7eb = a 4) (Synthesis from Minterms and Maxterms - 20 points) In class, we have seen how to synthesize optimal sum-of-product forms starting from the ON-set minterms of a function and implement the design using two- level AND-OR logic. In this problem, you will get more experience with this concept. Moreover, the duals of minterms and sum of product forms are maxterms and product of sum forms, respectively. Synthesis with product of sum forms and implementation using two-level OR-AND logic is described in Section 2.6.1, pp. 52 onwards. Please go through these concepts and study the solved examples when you attempt to solve this problem. Consider the Boolean function f (r, y. z) represented by the truth table shown in Table I. TABLE I TRUTH TABLE a) Derive the Minterm Canonical form (Sum of Minterms) expression of the Boolean function f from the truth table. b) Simplify the sum of product form as much as possible. c) Derive the Maxterm Canonical form (also called the Canonical Product-of-Sum form) expression of the Boolean function from the truth table. d) Is the minterm canonical form of the function logically cquivalent to its maxterm canonical form? If yes, prove the equivalence of the expressions. If not, prove otherwise. e) Implement the function using only NAND gates. 5) (A Digital Design Example 15 points) You are asked to design a controller for a printer as follows. This controller has 4 inputs, to, t1, t2, corresponding to 3 paper trays, and input j signaling a paper jam. The circuit has 3 outputs: E for error, fo, and f1. Description of inputs: Inputs to, t1,t2 show the status of paper trays. If there is no paper in any of the trays, the corresponding input (to, ti or t2) goes low (logical 0), indicating that there is no paper in the particular tray. Otherwise, t, = 1. If paper gets jammed in the printer, input j is asserted high (j = 1), indicating a paper jam. Description of outputs: Signal E should be set to high if a paper jam occurs OR all trays run out of paper. Signals fo and fi imply the tray from which papers should be fetched: { fo = 0, fi - 0} imply that tray 0 is selected; {fo = 1, fi = 0) imply that tray 1 is chosen; and {fo = 0. fi = 1} indicates that papers will be fetched from tray 2; and finally {So = 1, = 1} indicate that no tray is selected. To generate fo and f1. the !3! %3D %3! controller should check the following conditions: If there is a paper jam or all trays are empty, then no tray should be selected (fo 1, and f 1). Trays are selected based on their priority. The lower the number, the higher the priority, i.e. to > t > t. In other words, first, the controller checks tray 0. If it has papers, tray 0 is selected. If tray 0 is empty, the controller checks tray 1; and if both tray 0 and tray 1 run out of paper, then tray 2 is checked. Description of outputs: Signal E should be set to high if a paper jam occurs OR all trays run out of paper. imply the tray from which papers should be fetched: {fo = 0, fi = 0} imply that tray 0 Signals fo and %3D %3D is selected; (fo 1, fi 0} imply that tray 1 is chosen; and (fo-0, fi 1) indicates that papers will be fetched from tray 2; and finally (fo-1, f 1} indicate that no tray is selected. To generate fo and fi, the %3D controller should check the following conditions: If there is a paper jam or all trays are empty, then no tray should be selected (fo = 1, and fi = 1). Trays are selected based on their priority. The lower the number, the higher the priority, i.c. to >t; > t2. In other words, first, the controller checks tray 0. If it has papers, tray 0 is selected. If tray 0 is empty, the controller checks tray 1; and if both tray 0 and tray 1 run out of paper, then tray 2 is checked. Your assignment: a) Derive the truth table of this 4-input 3-output Boolean function according to the above specifications. b) Subsequently, derive a simplified Boolean expression and draw the corresponding logic circuit. In addition to the above questions, I'm giving you a list of some exercise problems from the book that you can try to solve to gain some more practice with Logic Design and Simplification. These are not part of the HW, and they will not be graded. This is just a suggested exercise for you: Problems: 2.7, 2.12, 2.35
