離散數(shù)學(xué)謂詞邏輯

1、謂詞邏輯習(xí)題課第九周2014.11命題符號(hào)化命題符號(hào)化討論在給定解釋下謂詞公式的真值討論在給定解釋下謂詞公式的真值判斷公式是不是永真式，并加以說明判斷公式是不是永真式，并加以說明轉(zhuǎn)換前束合取范式轉(zhuǎn)換前束合取范式推理證明推理證明1.將下列命題符號(hào)化將下列命題符號(hào)化(1)(1)沒有不犯錯(cuò)誤的人沒有不犯錯(cuò)誤的人(2) 發(fā)光的不都是金子發(fā)光的不都是金子(3) 一切人都不一樣高一切人都不一樣高(4) 并不是所有的汽車都比火車快并不是所有的汽車都比火車快(5)不管黑貓白貓，抓住老鼠就是好貓不管黑貓白貓，抓住老鼠就是好貓(6)有唯一的偶素?cái)?shù)有唯一的偶素?cái)?shù)(7)對(duì)平面上任意兩點(diǎn)，有且僅有一條直線通過這對(duì)平面上

2、任意兩點(diǎn)，有且僅有一條直線通過這 兩點(diǎn)兩點(diǎn)(1) 沒有不犯錯(cuò)誤的人沒有不犯錯(cuò)誤的人 存在不犯錯(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)(2) 發(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)

3、( x)(L(x)G(x) (3) 一切人都不一樣高一切人都不一樣高 設(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)(4) 并不是所有的汽車都比火車快并不是所有的汽車都比火車快 設(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)

4、（5）不管黑貓白貓，抓住老鼠就是好貓不管黑貓白貓，抓住老鼠就是好貓 需要考慮問題：需要考慮問題：只是限制黑貓白貓，還是包含其它顏色的貓？只是限制黑貓白貓，還是包含其它顏色的貓？是指至少抓住一只就可以，還是抓住所有的？是指至少抓住一只就可以，還是抓住所有的？ 設(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) (6)有唯一的偶素?cái)?shù)有唯一的偶素?cái)?shù) 設(shè)：設(shè)：Q(x):x是偶數(shù)是偶數(shù),P(x):x是素?cái)?shù)是素

5、數(shù), E(x,y):xy 命題符號(hào)化為：命題符號(hào)化為： ( x)(Q(x) P(x)y(Q(y) P(y)E(x,y) (7)對(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)2.討論在給定解釋下謂詞公式的真值討論在給定解釋下謂詞公式的真值（1） x(PQ(x)R(a)D=-2,

6、3,6 , P:21,Q(x):x3, R(x):x5,a:5（2） x y(P(x)Q(x,y)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（1） x(PQ(x)R(a)D=-2,3,6 , P:21,Q(x):x3, R(x):x5,a:5 x(PQ(x)R(a)(P xQ(x)R(a)(P(Q(-2)Q(3)Q(6)R(5)(T(T T F )F(TF)FFF F（2） x y(P(x)Q(x,y)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真值為真值為

7、F3.判斷下列公式是不是永真式，并加以說明判斷下列公式是不是永真式，并加以說明（1）( xP(x) xQ(x) x(P(x) Q(x)解：不是永真式，取解釋如下解：不是永真式，取解釋如下 D= 1,2 P(1) P(2) Q(1) Q(2) F T F T在該解釋下在該解釋下 xP(x) 為為T， xQ(x)為為F，所以，所以 xP(x) xQ(x)為為F；而；而(P(1) Q(1)為為T， (P(2) Q(2)為為T，所以所以 x(P(x) Q(x)為為T；綜上該公式不是永真式；綜上該公式不是永真式4. 轉(zhuǎn)換前束合取范式轉(zhuǎn)換前束合取范式(1) 將謂詞公式將謂詞公式( x)( y)P(x) (

8、 z)Q(z,y) ( y)R(x,y)化為化為與之等價(jià)的前束合取范式與之等價(jià)的前束合取范式第一步，取消多余量詞：第一步，取消多余量詞： ( x)P(x) ( z)Q(z,y) ( y)R(x,y)第二步，約束變量換名：第二步，約束變量換名： ( x)P(x) ( z)Q(z,y) ( w)R(x,w)第三步，消去條件聯(lián)結(jié)詞：第三步，消去條件聯(lián)結(jié)詞： ( x) (P(x) ( z)Q(z,y) ( w)R(x,w)第四步，將第四步，將 深入：深入： ( x)( P(x) ( z)Q(z,y) ( w) R(x,w) ( x)( P(x) ( z) Q(z,y) ( w) R(x,w)第五步，將

9、量詞提前：第五步，將量詞提前： ( x)( z)( w)( P(x)Q(z,y) R(x,w) ( x)( z)( w) ( P(x)R(x,w) ( Q(z,y) R(x,w) ) 5.推理證明：推理證明：(1) ( 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(2) xP(x

10、) xQ(x) x (P(x)Q(x)(1) x (P(x)Q(x)P(假設(shè)假設(shè))(2) x (P(x)Q(x)T(1)E(3) (P(c)Q(c)ES(2)(4) P(c) Q(c)T(3)E(5) P(c) T(4)I(6) x P(x)EG(5)(7) x P(x) T(6)E(8) xP(x) xQ(x) P(9) xQ(x) T(7)(8)I(10) Q(c)US(9)(11) Q(c)T(4)I(12) Q(c) Q(c)T(10)(11)I (3)(3)每個(gè)大學(xué)生不是文科生就是理工科生，有的大學(xué)生是每個(gè)大學(xué)生不是文科生就是理工科生，有的大學(xué)生是優(yōu)等生，小張不是理工科生，但他是優(yōu)等

11、生，因此如果小優(yōu)等生，小張不是理工科生，但他是優(yōu)等生，因此如果小張是大學(xué)生，他就是文科生張是大學(xué)生，他就是文科生。 設(shè)設(shè) A(x):xA(x):x是大學(xué)生是大學(xué)生, , B(x):xB(x):x是是文科生文科生, , C(x):x C(x):x是理工科生是理工科生，D(x):xD(x):x是優(yōu)等生是優(yōu)等生, a:a:小張小張 x(x(A(x)(A(x)( B(x)C(x)B(x)C(x),), x(A(x)x(A(x)D(x)D(x) C(a)C(a)D(a) D(a) A(a)B(a)A(a)B(a) x(x(A(x)(A(x)( B(x)C(x)B(x)C(x),), x(A(x)x(A(

12、x)D(x)D(x) C(a)C(a)D(a) D(a) A(a)B(a)A(a)B(a) A(a) P(A(a) P(附加前提附加前提) ) x(x(A(x)(A(x)( B(x)C(x)B(x)C(x) P) P A(a)(A(a)( B(a)C(a)B(a)C(a) US ) US B(a)C(a)B(a)C(a) T ) T I I C(a)C(a)D(a) PD(a) P C(a) T C(a) T I I B(a) T B(a) T I I B(a) T B(a) T E E A(a)B(a) CPA(a)B(a) CP(4) 所有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整所

13、有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)。數(shù)。設(shè)設(shè)Q(x):x是有理數(shù)是有理數(shù) R(x):x是實(shí)數(shù)是實(shí)數(shù) 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(5)小楊、小劉和小林為高山俱樂部成員，該俱樂部的每個(gè)成員小楊、小劉和小林為高山俱樂部成員，該俱樂部的每個(gè)成員是個(gè)滑雪者或登山者。沒有一個(gè)登山者喜

14、歡雨。而所有滑雪者是個(gè)滑雪者或登山者。沒有一個(gè)登山者喜歡雨。而所有滑雪者都喜歡雪。凡是小楊喜歡的，小劉就不喜歡。小楊喜歡雨和雪。都喜歡雪。凡是小楊喜歡的，小劉就不喜歡。小楊喜歡雨和雪。試證明該俱樂部是否有個(gè)試證明該俱樂部是否有個(gè)是登山者而不是滑雪者的成員。如果有，他是誰？是登山者而不是滑雪者的成員。如果有，他是誰？設(shè)：設(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:小楊；小楊；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