Đề thi toán rời rạc và đáp án cao học UIT từ năm 2009 - pdf 28

Link tải luận văn miễn phí cho ae Kết Nối

CÂU 1:
a) Cho các biến mệnh đề p, q, r, s, t và dạng mệnh đề
t s }  t) ]  (s  [ r  q) ]  (r  [ p A = { p
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, > R , 0x 0, < a || x < 0  < f(a) || f(x) < ’’ .
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ó).
trên A sao cho b, c là các phần tử tối đại vàb) Cho A = { a, b, c } và quan hệ thứ tự
). ) hay a là một phần tử tối tiểu ]. Vẽ các sơ đồ Hasse có thể có cho (A, [ a = min(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 :
là phép toán tổng Boole) x y t (ký hiệu  x z t  x y z  y z t  x y z  x y z f(x,y,z,t) = x y z t

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.
B4. (x,y,z,t) 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)

ĐÁP ÁN TÓM TẮT :
CÂU 1:
t) ] (3), s (4) và t (5). (s  q) ] (2), [ r  (r a) Cách 1 : Dùng các qui tắc suy diễn. Đặt p (1), [ p
t) (8). Từ (8), (4) có t (5). q) (6). Từ (6) có r (7). Từ (7), (3) có (s Từ (1), (2) có (r
1Vậy A
 t)  (s  t ) ]  ( s  [ r  q ) ]  ( r  [ p  p Cách 2 : Dùng các luật logic. Ta có A
1} t)  s  { (r  q )]  r  ( p  [1  t)]}  (s  t )  [( s  t)  s  {(r  q )]  r ( p  p) [( p 
1 t )  s  q  ( p  1  t )  s  q  ( p  r )  (r  t )  s  ( r  q ) r  ( p 
b) B = “ > 0, > R , 0x 0, < a || x < ] ’’  f(a) |  và [ f(x) = f(a) hay | f(x) 

CÂU 2:
a) X = { 1, 2, 3, 5, 6, 10, 15, 30 }.
Z, x = 1.x nên x | x ).1  X, x | phản xạ (
X, ( x | yx, y | phản xứng [ & 1 do Z, y = ux và x = vy trong đó u, v u, v  ( y | x )
x ( y  1 ) x, y & ( x = y ). y ) x
X, ( x | yx, y, z | truyền [ &  Z, y = ux và z = vy ) u, v  ( y | z )
( x | z ). Z, z = wx)  w = uv  ( 
X, 2 vả 3 không phải là 2, 3 Vậy | là một quan hệ thứ tự trên X. Đây là thứ tự bán phần vì
ướ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.


) ] : có 1 khả năng xảy ra (a kề b, a kề c).b) TH1 : [ b, c là các phần tử tối đại và a = min (A,
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) =
z ) t x y(z  y ) z t  x (y  t )  x y z (t  x )y z t  (x  t )  x y z(t  t )  x y z(t = x y z t
x yz t  xy z t  x y z t x yz t  x yz t x y zt x y z t  x yz t  x yz t = xy zt
x y z t ( đã loại bỏ một đơn thức tối tiểu trùng lặp ) x y z t 
K(x y t ) K( x z t )  K(x y z )  K(y z t)  K( x y z)  K(x y z) S = Kar(f) = K(x y z 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.
T2 (phép phủ tối tiểu) T7  T5  T4 Thuật toán cho 3 phép phủ của S theo sơ đồ sau : T3


T6 (phép phủ tối tiểu)T1

T2 (phép phủ chưa tối tiểu)
T2 T1  T7  T5  T4  T6 = T3  T1  T7  T5  T4  T2 = T3  T7  T5  T4 S = T3
(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)
z t x t  x y z  y z  x z  y t = x y  x y z  y z  x z Ta có f(x,y,z,t) = x y
y t y z  x z  x y z Công thức đa thức tối tiểu của f là f(x,y,z,t) = x y
y t y z  x z  x y z b) Vẽ sơ đồ mạng các cổng logic tổng hợp f(x,y,z,t) = x y
 x y z t )  u( x y z t  x y z t )  e( x y z t  d x y z t  c x y z t  bx y z t c) f(x,y,z,t) = ax y z t
x y z t) s( x y z t  x y z t )  r( x y z t  x y z t )  w( x y z t  x y z t )  v( 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 hay 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).
r r ) ]  ( q  r )  ( p  q ) b) Cho các biến mệnh đề p, q, r và dạng mệnh đề A = [ ( p
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).
1) ’’ . y  2) hay (2x  R , (x + y y  R, x c) Cho mệnh đề lượng từ B = “
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:
là phép toán tổng Boole) :a) Viết dạng nối rời chính tắc cho hàm Boole fm dưới đây (ký hiệu
{ 0, 1 } m.x y z t với m  x y t  x y z t  x y z t  x y z  x y z t  x y z fm(x,y,z,t) = x y z t
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


wPvIdVUMRoAOoUl
Music ♫

Copyright: Tài liệu đại học © DMCA.com Protection Status