謂詞邏輯的基本概念.ppt

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