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

1 43 第二章 謂詞邏輯 大連理工大學(xué)軟件學(xué)院 陳志奎 教授 辦公室 綜合樓411 Tel 87571525 實(shí)驗(yàn)室 教學(xué)樓A318 A323 Tel 87571620 24 MobileEmail zkchen zkchen00 2 43 回顧 謂詞 個(gè)體 量詞 一元 多元 域 全稱 存在 合式謂詞公式 定義 5條 自由變?cè)图s束變?cè)?含有量詞的等價(jià)式和永真蘊(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 約束變?cè)母拿?guī)則 對(duì)約束變?cè)M(jìn)行換名 使得一個(gè)變?cè)谝?個(gè)公式中只呈一種形式出現(xiàn) 規(guī)則如下 欲改名之變?cè)獞?yīng)是某量詞作用范圍內(nèi)的變 元 且應(yīng)同時(shí)更改該變?cè)诖肆吭~轄域內(nèi)的 所有約束出現(xiàn) 而公式的其余部分不變 新的變?cè)?hào)應(yīng)是此量詞轄域內(nèi)原先沒(méi)有使 用過(guò)的 最好是公式中未出現(xiàn)過(guò)的符號(hào) x P xy P y 等價(jià)于 6 43 規(guī)則1 約束變?cè)母拿?guī)則 例 對(duì)公式 進(jìn) 行換名 使各變?cè)怀室环N形式出現(xiàn) 解 需要對(duì)約束變?cè)獂 y進(jìn)行換名 不對(duì)的 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 自由變?cè)拇胍?guī)則 對(duì)公式中自由變?cè)母慕凶龃?規(guī)則 如下 欲改變自由變?cè)拿?必改在公式中的每一 處自由出現(xiàn) 新變?cè)粦?yīng)在原公式中以任何約束形式出現(xiàn) 例 對(duì)公式 的變?cè)?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 例如 例如 對(duì)公式對(duì)公式 x P x Q x x P x R x 為清楚起見 可對(duì)第二個(gè)約束變?cè)獮榍宄鹨?可對(duì)第二個(gè)約束變?cè)獂進(jìn)行換名進(jìn)行換名 x P x Q x y P y R y 又例如 又例如 對(duì)公式對(duì)公式 x P x R x y Q x y 可對(duì)約束變?cè)蓪?duì)約束變?cè)獂進(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 錯(cuò)誤 錯(cuò)誤 9 43 規(guī)則3 命題變?cè)拇鷵Q規(guī)則 用任一謂詞公式Ai 代換永真公式 中某一 命題變?cè)狿i 的所有出現(xiàn) 所得到的新公式 B 仍然是永真式 但在Ai 的個(gè)體變?cè)胁?應(yīng)有 中的約束變?cè)霈F(xiàn) 并有 BB 10 43 規(guī)則4 取代規(guī)則 設(shè) 都是含n個(gè) 自由變?cè)闹^詞公式 且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是個(gè)體域中任一個(gè)體 即 注意 y不能和A x 中其它指導(dǎo)變?cè)孛?存在特指規(guī)則ES 從 可得出結(jié)論A a 其中a是 和在此之前不曾出現(xiàn)過(guò)的個(gè)體常 量 即 注意 a不能和指定前提中任一自由變?cè)?也不能和使用本規(guī)則以前任一推導(dǎo)步驟上得到的 公式的自由變?cè)?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是個(gè)體域中的某一個(gè)個(gè)體 即 注意 y不和A x 中其他自由變?cè)蛑笇?dǎo)變?cè)?全稱推廣規(guī)則UG 從A x 可得出結(jié)論 其中x是個(gè)體域中的任意個(gè)體 即 使用條件 1 x不是給定前提中任一公式的自由變?cè)?2 x不是在前面推導(dǎo)步驟中使用ES規(guī)則引入的 變?cè)?3 若在前面推導(dǎo)過(guò)程中使用ES規(guī)則引入新變 元u時(shí) x是自由變?cè)?那么在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é)論 接上頁(yè) 18 43 例例4 指出下面推理的錯(cuò)誤指出下面推理的錯(cuò)誤 設(shè)設(shè)D x y 表示表示 x可被可被y 整除整除 個(gè)體域 為個(gè)體域 為 5 7 10 11 因?yàn)橐驗(yàn)镈 5 5 和和D 10 5 為真 所以 為真 所以 xD x 5 為真為真 因?yàn)橐驗(yàn)镈 7 5 和和D 11 5 為假 所以 為假 所以 xD x 5 為假為假 但有下面的推理過(guò)程 但有下面的推理過(guò)程 1 xD x 5 前提前提 2 D z 5 1 ES 3 xD x 5 2 UG 因此 因此 xD x 5 xD x 5 錯(cuò) 錯(cuò) 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 接上頁(yè) 21 43 謂詞邏輯中的推理 例6 使用CP規(guī)則證明 證明 因此原來(lái)的證明轉(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 對(duì)多個(gè)量詞的使用情況 觀察下列推理過(guò)程對(duì)多個(gè)量詞的使用情況 觀察下列推理過(guò)程 證明 證明 1 前提 前提 yxyPx 2 1 US yzyP 3 2 ES dzP 4 3 UG dxxP 5 4 EG yxxPy 推出錯(cuò)誤結(jié)論 與 可交換推出錯(cuò)誤結(jié)論 與 可交換 y x 注意 公式注意 公式 2 中中z有兩種可能有兩種可能 1 若若z是自由個(gè)體變?cè)?則此時(shí)是自由個(gè)體變?cè)?則此時(shí)y的值是隨的值是隨z的變化而變 化的 因此不能用 的變化而變 化的 因此不能用ES規(guī)則將規(guī)則將y改為個(gè)體常元改為個(gè)體常元d 2 若若z是個(gè)體常元 則公式是個(gè)體常元 則公式 3 沒(méi)錯(cuò) 但此時(shí)不能用沒(méi)錯(cuò) 但此時(shí)不能用UG規(guī) 則得到 規(guī) 則得到 4 dxxP 錯(cuò) 錯(cuò) 錯(cuò) 錯(cuò) 24 43 謂詞邏輯求解實(shí)際問(wèn)題 步驟 根據(jù)問(wèn)題的需要定義一組謂詞 將實(shí)際問(wèn)題符號(hào)化 使用推理規(guī)則有效推理 注意 符號(hào)化的原則 全稱量詞對(duì)應(yīng)邏輯聯(lián)結(jié)詞 存在量詞對(duì)應(yīng)邏輯聯(lián)結(jié)詞 推理時(shí)首先引入帶存在量詞的前提 以保證 ES 規(guī)則的有效性 25 43 謂詞邏輯求解實(shí)際問(wèn)題 例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 謂詞邏輯求解實(shí)際問(wèn)題 例9 所有的自然數(shù)都是整數(shù) 任何整數(shù)不是奇數(shù) 就是偶數(shù) 并非每個(gè)自然數(shù)都是偶數(shù) 所以 某 些自然數(shù)是奇數(shù) 解 第一步 定義謂詞 N x x是自然數(shù) I x x是整數(shù) Q x x是奇數(shù) O x x是偶數(shù) 第二步 問(wèn)題符號(hào)化 x N xI x x I xQ xO x x N xO x x N xQ x 27 43 謂詞邏輯求解實(shí)際問(wèn)題 第三步 證明 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 謂詞邏輯求解實(shí)際問(wèn)題 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 接上頁(yè) 29 43 謂詞邏輯求解實(shí)際問(wèn)題 例10 每個(gè)報(bào)考研究生的大學(xué)畢業(yè)生要么參加研究生 入學(xué)考試 要么推薦為免考生 每個(gè)報(bào)考研究生的 大學(xué)畢業(yè)生當(dāng)且僅當(dāng)學(xué)習(xí)成績(jī)優(yōu)秀才被推薦為免試 生 有些報(bào)考研究生的大學(xué)畢業(yè)生學(xué)習(xí)成績(jī)優(yōu)秀 但并非所有報(bào)考研究生的大學(xué)畢業(yè)生學(xué)習(xí)成績(jī)都優(yōu) 秀 因此 有些報(bào)考研究生的大學(xué)畢業(yè)生要參加研 究生入學(xué)考試 解 定義謂詞如下 YJS x x是要報(bào)考研究生的大學(xué)畢業(yè)生 MKS x x是免考生 CJYX x x是成績(jī)優(yōu)秀的 CJKS x x是參加考試的 30 43 謂詞邏輯求解實(shí)際問(wèn)題 第二步 符號(hào)化問(wèn)題 x YJS xCJKS xMKS x x YJS xMKS xCJYX x x YJS xCJYX x x YJS xCJYX x x YJS xCJKS x 31 43 謂詞邏輯求解實(shí)際問(wèn)題 第三步 證明 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 謂詞邏輯求解實(shí)際問(wèn)題 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 接上頁(yè) 33 43 謂詞邏輯求解實(shí)際問(wèn)題 例11 所有的蜂鳥都五彩斑斕 沒(méi)有大鳥以蜜為 生 不以蜜為生的鳥都色彩單調(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 謂詞邏輯求解實(shí)際問(wèn)題 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í) 符號(hào)化下列命題 并利用推理規(guī)則論 證結(jié)論 所有牛都有角 有些動(dòng)物是牛 所以有些動(dòng) 物有角 36 43 2 3謂詞公式的范式 命題邏輯中的兩種范式都可以直接推廣到 謂詞邏輯中來(lái) 只要把原子命題公式換成 原子謂詞公式即可 根據(jù)量詞在公式中出現(xiàn)的情況不同 又可 分為前束范式前束范式和斯柯林范式斯柯林范式 37 43 前束范式 定義 對(duì)任一謂詞公式F 如果其中所有 量詞均非否定的出現(xiàn)在公式的最前面 且 它們的轄域?yàn)檎麄€(gè)公式 則稱公式F為前前 束范式束范式 xyz P x yQ x yR x y z 38 43 前束范式 任意一個(gè)公式都可以轉(zhuǎn)化成與之等價(jià)的前 束范式 方法如下 消去公式中的聯(lián)結(jié)詞 和 例如 將公式內(nèi)的否定符號(hào)深入到謂詞變?cè)安⒒?簡(jiǎn)到謂詞變?cè)爸挥幸粋€(gè)否定號(hào) 利用改名 代入規(guī)則使所有的約束變?cè)?同名 且使自由變?cè)c約束變?cè)嗖煌?擴(kuò)充量詞的轄域至整個(gè)公式 ABABAB ABAB 39 43 前束范式 例 將下列公式轉(zhuǎn)化成前束范式 解 x P xy R yx F x x P xy R yx F x