離散數(shù)學(xué)-2-5謂詞演算的等價式與蘊含式.ppt

《離散數(shù)學(xué)-2-5謂詞演算的等價式與蘊含式.ppt》由會員分享，可在線閱讀，更多相關(guān)《離散數(shù)學(xué)-2-5謂詞演算的等價式與蘊含式.ppt（20頁珍藏版）》請在裝配圖網(wǎng)上搜索。

1 第二章謂詞邏輯 2 5謂詞演算的等價式與蘊含式授課人 李朔Email chn nj ls 2 一 基本概念 謂詞公式中可包含有命題變元和客體變元 當(dāng)命題變元用確定的命題取代 客體變元用確定的客體所取代時 就稱作對公式賦值 一個謂詞公式經(jīng)過賦值后 就成為真值確定的命題 T或F 定義2 5 1給定任何兩個謂詞公式wffA和wffB 設(shè)它們有共同的個體域E 若對A和B的任意一組變元進行賦值 所得命題的真值相同 則稱謂詞公式A和B在E上是等價的 記為A B 3 一 基本概念 定義2 5 2任意給定謂詞公式wffA 其個體域為E 若對A的任意變元賦值 wffA都為真 則稱該wffA在E上是有效的 或永真的 定義2 5 3對于一個謂詞公式wffA 如果在所有賦值下 該公式的真值都為假 則稱該wffA為不可滿足的 定義2 5 4對于一個謂詞公式wffA 如果至少在一種賦值下為真 則稱該wffA為可滿足的 4 二 命題公式的推廣 在命題邏輯中 重言式的同一分量出現(xiàn)的每一處都用同一合式公式置換 其結(jié)果仍是重言式類似于我們學(xué)習(xí)過的命題邏輯中的等價式與蘊含式 在謂詞邏輯中有了等價和永真的概念 同樣有謂詞演算的一些等價式與蘊含式 命題演算中的等價公式表和蘊涵式表都可以推廣到謂詞演算中 當(dāng)謂詞演算中的公式代替命題演算中永真公式的變元時 所得的謂詞公式即為有效公式 故命題演算中的等價公式和蘊含式表都可推廣到謂詞演算中使用 5 二 命題公式的推廣 例如 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 x H x y H x y F 6 三 量詞與聯(lián)結(jié)詞 之間的關(guān)系 例1設(shè)P x 表示x喜歡夢八隊 則 P x 表示x不喜歡夢八隊 個體域限定為人 1 不是所有人都喜歡夢八隊 x P x 2 存在一些人不喜歡夢八隊 x P x 3 不會有人喜歡夢八隊 x P x 4 所有人都不喜歡夢八隊 x P x 可以看出命題 1 2 意義完全相同 3 4 意義也完全相同 即有1 x P x x P x 2 x P x x P x 7 三 量詞與聯(lián)結(jié)詞 之間的關(guān)系 式1與式2反映了量詞與聯(lián)結(jié)詞 之間的關(guān)系 是我們可以得到的公式 量詞的轉(zhuǎn)化律 這里的約定 出現(xiàn)在量詞之前的否定 不是否定該量詞 而是否定被量化了的整個命題 上述公式在有限論域上的證明 設(shè)個體域中的客體變元為a1 a2 an 則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 8 三 量詞與聯(lián)結(jié)詞 之間的關(guān)系 量詞轉(zhuǎn)化律也能推廣到無窮個體域結(jié)論 當(dāng)將量詞前面的聯(lián)結(jié)詞 移到量詞的后面去時 存在量詞改為全稱量詞 全稱量詞改為存在量詞 反之 如果將量詞后面的聯(lián)結(jié)詞 移到量詞的前面去時 也要做相應(yīng)的改變 9 四 量詞作用域的擴張與收縮 量詞的作用域中常有合取項或析取項 如果其中一個為命題 即零元謂詞 則可將該命題移至量詞作用域外 如1 x A x B x A x B2 x A x B x A x B3 x A x B x A x B4 x A x B x A x B因為B中不出現(xiàn)約束變元x 所以它屬于或不屬于量詞作用域均有相同意義 10 四 量詞作用域的擴張與收縮 從1 4式還可推得如下幾個式子 5 x A x B x A x B 6 x A x B x A x B 7 B x A x x B A x 8 B x A x x B A x 例2證明5式P68當(dāng)謂詞變元與量詞的指導(dǎo)變元不同時 亦能有類似于上述的公式 11 五 量詞與命題聯(lián)結(jié)詞之間的一些等價關(guān)系 量詞與命題聯(lián)結(jié)詞存在不同的結(jié)合情況例學(xué)院里所有學(xué)生既懂理論也懂應(yīng)用 A x B x 學(xué)院里所有學(xué)生懂理論且所有學(xué)生懂應(yīng)用 上述語句意義相同 故有 個體域為學(xué)院全體學(xué)生 x A x B x x A x x B x 由上式可以有 x A x B x x A x x B x 故有 x A x B x x A x x B x 即有 x A x B x x A x x B x 12 六 量詞與命題聯(lián)結(jié)詞之間的一些蘊涵關(guān)系 量詞與命題與命題聯(lián)結(jié)詞之間存在一些不同情況 有些是蘊含公式 例可以從 這些學(xué)生都聰明或這些學(xué)生都努力 推出 這些學(xué)生都聰明或努力 但不能從 這些學(xué)生都聰明或努力 推出 這些學(xué)生都聰明或這些學(xué)生都努力 即有 x A x x B x x A x B x 由上式可推得 x A x B x x A x x B x 13 六 量詞與命題聯(lián)結(jié)詞之間的一些蘊涵關(guān)系 類似的可推得 x A x B x x A x x B x x A x B x x A x x B x 很多等價式與蘊含式可以相互推導(dǎo)表2 5 1 14 六 量詞與命題聯(lián)結(jié)詞之間的一些蘊涵關(guān)系 15 七 多個量詞的使用 對于二元謂詞有八種情況 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 16 七 多個量詞的使用 例設(shè)A x y 表示x和y同姓 論域x是甲村的人 y是乙村的人 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 乙村與甲村有人都同姓 故 x y A x y y x A x y 17 七 多個量詞的使用 但是 x y A x y 表示對于甲村所有的人 乙村都有人和他同姓 y x A x y 表示存在一個乙村的人 甲村所有的人和他同姓 y x A x y 表示對于乙村所有的人 甲村都有人和他同姓 x y A x y 表示存在一個甲村的人 乙村所有人和他同姓 上述四種語句 表達的情況各不相同 故全稱量詞與存在量詞的次序 不能隨意更換 18 七 多個量詞的使用 如下一蘊含式中不同量詞間的次序是不可隨意交換的 x yA x y y xA x y y xA x y x yA x y x yA x y y xA x y y xA x y x yA x y y xA x y x yA x y x yA x y y xA x y 例設(shè)x的個體域為動物 y的個體域為人 則由 有些動物為所有人喜歡 必可知 每個人喜歡一些動物 反之 每個人喜歡一些動物 不一定能有 有些動物為所有人喜歡 19 本課小結(jié) 1 等價式 有效式 可滿足式2 命題公式的推廣 量詞與聯(lián)結(jié)詞 之間的關(guān)系 量詞作用域的擴張與收縮 3 量詞與命題聯(lián)結(jié)詞之間的一些等價關(guān)系 4 量詞與命題聯(lián)結(jié)詞之間的一些蘊涵關(guān)系5 多個量詞的使用 20 作業(yè) P71 7