第二章 謂詞邏輯,問題的提出：(即命題邏輯的局限性) 在第一章, 一個原子命題只用一個字母表示， 而不再對命題中的句子成分細分。這樣有一些邏 輯問題無法解決。請看下面的例子。 例1.令：小張是大學生。 ：小李是大學生。 從符號、中不能歸納出他們都是大學生的共 性。我們希望從所使用的符號那里帶給我們更多 的信息，比如可以看出他們的共性。這種想法在 第一章是無法實現(xiàn)的。,例2.令 ：所有自然數(shù)都是整數(shù)。 ：是自然數(shù)。 ：是整數(shù)。 這是著名的三段論推理，A是大前提，B是小前提， C是結論。顯然，由和可以推出結論。這 個推理是有效的，但是這個推理在第一章也是無 法實現(xiàn)的。 分析：命題與中的謂語是相同的(是大學生), 只是主語不同。命題、之間在主語謂語 方面也是有聯(lián)系的，靠這種聯(lián)系才能由、推 出。而從這三個符號上看不出此種聯(lián)系。 所以就要另外考慮表示命題的方法。,解決這個問題的方法： 在表示命題時，既表示出主語，也表示出謂語， 就可以解決上述問題。這就提出了謂詞的概念。 令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)I(8),N(8), I(8),符號 S(x)、N(x)、I(x)就是所謂的謂詞。,推理如此實現(xiàn)：,2-1 基本概念,2-1.1 客體與客體變元 定義：能夠獨立存在的事物，稱之為客體，也 稱之為個體。它可以是具體的，也可以是抽象的 事物。通常用小寫英文字母a、b、c、.表示。 例如，小張、小李、8、a、沈陽、社會主義等等 都是客體。 定義：用小寫英文字母x、y、z.表示任何客 體，則稱這些字母為客體變元。 注意：客體變元本身不是客體。,2-1.2 謂詞 定義：一個大寫英文字母后邊有括號，括號內是若干個客體變元，用以表示客體的屬性或者客體之間的關系，稱之為謂詞。如果括號內有n個客體變元，稱該謂詞為n元謂詞。 例如 S(x):表示x是大學生。 一元謂詞 G(x,y)：表示 xy。 二元謂詞 B(x,y,z)：表示x在y與z之間。三元謂詞 一般地 P(x1,x2,xn) 是n元謂詞。,2-1.3 命題函數(shù) 謂詞本身并不是命題，只有謂詞的括號內填入足夠的客體，才變成命題。 例如， a表示小張，b表示小李，則 S(a):小張是大學生。 S(b):小李是大學生。 (7,3)表示:。 如果c表示錦州，d表示沈陽，e表示山海關，則B(c,d,e)表示：錦州在沈陽與山海關之間。 這時S(a)、S(b)、G(7,3)、B(c,d,e)才是命題。,令謂詞S(x):x是大學生，括號內填入不同的人名， 就得到不同的命題，故謂詞S(x)相當于一個函數(shù)， 稱之為命題函數(shù)。 定義：n元謂詞P(x1,x2,xn)稱之為簡單命題函數(shù)。 規(guī)定：當命題函數(shù)P(x1,x2,xn)中 n=0 時，即0 元謂詞，表示不含有客體變元的謂詞，它本身就是 一個命題變元。 定義：將若干個簡單命題函數(shù)用邏輯聯(lián)結詞聯(lián)結起 來，構成的表達式，稱之為復合命題函數(shù)。簡單命 題函數(shù)與復合命題函數(shù)統(tǒng)稱為命題函數(shù)。,例如 給定簡單命題函數(shù)： A(x)：x身體好， B(x)：x學習好， C(x)：x工作好， 復合命題函數(shù) A(x)(B(x)C(x) 表示如果x身體不好，則x的學習與工作都不會好。,2-1.4 論域(個體域) 定義：在命題函數(shù)中命題變元的取值范圍，稱之為論域，也稱之為個體域。 例如 S(x):x是大學生，論域是:人類。 G(x,y)：xy， 論域是:實數(shù)。 論域是一個集合。 定義：由所有客體構成的論域，稱之為全總個體域。它是個“最大”的論域。 約定:對于一個命題函數(shù)，如果沒有給定論域，則假定該論域是全總個體域。,2-1.5 量詞 例如：有些人是大學生。 所有事物都是發(fā)展變化的。 “有些”,“所有的”,就是對客體量化的詞。 定義：在命題中表示對客體數(shù)量化的詞，稱之為量詞。 定義了兩種量詞： (1).存在量詞：記作，表示“有些”、“一些”、 “某些”、“至少一個”等。 (2).全稱量詞：記作，表示“每個”、“任何 一個”、“一切”、“所有的”、“凡是”、“任意 的”等。,定義：量詞后邊要有一個客體變元，指明對哪個客體變元量化，稱此客體變元是量詞后的指導變元。 例如 x(讀作“任意x”)，x(讀作“存在x”)，其中的x就是量詞后的指導變元。 例題.所有的自然數(shù)都是整數(shù)。 設 N(x)：x是自然數(shù)。I(x)：x是整數(shù)。此命 題可以寫成 x(N(x)I(x) 例題.有些自然數(shù)是偶數(shù)。 設 E(x)：x是偶數(shù)。 此命題可以寫成 x(N(x)E(x),例題3. 每個人都有一個生母。 設 P(x):x是個人。M(x,y):y是x的生母。此命題可以寫成 x(P(x)y(P(y)M(x,y),2-2 謂詞公式及命題符號化,命題邏輯中有命題公式，類似地，在謂詞邏輯 中，要研究謂詞公式。 2-2.1 客體函數(shù) 有些命題中，可能有若干個客體，其中有些客體 之間有函數(shù)關系，例如 例題1. 如果x是奇數(shù)，則2x是偶數(shù)。 其中客體x與客體2x之間就有函數(shù)關系，可以設 客體函數(shù) g(x)=2x， 謂詞 O(x)：x是奇數(shù)， E(x)：x是偶數(shù)， 則此命題可以表示為： x(O(x)E(g(x),例題2 小王的父親是個醫(yī)生。 設函數(shù)f(x)=x的父親，謂詞D(x):x是個醫(yī)生，a:小王，此命題可以表示為D(f(a). 例題3 如果x和y都是奇數(shù)，則x+y是偶數(shù)。 設 h(x,y)=x+y ，此命題可以表示為: xy(O(x)O(y)E(h(x,y) 像上述的g(x)、f(x)、h(x,y)就是客體函數(shù)，一般地用小寫的英文字母f,g,h.表示客體函數(shù)。 注意:客體函數(shù)與謂詞是不同的，不可混淆.,要注意區(qū)分客體函數(shù)與謂詞間的區(qū)別： 設例題1的論域是自然數(shù)集合N。 客體函數(shù)中的客體變元用客體帶入后的結果依然是個客體(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-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是中的任何客體變元，則x和x也是合式公式。 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 量詞的作用域(轄域) 定義：在謂詞公式中，量詞的作用范圍稱之為量詞的作用域，也叫量詞的轄域。 例如 xA(x)中x的轄域為A(x). 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),一般地， 如果量詞后邊只是一個原子謂詞公式時，該量詞的轄域就是此原子謂詞公式。 如果量詞后邊是括號，則此括號所表示的區(qū)域就是該量詞的轄域。 如果多個量詞緊挨著出現(xiàn)，則后邊的量詞及其轄域就是前邊量詞的轄域。,2-2.5 自由變元與約束變元 在謂詞公式中的客體變元可以分成兩種， 一種是受到量詞約束的，一種是不受量詞 約束的。請看下面公式： x(F(x,y)yP(y)Q(z) (x,y)中的x在x的轄域內，受到x的 約束，而其中的y不受x的約束。 P(y)中的y在y的轄域內，受y的約束。 Q(z)中的z不受量詞約束。,定義：如果客體變元x在x或者x的轄域內，則稱x在此轄域內約束出現(xiàn)，并稱x在此轄域內是約束變元。否則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).對約束變元用什么符號表示無關緊要。就是說xA(x)與yA(y)是一樣的。這類似于計算積分與積分變元無關，即積分f(x)dx 與f(y)dy 相同。 (2).一個謂詞公式如果無自由變元，它就表示一個命題。 例如 A(x)表示x是個大學生。xA(x)或者xA(x)就是個命題了，因為它們分別表示命題“有些人是大學生”和“所有人都是大學生”。,(3).一個n元謂詞P(x1,x2,xn)，若在前邊添加k個量詞，使其中的 k個客體變元變成約束變元，則此 n元謂詞就變成了n-k元謂詞。 例如P(x,y,z)表示x+y=z，假設論域是整數(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”,。 可見每當給z指定個整數(shù)a后，xyP(x,y,a)就變成了一個命題。所以謂詞公式xyP(x,y,z)就相當于只含有客體變元 z的一元謂詞了。,在一個謂詞公式中，如果某個客體變元既以約束變元形式出現(xiàn)，又以自由變元形式出現(xiàn)，就容易產生混淆。為了避免此現(xiàn)象發(fā)生，可以對客體變元更改名稱。 如 x(F(x,y)yP(y)Q(z) 約束變元的改名規(guī)則： (1).對約束變元可以更改名稱，改名的范圍是：量詞后的指導變元以及該量詞的轄域內此客體變元出現(xiàn)的各處同時換名。 (2).改名后用的客體變元名稱，不能與該量詞的轄域內的其它變元名稱相同。,例如x(P(x)Q(x,y)(R(x)A(x) 此式中的x 就是以兩種形式出現(xiàn)?？梢詫改名成 z(P(z)Q(z,y)(R(x)A(x) 對自由變元也可以換名字，此換名叫代入。 對自由變元的代入規(guī)則： (1).對謂詞公式中的自由變元可以作代入。代入時需要對公式中出現(xiàn)該變元的每一處，同時作代入。 (2).代入后的變元名稱要與公式中的其它變元名稱不同 上例也可以對自由變元x作代入，改成 x(P(x)Q(x,y)(R(z)A(z),2-2.6 命題的符號化 在謂詞演算中，命題的符號化比較復雜，命題的符號表達式與論域有關系。例如 1.每個自然數(shù)都是整數(shù)。 (1).如果論域是自然數(shù)集合N，令 I(x)：x是整數(shù)，則命題的表達式為 xI(x) (2).如果論域擴大為全總個體域時，上述表達式xI(x)表示“所有客體都是整數(shù)”，顯然這是假的命題，此表達式已經不能表達原命題了。因此需要添加謂詞N(x)：x是自然數(shù)，用于表明x的特性，于是命題的符號表達式為 x(N(x)I(x),2.有些大學生吸煙。 (1).如果論域是大學生集合S，令A(x)：x吸煙，則命題的表達式為 xA(x) (2).如果論域擴大為全總個體域時，上述表達式xA(x)表示“有些客體吸煙”，就不是表示此命題了，故需要添加謂詞 S(x)：x是大學生，用于表明x的特性，于是命題的表達式為 x(S(x)A(x),從上述兩個例子可以看出，命題的符號表達式與論域有關。當論域擴大時，需要添加用來表示客體特性的謂詞，稱此謂詞為特性謂詞。特性謂詞往往就是給定命題中量詞后邊的那個名詞。如上面兩個例子中的“所有自然數(shù)”、“有些大學生”。 如何添加特性謂詞，這是個十分重要的問題，這與前邊的量詞有關。 特性謂詞的添加方法如下： 如果前邊是全稱量詞，特性謂詞后邊是蘊含聯(lián)結詞“”；如果前邊是存在量詞，特性謂詞后邊是合取聯(lián)結詞“”。,為什么必須這樣添加特性謂詞？ 分析一下特性謂詞和原謂詞所表示的概念之間的關系，得出下面的圖，從此圖可以得出如此添加特性謂詞的正確性。 令N:自然數(shù)集合，I:整數(shù)集合， S:大學生集合，A:煙民的集合。,I包含N x(N(x)I(x),吸煙大學生是S與A的交集 x(S(x)A(x),3.所有大學生都喜歡一些歌星。 令S(x)：x是大學生，X(x)：x是歌星， L(x,y)：x喜歡y。 則命題的表達式為 x(S(x)y(X(y)L(x,y) 4.沒有不犯錯誤的人。 此話就是“沒有人不犯錯誤”，“沒有”就是“不存在”之意。令P(x)：x是人，F(xiàn)(x)：x犯錯誤， 此命題的表達式為 x(P(x)F(x)或者 x(P(x)F(x) 5.不是所有的自然數(shù)都是偶數(shù)。 令N(x)：x是自然數(shù)，E(x)：x是偶數(shù)， 命題的表達式為: x(N(x)E(x)或者x(N(x)E(x),6.如果一個人只是說謊話，那么他所說的每句話沒有一句是可以相信的。 令A(x)：x是人，B(x,y)：y是x說的話， C(x):x是謊話，D(x)：x是可以相信的 命題的表達式為: 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.每個自然數(shù)都有唯一的后繼數(shù)。 令N(x)：x是自然數(shù)，A(x,y)：y是x的后繼數(shù)， E(x,y)：x=y 則命題的表達式為 x(N(x)y(N(y)A(x,y)z(N(z)A(x,z)E(y,z),有一個后繼數(shù),后繼數(shù)的唯一性,下面請同學們自己做練習第60頁(2),練習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),小結 1.命題的符號表達式形式與論域有關系。 論域擴大需要用特性謂詞對客體進行說明.注意如何添加特性謂詞(即要注意特性謂詞后邊是什么聯(lián)結詞)。 2.如果量詞前有否定符號，如“沒有.”“不是所有的.”等，可以按照字面直譯。如“x” “x.” 3.命題的符號表達式中所有客體變元必須都是約束變元，才表示命題。有時給定命題中有些量詞沒有明確給出，要仔細分析并寫出這隱含的量詞。 例如 a) 金子閃光，但閃光的不一定都是金子。G(x),F(x) x(G(x)F(x)x(F(x) G(x) b) 沒有大學生不懂外語。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謂詞演算的等價式與蘊涵式,在命題邏輯中，我們是通過對公式的命題變元賦值來討論永真式、永真蘊含式及等價公式的。 在謂詞演算中，也要討論一些重要的謂詞公式。但是由于謂詞公式中可能有命題變元、客體變元。對命題變元賦值比較容易，因為只有兩個值可賦。而對客體變元作指派卻不那么簡單，因為論域中的客體可能有無限個。另外謂詞公式的真值還與論域有關。,2-3.1 對謂詞公式賦值,定義：若將給定的謂詞公式中的命題變元，用確定的命題代替，對公式中的客體變元用論域中的客體代替，這個過程就稱之為對謂詞公式作指派，或者稱之 為對謂詞公式賦值。 例如公式 PN(x)，N(x)：x是自然數(shù)，論域為實數(shù)集合R， 令P：21，x=4 時，此公式變成PN(4)，它的真值就是“真”。,2-3.2 謂詞公式的永真式定義,定義：給定謂詞公式A，E是其論域，如果不論對公式A作任何賦值，都使得A的真值為真，則稱公式A在論域E上是永真式。如果不論對什么論域E，都使得公式A為永真式，則稱A為永真式。 例如，I(x)：x是整數(shù)，論域E為自然數(shù)集合，公式I(x)在E上就是永真式。 而公式 I(x)I(x)就是與論域無關的永真式。,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ù)，假設論域E是自然數(shù)集合，公式I(x)與N(x)在E上是等價的。 而公式N(x)I(x) 與N(x)I(x)就是與論域無關的等價的公式，即 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)就是與論域無關的永真式，所以(G(x)N(x)N(x)。,2-3.5. 重要公式,下面討論重要的謂詞等價公式和永真蘊含式。 一.由命題公式推廣出的公式 因一個不含自由變元的謂詞公式本身如xA(x)、xB(x) 就是命題。一個含有n個自由變元的謂詞公式，賦予論域 中的n個指定客體后就變成命題(例如S(a)、G(3,1)等)。 因此可以把此公式看成一個命題變元。所以在命題演算 的永真式中，將其中的同一個命題變元，用同一個謂詞 公式代替，所得到的公式也是永真式。這樣就可以將命 題演算中的等價公式和永真蘊含式推廣到謂詞演算中使 用。例如 A(x)A(x)B(x) PPQ x(A(x)B(x)x(A(x)B(x) PQPQ (xA(x)xB(x)xA(x)xB(x) 摩根定律,二.帶量詞的公式在論域內的展開式,先看一個例子，令A(x)：表示x是整數(shù)，B(x)：表示x是奇數(shù)，設論域是1,2,3,4,5，謂詞公式xA(x)表示論域內所有的客體都是整數(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)表示論域內有些客體是奇數(shù)，顯然公式xB(x)的真值也為真，因為B(1)、B(3)、B(5)的真值為真，于是有 xB(x)B(1)B(2)B(3)B(4)B(5) 一般地，設論域為a1,a2,.,an，則 1. xA(x)A(a1)A(a2).A(an) 2. xB(x)B(a1)B(a2).B(an),三.量詞否定公式,我們還是先用一個例子說明這個問題。令 (x)表示x是優(yōu)等生，論域是某班級的學生集合。 xA(x)表示：不是所有人都是優(yōu)等生。 xA(x)表示：有些人不是優(yōu)等生。 xA(x)表示：沒有人是優(yōu)等生。 xA(x)表示：所有人都不是優(yōu)等生。 從這個例子可以看出 “不是所有人都是優(yōu)等生?！迸c“有些人不是優(yōu)等生?！笔堑葍r的。 “沒有人是優(yōu)等生。”與“所有人都不是優(yōu)等生?！笔堑葍r的。于是有：,1. xA(x)xA(x) 2. xA(x)xA(x) 對這兩個公式可以證明如下： 證明：設論域為a1,a2,.,an，則 xA(x)(A(a1)A(a2).A(an) A(a1)A(a2).A(an)xA(x) 類似可以證明另一個公式。 從這兩個公式，可以總結出如下規(guī)律：將量詞前的“”移到量詞的后邊，或者將量詞后的“”移到量詞的前邊時，量詞也隨著改變，如果原來是全稱量詞改成存在量詞，如果原來是存在量詞改成全稱量詞。所以我們也把這兩個公式稱為量詞轉換公式。,四.量詞轄域的擴充公式,如果是個不含客體變元x的謂詞公式，且不在x和x的轄域內，可以將放入x和x的轄域內。即得如下公式： 1. xA(x)Bx(A(x)B) 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),上述公式我們只證明三個。 證明：設論域為a1,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) 在使用公式7.、8.時，要特別注意，量詞的轄域擴充后，量詞發(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) 證明：設論域為a1,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.不是等價公式，而是永 真蘊含式。 例如公式3.由xA(x)xB(x)不能推出x(A(x)B(x)， 我們可以舉一個反例，設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. x(A(x)B(x)xA(x)xB(x) 證明：假設前件x(A(x)B(x)為真， 則論域中至少有一個客體a，使得 A(a)B(a)為真，于是A(a)和B(a)都為 真，所以有xA(x)以及xB(x)為真，進而得xA(x)xB(x)為真。于是有 x(A(x)B(x)xA(x)xB(x),下面利用公式3.證明公式4.。 證明：因為公式3.中的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) 應用公式 PQQP 得 xA(x)xB(x)x(A(x)B(x) 公式4.得證。 在使用公式4.的時候，特別要注意蘊含式的方向，不要搞錯。,六其它公式,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) 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),七兩個量詞的公式,在A(x,y)前有兩個量詞，如果兩個量詞是相同的，它們的次序是無關緊要，但是如果是不同的，它們的次序就不可以隨便交換。例如設 A(x,y)表示“x+y=0”,論域為：實數(shù)集合， xyA(x,y)表示“對于任意給定的一個實數(shù)x,可以找到一個y,使得x+y=0”,這是一個為“真”的命題。而交換量詞后 yxA(x,y) 表示“存在一個實數(shù)y,與任意給定的一個實數(shù)x之和都等于0”,這是一個為“假”的命題。,有如下一些公式： 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),為了便于記憶，用下面圖形表示上面八個公式。,實際上，根據(jù)具有傳遞性，還可以派生出一些公式。下面我們只證明一個等價公式。用謂詞邏輯推理方法很容易證明上面那些永真蘊涵式，在此就不證明了。下面證明公式1.。 證明：設論域為a1,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é)小結： 熟練掌握謂詞等價公式和永真蘊涵式的證明方法及應用。 作業(yè)題： P66 (3) b) P71 (2) d), (6) 面作做個練習P71(1) c),練習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(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ī)范形式。這 里主要介紹前束范式-所有量詞都在公式前邊約束變元。 1.前束范式定義： 如果一個謂詞公式符合下面條件，它就是前束范式： 所有量詞前面都沒有聯(lián)接詞； 所有量詞都在公式的左面； 所有量詞的轄域都延伸到公式的末尾。 例如 yxz(A(x)(B(x,y)C(x,y,z) x(x)B(x) 就是前束范式，而 xA(x)yB(y) xy(A(x)(B(x,y)zC(z) xA(x)B(x) 這三個就不是前束范式。,2.前束范式的寫法 給定一個帶有量詞的謂詞公式， 1)消去公式中的聯(lián)接詞和(為了便于量詞轄域的擴充)； 2)如果量詞前有“”，則用量詞否定公式將“”后移。再用摩根定律或求公式的否定公式，將“”后移到原子謂詞公式之前。 3)用約束變元的改名規(guī)則或自由變元的代入規(guī)則對變元換名(為量詞轄域擴充作準備) 4)用量詞轄域擴充公式提取量詞，使之成為前束范式形式。,例1. xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) xA(x)yB(y) (換元) x(A(x)yB(y) (量詞轄域擴充) xy(A(x)B(y) 另一個方法：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) (量詞轉換) x(P(x)R(x)(xP(x)Q(x) (后移) x(P(x)R(x)(yP(y)Q(z) (換變元) x(P(x)R(x)y(P(y)Q(z) (擴量詞轄域) xy(P(x)R(x)(P(y)Q(z)(擴量詞轄域) 3.前束析取范式與前束合取范式： 前束析取范式:前束范式中量詞后的括號內是析取范式形式。 前束合取范式:前束范式中量詞后的括號內是合取范式形式。 上例的前束析取范式為: xy(P(x)R(x)(P(y)Q(z) 上例的前束合取范式為: xy(P(x)R(x)P(y)(P(x)R(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ī)則，是處理量詞的，因為推理時要使用不含量詞的命題公式，所以要去掉量詞，如果結論有量詞，還要添加量詞。 下面介紹四個新規(guī)則：,一.全稱特指規(guī)則 US (Universal Specialization) 形式： xA(x)A(c) (其中c是論域內指定客體) 含義：如果xA(x)為真，則在論域內任 何指定客體c，都使得A(c)為真。 作用：去掉全稱量詞。 要求：c不是A(x)中的符號。,二.存在特指規(guī)則ES(Existential Specialization) 形式： xA(x)A(c) (其中c是論域內指定客體) 含義：如果xA(x)為真，則在論域內指定客體c， 都使得A(c)為真。 作用：去掉存在量詞。 要求： c不是A(x)中的符號。 用ES指定的客體c不應該是在此之前用US規(guī)則或者用ES規(guī)則所指定的客體c(即本次用ES特指客體c，不應該是以前特指的客體)。 請看下面兩個例子：,例1. 令A(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是論域內指定客體) 含義：如果在論域內指定客體c使得 A(c)為真，則xA(x)為真。 作用：添加存在量詞。 要求：x不是A(c)中的符號。,四.全稱推廣規(guī)則UG (Universal Generalization) 形式： A(c)xA(x) (其中c是論域內任何指定客體) 含義：如果在論域內任何指定客體c都使 得A(c)為真，則xA(x)為真。 作用：添加全稱量詞。 要求：x不是A(c)中的符號。 c一定是任意的客體，否則不可全 稱推廣。,例1 所有金屬都導電。銅是金屬。 故銅導電。 令 M(x):x是金屬。C(x):x導電。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(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) T I11 xB(x) EG 問題在哪里？,例3 不認識錯誤的人，也不能改正錯誤。有些誠實的人改正了錯誤。所以有些誠實的人是認識了錯誤的人。 設A(x):x是認識錯誤的人。 B(x):x改正了錯誤。C(x):x是誠實的人。 符號化為： 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) T E1 C(c)A(c) T I9 x(C(x)A(x) EG ,例4 一些病人喜歡所有醫(yī)生。任何病人都不喜歡庸醫(yī)。所以沒有醫(yī)生是庸醫(yī)。 設: 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(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 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,課堂練習P79(1)d)改成： x(A(x)B(x),x(B(x)C(x),xC(x)x(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 xP(x)xQ(x) CP,用反證法證明例5： x(P(x)Q(x) xP(x)xQ(x) (xP(x)xQ(x) P(假設前提) (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(x,y) UG 作業(yè)：79頁 c)d) 、 推理時的注意事項：,推理時注意事項：,1.注意使用ES、US、EG、UG的限制條件。 2.對于同一個客體變元，既有帶也有帶的前提，去量詞時，應先去后去，這樣才可以特指同一個客體 c. 3.去量詞時，該量詞必須是公式的最左邊的量詞，且此量詞的前邊無任何符號，它的轄域作用到公式末尾。 下面的作法是錯誤的： 正確作法是： 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) xy(P(x)Q(y) T(3) E (5) y(P(a)Q(y) ES(4) 實際上x的轄域擴 (6) P(a)Q(b) ES(4) 充后量詞改成為x (7) P(a)Q(b) T(5)E,下面的作法是錯誤的： 正確作法是： xP(x) P xP(x) P P(c) US (2) xP(x) T(1)E 實際上中不是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的生母，顯然是個假命題. 另外X是公式A的子公式，且XY,如果用Y替換A中X而得 到B，那么不一定有AB。例如PQP,而(PQ)P 是不成立的。US和ES規(guī)則都是蘊涵式，所以不可對一個 子公式用這些規(guī)則。 4.添加量詞時，也要加在公式的最左邊，(即新加的量詞前也無任何符號！)且其轄域作用到公式的末尾。,第二章 小結,本章重點掌握內容： 1.各基本概念清楚。 2.會命題符號化。 3.熟練掌握等價公式和永真蘊涵式。 4.會寫前束范式。 5.熟練掌握謂詞邏輯的三種推理方法。,第二章 習題課,一. 命題符號化 60頁(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),62頁(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)設R(x):x是實數(shù)，G(x,y):xy x(R(x)y(R(y)G(y,x) c)設R(x):x是實數(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)設N(x):x是數(shù)，A(x,y):y是x的后繼數(shù) x(N(x)A(x,1) (6)設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.每個人的叔叔都是他父親的弟弟。 設：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整除并且不能被100整除的為閏年. 或者年號 能被400整除的也是閏年.” 設 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)(PxQ(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) xR(x)zS(x,z) y(P(y)(R(y)Q(y) tR(t)uS(x,u) (5)a)對自由變元代入 (yA(x,y)xB(x,z) xzC(x,y,z) (yA(u,y)xB(x,v) xzC(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 xy(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)(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) 第步錯，由到用的是公式： x(A(x)B(x)(xA(x)xB(x) 無此公式，而是 x(A(x)B(x) xA(x)xB(x)，應將中的換成 即：,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) 因為由公式E18 PQQP x(A(x)B(x) xA(x)xB(x) ， P Q 得 (xA(x)xB(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(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)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頁(2)a)用CP規(guī)則證明 x(P(x)Q(x) xP(x)x Q(x) 因為xP(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)x Q(x) CP,(3)a)所有有理數(shù)是實數(shù)，某些有理數(shù)是整數(shù)，因此某些實數(shù)是整數(shù)。 設Q(x):x是有理數(shù) R(x):x是實數(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)任何人如果他喜歡步行，他就不喜歡乘汽車；每個人或者喜歡乘汽車或者喜歡騎自行車。有的人不愛騎自行車，因此有的人不愛步行。 設 A(x):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 I A(a)B(a) T I x(A(x)B(x) EG ,c)每個大學生不是文科生就是理工科生，有的大學生是優(yōu)等生，小張不是理工科生，但他是優(yōu)等生，因此如果小張是大學生，他就是文科生。 設 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) 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,補充題：小楊、小劉和小林為高山俱樂部成員，該俱樂 部的每個成員是個滑雪者或登山者。沒有一個登山者喜 歡雨。而所有滑雪者都喜歡雪。凡是小楊喜歡的，小劉 就不喜歡。小楊喜歡雨和雪。試證明該俱樂部是否有個 是登山者而不是滑雪者的成員。如果有，他是誰？ 設：M(x):x是高山俱樂部成員。H(x):x是滑雪者。 D(x):x是登山者。L(x,y):x喜歡y。 a:小楊；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(b) US M(b) P H(b)D(b) T I11 D(b) T I10 D(b)H(b) T ,第二章 謂詞邏輯,到此結束,