離散數(shù)學(xué)謂詞邏輯PowerPoint 演示文稿

1、離離 散散 數(shù)數(shù) 學(xué)學(xué)第二章第二章 謂詞邏輯謂詞邏輯習(xí)題課習(xí)題課一. 命題符號(hào)化 60頁(2)n( x)(J(x)L(x)n( x)(L(x)S(x)n( x)(J(x)O(x)V(x)nJ(j) O(j) V(j) n ( x)(L(x)J(x) 或者或者 ( x)(L(x) J(x)n( x)(S(x)L(x)C(x) n ( x)(C(x) V(x) 或者或者( x)(C(x)V(x) h) ( x)(C(x)O(x)L(x) i) ( x)(W(x)C(x)H(x) j) ( x)(W(x)J(x)C(x) k) ( x)(L(x) y(J(y)A(x,y)l) ( x)(S(x) y

2、(L(y) A(x,y)習(xí)題課62頁(2) ( x ) y ( ( P ( x ) P ( y ) E ( x , y ) ) z(L(z)R(x,y,z)t(L(t)R(x,y,t)E(t,z)(3)b)設(shè)R(x):x是實(shí)數(shù)，G(x,y):xy (x)(R(x)y(R(y)G(y,x) c)設(shè)R(x):x是實(shí)數(shù)，G(x,y):xy f(x,y)=x+y g(x,y)=xy (x)yz(R(x)R(y)R(z)G(f(x,y),g(x,z) 或者 (x)yz(R(x)R(y)R(z)G(x+y,xz)習(xí)題課5)b)設(shè)N(x):x是數(shù)，A(x,y):y是x的后繼數(shù) (x)(N(x)A(x,1)(

3、6)設(shè)A(x):x是戴眼鏡的,B(x):x是用功的,C(x):x是大學(xué)生,D(x):x是大的,E(x):x是厚的，F(xiàn)(x):x是巨著, A(x,y):x在看y,a:那位，b:這本 A(a)B(a)C(a)D(b)E(b)F(b) A(a,b)補(bǔ)充題：1.每個(gè)人的叔叔都是他父親的弟弟。每個(gè)人的叔叔都是他父親的弟弟。 設(shè)：設(shè)：P(x):x是人，是人，U(x,y):y是是x的叔叔，的叔叔， B(x,y):x是是y的弟弟，的弟弟， f(x)=x的父親的父親 ( x)(P(x) y(U(x,y)B(y,f(x) 2.下面是判定一個(gè)年號(hào)是否為閏年的命題下面是判定一個(gè)年號(hào)是否為閏年的命題:“年號(hào)能被年號(hào)能被

4、4整除并且不能被整除并且不能被100整除的為閏年整除的為閏年. 或者年或者年號(hào)能被號(hào)能被400整除的也是閏年整除的也是閏年.” 設(shè)設(shè) Y(x):x是年號(hào)是年號(hào); D(x,y):x可整除可整除y; R(x):x是閏年是閏年 ( x)(Y(x)(D(4,x) D(100,x)R(x)(D(400,x) R(x)66頁(3)b)P:21,Q(x):x3, R(x):x5,a:5,-2,3,6( x)(PQ(x)R(a)(P( x)Q(x)R(a)(P(Q(-2)Q(3)Q(6)R(5)(T(T T F )F(TF)FFF F 4)b)對(duì)約束變?cè)獡Q名對(duì)約束變?cè)獡Q名( x)(P(x)(R(x)Q(x)

5、( x)R(x) zS(x,z) y(P(y)(R(y)Q(y) tR(t) uS(x,u) (5)a)對(duì)自由變?cè)雽?duì)自由變?cè)? yA(x,y)( x)B(x,z) ( x) zC(x,y,z) ( yA(u,y)( x)B(x,v) ( x) zC(x,w,z) 習(xí)題課習(xí)題課72頁頁(2)d)論域?yàn)檎撚驗(yàn)?,2 P(1) P(2) Q(1,1) Q(1,2) Q(2,1) Q(2,2) F T T T F F( x) y(P(x)Q(x,y)y(P(1)Q(1,y) y(P(2)Q(2,y)(P(1)Q(1,1)(P(1)Q(1,2) (P(2)Q(2,1)(P(2)Q(2,2)(FT

6、)(FT)(TF)(TF)(FF)(FF)F6)判斷下面推證是否正確。 ( x)(A(x)B(x) ( x)( A(x)B(x) ( x) (A(x) B(x) ( x)(A(x) B(x) ( x)A(x)( x) B(x) ( x)A(x) ( x) B(x) ( x)A(x)( x)B(x) ( x)A(x)( x)B(x)第步錯(cuò)，由到用的是公式：第步錯(cuò)，由到用的是公式： ( x)(A(x) B(x)( x)A(x)( x) B(x) 無 此 公 式 ， 而 是無 此 公 式 ， 而 是 ( x ) ( A ( x ) B ( x ) ) ( x)A(x)( x) B(x)，應(yīng)將中的，應(yīng)

7、將中的換成換成 即：即：( x)(A(x)B(x)( x)(A(x)B(x) ( x)( A(x)B(x) ( x) (A(x) B(x) ( x)(A(x) B(x) ( x)A(x)( x) B(x) ( x)A(x) ( x) B(x) ( x)A(x)( x)B(x) ( x)A(x)( x)B(x)因?yàn)橛晒揭驗(yàn)橛晒紼18 PQQ P ( x)(A(x)B(x) ( x)A(x)( x)B(x) ， P Q得得 ( x)A(x)( x)B(x)( x)(A(x)B(x)75頁(1)b)( x)(yP(x,y)( zQ(z)R(x)( x)( yP(x,y)(zQ(z)R(x)( x

8、)( yP(x,y)( z Q(z)R(x)( x)( yP(x,y) z( Q(z)R(x)( x) y z(P(x,y)( Q(z)R(x)(2)c)( x)P(x)( x)( zQ(x,z) zR(x,y,z)( x)P(x)( x)( zQ(x,z) zR(x,y,z)( x) P(x)( x)( zQ(x,z) zR(x,y,z) ( x) P(x) u( zQ(u,z) tR(u,y,t)( x) u z t( P(x)(Q(u,z)R(u,y,t)( x) u z t( P(x)Q(u,z)R(u,y,t)此式既是前束析取范式，也是前束合取范式。此式既是前束析取范式，也是前束合取

9、范式。79頁頁(2)a)用用CP規(guī)則證明規(guī)則證明( x)(P(x)Q(x) ( x)P(x)( x) Q(x)因?yàn)橐驗(yàn)? x)P(x)( x) Q(x) ( x)P(x)( x) Q(x) ( x)P(x) P(附加前提附加前提) ( x) P(x) T E P(a) ES ( x)(P(x)Q(x) P P(a)Q(a) US Q(a) T I ( x) Q(x) EG ( x)P(x)( x) Q(x) CP習(xí)題課3)a)所有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)所有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)。數(shù)是整數(shù)。設(shè)設(shè)Q(x):x是有理數(shù)是有理數(shù) R(x):x是實(shí)數(shù)是實(shí)數(shù)

10、 I(x):x是整數(shù)是整數(shù) ( x)(Q(x)R(x), ( x)(Q(x)I(x) ( x)(R(x)I(x) ( x)(Q(x)I(x) P Q(a)I(a) ES Q(a) T I I(a) T I ( x)(Q(x)R(x) P Q(a)R(a) US R(a) T I R(a)I(a) T I ( x)(R(x)I(x) EG習(xí)題課b)任何人如果他喜歡步行，他就不喜歡乘汽車；每任何人如果他喜歡步行，他就不喜歡乘汽車；每個(gè)人或者喜歡乘汽車或者喜歡騎自行車。有的人不個(gè)人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因此有的人不愛步行。愛騎自行車，因此有的人不愛步行。設(shè)設(shè) A(x):

11、x是人是人, B(x):x是是喜歡步行喜歡步行, C(x):x喜歡乘汽車，喜歡乘汽車，D(x):x喜歡騎自行車喜歡騎自行車( x)(A(x)(B(x) C(x),( x)(A(x)(C(x)D(x), ( x)(A(x) D(x) ( x)(A(x) B(x) ( x)(A(x) D(x) P A(a) D(a) ES A(a) T I D(a) T I ( x)(A(x)(B(x) C(x) P A(a)(B(a) C(a) US B(a) C(a) T I ( x)(A(x)(C(x)D(x) P A(a)(C(a)D(a) US C(a)D(a) T I C(a) T I B(a) T

12、I A(a) B(a) T I ( x)(A(x) B(x) EG 習(xí)題課c)每個(gè)大學(xué)生不是文科生就是理工科生，有的大學(xué)生是優(yōu)等生，小張不是理工科生，但他是優(yōu)等生，因此如果小張是大學(xué)生，他就是文科生。設(shè) A(x):x是大學(xué)生, B(x):x是文科生, C(x):x是理工科生，D(x):x是優(yōu)等生, a:小張(x)(A(x)(B(x)C(x),(x)(A(x)D(x) C(a)D(a) A(a)B(a)習(xí)題課(x)(A(x)(B(x)C(x),(x)(A(x)D(x) C(a)D(a) A(a)B(A) A(a) P(附加前提) (x)(A(x)(B(x)C(x) P A(a)(B(a)C(a)

13、 US B(a)C(a) T I C(a)D(a) P習(xí)題課補(bǔ)充題：小楊、小劉和小林為高山俱樂部成員，該俱樂部的每個(gè)成員是個(gè)滑雪者或登山者。沒有一個(gè)登山者喜歡雨。而所有滑雪者都喜歡雪。凡是小楊喜歡的，小劉就不喜歡。小楊喜歡雨和雪。試證明該俱樂部是否有個(gè)是登山者而不是滑雪者的成員。如果有，他是誰？設(shè)：M(x):x是高山俱樂部成員。H(x):x是滑雪者。 D(x):x是登山者。L(x,y):x喜歡y。 a:小楊；b:小劉；c:小林；d:雨；e:雪。 M(x):x是高山俱樂部成員。是高山俱樂部成員。H(x):x是滑雪者。是滑雪者。 D(x):x是登山者。是登山者。L(x,y):x喜歡喜歡y。 a:小

14、楊；小楊；b:小劉；小劉；c:小林；小林；d:雨；雨；e:雪。雪。命題符號(hào)化為：命題符號(hào)化為：M(a), M(b), M(c), ( x)(M(x)( H(x)D(x), ( x)(D(x)L(x,d), ( x)(H(x)L(x,e)( x)(L(a,x) L(b,x), L(a,d)L(a,e) L(a,d)L(a,e) P L(a,e) T ( x)(L(a,x) L(b,x) P L(a,e) L(b,e) US L(b,e) T I11( x)(H(x)L(x,e) P H(b)L(b,e) US H(b) T I12 ( x)(M(x)(H(x)D(x) P M(b)(H(b)D(

15、b) US M(b) P H(b)D(b) T I11 D(b) T I10 D(b) H(b) T 謂詞邏輯解決這個(gè)問題的方法：在表示命題時(shí)，既表示出主語，也表示出謂語，就可以解決上述問題。這就提出了謂詞的概念。令S(x)表示x是大學(xué)生，a:小張，b:小李 命題P表示成S(a):小張是大學(xué)生。 命題Q表示成S(b):小李是大學(xué)生。從符號(hào)S(a)、S(b)可看出小張和小李都是大學(xué)生的共性。謂詞邏輯令N(x):x是自然數(shù)。I(x):x是整數(shù)。 表示所有的。 A: (x)(N(x)I(x)B :N(8) C :I(8)N(8)N(8)I(8)I(8)推理如此實(shí)現(xiàn)：推理如此實(shí)現(xiàn)： N(8)I(8)N

16、(8)I(8)符號(hào)符號(hào) S(x)S(x)、N(x)N(x)、I(x)I(x)就是所謂的謂詞就是所謂的謂詞。習(xí)題選講命題符號(hào)化1. 1. 在一階邏輯中將下列命題符號(hào)化。在一階邏輯中將下列命題符號(hào)化。（1 1） 每個(gè)人都有心臟。每個(gè)人都有心臟。（2 2） 有的狗會(huì)飛。有的狗會(huì)飛。（3 3） 沒有不犯錯(cuò)誤的人。沒有不犯錯(cuò)誤的人。（4 4） 發(fā)光的不都是金子。發(fā)光的不都是金子。（5 5） 一切人都不一樣高。一切人都不一樣高。（6 6） 并不是所有的汽車都比火車快。并不是所有的汽車都比火車快。（7 7） 沒有一個(gè)自然數(shù)大于等于任何自然數(shù)。沒有一個(gè)自然數(shù)大于等于任何自然數(shù)。（8 8） 有唯一的偶素?cái)?shù)。有唯

17、一的偶素?cái)?shù)。（9 9） 不管黑貓白貓，抓住老鼠就是好貓。不管黑貓白貓，抓住老鼠就是好貓。（1010）對(duì)平面上任意兩點(diǎn)，有且僅有一條直線通過這兩點(diǎn)。）對(duì)平面上任意兩點(diǎn)，有且僅有一條直線通過這兩點(diǎn)。習(xí)題選講命題符號(hào)化解：由于沒指出個(gè)體域，故用全總個(gè)體域解：由于沒指出個(gè)體域，故用全總個(gè)體域（1）每個(gè)人都有心臟。）每個(gè)人都有心臟。本命題的含義：對(duì)于每一個(gè)本命題的含義：對(duì)于每一個(gè)x，如果，如果x是人，則是人，則x有心臟。有心臟。因而應(yīng)首先從宇宙間的一切事物中，將人分離出來，這就因而應(yīng)首先從宇宙間的一切事物中，將人分離出來，這就必須引入特性謂詞。必須引入特性謂詞。 令令M(x):x是人，是人，H(x):x

18、有心臟。有心臟。 命題符號(hào)化為：命題符號(hào)化為： ( x)(M(x)H(x)如果將其中的如果將其中的改為改為，即，即( x)(P(x)H(x)，它表示的，它表示的意思是：意思是：“對(duì)于每個(gè)對(duì)于每個(gè)x，x是人且是人且x有心臟有心臟”。這是一個(gè)假命題，。這是一個(gè)假命題，而而“每個(gè)人都有心臟每個(gè)人都有心臟”是真命題。是真命題。這 說 明 將 命 題這 說 明 將 命 題 “ 每 個(gè) 人 都 有 心 臟每 個(gè) 人 都 有 心 臟 ” 符 號(hào) 化 為符 號(hào) 化 為(x)(P(x)H(x)是錯(cuò)誤的。是錯(cuò)誤的。 習(xí)題選講命題符號(hào)化（2）有的狗會(huì)飛。）有的狗會(huì)飛。 命題的意思是：存在一個(gè)命題的意思是：存在一個(gè)x

19、，使得，使得x是狗，并且是狗，并且x會(huì)飛。會(huì)飛。 設(shè)設(shè)D(x)：x是狗，是狗，F(xiàn)(x)：x會(huì)飛。會(huì)飛。命題符號(hào)化為：命題符號(hào)化為：( x)(D(x)F(x)如果將其中的如果將其中的改為改為，即，即( x)(D(x)F(x)，如果用如果用a表示某只貓，則表示某只貓，則D(a)為假，因而，為假，因而，D(a)F(a)為真，所以為真，所以( x)(D(x)F(x)為真，而為真，而“有有的狗會(huì)飛的狗會(huì)飛”為假，為假，這說明將這說明將“有的狗會(huì)飛有的狗會(huì)飛”符號(hào)化為符號(hào)化為( x)(D(x)F(x)是錯(cuò)誤的。是錯(cuò)誤的。 （3）沒有不犯錯(cuò)誤的人。）沒有不犯錯(cuò)誤的人。 命題的意思是：命題的意思是： 存在不犯

20、錯(cuò)誤的人是不可能的。存在不犯錯(cuò)誤的人是不可能的。 只要是人，必然犯錯(cuò)誤。只要是人，必然犯錯(cuò)誤。 設(shè)設(shè) M(x): x是人，是人，F(xiàn)(x):x犯錯(cuò)誤犯錯(cuò)誤命題符號(hào)化為命題符號(hào)化為 ( x)(M(x)F(x) ( x)(M(x)F(x)（4）發(fā)光的不都是金子。）發(fā)光的不都是金子。 命題的意思是：命題的意思是： 不是發(fā)光的東西都是金子。不是發(fā)光的東西都是金子。 存在著發(fā)光的東西不是金子。存在著發(fā)光的東西不是金子。 設(shè)設(shè) L(x)：x是發(fā)光的東西，是發(fā)光的東西，G(x)：x是金子。是金子。 命題符號(hào)化為命題符號(hào)化為 ( x)(L(x)G(x) ( x)(L(x)G(x) （5）一切人都不一樣高。）一切

21、人都不一樣高。 設(shè)設(shè) F(x):x是人是人, H(x,y), x與與y相同相同, L(x,y): x與與y一樣高，一樣高，命題符號(hào)化為命題符號(hào)化為 ( x)(F(x)y(F(y)H(x,y)L(x,y)或或 ( x) y(F(x) F(y)H(x,y)L(x,y)（6）并不是所有的汽車都比火車快。）并不是所有的汽車都比火車快。 設(shè)設(shè) F(x):x是汽車是汽車, G(y):y是火車是火車, H(x,y):x比比y快，快，命題符號(hào)化為命題符號(hào)化為 ( x) y(F(x) G(y)H(x,y)或或( x) y(F(x) G(y)H(x,y)習(xí)題選講命題符號(hào)化習(xí)題選講命題符號(hào)化（7）沒有一個(gè)自然數(shù)大于

22、等于任何自然數(shù)。設(shè)N(x):x是自然數(shù)，G(x,y):xy命題符號(hào)化為：(x)(N(x) y(N(y)G(x,y)（8）有唯一的偶素?cái)?shù)。設(shè)：Q(x):x是偶數(shù)，P(x):x是素?cái)?shù)， E(x,y):xy命題符號(hào)化為：(x)(Q(x)P(x)y(Q(y)P(y)E(x,y)習(xí)題選講習(xí)題選講命題符號(hào)化命題符號(hào)化（9）不管黑貓白貓，抓住老鼠就是好貓。）不管黑貓白貓，抓住老鼠就是好貓。 需要考慮問題：需要考慮問題：只是限制黑貓白貓，還是包含其它顏色的貓？只是限制黑貓白貓，還是包含其它顏色的貓？是指至少抓住一只就可以，還是抓住所有的？是指至少抓住一只就可以，還是抓住所有的？ 因此在描述命題時(shí)，總是將這些模

23、糊概念做某種確切理解。因此在描述命題時(shí)，總是將這些模糊概念做某種確切理解。 設(shè)設(shè) C(x)：x是貓，是貓， W(x)：x是白的，是白的， B(x)：x是黑的是黑的 G(x)：x是好的，是好的，M(x)：x是老鼠，是老鼠， K(x)：x抓住抓住y命題符號(hào)化為命題符號(hào)化為( x) y(C(x)M(y)(B(x)W(x)K(x,y)G(x)習(xí)題選講命題符號(hào)化（10）對(duì)平面上任意兩點(diǎn)，有且僅有一條直線通過這兩）對(duì)平面上任意兩點(diǎn)，有且僅有一條直線通過這兩點(diǎn)。點(diǎn)。 設(shè)設(shè) P(x)：x是一個(gè)點(diǎn)，是一個(gè)點(diǎn)，L(x)：x是一條直線是一條直線 R(x,y,z)：z通過通過x,y，E(x,y)：x等于等于y命題符號(hào)化為命題符號(hào)化為( x) y(P(x)P(y)E(x,y) z(L(z)R(x,y,z) u(L(u)R(x,y,u)E(u,z)習(xí)題選講公式判斷2、判斷下列各式是否是重言式？證明你的判斷。、判斷下列各式是否是重言式？證明你的判斷。(1) ( x)(F(x) G(x)(2) ( x)(F(x) G(x)(3) ( x) y(F(