EECE 320 Homework 2, Fall 2016

Prof. M. Mansour American University of Beirut Department of Electrical and Computer Engineering EECE 320 – Digital Systems Design Homework 2 Problem 1 [10 pts]: Construct a logic circuit that performs the XOR operation using AND gates and inverters only. Problem 2 [10 pts]: Reduce the following Boolean expressions to the indicated number of literals: a) (x’y’ + z)’ + z + xy + wz to three literals b) A’B(D’ + C’D) + B(A + A’CD) to one literal c) (A’ + C)(A’ + C’)(A + B + C’D) to four literals Problem 3 [10 pts]: Implement the function F = xy + x’y’ + y’x a) Using AND, OR, inverters b) Using OR and inverters only c) Using AND and inverters only Problem 4 [10 pts]: Given the Boolean function F = xy’z + x’y’z + w’xy + wx’y + wxy. Draw the logic diagram of F. Then simplify F to the minimum number of literals using Boolean algebra. Draw the logic diagram of the simplified function and compare the total number of gates with the previous logic diagram. Problem 5 [10 pts]: Prove the identity of the following Boolean equations using only algebraic manipulations: a) bd + ac’d’ + abc’ + a’bc + b’cd’ = bd + ac’d’ + a’cd’ + ab’d’ b) (a’ + b’ + c + d’)(a + b + c’ + d) = cd + ab’ + ac + a’c’ +a’b + c’d’ Problem 6 [10 pts]: Express the following functions both in sum-of-products (SOP) and product-of-sums (POS) forms: a) (XY + Z)(Y + XZ) b) (A’ + B)(B’ + C) c) WXY’ + WXZ’ + WXZ + YZ’ Problem 7 [10 pts]: Simplify the function � � B C D A F , , , 13,15) ,7,6,4,3,1( using only algebraic manipulations. Problem 8 [10 pts]: Derive the Shannon expansion with respect to x1, x2, and x3 for F(x1, x2, x3) = x1� x2� x3. Problem 9 [10 pts]: A Boolean function is said to be symmetric if changing the order of all its variables can be changed without changing the value of the function itself. For example the Boolean function of three variables F(x1,x2,x3) = x’1x’2 x’3 + x1x2x3 is symmetric since F(x1,x2,x3) = F(x1,x3,x2) = F(x2,x1,x3) = F(x2,x3,x1) = F(x3,x1,x2) = F(x3,x2,x1). a) List all Boolean symmetric functions of two variables x1and x2. b) Find three non-trivial Boolean symmetric functions of three variables x1, x2, and x3. c) If F and G are symmetric functions, prove that F.G and F + G are also symmetric. Problem 10 [10 pts]: Let F be a Boolean function of n variables x1, x2, …, xn. Then the Boolean difference of F with respect to the ith variable xi is defined as ). , ,1 , , ( ) , ,0 , , ( 1 1 n i n i i x x F x x x F x x F � � � � � � � � � � Find the Boolean difference of F(x1, x2, x3) = (x1x2) � x3 with respect to x1. Problem 11 [10 pts]: A set of Boolean functions that realizes any logic function is called a complete set of logic gates. For example, the set of 2-input AND gates, 2-input OR gates, and inverters forms a complete set. Prove whether the following sets of functions are complete or not complete: (a) {NAND}, (b) {NOR}, (c) {AND, OR}, (d) {AND}, (e) {XOR}, (f) {AND, XOR}, (g) {OR, XOR}, (h) {AND, XNOR}, (i) {XOR, XNOR}, (j) {XOR, NAND}. Problem 12 [10 pts]: Invent a non-trivial 4-input logic gate and call it a ‘BUT’ gate. The function should have something to do with the name (BUT). Its symbol is shown below. Due to the symmetry of the symbol, the function should be symmetric with respect to the A and B inputs in each section and with respect to sections 1 and 2. Describe the BUT function and write its truth table. Problem 13 [40 pts]: A logic function F is called self-dual if F = FD. Remember that the dual of a logic function F is � � � � 1 2 1 2 , , , , , ,' , , , , , ,' D N N X X X X X X � � � � � F F � � 1. In class we proved that for any Boolean function F, � � � � � � ' ' ' ' ' ' 1 2 1 2 1 2 , ,, , , ,' , , , , , ,' , , , , , ,' D N N N X X X X X X X X X � � � � � � � � � � � � � F F F � � Show that specifically for a self-dual function F, we have: � � � � � � ' ' ' 1 2 1 2 1 2 , ,, , , ,' , , , , , ,' , ,, , , ,' D N N N X X X X X X X X X � � � � � � � � � � � � � F F F � By observing the second equality in the above equation, can you find a relationship between the entries of a truth table of a self-dual function? 2. Which of the following functions are self-dual? (a) F1 = X (b) F2 = �X,Y,Z(1,2,5,7) (c) A function F3 of 6 variables such that F3 = 1 if and only if 3 or more of the variables are 1. (d) A function F4 of 9 variables such that F4 = 1 if and only if 5 or more of the variables are 1. 3. How many self-dual logic functions of n-input variables are there? Hint: Consider the structure of the truth table of a self-dual logic function as determined in part (1) above. 4. Prove that any N-input logic function F(X1,…,XN) that can be written in the form � � � � � � ' 1 2 1 2 1 2 , , , , , ,' , , , , ,' , , , , ,' D N N N X X X X X X X X X � � � � � � � � � � F G G � � � is self-dual. A1 B1 A2 B2 Z1 Z2