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

1、離離 散散 數(shù)數(shù) 學學第二章第二章 謂詞邏輯謂詞邏輯習題課習題課一. 命題符號化 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)習題課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ù)，G(x,y):xy (x)(R(x)y(R(y)G(y,x) c)設(shè)R(x):x是實數(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)習題課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是大學生,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)補充題：1.每個人的叔叔都是他父親的弟弟。每個人的叔叔都是他父親的弟弟。 設(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.下面是判定一個年號是否為閏年的命題下面是判定一個年號是否為閏年的命題:“年號能被年號能被

4、4整除并且不能被整除并且不能被100整除的為閏年整除的為閏年. 或者年或者年號能被號能被400整除的也是閏年整除的也是閏年.” 設(shè)設(shè) Y(x):x是年號是年號; 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)對約束變元換名對約束變元換名( 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)對自由變元代入對自由變元代入( yA(x,y)( x)B(x,z) ( x) zC(x,y,z) ( yA(u,y)( x)B(x,v) ( x) zC(x,w,z) 習題課習題課72頁頁(2)d)論域為論域為1,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)第步錯，由到用的是公式：第步錯，由到用的是公式： ( 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)因為由公式因為由公式E18 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)因為因為( 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習題課3)a)所有有理數(shù)是實數(shù)，某些有理數(shù)是整數(shù)，因此某些實所有有理數(shù)是實數(shù)，某些有理數(shù)是整數(shù)，因此某些實數(shù)是整數(shù)。數(shù)是整數(shù)。設(shè)設(shè)Q(x):x是有理數(shù)是有理數(shù) R(x):x是實數(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習題課b)任何人如果他喜歡步行，他就不喜歡乘汽車；每任何人如果他喜歡步行，他就不喜歡乘汽車；每個人或者喜歡乘汽車或者喜歡騎自行車。有的人不個人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因此有的人不愛步行。愛騎自行車，因此有的人不愛步行。設(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 習題課c)每個大學生不是文科生就是理工科生，有的大學生是優(yōu)等生，小張不是理工科生，但他是優(yōu)等生，因此如果小張是大學生，他就是文科生。設(shè) A(x):x是大學生, 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)(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習題課補充題：小楊、小劉和小林為高山俱樂部成員，該俱樂部的每個成員是個滑雪者或登山者。沒有一個登山者喜歡雨。而所有滑雪者都喜歡雪。凡是小楊喜歡的，小劉就不喜歡。小楊喜歡雨和雪。試證明該俱樂部是否有個是登山者而不是滑雪者的成員。如果有，他是誰？設(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:雪。雪。命題符號化為：命題符號化為：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 謂詞邏輯解決這個問題的方法：在表示命題時，既表示出主語，也表示出謂語，就可以解決上述問題。這就提出了謂詞的概念。令S(x)表示x是大學生，a:小張，b:小李 命題P表示成S(a):小張是大學生。 命題Q表示成S(b):小李是大學生。從符號S(a)、S(b)可看出小張和小李都是大學生的共性。謂詞邏輯令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)推理如此實現(xiàn)：推理如此實現(xiàn)： N(8)I(8)N

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

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

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

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

20、錯誤的人是不可能的。存在不犯錯誤的人是不可能的。 只要是人，必然犯錯誤。只要是人，必然犯錯誤。 設(shè)設(shè) M(x): x是人，是人，F(xiàn)(x):x犯錯誤犯錯誤命題符號化為命題符號化為 ( 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是金子。是金子。 命題符號化為命題符號化為 ( 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一樣高，一樣高，命題符號化為命題符號化為 ( 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快，快，命題符號化為命題符號化為 ( x) y(F(x) G(y)H(x,y)或或( x) y(F(x) G(y)H(x,y)習題選講命題符號化習題選講命題符號化（7）沒有一個自然數(shù)大于

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

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