第二章謂詞邏輯

1、第二章 謂詞邏輯2014-2015 學(xué)年第二學(xué)期陳磊 在命題邏輯中，把命題分解到原子命題為止，認(rèn)為原子命題是不能再分解的，僅僅研究以原子命題為基本單位的復(fù)合命題之間的邏輯關(guān)系和推理。 有些推理用命題邏輯就難以確切地表示出來。例如，著名的蘇格拉底三段論推理：所有的人都是要死的，蘇格拉底是人，所以蘇格拉底是要死的。 根據(jù)常識，認(rèn)為這個推理是正確的 但無法用命題邏輯給予推證 問題在哪里呢? 這類推理中，各命題之間的邏輯關(guān)系不是體現(xiàn)在原子命題之間，而是體現(xiàn)在構(gòu)成原子命題的內(nèi)部成分之間，即體現(xiàn)在命題結(jié)構(gòu)的更深層次上。 在研究某些推理時，有必要對原子命題作進一步分析，分析出其中的客體詞，謂詞和量詞，研究它

2、們的形式結(jié)構(gòu)的邏輯關(guān)系、正確的推理形式和規(guī)則，這些正是謂詞邏輯的基本內(nèi)容。2.1 謂詞的概念與表示 命題是具有真假意義的陳述句 從語法上分析，一個陳述句由主語和謂語兩部分組成。 【例】電子計算機是科學(xué)技術(shù)的工具 主語: 電子計算機 謂語: 是科學(xué)技術(shù)的工具 主語是客體, 它可以是具體的,也可以是抽象的 小王, 老師 唯物主義 謂語: 用以刻劃客體的性質(zhì)或關(guān)系【例】張三是大學(xué)生, 李四是中學(xué)生 兩個命題的謂語不同, 表明對應(yīng)的兩個客體的身份不同 引入一種符號表示謂語, 再引入一種方法表示客體名稱 一般用大寫字母表示謂詞, 用小寫字母表示客體名稱 用謂詞表達命題必須包括客體和謂詞兩部分【例】A表示

3、“是大學(xué)生”, B表示“是中學(xué)生” c表示“張三”, d表示“李四” A(c)表示 “張三是大學(xué)生” B(d)表示 “李四是中學(xué)生” “b是A”類型的命題可用A(b)表示【例】5大于3 B表示 “大于” a表示 “5”, b表示 “3” 5大于3可用B(a, b)表示 類似于“a大于b”類型的命題, 可用B(a,b)表示 【例】小明站在小李和小王之間 L表示 “站在和之間” a表示 “小明”, b表示 “小李”, c表示“小王” 小明站在小李和小王之間可用L(a, b, c)表示 有三個客體的命題可用L(a, b, c)表示 A(b)一元謂詞; B(a, b)二元謂詞; L(a, b, c)三

4、元謂詞 一般來說, n元謂詞需要n個客體名稱插入到固定的位置上, 如果A為n元謂詞, a1,a2,an是客體名稱, 則A(a1,a2,an)就可以成為一個命題 一元謂詞表達了客體的“性質(zhì)”, 而多元謂詞表達了客體之間的“關(guān)系” 單獨一個謂詞不是完整的命題 謂詞填式: 謂詞字母后填以客體所得的式子 在多元謂詞中, 客體出現(xiàn)的次序與事先約定有關(guān)【例】 L(a, b, c)與L(b, a, c)如果a, b, c表示三個不同的客體,則表示兩個不同的命題2.2 命題函數(shù)與量詞【例】H表示謂詞 “能夠到達山頂”, l表示客體 “李四”, t表示客體 “老虎”, c表示客體 “汽車”. H(l): 李四能

5、夠到達山頂 H(t): 老虎能夠到達山頂 H(c): 汽車能夠到達山頂 上例有一個共同的形式 H(x). 當(dāng)x分別取l, t, c時, 分別表示不同的命題 H(x)本身不是一個命題, 只有當(dāng)x取特定的客體時, 才能確定一個命題 多元有類似情況 如L(x,y) H(x)與函數(shù)表示類似 定義 2-2.1 由一個謂詞, 一些客體變元組成的表達式稱為簡單命題函數(shù) n元謂詞就是有n個客體變元的命題函數(shù) 特殊情況: n=0時, 稱為0元謂詞, 它本身就是一個命題 命題是n元謂詞的特殊情況 由一個或n個簡單命題函數(shù)以及聯(lián)結(jié)詞組合而成的表達式稱為復(fù)合命題函數(shù) 【例】S(x)表示 “x學(xué)習(xí)很好”; W(x)表示

6、 “x工作很好” S(x)表示 “x學(xué)習(xí)不是很好”; S(x) W(x)表示 “x學(xué)習(xí)和工作都很好”; 【例】H(x,y)表示 “x比y長得高”, l表示李四, c表示張三 H(l,c)表示 “李四不比張三長得高” 命題函數(shù)不是命題, 只有客體變元取特定名稱時, 才能成為命題【例】R(x)表示 “x是大學(xué)生” 1. x的討論范圍是某大學(xué)的學(xué)生, 則R(x)為永真式 2. x的討論范圍是某中學(xué)的學(xué)生, 則R(x)為永假式 3. x的討論范圍是某劇場里的觀眾, 則R(x)可能為真也 可能為假【例】Q(x, y)表示 “x比y重” 1. x,y指人或物時, 它是一個命題 2. x,y指實數(shù)時, 它不

7、是一個命題對于一個命題函數(shù)而言, 客體變元在哪些范圍內(nèi)取值, 對其是否成為命題及命題的真值有很大的影響命題變元的論述范圍稱作個體域各個個體域綜合在一起作為論述范圍的域稱為全總個體域【例】S(x)表示 “x是大學(xué)生”, x的個體域為某單位的職工 S(x)到底表示如下哪種情況呢? 1. 某單位職工都是大學(xué)生 2. 某單位存在一些職工是大學(xué)生 目前所學(xué)的符號還是不能很好地表達日常生活中的各種命題 量詞: 用以刻畫 “所有的”和 “存在一些”的不同概念1. 全稱量詞 日常生活和數(shù)學(xué)中常用的“一切的”，“所有的”，“每一個”，“任意的”，“凡”，“都”等詞統(tǒng)稱為全稱量詞符號化為“”(x)，(y)等表示個

8、體域里的所有個體(x)F(x)和(y)G(y)等分別表示個體域中的所有個體都有性質(zhì)F和都有性質(zhì)G2. 存在量詞 “存在”，“有一個”，“有些”，“至少有一個”等詞統(tǒng)稱為存在量詞 符號化為“” (x)，(y)等表示個體域里有些個體 (x)F(x)和(y)G(y)等分別表示在個體域中存在個體具有性質(zhì)F和存在個體具有性質(zhì)G。 全稱量詞與存在量詞統(tǒng)稱為量詞?！纠總€體域是人類集合，對下列命題符號化。 凡人要死。 有的人是研究生。 解： 令F (x)：x要死。 命題“凡人要死?！狈柣癁椋?x)F (x) 令G(x)：x是研究生。 命題“有的人是研究生。”符號化為：(x)G(x) 在命題函數(shù)前加上量詞(

9、x)和(x)分別叫做個體變元x被全稱量化和存在量化。 一般地說，命題函數(shù)不是命題，如果對命題函數(shù)中所有客體變元進行全稱量化或存在量化，該命題函數(shù)就變成了命題?！纠繉ο铝忻}符號化，并在，三個個體域中考察命題的真值。 命題： 所有數(shù)小于5。 至少有一個數(shù)小于5。 個體域： -1，0，1，2，4 3，-2，7，8 15，20，24 解：設(shè)L(x)：x小于5。 “所有數(shù)小于5?！狈柣癁椋?x) L(x) 在個體域，中，它們的真值分別為：真，假，假。 “至少有一個數(shù)小于5?！狈柣癁椋?x) L(x)在個體域，中，它們的真值分別為：真，真，假。 命題函數(shù)中的個體變元被量化以后變成命題，其真值與個體

10、域的選定有關(guān). 為了統(tǒng)一，我們今后使用全總個體域 其它個體域用一個謂詞來表示，叫做特性謂詞。特性謂詞加入的方法為： 對全稱量詞，特性謂詞作為條件命題的前件加入。 對存在量詞，特性謂詞作為合取項加入?！纠繉ο铝忻}在，兩個個體域中符號化。 命題： 所有老虎是要吃人。 存在一個老虎要吃人。 個體域： 所有老虎組成的集合。 全總個體域。 解：設(shè)A(x)：x是要吃人的。 個體域為所有老虎的集合。 符號化為 (x)A(x) 符號化為 (x)A(x) 個體域為全總個體域。設(shè)特性謂詞T(x)：x是老虎。 符號化為 (x)(T(x)A(x) 符號化為 (x) (T(x)A(x) 作業(yè): (1) 2.3 謂詞

11、公式與翻譯 我們把A(x1,x2,xn)稱為謂詞演算的原子公式, 其中x1,x2,xn是客體變元 定義2-3.1按下列規(guī)則構(gòu)成的表達式稱為謂詞演算的合式公式，簡稱謂詞公式。 原子謂詞公式是合式公式。 若A是合式公式，則A是合式公式。 若A和B是合式公式，則(AB)，(AB)，(AB)和(AB)是合式公式。 如果A是合式公式，x是A中出現(xiàn)的任意個體變元，則(x)A，(x)A是合式公式。 只有有限次地應(yīng)用、所得的公式是合式公式。 謂詞公式也有以下約定： 最外層的括號可以省略。 如果按、在運算中的優(yōu)先級別，省略括號后不改變原來的運算次序，可以省略括號，但量詞后面括號不能省略?！纠坎⒎敲總€實數(shù)都是有

12、理數(shù)。 解：設(shè)R(x)：x是實數(shù) Q(x)：x是有理數(shù) 該命題符號化為：(x)(R(x)Q(x) 【例】沒有不犯錯誤的人。 解：設(shè)M(x)：x是人 F(x)：x犯錯誤 此命題可以理解為：存在一些人不犯錯誤，這句話是不 對的。此時，符號化為：(x) (M(x)F(x) ) 也可以理解為：任何人都是要犯錯誤的。此時，符號化為：(x) (M(x)F(x) 【例】并不是所有的兔子都比所有的烏龜跑得快。 解：設(shè)F(x)：x是兔子。 G(x)：x是烏龜。 H(x,y)：x比y跑得快。 該命題符號化為：(x) (y) (F(x)G(y)H(x,y) 作業(yè): (2) (3) (4) 2.4 變元的約束 給定一

13、個謂詞公式A，其中有一部分公式形如(x)B(x)或(x)B(x) 、后面所跟的x叫做量詞的指導(dǎo)變元或作用變元 B(x)叫做相應(yīng)量詞的作用域或轄域。 在轄域中，x的所有出現(xiàn)稱為約束出現(xiàn)，x稱為約束變元 B中不是約束出現(xiàn)的其它變元的出現(xiàn)稱為自由出現(xiàn)，這些變元稱自由變元。 對于給定的謂詞公式，能夠準(zhǔn)確地判定它的轄域、約束變元和自由變元是很重要的。 通常，一個量詞的轄域是某公式A的一部分，稱為A的子公式。因此，確定一個量詞的轄域即是找出位于該量詞之后的相鄰接的子公式，具體地講： 若量詞后有括號，則括號內(nèi)的子公式就是該量詞的轄域； 若量詞后無括號，則與量詞鄰接的子公式為該量詞的轄域?！纠空f明下列各式量

14、詞的轄域，找出約束變元和自由變元。 (x)P(x)Q(y) (x) (P(x)(y)Q(x,y) (x) P(x)(y)Q(x,y) (x)(y)(P(x,y)Q(y,z) (x) R(x,y) 解：(x)的轄域為P(x)，x是約束變元。 (x)的轄域為P(x)(y)Q(x,y)，(y)的轄域為Q(x,y)，x和y都是約束變元，無自由變元。 (x)的轄域為P(x)，(y)的轄域為Q(x,y)，P(x)中的x和Q(x,y)中的y是約束變元，Q(x,y)中的x是自由變元。 (x)和(y)的轄域為P(x,y)Q(y,z)，x, y是約束變元, z是自由變元; (x)的轄域為R(x,y)，x是約束變元

15、，y是自由變元 在一個公式中，同一個變元既可以是約束的，又可以是自由的，容易混淆?！纠?x)(y)(P(x,y)Q(y,z) (x) R(x,y) 約束變元與表示該變元的符號無關(guān) (x)P(x)與(y)P(y)，(x)P(x)與(y)P(y)都具有相同意義 可以對約束變元換名，以避免混淆 為了使換名后的公式中出現(xiàn)的變元要么是約束的，要么是自由的，我們提出如下的換名規(guī)則： 對約束變元可以換名，其更改變元名稱范圍是量詞中的指導(dǎo)變元，以及該量詞轄域中的所有該變元，公式的其余部分不變。 換名時一定要更改成轄域中沒有出現(xiàn)的變元名，最好是公式中沒有的變量名?！纠繉?x)(y)(P(x,y)Q(y,z)

16、(x)R(x,y)中的約束變元y換名。 解：用u置換約束變元y。換名后為： (x)(u)(P(x,u)Q(u,z)(x) R(x,y) 不能換成： (x)(u)(P(x,u)Q(y,z)(x) R(x, y) 也不能換成：(x)(z)(P(x, z)Q(z,z)(x) R(x,y) 也不能換成：(x)(u)(P(x,u)Q(u,z)(x) R(x,u) 對公式中的自由變元也可以進行更改，用來解決公式中約束變元與自由變元的同名問題。這種更改叫做代入，代入規(guī)則是： 對于謂詞公式中的自由變元可以代入，代入時需對公式中該變元自由出現(xiàn)的每處進行。 代入的變元與原公式中其他變元的名稱不能相同?！纠繉?x

17、)(P(y)R(x,y)(y)Q(y) 中的自由變元y進行代入。 解：用z代換y，代入后為： (x)(P(z)R(x,z)(y)Q(y) 不能換成： (x)(P(x)R(x,x)(y)Q(y) 或 (x)(P(z)R(x,y)(y)Q(y) 量詞作用域中的約束變元，當(dāng)論域的元素是有限時?？腕w變元的所有可能的取代是可枚舉的 設(shè)論域元素為a1,a2,an (x)A(x) A(a1) A(a2) A(an) (x)A(x) A(a1) A(a2) A(an)【例】A表示“是大學(xué)生”，論域為劇場里的觀眾，并用ai表示第i個觀眾 所有的觀眾都是大學(xué)生可表示為 A(a1) A(a2) A(an) 有一些觀

18、眾是大學(xué)生可表示為A(a1) A(a2) A(an) 量詞對變元的約束與量詞的次序有關(guān)【例】(1)(y)(x)(xy-2)表示任何的y均有x，使得xy-2 (2) (x)(y)(xy-2)表示存在x, 對于所有的y，有xy，設(shè)A(y)(x)G(x,y)， A(y)滿足條件，一定能推出(z)A(z)(z)(x)G(x,z)(z)(x)(xz)，這是一個真命題。 若推成(x)A(x)(x)(x)G(x,x)(x)(x)(xx)，就產(chǎn)生了錯誤，因為這是一個假命題。錯誤的原因是違背了條件。3.存在指定規(guī)則(ES規(guī)則) (x)A(x)A(c) 此式成立的條件是： c是個體域中的某個確定的客體，而不是客體

19、變元。 c是不出現(xiàn)在A(x)中的客體。 存在指定規(guī)則說明，若個體域中存在一些個體滿足謂詞A，則至少有某個確定的個體c滿足謂詞A?！纠吭O(shè)個體域為整數(shù)集合I，A(x)表示x是奇數(shù)，B(x)表示x是偶數(shù)。 (x)A(x)A(c): 若存在一些整數(shù)是奇數(shù)，令c為3，則c是奇數(shù)。這個推理是對的。 (x)B(x)B(d): 若存在一些整數(shù)是偶數(shù)，令d為4，則d是偶數(shù)。這個推理也是對的。 因此有下列推理成立： (x)A(x)(x)B(x)A(c)B(d) 而下列推理是錯誤的： (x)A(x)(x)B(x)A(c)B(c) (x)A(x)(x)B(x)A(d)B(d)4.存在推廣規(guī)則(EG規(guī)則) A(c)(

20、x)A(x) 此式成立的條件是： c是個體域中確定的客體。 x不能是出現(xiàn)在A(c)中的客體變元。 存在推廣規(guī)則說明：對于個體域中的某個個體c滿足謂詞A，當(dāng)然有(x)A(x)。【例】證明蘇格拉底論證：凡人要死。蘇格拉底是人，蘇格拉底要死。 設(shè)： H(x)：x是人。 M(x)：x是要死的。 s：蘇格拉底。 本題要證明：(x)(H(x)M(x)H(s)M(s) 證明： (x)(H(x)M(x) P H(s)M(s) US H(s) P M(s) T 【例】證明(x)(H(x)M(x)，(x)H(x)(x)M(x) 證明： (x)H(x) P H(c) ES (x)(H(x)M(x) P H(c)M(c) US M(c) T (x)M(x) EG 若把,寫在,的后面，得到如下的推理： (x)(H(x)M(x) P H(c)M(c) US (x)H(x) P H(c) ES M(c) T (x)M(x) EG 這個推理在邏輯上是錯誤的。因為中的c為個體域中任意一個客體，用ES規(guī)則由推到不能選擇中的c，因為它要選的客體和中的客體c不一定是同一個客體，故推理是錯誤的?！纠孔C明 (x)(A(x)B(x)，(x)A(x)(x)B(x) 證明：用直接法證明。 (x)(A(x)B(x) P A(s)B(s) US (x)A(x) P A(s) US B(s) T