BÀI KIỂM TRA GIỮA KỲ MẪU
(Môn Toán Rời Rạc 2)
Thời gian làm bài: 60 phút (Được sử dụng tài liệu)

1

Phần trắc nghiệm (4 điểm)

Câu 1. Trong logic mệnh đề, xét biểu thức mệnh đề sau
¬p
với p là một biến mệnh. Khẳng định nào sau đây là đúng?
✄  
✂A ✁ Biểu thức ¬p là hằng sai (contradiction) và không thỏa được (unsatisfiable).
✄  
✂B ✁ Biểu thức ¬p không là hằng đúng (invalid) và không thỏa được (unsatisfiable).
✄  
✂C ✁ Biểu thức ¬p không là hằng đúng (invalid) và thỏa được (satisfiable).
✄  
✂D ✁ Biểu thức ¬p là hằng đúng (valid) và không thỏa được (unsatisfiable).
✄  
✂E ✁ Tất cả các phương án kia đều sai.

Câu 2. Khẳng định nào sau đây là đúng?
✄  
✂A ✁ Không thể có chương trình nào in ra được chính bản thân nó.
✄  
✂B ✁ Phát biểu này không phải là một mệnh đề đúng: ’“Là một phần của câu” là một phần
của câu.’
✄  
✂C ✁ p =: “Câu này sai ” là một biến mệnh đề có thể nhận chân trị đúng hoặc chân trị sai.
✄  

✄  
✂B ✁ Luật Modus Tollens (MT).
✄  
✂C ✁ Tính phi mâu thuẫn (soundness) của các quy tắc suy luận tự nhiên.
✄  
✂D ✁ Tính đầy đủ (completeness) của các quy tắc suy luận tự nhiên.
✄  
✂E ✁ Tính compact (compactness) của các quy tắc suy luận tự nhiên.

2


Câu 5. Xét các bước suy luận sau đây để chứng minh tính đúng đắn của phép suy luận
(sequent)
(∀xP (x)) → Q, ∀xP (x) ∀z(P (z) → Q).
(∀xP (x)) → Q
∀xP (x)

1
2
3

tiền đề
tiền đề

x0

4
5
6

∀z Q(x) ∧ ∀x P (z) → R(x)

∧ R(z) → R(x)

∧ P (x).

Kết quả của phép thay thế (substitution) x ⇒ f (x, y, z)) φ là gì?
✄  
✂A ✁ ∀z
✄  
✂B ✁ ∀z
✄  
✂C ✁ ∀z
✄  
✂D ✁ ∀z
✄  
✂E ✁ ∀z

Q(f (x, y, z)) ∧ ∀x P (z) → R(f (x, y, z)) ∧ R(z ) → R(f (x, y, z)) ∧ P (f (x, y, z))
Q(f (x, y, z)) ∧ ∀x P (z ) → R(x)

∧ R(z ) → R(f (x, y, z))

∧ P (f (x, y, z))

Q(f (x, y, z)) ∧ ∀x P (z ) → R(f (x, y, z)) ∧ R(z ) → R(f (x, y, z)) ∧P (f (x, y, z))
Q(f (x, y, z )) ∧ ∀x P (z) → R(f (x , y, z )) ∧ R(z ) → R(f (x, y, z )) ∧P (f (x, y, z))
Q(f (x, y, z)) ∧ ∀x P (z) → R(x)

∧ R(z) → R(f (x, y, z))

✄  
✂D ✁ nghiệm tối ưu (optimal solution)
✄  
✂E ✁ là một nghiệm chấp nhận được (feasible solution)

4


2

Phần tự luận (6 điểm)

Bài 1. (2 điểm) Hãy giải thích tại sao {∨, ¬} là hệ đầy đủ (adequate set) các liên kết logic,
còn hệ {∧, ∨} thì không?
[viết lời giải vào khoảng trống]
Lời giải Bài 1:

5


Bài 2. (2 điểm) Xét ngôn ngữ gồm một phép toán một ngôi (unary function symbol) f và
một vị từ hai ngôi (binary predicate symbol) R. Xét ba biểu thức sau
φ1 = ∀xR(x, f (x));
φ2 = ∀x∀y∀z(R(x, y) ∧ R(y, z) → R(x, z));
φ3 = ∀x¬R(x, x).
1. Hãy chứng tỏ rằng ba biểu thức trên là nhất quán (consistent).
2. Mô hình của φ1 ∧ φ2 ∧ φ3 có thể hữu hạn (tức là có tập vũ trụ (universe) chỉ gồm hữu
hạn phần tử) hay không? Vì sao?
[viết lời giải vào khoảng trống]


Cửa hàng C2
50000VND
90000VND

Cửa hàng C3
80000VND
30000VND

Hãy lập kế hoạch vận chuyển thỏa mãn được nhu cần của mỗi cửa hàng mà chi phí vận
chuyển thấp nhất.
[viết lời giải vào khoảng trống]
Lời giải Bài 4:

8