NOTE: The formatting on this won't work unless you use an equal-width font (like courier) and turn off word-wrapping (or make the wrapping length very long). 2.3) Find a decomposed realization of the form specified, if possible: __ __ __ __ __ __ __ __ __ __ A) f (x1, x2, x3, x4) = x1 x2 x3 x4 + x1 x2 x3 x4 + x1 x2 x4 + x1 x2 x4 + x2 x3 x4 + x2 x3 x4 in the form F(g(x1, x3), x2, x4) Since the variables g() uses are x1 and x3 we want to put those two opposite each other in the k-map: x1 ____ --------- |1 1 1| x4|| 1 | ||1 1 1||x2 | 1 || --------- --- x3 __ Looking at the first row, we see the pattern g(x1, x3) = x3 + x1 ___ ___ the first row is then g(), the second row is g(), the third row is g() and the fourth row is g(), __ __ __ ___ __ ___ so f = x2 x4 g() + x2 x4 g() + x2 x4 g() + x2 x4 g() __ (Note: you could have picked g = x1 x3 as your pattern, ie. the compliment of the one I chose. B) f=SUM(m0, m3, m5, m6, m8, m10, m13, m15) as F(g(x1,x2), x3, x4) x1 ____ --------- |1 1| x4| | 1 1 | | |1 | |x3 | 1 1 1| | --------- --- x2 Looking at this k-map, we see that the first row and the second are compliments and the third and the fourth are compliments, but the first and second are completely independent from the third and the fourth. So to decompose this function, we would need two patterns (ie F(g1(x1, x2), g2(x1, x2), x3, x4) would be the form). NOT POSSIBLE __ __ __ __ __ c) f = x1 x2 x4 x5 + x1 x3 x4 x5 + x1 x4 + x2 x3 x4 as F(g(x1, x2, x3), x4, x5) where g=F'(g'(x2, x3), x1) For this problem, you should choose the location of the variables (in the k-map) carefully. Since the first decomposition is of the variables x1 x2 x3, you know that the pattern specified by G is going to be of two rows/columns. You should arrange the K-map so that fixed values of X4 and x5 specify adjacent rows/columns. X4 ____________ x2 x2 ____ ____ --------- --------- |1 1 1 1| | | x5||1 1 1 1| x5|| | ||1 ||x1 || 1 1 1||x1 |1 || | || --------- --------- --- --- x3 x3 looking at x4=1, x5=1 (the middle two rows of the left half of the k-map), we see the pattern: __ __ __ g(x1, x2, x3) = x1 + x2 x3 ___ when x4=0 and x5=1 (the middle two rows of the right half of the k-map), we see g(). when x4=0 and x5=0, we just see 0's, and when x4=1, and x5=0, we see g(). __ ___ __ __ __ so F= x4 x5 g() + x4 x5 g() + x4 x5 g() + x4 x5 0 (the last term, ANDed with zero disappears) to decompose g(), we write another k-map g()= x2 ____ --------- |1 1 1 1| |1 ||x1 --------- --- x3 __ __ clearly the pattern is just g' = x2 x3, because the other fixed value of x1 (x1=0) is just 1's __ g = x1 + x1 g'() or __ g = x1 + g'() 2.4) what must the values of a,b,c be in the following k-map for the function to have a simple disjunctive decomposition in the form F(g(x1, x2), x3, x4) x1 ____ --------- |c a 1| x4|| | ||b 1 1||x3 | || --------- --- x2 Since g is a function of x1 and x2, we know we are looking for a pattern in the rows of the k-map. if A=1, and B=C, then rows 1 and 3 (x4=0,x3=0 and x4=1, x3=1) will be identical, and the function will therefore have a decomposition. 2.5) which of the following functions are symmetric? a) f= sum(m1, m2, m4, m6, m7, m8, m11, m13, m14) I find that making a truth-table makes these problems much easier: Ignore the column under S for now x1 x2 x3 x4 | f | S --------------------- 0 0 0 0 | 0 | 2 -> 0 0 0 1 | 1 | 3 -> 0 0 1 0 | 1 | 1 0 0 1 1 | 0 | 2 -> 0 1 0 0 | 1 | 1 0 1 0 1 | 0 | 2 -> 0 1 1 0 | 1 | 0 -> 0 1 1 1 | 1 | 1 -> 1 0 0 0 | 1 | 3 1 0 0 1 | 0 | 4 1 0 1 0 | 0 | 2 -> 1 0 1 1 | 1 | 3 1 1 0 0 | 0 | 2 -> 1 1 0 1 | 1 | 3 -> 1 1 1 0 | 1 | 1 1 1 1 1 | 0 | 2 The arrows point to the 1-points of f now lets make the table of p's and q's, where pi = the number of 1-points of f that have xi=1 qi = the number of 1-points of f that have xi=0 x1 x2 x3 x4 ------------- p|4 5 5 4 q|5 4 4 5 so we know that, if f is symmetric, x1~x4, x2~x3, and both x1,x4 are oppositely symmetric to x2,x3 so the function will be of the form: (I use the curly-braces to denote subscripts of the function S) __ __ S{a,b,c...}(x1, x2, x3, x4) or __ __ S{a,b,c...}(x1, x2, x3, x4) (let's just pick the first S) To find the values of the sub-scripts of S, plug all possible values __ __ into the variables x1, x2, x3, x4 and count how many are true. This is the column under S. the zero-points are on the left half, and the one-points are on the right. you can see that 4,2 only appear for values of x1, x2, x3, x4 corresponding to 0-points and 0,1,3 appear for 1-points. Another way of saying this, is no number that appears in the left half appears in the right, and vice-versa. __ __ F is true exactly when 0, 1, or 3 of the variables x1, x2, x3, x4 are true. __ __ The function IS symmetric, and it is S{0,1,3}(x1, x2, x3, x4) b) f=sum(m1, m2, m4, m5, m7) x1 x2 x3 | f | S ------------------- 0 0 0 | 0 | 1 -> 0 0 1 | 1 | 2 -> 0 1 0 | 1 | 0 0 1 1 | 0 | 1 -> 1 0 0 | 1 | 2 -> 1 0 1 | 1 | 3 1 1 0 | 0 | 1 -> 1 1 1 | 1 | 2 x1 x2 x3 ---------- p|3 2 3 q|2 3 2 __ so x1 ~ x3 and x1 ~ x2 __ S{a,b,c...}(x1, x2, x3) Again, we see that no number that appears in the left half of column S appears in the right, and vice-versa. __ F is symmetric and is S{0,2,3}(x1, x2, x3) c) f=sum(m1, m4, m7) x1 x2 x3 | f | S ------------------- 0 0 0 | 0 | 1 -> 0 0 1 | 1 | 2 0 1 0 | 0 | 0 0 1 1 | 0 | 1 -> 1 0 0 | 1 | 2 1 0 1 | 0 | 3 1 1 0 | 0 | 1 -> 1 1 1 | 1 | 2 x1 x2 x3 ---------- p|2 1 2 q|1 2 1 __ so x1 ~ x3 and x1 ~ x2 __ S{a,b,c...}(x1, x2, x3) Again, we see that no number that appears in the left half of column S appears in the right, and vice-versa. __ F is symmetric and is S{2}(x1, x2, x3) d) f= sum(m1, m4, m6, m7, m8, m11, m14) x1 x2 x3 x4 | f | S --------------------- 0 0 0 0 | 0 | 2 -> 0 0 0 1 | 1 | 3 0 0 1 0 | 0 | 1 0 0 1 1 | 0 | 2 -> 0 1 0 0 | 1 | 1 0 1 0 1 | 0 | 2 -> 0 1 1 0 | 1 | 0 -> 0 1 1 1 | 1 | 1 -> 1 0 0 0 | 1 | 3 1 0 0 1 | 0 | 4 1 0 1 0 | 0 | 2 -> 1 0 1 1 | 1 | 3 1 1 0 0 | 0 | 2 1 1 0 1 | 0 | 3 -> 1 1 1 0 | 1 | 1 1 1 1 1 | 0 | 2 x1 x2 x3 x4 ------------- p|3 4 4 3 q|4 3 3 4 So __ __ f might be S{a,b,c...}(x1, x2, x3, x4) notice that 1 and 3 occur on both sides of column S, so the function is not symmetric. 2.8) What must the values of a, b, c be for the function f to be symmetric. x1 ____ --------- |a 1 1 b| x4||1 c 1 1| || 1||x3 |1 1 1|| --------- --- x2 the equivalent truth table is: x1 x2 x3 x4 | f ---------------- ?? 0 0 0 0 | a -> 0 0 0 1 | 1 -> 0 0 1 0 | 1 0 0 1 1 | 0 -> 0 1 0 0 | 1 ?? 0 1 0 1 | c 0 1 1 0 | 0 0 1 1 1 | 0 ?? 1 0 0 0 | b -> 1 0 0 1 | 1 -> 1 0 1 0 | 1 -> 1 0 1 1 | 1 -> 1 1 0 0 | 1 -> 1 1 0 1 | 1 -> 1 1 1 0 | 1 1 1 1 1 | 0 x1 x2 x3 x4 ---------------------------- p|6+b 4+c 4 4+c q|3+a+c 5+a+b 5+a+b+C 5+a+b where a,b,c must be 0 or 1 From looking at x3's column (in the p-q table), we can see that every column must have a four in it. Looking at x2's column, we can see that q2=5+a+b must be at least 5, therefore p2 must be 4, therefore c=0 Looking at x1's column, we can see that p1=6+b must be at least 6, therefore q2 must be 4, therefore a=1. Substituting in a=1, c=0 yields: x1 x2 x3 x4 | f | S --------------------- -> 0 0 0 0 | 1 | 1 -> 0 0 0 1 | 1 | 2 -> 0 0 1 0 | 1 | 2 0 0 1 1 | 0 | 3 -> 0 1 0 0 | 1 | 2 0 1 0 1 | 0 | 3 0 1 1 0 | 0 | 3 0 1 1 1 | 0 | 4 ?? 1 0 0 0 | b | (3) -> 1 0 0 1 | 1 | 1 -> 1 0 1 0 | 1 | 1 -> 1 0 1 1 | 1 | 2 -> 1 1 0 0 | 1 | 1 -> 1 1 0 1 | 1 | 2 -> 1 1 1 0 | 1 | 2 1 1 1 1 | 0 | 3 x1 x2 x3 x4 ----------------------- p|6+b 4 4 4 q|4 6+b 6+b 6+b __ So we know f might be S{c1,c2,c3...}(x1, x2, x3, x4) Now we can start to fill in the S column. (see above) Looking at the S column, we see that if we make b a 0-point (b=0) then 1's and 2's will occur only on the right hand side of that column, and not on the left, so a=1,b=0,c=0 gives the symmetric function __ S{1,2}(x1,x2,x3,x4) 2.20) for each of the following sets of 3-variable functions determine whether it is strong complete, weak complete, a strong basis, a weak basis. a) {f1} where f1 = sum(m1, m2, m4,m7) f1= x1 ____ --------- | 1 1| |1 1 ||x3 --------- --- x2 __ __ __ __ __ __ SOP form: f= x1 x2 x3 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 Each variable appears both complimented and uncomplimented, so it is definately non-positive. Reed-Muller form: f= a0 XOR a1 x1 XOR a2 x2 XOR a3 x3 XOR a4 x1 X2 XOR a5 x1 x3 XOR a6 x2 x3 XOR a7 x1 x2 x3 a=0 a1=1 a2=1 a3=1 a4=0 a5=0 a6=0 a7=0 so the funciton is linear, therefore by the theorm on page 2.9, the set is not weak complete (and thus not a weak basis,strong-complete, or a strong-basis). b) {f1, f2} f1 from a) and f2=sum(m0, m1, m2, m7) f2= x1 ____ --------- |1 1 | |1 1 ||x3 --------- --- x2 __ __ __ __ SOP form: f= x1 x2 + x1 x2 x3 + x1 x2 x3 Clearly this function is non-positive. Already we know {f1, f2} is not a weak-basis, because eliminating f1 from the set would not leave us with a set that didn't have a non-positive function. RM form: a0=1 a1=1 a2=0 a3=0 a4=0 a5=0 a6=1 a7=0 since a6=1, and 6>3 we know that this function is non-linear, so this set is weak complete. note that f2 by its self would be a weak basis, since it is both non-linear and non-positive. Also, this function is non 0-preserving (f2(0,0,0)=1). but since f1 and f2 are both 1-preserving, the set cannot be strong-complete. c) {f1, f2, f3} where f1 and f2 are the same as above, and f3=sum (m0, m3, m4) f3= x1 ____ --------- |1 1| | 1 ||x3 --------- --- x2 __ __ __ __ SOP form: f= x1 x2 x3 + x1 x2 x3 + x1 x2 x3 Clearly this set is weak-complete, since a subset of it is weak-complete. It is not a weak-basis for the same reason {f1, f2} is not. To establish if the set is strong-complete, we need to see if f3 is non 1-preserving and if f1, f2, or f3 are non-self-dual. f3 is clearly non 1-preserving since f3(1,1,1)=0. let's see if f3 is self-dual f3(000)=1 and f3(111)=0 so far, self dual f3(001)=0 and f3(110)=0 this tells us f3 is not self dual. Therefore this set is strong-complete. We also know it is not a strong-basis, since eliminating f1 from the set still leaves us with a strong-complete set: {f2, f3} has a non-positive function, a non 0-pres. funciton, a non 1-pres. funciton, a non-linear funciton, and a non self-dual funciton. 2.21) A 4-input module realizing a function f(x1, x2, x3, x4) is to be designed and must satisfy the following constraints: __ (i) f(0, x2, x3, x4) = x2 + x3 __ (ii) f(1, 0, 1, x4) = x4 __ (iii) f(1, x2, 0, x4) = x2 (iv) f(x1, x2, 1, 0) = 1 (a) is f() weak complete? A helpful thing to remember is that NAND and NOR are both strong-complete functions. So if we can build a NAND or NOR gate out of F, then we can realize any function. A little experimentation yields f(1, 0, 1, f(0, f(1, 0, 1, A), B, C)) = A NOR B So, because we can build a NOR gate from F, 0, and 1, we know that F is at least weak-complete (and possibly strong-complete) b) if f() strong complete? To answer this question, it will help to build a truth table of F x1 x2 x3 x4 | f ---------------- 0 0 0 0 | 1 (by condition i) 0 0 0 1 | 1 (by condition i) 0 0 1 0 | 1 (by condition i & iv) 0 0 1 1 | 1 (by condition i) 0 1 0 0 | 0 (by condition i) 0 1 0 1 | 0 (by condition i) 0 1 1 0 | 1 (by condition i & iv) 0 1 1 1 | 1 (by condition i) 1 0 0 0 | 1 (by condition iii) 1 0 0 1 | 1 (by condition iii) 1 0 1 0 | 1 (by condition ii & iv) 1 0 1 1 | 0 (by condition ii) 1 1 0 0 | 0 (by condition iii) 1 1 0 1 | 0 (by condition iii) 1 1 1 0 | 1 (by condition iv) 1 1 1 1 | ? x1 ____ --------- |1 0 0 1| x4||1 0 0 1| ||1 1 ? 0||x3 |1 1 1 1|| --------- --- x2 if we make f(1,1,1,1)=0 then: f is not positive: f(1,1,1,1)=0 but f(0,1,1,1)=1 (ie decreasing x1 made the function increase f is not 1-preserving: f(1,1,1,1)=0 f is not 0-preserving: f(0,0,0,0)=1 f is not self-dual: f(0,1,1,1)=1 and f(1,0,0,0)=1 Let's examine the RM form of f to see if it is linear: f= a0 XOR a1 x1 XOR a2 x2 XOR a3 x3 XOR a4 x4 a5 x1 X2 XOR a6 x1 x3 XOR a7 x1 x4 XOR a8 x2 x3 XOR a9 x2 x4 XOR a10 x3 x4 a11 x1 X2 x3 XOR a12 x1 x2 x4 XOR a13 x1 x3 x4 XOR a14 x2 x3 x4 XOR a15 x1 x2 x3 x4 a0=1 a1=0 a2=1 a3=0 a4=0 a5=1 ... already we can see the the function is non-linear, since a5=0 and 5>4. Therefore the function is strong-complete c) if possible specify a function f which is strong complete and satisfies these conditions __ __ and use f to realize the function g = x1 x2 + x1 x2. C is easy, since we already have the k-map for f: __ __ __ __ __ __ __ f = x3 x4 + x1 x2 x3 + x1 x2 x3 + x1 x2 x3 Note f=XOR _ since f is not 1 or 0 preserving f(a,a,a,a) = a so we can construct a NOT gate Since f is not self-dual around the points 1,0,0,0 and 0,1,1,1 _ f(a,a,a,a)=1 or f(f(a,a,a,a),a,a,a)=1 so we can construct 1 if we substitute x3=1 and x4=1 into f, __ it reduces to x1*x2, so we can build "half" of the function. if we substitute x3=1 and x2=1 into f, __ __ it reduces to x4 + x1, so we can build an or gate with both inputs inverted. now we have all we need: let 1=f(f(x1,x1,x1,x1),x1,x1,x1) let a=f(x1,x2,1,1) let b=f(x2,x1,1,1) g= f(f(a,a,a,a),1,1,f(b,b,b,b)) or, substituting them all in: g=f(f(f(x1,x2,f(f(x1,x1,x1,x1),x1,x1,x1)), f(x1,x2,f(f(x1,x1,x1,x1),x1,x1,x1)), f(x1,x2,f(f(x1,x1,x1,x1),x1,x1,x1)), f(x1,x2,f(f(x1,x1,x1,x1),x1,x1,x1))), f(f(x1,x1,x1,x1),x1,x1,x1),f(f(x1,x1,x1,x1),x1,x1,x1),f(x2,x1,f(f(x1,x1,x1,x1),x1,x1,x1)), f(x2,x1,f(f(x1,x1,x1,x1),x1,x1,x1)), f(x2,x1,f(f(x1,x1,x1,x1),x1,x1,x1)), f(x2,x1,f(f(x1,x1,x1,x1),x1,x1,x1)))) :( There is g expressed only in terms of f and the variables x1, x2, x3, and x4. 5.10 ) Write expressions for three-variable functions f(x,y,z) satisfying each of the given specifications. The functions should not be independent of any variable. (obviously there are many correct answers for these problems) a) a function that is both a threshold function, and totally symmetric: S{1}(x,y,z) is also a threshold funciton, where each weight is 1 and the threshold is 1. b) a function that is a threshold function but not symmetric: the threshold funciton: x--2--\ y--1---2--f z--1--/ is clearly not symmetric because variable x could not be switched with any other to produce the same function. (x is not symmetric to any other variable). c) a function that is symmetric, but not a threshold function. This one is trickier. Since there are some symmetric functions that are not unate, but no threshold functions that are not unate, let's try to find a symmetric function that is not unate, and it follows that it won't be threshold: For the first guess, let's try the following function: _ S{3,1}(x,y,z) _ _ _ _ _ _ this is x y z + x y z + x y z + x y z and we see immediately that it is not unate, and therefore not threshold. d) a function that is symmetric, but not unate. same as before, _ _ _ _ _ _ f= x y z + x y z + x y z + x y z _ f = S{3,1}(x,y,z) e) a function that is negative and a threshold function Since f is negative, all the weights should be negative. x-- -1--\ y-- -1---0--f z-- -1--/ satisfies this property. _ _ _ f = x Y z 4.27) Which, if any, of the following functions are fanout-free: It's a good idea to look for pairs of variables you can factor out of the SOP equation. These usually represent adjacent variables. __ __ (a) f = x1 x2 + x1 x3 this isn't even unate (look at x1), so it's clearly not FOF. __ __ __ (b) f2= x1 x2 x3 + x1 x3 x4 __ first off, let's factor out x1*x3 __ __ f2= (x1*x3)(x2 + x4) So F2 is FOF. __ __ __ __ __ (c) f3 = x1 x2 x3 x4 + x1 x2 x4 x5 + x1 x2 x3 x5 __ first factor out x1*x2 __ __ __ f3=(x1 x2)(x3 x4 + x4 x5 + x3 x5) we can see that x1 and x2 are adjacent (a1=0, a2=1), but the other term is not FOF, since there are no adjacent variables in it. so f3 is not FOF. 4.28) which, if any of the functions from problem 4.27 is a threshold function? a) not unate -> not threshold b) We could come up with a long list of constraints based on the minimal 1-points, and the maximal 0-points, but that's necessary for proving that a function is NOT a threshold function. First let's do some guessing and checking and see if we can puzzle out the weights before we do it the long way. __ __ remember f2= (x1*x3)(x2 + x4) since x1 being false, or x3 being true turn the whole function off, let's give x1 a big weight, and x3 a large, negative weight. x1-- 4-\ x2-- ??--\ x3-- -4---??--f x4-- ??-/ after we've established that x1 is true and x3 is false, there is the additional constraint that either x2 or x4-compliment needs to be true, so let's give x2 a small + weight and x4 a small - weight. x1-- 4-\ x2-- 1--\ x3-- -4---??--f x4-- -1-/ now we can look at the minimal 1-points to try and find a threshold minimal 1-points: (1,1,0,1), (1,0,0,0) the values of f corresponding to these points are: 4, 4, so the threshold is 4 x1-- 4-\ x2-- 1--\ x3-- -4---4--f x4-- -1-/ And finally, going through all possible values of x1,x2,x3,x4 shows that this works. __ __ __ __ __ (c) f3 = x1 x2 x3 x4 + x1 x2 x4 x5 + x1 x2 x3 x5 __ __ __ f3=(x1 x2)(x3 x4 + x4 x5 + x3 x5) let's try the same process as before. give x1 a large positive weight and x2 a large negative weight: x1-- 6-\ x2-- -6--\ x3-- ??---??--f x4-- ??--/ x5-- ??-/ For the function to be 1, we know x1 is 1 and x2 is 0. We also know that exactly 2 of x3-compliment, x4 and x5 must be 1 so let's give x3 a small negative weight, and x4 and x5 small positive weights: x1-- 6-\ x2-- -6--\ x3-- -1---??--f x4-- 1--/ x5-- 1-/ Minimal 1-points: (1,0,0,1,0) (1,0,1,1,1) (1,0,0,0,1) consider each of these minimal 1-points as a vector. when we take the dot-product of the point and the vector of weights, we are summing up each variable times its weight. these dot products are: 7, 7, 7. So the threshold should be 7 x1-- 6-\ x2-- -6--\ x3-- -1--- 7 --f x4-- 1--/ x5-- 1-/ to prove that it works.. Here's a truth table: x1 x2 x3 x4 x5 | f | threshold fn ----------------------------------- 0 0 0 0 0 | 0 |0 0 0 0 0 1 | 0 |0 0 0 0 1 0 | 0 |0 0 0 0 1 1 | 0 |0 0 0 1 0 0 | 0 |0 0 0 1 0 1 | 0 |0 0 0 1 1 0 | 0 |0 0 0 1 1 1 | 0 |0 0 1 0 0 0 | 0 |0 0 1 0 0 1 | 0 |0 0 1 0 1 0 | 0 |0 0 1 0 1 1 | 0 |0 0 1 1 0 0 | 0 |0 0 1 1 0 1 | 0 |0 0 1 1 1 0 | 0 |0 0 1 1 1 1 | 0 |0 0 0 0 0 0 | 0 |0 1 0 0 0 1 | 1 |1 1 0 0 1 0 | 1 |1 1 0 0 1 1 | 1 |1 1 0 1 0 0 | 0 |0 1 0 1 0 1 | 0 |0 1 0 1 1 0 | 0 |0 1 0 1 1 1 | 1 |1 1 1 0 0 0 | 0 |0 1 1 0 0 1 | 0 |0 1 1 0 1 0 | 0 |0 1 1 0 1 1 | 0 |0 1 1 1 0 0 | 0 |0 1 1 1 0 1 | 0 |0 1 1 1 1 0 | 0 |0 0 1 1 1 1 | 0 |0 Yes, it's a threshold function.