謂詞邏輯的基本概念.ppt

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