Tài liệu Đề thi toán rời rạc và đáp án cao học uit từ năm 2009

ĐỀ THI (PHẦN TOÁN RỜI RẠC) VÀ ĐÁP ÁN TÓM TẮT CỦA CÁC KỲ THI CAO HỌC UIT TỪ 2009 ĐẾN NAY (có bổ sung thêm một số câu hỏi phụ vào đề thi nguyên bản) NĂM 2009 CÂU 1: a) Cho các biến mệnh đề p, q, r, s, t và dạng mệnh đề A = { p  [ p  (r  q) ]  [ r  (s  t) ]  s }  t Chứng minh A hằng đúng (dùng các luật logic hay dùng các qui tắc suy diễn). b) Cho mệnh đề lượng từ B = “  > 0,  > 0, x  R , 0 < | x  a | <   0 < | f(x)  f(a) | <  ’’ . Viết mệnh đề phủ định B . CÂU 2: a) X là tập hợp các ước số dương của 30 và | là quan hệ ước số trên X. Chứng minh | là một quan hệ thứ tự bán phần trên X. Vẽ biểu đồ Hasse cho ( X, | ) và tìm min, max, các phần tử tối tiểu và tối đại (nếu có). b) Cho A = { a, b, c } và quan hệ thứ tự  trên A sao cho b, c là các phần tử tối đại và [ a = min(A,  ) hay a là một phần tử tối tiểu ]. Vẽ các sơ đồ Hasse có thể có cho (A,  ). CÂU 3: a) Viết dạng nối rời chính tắc và tìm các công thức đa thức tối tiểu cho hàm Boole f dưới đây : f(x,y,z,t) = x y z t  x y z  x y z  y z t  x y z  x z t  x y t (ký hiệu  là phép toán tổng Boole) b) Vẽ sơ đồ mạng các cổng logic tổng hợp f dựa vào một công thức đa thức tối tiểu của f. c) Tìm tất cả các hàm Boole g có 4 biến thỏa g(x,y,z,t) = g(y,x,t,z)  (x,y,z,t)  B4. ĐÁP ÁN TÓM TẮT : CÂU 1: a) Cách 1 : Dùng các qui tắc suy diễn. Đặt p (1), [ p  (r  q) ] (2), [ r  (s  t) ] (3), s (4) và t (5). Từ (1), (2) có (r  q) (6). Từ (6) có r (7). Từ (7), (3) có (s  t) (8). Từ (8), (4) có t (5). Vậy A  1 Cách 2 : Dùng các luật logic. Ta có A  p  [ p  ( r  q ) ]  [ r  ( s  t ) ]  (s  t)   [( p  p)( p  r  q )]  {(r  s  t)  [( s  t )  (s  t)]}  [1  ( p  r  q )]  { (r  s  t)  1}  ( p r  q )  ( r  s  t )  (r  r )  ( p  q  s  t )  1  ( p  q  s  t )  1 b) B = “ > 0,  > 0, x  R , 0 < | x  a | <  và [ f(x) = f(a) hay | f(x)  f(a) |   ] ’’ CÂU 2: a) X = { 1, 2, 3, 5, 6, 10, 15, 30 }. | phản xạ ( x  X, 1  Z, x = 1.x nên x | x ). | phản xứng [ x, y  X, ( x | y & y | x )  ( u, v  Z, y = ux và x = vy trong đó u, v  1 do x, y  1 )  ( y  x & x  y )  ( x = y ). | truyền [ x, y, z  X, ( x | y & y | z )  ( u, v  Z, y = ux và z = vy )   (  w = uv  Z, z = wx)  ( x | z ). Vậy | là một quan hệ thứ tự trên X. Đây là thứ tự bán phần vì  2, 3  X, 2 vả 3 không phải là ước số của nhau ( nghĩa là 2 và 3 không so sánh được bởi quan hệ thứ tự | ). Sơ đồ Hasse của (X, | ) có thể vẽ như một hình hộp chữ nhật mà các phần tử của X được ghi ở các đỉnh của hình hộp . Hai phần tử kề nhau có thương số là một số nguyên tố . Ta có min( X, | ) = 1 và max( X, | ) = 30. b) TH1 : [ b, c là các phần tử tối đại và a = min (A,  ) ] : có 1 khả năng xảy ra (a kề b, a kề c). TH2 : [ b, c là các phần tử tối đại và a là 1 phần tử tối tiểu ] : có 4 khả năng xảy ra (a, b, c cô lập), (c cô lập, a kề b), (b cô lập, a kề c), (a kề b và a kề c). Vẽ biểu đồ Hasse cho mỗi khả năng nói trên. CÂU 3: a) Viết f(x,y,z,t) = = x y z t  x y z(t  t )  x y z(t  t )  (x  x )y z t  x y z (t  t )  x (y  y ) z t  x y(z  z ) t = xy zt  x yz t  x yz t x y z t x y zt  x yz t x yz t  x y z t  xy z t x yz t   x y z t  x y z t ( đã loại bỏ một đơn thức tối tiểu trùng lặp ) S = Kar(f) = K(x y z t )  K(x y z)  K( x y z)  K(y z t)  K(x y z )  K( x z t )  K(x y t ) = { (1,1), (1,2), (1,4), (2,2), (2,4), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (4,4) } ( S có 12 ô ). S có 7 tế bào lớn T1 = x t , T2 = y t , T3 = x y, T4 = x z , T5 = y z , T6 = z t và T7 = x y z. Thuật toán cho 3 phép phủ của S theo sơ đồ sau : T3  T4  T5  T7  T2 (phép phủ tối tiểu)  T1  T6 (phép phủ tối tiểu)  T2 (phép phủ chưa tối tiểu) S = T3  T4  T5  T7  T2 = T3  T4  T5  T7  T1  T6 = T3  T4  T5  T7  T1  T2 (hai phép phủ đầu tiên là tối tiểu, phép phủ thứ 3 chưa tối tiểu nên bị loại) Ta có f(x,y,z,t) = x y  x z  y z  x y z  y t = x y  x z  y z  x y z  x t  z t Công thức đa thức tối tiểu của f là f(x,y,z,t) = x y  x y z  x z  y z  y t b) Vẽ sơ đồ mạng các cổng logic tổng hợp f(x,y,z,t) = x y  x y z  x z  y z  y t c) f(x,y,z,t) = ax y z t  bx y z t  c x y z t  d x y z t  e( x y z t  x y z t )  u( x y z t  x y z t )   v( x y z t  x y z t )  w( x y z t  x y z t )  r( x y z t  x y z t )  s( x y z t  x y z t) trong đó a, b, c, d, e, u, v, w, r, s là các số nhị phân tùy ý ( lấy trị số 0 hoặc 1 ). NĂM 2010 (ĐỢT 1) CÂU 1: a) Hãy trình bày 5 luật logic bất kỳ (trong số 10 luật logic). b) Cho các biến mệnh đề p, q, r và dạng mệnh đề A = [ ( p  q )  ( p  r )  ( q  r ) ]  r Chứng minh A hằng đúng (dùng các luật logic hay dùng các qui tắc suy diễn). c) Cho mệnh đề lượng từ B = “ x  R, y  R , (x + y  2) hay (2x  y  1) ’’ . Viết mệnh đề phủ định B rồi suy ra chân trị của B. CÂU 2: Cho các số nguyên dương n và k thỏa k < n. a) Có bao nhiêu dãy có n bits mà trong đó có ít nhất k bit 1? b) Có bao nhiêu dãy có 16 bits mà trong đó có ít nhất 4 bit 1 hay có ít nhất 4 bit 0 ? c) Có bao nhiêu dãy có 16 bits mà trong đó có ít nhất 9 bit 1 hay có ít nhất 9 bit 0 ? d) Có bao nhiêu dãy có 16 bits mà trong đó có ít nhất 8 bit 1 và có ít nhất 8 bit 0 ? CÂU 3: a) Viết dạng nối rời chính tắc cho hàm Boole fm dưới đây (ký hiệu  là phép toán tổng Boole) : fm(x,y,z,t) = x y z t  x y z  x y z t  x y z  x y z t  x y z t  x y t  m.x y z t với m  { 0, 1 } b) Xác định m sao cho fm(x,y,z,t) có công thức đa thức tối tiểu đơn giản nhất. c) Vẽ sơ đồ mạng các cổng logic tổng hợp fm dựa vào công thức đơn giản nhất tìm được ở câu b). ĐÁP ÁN TÓM TẮT : CÂU 1: a) Trình bày 5 luật : phủ định kép, lũy đẳng, giao hoán, phủ định DE-MORGAN và hấp thu. b) Cách 1 : Dùng các qui tắc suy diễn. Đặt ( p  q ) (1), ( p  r ) (2), ( q  r ) (3) và r (4). Từ (2), (3) có [ ( p  q )  ( r  r ) ] (5). Từ (5), (1) có r (4). Vậy A  1 . Cách 2 : Dùng các luật logic. Ta có A  ( p  q )  ( p  r )  [ ( q  r )  r ]   ( p q )  ( p r )  [ ( q  r )  (r  r ) ]  ( p q )  ( p r )  [ ( q  r )  1 ]  ( p q )  ( p r )  ( q  r )  [ ( p q )  q ]  [ ( p r )  r ]   [ ( p  q )  (q  q ) ]  [ ( p  r )  (r  r ) ]  [ ( p  q )  1 ]  [ ( p  r )  1 ]   (pq)(pr)  (pp)(qr)  1(qr)  1. c) B = “ x  R, y  R , ( x + y = 2 ) và ( 2x  y = 1 ) ’’ . Lấy x = 0 thì không có y  R thỏa ( y = 2 ) và (  y = 1 ), nghĩa là B sai và B đúng. CÂU 2: a) Có ( Cnk + Cnk 1 + Cnk  2 + … + Cnn 1 + Cnn ) dãy c) Có 2( C169 + C1610 + … + C1616 ) dãy b) Có 216 dãy (vì mọi dãy đều thỏa như yêu cầu) d) Có C168 dãy (các dãy đó có 8 bit 1 và 8 bit 0) CÂU 3: a) fm(x,y,z,t) = x y z t  x y z  x y z t  x y z  x y z t  x y z t  x y t  m.x y z t = = x y z t  x y z (t  t )  x y z t  x y z (t  t )  x y z t  x y z t  x y (z  z ) t  m.x y z t = = x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  m.x y z t b) Khi m = 0 : S0 = Kar(f0) = K( x y z t )  K( x y z)  K( x y z t)  K(x y z )  K(x y z t)  K(x y z t )  K(x y t) = { (1,4), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (4,1), (4,2), (4,4) } ( S0 có 10 ô ) S0 có 6 tế bào lớn T1 = z t, T2 = x t, T3 = x z , T4 = x y t , T5 = y z t và T6 = x y z . Thuật toán cho 3 phép phủ của S0 theo sơ đồ sau : T1  T3  T4 (phép phủ tối tiểu)  T6  T5 (phép phủ tối tiểu)  T4 (phép phủ chưa tối tiểu) S0 = T1  T3  T4 = T1  T3  T6  T5 = T1  T3  T6  T4 (hai phép phủ đầu tiên là tối tiểu, phép phủ thứ 3 chưa tối tiểu nên bị loại) Ta có f0(x,y,z,t) = z t  x z  x y t và f0(x,y,z,t) = z t  x z  x y z  y z t Công thức đa thức tối tiểu của f0 là f0(x,y,z,t) = z t  x z  x y t Khi m = 1 : S1 = Kar(f1) = = K( x y z t )  K( x y z)  K( x y z t)  K(x y z )  K(x y z t)  K(x y z t )  K(x y t)  K(x y z t ) = { (1,1), (1,4), (2,1), (2,2), (2,3), (2,4), (3,1), (3,2), (4,1), (4,2), (4,4) } ( S1 có 11 ô ) S1 có 6 tế bào lớn T1 = z t, T2 = x t, T3 = x z , Z4 = y t , Z5 = x y và T6 = x y z . Thuật toán cho một phép phủ của S theo sơ đồ sau : T1  T3  Z4 Ta có phép phủ tối tiểu duy nhất của S1 là S1 = T1  T3  Z4 Công thức đa thức tối tiểu của f1 là f1(x,y,z,t) = z t  x z  y t Vậy khi m = 1 thì fm(x,y,z,t) có công thức đa thức tối tiểu đơn giản nhất là f1(x,y,z,t) = z t  x z  y t . c) Vẽ sơ đồ mạng các cổng logic tổng hợp f1(x,y,z,t) = z t  x z  y t . NĂM 2010 (ĐỢT 2) CÂU 1: a) Hãy trình bày 5 luật logic bất kỳ (trong số 10 luật logic). b) Cho các biến mệnh đề p, q, r, s, t và dạng mệnh đề A = { [ p  ( q  r ) ]  ( p  s )  ( t  q ) s }  (r  t ) Chứng minh A hằng đúng (dùng các luật logic hay dùng các qui tắc suy diễn). c) Cho mệnh đề lượng từ B = “ x  N, y  N, k  N, kx = y ’’. Xét chân trị của B và viết mệnh đề phủ định B . CÂU 2: Xét các biển số xe có dạng    x y z t u v trong đó , ,  là các mẫu tự latin ( từ A đến Z ) và x, y, z, t, u, v, w là các chữ số hệ thập phân ( từ 0 đến 9 ). a) Có bao nhiêu biển số xe như trên ? b) Có bao nhiêu biển số xe có các mẫu tự đều khác nhau và có đúng một chữ số 3 và một chữ số 5 ? c) Có bao nhiêu biển số xe có ít nhất một chữ số 3 và có ít nhất một chữ số 5 ? CÂU 3: Cho hàm Boole f theo 4 biến x, y, z, t dưới đây (ký hiệu  là phép toán tổng Boole) : f(x,y,z,t) = x y z t  x z  x y z t  y z t  x y z t  x y z  x z t  x y t a) Vẽ biểu đồ Karnaugh S = Kar(f) và xác định các tế bào lớn trong S. b) Viết dạng nối rời chính tắc và tìm các công thức đa thức tối tiểu cho hàm Boole f. c) Vẽ sơ đồ mạng các cổng logic tổng hợp f dựa vào một công thức đa thức tối tiểu của f. ĐÁP ÁN TÓM TẮT : CÂU 1: a) Trình bày 5 luật : kết hợp, phân phối, trung hòa, thống trị và bù. b) Cách 1 : Dùng các qui tắc suy diễn. Đặt [ p  ( q  r ) ] (1), ( p  s ) (2), ( t  q ) (3), s (4) và ( r  t ) (5). Từ (2), (4) có p (6). Từ (6), (1) có ( q  r ) (7). Từ (7), (3) có ( t  r ) (8). Từ (8) có ( r  t ) (5). Vậy A  1 . Cách 2 : Dùng các luật logic. Ta có A  { ( p  q  r )  ( p  s )  s  ( t  q ) }  ( r  t )   { ( p  q  r )  [( p  s )  ( s  s ) ]  ( t  q ) }  ( r  t )   {( p  q  r)  [(p  s )  O]  ( t  q)}  (r  t )} { ( p  q  r)  p  s  ( t  q) }  ( r  t )  (p  q  r )  p  s  ( t  q )  ( r  t )  {( p  p )  [ (q  r )  p ) ]}  s  [( t  q )  t ]  r  {1  [ ( q  r )  p ] }  s  [ ( t  t )  ( q  t ) ]  r  [ (q  r )  p ]}  s  [ 1  ( q  t )]  r  [ ( q r )  (q  r ) ]  ( p  s t )  1  ( p  s t )  1 c) B đúng vì x = 1 N, y  N, k = y  N, kx = k.1 = k = y. B = “ x  N, y  N, k  N, kx  y ’’ . CÂU 2: a) Có 263 x 106 = 17.576 x 106 biển số xe. 3 b) Có A26 x A62 x 84 = 1.916.928 x 106 biển số xe c) Số biển số xe không có chữ số 3 là 263 x 96. Số biển số xe không có chữ số 5 là 263 x 96. Số biển số xe không có chữ số 3 và không có chữ số 5 là 263 x 86 . Dùng nguyên lý bù trừ, ta có Số biển số xe không có chữ số 3 hay không có chữ số 5 là 263(96 + 96  86) = 263(2.96  86). Dùng cách đếm phần bù, ta có số biển số xe có ít nhất một chữ số 3 và có ít nhất một chữ số 5 là 263 x 106  [ 263(2.96  86) ] = 263(106  2.96 + 86) = 17.567(106  1.062.882 + 262.144) = = 17.567 x 199.262 = 3.500.435.554 . CÂU 3: a) S = Kar(f) = = K( x y z t)  K(x z)  K( x y z t )  K(y z t)  K(x y z t)  K(x y z )  K( x z t )  K(x y t ) = {(1,1), (1,2), (1,4), (2,1), (2,2), (3,1), (3,2), (3,3), (4,1), (4,2), (4,3), (4,4)} (S có 12 ô). S có 4 tế bào lớn T1 = x, T2 = y t , T3 = z t và T4 = y z . b) Gọi tên mỗi ô của S và nối chúng bằng phép toán tổng Boole (  ), ta được được dạng nối rời chính tắc của f như sau : f(x,y,z,t) = x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x yz t  xy zt  x y z t Ta có phép phủ tối tiểu duy nhất S = T1  T2  T4 ( theo sơ đồ T1  T2  T4 ) Công thức đa thức tối tiểu của f là f(x,y,z,t) = x  y t  y z c) Vẽ sơ đồ mạng các cổng logic tổng hợp f(x,y,z,t) = x  y t  y z NĂM 2011 (ĐỢT 1) CÂU 1: a) Cho các biến mệnh đề p, q, r, s và dạng mệnh đề A = { p  [ ( q  r )  s ] } [ s  ( r  p) ] . Dùng các luật logic để rút gọn A về dạng (a  b)  (u  v  w  t) trong đó a, b, u, v, w, t được chọn từ { p, q, r, s, p , q , r , s }. Từ đó xác định chân trị của p, q, r và s để A có chân trị đúng. b) Cho vị từ p(x), q(x), r(x) và s(x) với x  X. Giải thích suy luận sau là đúng: x  X, p(x)  q(x) x  X, q( x )  s(x) x  X, r(x)  s ( x) x  X, p( x) ----------------------- x  X, r ( x) CÂU 2: a) Có bao nhiêu byte ( với 8 bits ) có bit đầu tiên là 1 hay có hai bit cuối là 00 ? b) Mỗi password là một dãy ký tự có 6, 7 hoặc 8 ký tự xếp liền nhau. Mỗi ký tự là một chữ số hệ thập phân (từ 0 đến 9) hoặc là một mẫu tự latin (từ A đến Z) và trong password phải có ít nhất một chữ số. Hỏi có bao nhiêu password thỏa các điều kiện trên ? CÂU 3: Cho hàm Boole f theo 4 biến x, y, z và t thỏa f 1(0) = { (0,0,1,1), (0,1,1,1), (1,1,1,0), (1,0,0,1) } a) Vẽ biểu đồ Karnaugh S = Kar(f) và xác định các tế bào lớn trong S. b) Viết dạng nối rời chính tắc và tìm các công thức đa thức tối tiểu cho hàm Boole f . c) Vẽ sơ đồ mạng các cổng logic tổng hợp f dựa vào một công thức đa thức tối tiểu của f. ĐÁP ÁN TÓM TẮT : CÂU 1: a) A  p  [ ( q  r )  s ]  [ s  ( r  p ) ]  ( p  u )  (s  v ) với u = [ ( q  r )  s ] và v = ( r  p ). Để ý (u  s)  [( q  r)  ( s  s)]  [( q  r)  O ]  O, ( p v)  r  (p  p )  r  O  O và ( u  v )  [ r  ( q  r ) ]  s  p  [ ( r  q )  ( r  r ) ]  s  p  [ ( r  q )  O ]  s  p   r q s  p . Ta có A  ( p  s )  ( p  v )  ( u  s )  ( u  v )  ( p  s )  O  O  ( u  v ) ( p  s )  ( u  v )  ( p  s )  ( r  q  s  p ). Suy ra A đúng  [ ( p  s ) đúng ] hay [ ( r  q  s  p ) đúng ]  ( p sai và s đúng ) hay ( p đúng và q, r, s đều sai ) b) Đặt x  X, p(x)  q(x) (1), x  X, q( x )  s(x) (2), x  X, r(x)  s ( x) (3), x  X, p( x) (4) và x  X, r ( x) (5). Từ (4), ta có x = a  X, p(a ) (6). Từ (1), ta có p(a)  q(a) (7). Từ (7), (6) ta có q(a) (8). Từ (2) ta có q(a )  s(a) (9). Từ (9), (8), ta có s(a) (10). Từ (3), ta có r(a)  s (a ) (11). Từ (11), (10), ta có r (a ) , nghĩa là có x = a  X, r ( x) (5). CÂU 2: a) Số chuỗi (8 bits) có (bit đầu = 1) là 27. Số chuỗi (8 bits) có (2 bit cuối = 00 ) là 26. Số chuỗi (8 bits) có (bit đầu = 1) và có (2 bit cuối = 00) là 25 . Theo nguyên lý bù trừ, Số chuỗi (8 bits) có (bit đầu = 1) hay (2 bit cuối = 00) là (27 + 26)  25 = (128 + 64)  32 = 160. b) Nếu password có 6 ký tự, dùng cách đếm phần bù, ta có số password có ít nhất 1 chữ số là (366  266). Tương tự khi password có 6 hoặc 7 ký tự, ta có số password có ít nhất 1 chữ số là (367  267) hoặc (368  268) . Theo nguyên lý cộng, kết quả chung là (366  266) + (367  267) + (368  268) = 1333.366  703.266 CÂU 3: a) S = Kar(f) = {(1,1), (1,3), (1,4), (2,1), (2,2), (3,2), (3,3), (3,4), (4,1), (4,2), (4,3), (4,4)} (S có 12 ô). Gọi tên mỗi ô của S và nối chúng bằng phép toán tổng Boole (  ), ta được được dạng nối rời chính tắc của f như sau : f(x,y,z,t) = x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y zt x yz t  xy zt x y zt S có 8 tế bào lớn T1 = y t , T2 = x t , T3 = y z , T4 = x z , T5 = z t , T6 = x y z , T7 = x z t và T8 = x y t Thuật toán cho 13 phép phủ (sau khi loại ra 3 phép phủ trùng lặp) và ta chọn ra 5 phép phủ tối tiểu của S : S = T2  T4  T7  T1  T3 = T2  T4  T6  T8  T5 = = T2  T4  T6  T8  T3  T1 = T2  T4  T6  T7  T3  T5 = T2  T4  T7  T1  T8  T5 f có công thức đa thức tối tiểu duy nhất tương ứng với phép phủ đầu tiên là f(x,y,z,t) = x t  x z  x z t  y t  y z b) Vẽ sơ đồ mạng các cổng logic tổng hợp f(x,y,z,t) = x t  x z  x z t  y t  y z NĂM 2011 (ĐỢT 2) CÂU 1: a) Cho các biến mệnh đề p, q, r, s, t và dạng mệnh đề A = { [ p  ( q  r ) ]  ( p  s )  ( t  q ) s ]  ( r t ) Chứng minh A hằng đúng (dùng các luật logic hay dùng các qui tắc suy diễn). b) Cho các mệnh đề lượng từ A = “ ( x  X, p(x) )  ( x  X, q(x) ) ’’ và B = “ x  X, y  X, p(x)  q(y) ’’ Viết các mệnh đề phủ định A và B để chứng minh A  B. CÂU 2: Xét các biển số xe có dạng     x y z t u trong đó , , ,  là các mẫu tự latin ( từ A đến Z ) và x, y, z, t, u là các chữ số hệ thập phân ( từ 0 đến 9 ). a) Có bao nhiêu biển số xe như trên ? b) Có bao nhiêu biển số xe có các chữ số đều khác nhau và có đúng một mẫu tự A và một mẫu tự B ? c) Có bao nhiêu biển số xe có ít nhất một mẫu tự A và có ít nhất một mẫu tự B ? CÂU 3: Cho hàm Boole f theo 4 biến x, y, z và t thỏa f 1(1) = = { (0,0,0,0),(1,0,0,0),(0,1,0,0),(0,0,1,0),(0,0,0,1),(1,0,0,1),(1,0,1,0),(0,1,1,0),(1,1,1,0), (0,1,1,1),(1,1,1,1) } a) Vẽ biểu đồ Karnaugh S = Kar(f) và xác định các tế bào lớn trong S. b) Viết dạng nối rời chính tắc và tìm các công thức đa thức tối tiểu cho hàm Boole f. c) Vẽ sơ đồ mạng các cổng logic tổng hợp f dựa vào một công thức đa thức tối tiểu của f. ĐÁP ÁN TÓM TẮT: CÂU 1: a) Để ý ( r  t )  ( r  t ) nên phần này trùng với phần a) CÂU 1 của ĐỀ THI 2010 (đợt 2). b) A = “ ( x  X, p( x) )  ( x  X, q( x ) ) ’’  “ ( x  X, p( x) )  ( y  X, q( y ) ) ’’ B = “ x  X, y  X, ( p( x)  q( y ) ) ’’ Ta có A  B ( vì đều có nghĩa là có a, b  X thỏa p(a ) và q(b) ). Suy ra A  B. CÂU 2: a) Có 264 x 105 = 456.976 x 105 biển số xe. b) Có A42 x 242 x A105 = 12 x 576 x 30240 = 209.018.880 biển số xe c) Số biển số xe không có mẫu tự A là 254 x 105 . Số biển số xe không có mẫu tự B là 254 x 105 . Số biển số xe không có mẫu tự A và không có mẫu tự B là 244 x 105 . Dùng nguyên lý bù trừ, ta có Số biển số xe không có mẫu tự A hay không có mẫu tự B là 105(254 + 254  244) = 105(2.254  244). Dùng cách đếm phần bù, ta có số biển số xe có ít nhất một mẫu tự A và có ít nhất một mẫu tự B là 264 x 105  [ 105(2.254  244) ] = 105(264  2.254 + 244) = 105( 456.976  781.250 + 331.776) = = 7.502 x 105. CÂU 3: a) S = Kar(f) = { (1,1), (1,2), (1,3), (1,4), (2,2), (2,3), (3,1), (3,4), (4,1), (4,3), (4,4) } ( S có 11 ô ). S có 5 tế bào lớn T1 = z t , T2 = y t , T3 = y z, T4 = x t và T5 = y z . b) Gọi tên mỗi ô của S và nối chúng bằng phép toán tổng Boole (  ), ta được dạng nối rời chính tắc của f như sau : f(x,y,z,t) = x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y zt  xy z t Thuật toán cho 2 phép phủ của S theo sơ đồ sau : T3  T5  T4  T1 (phép phủ tối tiểu)  T2 (phép phủ tối tiểu) S = T3  T5  T4  T1 = T3  T5  T4  T2 (hai phép phủ đều tối tiểu) f có 2 công thức đa thức tối tiểu đơn giản ngang nhau là f(x,y,z,t) = y z  x t  y z  z t = y z  x t  y z  y t c) Vẽ sơ đồ mạng các cổng logic tổng hợp f(x,y,z,t) = y z  x t  y z  z t NĂM 2012 (ĐỢT 1) CAÂU 1 : a) Cho các biến mệnh đề p, q, r . Chứng minh A  B trong đó A = { p  [ q  ( p  q  r ) ] } và B = [ q  ( p  r ) ] . 2 1 b) Cho C = “ x  (0, +), y  Q, 2 e y  x + “ trong đó Q là tập hợp các số hữu tỉ. x C đúng hay sai ? Tại sao ? Viết mệnh đề phủ định C . CAÂU 2 : 3 bác sĩ, 4 kỹ sư và 5 luật sư xếp thành một hàng dọc. Hỏi có bao nhiêu cách xếp nếu a) Các đồng nghiệp đứng gần nhau ? b) Các kỹ sư đứng gần nhau và các luật sư đứng gần nhau ? c) Mỗi bác sĩ đứng giữa 2 kỹ sư và các luật sư đứng gần nhau ? CAÂU 3 : Cho haøm Boole f theo 4 bieán coù coâng thöùc ña thöùc nhö sau : f(x, y, z, t) = x y z t  y z t  x y z  x y z t  x z t  x y z ( ký hiệu  là phép toán tổng Boole ) a) Veõ bieåu ñoà Karnaugh S = Kar(f) vaø xaùc ñònh caùc teá baøo lôùn trong S. b) Tìm caùc coâng thöùc ña thöùc toái tieåu cho f. c) Từ S = Kar(f), hãy viết dạng nối rời chính tắc của hàm Boole f và f . d) Vẽ sơ đồ mạng các cổng logic tổng hợp f dựa vào một công thức đa thức tối tiểu của f. ĐÁP ÁN TÓM TẮT: CÂU 1 : a) A  p  q  ( p  q  r )  u  ( u  r ) [ với u = ( p  q ) ]  ( u  u )  ( u  r )   1  (u  r )  u  r  p  q  r  q  ( p  r )  [ q  ( p  r ) ] = B 2 b) C đúng vì  x = 1  (0, +), y  Q, 2 e y  2e0 = 2 = 1 + (1/1) 2 C = “ x  (0, +), y  Q, 2 e y < x + (1/x) “ CÂU 2 : a) 3! ( 3! 4! 5! ) = 103.680 cách xếp b) 5! ( 4! 5! ) = 345.600 cách xếp c) 2 ( 3! 4! 5! ) = 34.560 cách xếp CÂU 3 : a) S = Kar(f) = K( x y z t )  K( y z t)  K( x y z)  K(x y z t )  K( x z t)  K(x y z ) = = { (1,3), (2,1), (2,3), (2,4), (3,1), (3,3), (3,4), (4,1), (4,2), (4,3) } ( S có 10 ô ). b) Các tế bào lớn trong S : T1 = y t, T2 = x t, T3 = x y, T4 = x y z , T5 = x z t và T6 = y z t . T5 (phép phủ chưa tối tiểu)  Thuật toán cho 3 phép phủ của S theo sơ đồ sau : T1  T3  T4  T6 (phép phủ tối tiểu)  T5 (phép phủ tối tiểu) S = T1  T3  T4  T5 (1) S = T1  T3  T4  T6 (2) S = T1  T3  T5 (3) Phép phủ (1) chưa tối tiểu nên ta loại. Phép phủ (2) và (3) đều tối tiểu . Từ (2) và (3), ta có f(x,y,z,t) = y t  x y  x y z  y z t = y t  x y  x z t f có công thức đa thức tối tiểu duy nhất ứng với phép phủ (3) : f(x,y,z,t) = y t  x y  x z t c) S là phần bù của S trong bảng mã của B4 thì S = { (1,1), (1,2), (1,4), (2,2), (3,2), (4,4) } ( 6 ô ). Gọi tên mỗi ô của S (tương ứng S ) và nối chúng bằng phép toán tổng Boole (  ), ta được dạng nối rời chính tắc của f (tương ứng f ) như sau : f(x,y,z,t) = x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y zt  xy z t f (x,y,z,t) = x y z t  x y z t  x y z t  x y z t  x y z t  x y z t d) Vẽ sơ đồ mạng các cổng logic tổng hợp f(x,y,z,t) = y t  x y  x z t NĂM 2012 (ĐỢT 2) CÂU 1: Cho 0 < a < b và H = { z  C / (z2  a2)( z2 + b2) = 0 }. Trên tập hợp (H) = { A / A  H } ta có quan hệ hai ngôi  . a) Kiểm chứng  là một quan hệ thứ tự bán phần trên (H) . b) Vẽ biểu đồ Hasse rồi tìm min, max, tối tiểu và tối đại (nếu có) của ((H) ,  ). CÂU 2: Cho N = { 1, 2, 3, … , 1998, 1999 } và M = { 1, 2, 3, … , 498, 499 }. a) Có bao nhiêu số k trong N sao cho k không chia hết cho cả 3, 4 và 5 ? b) Có bao nhiêu số k trong M sao cho khi chia k cho 3, 4 và 5, ta đều có số dư là 2 ? CÂU 3: Cho hàm Boole f theo 4 biến x, y, z và t thỏa f 1(1) = { (1,0,0,0), (1,1,0,0), (1,0,1,0), (0,1,1,0), (0,1,1,1), (1,1,0,1), (1,1,1,1) } a) Vẽ biểu đồ Karnaugh S = Kar(f) và xác định các tế bào lớn trong S. b) Viết dạng nối rời chính tắc và tìm các công thức đa thức tối tiểu cho hàm Boole f. c) Vẽ sơ đồ mạng các cổng logic tổng hợp f dựa vào một công thức đa thức tối tiểu của f. ĐÁP ÁN TÓM TẮT: CÂU 1 : H = { a, a, bi, bi } và H có 24 = 16 tập con là A1 = , A2 = {a}, A3 = {a}, A4 = {bi}, A5 = {bi}, A6 = { a, a }, A7 = { a, bi }, A8 = { a, bi }, A9 = { a, bi }, A10 = { a, bi }, A11 = { bi, bi }, A12 = { a, a, bi}, A13 = { a, a, bi}, A14 = { a, bi, bi}, A15 = { a, bi, bi} và A16 = H = { a, a, bi, bi } Như vậy (H) = { A / A  H } có 16 phần tử là A1, A2, … và A16 . a) Quan hệ  phản xạ (A  (H), A  A ), phản xứng [ A, B  (H), ( A  B và B  A )  A = B ] và truyền [ A, B, C  (H), (A  B và B  C)  A  C ] nên  là một quan hệ thứ tự trên (H). Do có A2 = {a} và A3 = {a} thỏa A2  A3 và A3  A2 nên quan hệ thứ tự  là bán phần. b) Vẽ cạnh nối cho mọi cặp phần tử kề nhau trong (H) bởi quan hệ  . Để ý mỗi cặp phần tử kề nhau trong (H) chính là 2 tập hợp con bất kỳ của H có quan hệ  và có số phần tử sai kém nhau là 1 ( chẳng hạn A1 nối với A2 , A3 , A4 , A5 ; A2 nối với A6 , A7 , A8 ; A6 nối với A12, A13 ; A12 nối A16 , … ). c) min((H),  ) =  và max((H),  ) = H. CÂU 2 : a) N = { 1, 2, 3, …, 1998, 1999 }, A = { n  N / 3 n }, B = { n  N / 4 n } và C = { n  N / 5 n }. A  B = { n  N / 12  n }, A  C = { n  N / 15  n } và B  C = { n  N / 20  n }  N  = 1999,  A  = 666,  B  = 499,  C  = 399,  A  B  = 166,  A  C  = 133 và  B  C  = 99 A  B  C = { n  N / 60  n } và  A  B  C  = 33 .  A  B  C  =  A  +  B  +  C   (  A  B  +  A  C  +  B  C  ) +  A  B  C  = 1199 . Đáp số cần tìm là  N    A  B  C  = 1999  1199 = 800. b) M = { 1, 2, 3, … , 498, 499 }. Xét n  M sao cho khi n chia cho 3, 4 và 5 đều có số dư là 2. Suy ra (n  2) là bội số của 3, 4 và 5. Vậy (n  2) là bội số của (3 x 4 x 5) = 60 nghĩa là (n  2)  { 0, 60, 120, 180, 240, 300, 360, 420, 480 }. Do đó n  { 2, 62, 122, 182, 242, 302, 362, 422, 482 }. CÂU 3: a) S = Kar(f) = { (1,1), (1,3), (2,2), (2,3), (3,2), (4,1), (4,2) } ( S có 7 ô ) . Các tế bào lớn trong S : T1 = x y t , T2 = x z t , T3 = x y z , T4 = x y t, T5 = y z t và T6 = x y z. b) Gọi tên mỗi ô của S và nối chúng bằng phép toán tổng Boole (  ), ta được dạng nối rời chính tắc của f như sau : f(x,y,z,t) = x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t T4 (phép phủ tối tiểu)  Thuật toán cho 3 phép phủ của S theo sơ đồ sau : T1  T6  T3  T5 (phép phủ tối tiểu)  T4  T2 (phép phủ tối tiểu) S = T1  T6  T3  T4 = T1  T6  T3  T5 = T1  T6  T4  T2 ( 3 phép phủ tối tiểu ) f có 3 công thức đa thức tối tiểu ngang nhau : f(x,y,z,t) = x y t  x y z  x y z  x y t = x y t  x y z  x y z  y z t = x y t  x y z  x y t  x z t c) Vẽ sơ đồ mạng các cổng logic tổng hợp f(x,y,z,t) = x y t  x y z  x y t  x y z NĂM 2013 (ĐỢT 1) CAÂU 1 : a) Cho các biến mệnh đề p, q, r . Chứng minh A  B trong đó A = { [ p  ( q  r ) ]  ( p  r ) } và B = [ p  ( q  r ) ] . b) Cho mệnh đề C = “ x  Q, y  R, ey + ey < 2x ’’. Viết mệnh đề phủ định C và xét chân trị của C. CAÂU 2 : Cho S = {1, 2, …. , 14, 15} và A = {1, 2, 5, 8, 10, 14}. a) A có bao nhiêu tập hợp con mà mỗi tập con đó có không quá 3 phần tử ? Có bao nhiêu tập hợp con B của S thỏa B  A = S ? b) Có bao nhiêu tập hợp con C có 4 phần tử của S mà tổng của các số trong C là một số nguyên chẵn ? c) Có bao nhiêu tập hợp con D của S mà tích của các số trong D là một số nguyên lẻ ? CAÂU 3 : Cho S = {2, 6, 8, 10, 24, 30, 36, 60, 72, 90}. Xét quan hệ thứ tự  trên S như sau : x, y  S, x  y  x | y (x là ước số của y) Vẽ sơ đồ Hasse cho (S, ) và tìm các phần tử cực tiểu (hoặc tối tiểu), cực đại (hoặc tối đại), nếu có. ĐÁP ÁN TÓM TẮT: CÂU 1: a) A  p  (q  r )  ( p  r )  [ p  q  r ]  ( p  r )  [ p  ( q  r ) ]  ( p  r )  ( p  r  q )  ( p  r )  (u  q)  u [ với u = (p  r ) ]  (u  u )  (q  u )  1  ( q  u )  ( q  u )  ( q  p  r )  ( p  q r )  [ p  ( q r ) ] = B b) C = “ x  Q, y  R, ey + ey  2x ‘’. C đúng vì x = 0  Q, y  R, ey + ey  2 e y e y = 2  1 = 20 (bất đẳng thức Cauchy). Vậy C sai. CÂU 2: a) Số tập con của A (mỗi tập có không quá 3 phần tử) là C60 + C61 + C62 + C63 = 1 + 6 + 15 + 20 = 42 B = (S \ A)  H với H tùy ý  A. Số tập B = Số tập H = 26 = 64 b) Đặt S = {2, 4, 6, … , 12, 14} thì | S2 | = 7. C có thể gồm (4 số chẵn) hoặc (4 số lẻ) hoặc (2 số chẵn và 2 số lẻ). Số tập C thỏa yêu cầu là C74 + C84 + C72 C82 = 35 + 70 + (21 x 28) = 105 + 588 = 693 c) D tùy ý  S1 = {1, 3, 5, … , 13, 15} với | D |  2 và | S1 | = 8. Số tập D là 28  (1 + 8) = 247 CÂU 3: min(S, ) = 2 và các phần tử tối đại của (S, ) là 60, 72 và 90. NĂM 2013 (ĐỢT 2) CAÂU 1: a) Cho các biến mệnh đề u, v, w . Chứng minh A  B trong đó A = { [ u  ( u  w ) ]  (v  w)  w } và B = v  (u  w) . Với P bất kỳ, ký hiệu P được hiểu là dạng phủ định của P. b) Cho mệnh đề C = “  > 0, p  N, m, n  N, (m > n  p  0 <xm  xn <  )’’. Hãy viết mệnh đề phủ định C . CAÂU 2 : Cho tam giác MNP. Chọn tùy ý 4 điểm trên cạnh MN, 5 điểm trên cạnh NP và 6 điểm trên cạnh MP (các điểm này đều khác nhau và không trùng với các điểm M, N và P). Gọi H là tập hợp các tam giác tạo bởi 3 điểm không thẳng hàng trong số 15 điểm đã chọn. a) H có bao nhiêu tam giác không có cạnh nào nằm trên các cạnh của tam giác MNP ? b) H có bao nhiêu tam giác có 1 cạnh nằm trên một cạnh nào đó của tam giác MNP ? c) H có tất cả bao nhiêu tam giác ? CAÂU 3 : Cho haøm Boole f theo 4 bieán coù coâng thöùc ña thöùc nhö sau : f(x, y, z, t) = x y z t  x y z t  yz t  x y z  y z t  x y z t (ký hiệu  là phép toán tổng Boole) a) Veõ bieåu ñoà Karnaugh S = Kar(f) vaø xaùc ñònh caùc teá baøo lôùn trong S. b) Viết dạng nối rời chính tắc và tìm caùc coâng thöùc ña thöùc toái tieåu cho f. c) Vẽ sơ đồ mạng các cổng logic tổng hợp f dựa vào một công thức đa thức tối tiểu của f. ĐÁP ÁN TÓM TẮT: CÂU 1: a) A  [ u  ( u  w )]  [( v  w )  w ]  [( u  u )  ( u  w )]  [( v  w )  ( w  w )]  (u  w )  ( v  w )  (u  v  w )  ( w  v  w )  (u  v  w )  ( v u  w )  v  uw = B b) C = “  > 0, p  N, m, n  N, ( m > n  p và [ xm = xn hay  xm  xn    ] ) ‘’. CÂU 2: a) 4 x 5 x 6 = 120 c) 120 + 301 = 421 b) (5 + 6) C42 + (4 + 6) C52 + (4 + 5) C62 = 66 + 100 + 135 = 301 CÂU 3: a) S = Kar(f) = K(x y z t)  K( x y z t)  K(yz t )  K(x y z )  K(y z t)  K( x y z t ) [ S có 9 ô ] Các tế bào lớn trong S là T1 = y z, T2 = x z t, T3 = x y t, T4 = x y t, T5 = x y z và T6 = y z t . b) Gọi tên mỗi ô của S và nối chúng bằng phép toán tổng Boole (  ), ta được dạng nối rời chính tắc của f như sau : f(x,y,z,t) = x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t  x y z t Thuật toán cho 3 phép phủ của S theo sơ đồ : T1  T4  T6  T3 (phép phủ tối tiểu)  T2  T5 (phép phủ tối tiểu)  T3 (phép phủ chưa tối tiểu) S = T1  T4  T6  T3 = T1  T4  T6  T2  T5 = T1  T4  T6  T2  T3 ( hai phép phủ đầu tiên là tối tiểu và phép phủ thứ 3 chưa tối tiểu nên bị loại ) Vậy f(x,y,z,t) = y z  x y t  y z t  x y t = y z  x y t  y z t  x z t  x y z Ta có công thức đa thức tối tiểu của f là f(x,y,z,t) = y z  x y t  y z t  x y t c) Vẽ sơ đồ mạng các cổng logic tổng hợp f(x,y,z,t) = y z  x y t  y z t  x y t NĂM 2014 (ĐỢT 1) CÂU 1: a) Cho C = “ x   , y   , y = cosx hay y = sinx’’. Viết mệnh đề phủ định C và xét chân trị của C. b) Cho các biến mệnh đề u, v, w . Chứng minh A  B trong đó A = { [ (v  w)  w ]  u  (u  w) } và B = u  (v  w) . CÂU 2: Xét các dãy số gồm a) Có bao nhiêu dãy Có bao nhiêu dãy b) Có bao nhiêu dãy Có bao nhiêu dãy 8 chữ số hệ thập phân ( chẳng hạn như dãy số 74285403, ... ) số như vậy ? số mà các chữ số trong đó đều khác nhau ? số mà trong đó mỗi chữ số 1, 4 và 9 xuất hiện đúng một lần ? số mà trong đó có ít nhất một trong 3 chữ số 1, 4 hay 9 ? CÂU 3: Cho S = {3, 6, 9, 15, 18, 27, 30, 54, 90, 270}. Xét quan hệ hai ngôi  trên S như sau: x, y  S, x  y  x  y (x là bội số của y). a) Giaûi thích  laø moät quan heä thöù töï treân S.  laø thöù töï toàn phần hay bán phần ? b) Vẽ sơ đồ Hasse cho (S, ) và tìm các phần tử cực tiểu (hoặc tối tiểu), cực đại (hoặc tối đại), nếu có. ĐÁP ÁN TÓM TẮT: CÂU 1: ( 2,5 đ = 1 đ + 1,5 đ ) a) C = “ x   , y   , y  cosx và y  sinx. 1    ). Do đó C sai. C đúng ( vì    , y   , y  cos = sin = 4 4 4 2 b) A  ( v  w  w)  (u  u  w )  [( v  w )  w)]  [u  ( u  w )]  [( v  w)  ( w  w)]  [(u  u )  (u  w )]  [( v  w)  1]  [ O  (u  w )]  ( v  w)  (u  w )  [( v  u  w )  (w  u  w )]  [( v  u  w )  (u  w  w )]   [( v  u  w )  O]  ( v  u  w )  [u  ( v  w )]  [u  v  w ]  u  (v  w) = B CÂU 2: a) 108 = 100.000.000 A108 = 10 x 9 x 8 x 7 x 6 x 5 x 4 x 3 = 1.814.400. và b) A83 x 75 = 336 x 16807 = 5.647.152 và 108  78 = 100.000.000  5.764.801 = 94.235.199. CÂU 3: a)  phản xạ (x  S : x = 1.x nên x  x ),  phản xứng ( x,y  S : [x  y và y  x]  [x = ky và y = k’x với k, k’ nguyên ≥ 1]  [ x ≥ y và y ≥ x ]  [ x = y ] ),  truyền (x,y,z  S : [x  y và y  z]  [x = ky và y = k’z với k, k’ nguyên ≥ 1]  [ x = kk’y với kk’ nguyên ≥ 1 ]  [ x  y ] )  là thứ tự bán phần ( vì 6, 9  S, 6  9 và 9  6 ). b) (S, ) min(S, ) = 270 và max(S, ) = 3.