ĐỀ THI MÔN TOÁN RỜI RẠC
Thời gian: 90 phút
(Sinh viên không được xem tài liệu)
 
Câu 1. Kiểm tra suy luận sau đây bằng 2 cách khác nhau:
p ( (q ( r)
( q ( ( p
p
----------------
( r
Câu 2.
(a)                   Hãy tính số dãy 6 bit khác nhau trong đó số bit 1 là một số chẵn.
(b)                  Cho n là một số nguyên dương. Tính số dãy n bit khác nhau trong đó số bit 1 là một số chẵn.
Câu 3. Cho X = (a,b,c,d,e(.
(a)                   Tìm một quan hệ thứ tự trên X sao cho a là phần tử nhỏ nhất, d và e là 2 phần tử tối đại.
(b)                  Hỏi có bao nhiêu quan hệ thứ tự trên X thỏa điều kiện được yêu cầu trong câu (a).
Câu 4.Tìm công thức dạng chính tắc và các công thức đa thức tối tiểu của hàm Bool f(x,y,z,t) có bảng giá trị như sau:
x
y
z
t
f

1
1
0
0
0

0
0
0
1
1

0
0
1
0
1

0
0
1
1
1

0
1
0
0
1

0
1
0
1
1

0
1
1
0
0

0
1
1
1
0

1
0
0
0
0

1
0
0
1
1

1
0
1
0
1

1
0
1
1
1

1
1
0
0
0

1
1
0
1
0

1
1
1
0
1

1
1
1
1
1

Câu 5. Tính số các hàm Bool theo 3 biến f(x,y,z) thỏa điều kiện
f(x,y,z) = f(x,z,y) = f(y,x,z) với mọi x, y, z.
-----------------------------------
Câu 1. Cho biểu thức logic E theo 4 biến p, q, r, s như sau:
A = (p ( (( q ( r) ( ( s ) ( (( s ( ( r ( p )
Hãy rút gọn biểu thức A và tìm các giá trị của các biến p, q, r, s để cho A = 1.
Câu 2. Cho n là một số nguyên dương và đặt Sn = (1, 2, . . ., n(.
(a)    Tính số tập hợp con của Sn chứa ít nhất một số chẵn trong trường hợp n = 14 và trong trường hợp n = 15.
(b)   Tính số tập hợp con của Sn chứa ít nhất một số chẵn trong trường hợp tổng quát (n tùy ý).
Câu 3.
(a)    Nêu lên định nghĩa về quan hệ thứ tự trên một tập hợp và cho một ví dụ.
(b)   Cho X = (a, b, c, d, e(. Tìm tất cả các quan hệ thứ tự trên X thỏa mãn điều kiện: a là phần tử nhỏ nhất và e là phần tử lớn nhất.
Câu 4. Tìm công thức dạng chính tắc và các công thức đa thức tối tiểu của hàm Bool f(x,y,z,t) có bảng giá trị như sau:
 
x
y
z
t
f

0
0
0
0
1

0
0
0
1
1

0
0
1
0
1

0
0
1
1
0

0
1
0
0
1

0
1
0
1
0

0
1
1
0
0

0
1
1
1
0

1
0
0
0
0

1
0
0
1
1

1
0
1
0
1

1
0
1
1
1

1
1
0
0
1

1
1
0
1
0

1
1
1
0
1

1
1
1
1
1

 
Câu 5. Cho X = (x1, x2, . . ., xn( là một tập hợp hữu hạn có n phần tử. Giả sử R là một quan hệ thứ tự trên X. Hãy viết một thuật toán tìm tất cả các phần tử tối đại của X theo quan hệ thứ tự R.
Câu