謂詞邏輯的基本概念.ppt

,第二章 謂詞邏輯,第一講,原因是三個(gè)原子命題不能把第1個(gè)命題和第2命題的共同屬性“人”表示出來。蘇格拉底是人，所有“人”具有的共同屬性“死亡”他也應(yīng)該有，但在命題邏輯中無法實(shí)現(xiàn)。這就是命題邏輯的局限性。為了解決這個(gè)問題需要引入謂詞邏輯的有關(guān)概念。,21 謂詞邏輯的基本概念 211 謂詞及其表示 命題是一個(gè)有唯一真值的陳述句。陳述句主要由主語、謂語、賓語和補(bǔ)語組成。其中主語、謂語是句子的主要成份。 主語是謂語描述的對(duì)象，稱為個(gè)體或客體。 謂語用于描述主語的性質(zhì)和關(guān)系，是陳述句的主體部分。,定義2-1 可以獨(dú)立存在的人、物、事稱為個(gè)體或客體。,定義2-2 在謂詞邏輯中，刻劃個(gè)體性質(zhì)和關(guān)系的 謂語稱為謂詞。,例2-1： 張三是大學(xué)生。 李四是大學(xué)生。 我們 用大寫字母S表示“是大學(xué)生”， 用小寫字母a、b分別表示“張三”和“李四”。 上述兩個(gè)命題可表示為： S（a）：張三是大學(xué)生。 S（b）：李四是大學(xué)生。,謂詞可分為一元謂詞和多元謂詞。在命題中若謂詞只聯(lián)系一個(gè)客體，則稱之為一元謂詞。一元謂詞表示客體的屬性。若謂詞聯(lián)系著n個(gè)客體，則稱之為n元謂詞。多元謂詞表示客體之間的聯(lián)系。,例2-2 冰比水密度小。 4大于3 解： 用D表示 比密度小， G表示大于， 則上述謂詞命題可以表示為： D（冰,水）和G（4,3）。 不難發(fā)現(xiàn)，在多元謂詞中，個(gè)體在謂詞中出現(xiàn)的次序不是任意的，它將直接影響謂詞命題的真值。在多元謂詞公式中，個(gè)體在謂詞公式出現(xiàn)的次序一旦約定就不能更改。 如果更改便變成不同的命題，其真值也發(fā)生變化。如上例中改為D（水，冰）和G（3，4），變成命題“水比冰密度小”和“3大于4”，其真值都為假。,21 常元與變?cè)?在謂詞邏輯中，表示特定個(gè)體的詞稱為個(gè)體常元。個(gè)體常元可以是代表個(gè)體的標(biāo)識(shí)符，也可以直接引用個(gè)體的名稱。如上述例2-1中a代表“張三”，b代表“李四”；在例2-中直接使用個(gè)體的名稱，如“水”、“冰”、“”、“”等。 在謂詞邏輯中，用來表示未知或泛指的個(gè)體的詞稱為個(gè)體變?cè)?。其?biāo)識(shí)符常用小寫字母x，y，z表示。例如用(x)表示x是素?cái)?shù)，Q(x)表示x是有理數(shù)。(x) 和Q(x)不是命題，只有用具體的個(gè)體取代其中的個(gè)體變?cè)蟛攀敲}，才有真值。,22 命題 函數(shù)及量化 221 命題 函數(shù) 單獨(dú)的謂詞不是命題，在謂詞后面的括號(hào)中填上代表個(gè)體的標(biāo)識(shí)符所得的式 子 稱為謂詞填式 。 如果在謂詞填式 的括號(hào)中填入的是個(gè)體常元，則該謂詞填式 是一個(gè)命題。在謂詞填 式 的括號(hào)中填入的是個(gè)體變?cè)?，則稱該謂詞 填式為命題函數(shù)。,定義2-3 由一個(gè)謂詞和一些個(gè)體變?cè)M成的表達(dá)式 稱為原子命題函數(shù)。用邏輯聯(lián)結(jié)詞把一個(gè)或多個(gè)原子命題函數(shù)連接而成的表達(dá)式 稱為復(fù)合命題函數(shù)。,如上述所舉例子中S（x）、D（x,y）、G（x,y）都是簡(jiǎn)單命題函數(shù)，其中x、y為個(gè)體變?cè)?把不含個(gè)體變?cè)拿}函數(shù)稱為0元謂詞。例如，上述的D（冰,水）和G（4，3）等都是0元謂詞， 0元謂詞本身就是命題。 命題邏輯中的原子命題都可以用0元謂詞表示，因此，可以將命題邏輯看成是謂詞邏輯的特殊情況。 值得注意的是，在謂詞演算中邏輯聯(lián)結(jié)詞的含義與命題演算中完全相同，且命題演算中的公式在謂詞演算中完全適用。,例2-3 將下列命題 符號(hào)化： （1）存在既是素?cái)?shù)又是偶數(shù)的數(shù)。 解：令：F(x):x是素?cái)?shù)； G(x):x是偶數(shù)； 則命題 符號(hào)化為：F(x)G(x)。,（2）只有努力學(xué)習(xí)才能取得好成績(jī)。 解： 令： G(x):x想取得好成績(jī)； H(x):x 努力學(xué)習(xí)； 則命題 符號(hào)化為： （3）在實(shí)數(shù)域中，若x比y大，y比大z，則x比z大。 解：設(shè)x、y、z是實(shí)數(shù)。 令：P(x,y): x比y大。 則命題 符號(hào)化為： P(x,y)P(y,z)P(x,z),定義2-4 個(gè)體變?cè)恼撌龇秶Q為個(gè)體域（或論域）。 各種個(gè)體域綜合在一起作為論述范圍稱為全總個(gè)體域。 個(gè)體域和全總個(gè)體域是相對(duì)的，它根據(jù)你討論的問題而定，同時(shí)它可以是有限的，也可以是無限的。,222 個(gè)體域,223 量 化 用具體個(gè)體的名稱取代個(gè)體變?cè)?，使命題函數(shù)成為命題的過程稱為代換，通過代換而得到的命題稱為命題函數(shù)的代換實(shí)例。由代換實(shí)例得到的命題是個(gè)別命題。 除代換外，我們還可以采用量化的辦法來確定命題，采用量化確定的命題是一個(gè)命題集合。 所謂量化是指出個(gè)體變?cè)趥€(gè)體域中的取值方式。 在謂詞邏輯中，個(gè)體域中個(gè)體變?cè)娜≈捣绞匠Ｓ玫挠幸韵聝煞N：,1.全稱量詞 如果命題函數(shù)個(gè)體變?cè)趥€(gè)體域中的取值方式是考慮論域中的所有個(gè)體，則這種量化稱為全稱量化。 如日常語言中的“所有的”、“任意的”、“每一個(gè)”等詞。 我們把“所有的”的英語短語“For All”中的“All”的第一個(gè)字母“A”倒寫為“” 作為全稱量詞符號(hào)?！皒 ”表示個(gè)體域中的所有個(gè)體，其中的“x”稱為指導(dǎo)變?cè)?。例如，“xP(x) ”就表示個(gè)體域中的所有個(gè)體都具有性質(zhì)P 。,例如：設(shè)論域?yàn)槿祟?H(x)：表示x是要呼吸的。 則xH(x)表示： 所有人都是要呼吸的。 例如：所有的自然數(shù)都是實(shí)數(shù)。 N(x) ：x是自然數(shù)。 R(x) ：x是實(shí)數(shù)。 則原命題可以表示為：,2.存在量詞 如果命題函數(shù)個(gè)體變?cè)趥€(gè)體域中的取值方式是考慮個(gè)體域中的部分個(gè)體，則稱為存在量化。 它對(duì)應(yīng)日常語言中的“存在著”、“有的”、“至少有一個(gè)”、“有一些”等詞。英語短語表示為“There Exist”，我們用“Exist”的第一個(gè)字母E的反寫為“”作為存在量詞符號(hào)?！皒 ”表示論域中存在某些個(gè)體，其中的“x”稱為指導(dǎo)變?cè)?。例如，“xP(x) ”表示論域中存在個(gè)體具有性質(zhì)P 。,例如：設(shè)論域?yàn)槿祟?S(x) ：表示x吸煙。 則x S(x) 表示有人 吸煙。 例如：有的學(xué)生在看書。 S(x) ：表示x是學(xué)生。 B(y) ：表示y是書籍。 R(x,y) ：表示x正在看y。 則原命題表示為：,P(x) 是不能確定真值的命題函數(shù)，其中的 x 是個(gè)體變?cè)?而 xP(x) 和xP(x) 都是可以確定真值的命題，其中的x再不起變?cè)淖饔?，已?jīng)受到量詞x、x 的限制。個(gè)體變?cè)艿搅吭~限制的過程 稱之為量化。,【說明】xP(x)和xP(x)與P(x)有著本質(zhì)的區(qū)別。,224 特性謂詞 命題函數(shù)的量化與個(gè)體域有關(guān)，個(gè)體域的指定不但影響命題的表達(dá)形式，而且影響命題的真值。 為了描述方便，將所討論的命題函數(shù)的個(gè)體域統(tǒng)一使用全總個(gè)體域。使用全總個(gè)體域后，對(duì)于每個(gè)個(gè)體變?cè)娜≈捣秶仨氂每虅潅€(gè)體特性的謂詞加以限制。 定義2-5 在全總個(gè)體域中, 表示具體個(gè)體域的謂詞稱為特性謂詞。 例如：所有人是要死的。 （1） 論域?yàn)槿祟悺?D(x) ：表示x是要死的。 符號(hào)化為：x D(x),（2）論域是全總個(gè)體域。 使用全總個(gè)體域，就必須使用特性謂詞來限制個(gè)體的取值范圍。 H(x) ：表示x是人類（特性謂詞）。 符號(hào)化為： 值得注意的是：在全稱量化中，特性謂詞常作為條件命題的前件。 例如：有人吸煙 （1）論域?yàn)槿祟悺?S(x) ：表示x吸煙。 符號(hào)化為： （2）論域?yàn)槿倐€(gè)體域。 此時(shí)就必須使用特性謂詞來限制個(gè)體的取值范圍。 H(x) ：表示x是人類 符號(hào)化為：,例如：存在既是偶數(shù)又是素?cái)?shù)的有理數(shù)。 論域?yàn)槿倐€(gè)體域。 Q(x) ：表示x是有理數(shù)。 E(x) ：表示x是偶數(shù)。 P(x) ：表示x是素?cái)?shù)。 原命題符號(hào)化為： 值得注意的是： 在存在量化中，特性謂詞常作為合取項(xiàng)。,225量化與代換實(shí)例 當(dāng)個(gè)體域?yàn)橛邢藜蠒r(shí)，例如個(gè)體域?yàn)橛邢藜痑1,a2,a3,an ，由量詞的定義可以知道，對(duì)于任意謂詞都有： （2-1） （2-2） 這就是量詞的消去規(guī)則，它可以將帶量詞的謂詞公式轉(zhuǎn)化成謂詞公式的代換實(shí)例。這一點(diǎn)非常重要，在謂詞邏輯的等價(jià)公式證明中常采用這個(gè)規(guī)則。,23謂詞合適公式與翻譯 231謂詞合適公式 在命題邏輯中引入了命題公式的概念，它是由命題常元、命題變?cè)?、命題聯(lián)結(jié)詞和圓括號(hào)按照一定的規(guī)律所組成的符號(hào)串。謂詞邏輯是命題邏輯的進(jìn)一步拓展，在謂詞邏輯中，也需要引入原子謂詞公式和謂詞合適公式(Well form formula簡(jiǎn)稱謂詞公式)的概念。,定義2-7 原子謂詞公式定義如下： (1) 一個(gè)命題是原子謂詞公式。 (2) 一個(gè)命題變?cè)窃又^詞公式。 (3) 由n 個(gè)個(gè)體變?cè)?及n 元謂詞所組成的命題函數(shù)也是一個(gè)原子謂詞公式。 原子謂詞公式簡(jiǎn)稱為原子公式。,定義2-8 謂詞公式定義如下： (1)一個(gè)原子公式是一個(gè)謂詞公式。 (2)若A是謂詞公式，則A 也是謂詞公式。 (3)若A、B是謂詞公式，則(AB) 、(AB) 、(AB) 、(AB) 也是謂詞公式。 (4)若A是謂詞公式，x是A中的個(gè)體變?cè)?，則xA(x) 、xA(x) 也是謂詞公式。 只有有限次地運(yùn)用規(guī)則(1)、(2)、(3)、(4)所得到的符號(hào)串才是謂詞公式。,注意: 謂詞公式中的某些圓括號(hào)也可以省 略,其規(guī)定與命題公式相同，但量詞后的圓括號(hào)不能省略，因?yàn)樗P(guān)系到量詞的作用范圍。,232謂詞公式的翻譯 與命題公式的翻譯類似，謂詞公式的翻譯同樣有兩個(gè)方 面，一是將自然語言描述的命題符號(hào)化，也稱形式化；二是將形式化的謂詞公式翻譯成自然語言描述的命題。在公式翻譯過程中，除注意聯(lián)結(jié)詞的選擇外，還必須注意量詞的選擇。 一、將自然語言描述的謂詞公式形式化 例2-4 每個(gè)人都會(huì)犯錯(cuò)誤 解：該命題可以說成“對(duì)于所有的x，如果x是人，則x會(huì)犯錯(cuò)誤”。 設(shè)H(x)：x 是人。 M(x)：x會(huì)犯錯(cuò)誤。 則命題可表示為：,例2-5 并非所有實(shí)數(shù)都是有理數(shù) 解：該命題可以說成“所有實(shí)數(shù)都是有理數(shù)是不對(duì)的”。 設(shè) R(x)：x是實(shí)數(shù)。 Q(x)：x是有理數(shù)。 則命題可表示為： 例2-6 盡管有的人聰明，但不是所有的人都聰明 解：該命題是由兩個(gè)并列的句子組成，即由兩個(gè)合取項(xiàng)組成。第一個(gè)合取項(xiàng)為“存在聰明的人”，第二個(gè)合取項(xiàng)是“不是所有的人都是聰明人”。 設(shè) H(x) ：x是人。 C(x)：x聰明。 則命題可表示為：,例2-7李濤無書不讀。 解：該命題即是說“李濤所有的書都讀”。 設(shè) P(x) ：x是書。 Q(y,x)：y讀x。 a: 李濤。 則命題可表示為： 例2-8有人無書不讀。 解：該命題可解釋為存在這樣的人，這種人所有書都讀。 H(y)：