【正文】 a：這只； b：那些。 謂詞公式： R(a) ? Q(b) ? F(a,b) 114 22 謂詞公式與翻譯 （續(xù)） 例題 5. 極限的定義：任給 ε 0，存在 δ 0，使得當(dāng) 0|xa|δ時(shí)有 |f(x)b|ε ，則稱 b 是 f(x)在 x→a 時(shí)的極限，記為 f(x)→ b（當(dāng) x→a ）。 下面用謂詞公式表示以上定義： 用 P(x,y)表示“ x大于 y” ， Q(x,y)表示“ x小于 y” ，則 以上定義的謂詞公式表示如下 ： (?ε )(?δ )(?x)(((P(ε ,0)?P(δ ,0)) ? Q(|xa|,δ ) ? P(|xa|,0))?Q(|f(x)b|,ε )) 115 22 謂詞公式與翻譯 定義： 謂詞公式的合式公式 ，可以由下述各條組成： （ 1）原子謂詞公式是合式公式。 （ 2）若 A是合式公式，則 ?A也是合式公式。 （ 3）若 A和 B都是合式公式，則 (A?B)， (A?B)、(A?B)和 (A? B)都是合式公式。 （ 4）若 A都是合式公式， x是出現(xiàn)在 A中的任何變?cè)?，則 (?x)A和 (?x)A都是合式公式。 （ 5）只有經(jīng)過(guò)有限次地應(yīng)用規(guī)則 (1)、 (2)、 (3)、(4)所得到的公式是合式公式。 謂詞合式公式簡(jiǎn)稱 謂詞公式 。 見書 P41關(guān)于字母表、項(xiàng)、原子公式、謂詞公式定義 原子公式 ： A(x1,x2,?,x n)，這里 x1,x2,?,x n是客體變?cè)? 116 變?cè)募s束 幾個(gè)名詞： （ 1）指導(dǎo)變項(xiàng)（作用變?cè)? （ 2）作用域（轄域） （ 3）約束出現(xiàn) （ 4）約束變項(xiàng)、自由變項(xiàng) （ 5）封閉的合式公式 117 24 變?cè)募s束 （續(xù)） 例題 1. 說(shuō)明以下各公式的作用域與變?cè)募s束情況。 a) (?x)(P(x)?Q(y)) (?x)的作用域是 P(x)?Q(y)， x為約束變?cè)? b) (?x)(P(x)?(?y)(R(x,y)) (?x)的作用域是 (P(x)?(?y)(R(x,y))， (?y)的作用域是 R(x,y)。 x,y為 約束變?cè)? 指導(dǎo)變?cè)? 作用域 118 24 變?cè)募s束 （續(xù)） c) (?x)(?y)(P(x,y)?Q(y,z))?(?x)P(x,y) (?x)(?y)的作用域是 (P(x,y)?Q(y,z)) x,y為約束變?cè)?z是自由變?cè)? (?x)的作用域是 P(x,y) x為約束變?cè)?y是自由變?cè)? 119 24 變?cè)募s束 （續(xù)） 約束變?cè)膿Q名規(guī)則： （ 1）對(duì)于約束變?cè)梢該Q名，其更改的變?cè)Q范圍是量詞中的指導(dǎo)變?cè)?，以及該量詞作用域中所出現(xiàn)的該變?cè)?，在公式的其余部分不變? （ 2）換名時(shí)一定要換為作用域中沒有出現(xiàn)過(guò)的變?cè)Q。 120 24 變?cè)募s束 （續(xù)） 例題 2. 對(duì) (?x)(P(x)?R(x,y)) ? Q(x,y)換名。 解：可換名為 (?z)(P(z)?R(z,y)) ? Q(x,y) 但不可換名為 (?y)(P(y)?R(y,y)) ? Q(x,y) 或 (?z)(P(z)?R(x,y)) ? Q(x,y) 121 24 變?cè)募s束 （續(xù)） 自由變?cè)拇嬉?guī)則： （ 1）對(duì)于自由變?cè)梢源?，代入時(shí)需對(duì)公式中出現(xiàn)該自由變?cè)拿恳惶庍M(jìn)行代入。 （ 2）用以代入的變?cè)c原公式中的所有變?cè)拿Q不能相同。 122 24 變?cè)募s束 （續(xù)） 例題 3. 對(duì) (?x)(P(y)?R(x,y))作自由變?cè)搿? 解：對(duì) y施行代入，得到： (?x)(P(z)?R(x,z) 但是 (?x)(P(x)?R(x,x) 和 (?x)(P(z)?R(x,y) 都是錯(cuò)誤的。 123 合式公式的解釋 見書 P43例題 定義 :邏輯有效式（永真式）、矛盾式（永假）、可滿足式 邏輯有效式是可滿足式，但反之不成立。 定義：代換實(shí)例 定理：命題公式中的重言式的代換實(shí)例在謂詞公式中仍為重言式，即邏輯有效式；命題公式中的矛盾式的代換實(shí)例仍為矛盾式 書 P43 例題 124 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 定義 A和 B，設(shè)它們有共同的個(gè)體域 E。若對(duì) A和 B的任意一組變?cè)M(jìn)行賦值，所得命題的真值相同，則稱謂詞公式 A和 B在 E上是等價(jià)的。記為 A?B。 定義 A，其個(gè)體域?yàn)?E。若對(duì) A的任意變?cè)x值， A都為真，則稱該 A在 E上是有效的（或永真的）。 定義 A，如果在所有賦值下，該公式的真值都為假，則稱該 A 為不可滿足的。否則，稱該 A 為可滿足的。 125 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） （ 1）命題公式的推廣 命題演算中的等價(jià)公式表和蘊(yùn)涵式表都可以推廣到謂詞演算中。例如： (?x)(P(x)?Q(x))?(? x)(?P(x)?Q(X)) (?x)P(x)?(?y)(R(x,y)??(?(?x)P(x)??(?y)(R(x,y)) (?y)(H(x,y)??(?x)H(x,y)?F 另外經(jīng)過(guò)換名和代替規(guī)則所得公式和原公式等值 126 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） （ 2）量詞與聯(lián)結(jié)詞 ?之間的關(guān)系 約定：出現(xiàn)在量詞之前的否定，不是否定該量詞，而是否定被量化了的整個(gè)命題。 轉(zhuǎn)化公式： 1.?(?x)P(x)?(?x)?P(x) 2.?(?x)P(x)?(?x)?P(x) 127 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） 上述公式的推廣： 設(shè)個(gè)體域中的客體變?cè)獮?a1,a2,?,a n，則 1. ?(?x)A(x) ??(A(a1)?A(a2)?… ?A(an)) ??A(a1)??A(a2)?… ??A(an)) ?(?x)?A(x) 2. ?(? x)A(x) ??(A(a1)?A(a2)?… ?A(an)) ??A(a1)??A(a2)?… ??A(an)) ?(?x)?A(x) 128 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） 結(jié)論： 當(dāng)將量詞前面的聯(lián)結(jié)詞 ?移到量詞的后面去時(shí)，存在量詞改為全稱量詞，全稱量詞改為存在量詞；反之，如果將 量詞后面的聯(lián)結(jié)詞 ?移到量詞的前面去時(shí)，也要做相應(yīng)的改變。 129 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） （ 3）量詞作用域的擴(kuò)張與收縮 1. (?x)(A(x)?B)?(?x)A(x)?B 2. (?x)(A(x)?B)?(?x)A(x)?B 3. (?x)(A(x)?B)?(?x)A(x)?B 4. (?x)(A(x)?B)?(?x)A(x)?B 5. (?x)(A(x)?B)?(?x)A(x)?B 6. (?x)(A(x)?B)?(?x)A(x)?B 7. (?x)(B?A(x))?(B?(?x)A(x)) 8. (?x)(B?A(x))?(B?(?x)A(x)) 130 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） （ 4）量詞與命題聯(lián)結(jié)詞之間的一些等價(jià)關(guān)系 量詞分配等值式 1. (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x) 2. (?x)(A(x)?B(x))?(?x)A(x)?(?x)B(x) 注意：全稱量詞只對(duì)合取有分配； 存在量詞只對(duì)析取有分配； 131 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） （ 5）量詞與命題聯(lián)結(jié)詞之間的一些蘊(yùn)涵關(guān)系 1.(?x)(A(x)?B(x))=(?x)A(x)?(?x)B(x) 2.(?x)(A(x)?B(x))=(?x)A(x)?(?x)B(x) 3.(?x)(A(x)? B(x))=(?x)A(x)? (?x)B(x) 132 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） （ 6）多個(gè)量詞的使用 對(duì)于二元謂詞的情況： 1.(?x)(?y)A(x,y) 2.(?x)(?y)A(x,y) 3.(?x)(?y)A(x,y) 4.(?x)(?y)A(x,y) 5.(?y)(?x)A(x,y) 6.(?y)(?x)A(x,y) 7.(?y)(?x)A(x,y) 8.(?y)(?x)A(x,y) （ 2種排列情況 4種組合情況） 133 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） （ 3） 量詞與命題聯(lián)結(jié)詞的一些等價(jià)式與蘊(yùn)涵式 序號(hào) 表達(dá)式 E23 (?x)（ A(x)? B（ x） )? (?x)A(x) ? (?x)B（ x） E24 (?x) (A(x)? B(x))? (?x) A(x)?(?x)B(x） E25 ?(?x) A(x) ? (?x)?A(x) E26 ?(?x)A(x) ? (?x)?A(x) E27 (?x) (A ? B(x))? A ? (?x)B(x） E28 (?x)（ A ? B（ x） )? A?(?x)B（ x） E29 (?x)(A(x)? B（ x） )? (?x) A(x)?(?x)B（ x） E30 (?x)A(x)? B? (?x)(A(x)?B（ x） ) E31 (?x)(A(x)?B) ? (?x)(A(x)? B) E32 A(x)? (?x) B（ x） ? (?x)(A(x)? B) 134 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） 序號(hào) 表達(dá)式 E33 A(x)? (?x) B（ x） ? (?x) (A(x)? B) I17 (?x) A(x)?(?x) B(x)? (?x)(A(x) ?B(x） ) I18 (?x)(A(x)? B(x)) ? (?x) A(x)? (?x) B(x） I19 (?x)A(x)?(?x) B(x) ? (?x)(A(x)?B(x） ) ? 量詞與命題聯(lián)結(jié)詞的一些等價(jià)式與蘊(yùn)涵式 135 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） （ 4）多個(gè) 量詞的使用 以兩個(gè)量詞對(duì)于二元謂詞的情況為例 (?x)(?y)A(x,y) ? (?y)(?x)A(x,y) (?x)(?y)A(x,y) ? (?y)(?x)A(x,y) (?x)(?y)A(x,y) (?y)(?x)A(x,y) (?y)(?x)A(x,y) (?x)(?y)A(x,y) 136 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） 例 設(shè) A(x,y)表示 x和 y同姓 ,論域 x是甲村的人 ,y是乙村的人 ,則 (?x)(?y)A(x,y): 甲村和乙村所有的人都同姓。 (?y)(?x)A(x,y)： 乙村和甲村所有的人都同姓。 顯然上述倆語(yǔ)句的含義相同。故 (?x)(?y)A(x,y) ? (?y)(?x)A(x,y) 137 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） (?x)(?y)A(x,y) ?(?y)(?x)A(x,y） 同理 (?x)(?y)A(x,y)： 甲村與乙村有人同姓。 (?y)(?x)A(x,y)： 乙村與甲村有人都同姓。 故 (?x)(?y)A(x,y) ? (?y)(?x)A(x,y) 138 25 謂詞演算的等價(jià)式與蘊(yùn)涵式 （續(xù)） 但是 (?x)(?y)A(x,y) 表示對(duì)于 甲村所有的人，乙村都有人和他同姓。 (?y)(?x)A(x,y) 表示存在一個(gè) 乙村的人，甲村所有的人和他同姓。 (?y)(?x)A(x,y) 表示對(duì)于乙 村所有的人，甲村都有人和他同姓。 (?x)(?y) A(x,y) 表示存在一個(gè) 甲村的人，乙村所有的人和他同姓。 上述四種語(yǔ)句，表達(dá)的情況各不相同，故全稱量詞與存在量詞的次序，不能隨意更換。 139 26 前束范式 定理：任何一個(gè)謂詞公式均等價(jià)于某個(gè)前束范式。 定義： 如果一個(gè)謂詞公式的量詞均在全式的開頭，而這些量詞的作用域延伸至整個(gè)公式的末尾，則該公式叫做 前束范式。 前束范式記為： (□ v1)(□ v2)?( □ vn)A 例： (?x)(?y)(?z)(Q(x,y)? R(z))是一個(gè)前束范式。 140 26 前束范式 例 1： 把公式 (?x)P(x)?(?x)Q(x)轉(zhuǎn)化為前束范式。 解： (?x)P(x)?(?x)Q(x) 等值代換 ? ? (?x)P(x)? (?x)Q(x) ?(?x)?P(x)?(?x)Q(x) ?(?x)(?P(x)?Q(x)) 前束范式 (參見教材