第三讲 谓词逻辑

例3.1(永真性判断)给定一阶语言 , 其中 是两个常元,是 元谓词符号, 是不同的变元. 假设 是以下公式:考察公式 :即它的前束范式是:它的 Skolem 范式 是:根据以下语义推出关系:可知:若将 看成是命题变元 , 对于子句集合它具有一个反驳, 这表明它能够语义推出一个恒假式, 所以, 能够语义推出一个恒假式, 因而 是永假的.所以 是永假的.所以 是永真的.□定义3.1(文字,相反文字,子句,子句集合,空子句,基文字,基子句,子句代换,子句集合代换 )对于谓词逻辑, 可以定义类似于命题逻辑的一些概念:z原子公式或者原子公式的非称为文字.谓词逻辑归结法,,,,.L={c1,c2,P,Q}c1,c2P,Q1x,y,zA(^xP(x)Z^xQ(x))> ^x(P(x)Z Q(x))\A\((^xP(x)Z^xQ(x))> ^x(P(x)Z Q(x))),(^xP(x)Z^xQ(x))[]x(\P(x)[\Q(x)).^x^y]z((P(x)Z Q(y))[\P(z)[\Q(z)).C]z((P(c1)Z Q(c2))[\P(z)[\Q(z)).C(P(c1)Z Q(c2))[\P(c1)[\Q(c1)C(P(c1)Z Q(c2))[\P(c2)[\Q(c2)C X P(c1)Z Q(c2)C X\P(c1)C X\Q(c2)P(c1),Q(c2)p,q{p Z q,\p,\q},CC\AA X Xz 若 是原子公式,则 是 的 相反文字,是 的相反文字. z 文字的有限集合称为子句.z 不出现变元的文字称为基文字. z 不出现变元的子句称为基子句. z 空的子句称为空子句.z 子句的有限集合称为子句集合.z称 为一个代换. 若 是文字, 则 表示z若子句 是 , 则 表示□事实3.1(子句集合与 Skolem 范式)子句 也写为 表示的闭包. 子句集合表示以下合取范式的闭包:因而表示一个 Skolem 范式.□例3.2(基本概念)z 与 是相反文字, 但是 与 不是相反文字.z假设代换 , 则 等于 .z基子句 表示 .z子句 表示语句L \L L L \L 5:{x 1/t 1,l ,x m /t m }L 5(L)L x 1,l ,xm t 1,l ,t m.C {L 1,l ,L n }5(C){5(L 1),l ,5(L n )}.{L 1,l ,L n }L 1ZlZ L n L 1ZlZ L n {{L 1,1,l ,L 1,n 1},{L 2,1,l ,L 2,n 2},l ,{L m,1,l ,L m,n m}}(L 1,1ZlZ L 1,n 1)[(L 2,1ZlZ L 2,n 2)[l[(L m,1ZlZ L m,nm).P(c 1)\P(c 1)P(c 1)\P(z)5={z/c 1}5(\P(z))\P(c 1){P(c)}P(c){P(x),Q(y)}]x ]y(P(x)Z Q(y)).z子句集合 表示 Skolem 范式□定义3.2(可满足)给定一阶语言 , 假设 是子句,是字句集合. z的一个解释 满足 , 是指 满足 所表示的语句.记为z若以下条件成立:则称 是 和 的逻辑推论. 记为 .z若存在 的解释满足 , 则称 是可满足的; 否则称 是不可满足的.z解释 满足 是指 满足 所表示的 Skolem 范式.z若存在 的解释满足 , 则称 是可满足的; 否则称 是不可满足的.□例3.3(可满足)给定一阶语言 , 假设 是 元谓词符号,是常元, 是变元. z子句 是可满足的.z□定义3.3(归结子句)给定一阶语言 , 假设 是 的两个子句. 形如的子句称为 与 的归结子句. 其中 是两个代换,而 与 是两个相反的文字.若三个子句 具有上述关系, 则记为 .□例3.4(归结子句)对任意的赋值 , 当 及 时, 有 . {P(x)Z Q(y),P(c)Z\Q(z)}]x ]y ]z ((P(x)Z Q(y))[(P(c)Z\Q(z))).L C,C 1,C 2,C 3S L I C I C I X C I I X C 1I X C 2I X C 3C 3C 1C 2C 1,C 2X C 3L C C C I S I S L S S S L P,Q 1c x,y P(c)Z Q(x)P(c)Z Q(x),\Q(y)P(c).L C 1,C 2L (51(C 1)-{L 1})P (52(C 2)-{L 2})C 1C 251,52L 1J 51(C 1),L 2J 52(C 2),L 1L 2C 1,C 2,C 3C 1,C 2U res C 3X给定一阶语言 , 其中 是常元,是变元, 是 元函数符号, 是 元谓词符号. 有以下归结推出关系:z .z .z .z .z. z假设{ 是 . {是 . 则:□定义3.4(反驳)子句集合 的一个反驳是指子句的有限序列 , 它满足以下条件:z 是 .z对于每个 :{或者 ,{或者存在 使得 . □例3.5(反驳)给定一阶语言 , 其中 是常元,是变元, 是 元谓词符号. 子句集合有一个反驳 , 其中:L ={c,f,g,P,Q}c x,y f,g 11P(c),\P(x)U res P(c)Z Q(x),\Q(y)U res P(c)P(x)Z Q(x),\Q(y)U res P(x)P(x)Z Q(x),\Q(y)U res P(f (x))P(x)Z Q(x),\Q(y)res P(f 2(x))A P(x)Z P(f(y))Z R(g(y))B \P(y)Z\R(y)A,B res P(f(y))Z R(g(y))Z\R(y),A,B res R(g(y))Z\R(f(y)).S {C i |15i 5n}C n `i C i J S j,k<i (15j,k< n )C j ,C k U res C i L ={c 1,c 2,P,Q}c 1,c 2x P,Q 1{P(c 1)Z Q(c 2),\P(x),\Q(x)}{C 1,C 2,C 3,C 4,C 5}C 1:P(c 1)Z Q(c 2)C 2:\P(x)C 3:\Q(x)C 4:Q(c 2)C 1,C 2U res C 4C 5:`C 3,C 4U res C 5`U U U□定理3.1(归结推出与语义推出)给定一阶语言 , 假设 是 的两个子句.证明:从 可知存在代换 及两个相反的文字 与 , 使得 , , 而假设子句 分别表示公式 . 则可知 . 因为 , 所以即:□定理3.2(归结方法的可靠性)给定一阶语言 , 假设 是 的子句集合. 若 有一个反驳, 则 是不可满足的. 证明根据归结一步可以传递可满性, 若 是可满足的, 则它的反驳序列中每个子句都是可满足的, 但最後一个空子句是不可满足的. 所以 是不可满足的.□定理3.3(归结方法的完全性)给定一阶语言 , 假设 是 的子句集合. 若 是不可满足的, 则 有一个反驳.□例3.6(简单证明)给定一阶语言 , 其中 是常元,是变元, 是 元谓词符号. 语句的 Skolem 范式是:所对应的子句集合是:若 则 .L C 1,C 2L C 1,C 2U res C 3C 1,C 2X C 3C 1,C 2U res C 351,52L 1L 2L 1J 51(C 1)L 2J 52(C 2)C 3=(51(C 1)-{L 1})P (52(C 2)-{L 2}).C i 9i 9i X 5i (C i )(i=1,2)(51(C 1)-{L 1})P (52(C 2)-{L 2})C 391,92C 3,91,9293.C 1,C 2X C 3.L S L S S S S L S L S S L ={c 1,c 2,P,Q}c 1,c 2x P,Q 1\((^xP(x)Z^xQ(x))> ^x(P(x)Z Q(x))),]z((P(c 1)Z Q(c 2))[\P(z)[\Q(z)).=X X它有一个反驳:因而是永假的, 即是永真的. 子句集合对应的基实例集合是若将 分别看成是命题变元 , 则上述基实例集合对应于命题逻辑语句集合:它有一个反驳:对应于谓词逻辑的反驳:可以直接转换为最初子句集合的反驳:□例3.7(多种证明)给定一阶语言 , 假设 是 元谓词符号, 是 元谓词符号,是三个不同的变元, 是两个不同的常元. 定义以下公式: {P(c 1)Z Q(c 2),\P(z),\Q(z)},< P (c 1)Z Q(c 2),\P(z),\Q(z),Q(c 2),`> .\((^xP(x)Z^xQ(x))> ^x(P(x)Z Q(x)))(^xP(x)Z^xQ(x))> ^x(P(x)Z Q(x)){P(c 1)Z Q(c 2),\P(z),\Q(z)},{P(c 1)Z Q(c 2),\P(c 1),\P(c 2),\Q(c 1),\Q(c 2),},P(c 1),P(c 2),Q(c 1),Q(c 2)p 1,p 2,q 1,q 2{p 1Z q 2,\p 1,\p 2,\q 1,\q 2},<p 1Z q 2,\p 1,\q 2,q 2,`> .<P (c 1)Z Q(c 2),\P(c 1),\Q(c 2),Q(c 2),`> .< P (c 1)Z Q(c 2),\P(z),\Q(z),Q(c 2),`> .L ={c 1,c 2,P,Q,R,S}P,Q,R 1S 2x,y,z c 1,c 2A :^x(P(x)[]y(R(y)> S (x,y))),B :]x(P(x)>]y(Q(y)> \S(x,y))),C :]x(R(x)>\Q(x)).则 .□证明(解释赋值方法).若 是一个解释. 假设 , 以下证明:z从 , 可知存在 , 使得 , 且对任意的 , 都有当 时z因为 且 , 所以因而 . z所以 .证毕.□证明(归结方法).的转化为:的转化为:的转化为:前提与结论的反面可以转化为以下子句:有以下的归结推出:对任意的 , 当 时 .若 则 , , , ,., , ,,A,B X C I I X A [B a J D I R I (a )=1Q I (a )=0I X A b J D I P I (b )=1a J D I R I (a )=1S I (b ,a )=1.I X B I X P I (b )Q I (a )=1S I (b ,a )=0.Q I (a )=0I X C A ^x(P(x)[]y(R(y)>S (x,y))),^x ]y(P(x)[(R(y)>S (x,y)))^x ]y(P(x)[(\R(y)Z S(x,y)))]y(P(c 1)[(\R(y)Z S(c 1,y)))]x(P(c 1)[(\R(x)Z S(c 1,x))){P(c 1),\R(x)Z S(c 1,x)}B ]x(P(x)> ]y(Q(y)> \S(x,y))),]x ]y(P(x)>(Q(y)> \S(x,y))),]x ]y(\P(x)Z\Q(y)Z\S(x,y)),]]x(\P(y)Z\Q(z)Z\S(y,z)),{\P(y)Z\Q(z)Z\S(y,z)}.\C \]x(R(x)> \Q(x)).^x \(R(x)> \Q(x))^x(R(x)[Q(x))R()[Q(c 2){R(c 2),Q(c 2)}C 1:P(c 1)C 2:\R(x)Z S(c 1,x),C 3:\P(y)Z\Q(z)Z\S(y,z),C 4:R(c 2)C 5:Q(c 2)y c 2所以证毕.□例3.8(语义推出)给定一阶语言 , 为 元谓词符号, 为 元谓词符号, 为元谓词符号,是三个不同的常元.是四个不同的变元.是以下公式:则 .证明的转化为:的转化为:的转化为:的转化为:可得以下子句:有以下的归结关系:,,..,.,.,,.C1,C3Ures\Q(z)Z\S(c1,z),C2,C4UresS(c1,c2),\Q(z)Z\S(c1,z),S(c1,c2)Ures\Q(c2),C5,\Q(c2)Ures`.A,B X C.L={a,b,c,P,Q,R,S}P,S1R2Q 3a,b,c x,y,z,w A,B,C,D ]x]y((Q(x,x,y)[\P(y))> S(x)),^x^y(R(y,x)[\P(x))^x]yQ(x,x,y)^xS(x)A,B,C X DA]x]y((Q(x,x,y)[\P(y))> S(x)),]x]y(\Q(x,x,y)Z P(y)Z S(x)),\Q(x,x,y)Z P(y)Z S(x)B^x^y(R(y,x)[\P(x)){R(b,a),\P(a)}C^x]yQ(x,x,y)Q(c,c,z)\D\^xS(x)]x\S(x)\S(w)\Q(x,x,y)Z P(y)Z S(x)R(b,a),\P(a)Q(c,c,z)\S(w)证毕.□例3.9(不可推出)给定一阶语言 , 为 元谓词符号,是两个不同的常元. 是三个不同的变元. 则证明可以化为:可能的归结推出只有:因而上述子句集合没有反驳. 即□例3.10(符号化与证明)某些学生喜欢每门课程, 没有学生喜欢文学. 因此, 没有课程是文学. 假设学生与课程的集合为论域, 定义以下谓词:则有以下的符号化:z“某些学生喜欢每门课程”的符号化为 :\Q(x,x,y)Z P(y)Z S(x),Q(c,c,z)U res P(y)Z S(c),P(y)Z S(c),\P(a)U res S(c),S(c),\S(w)U res `.L ={c 1,c 2,P,Q}P,Q 1c 1,c 2x,y,z ^xP(x),^xQ(x)X^x(P(x)[Q(x))./^xP(x)[^xQ(x)[\^x(P(x)[Q(x))^xP(x)[^xQ(x)[]x(\P(x)Z\Q(x))^x ^y(P(x)[Q(y))[]x(\P(x)Z\Q(x))^x ^y ]z(P(x)[Q(y)[(\P(z)Z\Q(z)){P(c 1),Q(c 2),\P(z)Z\Q(z)}P(c 1),\P(z)Z\Q(z)U res \Q(c 1),Q(c 2),\P(z)Z\Q(z)U res \P(c 2).^xP(x),^xQ(x)X^x(P(x)[Q(x))./P(x)x D(x)x S(x)x L(x,y)x yA ^x(P(x)[]y(D(y)>L (x,y))).z“没有学生喜欢文学”的符号化为 :z“没有课程是文学”的符号化为 :需要证明假设 是两个不同的常元,是三个不同的变元.的转化为:的转化为:的转化为:有以下归结推出关系:因而□作业全部B\^xy(P(x)[S(y)[L(x,y)).C\^x(D(x)[S(x)).A,B X C.c1,c2x,y,zA^x(P(x)[]y(D(y)> L(x,y))).P(c1),\D(y)Z L(c1,y).P(c1),\D()Z L(c1,z).B\^xy(P(x)[S(y)[L(x,y)).\P(x)Z\S(y)Z\L(x,y).\C\\^x(D(x)[S(x)).^x(D(x)[S(x)).D(c2),S(c2).P(c1),\P(x)Z\S(y)Z\L(x,y)Ures\S(y)Z\L(c1,y),S(c2),\S(y)Z\L(c1,y)Ures\L(c1,c2),\D(z)Z L(c1,z),\L(c1,c2)Ures\D(c2),D(c2),\D(c2)Ures`.A,B X C.z。

谓词逻辑推理定律首先，让我们了解什么是谓词逻辑。

谓词逻辑是一种逻辑分析方法，用于分析一些断言或句子的真假性。

谓词逻辑推理是指根据给定的谓词逻辑语句推理出另一个谓词逻辑语句的过程。

通常情况下，谓词逻辑推理被用于解决语义相关问题，如逻辑谬误，语言理解等。

谓词逻辑推理定律是用于谓词逻辑推理过程中所应注意的一些基本原则，它们能够帮助我们合理地进行推理，确保推理的合法性和准确性。

下面我们将详细介绍几个常见的谓词逻辑推理定律。

1. 否定演算规律：一个命题与它的否定命题不能同时成立。

例如，如果说“所有动物都能呼吸”，那么这么说就是错误的：“所有动物不能呼吸”。

因此，被推理的命题不能同时成立为“真”和“假”。

2. 否定引入规律：在一个推理中，当我们不能证明一个命题时，我们可以推出它的否定命题是真的。

例如，如果一个人说“我已经搜索了整个屋子，但是没有找到我的钥匙”，那么我们可以推断出：“我的钥匙不在我的房子里”。

因为如果钥匙在房子里，就一定会被找到。

3. 等价规律：如果两个命题具有相同的真值，那么它们具有等价关系。

例如，命题“猫是哺乳动物”和“所有哺乳动物都是猫”就是等价的。

4. 分配律：如果一个逻辑命题包含多个逻辑操作符，将它们分成两个组合不影响其含义。

例如，命题“(p∧q)∨r”和“(p∨r)∧(q∨r)”就是等价的。

5. 归纳法则：当推理一组命题时，我们通常可以通过研究一组具有相似特征的实例来了解整个集合的性质。

例如，如果我们希望证明所有偶数之和是偶数，我们可以归纳地首先证明2和4之和为6，接着证明6和6之和为12，以此类推。

通过这种归纳方法，我们可以得出结论：所有偶数之和是偶数。

6. 相反法则：只有证明命题的逆否命题为真，才能真正证明该命题为真。

例如，如果我们想证明“如果人类能够站立，那么他们就能够行走”，我们可以相反地批判性地假设人类不能行走，然后我们就可以推断出，他们也不能站立。

以上谓词逻辑推理定律是推理过程中注意的基本原则。

谓词逻辑知识点总结一、语言和推理的形式化语言和推理的形式化是数理逻辑的基础，它主要研究如何用严格的符号化方法来表示和分析自然语言中的语言和推理。

在谓词逻辑中，我们通常将自然语言中的命题分解成基本的谓词和常量，然后用谓词逻辑公式来表示这些命题。

例如，对于命题“人类都是有智慧的”，我们可以用P(x)来表示“x是人类”，用Q(x)表示“x有智慧”，那么这个命题可以表示为∀x(P(x)→Q(x))。

而推理的形式化则主要是研究如何用逻辑规则和演绎推理方法来推导出符合逻辑规律的结论。

二、谓词演算及其语义谓词逻辑的核心内容就是谓词演算，它是一种用来分析和推导谓词逻辑公式的形式系统。

谓词演算主要包括语法、语义和推导三个方面。

在语法方面，我们主要研究谓词逻辑公式的形式和结构，包括原子公式、复合公式和量词公式等。

在语义方面，我们主要研究谓词逻辑公式的意义和解释，包括谓词的扩展、量词的解释、模型的概念等。

在推导方面，我们主要研究如何用逻辑规则和推导方法来推导谓词逻辑公式的推导系统。

三、逻辑推导逻辑推导是谓词逻辑的核心内容之一，它主要研究如何用逻辑规则和演绎推理方法来推导出新的谓词逻辑公式。

在逻辑推导中，我们主要研究形式系统中的推理规则和推导方法，包括假言推理、析取推理、量词引入和消去等基本推理规则。

通过逻辑推导，我们可以推导出符合逻辑规律的结论，从而解决一些具体的逻辑问题。

四、完全正式系统完全正式系统是谓词逻辑的一个重要概念，它主要指的是一个完全形式化的逻辑系统，包括语法、语义和推导等方面。

在完全正式系统中，我们可以用严格的形式化方法来表示和分析逻辑语言和推理，从而解决一些具体的数理逻辑问题。

完全正式系统的建立对于谓词逻辑的发展具有重要意义，它不仅为逻辑学理论的研究提供了统一的规范框架，同时也为数理逻辑在实际应用中的推广提供了重要的理论基础。

五、争议在谓词逻辑的发展过程中，一些争议性问题也是不可避免的。

比如，有关谓词逻辑的语言和推理的形式化方法，不同的学者有着不同的观点和理论，针对谓词逻辑公式的语法和语义，也存在一些争议性问题。

第3章谓词逻辑谓词逻辑原子命题是命题逻辑中最基本的组成单元，不能对它再作进一步的分解，但同时也无法反映出某些原子命题的共同特征和相互关系。

例如，用p表示命题“小李是大学生”，用q表示命题“小王是大学生”，在命题逻辑的范畴中它们是两个独立的原子命题，p和q之间没有任何关系。

但是，命题“小李是大学生”和“小王是大学生”之间有着相同的结构和内在的联系，它们都具有相同的谓语（及宾语）“是大学生”，不同的只是主语，它们都描述了“是大学生”这样一个共同的特性；而使用原子命题表示时并没有能将这一共性刻画出来。

再如著名的苏格拉底三段论：凡是人都是要死的。

苏格拉底是人。

所以苏格拉底是要死的。

这个推理显然是正确的。

但是，如用p、q、r分别表示上面3个命题，由于p∧q?r不是永真式，因此它不是正确的推理；也就是说，当p和q都为真时，得不出r一定为真。

其根本原因在于命题逻辑不能将命题p、q、r间的内在的联系反映出来。

为了克服命题逻辑的局限性，引入了谓词和量词对原子命题和命题间的相互关系做进一步的剖析，从而产生了谓词逻辑。

谓词逻辑亦称一阶逻辑，它同命题逻辑一样，是数理逻辑中最基础的内容。

§3.1谓词、量词与自然语句形式化§3.1.1 谓词在谓词逻辑中，一般将原子命题分解为个体词和谓词两个部分。

定义3.1个体词（individual）是一个命题里表示思维对象的词，表示独立存在的具体或抽象的客体。

简单地讲，个体词就表示各种事物，相当于汉语中的名词。

具体的、确定的个体词称为个体常项，一般用a、b、c表示；抽象的、不确定的个体词称为个体变项，一般用x、y、z表示。

个体变项的取值范围称做个体域或论域（domain of the discourse），宇宙间一切事物组成的个体域称做全总个体域（universal domain of individuals）。

注：本书在提及论域时，如未特别说明，指的都是全总个体域。