Môn: Trí tu nhân to Ging viên: Tô Hoài Vit
10/15/2008
Bài tp Logic
Câu 1
Cho tp cơ s tri thc:
KB = { A => B C, C => E F, B => ¬E ,A}
Biến đổi tp cơ s tri thc trên v dng hi chun và chng minh F được suy dn t tp
cơ s tri thc trên bng phương pháp Robinson (DP).
Câu 2
Thc hin tương t cho bài tp sau
KB = {A => B; A => C E; B C => D; E => F; F D => G; A}
Có th suy din các s kin sau t cơ s tri thc trên hay không:
a) E?
b) G?
Câu 3
Cho cơ s tri thc sau:
KB = {A B D, D E F, E A ¬B}
Biến đổi tp cơ s tri thc trên v dng hi chun và kim tra các câu sau có rút ra được
t tp cơ s trên hay không, dùng phương pháp Robinson (DP):
a) A ¬D?
b) A B ¬D?
Câu 4
Đặt C(x): “x có mt con mèo”, D(x): “x có mt con chó”, F(x): “x có mt con chn”.
Biu din các phát biu sau theo C(x), D(x), F(x), các lượng t và các phép ni logic. Xét
không gian biến là các sinh viên trong lp
a) Mt sinh viên trong lp có mt con mèo, mt con chó hay mt con chn.
b) Tt c sinh viên trong lp có mt con mèo, mt con chó hay mt con chn.
c) Mt sinh viên nào đó có mt con mèo và mt con chn nhưng không có chó.
d) Không có sinh viên nào trong lp có mt con mèo, mt con chó và mt con
chn.
e) Vi mi loi con vt trên, có mt sinh viên trong lp có mt con.
Câu 5
Đặt: L(x): “x là mt nhà logic”; C(x): “x ung café”; W(x); “x làm vic chăm ch”, T(x):
“x phát biu định lý”; f(x): hàm tr ra giá tr là bn ca x (gi s mi người có đúng 1
bn).
1. Phát biu các câu sau dưới dng logic bc nht (có s dng du =):
a. Không nhà logic nào ung café
b. Bt k ai là mt nhà logic cũng đều là bn ca ai đó
c. Không người nào phát biu được định lý li có mt người bn ung café.
Môn: Trí tu nhân to Ging viên: Tô Hoài Vit
10/15/2008
d. Ai có mt người bn làm vic chăm ch thì hoc là mt nhà logic hoc cũng là
mt người làm vic chăm ch
e. Mi người bn là mt nhà logic.
2. T các tin đề sau:
a. Tt c nhà logic đều ung café.
b. Bt k ai không phát biu được định lý đều không ung café.
c. mt s người mà bn ca h là nhà logic.
Chng minh rng: Có mt nhà logic ung café và phát biu được định lý.
Thut gii Vương Ho
Thut gii Vương Ho là mt thut gii khác đề chng minh vic suy dn mnh đề (có
cùng mc đích vi Robinson):
Bước 1: Đưa bài toán cn chng minh v dng chun:
GT1 ,GT2 ,...,GTn
KL1 , KL2 ,..., KLm
Trong đó các GTi j KL là các câu ch gm các phép , , ¬, không cha phép
hay . Lưu ý: du phy (,) vế trái tương đương vi , vế phi tương đương vi
.
Bước 2: Nếu tn ti mt câu có phép ¬ đầu thì chuyn vế câu và loi b phép ¬
Bước 3: Thay các du vế trái và các du vế phi bng du phy (,). Khi đó vế
trái ch còn du và ¬ , v phi ch còn du và ¬ .
Bước 4:
Nếu dòng hin hành có dng:
thì thay bng hai dòng:
Nếu dòng hin hành có dng:
thì thay bng hai dòng:
Bước 5: Mt dòng được chng minh nếu tn ti mt mnh đề c hai vế.
Bước 6: Mt dòng không th tách cũng không th chuyn vế du ¬ mà không có biến
mnh đề chung c hai vế thì không được chng minh.
Lp li bước 2 đến 6 cho ti khi mi dòng được chng minh hay tn ti mt dòng không
được chng minh. Bài toán ban đầu được chng minh nếu mi dòng tách ra tđược
chng minh.
Ví d: Cho các mnh đề:
(A) Tri mưa
(B) Tri mưa mc mưa cm lnh.
(C) Mc mưa
Ta s chng minh (D) “cm lnh” là mnh đề đúng.
Bài toán được chuyn sang dng chun thành:
Môn: Trí tu nhân to Ging viên: Tô Hoài Vit
10/15/2008
A, ¬A ¬C D, C D
Chng minh:
Tách dòng
1. A, ¬A, C D
2. A, ¬C, C D
3. A, D, C D (được cm)
Chuyn vế:
1. A, C D, A (được cm)
3. A, C D, C (được cm)
Vy bài toán ban đầu được chng minh.
Bài tp: S dng thut gii Vương Ho để gii các bài tp logic mnh đề (1, 2, 3).