一階謂詞邏輯.ppt

第二講一階 謂詞邏輯 在Ls中 把命題分解到原子命題為止 認(rèn)為原子命題是不能再分解的 僅僅研究以原子命題為基本單位的復(fù)合命題之間的邏輯關(guān)系和推理 這樣 有些推理用命題邏輯就難以確切地表示出來 例如 著名的亞里士多德三段論蘇格拉底推理 退出 所有的人都是要死的 蘇格拉底是人 所以蘇格拉底是要死的 根據(jù)常識 認(rèn)為這個推理是正確的 但是 若用Ls來表示 設(shè)P Q和R分別表示這三個原子命題 則有 P Q R 然而 P Q R并不是永真式 故上述推理形式又是錯誤的 一個推理 得出矛盾的結(jié)論 問題在哪里呢 問題就在于這類推理中 各命題之間的邏輯關(guān)系不是體現(xiàn)在原子命題之間 而是體現(xiàn)在構(gòu)成原子命題的內(nèi)部成分之間 即體現(xiàn)在命題結(jié)構(gòu)的更深層次上 對此 Ls是無能為力的 所以 在研究某些推理時 有必要對原子命題作進(jìn)一步分析 分析出其中的個體詞 謂詞和量詞 研究它們的形式結(jié)構(gòu)的邏輯關(guān)系 正確的推理形式和規(guī)則 這些正是謂詞邏輯 簡稱為Lp 的基本內(nèi)容 2 1個體 謂詞和量詞2 2謂詞公式與翻譯2 3約束變元與自由變元2 4公式解釋與類型2 5等價式與蘊(yùn)涵式2 6謂詞公式范式2 7謂詞邏輯的推理理論 2 1個體 謂詞和量詞 在Lp中 命題是具有真假意義的陳述句 從語法上分析 一個陳述句由主語和謂語兩部分組成 在Lp中 為揭示命題內(nèi)部結(jié)構(gòu)及其不同命題的內(nèi)部結(jié)構(gòu)關(guān)系 就按照這兩部分對命題進(jìn)行分析 并且把主語稱為個體或客體 把謂語稱為謂詞 個體 謂詞和命題的謂詞形式定義2 1 1在原子命題中 所描述的對象稱為個體 用以描述個體的性質(zhì)或個體間關(guān)系的部分 稱為謂詞 個體 是指可以獨(dú)立存在的事物 它可以是具體的 也可以是抽象的 如張明 計(jì)算機(jī) 精神等 表示特定的個體 稱為個體常元 以a b c 或帶下標(biāo)的ai bi ci 表示 表示不確定的個體 稱為個體變元 以x y z 或xi yi zi 表示 謂詞 當(dāng)與一個個體相聯(lián)系時 它刻劃了個體性質(zhì) 當(dāng)與兩個或兩個以上個體相聯(lián)系時 它刻劃了個體之間的關(guān)系 表示特定謂詞 稱為謂詞常元 表示不確定的謂詞 稱為謂詞變元 都用大寫英文字母 如P Q R 或其帶上 下標(biāo)來表示 例如 在命題 張明是位大學(xué)生 中 張明 是個體 是位大學(xué)生 是謂詞 它刻劃了 張明 的性質(zhì) 設(shè)S 是位大學(xué)生 c 張明 則 張明是位大學(xué)生 可表示為S c 或者寫成S c 張明是位大學(xué)生 又如 在命題 武漢位于北京和廣州之間 中 武漢 北京和廣州是三個個體 而 位于 和 之間 是謂詞 它刻劃了武漢 北京和廣州之間的關(guān)系 設(shè)P 位于 和 之間 a 武漢 b 北京 c 廣州 則P a b c 武漢位于北京和廣州之間 定義2 1 2一個原子命題用一個謂詞 如P 和n個有次序的個體常元 如a1 a2 an 表示成P a1 a2 an 稱它為該原子命題的謂詞形式或命題的謂詞形式 應(yīng)注意的是 命題的謂詞形式中的個體出現(xiàn)的次序影響命題的真值 不是隨意變動 否則真值會有變化 如上述例子中 P b a c 是假 原子謂詞公式原子命題的謂詞形式還可以進(jìn)一步加以抽象 比如在謂詞右側(cè)的圓括號內(nèi)的n個個體常元被替換成個體變元 如x1 x2 xn 這樣便得了一種關(guān)于命題結(jié)構(gòu)的新表達(dá)形式 稱之為n元原子謂詞 定義2 1 3由一個謂詞 如P 和n個體變元 如x1 x2 xn 組成的P x1 x2 xn 稱它為n元原子謂詞或n元命題函數(shù) 簡稱n元謂詞 而個體變元的論述范圍 稱為個體域或論域 當(dāng)n 1時 稱一元謂詞 當(dāng)n 2時 稱為二元謂詞 特別地 當(dāng)n 0 稱為零元謂詞 零元謂詞是命題 這樣命題與謂詞就得到了統(tǒng)一 n元謂詞不是命題 只有其中的個體變元用特定個體或個體常元替代時 才能成為一個命題 但個體變元在哪些論域取特定的值 對命題的真值極有影響 例如 令S x x是大學(xué)生 若x的論域?yàn)槟炒髮W(xué)的計(jì)算機(jī)系中的全體同學(xué) 則S x 是真的 若x的論域是某中學(xué)的全體學(xué)生 則S x 是假的 若x的論域是某劇場中的觀眾 且觀眾中有大學(xué)生也有非大學(xué)生的其它觀眾 則S x 是真值是不確定的 通常 把一個n元謂詞中的每個個體的論域綜合在一起作為它的論域 稱為n元謂詞的全總論域 定義了全總論域 為深入研究命題提供了方便 當(dāng)一個命題沒有指明論域時 一般都從全總論域作為其論域 而這時又常常要采用一個謂詞如P x 來限制個體變元x的取值范圍 并把P x 稱為特性謂詞 量詞利用n元謂詞和它的論域概念 有時還是不能用符號來很準(zhǔn)確地表達(dá)某些命題 例如S x 表示x是大學(xué)生 而x的個體域?yàn)槟硢挝坏穆毠?那么S x 可表示某單位職工都是大學(xué)生 也可表示某單位有一些職工是大學(xué)生 為了避免理解上的歧義 在Lp中 需要引入用以刻劃 所有的 存在一些 等表示不同數(shù)量的詞 即量詞 其定義如下 定義2 1 4 符號 稱為全稱量詞符 用來表達(dá) 對所有的 每一個 對任何一個 一切 等詞語 x稱為全稱量詞 稱x為指導(dǎo)變元 符號 稱為存在量詞符 用來表達(dá) 存在一些 至少有一個 對于一些 某個 等詞語 x稱為存在量詞 x稱為指導(dǎo)變元 符號 稱為存在唯一量詞符 用來表達(dá) 恰有一個 存在唯一 等詞語 x稱為存在唯一量詞 稱x為指導(dǎo)變元 全稱量詞 存在量詞 存在唯一量詞統(tǒng)稱量詞 量詞記號是由邏輯學(xué)家Fray引入的 有了量詞之后 用邏輯符號表示命題的能力大大加強(qiáng)了 例試用量詞 謂詞表示下列命題 所有大學(xué)生都熱愛祖國 每個自然數(shù)都是實(shí)數(shù) 一些大學(xué)生有遠(yuǎn)大理想 有的自然數(shù)是素?cái)?shù) 解令S x x是大學(xué)生 L x x熱愛祖國 N x x是自然數(shù) R x x是實(shí)數(shù) I x x有遠(yuǎn)大理想 P x x是素?cái)?shù) 則例中各命題分別表示為 x S x L x x N x R x x S x I x x N x P x 在該例的解答中 由于命題中沒有指明個體域 這便意味著各命題是在全總論域中討論 因而都使用了特性謂詞 如S x N x 而且還可以看出 量詞與特性謂詞的搭配還有一定規(guī)律 即全稱量詞后跟一個條件式 而特性謂詞作為其前件出現(xiàn) 存在量詞后跟一個合取式 特性謂詞作為一個合取項(xiàng)出現(xiàn) 如果在解答時 指明了個體域 便不用特性謂詞 例如在 中令個體域?yàn)槿w大學(xué)生 和 中的個體域?yàn)槿孔匀粩?shù) 則可符號化為 x L x x R x x I x x P x 謂詞前加上了量詞 稱為謂詞的量化 若一個謂詞中所有個體變元都量化了 則該謂詞就變成了命題 這是因?yàn)樵谥^詞被量化后 可以在整個個體域中考慮命題的真值了 這如同數(shù)學(xué)中的函數(shù)f x 的值是不確定的 但可確定其值 2 2謂詞公式與翻譯 謂詞公式為了方便處理數(shù)學(xué)和計(jì)算機(jī)科學(xué)的邏輯問題及謂詞表示的直覺清晰性 將引進(jìn)項(xiàng)的概念 定義2 2 1項(xiàng)由下列規(guī)則形成 個體常元和個體變元是項(xiàng) 若f是n元函數(shù) 且t1 t2 tn是項(xiàng) 則f t1 t2 tn 是項(xiàng) 所有項(xiàng)都由 和 生成 有了項(xiàng)的定義 函數(shù)的概念就可用來表示個體常元和個體變元 例如 令f x y 表示x y 謂詞N x 表示x是自然數(shù) 那么f 2 3 表示個體自然數(shù)5 而N f 2 3 表示5是自然數(shù) 這里函數(shù)是就廣義而言的 例如P x x是教授 f x x的父親 c 張強(qiáng) 那么P f c 便是表示 張強(qiáng)的父親是教授 這一命題 函數(shù)的使用給謂詞表示帶來很大方便 例如 用謂詞表示命題 對任意整數(shù)x x2 1 x 1 x 1 是恒等式 解 令I(lǐng) x x是整數(shù) f x x2 1 g x x 1 x 1 E x y x y 則該命題可表示成 x I x E f x g x 定義2 2 2若P x1 x2 xn 是n元謂詞 t1 t2 tn是項(xiàng) 則稱P t1 t2 tn 為Ls中原子謂詞公式 簡稱原子公式 下面 由原子公式出發(fā) 給出Lp中的合式謂詞公式的歸納定義 定義2 2 3合式謂詞公式當(dāng)且僅當(dāng)由下列規(guī)則形成的符號串 原子公式是合式謂詞公式 若A是合式謂詞公式 則 A 是合式謂詞公式 若A B是合式謂詞公式 則 A B A B A B 和 A B 都是合式謂詞公式 若A是合式謂詞公式 x是個體變元 則 x A x A都是合式謂詞公式 僅有有限項(xiàng)次使用 和 形成的才是合式謂詞公式 謂詞邏輯的翻譯把一個文字?jǐn)⑹龅拿} 用謂詞公式表示出來 稱為謂詞邏輯的翻譯或符號化 反之亦然 一般說來 符號化的步驟如下 正確理解給定命題 必要時把命題改敘 換句話說 使其中每個原子命題 原子命題之間的關(guān)系能明顯表達(dá)出來 把每個原子命題分解成個體 謂詞和量詞 在全總論域討論時 要給出特性謂詞 找出恰當(dāng)量詞 應(yīng)注意全稱量詞 x 后跟條件式 存在量詞 x 后跟合取式 用恰當(dāng)?shù)穆?lián)結(jié)詞把給定命題表示出來 例將命題 沒有最大的自然數(shù) 符號化 解 命題中 沒有最大的 顯然是對所有的自然數(shù)而言 所以可理解為 對所有的x 如果x是自然數(shù) 則一定還有比x大的自然數(shù) 再具體點(diǎn) 即 對所有的x如果x是自然數(shù) 則一定存在y y也是自然數(shù) 并且y比x大 令N x x是自然數(shù) G x y x大于y 則原命題表示為 x N x y N y G y x 例將語句 今天有雨雪 有些人會跌跤 符號化 解 本語句可理解為 若今天下雨又下雪 則存在x x是人且x會跌跤 令R 今天下雨 S 今天下雪 M x x是人 F x x會跌跤 則本語句可表示為 R S x M x F x 由于人們對命題的文字?jǐn)⑹龊饫斫獾牟煌?強(qiáng)調(diào)的重點(diǎn)不同 會影響到命題符號化的形式不同 2 3約束變元與自由變元 定義2 3 1給定一個謂詞公式A 其中有一部分公式形如 x B x 或 x B x 則稱它為A的x約束部分 稱B x 為相應(yīng)量詞的作用域或轄域 在轄域中 x的所有出現(xiàn)稱為約束出現(xiàn) x稱為約束變元 B中不是約束出現(xiàn)的其它個體變元的出現(xiàn)稱為自由出現(xiàn) 這些個體變元稱自由變元 對于給定的謂詞公式 能夠準(zhǔn)確地判定它的轄域 約束變元和自由變元是很重要的 通常 一個量詞的轄域是某公式A的一部分 稱為A的子公式 因此 確定一個量詞的轄域即是找出位于該量詞之后的相鄰接的子公式 具體地講 若量詞后有括號 則括號內(nèi)的子公式就是該量詞的轄域 若量詞后無括號 則與量詞鄰接的子公式為該量詞的轄域 判定給定公式A中個體變元是約束變元還是自由變元 關(guān)鍵是要看它在A中是約束出現(xiàn) 還是自由出現(xiàn) 今后常用元語言符號A x 表示x是其中的一個個體變元自由出現(xiàn)的任意公式 如A x 可為P x Q x P x y Q x y 等 一旦在A x 前加上量詞 x 或 x 即得公式 x A x 或 x A x 這時 x即是約束出現(xiàn)了 類似地 用A x y 表示x和y是自由出現(xiàn)的公式 定義2 3 2設(shè)A為任意一個公式 若A中無自由出現(xiàn)的個體變元 則稱A為封閉的合式公式 簡稱閉式 由閉式定義可知 閉式中所有個體變元均為約束出現(xiàn) 例如 x P x Q x 和 x y P x Q x y 是閉式 而 x P x Q x y 和 y z L x y z 不是閉式 從下面討論可以看出 在一公式中 有的個體變元既可以是約束出現(xiàn) 又可以是自由出現(xiàn) 這就容易產(chǎn)生混淆 為了避免混淆 采用下面兩個規(guī)則 約束變元換名規(guī)則 將量詞轄域中某個約束出現(xiàn)的個體變元及相應(yīng)指導(dǎo)變元 改成本轄域中未曾出現(xiàn)過的個體變元 其余不變 自由變元代替規(guī)則 對某自由出現(xiàn)的個體變元可用個體常元或與原子公式中所有個體變元不同的個體變元去代替 且處處代替 換名規(guī)則與代替規(guī)則的共同點(diǎn)都是不能改變約束關(guān)系 而不同點(diǎn)是 施行的對象不同 換名是對約束變元施行 代替是對自由變元施行 施行的范圍不同 換名可以只對公式中一個量詞及其轄域內(nèi)施行 即只對公式的一個子公式施行 而代替必須對整個公式同一個自由變元的所有自由出現(xiàn)同時施行 即必須對整個公式施行 例 x y R x y L y z xH x y 換名和代替為 x y R x y L y z tH t w 施行后的結(jié)果不同 換名后 公式含義不變 因?yàn)榧s束變元只改名為另一個個體變元 約束關(guān)系不改變 約束變元不能改名為個體常元 代替 不僅可用另一個個體變元進(jìn)行代替 并且也可用個體常元去代替 從而使公式由具有普遍意義變?yōu)閮H對該個體常元有意義 即公式的含義改變了 2 4公式解釋與類型 1 公式解釋一般情況下 Lp中的公式含有 個體常元 個體變元 約束變元或自由變元 函數(shù)變元 為謂詞變元等 對各種變元用指定的特殊常元去代替 就構(gòu)成了一個公式的解釋 當(dāng)然在給定的解釋下 可以對多個公式進(jìn)行解釋 下面給出解釋的一般定義 定義2 4 1一個解釋I由下面4部分組成 非空個體域DI DI中部分特定元素a b DI上的特定一些函數(shù)f g DI上特定謂詞 P Q 在一個具體解釋中 個體常元 函數(shù)符號 謂詞符號的數(shù)量一般是有限的 并且其解釋一旦確定下來就不再改變 只是個體變元的值在個體域DI內(nèi)變化 量詞符 或 僅作用于DI中的元素 2 公式類型定義2 4 2 若一公式在任何解釋下都是真的 稱該公式為邏輯有效的 或永真的 若一公式在任何解釋下都是假的 稱該公式為矛盾式 或永假式 若一公式至少存在一個解釋使其為真 稱該公式為可滿足式 從定義可知 邏輯有效式為可滿足式 反之未必成立 與命題公式中分類一樣 謂詞公式也分為三種類型 即邏輯有效式 或重言式 矛盾式 或永假式 和可滿足式 由于謂詞公式的復(fù)雜性和解釋的多樣性 至今還沒有一個可行的算法判定任何公式的類型 早在1936年 Churen和Turing各自獨(dú)立地證明了 對于Lp 其判定問題是不可解的 但是 Lp是個半個可判定的 即若Lp中公式是重言式 則存在算法在有限步驟內(nèi)能驗(yàn)證它 當(dāng)然 對于一些較為簡單的公式 或某些特殊公式 還是可以判定其類型的 例如 如果一個謂詞公式是命題公式中的重言式的代換實(shí)例 則這個謂詞公式是邏輯有效式 或重言式 見教材P44例2 9 2 5等價式與蘊(yùn)涵式 1 等價式定義2 5 1設(shè)A B為任意兩個公式 若A B為邏輯有效的 則稱A與B是等價的 記為A B 稱A B為等價式 由于重言式 永真式 都是邏輯有效的 可見1 3節(jié)中的命題定律 基本等價式 都是Lp等價式 此外 還有一置換規(guī)則 設(shè) A 是含有A出現(xiàn)的公式 B 是用公式B替換若干個公式A的結(jié)果 若A B 則 A B 顯然 若 A 為重言式 則 B 也是重言式 下面給出涉及量詞的一些等值式 1 量詞否定等值式 量詞可互相轉(zhuǎn)化 a x A x A b x A x A 這兩個等值式 可用量詞的定義給予說明 由于 并非對一切x A為真 等價于 存在一些x A為真 故 a 成立 由于 不存在一些x A為真 等價于 對一切x A為真 所以 b 成立 這兩個等值式的意義是 否定聯(lián)結(jié)詞可通過量詞深入到轄域中 對比這兩個式子 容易看出 將 x 與 x 兩者互換 可從一個式子得到另一個式子 這表明 x 與 x 具有對偶性 另外 由于這兩個公式成立也表明了 兩個量詞是不獨(dú)立的 可以互相表示 所以只有一個量詞就夠了 對于多重量詞前置 可反復(fù)應(yīng)用上面結(jié)果 逐次右移 例如 x y z P x y z x y z P x y z 2 量詞轄域縮小或擴(kuò)大等值式設(shè)B是不含x自由出現(xiàn) A x 為有x自由出現(xiàn)的任意公式 則有 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 B A x B x A x e x A x B x A x B f x A x B x A x B g x A x B x A x B h x B A x B x A x 運(yùn)用 c g 時要小心 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 其中 A x B x 為有x自由出現(xiàn)的任何公式 4 多重量詞等值式 a x y A x y y x A x y b x y A x y y x A x y 其中A x y 為含有x y自由出現(xiàn)的任意公式 2 蘊(yùn)涵式由于Ls中蘊(yùn)涵式 或永真條件式 在Lp中都是邏輯有效的 而且使用代入規(guī)則得到蘊(yùn)涵式也都是Lp中邏輯有效的 例如 x P x x P x y Q y 附加 x P x Q x y x P x Q x y 假言推理 下面將給出Lp中的一些蘊(yùn)涵式 1 a x A x x B x x A x B x b x A x B x x A x x B x c x A x B x x A x x B x d x A x B x x A x x B x 其中 A x 和B x 為含有x自由出現(xiàn)的任意公式 2 6謂詞公式范式 前束范式定義2 9 1一個合式公式稱為前束范式 如果它有如下形式 Q1x1 Q2x2 Qkxk B其中Qi 1 i k 為 或 B為不含有量詞的公式 稱Q1x1Q2x2 Qkxk為公式的首標(biāo) 特別地 若 中無量詞 則 也看作是前束范式 可見 前束范式的特點(diǎn)是 所有量詞均非否定地出現(xiàn)在公式最前面 且它的轄域一直延伸到公式之末 例如 x y P x y Q y z R x y 等都是前束范式 而 x P x y Q y x P x y Q x y 不是前束范式 定理2 6 1 前束范式存在定理 Lp中任意公式A都有與之等價的前束范式 本教材轉(zhuǎn)化前束范式原則 能不換名就不換 見教材P47例2 11 求公式的前束范式 1 x F x G x xH x y 2 xF x y yG y xH x y 例2 20 例2 11 5 2 7謂詞邏輯的推理理論 Lp是Ls的進(jìn)一步深化和發(fā)展 因此Ls的推理理論在Lp中幾乎可以完全照搬 只不過這時涉及的公式是Lp的公式罷了 在Lp中 某些前提和結(jié)論可能受到量詞的約束 為確立前提和結(jié)論之間的內(nèi)部聯(lián)系 有必要消去量詞和添加量詞 因此正確理解和運(yùn)用有關(guān)量詞消去和添加規(guī)則是Lp推理理論中十分重要的關(guān)鍵所在 在一階邏輯中 推理的形式結(jié)構(gòu)仍為 若 H1 H2 Hn C是邏輯有效式 則稱C是H1 H2 Hn的邏輯結(jié)論 記為 H1 H2 Hn C除命題邏輯的11條規(guī)則外 加上前面證明的 a x A x x B x x A x B x b x A x B x x A x x B x c x A x B x x A x x B x d x A x B x x A x x B x 有關(guān)量詞消去和產(chǎn)生規(guī)則還要用到以下4條推理規(guī)則注意 其中A B不一定表示A B是邏輯有效式 而只表示在一定條件下 當(dāng)A為真時 B也為真的推理關(guān)系 全稱量詞消去規(guī)則 簡稱UI或US規(guī)則 有兩種形式 x A x A c x A x A y 成立充分條件是 c為論域中任意個體常項(xiàng) y為論域中任一個體 x在A x 中是自由出現(xiàn)的 y為任意的不在A x 中約束出現(xiàn)的個體變項(xiàng) 2 存在量詞消去規(guī)則 簡稱EI或ES規(guī)則 x A x A c 成立充分條件是 c是使A為真的特定個體常項(xiàng) c不曾在A x 中出現(xiàn)過 若A x 中有其它自由變項(xiàng)時 不能應(yīng)用本規(guī)則 3 全稱量詞產(chǎn)生規(guī)則 簡稱UG規(guī)則 A y x A x 成立條件 y在A y 中自由出現(xiàn) 且y取任何值時A均為真 取代y的x不能在A y 中約束出現(xiàn) A y 中含有個體常項(xiàng)時 要小心使用 4 存在量詞產(chǎn)生規(guī)則 簡稱EG規(guī)則 A c x A x 成立充分條件 c是特定的個體常項(xiàng) 取代c的個體變元x不能已在A c 中出現(xiàn)過 錯在哪里 P53例2 18 1 x F x G x P 2 F y G y 1 UI 3 xF x P 4 F y 3 EI 5 G y 2 4 假言推理 6 xG x 5 UG 錯在哪里 P53例2 18 1 x yF x y P 2 yF z y 1 UI 3 F z c 2 EI 4 xF x c 3 UG 5 y xF x y 4 EG 錯在哪里 P57習(xí)題2 16 1 xF x G x 前提引入 F y G y UI 2 x F x G x 前提引入 F a G b UI 3 F x G x 前提引入 y F y G y EG 4 F x G c 前提引入 x F x G x EG 5 F a G b 前提引入 x F x G x EG 錯在哪里 P57習(xí)題2 16 6 x F x G x 前提引入 y H y R y 前提引入 F