離散數(shù)學(xué)(謂詞邏輯)課后總結(jié)

1、第2章 謂詞邏輯21基本概念 例題 . 所有的自然數(shù)都是整數(shù)。 設(shè) N(x)：x是自然數(shù)。I(x)：x是整數(shù)。此命題可以寫(xiě)成 "x(N(x)I(x) 例題. 有些自然數(shù)是偶數(shù)。設(shè) E(x)：x是偶數(shù)。此命題可以寫(xiě)成 $x(N(x)E(x) 例題3. 每個(gè)人都有一個(gè)生母。 設(shè) P(x):x是個(gè)人。M(x,y):y是x的生母。此命題可以寫(xiě)成： "x(P(x)$y(P(y)M(x,y)2-2 謂詞公式及命題符號(hào)化 例題1. 如果x是奇數(shù)，則2x是偶數(shù)。 其中客體x與客體2x之間就有函數(shù)關(guān)系，可以設(shè)客體函數(shù) g(x)=2x， 謂詞 O(x)：x是奇數(shù)， E(x)：x是偶數(shù)， 則此命

2、題可以表示為： "x(O(x)E(g(x) 例題2 小王的父親是個(gè)醫(yī)生。 設(shè)函數(shù)f(x)=x的父親，謂詞D(x):x是個(gè)醫(yī)生，a:小王，此命題可以表示為D(f(a)。 例題3 如果x和y都是奇數(shù)，則x+y是偶數(shù)。 設(shè) h(x,y)=x+y ，此命題可以表示為:"x"y(O(x)O(y)E(h(x,y)命題的符號(hào)表達(dá)式與論域有關(guān)系兩個(gè)公式：一般地，設(shè)論域?yàn)閍1,a2,.,an，則有 (1). "xA(x)ÛA(a1)A(a2).A(an) (2). $xB(x)ÛB(a1)B(a2).B(an)1.每個(gè)自然數(shù)都是整數(shù)。該命題的真值是真的

3、。 表達(dá)式"x(N(x)I(x)在全總個(gè)體域的真值是真的,因"x(N(x)I(x)Û(N(a1)I(a1) (N(a2)I(a2) (N(an)I(an) 式中的x不論用自然數(shù)客體代入，還是用非自然數(shù)客體代入均為真。例如(N(0.1)I(0.1)也為真。 而"x(N(x)I(x)在全總個(gè)體域卻不是永真式。 "x(N(x)I(x)Û(N(a1)I(a1)(N(a2)I(a2) (N(an)I(an) 比如x用0.2代入(N(0.2)I(0.2)就為假。所以此表達(dá)式不能表示這個(gè)命題。 2.有些大學(xué)生吸煙。 此命題的真值也是真的。 $x(S

4、(x)A(x)Û(S(a1)A(a1)(S(a2)A(a2) (S(an)A(an)且x只有用吸煙的大學(xué)生代入才為真，例如a2不是大學(xué)生或者不會(huì)吸煙的客體，則(S(a2)A(a2)為假。所以用$x(S(x)A(x)表示此命題是對(duì)的。 而$x(S(x)A(x)中的x用非大學(xué)生的客體代入時(shí)也為真，例如(S(a2)A(a2)為真。所以表達(dá)式$x(S(x)A(x)不能表示這個(gè)命題。3.所有大學(xué)生都喜歡一些歌星。 令S(x)：x是大學(xué)生，X(x)：x是歌星，L(x,y)：x喜歡y。 則命題的表達(dá)式為： "x(S(x)$y(X(y)L(x,y) 4.沒(méi)有不犯錯(cuò)誤的人。 此話(huà)就是“沒(méi)有人

5、不犯錯(cuò)誤”，“沒(méi)有”就是“不存在”之意。令P(x)：x是人，F(xiàn)(x)：x犯錯(cuò)誤， 此命題的表達(dá)式為：Ø$x(P(x)ØF(x) 或者 "x(P(x)F(x)5.不是所有的自然數(shù)都是偶數(shù)。 令N(x)：x是自然數(shù)，E(x)：x是偶數(shù)， 命題的表達(dá)式為: Ø"x(N(x)E(x) 或者 $x(N(x)ØE(x)6.如果一個(gè)人只是說(shuō)謊話(huà)，那么他所說(shuō)的每句話(huà)沒(méi)有一句是可以相信的。 令A(yù)(x)：x是人，B(x,y)：y是x說(shuō)的話(huà)，C(x):x是謊話(huà)，D(x)：x是可以相信的 命題的表達(dá)式為: "x(A(x)("y(B(x,y

6、)C(y)Ø$z(B(x,z)D(z)7.每個(gè)自然數(shù)都有唯一的后繼數(shù)。 令N(x)：x是自然數(shù)，A(x,y)：y是x的后繼數(shù)， E(x,y)：x=y 則命題的表達(dá)式為 "x(N(x)$y(N(y)A(x,y)"z(N(z)A(x,z)E(y,z) 小結(jié)1.命題的符號(hào)表達(dá)式形式與論域有關(guān)系。 論域擴(kuò)大需要用特性謂詞對(duì)客體進(jìn)行說(shuō)明.注意如何添加特性謂詞(即要注意特性謂詞后邊是什么聯(lián)結(jié)詞)。2.如果量詞前有否定符號(hào)，如“沒(méi)有.”“不是所有的.”等，可以按照字面直譯。如“Ø$x” “Ø"x.”3.命題的符號(hào)表達(dá)式中所有客體變?cè)仨毝际羌s束變?cè)?/p>

7、，才表示命題。有時(shí)給定命題中有些量詞沒(méi)有明確給出，要仔細(xì)分析并寫(xiě)出這隱含的量詞。 例如 a) 金子閃光，但閃光的不一定都是金子。G(x),F(x) "x(G(x)F(x)Ø"x(F(x) G(x) b) 沒(méi)有大學(xué)生不懂外語(yǔ)。S(x),K(x,y),F(x)Ø$x(S(x)"y(F(y)ØK(x,y)2-3謂詞演算的等價(jià)式與蘊(yùn)涵式 例1.設(shè)論域D=1,2 a=1 b=2 f(1)=2 ，f(2)=1P(1,1)=T ，P(1,2)=T ，P(2 ,1)=F P(2,2)=F求謂詞公式"x$y(P(x,y)®P(f(x

8、),f(y)的真值。解： "x$y(P(x,y)®P(f(x),f(y)Û$y(P(1,y) ®P(f(1),f(y) Ù$y(P(2,y) ®P(f(2),f(y)Û(P(1,1) ®P(f(1),f(1)Ú (P(1,2) ®P(f(1),f(2)Ù (P(2,1) ®P(f(2),f(1)Ú(P(2,2) ®P(f(2),f(2) Û(P(1,1) ®P(2,2)Ú(P(1,2) ®P(2,1)Ù (

9、P(2,1) ®P(1,2)Ú(P(2,2) ®P(1,1)Û(T®F )Ú (T®F)Ù(F®T) Ú (F®T)Û(FÚ F)Ù(T Ú T)ÛFÙT ÛF量詞轄域的擴(kuò)充公式 1. "xA(x)BÛ"x(A(x)B) 2. "xA(x)BÛ"x(A(x)B) 3. $xA(x)BÛ$x(A(x)B) 4. $xA(x)BÛ$x(x)B

10、) 5. B"xA(x)Û"x(BA(x) 6. B$xA(x)Û$x(BA(x) 7. "xA(x)BÛ$x(A(x)B) 8. $xA(x)BÛ"x(A(x)B)量詞分配公式1. $x(A(x)B(x)Û$xA(x)$xB(x)2. "x(A(x)B(x)Û"xA(x)"xB(x)3. $x(A(x)B(x)Þ$xA(x)$xB(x)4. "xA(x)"xB(x)Þ"x(A(x)B(x)其它公式1. $x(A(x

11、)B(x)Û"xA(x)$xB(x) 2. $xA(x)"xB(x)Þ"x(A(x)B(x)兩個(gè)量詞的公式1. "x"yA(x,y)Û"y"xA(x,y)2. "x"yA(x,y)Þ$y"xA(x,y)3. $y"xA(x,y)Þ"x$yA(x,y)4. "x$yA(x,y)Þ$x$yA(x,y)5. "y"xA(x,y)Þ$x"yA(x,y)6. $x"y

12、A(x,y)Þ"y$xA(x,y)7. "y$xA(x,y)Þ$x$yA(x,y)8. $x$yA(x,y)Û$y$xA(x,y)下面證明公式1.。 證明：設(shè)論域?yàn)閍1,a2,.,an，則"x"yA(x,y)Û"yA(a1,y)"yA(a2,y)"yA(an,y) Û(A(a1,a1)A(a1,a2)A(a1,an)(A(a2,a1)A(a2,a2)A(a2,an) (A(an,a1)A(an,a2)A(an,an) Û(A(a1,a1)A(a2,a1)A(an,a

13、1) (A(a1,a2)A(a2,a2)A(an,a2) (A(a1,an)(A(a2,an)A(an,an) Û"xA(x,a1)"xA(x,a2)"xA(x,an) Û"y"xA(x,y)例2. 令A(yù)(x,y)表示x+y=xy, 論域是1,2,3, 求謂詞公式Ø"x$yA(x,y)的真值。解： Ø"x$yA(x,y)Û$x"yØA(x,y) Û"yØA(1,y)"yØA(2,y)"yØ

14、;A(3,y) Û(ØA(1,1)ØA(1,2)ØA(1,3) (ØA(2,1)ØA(2,2)ØA(2,3)(ØA(3,1)ØA(3,2)ØA(3,3) Û(TTT)(TFT)(TTT) ÛTFTÛT2-4前束范式例1. "xA(x)$xB(x) ÛØ"xA(x)$xB(x) Û$xØA(x)$xB(x) Û$xØA(x)$yB(y) (換元) Û$x(ØA(x)$y

15、B(y) (量詞轄域擴(kuò)充) Û$x$y(ØA(x)B(y)另一個(gè)方法："xA(x)$xB(x) ÛØ"xA(x)$xB(x) Û$xØA(x)$xB(x) Û$x(ØA(x)B(x) (量詞分配公式)例2."x(P(x)R(x)(Ø$xP(x)Q(x) ÛØ"x(P(x)R(x)(Ø$xP(x)Q(x) (去) Û$xØ(P(x)R(x)("xØP(x)Q(x) (量詞轉(zhuǎn)換) Û$x(&

16、#216;P(x)ØR(x)("xØP(x)Q(x) (后移Ø) Û$x(ØP(x)ØR(x)("yØP(y)Q(z) (換變?cè)? Û$x(ØP(x)ØR(x)"y(ØP(y)Q(z) (擴(kuò)量詞轄域) Û$x"y(ØP(x)ØR(x)(ØP(y)Q(z)(擴(kuò)量詞轄域)2-5 謂詞演算的推理理論例1. 令A(yù)(x)表示x是自然數(shù)，B(x)表示x是整數(shù)。 "x(A(x)B(x) P A(c)B(c) U

17、S 如c=0.1 $xA(x) P A(c) × ES A(0.1)為F $xB(x) P B(c) ES 如c=-1 $xA(x) P A(c) × ES A(-1)為F正確解法如下： $xA(x) P A(c) ES "x(A(x)B(x) P A(c)B(c) US B(c) T I11例2 所有金屬都導(dǎo)電。銅是金屬。故銅導(dǎo)電。令 M(x):x是金屬。C(x):x導(dǎo)電。a:銅。符號(hào)化為： "x(M(x)C(x),M(a) ÞC(a) "x(M(x)C(x) P M(a)C(a) US M(a) P C(a) T I11 例3 所

18、有自然數(shù)都是整數(shù)。有些數(shù)是自然數(shù)。因此有些數(shù)是整數(shù)。令A(yù)(x)表示x是自然數(shù)，B(x)表示x是整數(shù)。"x(A(x)B(x)， $xA(x) Þ $xB(x) $xA(x) P A(c) ES "x(A(x)B(x) P A(c)B(c) US B(c) T I11 $xB(x) EG 例4不認(rèn)識(shí)錯(cuò)誤的人，也不能改正錯(cuò)誤。有些誠(chéng)實(shí)的人改正了錯(cuò)誤。所以有些誠(chéng)實(shí)的人是認(rèn)識(shí)了錯(cuò)誤的人。設(shè)A(x):x是認(rèn)識(shí)錯(cuò)誤的人。B(x):x改正了錯(cuò)誤。C(x):x是誠(chéng)實(shí)的人。符號(hào)化為："x(ØA(x)ØB(x)，$x(C(x)B(x), Þ $x

19、(C(x)A(x) $x(C(x)B(x) P C(c)B(c) ES C(c) T I1 B(c) T I2 "x(ØA(x)ØB(x)P ØA(c)ØB(c) US ØØA(c) T I12 A(c) T E1 C(c)A(c) T I9 $x(C(x)A(x) EG 例5.“鳥(niǎo)都會(huì)飛。猴子都不會(huì)飛。所以，猴子都不是鳥(niǎo)?！痹O(shè) B(x):x是鳥(niǎo)；F(x):x會(huì)飛；M(x):x是猴子。"x(B(x)F(x),"x(M(x)ØF(x)Þ"x(M(x)ØB(x) 證明：

20、 "x(B(x)F(x) P B(a)F(a) US "x(M(x)ØF(x) P M(a)ØF(a) US ØF(a)ØB(a) T E18 M(a)ØB(a) T I13 "x(M(x)ØB(x) UG 例6.$x(A(x)B(x),"x(B(x)ØC(x),"xC(x)Þ$xA(x) (1) $x(A(x)B(x) P (2) A(a)B(a) ES (1) (3) "x(B(x)ØC(x) P (4) B(a)ØC(a) US

21、(3) (5) "xC(x) P (6) C(a) US (5) (7) ØB(a) T (4)(6) I12 (8) A(a) T (2)(7) I10 (9) $xA(x) EG (8)例7 一些病人喜歡所有醫(yī)生。任何病人都不喜歡庸醫(yī)。所以沒(méi)有醫(yī)生是庸醫(yī)。設(shè): P(x):x是病人, D(x):x是醫(yī)生, Q(x):x是庸醫(yī), L(x,y): x喜歡y.請(qǐng)同學(xué)將上述各個(gè)命題符號(hào)化： $x(P(x)"y(D(y)L(x,y)，"x(P(x)"y(Q(y)ØL(x,y) ÞØ$y(D(y)Q(y)$x(P(x)&qu

22、ot;y(D(y)L(x,y)，"x(P(x)"y(Q(y)ØL(x,y) ÞØ$y(D(y)Q(y) $x(P(x)"y(D(y)L(x,y) P P(a)"y(D(y)L(a,y) ES P(a) T I1 "y(D(y)L(a,y) T I2 "x(P(x)"y(Q(y)ØL(x,y) P P(a)"y(Q(y)ØL(a,y) US "y(Q(y)ØL(a,y) T I11 D(b)L(a,b) US Q(b)ØL(a,b) US

23、 L(a,b) ØQ(b) T E18 D(b)ØQ(b) T I13 ØD(b)ØQ(b) T E16 Ø(D(b)Q(b) T E8 "yØ(D(y)Q(y) UG Ø$y(D(y)Q(y) T E25例8 $x(P(x)Q(x) Þ "xP(x)$xQ(x)用條件論證證明： "xP(x) P (附加前提) $x(P(x)Q(x) P P(a)Q(a) ES P(a) US Q(a) T I11 $xQ(x) EG "xP(x)$xQ(x) CP用反證法證明例5： $x(

24、P(x)Q(x)Þ "xP(x)$xQ(x) Ø("xP(x)$xQ(x) P(假設(shè)前提) Ø(Ø"xP(x)$xQ(x) T E16 "xP(x)Ø$xQ(x) T E9 "xP(x) T I1 Ø$xQ(x) T I2 $x(P(x)Q(x) P P(a)Q(a) ES P(a) US Q(a) T I11 $xQ(x) EG Ø$xQ(x)$xQ(x) T I9 例9.給定謂詞如下：S(x):x是學(xué)生；L(x):x是校領(lǐng)導(dǎo)； G(x):x是好的；T(x):x是老師；P(

25、x): x受過(guò)處分； C(x,y):y表?yè)P(yáng)x用上述謂詞表達(dá)下面各個(gè)命題，并且用謂詞邏輯推理方法證明下面推理的有效性?！皼](méi)有受過(guò)處分的學(xué)生，都受到過(guò)校領(lǐng)導(dǎo)的表?yè)P(yáng)；有些好學(xué)生，僅僅受到老師的表?yè)P(yáng)；所有好學(xué)生，都沒(méi)有受過(guò)處分。所以，有的老師是校領(lǐng)導(dǎo)。”先請(qǐng)同學(xué)將上述各個(gè)命題符號(hào)化，然后推理。"x(S(x)ÙØP(x)®$y(L(y)ÙC(x,y),$x(S(x)ÙG(x)Ù"y(C(x,y)®T(y) ,"x(S(x) ÙG(x) ®ØP(x)Þ$y(T(y)&

26、#217;L(y) $x(S(x)ÙG(x)Ù"y(C(x,y)®T(y) P (S(a)ÙG(a)Ù"y(C(a,y)®T(y) ES S(a)ÙG(a) T I1 "x(S(x) ÙG(x) ®ØP(x) P (S(a) ÙG(a) ®ØP(a) US ØP(a) T I11 S(a) T I1 S(a) Ù ØP(a) T I9 "x(S(x)ÙØP(x)®$y

27、(L(y)ÙC(x,y) P (S(a)ÙØP(a)®$y(L(y)ÙC(a,y) US $y(L(y)ÙC(a,y) T I11 "y(C(a,y)®T(y) T I2 L(b) ÙC(a,b) ES C(a,b)®T(b) US L(b) T I1 C(a,b) T I2 T(b) T I11 T(b)ÙL(b) T I9 $y(T(y)ÙL(y) EG 例10.用推理證明公式：$y"xA(x,y)Þ"x$yA(x,y) $y"xA

28、(x,y) P "xA(x,b) ES A(a,b) US $yA(a,y) EG "x$yA(x,y) UG 補(bǔ)充題1.每個(gè)人的叔叔都是他父親的弟弟。 設(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)是否為閏年的命題:“年號(hào)能被4整除并且不能被100整除的為閏年， 或者年號(hào)能被400整除的也是閏年?！?設(shè) Y(x):x是年號(hào); D(x,y):x可整除y; R(x):x是閏年 "x(Y(x)(D(4,x)ØD(1

29、00,x)R(x)(D(400,x) R(x)此式有些問(wèn)題，因?yàn)樗葍r(jià)于 "x(Y(x)(D(4,x)ØD(100,x)D(400,x)R(x)正確答案：1)"x(Y(x)(D(4,x)ØD(100,x)R(x) "x(Y(x)(D(400,x) R(x) 2）"x(Y(x)(D(4,x)ØD(100,x)D(400,x) R(x)小楊、小劉和小林為高山俱樂(lè)部成員，該俱樂(lè)部的每個(gè)成員是個(gè)滑雪者或登山者。沒(méi)有一個(gè)登山者喜歡雨。而所有滑雪者都喜歡雪。凡是小楊喜歡的，小劉就不喜歡。小楊喜歡雨和雪。試證明該俱樂(lè)部是否有個(gè)是登山者而不是滑雪者的成員。如果有，他是誰(shuí)？設(shè)：M(x):x是高山俱樂(lè)部成員。H(x):x是滑雪者。 D(x):x是登山者。L(x,y):x喜歡y。 a:小楊；b:小劉；c:小林；d:雨；e:雪。命題符號(hào)化為：M(a), M(b), M(c), "x(M(x)( H(x)D(x),