【文章內(nèi)容簡(jiǎn)介】 （ 2）有些運(yùn)動(dòng)員不欽佩教練 . 設(shè)： L(x):x是運(yùn)動(dòng)員 J(y):y是教練 A(x,y):x欽佩 y (1) (?x)(L(x) ?（ ?y)(J(y)∧ A(x,y))) (2)（ ?x)(L(x) ∧ (?y)(J(y)??A(x,y))) 第二章 謂 詞 邏 輯 謂詞公式與翻譯 41 小結(jié)： 本節(jié)介紹了 謂詞合式 公式的概念 ， 重點(diǎn)掌握 謂詞公式的翻譯 。 第二章 謂 詞 邏 輯 謂詞公式與翻譯 42 定義 :在 謂詞 公式 中 ， 形如 (?x)P(x)和 (?x)P(x)的部 分 ， 稱為謂詞 公式的 x約束部分 。 (?x)P(x)或 (?x)P(x)中的 x叫做量詞的 指導(dǎo)變?cè)? 或 作用變?cè)?， P(x)稱為 相應(yīng)量詞的 作用域 或 轄域 。 在 ?x和 ?x的轄域中 ， x的所有出現(xiàn)都稱為 約束出 現(xiàn) ， 相應(yīng)的 x稱為 約束變?cè)?。 P(x)中除約束變?cè)? 以外出現(xiàn)的變?cè)Q為是 自由變?cè)?。 第二章 謂 詞 邏 輯 變?cè)募s束 43 例 1： ?x( H(x,y)??y(W(y) ∧ L(x,y,z))) ?x( H(x)?W(y)) ? ?y( F(x) ∧ L(x,y,z)) 第二章 謂 詞 邏 輯 變?cè)募s束 44 說明 : (1)n元謂詞公式 A(x1， x2...xn) 中有 n個(gè)自由變?cè)?，若?duì)其中的 k(k≤n)個(gè)進(jìn)行約束，則構(gòu)成了 nk元謂詞；如果一個(gè)公式中沒有自由變?cè)霈F(xiàn)，則該公式就變成了一個(gè)命題。 (2)一個(gè)公式的約束變?cè)褂玫拿Q符號(hào)是無關(guān)緊要的，如 (?x)M(x)與 (?y)M(y)意義相同。 第二章 謂 詞 邏 輯 變?cè)募s束 45 約束變?cè)?換名與 自由變?cè)?代入 一個(gè)變?cè)谕粋€(gè)公式中既是自由出現(xiàn)又是約束出現(xiàn)，這樣在理解上容易發(fā)生混淆。為了避免這種混亂，可對(duì) 約束變?cè)M(jìn)行換名。 第二章 謂 詞 邏 輯 變?cè)募s束 46 換名規(guī)則 : (對(duì)約束變?cè)裕? 對(duì)約束變?cè)M(jìn)行換名，使得一個(gè)變?cè)谝粋€(gè)公式中 只呈一種形式出現(xiàn) (1)約束變?cè)梢該Q名，其更改的變?cè)Q范圍是量詞中的指導(dǎo)變?cè)约霸摿吭~作用域中所出現(xiàn)的該變?cè)?，公式的其余部分不變? (2)換名時(shí)一定要更改為作用域中沒有出現(xiàn)的變?cè)Q。 第二章 謂 詞 邏 輯 變?cè)募s束 47 例 1: ?x( P(x)?R(x,y))∧ L(x,y) 換名為 ?t( P(t)?R(t,y))∧ L(x,y) 2： ?x( H(x,y)??y(W(y) ∧ L(x,y,z))) 換名為 ?x( H(x,y)??s(W(s) ∧ L(x,s,z))) 第二章 謂 詞 邏 輯 變?cè)募s束 48 代入規(guī)則 （對(duì)自由變?cè)裕? 對(duì)公式中自由變?cè)母姆Q為代入 (1)對(duì)于謂詞公式中的自由變?cè)梢宰鞔?，代入時(shí)需要對(duì)公式中出現(xiàn)該自由變?cè)?每一處 進(jìn)行； (2)用以代入的變?cè)c原公式中所有變?cè)拿Q不能相同。 例： ?x( P(x)?R(x,y))∧ L(x,y) 對(duì)自由變?cè)?y用 z來代入，得 ?x( P(x)?R(x,z))∧ L(x,z) 第二章 謂 詞 邏 輯 變?cè)募s束 49 小結(jié)： 本節(jié)介紹了 約束變?cè)?、 自由變?cè)?的 概念 ， 重點(diǎn)掌握 約束變?cè)?換名與 自由變?cè)?代入 。 第二章 謂 詞 邏 輯 變?cè)募s束 50 定義： 一個(gè) 解釋 I由下面 4部分 組成： DI； a’、 b’， ...； f’、 g’， ...； 4. DI上特定謂詞 P’、 Q’， ...。 見書 P40例 。 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 51 定義 ： 給定任意的謂詞公式 A， 其個(gè)體域?yàn)?E， （ 1） 對(duì)于 A的所有解釋 ， 公式 A都為真 ， 則稱 A在 E上是 永真的 (或有效的 )。 （ 2） 若對(duì)于 A的所有解釋 ， 公式 A都為假 ， 則稱 A在 E上是 永假的 (或不可滿足的 )。 （ 3） 若至少存在著一種解釋使得公式 A為真 ， 則稱A在 E上是 可滿足的 。 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 52 定義： 給定任何兩個(gè)謂詞公式 A、 B， 設(shè)它們有共同的個(gè)體域 E， 若對(duì) A和 B的任一組變?cè)M(jìn)行解釋 ， 所得命題的真值相同 ， 則稱謂詞公式 A和 B在 E上等價(jià) ， 并記為 A ? B。 定義： 給定任何兩個(gè)謂詞公式 A、 B， 當(dāng)且僅當(dāng) A ? B是永真式時(shí) ， 稱 “ A蘊(yùn)涵 B”， 記作A ? B。 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 53 謂詞演算的等價(jià)式和蘊(yùn)涵式 命題公式的推廣 在命題公式中成立的等價(jià)公式，用謂詞公式去代換 其中相應(yīng)的命題變?cè)?，得到的公式依然成? 如： ?x( P(x)?Q(x)) ? ?x(? P(x) ∨ Q(x)) P(x) ∨ ? Q(x) ? ? （ P(x) ∧ Q(x)） 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 54 量詞與 ?之間的關(guān)系 ?（ ?x） P(x) ? （ ?x） ? P(x) ?（ ?x） P(x) ? （ ?x） ? P(x) 證明：對(duì)個(gè)體域 {a1， a2， … ， an}， ┐?xP(x) ?┐(P(a1)?P(a2)?… ?P(an)) ?┐P(a1)? ┐P(a2)?… ? ┐P(an) ??x ┐P(x) 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 55 量詞作用域的擴(kuò)張與收縮 量詞作用域中如果有合取或析取項(xiàng)，且其中有一個(gè) 是命題，則可將該命題移至量詞作用域之外。如： （ ?x） （ A(x)∨ B） ? （ ?x） A(x)∨ B （ ?x） （ A(x)∧ B） ? （ ?x） A(x)∧ B （ ?x） （ A(x)∨ B） ? （ ?x） A(x)∨ B （ ?x） （ A(x)∧ B） ? （ ?x） A(x)∧ B 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 56 證明：當(dāng)個(gè)體域?yàn)?{a1， a2， … ， an} ， ?xA(x)?P ?(P(a1)?P(a2)?… ?P(an))?P) ?((P(a1)?P)?(P(a2) ?P)?… ?(P(an)?P)) ? ?x(A(x)?P) 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 57 ? 量詞作用域的擴(kuò)張和收縮 ( ?xA(x)?B） ? （ ?x) (A(x)? B） (（ ?x)A(x)? B) ?(?x) (A(x)?B） (B ? (?x)A(x)） ?（ ?x)(B? A(x)） (B ? (?x)A(x)) ?（ ?x） (B? A(x)) 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 58 例 1： ?xA(x， y)?P(y) ? ?x(A(x， y)?P(y)) 例 2： ?x?y(P(x)→Q(y )) ? (? x P(x) → ?yQ(y)) 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 59 例 1： ?xA(x， y)?P(y) ? ?x(A(x， y)?P(y)) 例 2： ?x?y(P(x)→Q(y )) ? (? x P(x) → ?yQ(y)) 證明： ?x?y(P(x)→Q(y )) ? ?x?y(┐P(x) ?Q(y )) ? ?x (┐P(x) ??y Q(y )) ? ?x┐P(x)??yQ(y )) ? ┐? x P(x) ??y Q(y ) ? ? x P(x) → ?yQ(y) 第二章 謂 詞 邏 輯 謂詞演算的等價(jià)式與蘊(yùn)涵式 60 量詞的分配 設(shè) A(x)、 B(x)是任意的含自由出現(xiàn)個(gè)體變?cè)?x的公式 ， 則 (1) ?x(A(x)∧ B(x)) ? ? x A(x) ∧ ?x B(x) (2) ?x(A(x)∨ B(