2-謂詞邏輯(編輯修改稿)
2024-09-01 19:31 本頁面
【文章內(nèi)容簡介】 代換規(guī)則： （對自由變元代換） (1) 對自由變元可以更改（稱為代換），代換時需對公式中該自由變元的自由出現(xiàn)每一處進(jìn)行代換。 (2) 用以代換的變元符號與原公式中所有變元的符號不能相同。 例、指出下列謂詞公式中的自由變元和約束變元 (1) (?x)(P(x,y)∨R(x)) (2) (?x)F(x)→P(x) (?x)(P(x,y)∨R(x)) x是約束變元 y是自由變元； 約束出現(xiàn) 約束出現(xiàn) 自由出現(xiàn) (?x)F(x)→P(x) F(x)中的 x是約束變元； 注意 ：在同一個公式中，允許一個變元即呈自由出現(xiàn)又呈約束出現(xiàn)。但是，為了避免概念上的混淆，通過改名規(guī)則，使得一個變元在一個公式中只呈一種出現(xiàn)。 約束出現(xiàn) 自由出現(xiàn) P(x)中的 x是自由變元； 例、判斷對下列公式中約束變元的改名是否正確 (?x)(P(x)→R( x,y)) 改為： (1)(?z)(P(z)→R( z,y)) (2) (?y)(P(y)→R( y,y)) (3) (?z)(P(z)→R(x,y)) （正確） （錯誤） （錯誤） 例、判斷對下列公式中自由變元的代入是否正確 (?x)(P(x)→R(x, y)) 改為： (1)(?x)(P(x)→R(x, z)) (2) (?x)(P(x)→R(x, x)) （正確） （錯誤） 謂詞公式的等價式或蘊(yùn)含式 ? 謂詞前加上量詞，稱為謂詞的量化。 ? 謂詞被量化后，便可在確定的個體域中考慮其真值了（變成了命題）。如 (?x)A(x) ? 謂詞公式的真值只與論域，自由變元和命題變元有關(guān)。 如： (?x)A(x) ∧ B(x) ∧ P ? 和命題邏輯中一樣： 給定一個謂詞公式，它也具有永真式，永假式，可滿足的概念； 給定兩個謂詞公式 A和 B，也具有 A ? B， A ? B的概念。 ? 命題演算中的等價公式表和蘊(yùn)含公式表都可推廣到謂詞演算中使用。如： (?x)(P(x)→Q(x)) ?(?x)(? P(x)∨ Q(x)) (?x) P(x)→( ?x)Q(x) ? ?(?x)P(x)∨ (?x)Q(x) 含有量詞的等價式和蘊(yùn)含式 （ 0）消去量詞等價式 量詞可以用 ∧ ， ∨ 聯(lián)結(jié)詞代替，若個體域 D={a1，a2， … an}, 有 ： (?x)A(x) ?A(a1) ∧ A(a2) ∧ … A( an) (?x)A(x) ?A(a1) ∨ A(a2) ∨ … A( an) 證明 (a) 式： ? (?x)A (x) ? ? (A(a1) ∧ A(a2) ∧ … A(an) ) ? ?A(a1) ∨ ? A(a2) ∨ … ? A(an) ) ? (?x) ? A (x) （ 1）量詞轉(zhuǎn)換律： (a) ? (?x)A (x) ?(?x) ? A (x) (b) ? (?x)A (x) ?(?x) ? A (x) （ 2）量詞轄域的擴(kuò)張與收縮： 其中 B 中不含變元 x (a) (?x)A(x) ∨ B ?(?x)(A(x) ∨ B) (b) (?x)A(x) ∧ B ?(?x)(A(x) ∧ B) (c) (?x)A(x) ∨ B ?(?x)(A(x) ∨ B) (d) (?x)A(x) ∧ B ?(?x)(A(x) ∧ B) 證明（ b）式 （ 3）量詞分配律 (a) (?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x) (b) (?x)(A(x)∨ B(x))?(?x)A(x)∨ (?x)B(x) (c) (?x)A(x)∨ (?x)B(x)?(?x)(A(x)∨ B(x)) (d) (?x)(A(x)∧ B(x))?(?x)A(x)∧ (?x)B(x) 證明（ a）式和（ d）式 可用前件后件 的方法 (4) 多個量詞的等價公式 ? (a) (?x)(?y)A(x,y)?(?y)(?x)A(x,y) ? (b) (?x)(?y)A(x,y)?(?y)(?x)A(x,y) 證等價式或蘊(yùn)含式的方法（沒有真值表法） ?直接定義推導(dǎo)法 ?前件后件的方法 ?等價推導(dǎo)或蘊(yùn)含推導(dǎo) 法 ?證蘊(yùn)含式還有 推理規(guī)則法 （ ） 謂詞邏輯比命題邏輯范圍更加廣泛。 謂詞邏輯是命題邏輯的完善和擴(kuò)充。 謂詞演算的推理理論 但是，謂詞公式中由于有量詞，因此推理過程中必須有消去和添加量詞的規(guī)則。 命題演算中的推理規(guī)則，如規(guī)則 P， T， CP和 F 都可以在謂詞邏輯的推理理論中應(yīng)用。 (1)全稱特指規(guī)則 (US規(guī)則 ) ：如對個體域中所有個體 x都滿足 P，則對個體域中 任一個個體 y滿足 P 。 即： (?x)P(x)?P(y) (y是任意的 ) (2)存在特指規(guī)則 (ES規(guī)則 )：如對于個體域中某些 個體 x滿足 P ，則必有 某個特定個體 y 滿足 P 。 即： (?x)P(x)?P(y) (y是特定的 ) (3)全稱推廣規(guī)則 (UG規(guī)則 ) ： 如能夠證明對個體域中 每一個個體 y都滿足 P，則可得到結(jié)論 (?x)P(x)成立。 即： P(y ) ? (?x)P(x) (4) 存在推廣規(guī)則 (EG規(guī)則 )：如對個體域中 某個特定個體 y滿足 P， 則在個體域中必存在滿足 P(x)的 x。 即： P(y ) ? (?x)P(x) UG規(guī)則的使用條件舉例 已知： D(u,v): u可以被 v整除； 個體域： ｛ 5， 7， 10， 11｝ D(5,5) D(10,5) 真 (?u)D(u,5) 真 D(7,5) D(11,5) 假 (?x)D(x,5) 假 考察以下推導(dǎo)過程 （ 1） (?x)D(x,5) 錯在（ 3）： 使用 ES規(guī)則引入的個體 a，不得使用UG規(guī)則加以推廣。 P規(guī)則 （ 2） D(a,5) ES規(guī)則（ 1） （ 3） (?y)D(y,5) UG規(guī)則（ 2） 個體域中 某一個個體 例 . 判斷以下推理是否正確？ 1） (1) (?x) P(x) ? Q(x) P (2) P(x) ? Q(x) US(1) 錯 ! 說明： 約束出現(xiàn)的 x和自由
環(huán)評公示相關(guān)推薦
鄂ICP備17016276號-1