離散數(shù)學(xué)242442

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

2、是主語不同。命題、之間在主語謂語方面也是有聯(lián)系的，靠這種聯(lián)系才能由、推出。而從這三個符號上看不出此種聯(lián)系。 所以就要另外考慮表示命題的方法另外考慮表示命題的方法。解決這個問題的方法：在表示命題時，既表示出主語，也表示出謂語，在表示命題時，既表示出主語，也表示出謂語，就可以解決上述問題。這就提出了就可以解決上述問題。這就提出了謂詞謂詞的概念。的概念。令令S(x)S(x)表示表示x x是大學(xué)生，是大學(xué)生，a:a:小張，小張，b:b:小李小李 命題命題P P表示成表示成S(a):S(a):小張是大學(xué)生。小張是大學(xué)生。 命題命題Q Q表示成表示成S(b):S(b):小李是大學(xué)生。小李是大學(xué)生。從符號從

3、符號S(a)S(a)、S(b)S(b)可看出小張和小李都是大學(xué)生的共性可看出小張和小李都是大學(xué)生的共性. .令令N(x):xN(x):x是自然數(shù)。是自然數(shù)。I(x):xI(x):x是整數(shù)。是整數(shù)。 表示所有的。表示所有的。 A: x(N(x)I(x)(N(x)I(x) B :N(8) :N(8) C :I(8):I(8)N(8)I(8)N(8)I(8)N(8)N(8) I(8) I(8)符號符號 S(x)S(x)、N(x)N(x)、I(x)I(x)就是所謂的謂詞就是所謂的謂詞。推理如此實現(xiàn)：推理如此實現(xiàn)：2-1 2-1 基本概念基本概念2-1.1 2-1.1 客體與客體變元客體與客體變元 定義

4、定義：能夠獨立存在的事物，稱之為客體，也稱之為個體。它可以是具體的，也可以是抽象的事物。通常用小寫英文字母a、b、c、.表示。例如，小張、小李、8、a、沈陽、社會主義等等都是客體。 定義定義：用小寫英文字母x、y、z.表示任何客體，則稱這些字母為客體變元。 注意：客體變元本身不是客體。2-1.2 2-1.2 謂詞謂詞 定義定義：一個大寫英文字母后邊有括號，括號內(nèi)是若干個客體變元，用以表示客體的屬性或者客體之間的關(guān)系，稱之為謂詞。如果括號內(nèi)有n個客體變元，稱該謂詞為n元謂詞。 例如 S(x):表示x是大學(xué)生。 一元謂詞 G(x,y)：表示 xy。 二元謂詞 B(x,y,z)：表示x在y與z之間。

5、三元謂詞一般地 P(x1,x2,xn) 是n元謂詞。2-1.3 2-1.3 命題函數(shù)命題函數(shù) 謂詞本身并不是命題，只有謂詞的括號內(nèi)填入足夠的客體，才變成命題。 例如， a表示小張，b表示小李，則 S(a):小張是大學(xué)生。 S(b):小李是大學(xué)生。 (7,3)表示:。 如果c表示錦州，d表示沈陽，e表示山海關(guān)，則B(c,d,e)表示：錦州在沈陽與山海關(guān)之間。這時S(a)、S(b)、G(7,3)、B(c,d,e)才是命題。令謂詞S(x):x是大學(xué)生，括號內(nèi)填入不同的人名，就得到不同的命題，故謂詞S(x)相當(dāng)于一個函數(shù)，稱之為命題函數(shù)。定義定義：n元謂詞P(x1,x2,xn)稱之為簡單命題函數(shù)。規(guī)定

6、：當(dāng)命題函數(shù)P(x1,x2,xn)中 n=0 時，即0元謂詞，表示不含有客體變元的謂詞，它本身就是一個命題變元命題變元。定義定義：將若干個簡單命題函數(shù)用邏輯聯(lián)結(jié)詞聯(lián)結(jié)起來，構(gòu)成的表達(dá)式，稱之為復(fù)合命題函數(shù)。簡單命題函數(shù)與復(fù)合命題函數(shù)統(tǒng)稱為命題函數(shù)。 例如 給定簡單命題函數(shù)： A(x)：x身體好， B(x)：x學(xué)習(xí)好， C(x)：x工作好， 復(fù)合命題函數(shù) A(x)(B(x)C(x) 表示如果x身體不好，則x的學(xué)習(xí)與工作都不會好。2-1.4 2-1.4 論域論域( (個體域個體域) ) 定義定義：在命題函數(shù)中客體變元的取值范圍，稱之為論域，也稱之為個體域。 例如 S(x):x是大學(xué)生，論域是:人類

7、。 G(x,y)：xy， 論域是:實數(shù)。 論域是一個集合。 定義定義：由所有客體構(gòu)成的論域，稱之為全總個體域。它是個“最大”的論域。 約定:對于一個命題函數(shù)，如果沒有給定論域，則假定該論域是全總個體域。2-1.5 2-1.5 量詞量詞 例如：有些人是大學(xué)生。 所有事物都是發(fā)展變化的。“有些”,“所有的”,就是對客體量化的詞。 定義定義：在命題中表示對客體數(shù)量化的詞，稱之為量詞。 定義了兩種量詞： (1).存在量詞：記作 ，表示“有些”、“一些”、“某些”、“至少一個”等。 (2).全稱量詞：記作 ，表示“每個”、“任何一個”、“一切”、“所有的”、“凡是”、“任意的”等。 定義定義：量詞后邊要

8、有一個客體變元，指明對哪個客體變元量化，稱此客體變元是量詞后的指導(dǎo)變元。例如 x(讀作“任意x”)， x(讀作“存在x”)，其中的x就是量詞后的指導(dǎo)變元。例題.所有的自然數(shù)都是整數(shù)。 設(shè) N(x)：x是自然數(shù)。I(x)：x是整數(shù)。此命題可以寫成 x(N(x)I(x)例題.有些自然數(shù)是偶數(shù)。 設(shè) E(x)：x是偶數(shù)。 此命題可以寫成 x(N(x)E(x) 例題3. 每個人都有一個生母。 設(shè) P(x):x是個人。M(x,y):y是x的生母。此命題可以寫成 x(P(x)y(P(y)M(x,y)2-2 2-2 謂詞公式及命題符號化謂詞公式及命題符號化 命題邏輯中有命題公式，類似地，在謂詞邏輯中，要研究

9、謂詞公式。2-2.1 2-2.1 客體函數(shù)客體函數(shù) 有些命題中，可能有若干個客體，其中有些客體之間有函數(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 小王的父親是個醫(yī)生。 設(shè)函數(shù)f(x)=x的父親，謂詞D(x):x是個醫(yī)生，a:小王，此命題可以表示為D(f(a). 例題3 如果x和y都是奇數(shù)，則x+y是偶數(shù)。 設(shè) h(x,y)=x+y ，此命題可以表示為: xy(O(x)O(y)E(h(x,y) 像上述的g(x)、f(x

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

11、-2.2 2-2.2 原子謂詞公式原子謂詞公式 定義定義：稱n元謂詞P(x1,x2,.,xn)為原子謂詞公式。 例如 P、Q(x) 、 A(x,f(x)、B(x,y,a) 都是原子謂詞公式。2-2.3 2-2.3 謂詞合式公式謂詞合式公式( (WFF)WFF) (Well Formed formulas) (Well Formed formulas) 定義定義：謂詞合式公式遞歸定義如下： 1.原子謂詞公式是合式公式。 2.如果A是合式公式，則A也是合式公式。 3.如果A、B是合式公式，則(AB)、(AB)、(AB)、(AB)都是合式公式。 4.如果A是合式公式，x是中的任何客體變元，則x和x也

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

13、. x(P(x)Q(x)yR(x,y)中 x的轄域是(P(x)Q(x)yR(x,y) y的轄域為R(x,y)。 xyz(A(x,y)B(x,y,z)C(t) x x的轄域的轄域 z z的轄域的轄域 y y的轄域的轄域一般地， 如果量詞后邊只是一個原子謂詞公式時，該量詞的轄域就是此原子謂詞公式。 如果量詞后邊是括號，則此括號所表示的區(qū)域就是該量詞的轄域。 如果多個量詞緊挨著出現(xiàn)，則后邊的量詞及其轄域就是前邊量詞的轄域。2-2.5 2-2.5 自由變元與約束變元自由變元與約束變元 在謂詞公式中的客體變元可以分成兩種，一種是受到量詞約束的，一種是不受量詞約束的。請看下面公式： x(F(x,y)yP(

14、y)Q(z) (x,y)中的x在x的轄域內(nèi)，受到x的約束，而其中的y不受x的約束。 P(y)中的y在y的轄域內(nèi)，受y的約束。 Q(z)中的z不受量詞約束。 定義定義：如果客體變元x在x或者x的轄域內(nèi)，則稱x在此轄域內(nèi)約束出現(xiàn)，并稱x在此轄域內(nèi)是約束變元。否則x是自由出現(xiàn)，并稱x是自由變元。 上例中 x(F(x,y)yP(y)Q(z) F(x,y)中的x和P(y)中的y是約束變元。而F(x,y)中的y和Q(z)中的z是自由變元。 對約束變元和自由變元有如下幾點說明：(1).對約束變元用什么符號表示無關(guān)緊要。就是說xA(x)與yA(y)是一樣的。這類似于計算積分與積分變元無關(guān)，即積分f(x)dx

15、與f(y)dy 相同。(2).一個謂詞公式如果無自由變元，它就表示一個命題。 例如 A(x)表示x是個大學(xué)生。xA(x)或者xA(x)就是個命題了，因為它們分別表示命題“有些人是大學(xué)生”和“所有人都是大學(xué)生”。(3).(3).一個一個n n元謂詞元謂詞P(xP(x1 1,x,x2 2, ,x,xn n) )，若在前邊添加，若在前邊添加k k個量詞，使其中的個量詞，使其中的 k k個客體變元變成約束變個客體變元變成約束變元，則此元，則此 n n元謂詞就變成了元謂詞就變成了n-kn-k元謂詞。元謂詞。 例如例如P(x,y,z)P(x,y,z)表示表示x+y=zx+y=z，假設(shè)論域是整數(shù)集。，假設(shè)論

16、域是整數(shù)集。 x x yPyP(x,y,z)(x,y,z)表示表示“任意給定的整數(shù)任意給定的整數(shù)x x，都可，都可以找到整數(shù)以找到整數(shù)y y，使得，使得x+y=z” x+y=z” 。 如果令如果令 z=1z=1，則，則 x x yPyP(x,y,1)(x,y,1)就變成了命題就變成了命題“任意給定的整數(shù)任意給定的整數(shù)x x，都可以找到整數(shù)，都可以找到整數(shù)y y，使得，使得x+y=1”,x+y=1”,。 可見每當(dāng)給可見每當(dāng)給z z指定個整數(shù)指定個整數(shù)a a后，后， x x yPyP(x,y,a)(x,y,a)就變成了一個命題。所以謂詞公式就變成了一個命題。所以謂詞公式 x x yPyP(x,y,

17、z)(x,y,z)就相當(dāng)于只含有客體變元就相當(dāng)于只含有客體變元 z z的的一元謂詞了。一元謂詞了。 在一個謂詞公式中，如果某個客體變元既以約束變元形式出現(xiàn)，又以自由變元形式出現(xiàn)，就容易產(chǎn)生混淆。為了避免此現(xiàn)象發(fā)生，可以對客體變元更改名稱。 如 x(F(x,y)yP(y)Q(z) 約束變元的改名規(guī)則：(1).對約束變元可以更改名稱，改名的范圍是：量詞后的指導(dǎo)變元以及該量詞的轄域內(nèi)此客體變元出現(xiàn)的各處同時換名。(2).改名后用的客體變元名稱，不能與該量詞的轄域內(nèi)的其它變元名稱相同。 例如例如 x(P(x)Q(x,y)(R(x)A(x) x(P(x)Q(x,y)(R(x)A(x) 此式中的此式中的x

18、 x 就是以兩種形式出現(xiàn)?？梢詫褪且詢煞N形式出現(xiàn)?？梢詫 x改名改名成成 z(P(z)Q(z,y)(R(x)A(x) z(P(z)Q(z,y)(R(x)A(x) 對自由變元也可以換名字，此換名叫代入。對自由變元也可以換名字，此換名叫代入。對對自由變元的代入規(guī)則自由變元的代入規(guī)則：(1).(1).對謂詞公式中的自由變元可以作代入。代入對謂詞公式中的自由變元可以作代入。代入時需要對公式中出現(xiàn)該變元的每一處，同時作時需要對公式中出現(xiàn)該變元的每一處，同時作代入。代入。(2).(2).代入后的變元名稱要與公式中的其它變元名代入后的變元名稱要與公式中的其它變元名稱不同稱不同上例也可以對自由變元上例也可

19、以對自由變元x x作代入，改成作代入，改成 x(P(x)Q(x,y)(R(z)A(z) x(P(x)Q(x,y)(R(z)A(z) 2-2.6 2-2.6 命題的符號化命題的符號化在謂詞演算中，命題的符號化比較復(fù)雜，命題的符號表達(dá)式與論域有關(guān)系。例如1.每個自然數(shù)都是整數(shù)。(1).如果論域是自然數(shù)集合N，令 I(x)：x是整數(shù)，則命題的表達(dá)式為 xI(x) (2).如果論域擴大為全總個體域時，上述表達(dá)式xI(x)表示“所有客體都是整數(shù)”，顯然這是假的命題，此表達(dá)式已經(jīng)不能表達(dá)原命題了。因此需要添加謂詞N(x)：x是自然數(shù)，用于表明x的特性，于是命題的符號表達(dá)式為 x(N(x)I(x)2.有些大

20、學(xué)生吸煙。(1).如果論域是大學(xué)生集合S，令A(yù)(x)：x吸煙，則命題的表達(dá)式為 xA(x) (2).如果論域擴大為全總個體域時，上述表達(dá)式xA(x)表示“有些客體吸煙”，就不是表示此命題了，故需要添加謂詞 S(x)：x是大學(xué)生，用于表明x的特性，于是命題的表達(dá)式為 x(S(x)A(x) 從上述兩個例子可以看出，命題的符號表達(dá)式與論域有關(guān)。當(dāng)論域擴大時，需要添加用來表示客體特性的謂詞，稱此謂詞為特性謂詞。特特性謂詞性謂詞往往就是給定命題中量詞后邊的那個名詞。如上面兩個例子中的“所有自然數(shù)”、“有些大學(xué)生”。 如何添加特性謂詞，這是個十分重要的問題，這與前邊的量詞有關(guān)。 特性謂詞的添加方法如下：

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

22、則命題的表達(dá)式為則命題的表達(dá)式為 x(S(x)x(S(x) y(X(y)L(x,y) y(X(y)L(x,y) 4.4.沒有不犯錯誤的人。沒有不犯錯誤的人。 此話就是此話就是“沒有人不犯錯誤沒有人不犯錯誤”，“沒有沒有”就是就是“不存不存在在”之意。令之意。令P(x)P(x)：x x是人，是人，F(xiàn)(x)F(x)：x x犯錯誤，犯錯誤， 此命題的表達(dá)式為此命題的表達(dá)式為 x(P(x)x(P(x) F(x)F(x)或者或者 x(P(x)F(x)x(P(x)F(x)5.5.不是所有的自然數(shù)都是偶數(shù)。不是所有的自然數(shù)都是偶數(shù)。 令令N(x)N(x)：x x是自然數(shù)，是自然數(shù)，E(x)E(x)：x x是

23、偶數(shù)，是偶數(shù)， 命題的表達(dá)式為命題的表達(dá)式為: : x(N(x)E(x)x(N(x)E(x)或者或者 x(N(x)x(N(x) E(x)E(x)6.6.如果一個人只是說謊話，那么他所說的每句話沒有如果一個人只是說謊話，那么他所說的每句話沒有一句是可以相信的。一句是可以相信的。 令令A(yù)(x)A(x)：x x是人，是人，B(x,y)B(x,y)：y y是是x x說的話，說的話， C(x):xC(x):x是謊話，是謊話，D(x)D(x)：x x是可以相信的是可以相信的 命題的表達(dá)式為命題的表達(dá)式為: : x(A(x)(x(A(x)( y(B(x,y)C(y)y(B(x,y)C(y) z(B(x,z)

24、D(z)z(B(x,z)D(z) 或者或者 x(A(x)x(A(x) y(B(x,y)C(y)y(B(x,y)C(y)D(y)D(y) 7. 7.每個自然數(shù)都有唯一的后繼數(shù)。每個自然數(shù)都有唯一的后繼數(shù)。 令令N(x)N(x)：x x是自然數(shù)，是自然數(shù)，A(x,y)A(x,y)：y y是是x x的后繼數(shù)，的后繼數(shù)， E(x,y)E(x,y)：x=y x=y 則命題的表達(dá)式為則命題的表達(dá)式為 x(N(x)x(N(x) y(N(y)A(x,y)y(N(y)A(x,y) z(N(z)A(x,z)E(y,z)z(N(z)A(x,z)E(y,z) 有一個后繼數(shù)后繼數(shù)的唯一性下面請同學(xué)們自己做練習(xí)第下面請同

25、學(xué)們自己做練習(xí)第6060頁頁(2)(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) 或者 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é)小結(jié)1.1.命題的符號表達(dá)式形式與論域有關(guān)系。命題的符號表達(dá)式形式與論域

26、有關(guān)系。 論域擴大需要用特性謂詞對客體進(jìn)行說明論域擴大需要用特性謂詞對客體進(jìn)行說明. .注意如何添注意如何添加特性謂詞加特性謂詞( (即要注意特性謂詞后邊是什么聯(lián)結(jié)詞即要注意特性謂詞后邊是什么聯(lián)結(jié)詞) )。2.2.如果量詞前有否定符號，如如果量詞前有否定符號，如“沒有沒有.”“.”“不是所有不是所有的的.”.”等，可以按照字面直譯。如等，可以按照字面直譯。如“x” “x.”3.3.命題的符號表達(dá)式中所有客體變元必須都是約束變元，命題的符號表達(dá)式中所有客體變元必須都是約束變元，才表示命題。有時給定命題中有些量詞沒有明確給出，才表示命題。有時給定命題中有些量詞沒有明確給出，要仔細(xì)分析并寫出這隱含的

27、量詞。要仔細(xì)分析并寫出這隱含的量詞。 例如例如 a) a) 金子閃光，但閃光的不一定都是金子。金子閃光，但閃光的不一定都是金子。G(x),F(x)G(x),F(x) x(G(x)F(x)x(F(x) G(x) b) 沒有大學(xué)生不懂外語。沒有大學(xué)生不懂外語。S(x),K(x,y),F(x)S(x),K(x,y),F(x) x(S(x)y(F(y)K(x,y) 作業(yè) 60頁 (2) 62頁 (2), (3) b), c), (5) b) (6) 65頁 (4) b) (5) a)2-3謂詞演算的等價式與蘊涵式 在命題邏輯中，我們是通過對公式的命題變元賦值來討論永真式、永真蘊含式及等價公式的。 在謂

28、詞演算中，也要討論一些重要的謂詞公式。但是由于謂詞公式中可能有命題變元、客體變元。對命題變元賦值比較容易，因為只有兩個值可賦。而對客體變元作指派卻不那么簡單，因為論域中的客體可能有無限個。另外謂詞公式的真值還與論域有關(guān)。2-3.1 對謂詞公式賦值 定義定義：若將給定的謂詞公式中的命題變元，用確定的命題代替，對公式中的客體變元用論域中的客體代替，這個過程就稱之為對謂詞公式作指派，或者稱之 為對謂詞公式賦值。 例如公式 PN(x)，N(x)：x是自然數(shù)，論域為實數(shù)集合R， 令P：21，x=4 時，此公式變成PN(4)，它的真值就是“真”。2-3.2 謂詞公式的永真式定義 定義定義：給定謂詞公式A，

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

30、假設(shè)論域E是自然數(shù)集合，公式I(x)與N(x)在E上是等價的。 而公式N(x)I(x) 與N(x)I(x)就是與論域無關(guān)的等價的公式，即 N(x)I(x)N(x)I(x)。2-3.4 謂詞公式的永真蘊含式定義 定義定義：給定謂詞公式A、B，E是它們的論域，如果不論對公式A、B作任何賦值，都使得AB為永真式，則稱在論域E上公式A永真蘊含B。如果不論對什么論域E，都使得公式AB為永真式，則稱A永真蘊含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)就是與論域無關(guān)的

31、永真式，所以(G(x)N(x)N(x)。2-3.5. 重要公式 下面討論重要的謂詞等價公式和永真蘊含式。下面討論重要的謂詞等價公式和永真蘊含式。一一. .由命題公式推廣出的公式由命題公式推廣出的公式因一個不含自由變元的謂詞公式本身如因一個不含自由變元的謂詞公式本身如 xA(x)xA(x)、 xBxB(x)(x)就是命題就是命題。一個含有。一個含有n n個自由變元的謂詞公式，賦予論域個自由變元的謂詞公式，賦予論域中的中的n n個指定客體后就變成命題個指定客體后就變成命題( (例如例如S(a)S(a)、G(3,1)G(3,1)等等) )。因此可以把此公式因此可以把此公式看成一個命題變元看成一個命題

32、變元。所以在命題演算。所以在命題演算的永真式中，將其中的同一個命題變元，用同一個謂詞的永真式中，將其中的同一個命題變元，用同一個謂詞公式代替，所得到的公式也是永真式。這樣就可以將命公式代替，所得到的公式也是永真式。這樣就可以將命題演算中的等價公式和永真蘊含式推廣到謂詞演算中使題演算中的等價公式和永真蘊含式推廣到謂詞演算中使用。例如用。例如A(x)A(x)A(x)B(x) A(x)B(x) P PPQPQ x(A(x)B(x)x(A(x)B(x)x(x( A(x)B(x) A(x)B(x) PQPQP PQ Q ( ( xA(x)xA(x) xBxB(x)(x)xA(x)xA(x)xBxB(x)

33、 (x) 摩根定律摩根定律二二. .帶量詞的公式在論域內(nèi)的展開式帶量詞的公式在論域內(nèi)的展開式 先看一個例子，令A(yù)(x)：表示x是整數(shù)，B(x)：表示x是奇數(shù)，設(shè)論域是1,2,3,4,5，謂詞公式 xA(x)表示論域內(nèi)所有的客體都是整數(shù)，顯然公式 xA(x)的真值為真，因為A(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)的真值也為真，因為B(1)、B(3)、B(5)的真值為真，于是有 xB(x)B(1)B(2)B(3)B(4)B(5) 一般地，設(shè)論域為a1,a

34、2,.,an，則 1. 1. xA(x)xA(x)A(aA(a1 1)A(a)A(a2 2).A(a).A(an n) ) 2. 2. xBxB(x)(x)B(aB(a1 1)B(a)B(a2 2).B(a).B(an n) )三三. .量詞否定公式量詞否定公式 我們還是先用一個例子說明這個問題。令(x)表示x是優(yōu)等生，論域是某班級的學(xué)生集合。 xA(x)表示：不是所有人都是優(yōu)等生。 xA(x)表示：有些人不是優(yōu)等生。 xA(x)表示：沒有人是優(yōu)等生。 xA(x)表示：所有人都不是優(yōu)等生。 從這個例子可以看出 “不是所有人都是優(yōu)等生?！迸c“有些人不是優(yōu)等生?！笔堑葍r的。 “沒有人是優(yōu)等生?！迸c

35、“所有人都不是優(yōu)等生?！笔堑葍r的。于是有： 1. 1. xA(x)xA(x)x x A(x)A(x)2. 2. xA(x)xA(x)x x A(x)A(x)對這兩個公式可以證明如下：證明：證明：設(shè)論域為a1,a2,.,an，則 xA(x)(A(a1)A(a2).A(an)A(a1)A(a2).A(an)xA(x)類似可以證明另一個公式。從這兩個公式，可以總結(jié)出如下規(guī)律：將量詞前的“”移到量詞的后邊，或者將量詞后的“”移到量詞的前邊時，量詞也隨著改變，如果原來是全稱量詞改成存在量詞，如果原來是存在量詞改成全稱量詞。所以我們也把這兩個公式稱為量詞轉(zhuǎn)換公式。四.量詞轄域的擴充公式如果是個不含客體變元

36、x的謂詞公式，且不在 x和x的轄域內(nèi)，可以將放入 x和x的轄域內(nèi)。即得如下公式： 1. 1. xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 2. 2. xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 3. 3. xA(x)BxA(x)Bx(A(x)B)x(A(x)B) 4. 4. xA(x)BxA(x)Bx(x( (x)B)x)B) 5. B 5. B xA(x)xA(x)x(BA(x)x(BA(x) 6. B 6. B xA(x)xA(x)x(BA(x)x(BA(x) 7 7. . xA(x)BxA(x)B x(A(x)B)x(A(x)B) 8 8. . xA(x)Bx

37、A(x)B x(A(x)B)x(A(x)B)上述公式我們只證明三個。上述公式我們只證明三個。 證明：證明：設(shè)論域為設(shè)論域為 a a1 1,a,a2 2,.,a,.,an n ， xA(x)BxA(x)B(A(a(A(a1 1)A(a)A(a2 2).A(a).A(an n)B)B(A(a(A(a1 1)B)(A(a)B)(A(a2 2)B).(A(a)B).(A(an n)B)B)x(x(x)(x) )BB xA(x)xA(x)BB xA(x)xA(x)x(x( BA(x)BA(x)x(BA(x)x(BA(x) xA(x)BxA(x)BxA(x)BxA(x)Bx x A(x)BA(x)B x(

38、x( A(x)B)A(x)B)x(A(x)B)x(A(x)B) 在使用公式在使用公式7.7.、8.8.時，要特別注意，量詞的轄時，要特別注意，量詞的轄域擴充后，量詞發(fā)生了變化域擴充后，量詞發(fā)生了變化。五五. .量詞分配公式量詞分配公式1. 1. x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xBxB(x)(x)2. 2. x(A(x)B(x)x(A(x)B(x)xA(x)xA(x) xBxB(x)(x)3. 3. x(A(x)B(x)x(A(x)B(x) xA(x)xA(x) xBxB(x)(x)4. 4. xA(x)xA(x) xBxB(x)(x) x(A(x)B(x)x(A

39、(x)B(x)證明證明：設(shè)論域為：設(shè)論域為 a a1 1,a,a2 2,.,a,.,an n ， x(A(x)B(x) x(A(x)B(x) (A(a(A(a1 1)B(a)B(a1 1)(A(a)(A(a2 2)B(a)B(a2 2) (A(a (A(an n)B(a)B(an n)(A(a(A(a1 1)A(a)A(a2 2).A(a).A(an n) (B(a (B(a1 1)B(a)B(a2 2).B(a).B(an n)xA(x)xA(x) xBxB(x)(x) 注意公式3.和4.不是等價公式，而是永真蘊含式。例如公式3.由xA(x)xB(x)不能推出x(A(x)B(x)， 我們可以

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

41、所以有真，所以有xA(x)xA(x)以及以及xBxB(x)(x)為真，進(jìn)為真，進(jìn)而得而得xA(x)xA(x)xBxB(x)(x)為真。于是有為真。于是有 x(A(x)B(x)x(A(x)B(x)xA(x)xA(x)xBxB(x)(x) 下面利用公式下面利用公式3.3.證明公式證明公式4.4.。證明證明：因為公式：因為公式3.3.中的中的A(x)A(x)和和B(x)B(x)是任意是任意的謂詞公式，不妨用的謂詞公式，不妨用 A(x)A(x)和和 B(x)B(x)分別分別代替公式代替公式3.3.中的中的A(x)A(x)和和B(x)B(x)得得 x(x( A(x)A(x) B(x)B(x)x x A(

42、x)A(x) x x B(x)B(x) x x (A(x)B(x)(A(x)B(x)xA(x)xA(x)xBxB(x)(x) x(A(x)B(x)x(A(x)B(x)( ( xA(x)xA(x) xBxB(x) (x) 應(yīng)用公式應(yīng)用公式 P PQ QQ Q P P 得得 xA(x)xA(x) xBxB(x)(x)x(A(x)B(x)x(A(x)B(x)公式公式4.4.得證。得證。在使用公式在使用公式4.4.的時候，的時候，特別要注意蘊含式特別要注意蘊含式的方向，不要搞錯。的方向，不要搞錯。六其它公式1. x(A(x)B(x)xA(x)xB(x) 2. xA(x)xB(x)x(A(x)B(x)證

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

44、xA(x,y)xA(x,y) 表示“存在一個實數(shù)y,與任意給定的一個實數(shù)x之和都等于0”,這是一個為“假”的命題。 有如下一些公式：1. 1. x x yAyA(x,y)(x,y)y y xA(x,y)xA(x,y)2. 2. x x yAyA(x,y)(x,y)y y xA(x,y)xA(x,y)3. 3. y y xA(x,y)xA(x,y)x x yAyA(x,y)(x,y)4. 4. x x yAyA(x,y)(x,y)x x yAyA(x,y)(x,y)5. 5. y y xA(x,y)xA(x,y)x x yAyA(x,y)(x,y)6. 6. x x yAyA(x,y)(x,y)

45、y y xA(x,y)xA(x,y)7. 7. y y xA(x,y)xA(x,y)x x yAyA(x,y)(x,y)8. 8. x x yAyA(x,y)(x,y)y y xA(x,y)xA(x,y)注意：下面式子不成立注意：下面式子不成立 x x yAyA(x,y)(x,y)y y xA(x,y)xA(x,y) 為了便于記憶，用下面圖形表示上面八個公式。 x x yAyA(x,y)(x,y) y y xA(x,y)xA(x,y) x x yAyA(x,y)(x,y) y y xA(x,y)xA(x,y) x x yAyA(x,y)(x,y) y y xA(x,y)xA(x,y) y y

46、xA(x,y)xA(x,y) x x yAyA(x,y)(x,y) 實際上，根據(jù)實際上，根據(jù)具有傳遞性，還可以派生出一些公式。具有傳遞性，還可以派生出一些公式。下面我們只證明一個等價公式。用謂詞邏輯推理方法很下面我們只證明一個等價公式。用謂詞邏輯推理方法很容易證明上面那些永真蘊涵式，在此就不證明了。下面容易證明上面那些永真蘊涵式，在此就不證明了。下面證明公式證明公式1.1.。 證明：證明：設(shè)論域為設(shè)論域為 a a1 1,a,a2 2,.,a,.,an n ，則，則 x x yAyA(x,y)(x,y) yAyA(a(a1 1,y),y) yAyA(a(a2 2,y),y) yAyA(a(an

47、n,y),y) (A(a(A(a1 1,a,a1 1)A(a)A(a1 1,a,a2 2)A(aA(a1 1,a,an n) (A(a (A(a2 2,a,a1 1)A(a)A(a2 2,a,a2 2)A(aA(a2 2,a,an n) (A(a (A(an n,a,a1 1)A(a)A(an n,a,a2 2)A(aA(an n,a,an n) (A(a(A(a1 1,a,a1 1)A(a)A(a2 2,a,a1 1)A(aA(an n,a,a1 1) (A(a (A(a1 1,a,a2 2)A(a)A(a2 2,a,a2 2)A(aA(an n,a,a2 2) (A(a (A(a1 1,a

48、,an n)(A(a)(A(a2 2,a,an n)A(aA(an n,a,an n) xA(x,axA(x,a1 1) xA(x,axA(x,a2 2) xA(x,axA(x,an n) ) y y xA(x,y)xA(x,y) 本節(jié)小結(jié)： 熟練掌握謂詞等價公式和永真蘊涵式的證明方法及應(yīng)用。 作業(yè)題： P66 (3) b) P71 (2) d), (6) 面作做個練習(xí)P71(1) c)練習(xí)練習(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求求 x y(P(x,y)P(f(x),f(

49、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) ) ( (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 F2-42-4前束范式前束范式 與命題公式的范式類似，謂詞公式也有規(guī)范形式。這與命題

50、公式的范式類似，謂詞公式也有規(guī)范形式。這里主要介紹前束范式里主要介紹前束范式-所有量詞都在公式前邊約束變元所有量詞都在公式前邊約束變元。1.1.前束范式定義：前束范式定義： 如果一個謂詞公式符合下面條件，它就是如果一個謂詞公式符合下面條件，它就是前束范式前束范式： 所有量詞前面都沒有聯(lián)接詞；所有量詞前面都沒有聯(lián)接詞； 所有量詞都在公式的左面；所有量詞都在公式的左面； 所有量詞的轄域都延伸到公式的末尾。所有量詞的轄域都延伸到公式的末尾。 例如例如 y y x x z z( (A(x)(B(x,y)C(x,y,z)A(x)(B(x,y)C(x,y,z) ) x x( ( (x)B(x)x)B(x)

51、 ) 就是前束范式，而就是前束范式，而 xA(x)xA(x) y yB B(y)(y) x x y(A(x)(B(x,y)y(A(x)(B(x,y) zCzC(z)(z) xA(x)B(x) xA(x)B(x) 這三個就不是前束范式。這三個就不是前束范式。 2.前束范式的寫法法給定一個帶有量詞的謂詞公式，1)消去公式中的聯(lián)接詞和(為了便于量詞轄域的擴充)；2)如果量詞前有“ ”，則用量詞否定公式將“ ”后移。再用摩根定律或求公式的否定公式，將“ ”后移到原子謂詞公式之前。3)用約束變元的改名規(guī)則或自由變元的代入規(guī)則對變元換名(為量詞轄域擴充作準(zhǔn)備)4)用量詞轄域擴充公式提取量詞，使之成為前束范

52、式形式。 例1. xA(x)xB(x) xA(x)xA(x)xB B(x)(x) x x A(x)A(x)xB B(x)(x) x x A(x)A(x)yB B(y) (y) (換元換元) ) x(x( A(x)A(x)yB B(y) (y) (量詞轄域擴充量詞轄域擴充) ) x xy( ( A(x)B(y)A(x)B(y) 另一個方法：xA(x)xB(x) xA(x)xA(x)xB B(x)(x) x x A(x)A(x)xB B(x)(x) x(x( A(x)B(x) A(x)B(x) ( (量詞分配公式量詞分配公式) ) 例例2.2. x x( (P(x)R(x)(P(x)R(x)(xP

53、(x)Q(x)xP(x)Q(x)x x( (P(x)R(x)(P(x)R(x)(xP(x)Q(x)xP(x)Q(x) ( (去去) )x x ( (P(x)R(x)(P(x)R(x)( x x P(x)Q(xP(x)Q(x) () (量詞轉(zhuǎn)換量詞轉(zhuǎn)換) )x x( ( P(x)P(x) R(x)(R(x)( x x P(x)Q(xP(x)Q(x) () (后移后移 ) )x x( ( P(x)P(x) R(x)(R(x)( y y P(y)Q(zP(y)Q(z) () (換變元換變元) )x x( ( P(x)P(x) R(x)R(x) y(y( P(y)Q(zP(y)Q(z) () (擴量詞

54、轄域擴量詞轄域) )x x y(y( ( P(x)P(x) R(x)(R(x)( P(y)Q(zP(y)Q(z)()(擴量詞轄域擴量詞轄域) )3.3.前束析取范式與前束合取范式：前束析取范式與前束合取范式：前束析取范式前束析取范式: :前束范式中量詞后的括號內(nèi)是析取范式形式。前束范式中量詞后的括號內(nèi)是析取范式形式。前束合取范式前束合取范式: :前束范式中量詞后的括號內(nèi)是合取范式形式。前束范式中量詞后的括號內(nèi)是合取范式形式。上例的前束析取范式為上例的前束析取范式為: : x x y(y( P(x)P(x) R(x)(R(x)( P(y)Q(zP(y)Q(z)上例的前束合取范式為上例的前束合取范

55、式為: : x x y(y( P(x)P(x) R(x)R(x) P(y)(P(y)( P(x)P(x) R(x)Q(zR(x)Q(z) 本節(jié)掌握前束范式的寫法。 作業(yè) P75 (1)b) (2)c)2-5 謂詞演算的推理理論推理方法： 直接推理、條件論證、反證法所用公式：43頁和70頁的I1I19，E1E33推理規(guī)則：P、T、CP、US、ES、EG、UG 后四個規(guī)則，是處理量詞的，因為推理時要使用不含量詞的命題公式，所以要去掉量詞，如果結(jié)論有量詞，還要添加量詞。 下面介紹四個新規(guī)則：一一.全稱特指規(guī)則全稱特指規(guī)則 US (Universal Specialization) 形式： xA(x)

56、A(c) (其中c是論域內(nèi)指定客體) 含義：如果xA(x)為真，則在論域內(nèi)任 何指定客體c，都使得A(c)為真。 作用：去掉全稱量詞。 要求：c不是A(x)中的符號。二二.存在特指規(guī)則存在特指規(guī)則ES(Existential Specialization) 形式： xA(x)A(c) (其中c是論域內(nèi)指定客體) 含義：如果xA(x)為真，則在論域內(nèi)指定指定客體c， 都使得A(c)為真。 作用：去掉存在量詞。 要求： c不是A(x)中的符號。 用ES指定的客體c不應(yīng)該是在此之前在此之前用US規(guī)則或者用ES規(guī)則所指定的客體c(即本次用ES特指客體c，不應(yīng)該是以前特指的客體)。請看下面兩個例子：例1

57、. 令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ī)則存在推廣規(guī)則 EGEG (Existential Generalization) 形式： A(c)xA(x) (其中c是論域內(nèi)指定客體) 含義：如果在論域內(nèi)指定客體c使得 A(c)為真，則xA(x)為真。 作用：添加存在量詞。 要求：x不是A(c)中的符號。四四. .全稱推廣規(guī)則全稱推廣規(guī)則UGUG (Universa

58、l Generalization) 形式： A(c)xA(x) (其中c是論域內(nèi)任何指定客體) 含義：如果在論域內(nèi)任何指定客體c都使 得A(c)為真，則xA(x)為真。 作用：添加全稱量詞。 要求：x不是A(c)中的符號。 c一定是任意一定是任意的客體，否則不可全 稱推廣。例1 所有金屬都導(dǎo)電。銅是金屬。 故銅導(dǎo)電。令 M(x):x是金屬。C(x):x導(dǎo)電。a:銅。符號化為： 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 例2. 所有自然數(shù)都是整數(shù)。有些數(shù)是自然數(shù)。因此有些數(shù)是整數(shù)。令A(yù)(x)表示x是自然數(shù)，B(x)

59、表示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) T I11 xB(x) EG 問題在哪里？例3 不認(rèn)識錯誤的人，也不能改正錯誤。有些誠實的人改正了錯誤。所以有些誠實的人是認(rèn)識了錯誤的人。設(shè)A(x):x是認(rèn)識錯誤的人。 B(x):x改正了錯誤。C(x):x是誠實的人。符號化為：x(A(x

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