離散數(shù)學(xué)]離散數(shù)學(xué).ppt

《離散數(shù)學(xué)]離散數(shù)學(xué).ppt》由會(huì)員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)]離散數(shù)學(xué).ppt（99頁(yè)珍藏版）》請(qǐng)?jiān)谘b配圖網(wǎng)上搜索。

1、第二章 謂詞邏輯,問(wèn)題的提出：(即命題邏輯的局限性) 在第一章, 一個(gè)原子命題只用一個(gè)字母表示， 而不再對(duì)命題中的句子成分細(xì)分。這樣有一些邏 輯問(wèn)題無(wú)法解決。請(qǐng)看下面的例子。 例1.令：小張是大學(xué)生。 ：小李是大學(xué)生。 從符號(hào)、中不能歸納出他們都是大學(xué)生的共 性。我們希望從所使用的符號(hào)那里帶給我們更多 的信息，比如可以看出他們的共性。這種想法在 第一章是無(wú)法實(shí)現(xiàn)的。,例2.令 ：所有自然數(shù)都是整數(shù)。 ：是自然數(shù)。 ：是整數(shù)。 這是著名的三段論推理，A是大前提，B是小前提， C是結(jié)論。顯然，由和可以推出結(jié)論。這 個(gè)推理是有效的，但是這個(gè)推理在第一章也是無(wú) 法實(shí)現(xiàn)的。 分析：命題與中的謂語(yǔ)是

2、相同的(是大學(xué)生), 只是主語(yǔ)不同。命題、、之間在主語(yǔ)謂語(yǔ) 方面也是有聯(lián)系的，靠這種聯(lián)系才能由、推 出。而從這三個(gè)符號(hào)上看不出此種聯(lián)系。 所以就要另外考慮表示命題的方法。,解決這個(gè)問(wèn)題的方法： 在表示命題時(shí)，既表示出主語(yǔ)，也表示出謂語(yǔ)， 就可以解決上述問(wèn)題。這就提出了謂詞的概念。 令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)

3、I(8),N(8), I(8),符號(hào) S(x)、N(x)、I(x)就是所謂的謂詞。,推理如此實(shí)現(xiàn)：,2-1 基本概念,2-1.1 客體與客體變?cè)?定義：能夠獨(dú)立存在的事物，稱之為客體，也 稱之為個(gè)體。它可以是具體的，也可以是抽象的 事物。通常用小寫(xiě)英文字母a、b、c、...表示。 例如，小張、小李、8、a、沈陽(yáng)、社會(huì)主義等等 都是客體。 定義：用小寫(xiě)英文字母x、y、z...表示任何客 體，則稱這些字母為客體變?cè)?注意：客體變?cè)旧聿皇强腕w。,2-1.2 謂詞 定義：一個(gè)大寫(xiě)英文字母后邊有括號(hào)，括號(hào)內(nèi)是若干個(gè)客體變?cè)靡员硎究腕w的屬性或者客體之間的關(guān)系，稱之為謂詞。如果括號(hào)內(nèi)有n個(gè)客體變?cè)?/p>

4、稱該謂詞為n元謂詞。 例如 S(x):表示x是大學(xué)生。 一元謂詞 G(x,y)：表示 xy。 二元謂詞 B(x,y,z)：表示x在y與z之間。三元謂詞 一般地 P(x1,x2,,xn) 是n元謂詞。,2-1.3 命題函數(shù) 謂詞本身并不是命題，只有謂詞的括號(hào)內(nèi)填入足夠的客體，才變成命題。 例如， a表示小張，b表示小李，則 S(a):小張是大學(xué)生。 S(b):小李是大學(xué)生。 (7,3)表示:。 如果c表示錦州，d表示沈陽(yáng)，e表示山海關(guān)，則B(c,d,e)表示：錦州在沈陽(yáng)與山海關(guān)之間。 這時(shí)S(a)、S(b)、G(7,3)、B(c,d,e)才是命題。,令謂詞S(x):x是大學(xué)生，括號(hào)內(nèi)

5、填入不同的人名， 就得到不同的命題，故謂詞S(x)相當(dāng)于一個(gè)函數(shù)， 稱之為命題函數(shù)。 定義：n元謂詞P(x1,x2,,xn)稱之為簡(jiǎn)單命題函數(shù)。 規(guī)定：當(dāng)命題函數(shù)P(x1,x2,,xn)中 n=0 時(shí)，即0 元謂詞，表示不含有客體變?cè)闹^詞，它本身就是 一個(gè)命題變?cè)?定義：將若干個(gè)簡(jiǎn)單命題函數(shù)用邏輯聯(lián)結(jié)詞聯(lián)結(jié)起 來(lái)，構(gòu)成的表達(dá)式，稱之為復(fù)合命題函數(shù)。簡(jiǎn)單命 題函數(shù)與復(fù)合命題函數(shù)統(tǒng)稱為命題函數(shù)。,例如 給定簡(jiǎn)單命題函數(shù)： A(x)：x身體好， B(x)：x學(xué)習(xí)好， C(x)：x工作好， 復(fù)合命題函數(shù) A(x)(B(x)C(x)) 表示如果x身體不好，則x的學(xué)習(xí)與工作都不會(huì)好。,2-1.4 論域

6、(個(gè)體域) 定義：在命題函數(shù)中命題變?cè)娜≈捣秶Q之為論域，也稱之為個(gè)體域。 例如 S(x):x是大學(xué)生，論域是:人類。 G(x,y)：xy， 論域是:實(shí)數(shù)。 論域是一個(gè)集合。 定義：由所有客體構(gòu)成的論域，稱之為全總個(gè)體域。它是個(gè)“最大”的論域。 約定:對(duì)于一個(gè)命題函數(shù)，如果沒(méi)有給定論域，則假定該論域是全總個(gè)體域。,2-1.5 量詞 例如：有些人是大學(xué)生。 所有事物都是發(fā)展變化的。 “有些”,“所有的”,就是對(duì)客體量化的詞。 定義：在命題中表示對(duì)客體數(shù)量化的詞，稱之為量詞。 定義了兩種量詞： (1).存在量詞：記作，表示“有些”、“一些”、 “某些”、“至少一個(gè)”等。 (2).全稱量詞

7、：記作，表示“每個(gè)”、“任何 一個(gè)”、“一切”、“所有的”、“凡是”、“任意 的”等。,定義：量詞后邊要有一個(gè)客體變?cè)该鲗?duì)哪個(gè)客體變?cè)炕?，稱此客體變?cè)橇吭~后的指導(dǎo)變?cè)?例如 x(讀作“任意x”)，x(讀作“存在x”)，其中的x就是量詞后的指導(dǎo)變?cè)?例題.所有的自然數(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

8、,y))),2-2 謂詞公式及命題符號(hào)化,命題邏輯中有命題公式，類似地，在謂詞邏輯 中，要研究謂詞公式。 2-2.1 客體函數(shù) 有些命題中，可能有若干個(gè)客體，其中有些客體 之間有函數(shù)關(guān)系，例如 例題1. 如果x是奇數(shù)，則2x是偶數(shù)。 其中客體x與客體2x之間就有函數(shù)關(guān)系，可以設(shè) 客體函數(shù) g(x)=2x， 謂詞 O(x)：x是奇數(shù)， E(x)：x是偶數(shù)， 則此命題可以表示為： 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)=

9、x+y ，此命題可以表示為: xy((O(x)O(y))E(h(x,y)) 像上述的g(x)、f(x)、h(x,y)就是客體函數(shù)，一般地用小寫(xiě)的英文字母f,g,h.表示客體函數(shù)。 注意:客體函數(shù)與謂詞是不同的，不可混淆.,要注意區(qū)分客體函數(shù)與謂詞間的區(qū)別： 設(shè)例題1的論域是自然數(shù)集合N。 客體函數(shù)中的客體變?cè)每腕w帶入后的結(jié)果依然是個(gè)客體(3N,g(3)=6，所以g(3)N)。 謂詞中的客體變?cè)么_定的客體帶入后就變成了命題，其真值為或者為(3N, O()是個(gè)命題,真值為T(mén))。 把它們都看成“映射”的話，則 客體函數(shù)是論域到論域的映射，g:NN，如果 指定的客體aN，則g(a)N。 而謂詞是從

10、論域到T,F的映射，即謂詞E(x)可 以看成映射E:NT,F，如果指定客體aN，則 E(a)的真值T,F。,2-2.2 原子謂詞公式 定義：稱n元謂詞P(x1,x2,...,xn)為原子謂詞公式。 例如 P、Q(x) 、 A(x,f(x))、B(x,y,a) 都是原子謂詞公式。,2-2.3 謂詞合式公式(WFF) (Well Formed formulas) 定義：謂詞合式公式遞歸定義如下： 1.原子謂詞公式是合式公式。 2.如果A是合式公式，則A也是合式公式。 3.如果A、B是合式公式，則(AB)、(AB)、(AB)、(AB)都是合式公式。 4.如果A是合式公式，x是中的任何客體變?cè)?，則x和

11、x也是合式公式。 5.只有有限次地按規(guī)則(1)至(4)求得的公式才是合式公式。 謂詞合式公式也叫謂詞公式，簡(jiǎn)稱公式。,下面都是合式公式： P、(PQ)、(Q(x)P)、x(A(x)B(x))、xC(x) 而下面都不是合式公式： xyP(x) 、P(x)Q(x)x 為了方便，最外層括號(hào)可以省略，但是若量詞后邊有括號(hào)，則此括號(hào)不能省。 注意：公式x(A(x)B(x))中x后邊的括號(hào)不是最外層括號(hào)，所以不可以省略。,2-2.4 量詞的作用域(轄域) 定義：在謂詞公式中，量詞的作用范圍稱之為量詞的作用域，也叫量詞的轄域。 例如 xA(x)中x的轄域?yàn)锳(x). x((P(x)Q(x))yR(x,y))

12、中 x的轄域是((P(x)Q(x))yR(x,y)) y的轄域?yàn)镽(x,y)。 xyz(A(x,y)B(x,y,z))C(t),一般地， 如果量詞后邊只是一個(gè)原子謂詞公式時(shí)，該量詞的轄域就是此原子謂詞公式。 如果量詞后邊是括號(hào)，則此括號(hào)所表示的區(qū)域就是該量詞的轄域。 如果多個(gè)量詞緊挨著出現(xiàn)，則后邊的量詞及其轄域就是前邊量詞的轄域。,2-2.5 自由變?cè)c約束變?cè)?在謂詞公式中的客體變?cè)梢苑殖蓛煞N， 一種是受到量詞約束的，一種是不受量詞 約束的。請(qǐng)看下面公式： x(F(x,y)yP(y))Q(z) (x,y)中的x在x的轄域內(nèi)，受到x的 約束，而其中的y不受x的約束。 P(y)中的y在y的轄

13、域內(nèi)，受y的約束。 Q(z)中的z不受量詞約束。,定義：如果客體變?cè)獂在x或者x的轄域內(nèi)，則稱x在此轄域內(nèi)約束出現(xiàn)，并稱x在此轄域內(nèi)是約束變?cè)?。否則x是自由出現(xiàn)，并稱x是自由變?cè)?上例中 x(F(x,y)yP(y))Q(z) F(x,y)中的x和P(y)中的y是約束變?cè)?而F(x,y)中的y和Q(z)中的z是自由變?cè)?對(duì)約束變?cè)妥杂勺冊(cè)腥缦聨c(diǎn)說(shuō)明： (1).對(duì)約束變?cè)檬裁捶?hào)表示無(wú)關(guān)緊要。就是說(shuō)xA(x)與yA(y)是一樣的。這類似于計(jì)算積分與積分變?cè)獰o(wú)關(guān)，即積分f(x)dx 與f(y)dy 相同。 (2).一個(gè)謂詞公式如果無(wú)自由變?cè)?，它就表示一個(gè)命題。 例如 A(x)表示x是個(gè)

14、大學(xué)生。xA(x)或者xA(x)就是個(gè)命題了，因?yàn)樗鼈兎謩e表示命題“有些人是大學(xué)生”和“所有人都是大學(xué)生”。,(3).一個(gè)n元謂詞P(x1,x2,,xn)，若在前邊添加k個(gè)量詞，使其中的 k個(gè)客體變?cè)兂杉s束變?cè)?，則此 n元謂詞就變成了n-k元謂詞。 例如P(x,y,z)表示x+y=z，假設(shè)論域是整數(shù)集。xyP(x,y,z)表示“任意給定的整數(shù)x，都可以找到整數(shù)y，使得x+y=z” 。 如果令 z=1，則xyP(x,y,1)就變成了命題“任意給定的整數(shù)x，都可以找到整數(shù)y，使得x+y=1”,。 可見(jiàn)每當(dāng)給z指定個(gè)整數(shù)a后，xyP(x,y,a)就變成了一個(gè)命題。所以謂詞公式xyP(x,y,z)就

15、相當(dāng)于只含有客體變?cè)?z的一元謂詞了。,在一個(gè)謂詞公式中，如果某個(gè)客體變?cè)纫约s束變?cè)问匠霈F(xiàn)，又以自由變?cè)问匠霈F(xiàn)，就容易產(chǎn)生混淆。為了避免此現(xiàn)象發(fā)生，可以對(duì)客體變?cè)拿Q。 如 x(F(x,y)yP(y))Q(z) 約束變?cè)母拿?guī)則： (1).對(duì)約束變?cè)梢愿拿Q，改名的范圍是：量詞后的指導(dǎo)變?cè)约霸摿吭~的轄域內(nèi)此客體變?cè)霈F(xiàn)的各處同時(shí)換名。 (2).改名后用的客體變?cè)Q，不能與該量詞的轄域內(nèi)的其它變?cè)Q相同。,例如x(P(x)Q(x,y))(R(x)A(x)) 此式中的x 就是以兩種形式出現(xiàn)?？梢詫?duì)x改名成 z(P(z)Q(z,y))(R(x)A(x)) 對(duì)自由變?cè)部梢該Q名字

16、，此換名叫代入。 對(duì)自由變?cè)拇胍?guī)則： (1).對(duì)謂詞公式中的自由變?cè)梢宰鞔?。代入時(shí)需要對(duì)公式中出現(xiàn)該變?cè)拿恳惶帲瑫r(shí)作代入。 (2).代入后的變?cè)Q要與公式中的其它變?cè)Q不同 上例也可以對(duì)自由變?cè)獂作代入，改成 x(P(x)Q(x,y))(R(z)A(z)),2-2.6 命題的符號(hào)化 在謂詞演算中，命題的符號(hào)化比較復(fù)雜，命題的符號(hào)表達(dá)式與論域有關(guān)系。例如 1.每個(gè)自然數(shù)都是整數(shù)。 (1).如果論域是自然數(shù)集合N，令 I(x)：x是整數(shù)，則命題的表達(dá)式為 xI(x) (2).如果論域擴(kuò)大為全總個(gè)體域時(shí)，上述表達(dá)式xI(x)表示“所有客體都是整數(shù)”，顯然這是假的命題，此表達(dá)式已經(jīng)不能

17、表達(dá)原命題了。因此需要添加謂詞N(x)：x是自然數(shù)，用于表明x的特性，于是命題的符號(hào)表達(dá)式為 x(N(x)I(x)),2.有些大學(xué)生吸煙。 (1).如果論域是大學(xué)生集合S，令A(yù)(x)：x吸煙，則命題的表達(dá)式為 xA(x) (2).如果論域擴(kuò)大為全總個(gè)體域時(shí)，上述表達(dá)式xA(x)表示“有些客體吸煙”，就不是表示此命題了，故需要添加謂詞 S(x)：x是大學(xué)生，用于表明x的特性，于是命題的表達(dá)式為 x(S(x)A(x)),從上述兩個(gè)例子可以看出，命題的符號(hào)表達(dá)式與論域有關(guān)。當(dāng)論域擴(kuò)大時(shí)，需要添加用來(lái)表示客體特性的謂詞，稱此謂詞為特性謂詞。特性謂詞往往就是給定命題中量詞后邊的那個(gè)名詞。如上面兩個(gè)例子中

18、的“所有自然數(shù)”、“有些大學(xué)生”。 如何添加特性謂詞，這是個(gè)十分重要的問(wèn)題，這與前邊的量詞有關(guān)。 特性謂詞的添加方法如下： 如果前邊是全稱量詞，特性謂詞后邊是蘊(yùn)含聯(lián)結(jié)詞“”；如果前邊是存在量詞，特性謂詞后邊是合取聯(lián)結(jié)詞“”。,為什么必須這樣添加特性謂詞？ 分析一下特性謂詞和原謂詞所表示的概念之間的關(guān)系，得出下面的圖，從此圖可以得出如此添加特性謂詞的正確性。 令N:自然數(shù)集合，I:整數(shù)集合， S:大學(xué)生集合，A:煙民的集合。,I包含N x(N(x)I(x)),吸煙大學(xué)生是S與A的交集 x(S(x)A(x)),3.所有大學(xué)生都喜歡一些歌星。 令S(x)：x是大學(xué)生，X(x)：x是歌星， L(x

19、,y)：x喜歡y。 則命題的表達(dá)式為 x(S(x)y(X(y)L(x,y))) 4.沒(méi)有不犯錯(cuò)誤的人。 此話就是“沒(méi)有人不犯錯(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ō)謊話，那么他所說(shuō)的每句話沒(méi)有一句是可以相信的。 令A(yù)(x)：x是人，B(x,y)：y是x說(shuō)的話， C(x):x是謊話，D(x)：x是可以相信的 命題的表達(dá)式為:

20、x(A(x)(y(B(x,y)C(y))z(B(x,z)D(z))) 或者 x(A(x)y((B(x,y)C(y))D(y))) 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)))),,有一個(gè)后繼數(shù),后繼數(shù)的唯一性,,,下面請(qǐng)同學(xué)們自己做練習(xí)第60頁(yè)(2),練習(xí)P60(2),a) x(J(x)L(x)) b) x(L(x)S(x)) c) x(J(x)O(x)V(x)) d) J(j)O(j)V(j) e) x(L(x)J(x)) 或

21、者 x(L(x)J(x)) f) x(S(x)L(x)C(x)) g) 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(L(y)A(x,y))),小結(jié) 1.命題的符號(hào)表達(dá)式形式與論域有關(guān)系。 論域擴(kuò)大需要用特性謂詞對(duì)客體進(jìn)行說(shuō)明.注意如何添加特性謂詞(即要注意特性謂詞后邊是什么聯(lián)結(jié)詞)。 2.如果量詞前有否定符號(hào)，如“沒(méi)有...”“不是所有的...”等，可以按照字面直譯。如“x” “x...” 3.命題

22、的符號(hào)表達(dá)式中所有客體變?cè)仨毝际羌s束變?cè)?，才表示命題。有時(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))),作業(yè) 60頁(yè) (2) 62頁(yè) (2), (3) b), c), (5) b) (6) 65頁(yè) (4) b) (5) a),2-3謂詞演算的等價(jià)式與蘊(yùn)涵式,在命題邏輯中，我們是通過(guò)對(duì)公式的命題變?cè)x值來(lái)討論永真式、永真蘊(yùn)含式及等價(jià)公式的。

23、在謂詞演算中，也要討論一些重要的謂詞公式。但是由于謂詞公式中可能有命題變?cè)?、客體變?cè)?duì)命題變?cè)x值比較容易，因?yàn)橹挥袃蓚€(gè)值可賦。而對(duì)客體變?cè)髦概蓞s不那么簡(jiǎn)單，因?yàn)檎撚蛑械目腕w可能有無(wú)限個(gè)。另外謂詞公式的真值還與論域有關(guān)。,2-3.1 對(duì)謂詞公式賦值,定義：若將給定的謂詞公式中的命題變?cè)?，用確定的命題代替，對(duì)公式中的客體變?cè)谜撚蛑械目腕w代替，這個(gè)過(guò)程就稱之為對(duì)謂詞公式作指派，或者稱之 為對(duì)謂詞公式賦值。 例如公式 PN(x)，N(x)：x是自然數(shù)，論域?yàn)閷?shí)數(shù)集合R， 令P：21，x=4 時(shí)，此公式變成PN(4)，它的真值就是“真”。,2-3.2 謂詞公式的永真式定義,定義：給定謂詞公式A，

24、E是其論域，如果不論對(duì)公式A作任何賦值，都使得A的真值為真，則稱公式A在論域E上是永真式。如果不論對(duì)什么論域E，都使得公式A為永真式，則稱A為永真式。 例如，I(x)：x是整數(shù)，論域E為自然數(shù)集合，公式I(x)在E上就是永真式。 而公式 I(x)I(x)就是與論域無(wú)關(guān)的永真式。,2-3.3 謂詞公式的等價(jià)公式定義,定義：給定謂詞公式A、B，E是它們的論域，如果不論對(duì)公式A、B作任何賦值，都使得A與B的真值相同(或者說(shuō)AB是永真式)，則稱公式A與B在論域E上是等價(jià)的。如果不論對(duì)什么論域E，都使得公式A與B等價(jià)，則稱A與B等價(jià)，記作AB。 例如，I(x)：表示x是整數(shù)，N(x)：表示x是自然數(shù)，假

25、設(shè)論域E是自然數(shù)集合，公式I(x)與N(x)在E上是等價(jià)的。 而公式N(x)I(x) 與N(x)I(x)就是與論域無(wú)關(guān)的等價(jià)的公式，即 N(x)I(x)N(x)I(x)。,2-3.4 謂詞公式的永真蘊(yùn)含式定義,定義：給定謂詞公式A、B，E是它們的論域，如果不論對(duì)公式A、B作任何賦值，都使得AB為永真式，則稱在論域E上公式A永真蘊(yùn)含B。如果不論對(duì)什么論域E，都使得公式AB為永真式，則稱A永真蘊(yùn)含B，記作AB。 例如，G(x)：表示x大于5，N(x)：表示x是自然數(shù)，論域E=-1,-2,6,7,8,9,....， 在E上公式G(x)N(x)是永真式。 而公式(G(x)N(x))N(x)就是與論域無(wú)

26、關(guān)的永真式，所以(G(x)N(x))N(x)。,2-3.5. 重要公式,下面討論重要的謂詞等價(jià)公式和永真蘊(yùn)含式。 一.由命題公式推廣出的公式 因一個(gè)不含自由變?cè)闹^詞公式本身如xA(x)、xB(x) 就是命題。一個(gè)含有n個(gè)自由變?cè)闹^詞公式，賦予論域 中的n個(gè)指定客體后就變成命題(例如S(a)、G(3,1)等)。 因此可以把此公式看成一個(gè)命題變?cè)?。所以在命題演算 的永真式中，將其中的同一個(gè)命題變?cè)?，用同一個(gè)謂詞 公式代替，所得到的公式也是永真式。這樣就可以將命 題演算中的等價(jià)公式和永真蘊(yùn)含式推廣到謂詞演算中使 用。例如 A(x)A(x)B(x) PPQ x(A(x)B(x))x(A(

27、x)B(x)) PQPQ (xA(x)xB(x))xA(x)xB(x) 摩根定律,二.帶量詞的公式在論域內(nèi)的展開(kāi)式,先看一個(gè)例子，令A(yù)(x)：表示x是整數(shù)，B(x)：表示x是奇數(shù)，設(shè)論域是1,2,3,4,5，謂詞公式xA(x)表示論域內(nèi)所有的客體都是整數(shù)，顯然公式xA(x)的真值為真，因?yàn)锳(1)、A(2)、A(3)、A(4)、A(5)都為真，于是有 xA(x)A(1)A(2)A(3)A(4)A(5) 類似地，謂詞公式xB(x)表示論域內(nèi)有些客體是奇數(shù)，顯然公式xB(x)的真值也為真，因?yàn)锽(1)、B(3)、B(5)的真值為真，于是有 xB(x)B(1)B(2)B(3)B(4)B(5) 一般

28、地，設(shè)論域?yàn)閍1,a2,....,an，則 1. xA(x)A(a1)A(a2)......A(an) 2. xB(x)B(a1)B(a2)......B(an),三.量詞否定公式,我們還是先用一個(gè)例子說(shuō)明這個(gè)問(wèn)題。令 (x)表示x是優(yōu)等生，論域是某班級(jí)的學(xué)生集合。 xA(x)表示：不是所有人都是優(yōu)等生。 xA(x)表示：有些人不是優(yōu)等生。 xA(x)表示：沒(méi)有人是優(yōu)等生。 xA(x)表示：所有人都不是優(yōu)等生。 從這個(gè)例子可以看出 “不是所有人都是優(yōu)等生?！迸c“有些人不是優(yōu)等生?！笔堑葍r(jià)的。 “沒(méi)有人是優(yōu)等生?！迸c“所有人都不是優(yōu)等生?！笔堑葍r(jià)的。于是有：,1. xA(x)xA(x) 2. x

29、A(x)xA(x) 對(duì)這兩個(gè)公式可以證明如下： 證明：設(shè)論域?yàn)閍1,a2,....,an，則 xA(x)(A(a1)A(a2)...A(an)) A(a1)A(a2)...A(an)xA(x) 類似可以證明另一個(gè)公式。 從這兩個(gè)公式，可以總結(jié)出如下規(guī)律：將量詞前的“”移到量詞的后邊，或者將量詞后的“”移到量詞的前邊時(shí)，量詞也隨著改變，如果原來(lái)是全稱量詞改成存在量詞，如果原來(lái)是存在量詞改成全稱量詞。所以我們也把這兩個(gè)公式稱為量詞轉(zhuǎn)換公式。,四.量詞轄域的擴(kuò)充公式,如果是個(gè)不含客體變?cè)獂的謂詞公式，且不在x和x的轄域內(nèi)，可以將放入x和x的轄域內(nèi)。即得如下公式： 1. xA(x)Bx(A(x)B)

30、 2. xA(x)Bx(A(x)B) 3. xA(x)Bx(A(x)B) 4. xA(x)Bx((x)B) 5. BxA(x)x(BA(x)) 6. BxA(x)x(BA(x)) 7. xA(x)Bx(A(x)B) 8. xA(x)Bx(A(x)B),上述公式我們只證明三個(gè)。 證明：設(shè)論域?yàn)閍1,a2,....,an， xA(x)B(A(a1)A(a2)...A(an))B (A(a1)B)(A(a2)B)...(A(an)B) x((x)) BxA(x)BxA(x)x(BA(x)) x(BA(x)) xA(x)BxA(x)BxA(x)B x(A(x)B)x(A(x)B) 在使用

31、公式7.、8.時(shí)，要特別注意，量詞的轄域擴(kuò)充后，量詞發(fā)生了變化。,五.量詞分配公式,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)) 證明：設(shè)論域?yàn)閍1,a2,....,an， x(A(x)B(x)) (A(a1)B(a1))(A(a2)B(a2)) (A(an)B(an)) (A(a1)A(a2)...A(an)) (B(a1)B(a2)...B(an)) xA(x)xB(x),注意公式3.和4.不是等價(jià)公式，而是永 真蘊(yùn)含式。 例如公式3

32、.由xA(x)xB(x)不能推出x(A(x)B(x))， 我們可以舉一個(gè)反例，設(shè)A(x)和B(x)分別表示“x是奇數(shù)”和“x是偶數(shù)”，顯然命題xA(x)xB(x)為真。而x(A(x)B(x))是表示命題“存在一些數(shù)既是奇數(shù)，也是偶數(shù)”，顯然不為真。 所以說(shuō)由xA(x)xB(x)不能推出 x(A(x)B(x)).,證明公式3. x(A(x)B(x))xA(x)xB(x) 證明：假設(shè)前件x(A(x)B(x))為真， 則論域中至少有一個(gè)客體a，使得 A(a)B(a)為真，于是A(a)和B(a)都為 真，所以有xA(x)以及xB(x)為真，進(jìn)而得xA(x)xB(x)為真。于是有 x(A(x)B(x))

33、xA(x)xB(x),下面利用公式3.證明公式4.。 證明：因?yàn)楣?.中的A(x)和B(x)是任意的謂詞公式，不妨用A(x)和B(x)分別代替公式3.中的A(x)和B(x)得 x(A(x)B(x))xA(x)xB(x) x(A(x)B(x))xA(x)xB(x) x(A(x)B(x))(xA(x)xB(x)) 應(yīng)用公式 PQQP 得 xA(x)xB(x)x(A(x)B(x)) 公式4.得證。 在使用公式4.的時(shí)候，特別要注意蘊(yùn)含式的方向，不要搞錯(cuò)。,六其它公式,1. x(A(x)B(x))xA(x)xB(x) 2. xA(x)xB(x)x(A(x)B(x)) 證明1. xA(x)xB(x)

34、 xA(x)xB(x) xA(x)xB(x) x(A(x)B(x)) x(A(x)B(x)) 證明2. xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) x(A(x)B(x)) x(A(x)B(x)),七兩個(gè)量詞的公式,在A(x,y)前有兩個(gè)量詞，如果兩個(gè)量詞是相同的，它們的次序是無(wú)關(guān)緊要，但是如果是不同的，它們的次序就不可以隨便交換。例如設(shè) A(x,y)表示“x+y=0”,論域?yàn)椋簩?shí)數(shù)集合， xyA(x,y)表示“對(duì)于任意給定的一個(gè)實(shí)數(shù)x,可以找到一個(gè)y,使得x+y=0”,這是一個(gè)為“真”的命題。而交換量詞后 yxA(x,y) 表示“存在一個(gè)實(shí)數(shù)y,與任意給定的一個(gè)實(shí)數(shù)x

35、之和都等于0”,這是一個(gè)為“假”的命題。,有如下一些公式： 1. xyA(x,y)yxA(x,y) 2. xyA(x,y)yxA(x,y) 3. yxA(x,y)xyA(x,y) 4. xyA(x,y)xyA(x,y) 5. yxA(x,y)xyA(x,y) 6. xyA(x,y)yxA(x,y) 7. yxA(x,y)xyA(x,y) 8. xyA(x,y)yxA(x,y) 注意：下面式子不成立 xyA(x,y)yxA(x,y),,,為了便于記憶，用下面圖形表示上面八個(gè)公式。,實(shí)際上，根據(jù)具有傳遞性，還可以派生出一些公式。下面我們只證明一個(gè)等價(jià)公式。用謂詞邏輯推理方法很容易證明上面那些永真蘊(yùn)

36、涵式，在此就不證明了。下面證明公式1.。 證明：設(shè)論域?yàn)閍1,a2,....,an，則 xyA(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,a1)) (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) yxA(x,y),本節(jié)小結(jié)： 熟練掌握謂詞等價(jià)公式和永真蘊(yùn)

37、涵式的證明方法及應(yīng)用。 作業(yè)題： P66 (3) b) P71 (2) d), (6) 面作做個(gè)練習(xí)P71(1) c),練習(xí)P71(1) c) .論域D=1,2 a=1 b=2 f(1)=2 f(2)=1 P(1,1)=T P(1,2)=T P(2 ,1)=F P(2,2)=F 求xy(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

38、(2)))) ((P(1,1) P(2,2)) (P(1,2) P(2,1))) ((P(2,1) P(1,2)) (P(2,2) P(1,1))) ((T F ) (T F))((F T) (F T)) (F F)(T T) FT F,2-4前束范式,與命題公式的范式類似，謂詞公式也有規(guī)范形式。這 里主要介紹前束范式--所有量詞都在公式前邊約束變?cè)?1.前束范式定義： 如果一個(gè)謂詞公式符合下面條件，它就是前束范式： 所有量詞前面都沒(méi)有聯(lián)接詞； 所有量詞都在公式的左面； 所有量詞的轄域都延伸到公式的末尾。 例如 yxz(A(x)(B(x,y)C(x,y,z))) x((x)B(x)

39、) 就是前束范式，而 xA(x)yB(y) xy(A(x)(B(x,y)zC(z))) xA(x)B(x) 這三個(gè)就不是前束范式。,2.前束范式的寫(xiě)法 給定一個(gè)帶有量詞的謂詞公式， 1)消去公式中的聯(lián)接詞和(為了便于量詞轄域的擴(kuò)充)； 2)如果量詞前有“”，則用量詞否定公式將“”后移。再用摩根定律或求公式的否定公式，將“”后移到原子謂詞公式之前。 3)用約束變?cè)母拿?guī)則或自由變?cè)拇胍?guī)則對(duì)變?cè)獡Q名(為量詞轄域擴(kuò)充作準(zhǔn)備) 4)用量詞轄域擴(kuò)充公式提取量詞，使之成為前束范式形式。,例1. xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) xA(x)yB(y) (換元)

40、x(A(x)yB(y)) (量詞轄域擴(kuò)充) xy(A(x)B(y)) 另一個(gè)方法：xA(x)xB(x) xA(x)xB(x) xA(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))(xP(x)Q(x)) (量詞轉(zhuǎn)換) x(P(x)R(x))(xP(x)Q(x)) (后移) x(P(x)R(x))(yP(y)Q(z)) (換變?cè)? x(P(x)R(x))y(P(y)Q(z)) (擴(kuò)量詞轄域) xy((P(x)R(x))(P(y)Q(z)))(擴(kuò)量詞轄域)

41、3.前束析取范式與前束合取范式： 前束析取范式:前束范式中量詞后的括號(hào)內(nèi)是析取范式形式。 前束合取范式:前束范式中量詞后的括號(hào)內(nèi)是合取范式形式。 上例的前束析取范式為: xy(P(x)R(x)(P(y)Q(z))) 上例的前束合取范式為: xy((P(x)R(x)P(y))(P(x)R(x)Q(z))),本節(jié)掌握前束范式的寫(xiě)法。 作業(yè) P75 (1)b) (2)c),2-5 謂詞演算的推理理論,推理方法： 直接推理、條件論證、反證法 所用公式：43頁(yè)和70頁(yè)的I1I19，E1E33 推理規(guī)則：P、T、CP、US、ES、EG、UG 后四個(gè)規(guī)則，是處理量詞的，因?yàn)橥评頃r(shí)要使用不含量詞的命題公

42、式，所以要去掉量詞，如果結(jié)論有量詞，還要添加量詞。 下面介紹四個(gè)新規(guī)則：,一.全稱特指規(guī)則 US (Universal Specialization) 形式： xA(x)A(c) (其中c是論域內(nèi)指定客體) 含義：如果xA(x)為真，則在論域內(nèi)任 何指定客體c，都使得A(c)為真。 作用：去掉全稱量詞。 要求：c不是A(x)中的符號(hào)。,二.存在特指規(guī)則ES(Existential Specialization) 形式： xA(x)A(c) (其中c是論域內(nèi)指定客體) 含義：如果xA(x)為真，則在論域內(nèi)指定客體c， 都使得A(c)為真。 作用：去掉存在量詞。 要求： c不是A(x

43、)中的符號(hào)。 用ES指定的客體c不應(yīng)該是在此之前用US規(guī)則或者用ES規(guī)則所指定的客體c(即本次用ES特指客體c，不應(yīng)該是以前特指的客體)。 請(qǐng)看下面兩個(gè)例子：,例1. 令A(yù)(x)表示x是自然數(shù)，B(x)表示x是整數(shù)。 x(A(x)B(x)) P A(c)B(c) US 如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,三.存在推廣規(guī)則 EG (Existential Generalization) 形式： A(c)xA(x) (其中c是論域內(nèi)指定客體) 含義

44、：如果在論域內(nèi)指定客體c使得 A(c)為真，則xA(x)為真。 作用：添加存在量詞。 要求：x不是A(c)中的符號(hào)。,四.全稱推廣規(guī)則UG (Universal Generalization) 形式： A(c)xA(x) (其中c是論域內(nèi)任何指定客體) 含義：如果在論域內(nèi)任何指定客體c都使 得A(c)為真，則xA(x)為真。 作用：添加全稱量詞。 要求：x不是A(c)中的符號(hào)。 c一定是任意的客體，否則不可全 稱推廣。,例1 所有金屬都導(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

45、(x)C(x))P M(a)C(a) US M(a) P C(a) T I11,例2. 所有自然數(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 ,例2中，如果按下面方法推理，是否正確？ x(A(x)B(x))， xA(x) xB(x) x(A(x)B(x)) P A(c)B(c) US xA(x) P A(c) ES B(C

46、) T I11 xB(x) EG 問(wèn)題在哪里？,例3 不認(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(C(x)A(x)),x(A(x)B(x))，x(C(x)B(x)), x(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)

47、T E1 C(c)A(c) T I9 x(C(x)A(x)) EG ,例4 一些病人喜歡所有醫(yī)生。任何病人都不喜歡庸醫(yī)。所以沒(méi)有醫(yī)生是庸醫(yī)。 設(shè): P(x):x是病人, D(x):x是醫(yī)生, Q(x):x是庸醫(yī), L(x,y): x喜歡y. 符號(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)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

48、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 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,課堂練習(xí)P79(1)d)改成： x(A(x)B(x)),x(B(x)C(x)),xC(x)x

49、(A(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 (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) x(A(x) EG (8),例5 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

50、xP(x)xQ(x) CP,用反證法證明例5： x(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,用推理證明公式： yxA(x,y)xyA(x,y) yxA(x,y) P xA(x,b) ES A(a,b) US yA(a,y) EG xyA

51、(x,y) UG 作業(yè)：79頁(yè) c)d) 、 推理時(shí)的注意事項(xiàng)：,推理時(shí)注意事項(xiàng)：,1.注意使用ES、US、EG、UG的限制條件。 2.對(duì)于同一個(gè)客體變?cè)?，既有帶也有帶的前提，去量詞時(shí)，應(yīng)先去后去，這樣才可以特指同一個(gè)客體 c. 3.去量詞時(shí)，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無(wú)任何符號(hào)，它的轄域作用到公式末尾。 下面的作法是錯(cuò)誤的： 正確作法是： xP(x)yQ(y) P xP(x)yQ(y) P xP(x)Q(b) ES (2)xP(x)yQ(y) T(1) E (3)P(a)Q(b) US(2) (3) xP(x)yQ(y) T(2) E (4

52、) xy(P(x)Q(y)) T(3) E (5) y(P(a)Q(y)) ES(4) 實(shí)際上x(chóng)的轄域擴(kuò) (6) P(a)Q(b)) ES(4) 充后量詞改成為x (7) P(a)Q(b) T(5)E,,下面的作法是錯(cuò)誤的： 正確作法是： xP(x) P xP(x) P P(c) US (2) xP(x) T(1)E 實(shí)際上中不是x而是x (3) P(c) ES (2) xyP(x,y) P xyP(x,y) P xP(x,c) ES (2) yP(a,y) US(1) 令P(x,y):y是x的生母，顯然是個(gè)假命題. 另外X是公式A的子

53、公式，且XY,如果用Y替換A中X而得 到B，那么不一定有AB。例如PQP,而(PQ)P 是不成立的。US和ES規(guī)則都是蘊(yùn)涵式，所以不可對(duì)一個(gè) 子公式用這些規(guī)則。 4.添加量詞時(shí)，也要加在公式的最左邊，(即新加的量詞前也無(wú)任何符號(hào)??！)且其轄域作用到公式的末尾。,第二章 小結(jié),本章重點(diǎn)掌握內(nèi)容： 1.各基本概念清楚。 2.會(huì)命題符號(hào)化。 3.熟練掌握等價(jià)公式和永真蘊(yùn)涵式。 4.會(huì)寫(xiě)前束范式。 5.熟練掌握謂詞邏輯的三種推理方法。,第二章 習(xí)題課,一. 命題符號(hào)化 60頁(yè)(2) a) x(J(x)L(x)) b) x(L(x)S(x)) c) x(J(x)O(x)V(x)) d) J(j)O

54、(j)V(j) e) x(L(x)J(x)) 或者 x(L(x)J(x)) f) x(S(x)L(x)C(x)) g) 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(L(y)A(x,y))),62頁(yè)(2) xy((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(

55、y)G(y,x))) c)設(shè)R(x):x是實(shí)數(shù)，G(x,y):xy f(x,y)=x+y g(x,y)=xy xyz(R(x)R(y)R(z)G(f(x,y),g(x,z))) 或者 xyz(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)) (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.

56、每個(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(100,x))R(x))(D(400,x) R(x)))),66頁(yè)(3)b)P:21,Q(x):x3, R(x):x5,a:5,-2,3,6 x(PQ(x))R(a)(PxQ(

57、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名 x(P(x)(R(x)Q(x))) xR(x)zS(x,z) y(P(y)(R(y)Q(y))) tR(t)uS(x,u) (5)a)對(duì)自由變?cè)?(yA(x,y)xB(x,z)) xzC(x,y,z) (yA(u,y)xB(x,v)) xzC(x,w,z),72頁(yè)(2)d)論域?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 xy(P(x)Q(x,y)) y(P(1)Q(1,y))y(P(

58、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)(FT))((TF)(TF)) (FF)(FF)F,(6)判斷下面推證是否正確。 x(A(x)B(x)) x(A(x)B(x)) x(A(x)B(x) x(A(x)B(x)) (xA(x)xB(x)) xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) 第步錯(cuò)，由到用的是公式： x(A(x)B(x))(xA(x)xB(x)) 無(wú)此公式，而是 x(A(x)B(x)) xA(x)xB(x)，應(yīng)將中的換成 即：,x(A(x)B(x)) x(A(x)B

59、(x)) x(A(x)B(x) x(A(x)B(x)) (xA(x)xB(x)) xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) 因?yàn)橛晒紼18 PQQP x(A(x)B(x)) xA(x)xB(x) ， P Q 得 (xA(x)xB(x))x(A(x)B(x)),75頁(yè)(1)b)x(yP(x,y)(zQ(z)R(x))) x(yP(x,y)(zQ(z)R(x))) x(yP(x,y)(zQ(z)R(x))) x(yP(x,y) z(Q(z)R(x))) xyz(P(x,y)(Q(z)R(x))) (2)c)xP(x)x(zQ(x,z)zR(x,y,z)) xP(x

60、)x(zQ(x,z)zR(x,y,z)) xP(x)x(zQ(x,z)zR(x,y,z)) xP(x)u(zQ(u,z)tR(u,y,t)) xuzt(P(x)(Q(u,z)R(u,y,t))) xuzt(P(x)Q(u,z)R(u,y,t)) 此式既是前束析取范式，也是前束合取范式。,79頁(yè)(2)a)用CP規(guī)則證明 x(P(x)Q(x) xP(x)x Q(x) 因?yàn)閤P(x)x Q(x) xP(x)x Q(x) xP(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 xP(x

61、)x Q(x) CP,(3)a)所有有理數(shù)是實(shí)數(shù)，某些有理數(shù)是整數(shù)，因此某些實(shí)數(shù)是整數(shù)。 設(shè)Q(x):x是有理數(shù) R(x):x是實(shí)數(shù) I(x):x是整數(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)任何人如果他喜歡步行，他就不喜歡乘汽車(chē)；每個(gè)人或者喜歡乘汽車(chē)或者喜歡騎自行車(chē)。有的人不愛(ài)騎自行車(chē)，因此有的人不愛(ài)步行。 設(shè) A(x

62、):x是人, B(x):x是喜歡步行, C(x):x喜歡乘汽車(chē)，D(x):x喜歡騎自行車(chē) 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)

63、 T I A(a)B(a)) T I x(A(x)B(x)) EG ,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(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

64、(a)C(a)) US B(a)C(a)) T I C(a)D(a) P C(a) T I B(a) T I B(a) T E A(a)B(a) CP,補(bǔ)充題：小楊、小劉和小林為高山俱樂(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:雪。

65、命題符號(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(b)) US M(b) P H(b)D(b) T I11 D(b) T I10 D(b)H(b) T ,第二章 謂詞邏輯,到此結(jié)束,