離散數(shù)學(xué)課件 第二章 謂詞邏輯-2nd.pdf

1 43 第二章 謂詞邏輯 大連理工大學(xué)軟件學(xué)院 陳志奎 教授 辦公室 綜合樓411 Tel 87571525 實驗室 教學(xué)樓A318 A323 Tel 87571620 24 MobileEmail zkchen zkchen00 2 43 回顧 謂詞 個體 量詞 一元 多元 域 全稱 存在 合式謂詞公式 定義 5條 自由變元和約束變元 含有量詞的等價式和永真蘊(yùn)含式 謂詞公式的解釋 3 43 記憶規(guī)律 xy yx yx xy xy yx yx xy 1B 2B 4B 3B 5B 7B 6B 8B 4 43 2 2謂詞邏輯中的推理規(guī)則 推理規(guī)則 5 43 規(guī)則1 約束變元的改名規(guī)則 對約束變元進(jìn)行換名 使得一個變元在一 個公式中只呈一種形式出現(xiàn) 規(guī)則如下 欲改名之變元應(yīng)是某量詞作用范圍內(nèi)的變 元 且應(yīng)同時更改該變元在此量詞轄域內(nèi)的 所有約束出現(xiàn) 而公式的其余部分不變 新的變元符號應(yīng)是此量詞轄域內(nèi)原先沒有使 用過的 最好是公式中未出現(xiàn)過的符號 x P xy P y 等價于 6 43 規(guī)則1 約束變元的改名規(guī)則 例 對公式 進(jìn) 行換名 使各變元只呈一種形式出現(xiàn) 解 需要對約束變元x y進(jìn)行換名 不對的 x P x y yQ x y z S x z u P u y Q u v z S x z v u P u vQ u v z S vx z z S x z zQ u y u P u z 7 43 規(guī)則2 自由變元的代入規(guī)則 對公式中自由變元的更改叫做代入 規(guī)則 如下 欲改變自由變元的名 必改在公式中的每一 處自由出現(xiàn) 新變元不應(yīng)在原公式中以任何約束形式出現(xiàn) 例 對公式 的變元 x y的自由出現(xiàn)用w t代入 得 x P x y x y z S x z yQ x P x t x y z S w z yQ 8 43 例如 例如 對公式對公式 x P x Q x x P x R x 為清楚起見 可對第二個約束變元為清楚起見 可對第二個約束變元x進(jìn)行換名進(jìn)行換名 x P x Q x y P y R y 又例如 又例如 對公式對公式 x P x R x y Q x y 可對約束變元可對約束變元x進(jìn)行換名 得進(jìn)行換名 得 z P z R z y Q x y z P z R x y Q x y y P y R y y Q x y 錯誤 錯誤 9 43 規(guī)則3 命題變元的代換規(guī)則 用任一謂詞公式Ai 代換永真公式 中某一 命題變元Pi 的所有出現(xiàn) 所得到的新公式 B 仍然是永真式 但在Ai 的個體變元中不 應(yīng)有 中的約束變元出現(xiàn) 并有 BB 10 43 規(guī)則4 取代規(guī)則 設(shè) 都是含n個 自由變元的謂詞公式 且A 是A的子公式 若在A中用B 取代A 的一處或多處出現(xiàn)后 所得的新公式是B 則有 如果A為 永真式 則B也是永真式 1212 nnA x xxB x xx AB 11 43 謂詞邏輯的推理 在謂詞邏輯中 推理的形式結(jié)構(gòu)仍為在謂詞邏輯中 推理的形式結(jié)構(gòu)仍為 CHHH n 21 若 是永真式 則稱由前提 邏輯的推出結(jié)論 若 是永真式 則稱由前提 邏輯的推出結(jié)論C 在此 在此 C均為謂詞公式 均為謂詞公式 n HHH 21 n HHH 21 CHHH n 21 12 43 規(guī)則5 量詞的增加和刪除規(guī)則 全稱特指規(guī)則US 從 可得出結(jié)論A y 其中y是個體域中任一個體 即 注意 y不能和A x 中其它指導(dǎo)變元重名 存在特指規(guī)則ES 從 可得出結(jié)論A a 其中a是 和在此之前不曾出現(xiàn)過的個體常 量 即 注意 a不能和指定前提中任一自由變元同名 也不能和使用本規(guī)則以前任一推導(dǎo)步驟上得到的 公式的自由變元同名 x A x x A xA y x A x x A x x A xA a 13 43 規(guī)則5 量詞的增加和刪除規(guī)則 存在推廣規(guī)則EG 從A x 可得出結(jié)論 其 中x是個體域中的某一個個體 即 注意 y不和A x 中其他自由變元或指導(dǎo)變元同名 全稱推廣規(guī)則UG 從A x 可得出結(jié)論 其中x是個體域中的任意個體 即 使用條件 1 x不是給定前提中任一公式的自由變元 2 x不是在前面推導(dǎo)步驟中使用ES規(guī)則引入的 變元 3 若在前面推導(dǎo)過程中使用ES規(guī)則引入新變 元u時 x是自由變元 那么在A x 中 u應(yīng) 約束出現(xiàn) A xy A y A xy A y y A y y A y 14 43 謂詞邏輯中的推理 例1 證明 x M xx H xM x x H x 試證明是前提 和的邏輯結(jié)果 1 2 1 3 4 3 5 x H xP H yES x H xM xP H yM yUS M y 2 4 6 5 T x M xEG 15 43 謂詞邏輯中的推理 例2 試證明 證明 x P xQ xx Q xR xx P xR x 1 2 1 3 4 3 5 x P xQ xP P xQ xUS x Q xR xP Q xR xUS 2 4 6 5 P xR xT x P xR xUG 16 43 謂詞邏輯中的推理 例3 證明 x R xy D yL x y x R xy S yL x y x D xS x 已知前提 試推出結(jié)論 1 2 1 3 x R xy D yL x yP R ay D yL a yES R a 2 4 2 5 4 6 T y D yL a yT D uL a uUS x R xy S yL x y 7 6 8 3 7 P R ay S yL a yUS y S yL a yT 17 43 謂詞邏輯中的推理 9 8 10 9 11 S uL a uUS L a uS uT D uS uT 5 10 12 11 x D xS xUG x R xy D yL x y x R xy S yL x y x D xS x 已知前提 試推出結(jié)論 接上頁 18 43 例例4 指出下面推理的錯誤指出下面推理的錯誤 設(shè)設(shè)D x y 表示表示 x可被可被y 整除整除 個體域 為個體域 為 5 7 10 11 因為因為D 5 5 和和D 10 5 為真 所以 為真 所以 xD x 5 為真為真 因為因為D 7 5 和和D 11 5 為假 所以 為假 所以 xD x 5 為假為假 但有下面的推理過程 但有下面的推理過程 1 xD x 5 前提前提 2 D z 5 1 ES 3 xD x 5 2 UG 因此 因此 xD x 5 xD x 5 錯 錯 19 43 反證法舉例 例5 證明 x A xB xx B xC xx C x x A x 給定前提 試推出結(jié)論 1 2 1 3 x A xP xA xT A a 假設(shè)前提 2 4 5 4 6 ES x A xB xP A aB aUS B a 3 5 7 B C 8 7 9 T xxxP B aC aUS C a 6 8 10 C T xxP 20 43 反證法舉例 11 10 12 9 11 13 A F C aUS C aC aT xx 1 12 接上頁 21 43 謂詞邏輯中的推理 例6 使用CP規(guī)則證明 證明 因此原來的證明轉(zhuǎn)化為證明下式 xyP xQ yxP xy Q y xP xy Qy x P xy Q yx P xy Q y 由于 xyP xQ yx P xy Q y 22 43 謂詞邏輯中的推理 證明 xyP xQ yx P xy Q y 1 2 1 3 x P xP P aES xyP xQ y 附加前提 4 3 5 4 6 2 P yP aQ yUS P aQ bUS Q bT 5 7 6 8 Q y 1 7 y Q yUG x P xyCP 23 43 例7 例7 對多個量詞的使用情況 觀察下列推理過程對多個量詞的使用情況 觀察下列推理過程 證明 證明 1 前提 前提 yxyPx 2 1 US yzyP 3 2 ES dzP 4 3 UG dxxP 5 4 EG yxxPy 推出錯誤結(jié)論 與 可交換推出錯誤結(jié)論 與 可交換 y x 注意 公式注意 公式 2 中中z有兩種可能有兩種可能 1 若若z是自由個體變元 則此時是自由個體變元 則此時y的值是隨的值是隨z的變化而變 化的 因此不能用 的變化而變 化的 因此不能用ES規(guī)則將規(guī)則將y改為個體常元改為個體常元d 2 若若z是個體常元 則公式是個體常元 則公式 3 沒錯 但此時不能用沒錯 但此時不能用UG規(guī) 則得到 規(guī) 則得到 4 dxxP 錯 錯 錯 錯 24 43 謂詞邏輯求解實際問題 步驟 根據(jù)問題的需要定義一組謂詞 將實際問題符號化 使用推理規(guī)則有效推理 注意 符號化的原則 全稱量詞對應(yīng)邏輯聯(lián)結(jié)詞 存在量詞對應(yīng)邏輯聯(lián)結(jié)詞 推理時首先引入帶存在量詞的前提 以保證 ES 規(guī)則的有效性 25 43 謂詞邏輯求解實際問題 例8 證明蘇格拉底的三段論 所有的人都是要死的 蘇格拉底是人 所以蘇格拉底是要死的 解 M x x是人 D x x是要死的 c 蘇格拉底 蘇格拉底三段論可以表示成 證明 1 M c P 2 P 3 M c D c US 2 4 D c T 1 3 x M x D x M c D c x M x D x 26 43 謂詞邏輯求解實際問題 例9 所有的自然數(shù)都是整數(shù) 任何整數(shù)不是奇數(shù) 就是偶數(shù) 并非每個自然數(shù)都是偶數(shù) 所以 某 些自然數(shù)是奇數(shù) 解 第一步 定義謂詞 N x x是自然數(shù) I x x是整數(shù) Q x x是奇數(shù) O x x是偶數(shù) 第二步 問題符號化 x N xI x x I xQ xO x x N xO x x N xQ x 27 43 謂詞邏輯求解實際問題 第三步 證明 x N xI xx I xQ xO x x N xO xx N xQ x 1 2 1 3 N a 2 4 x N xO xP xN xO xT O aES N a 3 4 3 5 6 N T O aT x N xI xP a I a 5 7 I a 4 6 US T 28 43 謂詞邏輯求解實際問題 8 9 8 10 7 9 11 x I xQ xO xP I aQ aO aUS Q aO aT Q a 4 10 12 4 11 13 12 T N aO aT x N xQ xEG 接上頁 29 43 謂詞邏輯求解實際問題 例10 每個報考研究生的大學(xué)畢業(yè)生要么參加研究生 入學(xué)考試 要么推薦為免考生 每個報考研究生的 大學(xué)畢業(yè)生當(dāng)且僅當(dāng)學(xué)習(xí)成績優(yōu)秀才被推薦為免試 生 有些報考研究生的大學(xué)畢業(yè)生學(xué)習(xí)成績優(yōu)秀 但并非所有報考研究生的大學(xué)畢業(yè)生學(xué)習(xí)成績都優(yōu) 秀 因此 有些報考研究生的大學(xué)畢業(yè)生要參加研 究生入學(xué)考試 解 定義謂詞如下 YJS x x是要報考研究生的大學(xué)畢業(yè)生 MKS x x是免考生 CJYX x x是成績優(yōu)秀的 CJKS x x是參加考試的 30 43 謂詞邏輯求解實際問題 第二步 符號化問題 x YJS xCJKS xMKS x x YJS xMKS xCJYX x x YJS xCJYX x x YJS xCJYX x x YJS xCJKS x 31 43 謂詞邏輯求解實際問題 第三步 證明 1 2 1 a 3 x YJS xCJYX xP xYJS xCJYX xT YJSCJYX a 2 a 43 5 3 6 ES YJST CJYX aT a a 76 847 9 x YJS xCJKS xMKS xP YJSCJaMKS aUS CJKSMKS aT KS xYJS xMKS xCJYX xP 32 43 謂詞邏輯求解實際問題 10 9 11410 12 YJS aMKS aCJYX aUS MKS aCJYX aT MKS a 511 13812 144 13 1 5 KS T CJaT YJS aCJKS aT 1 4 x YJS xCJKS xEG 接上頁 33 43 謂詞邏輯求解實際問題 例11 所有的蜂鳥都五彩斑斕 沒有大鳥以蜜為 生 不以蜜為生的鳥都色彩單調(diào) 因此 蜂鳥都是 小鳥 解 定義謂詞如下 P x x是只蜂鳥 Q x x是大鳥 R x x是以蜜為生的鳥 S x x五彩斑斕 x P xS xx Q xR x xR xS xx P xQ x 34 43 謂詞邏輯求解實際問題 x P xS xx Q xR x xR xS xx P xQ x 證明 1 2 1 3 4 3 5 4 6 7 6 8 7 9 8 10 2 5 11 x P xS xP P xS xUS xR xS xP R xS xUS S xR xT x Q xR xP xQ xR xT Q xR xUS R xQ xT P xR xT P x 10 9 12 11 Q xT x P xQ xUG 35 43 隨堂練習(xí) 練習(xí) 符號化下列命題 并利用推理規(guī)則論 證結(jié)論 所有牛都有角 有些動物是牛 所以有些動 物有角 36 43 2 3謂詞公式的范式 命題邏輯中的兩種范式都可以直接推廣到 謂詞邏輯中來 只要把原子命題公式換成 原子謂詞公式即可 根據(jù)量詞在公式中出現(xiàn)的情況不同 又可 分為前束范式前束范式和斯柯林范式斯柯林范式 37 43 前束范式 定義 對任一謂詞公式F 如果其中所有 量詞均非否定的出現(xiàn)在公式的最前面 且 它們的轄域為整個公式 則稱公式F為前前 束范式束范式 xyz P x yQ x yR x y z 38 43 前束范式 任意一個公式都可以轉(zhuǎn)化成與之等價的前 束范式 方法如下 消去公式中的聯(lián)結(jié)詞 和 例如 將公式內(nèi)的否定符號深入到謂詞變元前并化 簡到謂詞變元前只有一個否定號 利用改名 代入規(guī)則使所有的約束變元均不 同名 且使自由變元與約束變元亦不同名 擴(kuò)充量詞的轄域至整個公式 ABABAB ABAB 39 43 前束范式 例 將下列公式轉(zhuǎn)化成前束范式 解 x P xy R yx F x x P xy R yx F x