Đề thi cuối học kỳ môn Luận lý toán học năm 2008 - Mã đề 0101
Mã số đề 0101
LUẬN LÝ TOÁN HỌC
Thí sinh được sử dụng tài liệu và giữ lại đề thi.
Thời gian làm bài : 90 phút.
Qui ước : a, b, c, … là hằng, x, y, z ... là biến.
1*. Chọn phát biểu sai :
@a. P Q R không ở dạng chuẩn giao.
b. Công thức nguyên là vị từ có thông số được thay bằng các nguyên từ.
c. Định nghĩa của khái niệm phân giải là định nghĩa đệ qui.
d. Có thể dùng thuật toán hằng đúng để kiểm tra tính khả sai của 1công thức.
2*. Chứng minh F (q1q2) ├─ (Fq1) (Fq2) (trong LLMĐ)
1. F (q1q2) tiền đề
4. q1 e 3
5. q2 e 3
7. Fq2
8. nif (Fq1)(Fq2) i 6,7
9. (Fq1) (Fq2) e 2,6,7,8
i 2,5
2. If F
3. q1q2
e 1,2
6. Fq1 i 2,4
@a. sai từ dòng 6 b. sai từ dòng 7 c. sai từ dòng 8 d. Chứng minh đúng.
3*. Chọn phát biểu đúng và bao quát nếu có thể :
@a. Định lý (soundness). Nếu F├─H thì F╞═H. b. Hợpnối 2 thaythế có tính
phốihợp.
c. Dạng chuẩn Skolem S của F còn tương đương với F. d. Câu a, b, c đều đúng.
4*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Thuật toán hằng sai cùng cho kết quả yes với F và F. Vậy F hằng sai.
b. DC Prenex của x(y(p(x) r(y)) z q(z)) là xyz ((p(x) r(y)) q(z))
c. Hệ thống mâu thuẫn là khả sai, khả đúng.
@d. Có câu sai trong 3 câu a, b, c.
5*. Chọn phát biểu đúng và bao quát nếu có thể :
a. {p(f(x)) r(z)} ở dc Skolem.
b. x y(p(x)q(b,y)) ở dc Prenex.
c. ╞/═ (xH) H[a/x], với H là công thức, a là hằng. @d. Các câu a, b, c đều đúng.
6*. Chọn phát biểu sai :
@a. Qui tắc (i) : dòng 1: if F, dòng 1+k : nif FG, dòng 2+k : FG.
b. Một công thức hằng sai nếu phân giải ra được mệnh đề hằng sai.
c. xy (p(x) q(y)) = yx (p(x) q(y)).
d. Hàm là ánh xạ từ Dn vào D của miền đối tượng D, với n 0.
7*. A = p(f(x)) r(a), B = p(f(a)) r(x), C = p(f(x)) r(z), D = p(x) r(z),
pgb(A, B) = K, pgb (C, D) = H. (Ghi chú : không phân giải nhị phân được = kpgđ)
a. K = , H = r(z)
@c. K = hằng đúng, H = kpgđ
b. K = , H =kpgđ
d. K = hằng đúng, H = r(z)
8*. F= ((P (Q R)) (Q R)) P,và G = ((P Q) R) (R (Q P))
a. F, G hđ. b. F, G kđks. @c. F hđ, G kđks. d. F, G hs.
1
Mã số đề 0101
9*. Chọn phát biểu sai :
@a. Qui tắc (e) : dòng m : F F, dòng k : .
b. H là hệ quả luận lý của F thì tập các mô hình của H chứa tập mô hình của F.
c. {A, B, C, F} là 1 dòng của bảng thực trị của F = (A B) C.
d. Dạng chuẩn Skolem bảo toàn tính hằng sai.
10*. Chọn phát biểu sai :
a. Dạng chuẩn Prenex vẫn tương đương với công thức ban đầu.
b. Đoạn chứng minh sau : dòng 1 : if x0, dòng n : nif q(x0), dòng n+1 : x q(x) sử
dụng qui tắc i.
c. (P Q R) ở dạng chuẩn hội.
@d. Có câu sai trong 3 câu a, b, c.
11*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Dòng A=0, B=1, F= 1 của bảng thực trị được biểu diễn ở dạng {A, B, F}.
b. Công thức A hằng đúng nên A khả sai.
@c. Unifier là mgu của {E1, ..., Ek} nếu ( unifier )( thay thế ) ( = ).
d. Thừa số của 1 công thức là kết quả của công thức qua tác động của 1 mgu.
12*. = <R, F, C> với R = {p(_)}, F = {s(_), m(_,_)}, C = {}.
Diễn dịch I : D = {word | word là từ trên tập ký tự {0, 1}}, I() = 10.
I(s) là hàm endcut bỏ ký tự cuối của từ, thí dụ endcut(111001) = 11100.
I(m) là hàm mix kết nối xen kẻ 2 từ, thí dụ mix(000, 11111) = 01010111.
I(p) là vị từ cir, cir(x) đúng nếu x là tuần hoàn có chiều dài chẵn, thí dụ 10, 01, 1010,
0101, ... Nếu x = 0011 thì I(m(s() + s(x))) = ?, I(p(m(s() + s(x))) = ?.
a. 0101, đúng. @b. 1001, sai. c. 1010, đúng.
d. 0011, sai.
13*. Chọn phát biểu đúng và bao quát nếu có thể :
a. (F ├─ H) là công thức hằng đúng với F, H là công thức LLMĐ.
b. Luận lý vị từ chấp nhận dạng hội, giao vô hạn các công thức.
c. Phạm vi của (x) là p(x) trong công thức (y)(r(y)) (x)(p(x) q(z)).
@d. Có câu sai trong 3 câu a, b, c.
14*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Qui tắc (i) còn gọi là Modus ponens. b. Công thức hằng sai có ít nhất 1mô hình.
@c. Công thức F (G F) là khả đúng khả sai, với F, G là công thức.
d. Một dạng chuẩn Skolem của F : SF = {p(a, b, f(y)) q(y), h(y, z)}.
15*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Dạng chuẩn Skolem S của F còn tương đương với F theo nghĩa hằng sai.
b. mgu của {p(x, f(x, g(x)), y), p(a, z, g(w))} là = a/x, f(a, g(a))/z, , g(w)/y
c. Hai côngthức tươngđương nếu có cùng tập các mô hình. @d.Câu a, b, c đều đúng.
16*. F = x p(x, a) z y (q(x, y) r(z)), t nào tự do đối với x trong F :
a. t = f(z, y). @b. t = g(w). c. t = z.
d. Các câu a, b, c đều sai.
2
Mã số đề 0101
17*. Chọn phát biểu sai :
@a. Hệ thống là một công thức gồm hội các thành phần của hệ thống.
b. Có thể dùng thuật toán hằng sai để kiểm tra tính hằng đúng của 1công thức.
c. ╞═ x (H H[a/x]), H là công thức, a là hằng. d. Có câu sai trong 3 câu a, b, c.
18*. R = {ptrên(_,_), ptròn(_), pvuông(_), pthoi(_)}, F = {fnón(_)}.C = {cMinh}.
Cho 1 diễn dịch I : D = {▲, , , },
cMinh =▲.
ptrên = {(, ▲), (, )}, ptròn = {}, pvuông = {}, pthoi = {, }.
fnón = {(▲, ), (, ), (, ), (▲, )}
E = x (pvuông(x) ptròn(x)), F = x y (ptrên(x, y) ptrên(y, x)).
Đánh giá E, F trong diễn dịch I.
a. E , F đúng. b. E đúng, F sai. @c. E sai, F đúng. d. E, F sai.
19*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Từ dòng m : F, viết ra dòng m+k : F (G H) là áp dụng qui tắc i.
b. ├─ F F còn gọi là qui tắc suy luận triệt tam (LEM).
c. f(a) trong p(x) r(f(a)) là một nguyên từ.
@d. Câu a, b, c đều đúng.
20*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Công thức khả sai nếu có ít nhất một mô hình.
@b. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
c. Mệnh đề rỗng là công thức vừa hằng sai vừa hằng đúng.
d. Định lý completeness. Nếu F├─ H thì F╞═ H.
21*. Chọn phát biểu đúng và bao quát nếu có thể :
a. pg(F, G) ╞═ F G.
@b. Luận lý mệnh đề không chấp nhận dạng hội, giao vô hạn các công thức.
c. Công thức đóng là công thức có ít nhất 1 biến có tất cả hiện hữu ràng buộc.
d. Biểu thức vị từ là giá trị đúng sai của vị từ trong thế giới thật.
22*. Nếu nhiệt độ và áp suất không đổi thì trời không mưa. Nhiệt độ vẫn không đổi. Vì vậy
nếu trời mưa thì áp suất thay đổi.
A = nhiệt độ không đổi, B = áp suất không đổi, C = trời mưa.
Vị từ ch(x) : x không thay đổi và p() : trời mưa, hằng a, b.
a. (AB) C, A ╞═ C B
c. Câu a, b đều sai.
b. (ch(a)ch(b)) p(), ch(a) ╞═ p() ch(b)
@d. Câu a, b đều đúng.
23*. Chọn phát biểu đúng và bao quát nếu có thể :
a. F ╞═ H nếu tập mô hình của H là tập con của tập mô hình của F.
@b. y x K ╞/═ x y K.
c. Hằng không là nguyên từ.
d. Công thức G = (xy (p(x) q(y))) ở dạng chuẩn Prenex.
24*. Diễn dịch D = {1, 2}, I = { p(1), p(2), q(1), q(2)} là mô hình của công thức :
@a. x t (p(x) q(t)) x p(x).
c. x t (p(x) q(t)) x p(x).
b. t x (p(x) q(t)) x p(x).
d. Câu a, b, c đều đúng.
3
Mã số đề 0101
25*. Chọn phát biểu đúng và bao quát nếu có thể :
a. F và dạng chuẩn Skolem của F tương đương nhau.
b. Mệnh đề trong LLVT là giao các lưỡng nguyên.
c. pg(p(x) q(f(y)), q(a) r(x)) = p(x) r(x). @d. Có câu sai trong 3 câu a, b, c.
26*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Công thức hoàn hảo chỉ là công thức nguyên.
@b. Qui tắc e, dòng 1 : F G, dòng 2 : if F, dòng 2+m : nif H, dòng 3+m : if G,
dòng 3+m+n : nif H, dòng 4+m+n : H.
c. G = p(x) p(f(y)) là một thừa số của T = p(x) r(y) p(f(y)) r(y).
d. Mô hình của 1 công thức là diễn dịch mà công thức được đánh giá trong đó.
27*. Chọn phát biểu sai :
a. Công thức của LLMĐ biểu diễn được 1 câu khai báo.
b. Vị từ là quan hệ trên tập Dn của miền đối tượng D, với n 0.
@c. Chứng minh eq(t1, t2)├─ eq(t2, t1). Đặt F = eq(x, t1). Dòng 1: eq(t1, t2), dòng 2:
eq(t1, t1), dòng 3: eq(t2, t1). Dòng 3 sử dụng qui tắc (=i) 1, 2.
d. Có câu sai trong 3 câu a, b, c.
28*. Chọn phát biểu đúng và bao quát nếu có thể :
a. (F G) F là công thức hằng sai. b. Biểu thức vị từ là nguyên từ.
@c. DC Prenex của x ( z r(x,z) x p(x) ) là x z t (r(x,z) p(t))
d. Các câu a, b, c đều sai.
29*. Chọn phát biểu sai :
a. Hệ thống mâu thuẫn là hằng sai. @b. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
c. Biểu thức hàm là nguyên từ. d. Công thức hằng đúng nếu mọi diễn dịch là mô hình.
30*. Chọn phát biểu sai :
a. “Nếu hàm f khả vi thì f liên tục”, và “f không liên tục”, vậy “f không khả vi”. Lập
luận sử dụng qui tắc modus tolens.
@b. Lưỡng nguyên là công thức nguyên hoặc công thức.
c. Thuật toán hằng sai cho kết quả no với F và yes với F. Vậy Fhằng đúng.
d. = {f(t)/x, z/t} và = {a/x, b/t, t/z}. = {f(b)/x, t/z}.
31*. Câu nào ở dạng chuẩn Skolem :
a. {p(x) q(y), p(f(x)) r(z)}
c. {p(x) q(b) x y}
b. {p(a) xq(x)}
@d. Các câu a, b, c đều sai.
32*. Chứng minh F x q(x) ├─ x (F q(x)) với x không tự do trong F.
1. F x q(x) tđề
2. if F
4. if xo
5. q(xo)
7. If x (F q(x)) i 4,6
e 3
8. x (F q(x))
e 3,4-7
3. x q(x) e 1,2 6. nif F q(xo) i 2,5
@a. áp dụng sai qui tắc i, if
c. áp dụng sai qui tắc if, e
b. áp dụng sai qui tắc i, e
d. Chứng minh đúng.
4
Mã số đề 0101
33*. mgu của {p(x, h(y)), p(x, z), p(f(y), w) là :
a. = f(y)/x, z/w, h(y)/z .
c. = f(y)/x, w/z, h(y)/z.
@b. = f(y)/x, h(y)/w, h(y)/z.
d. Câu a, b, c đều đúng.
34*. M1 = r(y) q(a), M2 = p(x) r(y), M3 = q(a) p(x), M4= q(a) r(y),
M5= r(y), bằng phân giải chứng minh {M1, M2, M3, M4, M5} hằng sai :
a. pg(M2, M3) = F, pg(M2, M1) = G, pg(F, G) = .
b. pg(M3, M2) = F, pg(M4, F) = G, pg(M1, G) = .
c. pg(M2, M1) = F, pg(M4, F) = G, pg(M5, G) = . @d. Câu a, b, c đều sai.
35*. Công thức x (p(x) y (q(f(x)) r(y)) ) với D = {1, 2} có mô hình là :
@a. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q( 2), r(1), r(2)}. b. Câu a, b đều sai.
c. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q(2), r (1), r(2)}. d. Câu a, b đều đúng.
36*. Chọn phát biểu sai :
a. Công thức (F (G F)) là định lý, với F, G là công thức.
b. Nguyên tắc phân giải dựa trên qui tắc truyền.
@c. Đoạn chứng minh sau : dòng 3 : if x0 p(x0), dòng 4 : p(x0) q(x0), dòng 5 : nif
q(x0), dòng 6 q(x0), không có lỗi.
d. ((x) p(x,y) q(t,y)) (y)(r(x,y,z)) có tất cả 5 hiện hữu tự do.
37*. F = x ( (p(x) y q(x, y)) z t q(z, t) ) có dạng chuẩn Skolem :
a. {p(x) q(x, y) q(f(x), g(x, y))}.
@c. Câu a, b đều sai.
b. {p(x) q(x, y) q(f(x, y), g(x, y))}.
d. Câu a, b đều đúng.
38*. Chọn phát biểu sai :
a. Các dòng của bảng thực trị đại diện cho tất cả diễn dịch của 1 công thức LLMĐ.
@b. (p(x, r(y)) yq(y)) yr(f(y)) là công thức và tự do của LLVT.
c. Qui tắc (e) có dạng : dòng n FG, dòng n+k F, dòng n+k+1 G.
d. Mệnh đề rỗng của LLVT là công thức hằng sai.
39*. Tập khả đồng nhất thế :
a. {p(a, x) r(x), p(a, h(x)) r(b), p(z, t) r(y)}.
b. Câu a và c đúng.
@c. {p(a, x) r(x), p(a, h(y)) r(w), p(z, t) r(w)}. d. Câu a và c sai.
40*. Chọn phát biểu sai :
@a. p(x) r(f(a)) là một nguyên từ. b. Công thức nguyên cũng là công thức.
c. Luận lý mệnh đề là logic ở cấp độ câu. Vị từ là logic ở cấp độ đối tượng.
d. Chứng minh là 1chuỗi công thức được tạo từ tiền đề hoặc qui tắc suy luận.
Tổng cộng : 40 câu.
5
Mã số đề 1001
LUẬN LÝ TOÁN HỌC
Thí sinh được sử dụng tài liệu và giữ lại đề thi.
Thời gian làm bài : 90 phút.
Qui ước : a, b, c, … là hằng, x, y, z ... là biến.
1*. M1 = r(y) q(a), M2 = p(x) r(y), M3 = q(a) p(x), M4= q(a) r(y),
M5= r(y), bằng phân giải chứng minh {M1, M2, M3, M4, M5} hằng sai :
a. pg(M2, M3) = F, pg(M2, M1) = G, pg(F, G) = .
b. pg(M3, M2) = F, pg(M4, F) = G, pg(M1, G) = .
c. pg(M2, M1) = F, pg(M4, F) = G, pg(M5, G) = . @d. Câu a, b, c đều sai.
2*. Công thức x (p(x) y (q(f(x)) r(y)) ) với D = {1, 2} có mô hình là :
@a. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q( 2), r(1), r(2)}. b. Câu a, b đều sai.
c. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q(2), r (1), r(2)}. d. Câu a, b đều đúng.
3*. Chọn phát biểu sai :
a. Công thức (F (G F)) là định lý, với F, G là công thức.
b. Nguyên tắc phân giải dựa trên qui tắc truyền.
@c. Đoạn chứng minh sau : dòng 3 : if x0 p(x0), dòng 4 : p(x0) q(x0), dòng 5 : nif
q(x0), dòng 6 q(x0), không có lỗi.
d. ((x) p(x,y) q(t,y)) (y)(r(x,y,z)) có tất cả 5 hiện hữu tự do.
4*. F = x ( (p(x) y q(x, y)) z t q(z, t) ) có dạng chuẩn Skolem :
a. {p(x) q(x, y) q(f(x), g(x, y))}.
@c. Câu a, b đều sai.
b. {p(x) q(x, y) q(f(x, y), g(x, y))}.
d. Câu a, b đều đúng.
5*. Chọn phát biểu sai :
a. Các dòng của bảng thực trị đại diện cho tất cả diễn dịch của 1 công thức LLMĐ.
@b. (p(x, r(y)) yq(y)) yr(f(y)) là công thức và tự do của LLVT.
c. Qui tắc (e) có dạng : dòng n FG, dòng n+k F, dòng n+k+1 G.
d. Mệnh đề rỗng của LLVT là công thức hằng sai.
6*. Tập khả đồng nhất thế :
a. {p(a, x) r(x), p(a, h(x)) r(b), p(z, t) r(y)}.
b. Câu a và c đúng.
@c. {p(a, x) r(x), p(a, h(y)) r(w), p(z, t) r(w)}. d. Câu a và c sai.
7*. Chọn phát biểu sai :
@a. p(x) r(f(a)) là một nguyên từ. b. Công thức nguyên cũng là công thức.
c. Luận lý mệnh đề là logic ở cấp độ câu. Vị từ là logic ở cấp độ đối tượng.
d. Chứng minh là 1chuỗi công thức được tạo từ tiền đề hoặc qui tắc suy luận.
8*. A = p(f(x)) r(a), B = p(f(a)) r(x), C = p(f(x)) r(z), D = p(x) r(z),
pgb(A, B) = K, pgb (C, D) = H. (Ghi chú : không phân giải nhị phân được = kpgđ)
a. K = , H = r(z)
@c. K = hằng đúng, H = kpgđ
b. K = , H =kpgđ
d. K = hằng đúng, H = r(z)
6
Mã số đề 1001
9*. Chọn phát biểu sai :
@a. Qui tắc (e) : dòng m : F F, dòng k : .
b. H là hệ quả luận lý của F thì tập các mô hình của H chứa tập mô hình của F.
c. {A, B, C, F} là 1 dòng của bảng thực trị của F = (A B) C.
d. Dạng chuẩn Skolem bảo toàn tính hằng sai.
10*. Chọn phát biểu sai :
a. Dạng chuẩn Prenex vẫn tương đương với công thức ban đầu.
b. Đoạn chứng minh sau : dòng 1 : if x0, dòng n : nif q(x0), dòng n+1 : x q(x) sử
dụng qui tắc i.
c. (P Q R) ở dạng chuẩn hội.
@d. Có câu sai trong 3 câu a, b, c.
11*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Dòng A=0, B=1, F= 1 của bảng thực trị được biểu diễn ở dạng {A, B, F}.
b. Công thức A hằng đúng nên A khả sai.
@c. Unifier là mgu của {E1, ..., Ek} nếu ( unifier )( thay thế ) ( = ).
d. Thừa số của 1 công thức là kết quả của công thức qua tác động của 1 mgu.
12*. Chọn phát biểu sai :
@a. Hệ thống là một công thức gồm hội các thành phần của hệ thống.
b. Có thể dùng thuật toán hằng sai để kiểm tra tính hằng đúng của 1công thức.
c. ╞═ x (H H[a/x]), H là công thức, a là hằng. d. Có câu sai trong 3 câu a, b, c.
13*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Dạng chuẩn Skolem S của F còn tương đương với F theo nghĩa hằng sai.
b. mgu của {p(x, f(x, g(x)), y), p(a, z, g(w))} là = a/x, f(a, g(a))/z, , g(w)/y
c. Hai côngthức tươngđương nếu có cùng tập các mô hình. @d.Câu a, b, c đều đúng.
14*. = <R, F, C> với R = {p(_)}, F = {s(_), m(_,_)}, C = {}.
Diễn dịch I : D = {word | word là từ trên tập ký tự {0, 1}}, I() = 10.
I(s) là hàm endcut bỏ ký tự cuối của từ, thí dụ endcut(111001) = 11100.
I(m) là hàm mix kết nối xen kẻ 2 từ, thí dụ mix(000, 11111) = 01010111.
I(p) là vị từ cir, cir(x) đúng nếu x là tuần hoàn có chiều dài chẵn, thí dụ 10, 01, 1010,
0101, ... Nếu x = 0011 thì I(m(s() + s(x))) = ?, I(p(m(s() + s(x))) = ?.
a. 0101, đúng. @b. 1001, sai. c. 1010, đúng.
d. 0011, sai.
15*. Chọn phát biểu đúng và bao quát nếu có thể :
a. (F ├─ H) là công thức hằng đúng với F, H là công thức LLMĐ.
b. Luận lý vị từ chấp nhận dạng hội, giao vô hạn các công thức.
c. Phạm vi của (x) là p(x) trong công thức (y)(r(y)) (x)(p(x) q(z)).
@d. Có câu sai trong 3 câu a, b, c.
16*. F= ((P (Q R)) (Q R)) P,và G = ((P Q) R) (R (Q P))
a. F, G hđ. b. F, G kđks. @c. F hđ, G kđks. d. F, G hs.
7
Mã số đề 1001
17*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Qui tắc (i) còn gọi là Modus ponens. b. Công thức hằng sai có ít nhất 1mô hình.
@c. Công thức F (G F) là khả đúng khả sai, với F, G là công thức.
d. Một dạng chuẩn Skolem của F : SF = {p(a, b, f(y)) q(y), h(y, z)}.
18*. R = {ptrên(_,_), ptròn(_), pvuông(_), pthoi(_)}, F = {fnón(_)}.C = {cMinh}.
Cho 1 diễn dịch I : D = {▲, , , },
cMinh =▲.
ptrên = {(, ▲), (, )}, ptròn = {}, pvuông = {}, pthoi = {, }.
fnón = {(▲, ), (, ), (, ), (▲, )}
E = x (pvuông(x) ptròn(x)), F = x y (ptrên(x, y) ptrên(y, x)).
Đánh giá E, F trong diễn dịch I.
a. E , F đúng. b. E đúng, F sai. @c. E sai, F đúng. d. E, F sai.
19*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Từ dòng m : F, viết ra dòng m+k : F (G H) là áp dụng qui tắc i.
b. ├─ F F còn gọi là qui tắc suy luận triệt tam (LEM).
c. f(a) trong p(x) r(f(a)) là một nguyên từ.
@d. Câu a, b, c đều đúng.
20*. F = x p(x, a) z y (q(x, y) r(z)), t nào tự do đối với x trong F :
a. t = f(z, y). @b. t = g(w). c. t = z.
d. Các câu a, b, c đều sai.
21*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Công thức khả sai nếu có ít nhất một mô hình.
@b. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
c. Mệnh đề rỗng là công thức vừa hằng sai vừa hằng đúng.
d. Định lý completeness. Nếu F├─ H thì F╞═ H.
22*. Chọn phát biểu đúng và bao quát nếu có thể :
a. pg(F, G) ╞═ F G.
@b. Luận lý mệnh đề không chấp nhận dạng hội, giao vô hạn các công thức.
c. Công thức đóng là công thức có ít nhất 1 biến có tất cả hiện hữu ràng buộc.
d. Biểu thức vị từ là giá trị đúng sai của vị từ trong thế giới thật.
23*. Nếu nhiệt độ và áp suất không đổi thì trời không mưa. Nhiệt độ vẫn không đổi. Vì vậy
nếu trời mưa thì áp suất thay đổi.
A = nhiệt độ không đổi, B = áp suất không đổi, C = trời mưa.
Vị từ ch(x) : x không thay đổi và p() : trời mưa, hằng a, b.
a. (AB) C, A ╞═ C B
c. Câu a, b đều sai.
b. (ch(a)ch(b)) p(), ch(a) ╞═ p() ch(b)
@d. Câu a, b đều đúng.
24*. Chọn phát biểu đúng và bao quát nếu có thể :
a. F ╞═ H nếu tập mô hình của H là tập con của tập mô hình của F.
@b. y x K ╞/═ x y K.
c. Hằng không là nguyên từ.
d. Công thức G = (xy (p(x) q(y))) ở dạng chuẩn Prenex.
8
Mã số đề 1001
25*. Chọn phát biểu đúng và bao quát nếu có thể :
a. F và dạng chuẩn Skolem của F tương đương nhau.
b. Mệnh đề trong LLVT là giao các lưỡng nguyên.
c. pg(p(x) q(f(y)), q(a) r(x)) = p(x) r(x). @d. Có câu sai trong 3 câu a, b, c.
26*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Công thức hoàn hảo chỉ là công thức nguyên.
@b. Qui tắc e, dòng 1 : F G, dòng 2 : if F, dòng 2+m : nif H, dòng 3+m : if G,
dòng 3+m+n : nif H, dòng 4+m+n : H.
c. G = p(x) p(f(y)) là một thừa số của T = p(x) r(y) p(f(y)) r(y).
d. Mô hình của 1 công thức là diễn dịch mà công thức được đánh giá trong đó.
27*. Chọn phát biểu sai :
a. Công thức của LLMĐ biểu diễn được 1 câu khai báo.
b. Vị từ là quan hệ trên tập Dn của miền đối tượng D, với n 0.
@c. Chứng minh eq(t1, t2)├─ eq(t2, t1). Đặt F = eq(x, t1). Dòng 1: eq(t1, t2), dòng 2:
eq(t1, t1), dòng 3: eq(t2, t1). Dòng 3 sử dụng qui tắc (=i) 1, 2.
d. Có câu sai trong 3 câu a, b, c.
28*. Chọn phát biểu đúng và bao quát nếu có thể :
a. (F G) F là công thức hằng sai. b. Biểu thức vị từ là nguyên từ.
@c. DC Prenex của x ( z r(x,z) x p(x) ) là x z t (r(x,z) p(t))
d. Các câu a, b, c đều sai.
29*. Diễn dịch D = {1, 2}, I = { p(1), p(2), q(1), q(2)} là mô hình của công thức :
@a. x t (p(x) q(t)) x p(x).
c. x t (p(x) q(t)) x p(x).
b. t x (p(x) q(t)) x p(x).
d. Câu a, b, c đều đúng.
30*. Chọn phát biểu sai :
a. Hệ thống mâu thuẫn là hằng sai. @b. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
c. Biểu thức hàm là nguyên từ. d. Công thức hằng đúng nếu mọi diễn dịch là mô hình.
31*. Chọn phát biểu sai :
a. “Nếu hàm f khả vi thì f liên tục”, và “f không liên tục”, vậy “f không khả vi”. Lập
luận sử dụng qui tắc modus tolens.
@b. Lưỡng nguyên là công thức nguyên hoặc công thức.
c. Thuật toán hằng sai cho kết quả no với F và yes với F. Vậy Fhằng đúng.
d. = {f(t)/x, z/t} và = {a/x, b/t, t/z}. = {f(b)/x, t/z}.
32*. Câu nào ở dạng chuẩn Skolem :
a. {p(x) q(y), p(f(x)) r(z)}
c. {p(x) q(b) x y}
b. {p(a) xq(x)}
@d. Các câu a, b, c đều sai.
9
Mã số đề 1001
33*. mgu của {p(x, h(y)), p(x, z), p(f(y), w) là :
a. = f(y)/x, z/w, h(y)/z .
c. = f(y)/x, w/z, h(y)/z.
@b. = f(y)/x, h(y)/w, h(y)/z.
d. Câu a, b, c đều đúng.
34*. Chứng minh F x q(x) ├─ x (F q(x)) với x không tự do trong F.
1. F x q(x) tđề
2. if F
4. if xo
5. q(xo)
7. If x (F q(x)) i 4,6
8. x (F q(x)) e 3,4-7
e 3
3. x q(x) e 1,2 6. nif F q(xo) i 2,5
@a. áp dụng sai qui tắc i, if
c. áp dụng sai qui tắc if, e
b. áp dụng sai qui tắc i, e
d. Chứng minh đúng.
35*. Chọn phát biểu sai :
@a. P Q R không ở dạng chuẩn giao.
b. Công thức nguyên là vị từ có thông số được thay bằng các nguyên từ.
c. Định nghĩa của khái niệm phân giải là định nghĩa đệ qui.
d. Có thể dùng thuật toán hằng đúng để kiểm tra tính khả sai của 1công thức.
36*. Chứng minh
F (q1q2) ├─ (Fq1) (Fq2) (trong LLMĐ)
1. F (q1q2) tiền đề
2. If F
4. q1 e 3
5. q2 e 3
6. Fq1 i 2,4
7. Fq2
8. nif (Fq1)(Fq2) i 6,7
9. (Fq1) (Fq2) e 2,6,7,8
i 2,5
3. q1q2
e 1,2
@a. sai từ dòng 6 b. sai từ dòng 7 c. sai từ dòng 8 d. Chứng minh đúng.
37*. Chọn phát biểu đúng và bao quát nếu có thể :
@a. Định lý (soundness). Nếu F├─H thì F╞═H. b. Hợpnối 2 thaythế có tính
phốihợp.
c. Dạng chuẩn Skolem S của F còn tương đương với F. d. Câu a, b, c đều đúng.
38*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Thuật toán hằng sai cùng cho kết quả yes với F và F. Vậy F hằng sai.
b. DC Prenex của x(y(p(x) r(y)) z q(z)) là xyz ((p(x) r(y)) q(z))
c. Hệ thống mâu thuẫn là khả sai, khả đúng.
@d. Có câu sai trong 3 câu a, b, c.
39*. Chọn phát biểu đúng và bao quát nếu có thể :
a. {p(f(x)) r(z)} ở dc Skolem.
b. x y(p(x)q(b,y)) ở dc Prenex.
c. ╞/═ (xH) H[a/x], với H là công thức, a là hằng. @d. Các câu a, b, c đều đúng.
40*. Chọn phát biểu sai :
@a. Qui tắc (i) : dòng 1: if F, dòng 1+k : nif FG, dòng 2+k : FG.
b. Một công thức hằng sai nếu phân giải ra được mệnh đề hằng sai.
c. xy (p(x) q(y)) = yx (p(x) q(y)).
d. Hàm là ánh xạ từ Dn vào D của miền đối tượng D, với n 0.
Tổng cộng : 40 câu.
10
Mã số đề 0110
LUẬN LÝ TOÁN HỌC
Thí sinh được sử dụng tài liệu và giữ lại đề thi.
Thời gian làm bài : 90 phút.
Qui ước : a, b, c, … là hằng, x, y, z ... là biến.
1*. Chọn phát biểu đúng và bao quát nếu có thể :
@a. Định lý (soundness). Nếu F├─H thì F╞═H. b. Hợpnối 2 thaythế có tính
phốihợp.
c. Dạng chuẩn Skolem S của F còn tương đương với F. d. Câu a, b, c đều đúng.
2*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Thuật toán hằng sai cùng cho kết quả yes với F và F. Vậy F hằng sai.
b. DC Prenex của x(y(p(x) r(y)) z q(z)) là xyz ((p(x) r(y)) q(z))
c. Hệ thống mâu thuẫn là khả sai, khả đúng.
@d. Có câu sai trong 3 câu a, b, c.
3*. Chọn phát biểu đúng và bao quát nếu có thể :
a. {p(f(x)) r(z)} ở dc Skolem.
b. x y(p(x)q(b,y)) ở dc Prenex.
c. ╞/═ (xH) H[a/x], với H là công thức, a là hằng. @d. Các câu a, b, c đều đúng.
4*. Chọn phát biểu sai :
@a. Qui tắc (i) : dòng 1: if F, dòng 1+k : nif FG, dòng 2+k : FG.
b. Một công thức hằng sai nếu phân giải ra được mệnh đề hằng sai.
c. xy (p(x) q(y)) = yx (p(x) q(y)).
d. Hàm là ánh xạ từ Dn vào D của miền đối tượng D, với n 0.
5*. Câu nào ở dạng chuẩn Skolem :
a. {p(x) q(y), p(f(x)) r(z)}
c. {p(x) q(b) x y}
b. {p(a) xq(x)}
@d. Các câu a, b, c đều sai.
6*. Chọn phát biểu sai :
a. Dạng chuẩn Prenex vẫn tương đương với công thức ban đầu.
b. Đoạn chứng minh sau : dòng 1 : if x0, dòng n : nif q(x0), dòng n+1 : x q(x) sử
dụng qui tắc i.
c. (P Q R) ở dạng chuẩn hội.
@d. Có câu sai trong 3 câu a, b, c.
7*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Dòng A=0, B=1, F= 1 của bảng thực trị được biểu diễn ở dạng {A, B, F}.
b. Công thức A hằng đúng nên A khả sai.
@c. Unifier là mgu của {E1, ..., Ek} nếu ( unifier )( thay thế ) ( = ).
d. Thừa số của 1 công thức là kết quả của công thức qua tác động của 1 mgu.
8*. A = p(f(x)) r(a), B = p(f(a)) r(x), C = p(f(x)) r(z), D = p(x) r(z),
pgb(A, B) = K, pgb (C, D) = H. (Ghi chú : không phân giải nhị phân được = kpgđ)
a. K = , H = r(z)
@c. K = hằng đúng, H = kpgđ
b. K = , H =kpgđ
d. K = hằng đúng, H = r(z)
11
Mã số đề 0110
9*. Chọn phát biểu sai :
@a. Hệ thống là một công thức gồm hội các thành phần của hệ thống.
b. Có thể dùng thuật toán hằng sai để kiểm tra tính hằng đúng của 1công thức.
c. ╞═ x (H H[a/x]), H là công thức, a là hằng. d. Có câu sai trong 3 câu a, b, c.
10*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Dạng chuẩn Skolem S của F còn tương đương với F theo nghĩa hằng sai.
b. mgu của {p(x, f(x, g(x)), y), p(a, z, g(w))} là = a/x, f(a, g(a))/z, , g(w)/y
c. Hai côngthức tươngđương nếu có cùng tập các mô hình. @d.Câu a, b, c đều đúng.
11*. = <R, F, C> với R = {p(_)}, F = {s(_), m(_,_)}, C = {}.
Diễn dịch I : D = {word | word là từ trên tập ký tự {0, 1}}, I() = 10.
I(s) là hàm endcut bỏ ký tự cuối của từ, thí dụ endcut(111001) = 11100.
I(m) là hàm mix kết nối xen kẻ 2 từ, thí dụ mix(000, 11111) = 01010111.
I(p) là vị từ cir, cir(x) đúng nếu x là tuần hoàn có chiều dài chẵn, thí dụ 10, 01, 1010,
0101, ... Nếu x = 0011 thì I(m(s() + s(x))) = ?, I(p(m(s() + s(x))) = ?.
a. 0101, đúng. @b. 1001, sai. c. 1010, đúng.
d. 0011, sai.
12*. Chọn phát biểu đúng và bao quát nếu có thể :
a. (F ├─ H) là công thức hằng đúng với F, H là công thức LLMĐ.
b. Luận lý vị từ chấp nhận dạng hội, giao vô hạn các công thức.
c. Phạm vi của (x) là p(x) trong công thức (y)(r(y)) (x)(p(x) q(z)).
@d. Có câu sai trong 3 câu a, b, c.
13*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Qui tắc (i) còn gọi là Modus ponens. b. Công thức hằng sai có ít nhất 1mô hình.
@c. Công thức F (G F) là khả đúng khả sai, với F, G là công thức.
d. Một dạng chuẩn Skolem của F : SF = {p(a, b, f(y)) q(y), h(y, z)}.
14*. R = {ptrên(_,_), ptròn(_), pvuông(_), pthoi(_)}, F = {fnón(_)}.C = {cMinh}.
Cho 1 diễn dịch I : D = {▲, , , },
cMinh =▲.
ptrên = {(, ▲), (, )}, ptròn = {}, pvuông = {}, pthoi = {, }.
fnón = {(▲, ), (, ), (, ), (▲, )}
E = x (pvuông(x) ptròn(x)), F = x y (ptrên(x, y) ptrên(y, x)).
Đánh giá E, F trong diễn dịch I.
a. E , F đúng. b. E đúng, F sai. @c. E sai, F đúng. d. E, F sai.
15*. F= ((P (Q R)) (Q R)) P,và G = ((P Q) R) (R (Q P))
a. F, G hđ. b. F, G kđks. @c. F hđ, G kđks. d. F, G hs.
16*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Từ dòng m : F, viết ra dòng m+k : F (G H) là áp dụng qui tắc i.
b. ├─ F F còn gọi là qui tắc suy luận triệt tam (LEM).
c. f(a) trong p(x) r(f(a)) là một nguyên từ.
@d. Câu a, b, c đều đúng.
12
Mã số đề 0110
17*. F = x p(x, a) z y (q(x, y) r(z)), t nào tự do đối với x trong F :
a. t = f(z, y). @b. t = g(w). c. t = z.
d. Các câu a, b, c đều sai.
18*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Công thức khả sai nếu có ít nhất một mô hình.
@b. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
c. Mệnh đề rỗng là công thức vừa hằng sai vừa hằng đúng.
d. Định lý completeness. Nếu F├─ H thì F╞═ H.
19*. Chọn phát biểu đúng và bao quát nếu có thể :
a. pg(F, G) ╞═ F G.
@b. Luận lý mệnh đề không chấp nhận dạng hội, giao vô hạn các công thức.
c. Công thức đóng là công thức có ít nhất 1 biến có tất cả hiện hữu ràng buộc.
d. Biểu thức vị từ là giá trị đúng sai của vị từ trong thế giới thật.
20*. Nếu nhiệt độ và áp suất không đổi thì trời không mưa. Nhiệt độ vẫn không đổi. Vì vậy
nếu trời mưa thì áp suất thay đổi.
A = nhiệt độ không đổi, B = áp suất không đổi, C = trời mưa.
Vị từ ch(x) : x không thay đổi và p() : trời mưa, hằng a, b.
a. (AB) C, A ╞═ C B
c. Câu a, b đều sai.
b. (ch(a)ch(b)) p(), ch(a) ╞═ p() ch(b)
@d. Câu a, b đều đúng.
21*. Chọn phát biểu đúng và bao quát nếu có thể :
a. F ╞═ H nếu tập mô hình của H là tập con của tập mô hình của F.
@b. y x K ╞/═ x y K.
c. Hằng không là nguyên từ.
d. Công thức G = (xy (p(x) q(y))) ở dạng chuẩn Prenex.
22*. Chọn phát biểu đúng và bao quát nếu có thể :
a. F và dạng chuẩn Skolem của F tương đương nhau.
b. Mệnh đề trong LLVT là giao các lưỡng nguyên.
c. pg(p(x) q(f(y)), q(a) r(x)) = p(x) r(x). @d. Có câu sai trong 3 câu a, b, c.
23*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Công thức hoàn hảo chỉ là công thức nguyên.
@b. Qui tắc e, dòng 1 : F G, dòng 2 : if F, dòng 2+m : nif H, dòng 3+m : if G,
dòng 3+m+n : nif H, dòng 4+m+n : H.
c. G = p(x) p(f(y)) là một thừa số của T = p(x) r(y) p(f(y)) r(y).
d. Mô hình của 1 công thức là diễn dịch mà công thức được đánh giá trong đó.
24*. Chọn phát biểu sai :
a. Công thức của LLMĐ biểu diễn được 1 câu khai báo.
b. Vị từ là quan hệ trên tập Dn của miền đối tượng D, với n 0.
@c. Chứng minh eq(t1, t2)├─ eq(t2, t1). Đặt F = eq(x, t1). Dòng 1: eq(t1, t2), dòng 2:
eq(t1, t1), dòng 3: eq(t2, t1). Dòng 3 sử dụng qui tắc (=i) 1, 2.
d. Có câu sai trong 3 câu a, b, c.
Mã số đề 0110
25*. Chọn phát biểu đúng và bao quát nếu có thể :
13
a. (F G) F là công thức hằng sai. b. Biểu thức vị từ là nguyên từ.
@c. DC Prenex của x ( z r(x,z) x p(x) ) là x z t (r(x,z) p(t))
d. Các câu a, b, c đều sai.
26*. Diễn dịch D = {1, 2}, I = { p(1), p(2), q(1), q(2)} là mô hình của công thức :
@a. x t (p(x) q(t)) x p(x).
c. x t (p(x) q(t)) x p(x).
b. t x (p(x) q(t)) x p(x).
d. Câu a, b, c đều đúng.
27*. Chọn phát biểu sai :
a. Hệ thống mâu thuẫn là hằng sai. @b. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
c. Biểu thức hàm là nguyên từ. d. Công thức hằng đúng nếu mọi diễn dịch là mô hình.
28*. mgu của {p(x, h(y)), p(x, z), p(f(y), w) là :
a. = f(y)/x, z/w, h(y)/z .
c. = f(y)/x, w/z, h(y)/z.
@b. = f(y)/x, h(y)/w, h(y)/z.
d. Câu a, b, c đều đúng.
29*. Chọn phát biểu sai :
a. “Nếu hàm f khả vi thì f liên tục”, và “f không liên tục”, vậy “f không khả vi”. Lập
luận sử dụng qui tắc modus tolens.
@b. Lưỡng nguyên là công thức nguyên hoặc công thức.
c. Thuật toán hằng sai cho kết quả no với F và yes với F. Vậy Fhằng đúng.
d. = {f(t)/x, z/t} và = {a/x, b/t, t/z}. = {f(b)/x, t/z}.
30*. Chứng minh F x q(x) ├─ x (F q(x)) với x không tự do trong F.
1. F x q(x) tđề
2. if F
4. if xo
5. q(xo)
7. If x (F q(x)) i 4,6
e 3
8. x (F q(x))
e 3,4-7
3. x q(x) e 1,2 6. nif F q(xo) i 2,5
@a. áp dụng sai qui tắc i, if
c. áp dụng sai qui tắc if, e
b. áp dụng sai qui tắc i, e
d. Chứng minh đúng.
31*. Chọn phát biểu sai :
@a. P Q R không ở dạng chuẩn giao.
b. Công thức nguyên là vị từ có thông số được thay bằng các nguyên từ.
c. Định nghĩa của khái niệm phân giải là định nghĩa đệ qui.
d. Có thể dùng thuật toán hằng đúng để kiểm tra tính khả sai của 1công thức.
32*. Chứng minh
F (q1q2) ├─ (Fq1) (Fq2) (trong LLMĐ)
1. F (q1q2) tiền đề
2. If F
4. q1 e 3
5. q2 e 3
6. Fq1 i 2,4
7. Fq2
8. nif (Fq1)(Fq2) i 6,7
9. (Fq1) (Fq2)
i 2,5
3. q1q2
e 1,2
Mã số đề 0110
@a. sai từ dòng 6 b. sai từ dòng 7 c. sai từ dòng 8 d. Chứng minh đúng.
33*. M1 = r(y) q(a), M2 = p(x) r(y), M3 = q(a) p(x), M4= q(a) r(y),
M5= r(y), bằng phân giải chứng minh {M1, M2, M3, M4, M5} hằng sai :
14
a. pg(M2, M3) = F, pg(M2, M1) = G, pg(F, G) = .
b. pg(M3, M2) = F, pg(M4, F) = G, pg(M1, G) = .
c. pg(M2, M1) = F, pg(M4, F) = G, pg(M5, G) = . @d. Câu a, b, c đều sai.
34*. Công thức x (p(x) y (q(f(x)) r(y)) ) với D = {1, 2} có mô hình là :
@a. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q( 2), r(1), r(2)}. b. Câu a, b đều sai.
c. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q(2), r (1), r(2)}. d. Câu a, b đều đúng.
35*. Chọn phát biểu sai :
a. Công thức (F (G F)) là định lý, với F, G là công thức.
b. Nguyên tắc phân giải dựa trên qui tắc truyền.
@c. Đoạn chứng minh sau : dòng 3 : if x0 p(x0), dòng 4 : p(x0) q(x0), dòng 5 : nif
q(x0), dòng 6 q(x0), không có lỗi.
d. ((x) p(x,y) q(t,y)) (y)(r(x,y,z)) có tất cả 5 hiện hữu tự do.
36*. F = x ( (p(x) y q(x, y)) z t q(z, t) ) có dạng chuẩn Skolem :
a. {p(x) q(x, y) q(f(x), g(x, y))}.
@c. Câu a, b đều sai.
b. {p(x) q(x, y) q(f(x, y), g(x, y))}.
d. Câu a, b đều đúng.
37*. Chọn phát biểu sai :
a. Các dòng của bảng thực trị đại diện cho tất cả diễn dịch của 1 công thức LLMĐ.
@b. (p(x, r(y)) yq(y)) yr(f(y)) là công thức và tự do của LLVT.
c. Qui tắc (e) có dạng : dòng n FG, dòng n+k F, dòng n+k+1 G.
d. Mệnh đề rỗng của LLVT là công thức hằng sai.
38*. Tập khả đồng nhất thế :
a. {p(a, x) r(x), p(a, h(x)) r(b), p(z, t) r(y)}.
b. Câu a và c đúng.
@c. {p(a, x) r(x), p(a, h(y)) r(w), p(z, t) r(w)}. d. Câu a và c sai.
39*. Chọn phát biểu sai :
@a. p(x) r(f(a)) là một nguyên từ. b. Công thức nguyên cũng là công thức.
c. Luận lý mệnh đề là logic ở cấp độ câu. Vị từ là logic ở cấp độ đối tượng.
d. Chứng minh là 1chuỗi công thức được tạo từ tiền đề hoặc qui tắc suy luận.
40*. Chọn phát biểu sai :
@a. Qui tắc (e) : dòng m : F F, dòng k : .
b. H là hệ quả luận lý của F thì tập các mô hình của H chứa tập mô hình của F.
c. {A, B, C, F} là 1 dòng của bảng thực trị của F = (A B) C.
d. Dạng chuẩn Skolem bảo toàn tính hằng sai.
Tổng cộng : 40 câu.
15
Mã số đề 1010
LUẬN LÝ TOÁN HỌC
Thí sinh được sử dụng tài liệu và giữ lại đề thi.
Thời gian làm bài : 90 phút.
Qui ước : a, b, c, … là hằng, x, y, z ... là biến.
1*. Chọn phát biểu sai :
@a. Hệ thống là một công thức gồm hội các thành phần của hệ thống.
b. Có thể dùng thuật toán hằng sai để kiểm tra tính hằng đúng của 1công thức.
c. ╞═ x (H H[a/x]), H là công thức, a là hằng. d. Có câu sai trong 3 câu a, b, c.
2*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Dạng chuẩn Skolem S của F còn tương đương với F theo nghĩa hằng sai.
b. mgu của {p(x, f(x, g(x)), y), p(a, z, g(w))} là = a/x, f(a, g(a))/z, , g(w)/y
c. Hai côngthức tươngđương nếu có cùng tập các mô hình. @d.Câu a, b, c đều đúng.
3*. = <R, F, C> với R = {p(_)}, F = {s(_), m(_,_)}, C = {}.
Diễn dịch I : D = {word | word là từ trên tập ký tự {0, 1}}, I() = 10.
I(s) là hàm endcut bỏ ký tự cuối của từ, thí dụ endcut(111001) = 11100.
I(m) là hàm mix kết nối xen kẻ 2 từ, thí dụ mix(000, 11111) = 01010111.
I(p) là vị từ cir, cir(x) đúng nếu x là tuần hoàn có chiều dài chẵn, thí dụ 10, 01, 1010,
0101, ... Nếu x = 0011 thì I(m(s() + s(x))) = ?, I(p(m(s() + s(x))) = ?.
a. 0101, đúng. @b. 1001, sai. c. 1010, đúng.
d. 0011, sai.
4*. Chọn phát biểu đúng và bao quát nếu có thể :
a. (F ├─ H) là công thức hằng đúng với F, H là công thức LLMĐ.
b. Luận lý vị từ chấp nhận dạng hội, giao vô hạn các công thức.
c. Phạm vi của (x) là p(x) trong công thức (y)(r(y)) (x)(p(x) q(z)).
@d. Có câu sai trong 3 câu a, b, c.
5*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Qui tắc (i) còn gọi là Modus ponens. b. Công thức hằng sai có ít nhất 1mô hình.
@c. Công thức F (G F) là khả đúng khả sai, với F, G là công thức.
d. Một dạng chuẩn Skolem của F : SF = {p(a, b, f(y)) q(y), h(y, z)}.
6*. R = {ptrên(_,_), ptròn(_), pvuông(_), pthoi(_)}, F = {fnón(_)}.C = {cMinh}.
Cho 1 diễn dịch I : D = {▲, , , },
cMinh =▲.
ptrên = {(, ▲), (, )}, ptròn = {}, pvuông = {}, pthoi = {, }.
fnón = {(▲, ), (, ), (, ), (▲, )}
E = x (pvuông(x) ptròn(x)), F = x y (ptrên(x, y) ptrên(y, x)).
Đánh giá E, F trong diễn dịch I.
a. E , F đúng. b. E đúng, F sai. @c. E sai, F đúng. d. E, F sai.
Mã số đề 1010
7*. F= ((P (Q R)) (Q R)) P,và G = ((P Q) R) (R (Q P))
a. F, G hđ. b. F, G kđks. @c. F hđ, G kđks. d. F, G hs.
8*. Chọn phát biểu đúng và bao quát nếu có thể :
16
@a. Định lý (soundness). Nếu F├─H thì F╞═H. b. Hợpnối 2 thaythế có tính
phốihợp.
c. Dạng chuẩn Skolem S của F còn tương đương với F. d. Câu a, b, c đều đúng.
9*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Thuật toán hằng sai cùng cho kết quả yes với F và F. Vậy F hằng sai.
b. DC Prenex của x(y(p(x) r(y)) z q(z)) là xyz ((p(x) r(y)) q(z))
c. Hệ thống mâu thuẫn là khả sai, khả đúng.
@d. Có câu sai trong 3 câu a, b, c.
10*. Chọn phát biểu đúng và bao quát nếu có thể :
a. {p(f(x)) r(z)} ở dc Skolem.
b. x y(p(x)q(b,y)) ở dc Prenex.
c. ╞/═ (xH) H[a/x], với H là công thức, a là hằng. @d. Các câu a, b, c đều đúng.
11*. Chọn phát biểu sai :
@a. Qui tắc (i) : dòng 1: if F, dòng 1+k : nif FG, dòng 2+k : FG.
b. Một công thức hằng sai nếu phân giải ra được mệnh đề hằng sai.
c. xy (p(x) q(y)) = yx (p(x) q(y)).
d. Hàm là ánh xạ từ Dn vào D của miền đối tượng D, với n 0.
12*. Câu nào ở dạng chuẩn Skolem :
a. {p(x) q(y), p(f(x)) r(z)}
c. {p(x) q(b) x y}
b. {p(a) xq(x)}
@d. Các câu a, b, c đều sai.
13*. Chọn phát biểu sai :
a. Dạng chuẩn Prenex vẫn tương đương với công thức ban đầu.
b. Đoạn chứng minh sau : dòng 1 : if x0, dòng n : nif q(x0), dòng n+1 : x q(x) sử
dụng qui tắc i.
c. (P Q R) ở dạng chuẩn hội.
@d. Có câu sai trong 3 câu a, b, c.
14*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Dòng A=0, B=1, F= 1 của bảng thực trị được biểu diễn ở dạng {A, B, F}.
b. Công thức A hằng đúng nên A khả sai.
@c. Unifier là mgu của {E1, ..., Ek} nếu ( unifier )( thay thế ) ( = ).
d. Thừa số của 1 công thức là kết quả của công thức qua tác động của 1 mgu.
15*. A = p(f(x)) r(a), B = p(f(a)) r(x), C = p(f(x)) r(z), D = p(x) r(z),
pgb(A, B) = K, pgb (C, D) = H. (Ghi chú : không phân giải nhị phân được = kpgđ)
a. K = , H = r(z)
@c. K = hằng đúng, H = kpgđ
b. K = , H =kpgđ
d. K = hằng đúng, H = r(z)
Mã số đề 1010
16*. F = x p(x, a) z y (q(x, y) r(z)), t nào tự do đối với x trong F :
a. t = f(z, y). @b. t = g(w). c. t = z.
d. Các câu a, b, c đều sai.
17*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Công thức khả sai nếu có ít nhất một mô hình.
17
@b. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
c. Mệnh đề rỗng là công thức vừa hằng sai vừa hằng đúng.
d. Định lý completeness. Nếu F├─ H thì F╞═ H.
18*. Chọn phát biểu đúng và bao quát nếu có thể :
a. pg(F, G) ╞═ F G.
@b. Luận lý mệnh đề không chấp nhận dạng hội, giao vô hạn các công thức.
c. Công thức đóng là công thức có ít nhất 1 biến có tất cả hiện hữu ràng buộc.
d. Biểu thức vị từ là giá trị đúng sai của vị từ trong thế giới thật.
19*. Nếu nhiệt độ và áp suất không đổi thì trời không mưa. Nhiệt độ vẫn không đổi. Vì vậy
nếu trời mưa thì áp suất thay đổi.
A = nhiệt độ không đổi, B = áp suất không đổi, C = trời mưa.
Vị từ ch(x) : x không thay đổi và p() : trời mưa, hằng a, b.
a. (AB) C, A ╞═ C B
c. Câu a, b đều sai.
b. (ch(a)ch(b)) p(), ch(a) ╞═ p() ch(b)
@d. Câu a, b đều đúng.
20*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Từ dòng m : F, viết ra dòng m+k : F (G H) là áp dụng qui tắc i.
b. ├─ F F còn gọi là qui tắc suy luận triệt tam (LEM).
c. f(a) trong p(x) r(f(a)) là một nguyên từ.
@d. Câu a, b, c đều đúng.
21*. Chọn phát biểu đúng và bao quát nếu có thể :
a. F ╞═ H nếu tập mô hình của H là tập con của tập mô hình của F.
@b. y x K ╞/═ x y K. c. Hằng không là nguyên từ.
d. Công thức G = (xy (p(x) q(y))) ở dạng chuẩn Prenex.
22*. Chọn phát biểu đúng và bao quát nếu có thể :
a. F và dạng chuẩn Skolem của F tương đương nhau.
b. Mệnh đề trong LLVT là giao các lưỡng nguyên.
c. pg(p(x) q(f(y)), q(a) r(x)) = p(x) r(x). @d. Có câu sai trong 3 câu a, b, c.
23*. Chọn phát biểu đúng và bao quát nếu có thể :
a. Công thức hoàn hảo chỉ là công thức nguyên.
@b. Qui tắc e, dòng 1 : F G, dòng 2 : if F, dòng 2+m : nif H, dòng 3+m : if G,
dòng 3+m+n : nif H, dòng 4+m+n : H.
c. G = p(x) p(f(y)) là một thừa số của T = p(x) r(y) p(f(y)) r(y).
d. Mô hình của 1 công thức là diễn dịch mà công thức được đánh giá trong đó.
Diễn dịch D = {1, 2}, I = { p(1), p(2), q(1), q(2)} là mô hình của công thức :
Mã số đề 1010
@a. x t (p(x) q(t)) x p(x).
c. x t (p(x) q(t)) x p(x).
b. t x (p(x) q(t)) x p(x).
d. Câu a, b, c đều đúng.
25*. Chọn phát biểu đúng và bao quát nếu có thể :
a. (F G) F là công thức hằng sai. b. Biểu thức vị từ là nguyên từ.
18
@c. DC Prenex của x ( z r(x,z) x p(x) ) là x z t (r(x,z) p(t))
d. Các câu a, b, c đều sai.
26*. Chọn phát biểu sai :
a. Hệ thống mâu thuẫn là hằng sai. @b. ╞═ (x p(x) x q(x)) x (p(x) q(x)).
c. Biểu thức hàm là nguyên từ. d. Công thức hằng đúng nếu mọi diễn dịch là mô hình.
27*. mgu của {p(x, h(y)), p(x, z), p(f(y), w) là :
a. = f(y)/x, z/w, h(y)/z .
c. = f(y)/x, w/z, h(y)/z.
@b. = f(y)/x, h(y)/w, h(y)/z.
d. Câu a, b, c đều đúng.
28*. Chọn phát biểu sai :
a. Công thức của LLMĐ biểu diễn được 1 câu khai báo.
b. Vị từ là quan hệ trên tập Dn của miền đối tượng D, với n 0.
@c. Chứng minh eq(t1, t2)├─ eq(t2, t1). Đặt F = eq(x, t1). Dòng 1: eq(t1, t2), dòng 2:
eq(t1, t1), dòng 3: eq(t2, t1). Dòng 3 sử dụng qui tắc (=i) 1, 2.
d. Có câu sai trong 3 câu a, b, c.
29*. Chọn phát biểu sai :
a. “Nếu hàm f khả vi thì f liên tục”, và “f không liên tục”, vậy “f không khả vi”. Lập
luận sử dụng qui tắc modus tolens.
@b. Lưỡng nguyên là công thức nguyên hoặc công thức.
c. Thuật toán hằng sai cho kết quả no với F và yes với F. Vậy Fhằng đúng.
d. = {f(t)/x, z/t} và = {a/x, b/t, t/z}. = {f(b)/x, t/z}.
30*. Chứng minh F x q(x) ├─ x (F q(x)) với x không tự do trong F.
1. F x q(x) tđề
2. if F
4. if xo
5. q(xo)
7. If x (F q(x)) i 4,6
e 3
8. x (F q(x))
e 3,4-7
3. x q(x) e 1,2 6. nif F q(xo) i 2,5
@a. áp dụng sai qui tắc i, if
c. áp dụng sai qui tắc if, e
b. áp dụng sai qui tắc i, e
d. Chứng minh đúng.
31*. Chọn phát biểu sai :
a. Công thức (F (G F)) là định lý, với F, G là công thức.
b. Nguyên tắc phân giải dựa trên qui tắc truyền.
@c. Đoạn chứng minh sau : dòng 3 : if x0 p(x0), dòng 4 : p(x0) q(x0), dòng 5 : nif
q(x0), dòng 6 q(x0), không có lỗi.
d. ((x) p(x,y) q(t,y)) (y)(r(x,y,z)) có tất cả 5 hiện hữu tự do.
32*. F = x ( (p(x) y q(x, y)) z t q(z, t) ) có dạng chuẩn Skolem :
Mã số đề 1010
a. {p(x) q(x, y) q(f(x), g(x, y))}.
@c. Câu a, b đều sai.
b. {p(x) q(x, y) q(f(x, y), g(x, y))}.
d. Câu a, b đều đúng.
33*. Chọn phát biểu sai :
a. Các dòng của bảng thực trị đại diện cho tất cả diễn dịch của 1 công thức LLMĐ.
19
@b. (p(x, r(y)) yq(y)) yr(f(y)) là công thức và tự do của LLVT.
c. Qui tắc (e) có dạng : dòng n FG, dòng n+k F, dòng n+k+1 G.
d. Mệnh đề rỗng của LLVT là công thức hằng sai.
34*. Tập khả đồng nhất thế :
a. {p(a, x) r(x), p(a, h(x)) r(b), p(z, t) r(y)}.
b. Câu a và c đúng.
@c. {p(a, x) r(x), p(a, h(y)) r(w), p(z, t) r(w)}. d. Câu a và c sai.
35*. Chọn phát biểu sai :
@a. p(x) r(f(a)) là một nguyên từ. b. Công thức nguyên cũng là công thức.
c. Luận lý mệnh đề là logic ở cấp độ câu. Vị từ là logic ở cấp độ đối tượng.
d. Chứng minh là 1chuỗi công thức được tạo từ tiền đề hoặc qui tắc suy luận.
36*. Chọn phát biểu sai :
@a. Qui tắc (e) : dòng m : F F, dòng k : .
b. H là hệ quả luận lý của F thì tập các mô hình của H chứa tập mô hình của F.
c. {A, B, C, F} là 1 dòng của bảng thực trị của F = (A B) C.
d. Dạng chuẩn Skolem bảo toàn tính hằng sai.
37*. Chọn phát biểu sai :
@a. P Q R không ở dạng chuẩn giao.
b. Công thức nguyên là vị từ có thông số được thay bằng các nguyên từ.
c. Định nghĩa của khái niệm phân giải là định nghĩa đệ qui.
d. Có thể dùng thuật toán hằng đúng để kiểm tra tính khả sai của 1công thức.
38*. Chứng minh
1. F (q1q2) tiền đề
2. If F
F (q1q2) ├─ (Fq1) (Fq2) (trong LLMĐ)
4. q1 e 3
7. Fq2
8. nif (Fq1)(Fq2) i 6,7
9. (Fq1) (Fq2) e 2,6,7,8
i 2,5
5. q2 e 3
3. q1q2
e 1,2
6. Fq1 i 2,4
@a. sai từ dòng 6 b. sai từ dòng 7 c. sai từ dòng 8 d. Chứng minh đúng.
39*. M1 = r(y) q(a), M2 = p(x) r(y), M3 = q(a) p(x), M4= q(a) r(y),
M5= r(y), bằng phân giải chứng minh {M1, M2, M3, M4, M5} hằng sai :
a. pg(M2, M3) = F, pg(M2, M1) = G, pg(F, G) = .
b. pg(M3, M2) = F, pg(M4, F) = G, pg(M1, G) = .
c. pg(M2, M1) = F, pg(M4, F) = G, pg(M5, G) = . @d. Câu a, b, c đều sai.
40*. Công thức x (p(x) y (q(f(x)) r(y)) ) với D = {1, 2} có mô hình là :
@a. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q( 2), r(1), r(2)}. b. Câu a, b đều sai.
c. f(1) = 2, f(2) = 1, { p(1), p(2), q(1), q(2), r (1), r(2)}. d. Câu a, b đều đúng.
Tổng cộng : 40 câu.
20
20 trang
25940
Free
Bạn đang xem tài liệu "Đề thi cuối học kỳ môn Luận lý toán học năm 2008 - Mã đề 0101", để tải tài liệu gốc về máy hãy click vào nút Download ở trên
File đính kèm:
- de_thi_cuoi_hoc_ky_mon_luan_ly_toan_hoc_nam_2008_ma_de_0101.doc
- FIN_LOGIC_MT2k08_DA.DOC
