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