5. f,g,h f d,g d,h d. f f = y f d = f(, ȳ) = ȳ = y f f d, f. g g = g d = = g = g d, g. h h = yz y ȳz h d =( y z)( y)( ȳ z) h = h d, h. 5.2 f d ((f d ) d =(f(, 2,..., n )) d = f(, 2,..., n )=f. 5.3 f f d f d = f(, 2,..., n ). h h d h d = ( n+ f d n+ f) d = ( n+ f(, 2,..., n )) ( n+ f(, 2,..., n )) = n+ n+ n+ f(, 2,..., n ) n+ f(, 2,..., n ) f(, 2,..., n ) f(, 2,..., n ) = n+ f(, 2,..., n ) n+ f d (, 2,..., n ) f(, 2,..., n ) f d (, 2,..., n ), h d n+ h d = n+ f(, 2,..., n )f d (, 2,..., n ) n+ f d (, 2,..., n )f(, 2,..., n ) = n+ f(, 2,..., n ) n+ f d (, 2,..., n ) = h, h. 5.4 n, f 0 = f 2n,f = f 2n 2,...,f 2 n = f 2 n.
, f 0,f,...,f 2 n f. n 2 2n. 5.5 : 3 yz f f 2 f 3 f 4 f 5 f 6 f 7 f 8 f 9 f 0 f f 2 f 3 f 4 f 5 f 6 000 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 00 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0, 3 f 2,f 3,f 5,f 7,f 8,f 9,f 0,f 2,f 4,f 5. f 2 = yz ȳz y z yz = y yz z f 3 = y z ȳ z y z yz = y y z z f 5 = ȳz ȳ z ȳz yz = ȳ ȳz z f 7 = ȳz y z ȳ z yz = y z f 8 = ȳz y z yz yz = y yz z f 9 = ȳ z ȳ z ȳz y z = ȳ ȳ z z f 0 = ȳ z yz ȳz y z = ȳ z f 2 = ȳ z y z yz y z = y y z z f 4 = ȳ z ȳz yz ȳz = ȳ ȳz z f 5 = ȳ z ȳz y z ȳ z = ȳ ȳ z z 5.6. (i) (f 0 f f n ) d =(f0 d f d fn) d (f 0 f f n ) d = f 0 (,..., m ) f (,..., m ) f n (,..., m ) = f 0 (,..., m ) f (,..., m ) f n (,..., m ) = f0 d f d fn d (ii) (f 0 f f n ) d = f0 d f d f n d (i). (iii) ( f) d = (f d ) f(,..., n ) d = f(,..., n ) 2
= (f d ) (iv) ( i ) d = i (i =, 2,...,n), (y j ) d = y j (j =, 2,...,m)., F, AND OR f. 5.7., f d F d, 2 F.. F f. 2. F. ()., f d, f d. (f d ) d = f, F f. (2) P F.. F., F F. F F d., F F, F d F d., F d,., P. 5.8 NAND AND NOT, 5.6 f AND OR, f NAND NOR, f f d., f d., f = 2 n f d = f(, 2,..., n ) = ( ) ( 2 ) ( n ) = f (n : ) = f (n : ) f d = f f d = f. 5.9, f(, ) f(, 0) f(, ) f(, 0) = f(, ), f(,y) f(0,y) f(,y) f(0,y)=f(,y). 3
,,. f(, y) = f(, y) f(0, y) = (f(,y) f(0,y)) f(0,y) = f(,y) ( )f(0,y) = f(,y) f(0,y), f(, y) = {yf(, ) ȳf(, 0)} {yf(0, ) ȳf(0, 0)} = yf(, ) ȳf(, 0) y(0, ) ȳf(0, 0) = y{f(, ) f(, 0)} ȳf(, 0) y{f(0, ) f(0, 0)} ȳf(0, 0) = yf(, ) (y ȳ)f(, 0) yf(0, ) (y ȳ)f(0, 0) = yf(, ) f(, 0) yf(0, ) f(0, 0). 5.0 n i i2 ij (0 <j n), i i2 ij i i2 ij i i i 2 i n j, i i2 ij i i i 2 i n j (, 0 i <n, i i j ). i i2 ij. i i2 ij i i i 2 i n j i,, ij, i i,..., i n j., f,,., j i i2 ij,, j i i2 ij., i i2 ij i i i 2 i n j.,.,. 5. n, n/2.. n/2 n C n/2. 5.0, n/2,,.,, 2 nc n/2. n 2 nc n/2. 5.2 f f = y ȳ z = ( ȳ) (y ȳ) z 4
= ȳ z = z ȳ = ( ) ( z) ȳ = z ȳ. f. g g = ȳ y = ( y) (ȳ y) = y. g. h h = ȳ z ȳz w = ȳ ( z z) w = ȳ ( z) w. h. 5.3 n f f = 2 3 n, f(a) =. n = (2 = ), n =2 2 (2 2 = 2), n =3 4 (2 3 = 4), n =4 8 (2 4 =8), f n, f(a) = 2 n. 2: n = 3: n =2 4: n =3 5: n =4 f 2 f 2 3 f 2 3 4 f 2 3 4 f 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 5.4 f(y, ) = (y )(ȳ ) 5
= (ȳ )(y ) = ( ȳ)( y) = f(, y) f. g(, y, z) = y yz z g(, z, y) = z zy y = y yz z = g(, y, z) g(y,, z) = y z zy = y yz z = g(, y, z) g(y, z, ) = yz z y = y yz z = g(, y, z) g(z,, y) = z y yz = y yz z = g(, y, z) g(z,y,) = zy y z = y yz z = g(, y, z) g. y = y yz( ) h = y ȳz yz yz yz = y z yz g(, y, z) h. 5.5 3 f, f = b 0 S0 3 b S 3 b 2 S2 3 b 3 S3 3 (b {0, }). 6. Sφ 3 =0 S{0} 3 = ȳ z S{} 3 S{2} 3 = ȳ z y z ȳz = yz ȳz y z S 3 {3} = yz S{0,} 3 S{0,2} 3 S{0,3} 3 S{,2} 3 S{,3} 3 S{2,3} 3 S{0,,2} 3 S{0,,3} 3 S{,2,3} 3 S{0,2,3} 3 S 3 {0,,2,3} = ȳ z ȳ z y z ȳz = ȳ z zȳ = ȳ z yz ȳz y z = ȳ z yz = ȳ z y z ȳz yz ȳz y z = z y z ȳ = ȳ z y z ȳz yz = ȳ z y z ȳz yz = yz ȳz y z yz = z y yz = ȳ z z y z ȳ = ȳ z = ȳ z zȳ yz = z y z ȳ yz = y z = z y z ȳ ȳ z = y z ȳ z = 5.6 6
n,. n SA n = b i Si n i=0,a {0,,...,n}, b i {0, } A 0 n n + 2, A 2 n+. n 2 n+. 5.7 n Si n, n, i. 3, y, z, 0, f=0,, 2,3 f =., f = S{2,3} 3. 5.8 n n SA n = b i Si n i=0,a {0,,...,n}, b i {0, },,. S n φ =0,S n {0,,...,n} =, n f, AND f f = 2 3 n n. n f, f = 2 3 n 2 f = 2 2 3 n n. n f = 2 n 2 n 2 n 2 3 n n, f n., n, +++n =n +2. 5.9 n,. n SA n = b i Si n i=0,a {0,,...,n}, b i {0, }. 7
, n,., n, f 0,f,...,f 2n, f 0 = f 2n, f = f 2n 2,..., f 2 n = f 2 n., n SA n = b 0 S0 n b S n bn S n n 2 2 b n S n n+ b Sn n b 0 Sn n 2 2., b 0,b,...,bn n+ 2 2., n, n 2 n+ 2. 5.20, f(, 2,..., n )=f( 2,,..., n ), 2., f(, 2,..., n )=f( 2, 3,..., n, ), 2., 2, 3., 2, 3 f(, 2,..., i,..., j,..., n )=f(, 2,..., j,..., i,..., n )., 0 i<j n. ( ) = f(, 2,..., i,..., j,..., n ) = f( i,..., j,..., n,,..., i ) ( 2 i ) = f( i+, i,..., j,..., n,,..., i ) ( ) = f( i,..., j,..., n,,..., i, i+ ) ( 2 ) = f( i, j,..., n,,..., i, i+,..., j ) (, 2 ) = f( j, i,..., n,,..., i, i+,..., j ) ( ) = f( j, j, i,..., n,,..., i, i+,..., j 2 ) ( 3 ) = f( j, j, i,..., n,,..., i, i+,..., j 2 ) ( ) = f( j,..., i,..., n,,..., i ) ( 3, ) = f(, 2,..., i,..., j,..., n ) ( 3 i ) = ( ), f(, 2,..., i,..., j,..., n )=f(, 2,..., j,..., i,..., n ), f., f(, 2,..., n )=f( 2,,..., n )=f( 2, 3,..., n, ) f. 5.22 S{0,,...,n 2} n = f(, 2,..., n )., 2 n 0, f =. 4 4. 4, 6, n =4 n(n )/2., n>4., 2 n 2 2., 2 n 2,, n C 2. S{0,,...,n 2} n nc 2 = n(n )/2. 8
, S{0,,...,n 2} n,n 4 n(n )/2. 3 2 4 : 4 5.2 f 6., f 2. 2(b) f = y z ȳw z w y zw yz zw, AND-OR 3. 6: y z w f 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 9
y z w (a) y z w (b) 2: f y z w y y y z z z z w w w 3: AND-OR 0
5.22 S{0,,...,n 2} n = f(, 2,..., n )., 2 n 0, f =. 4 4. 4, 6, n =4 n(n )/2., n>4., 2 n 2 2., 2 n 2,, n C 2. S n {0,,...,n 2} nc 2 = n(n )/2., S{0,,...,n 2} n,n 4 n(n )/2. 3 2 4 4: 4 5.23 S{m,m+,...,2m} 3m, (3m)!/(m!)3. S{m,m+,...,2m} 3m = f(, 2,..., 3m )., 2 3m c 0., c m 0, c m 2m, c 2m + 3m., 2 3m m 2., 2 3m m,, 3m C m., 3m C m c mi ( i 3m C m ). c mi. c mi c m, 3m m., c 2m, c mi m 2. c 2m, c 2m., c mi, c 2m c mi
., 2m m,, 2m C m. c mi,, 3m C m, 2m C m., 3m C m 2m C m =(3m)!/(m!) 3,, S 3m {m,m+,...,2m}, (3m)!/(m!)3., 2 3m m 2., 2 3m m,, 3m C m., 3m C m =(3m)!/(m!(2m!)), S{m,m+,...,2m} 3m (3m)!/(m!(2m!)). 5.23 S{m,m+,...,2m} 3m, (3m)!/(m!)3. S{m,m+,...,2m} 3m = f(, 2,..., 3m )., 2 3m c 0., c m 0, c m 2m, c 0 2m + 3m., 2 3m m 2., 2 3m m,, 3m C m., 3m C m c mi ( i 3m C m ). c mi. c mi c m, 3m m., c 2m, c mi m 2. c 2m, c mi m c 2m., c mi, c 2m c mi., 2m m,, 2m C m. c mi,, 3m C m, 2m C m., 3m C m 2m C m =(3m)!/(m!) 3,, S 3m {m,m+,...,2m}, (3m)!/(m!)3., 2 3m m 2., 2 3m m,, 3m C m., 3m C m =(3m)!/(m!(2m!)), S{m,m+,...,2m} 3m (3m)!/(m!(2m!)). 2
5.24 S n i nc i. 2,, n C i. 5.25 f, { f w + w 2 2 + + w j j + + w n n t () (, 2,..., n )= w,w 2,...,w n., g = f j ( j n +), (i) j =, g = f = (), w j w = w + w 2 +...+ w n + t w + w 2 2 + + w j j + + w n n t () j =,. { w + w 2 2 + + w j g(, 2,..., n )= j + + w n n t. (ii) j =0, (), j =0, w j j =0, () (). { w + w 2 2 + + w j g(, 2,..., n )= j + + w n n t. (i)(ii) { w + w 2 2 + + w j g(, 2,..., n )= j + + w n n t w = w + w 2 +...+ w n + t, g f f j 3
g = f j, g, ḡ = j f = i f, u, { w + w 2 2 + + w n n t u(, 2,..., n )=, ū, { w + w 2 2 + + w n n <t (2) ū(, 2,..., n )=, (2), w w 2 2 w n n > t (2), w i (i =, 2, n) w i = w i (i =, 2, n),t t = (t + α), α< w i (w i w,w 2,,w n ), (2) w + w 2 2 + w n n t. w i,t, u ū., f f., OR, ḡ. ḡ g. 5.26 (i). (ii) g = ȳ y = y. (iii). (iv) u = y yz = y( z) = y( )( z) = y( z) = y yz,. 4
(v) v = y ȳ = ( ȳ)(y ȳ) = ( ȳ)(y ) = y. 5.27, f. f = { (2 2 2 +4 3 3 ) 0 ( ). f 7, 5. 7: f 2 3 f 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 5: f f. f = 2 3 3 = 3 ( 2 ) 5
, g. g = { ( 4 2 +3 3 ) 0 ( ). g 8, 6. 8: g 2 3 f 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 0 3 2 6: g g. g = 2 2 3 = 2 ( 3 ) 5.28 f i. i w i w i > 0 f(,...,,..., n ) f(,...,0,..., n ), i f. 5.29 f, i i. 6
f i i f { w f + w 2 2 + + w n n t (, 2,..., n )=. f (, 2,..., n ) = = { w + w 2 2 + + w n n <t { w w 2 2 w n n > t. f f d., w + w 2 2 + + w n n (w + w 2 + + w n )= w w 2 2 w n n f f d { f d w + w 2 2 + + w n n > t +(w + w 2 + + w n ) =., w min f d { f d w + w 2 2 + + w n n t +(w + w 2 + + w n )+w min =. f d w i ( i n), t +(w + w 2 + w n )+w min. 5.30. f. f, { w + w 2 y + w 3 z + w 4 w t f =., (, y, z, w) =(,, 0, 0) w + w 2 t,(, y, z, w)=(0, 0,, ) w 3 + w 4 t., w + w 2 + w 3 + w 4 2t., (, y, z, w) =(, 0,, 0) w + w 3 <t,(, y, z, w) =(0,, 0, ) w 2 + w 4 <t. w + w 2 + w 3 + w 4 < 2t, f.,. 5.3 (a) ) =,y 2 = 0, =0, =. (b) ) =,y =,y 2 =,z =, 0, =, =0. 5.32 T i. 5. i 7
., n C i.,, n C i. 5.33 n, m., m +,.,. n,., m +, m +., m +., m+., n C m+ = nc m. 5.34 (i) M(, y, ) = y y = y (ii) M(, y, 0) = y (iii) (ii) y = M(,, 0) = (iv) M(, y, z) M(, y, z) =M(y, z, ) =M(y,, z) (v) M(,, y) = y y = y = M(, y, ȳ) = y yȳ ȳ = y ȳ = (y ȳ) = 8
(vi) M(, ȳ, z) = ȳ ȳ z z = ( y)(y z)(z ) = y yz z = M(, y, z) (vii) z = y y(3 ) M(, y, z) = (y yz) z (z yz)z = y yz yz z yz = y yz z (viii) M( y, z, w) = ( y)z zw ( y)w = z yz zw w yw = z yz zw zw w yw = z zw zw yz zw yw = M(, z, w) M(y, z, w) (viv), M(, u, w)m(z, u, w)=m(z,u,w) M(, u, w)m(z, u, w) = M(, ū, w) M( z,ū, w) = M( z,ū, w) = M(z,u,w) M(M(, u, w),y,m(z, u, w)) = M(, u, w)m(z, u, w) ym(, u, w) ym(z, u, w) = M(z,u,w) ym( z, u, w) = zu zw uw y( z)u ( z)w uw = zw zw uw yu yzu yw yzw uw = (yu yzu zu) (zw yw yzw) uw = um(, y, z) wm(, y, z) uw = M(M(, y, z),u,w) 5.35 5 f, f = 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5 9
2 3 4 5 2 3 4 5 2 3 4 5 2 3 4 5,., n = n. f = 2 3 ( 4 )( 5 ) 2 ( 3 ) 4 ( 5 ) ( 2 ) 3 4 ( 5 ) ( ) 2 3 4 ( 5 ) 2 ( 3 )( 4 ) 5 ( 2 ) 3 ( 4 ) 5 ( ) 2 3 ( 4 ) 5 ( 2 )( 3 ) 4 5 ( ) 2 ( 3 ) 4 5 ( )( 2 ) 3 4 5 2 3 4 ( 5 ) 2 3 ( 4 ) 5 2 ( 3 ) 4 5 ( 2 ) 3 4 5 ( ) 2 3 4 5 2 3 4 5, f = 2 3 2 4 3 4 2 3 4 2 5 3 5 2 3 5 4 5 2 4 5 3 4 5 2 3 4 2 3 5 2 4 5 3 4 5 2 3 4 5. 5.36 5.34(viv) M(M(, 3, 4 ), 5,M( 2, 3, 4 )) = M(M(, 2, 5 ), 3, 4 ). M(M(, 2, 3 ),M(M(, 2, 5 ), 3, 4 ), 5 ) = M(M(, 2, 3 ),M(, 2, 5 ) 3 M(, 2, 5 ) 4 3 4, 5 ) = M( 3 5,, 2 ) 3 M( 3 5,, 2 ) 4 M(, 2, 3 ) 3 4 5 M(, 2, 3 ) M(, 2, 5 ) 3 5 M(, 2, 5 ) 4 5 3 4 5 5.35. 5.37 f(, y, z) = y z NOT: f(,, ) = 0= AND: f(, y, ) = y 0= y f(f(,, ),y,) = y = y OR: f(,,z)= z f(f(,, ),,f(z,, )) = z 5.38 f(,, ) =( ) = 20
y y z v z (a) NOT (b) AND (c) OR 7: AND, OR, NOT, NOT. f(,, z) = ( z) ( z) = z f(f(,, z),f(,, z),f(,, z)) = z = z, OR., f(f(,, ), f(,, ), f(z, z, z)) = z, AND. 5.39 y = z =0 f(, 0, 0) = (NOT), y =0 f(, 0,z)= z NOT AND., z = z OR. 5.40 f(, y) = y, g(, y, z) =y yz z f(,y)= y =ȳ, f NOT. g, z = g(, y, ) = y y = y 2
g(,y, ) = ( ) (y ) ( )(y ) = y = y NOT g(f(,),f(,y), ) = f(,)f(,y) = ȳ = y, OR., f(,g(,y, )) = y = y, AND. 5.4 f = y z, g = y yz z. NOT: f(, y, 0) = 0 0= AND: g(, y, 0) = y 0 0=y OR: g(, y, ) = y y = y 5.42 f(0, 0, 0) = 0 = f. f(,, ) = 0= f. f(, ȳ, z) f(, y, z) f., f. f, y{f(0, 0, 0) f(, 0, 0) f(0,, 0) (,, 0)}, y 2 f. f. 5.43. = y = f = z = z, NOT., z = f = y =y 22
NOT AND., y = ȳ NOT OR.,. 5.44 3 NPN. y yz z y z y z (y z) yz ȳ z yz ȳ z (yz ȳ z) y yz z yz ȳz y z ȳ z yz 5.45 NPN,,,, f d (, 2,..., n )= f(, 2,..., n ), f(, 2,..., n ) NPN., NPN, f f d. 5.46 a) y yz z NP f = y yz z f 2 = y yz z f 3 = ȳ ȳz z f 4 = y y z z f 5 = ȳ ȳz z f 6 = ȳ ȳ z z f 7 = y y z z f 8 = ȳ ȳ z z b) y yz z NPN f,f 2,f 3,f 4,f 5,f 6,f 7,f 8 c) y z NP f 9 = y z f 0 = ȳ z 5.47 23
n 2 n. 2 n, 2 nc 2 n. 5.48. BDD 8. S 3 {,2} = S 3 S3 2 = 2 2 3 3 0 2 2 3 3 0 8: 5.48 BDD 5.49 5. 5.6 6 5.7. F M 0 F., F M F... F f 5.4 f NOT., F M 2. 5.3 0., F M 4 5.2 AND OR. 2. F F M 0 F M 0 f i,0 f j. 5.5 5.6., F M 3 5. NOT. F M 4 5.2 AND OR. F, 5.7. 5.50 g(, 2,, n ), h(y,y 2,,y n ) f = g h 24
= ḡ(, 2,, n ) h(ȳ, ȳ 2,, ȳ n ) = g(, 2,, n ) h(ȳ, ȳ 2,, ȳ n ) = {g(, 2,, n ) h(ȳ, ȳ 2,, ȳ n )} = g(, 2,, n ) h(ȳ, ȳ 2,, ȳ n ) = f d f. 5.5 f d = g(, 2,, n ) h(ȳ, ȳ 2,, ȳ n ) = {g(, 2,, n ) h(ȳ, ȳ 2,, ȳ n )} = {g(, 2,, n ) } {h(ȳ, ȳ 2,, ȳ n ) } = ḡ(, 2,, n ) h(ȳ, ȳ 2,, ȳ n ) = g d h d, g h, f d = g h = f 5.52 f { w + w 2 2 + + w n n t f =. { f d w + w 2 2 + + w n n t +(w + w 2 + + w n )+w min =. w min., f f d. () t t +(w + w 2 + + w n )+w min f { w + w 2 2 + + w n n t t +(w + w 2 + + w n )+w min f = f d f. (2) t +(w + w 2 + + w n )+w min >t f { w + w 2 2 + + w n n > t +(w + w 2 + + w n )+w min >t f = f>f d. 25
,.,,. f. f = yz ȳz y z f f d. f d = ȳ z y z yz f d f f., f. 5.53 f = g 6 f 2 = g 7 f 3 = g 3 f 4 = g 9 f 5 = g 2 f 6 = g 4 f 7 = g f 8 = g 5 f 9 = g 8 26