1、1第 二 章 谓 词 逻 辑Predicate Logic2一二请在这里输入您的主要叙述内容整体概述三请在这里输入您的主要叙述内容请在这里输入您的主要叙述内容3 在命题逻辑中，主要研究命题和命题演算，其基本单位是原子命题，认为原子命题是不能再分解的。这样，有些推理用命题逻辑就难以确切地表示出来。例如，著名的苏格拉底三段论推理：前言4前 言苏格拉底三段论(Socrates syllogism)：所有人都是要死的。苏格拉底是人。所以苏格拉底是要死的。（Socrates,古希腊哲学家,公元前470前399）(孔子,中国伟大哲学家,公元前551前479)5前言在命题逻辑中，如果设：P：所有人都是要死的
2、；Q：苏格拉底是人；R：苏格拉底是要死的。前提：P,Q，结论：R。则(PQ)R表示上述推理，这个命题公式不是重言式。6 一个推理，得出矛盾的结论，问题在哪里呢?问题就在于这类推理中，各命题之间的逻辑关系不是体现在原子命题之间，而是体现在构成原子命题的内部成分之间，即体现在命题结构的更深层次上。对此，命题逻辑是无能为力的。所以，在研究某些推理时，有必要对原子命题作进一步分析，分析出其中的个体词，谓词和量词，研究它们的形式结构的逻辑关系、正确的推理形式和规则，这些正是谓词逻辑的基本内容。7前言在谓词逻辑中，如果设：H(x)：x是人。D(x)：x是要死的。a：苏格拉底。前提：(x)(H(x)D(x)
3、，H(a)结论：D(a)(x)(H(x)D(x)H(a)D(a)8前言又比如：P：张三是大学生Q：李四是大学生以上这些命题都具备有一个共同的特征就是：x是大学生。S(x)就可以代表这一类的命题。S(x)：x是大学生，a：张三，b：李四，S(a)：张三是大学生S(b)：李四是大学生9前言 主语 谓语 客（个）体 谓词客体可以独立存在，它可以是具体的，也可以是抽象的。而用来描述客体的性质或关系的即是谓词。为了刻画命题内部的逻辑结构，就需要研究谓词逻辑（Predicate Logic）。102-1 谓词的概念与表示2-2 命题函数与量词2-3 谓词公式与翻译 2-4 变元的约束 第二章 谓词演算2-
4、5 谓词演算的等价式与蕴含式 2-6 前束范式 2-7 谓词演算的推理理论 112-1 2-1 谓词的概念与表示 命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和谓语两部分组成。在谓词逻辑中，为了揭示命题内部结构及其不同命题的内部结构关系，就按照这两部分对命题进行分析，并且把主语称为个体或客体，把谓语称为谓词。12客体、谓词和命题的谓词形式 定义 在原子命题中，所描述的对象称为客体（；用以描述客体的性质或客体间关系的部分，称为谓词。客体，是指可以独立存在的事物，它可以是具体的，也可以是抽象的，如张明，计算机，精神等。表示特定的客体，称为客体常元，以a，b，c或带下标的ai，bi，c
5、i表示；表示不确定的客体，称为客体变元，以x，y，z或xi，yi，zi表示。13定义1：谓词（predicate）在命题中，用以刻画客体的性质或客体之间关系的词即是谓词，谓词相当于命题中的谓语部分。例如：他是三好学生 “他”是个体，“是三好学生”是表示个体性质的谓词5大于3(1)“5”和“3”是个体，“大于”是表示个体之间关系的谓词谓词的概念14谓词的表示：用大写英文字母 A,B,C,D,表示谓词，用小写字母表示客体。前面的例子可表示为：(1)A(x):x是三好学生，h:他，A(h):他是三好学生(2)G(x,y):x大于y，G(5,3):5大于315如何利用谓词表达命题：用谓词表达命题必须包
6、括谓词和客体两个部分。比如：A(x)可以表示“x是A”类型的命题，表达了客体的性质，称为一元谓词。B(x,y)可以表示“x小于y”类型的命题，表达了客体之间的关系，称为二元谓词。L(x,y,z)可以表示“点x在y与z之间”类型的命题，表达了客体之间的关系，称为三元谓词。用P(x1,x2,xn)表示n元谓词，在这里n个客体变元的顺序不能随意改动。16表示特定谓词，称为谓词常元表示不确定的谓词，称为谓词变元都用大写英文字母，如P，Q，R，或其带上、下标来表示。在本书中，不对谓词变元作更多地讨论。17 定义 一个原子命题用一个谓词(如P)和n个有次序的客体常元(如a1，a2，an)表示成P(a1，a
7、2，an)，称它为该原子命题的谓词填式或命题的谓词形式。应注意的是，命题的谓词填式中的客体出现的次序影响命题的真值，不是随意变动，否则真值会有变化。如上述例子中，L(b,a,c)是假。182-2 2-2 命题函数与量词 一般来说，当谓词P给定，x1,x2,xn是客体变元，P(x1,x2,xn)不是一个命题，因为他的真值无法确定，要想使它成为命题，要用n个客体常项代替n个客体变元。P(x1,x2,xn)就是命题函数。比如L(x,y)表示“x小于y”，那么L(2,3)表示了一个真命题“2小于3”。而 L(5,1)表示了一个假命题“5小于1”19 对于n元谓词P（x1,x2,xn），当n=1时，称一
8、元谓词；当n=2时，称为二元谓词，。特别地，当n=0，称为零元谓词。零元谓词是命题，这样命题与谓词就得到了统一。20 n元谓词不是命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个命题。但个体变元在哪些论域取特定的值，对命题的真值极有影响。例如，令S(x)：x是大学生。若x的论域为某大学的计算机系中的全体同学，则S(x)是真的；若x的论域是某中学的全体学生，则S(x)是假的；若x的论域是某剧场中的观众，且观众中有大学生也有非大学生的其它观众，则S(x)是真值是不确定的。21个体域(universe of discourse)：在命题函数中，命题变元的论述范围称为个体域。全总个体域
9、：个体域可以是有限的，也可以是无限的，把各种个体域综合在一起，作为论述范围的域，称为全总个体域。定义了全总个体域，为深入研究命题提供了方便。当一个命题没有指明论域时，一般都以全总个体域作为其论域。而这时又常常要采用一个谓词如P(x)来限制个体变元x的取值范围，并把P(x)称为特性谓词。22232-2.2 量词例题：符号化以下命题所有人都要死去。有的人的年龄超过百岁。以上给出的命题，除了有个体和谓词以外，还有表示数量的词，称表示数量的词为量词。量词有两种：全称量词(universal quantifier)存在量词(existential quantifier)24定义1全称量词(univers
10、al quantifier)用符号“”表示，“x”表示对个体域里的所有个体。(x)P(x)表示对个体域里的所有个体都有属性P。表达“对所有的”，“每一个”，“对任一个”，“凡”，“一切”等词。定义2存在量词(existential quantifier)用符号“”表示。x表示存在个体域里的个体。(x)P(x)表示存在个体域里的个体具有性质P。符号“”称为存在量词，用以表达“某个”，“存在一些”，“至少有一个”，“对于一些”等词。25现在对以上两个命题进行符号化，在进行符号化之前必须确定个体域。第一种情况个体域D为人类集合。设：D(x)：x是要死的。H(x)：x活百岁以上。则有(x)D(x)和
11、(x)H(x)这两个命题都是真命题26 第二种情况个体域D为全总个体域。不能符号化为(x)D(x)和(x)H(x)，因为:(x)D(x)表示宇宙间一切事物都要死的，这与原命题不符。(x)H(x)表示宇宙间一切事物中存在百岁以上，这与原命题不符。27因此必须引入一个新的谓词，将人分离出来。在全总个体域的情况下，以上两个命题叙述如下：(1)对于所有个体而言，如果它是人，则它要死去。(2)存在着个体，它是人并且活过百岁以上。于是，再符号化时必须引入一个新的谓词 M(x)：x是人。称这个谓词为特性谓词。28定义：特性谓词在讨论带有量词的命题函数时，必须确定其个体域，为了方便，可使用全总个体域。限定客体
12、变元变化范围的谓词，称作特性谓词。利用特性谓词，对以上两个命题进行符号化(1)(x)(M(x)D(x)(2)(x)(M(x)H(x)29使用量词时应注意的问题：在讨论有量词的命题函数时如果事先没有给出个体域，那么都应以全总个体域为个体域。对全称量词，特性谓词常做蕴含的前件。对存在量词，特性谓词常做合取项。30举例说明：例1“有些人是要死的”.解1：采用全体人作为个体域.设:D(x):x是要死的.原命题符号化成:(x)D(x)解2：采用全总个体域.设:H(x):x是人;D(x):x是要死的.原命题符号化成:(x)(H(x)D(x)31例2“凡人都是要死的”.解1:采用全体人作为个体域.设:D(x
13、):x是要死的.原命题符号化成:(x)D(x)解2:采用全总个体域.设:H(x):x是人;D(x):x是要死的.原命题符号化成:(x)(H(x)D(x)32例3:“存在最小的自然数”。解1:采用全体自然数作为个体域.设:G(x,y):xy;原命题符号化成:(x)(y)G(x,y)注意量词顺序:(y)(x)G(x,y):“没有最小的自然数”.解2:设:N(x):x是自然数;G(x,y):xy;原命题符号化成:(x)(N(x)(y)(N(y)G(x,y)33例4:“不存在最大的自然数”。解:设:N(x):x是自然数;G(x,y):xy;原命题符号化成:(x)(N(x)(y)(N(y)G(x,y)或
14、:(x)(N(x)(y)(N(y)G(x,y)34例5:“火车比汽车快”。解:设:T(x):x是火车;C(x):x是汽车;Q(x,y):x比y快原命题符号化成:(x)(T(x)(y)(C(y)Q(x,y)或:(x)(y)(T(x)C(y)Q(x,y)35例6:“有的汽车比火车快”。解:设:C(x):x是汽车;T(x):x是火车;Q(x,y):x比y快原命题符号化成:(x)(C(x)(y)(T(y)Q(x,y)或:(x)(y)(C(x)T(y)Q(x,y)36例7:“有些病人相信所有的医生”。解:设:P(x):x是病人;D(x):x是医生;B(x,y):x相信y原命题符号化成:(x)(P(x)(
15、y)(D(y)B(x,y)37例8:“存在唯一的对象满足性质P”。解:设:P(x):x满足性质PE(x,y):x和y是同一个个体原命题符号化成:(x)(P(x)(y)(P(y)E(x,y)38 练习：试用量词、谓词表示下列命题：所有大学生都热爱祖国；每个自然数都是实数；一些大学生有远大理想；有的自然数是素数。39 解 令S(x)：x是大学生，L(x)：x热爱祖国，N(x)：x是自然数，R(x)：x是实数，I(x)：x有远大理想，P(x)：x是素数。则例中各命题分别表示为：(x)(S(x)L(x)(x)(N(x)R(x)(x)(S(x)I(x)(x)(N(x)P(x)40 在该例的解答中，由于命
16、题中没有指明个体域，这便意味着各命题是在全总个体域中讨论，因而都使用了特性谓词，如S(x)、N(x)。而且还可以看出，量词与特性谓词的搭配还有一定规律，即全称量词后跟一个条件式，而特性谓词作为其前件出现；存在量词后跟一个合取式，特性谓词作为一个合取项出现。41 如果在解答时，指明了个体域，便不用特性谓词，例如在、中令个体域为全体大学生，和中的个体域为全部自然数，则可符号化为：(x)L(x)(x)R(x)(x)I(x)(x)P(x)42 谓词前加上了量词，称为谓词的量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同数学
17、中的函数f(x)，的值是不确定的，但 可确定其值。dx)x(fbadx)x(f43作 业2-1，2-2，P59-60 (1)a),c),e),g)(2)a),c),e),g),i),k)442-3 谓词公式与翻译书上已经给出谓词，命题函数，谓词表达式。在数理逻辑中需要对能够进行谓词演算的公式进行准确的定义。这样以后我们不再说谓词，命题函数，谓词表达式等,而只研究谓词公式。452-3.1 谓词逻辑字母表：个体常项:a,b,c,a1,b1,c1,个体变项:x,y,z,x1,y1,z1,函数符号:f,g,h,f1,g1,h1,谓词符号:F,G,H,F1,G1,H1,量词符号:,联结词符号:,括号与逗
18、号:(),，46 我们把 A(x1,x2,xn)称为谓词演算的原子公式，其中x1,x2,xn是客体变元，原子公式包括下述形式：Q，A(x),A(x,y),A(f(x),y),A(x,y,z),A(a,y)等。定义2-3.1 谓词公式是合式公式。若A是合式公式，则(A)是合式公式。若A和B都是合式公式，则(AB)，(AB)，(AB)，(AB)）都是合式公式。如果A是合式公式，x是A中出现的任何变元，则(x）A和(x）A都是合式公式。只有经过有限次地应用规则（1）、(2)、(、(所得到的公式是合式公式。2-3.2 谓词公式47谓词逻辑的翻译 把一个文字叙述的命题，用谓词公式表示出来，称为谓词逻辑的
19、翻译或符号化；反之亦然。一般说来，符号化的步骤如下：正确理解给定命题。必要时把命题改叙，使其中每个原子命题、原子命题之间的关系能明显表达出来。48 把每个原子命题分解成个体、谓词和量词；在全总个体域讨论时，要给出特性谓词。找出恰当量词。应注意全称量词(x)后跟条件式，存在量词(x)后跟合取式。用恰当的联结词把给定命题表示出来。49 例 将命题“没有最大的自然数”符号化。解 命题中“没有最大的”显然是对所有的自然数而言，所以可理解为“对所有的x，如果x是自然数，则一定还有比x大的自然数”，再具体点，即“对所有的x如果x是自然数，则一定存在y，y也是自然数，并且y比x大”。令N(x):x是自然数，
20、G(x,y):x大于y，则原命题表示为：(x)(N(x)(y)(N(y)G(y,x)。50 例 将语句“今天有雨雪，有些人会摔跤”符号化。解 本语句可理解为“若今天下雨又下雪，则存在x，x是人且x会摔跤”。令R:今天下雨，S:今天下雪，M(x):x是人，F(x):x会跌跤，则本语句可表示为：R S(x)(M(x)F(x)。由于人们对命题的文字叙述含意理解的不同，强调的重点不同，会影响到命题符号化的形式不同。51例 将下列命题符号化。（1 1）尽管有人聪明，但并非所有人都聪明。（2 2）这只大红书柜摆满了那些古书。解 （1 1）令C C（x x）：x x聪明；M M（x x）：x x是人。则命题
21、（1 1）可符号化为 x x（M M（x x）CC（x x）x x（M M（x x）CC（x x）（2 2）令F F（x x，y y）：x x摆满了y y；R R（x x）：x x是大红书柜；Q Q（x x）:x x是古书；a a：这只；b b：那些。则命题（2 2）可符号化为R R（a a）QQ（b b）FF（a a，b b）52作 业2-3 P62 (2)(3)(6)53 在谓词公式中，、后面所跟的x叫做量词的指导变元或作用变元，xA(x),xA(x),xP(x)xP(x)中的A(x)A(x)和P(x)P(x)分别叫做量词 和 的作用域或辖域。即当量词用于一谓词或复合谓词表达式时，该谓词或
22、复合谓词表达式称为(domains of quantifiers)。在作用域中x x的一切出现称为约束出现，即不可以取值代入的变元称为(binding variables)。除去约束变元以外所出现的变元称为自由变元，即可取值代入的变元称为(free variables)。见P-63页例题1。2-4 2-4 变元的约束542-4.1 变元的约束定义1：指导变元（作用变元）谓 词 公 式 中 的 一 部 分 公 式 形 式 为(x)P(x)，或(x)P(x)，这里的，后面所跟的x，称为相应量词的指导变元（作用变元）。例如：(x)(F(x)(y)(G(y)H(x,y)2-4 2-4 变元的约束55定
23、义2：量词作用域（量词辖域）：给定谓词公式中，形式为(x)P(x)，(x)P(x)中的P(x)称为相应量词的作用域（辖域）。例如:(x)(F(x)(y)(G(y)H(x,y)56定义3：约束变元(bound variable)：在作用域中x的一切出现，称为x在该谓词公式中的约束出现，所有约束出现的变元，叫做约束变元。例如:(x)(F(x)(y)(G(y)H(x,y)57定义4：自由变元(free variable)：在谓词公式中，除去约束变元以外所出现的变元，称作自由变元。自由变元可以在作用域外出现，也可以在作用域中出现，但它不受相应量词中的指导变元的约束，故我们可把自由变元看作是公式中的参数
24、。例如:(y)(G(y)H(x,y)举例说明：P63 例158例 指出下列各式量词的辖域及变元的约束情况：（1 1）x x（F F（x x，y y）G G（x x，z z）（2 2）x x（P P（x,yx,y）x y Ry R（x x，y y）（3 3）x x（F F（x x）G G（y y）y y（H H（x x）MM（x x，y y，z z）59解 （1 1）对于 x x的辖域是A=A=（F F（x x，y y）G G（x x，z z），在A A中，x x是约束出现的，而且约束出现两次，y y，z z均为自由出现，而且各自由出现一次。（2 2）对于 x x的辖域是（P P（x,yx,y）
25、x y Ry R（x x，y y），x的辖域是R（x，y），y y的辖域是R R（x x，y y），在整个公式中，x全称约束出现一次，存在约束出现1次，y自由出现1次，约束出现一次。（3 3）对于 x x的辖域是（F F（x x）G G（y y），其中x x是约束出现的，而y y是自由出现的。对 y y的辖域是（H H（x x）MM（x x，y y，z z），其中y y是约束出现的，而x x，z z是自由出现的。在整个公式中，x x约束出现一次，自由出现两次，y y约束出现一次，自由出现一次，z z仅自由出现一次。60 由前所述，P(x1,x2,xn)称为n元谓词。他有n个相互独立的客体变元x
26、1,x2,xn，若对其中的 k个变元进行约束，则P(x1,x2,xn)称变成n-k元谓词。因此，谓词公式中如果没有自由变元出现，则该式就成为一个命题。为了避免由于变元的约束与自由同时出现，引起概念上的混乱，故可以对约束变元进行更名。使得一个变元在一个公式中具有一种形式出现，即呈自由出现或约束出现。612-4.2约束变元换名(rename)规则对公式中的约束变元，遵照一定规则更改名称符号，称为约束变元的换名。其规则为：（1）对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余部分不变。（2）换名时一定要更改为作用域中没有出现过的变元名称。6
27、2例如:(x)(A(x)B(x)(x)A(x)(x)B(x)H(x,y)(x)F(x)(y)(G(y)H(x,y)(y)(A(y)B(y)(x)A(x)(y)B(y)H(x,y)(z)F(z)(u)(G(u)H(x,u)632-4.3 自由变元代入(substitute)规则 对于公式中的自由变元，也允许更改，这种更改叫做代入。其规则为：（1）对于谓词公式中的自由变元，可以作代入，代入时需要对公式中出现该自由变元的每一处进行代入。（2）用以代入的变元与原公式中所有变元的名称不能相同。见P-65页例题3。64例如:A(x)B(x)(x)A(x)B(x)H(x,y)(x)F(x)(y)(G(y)H
28、(x,y)A(y)B(y)(x)A(x)B(y)H(s,t)(x)F(x)(y)(G(y)H(s,y)652-4.4 消去量词需要指出，量词作用域中的约束变元，当论域的元素是有限时，客体变元的所有可能的取代是可枚举的。设论域元素为a1，a2，an。为有限个体域。则(x)A(x)A(a1)A(a2)A(an)(x)A(x)A(a1)A(a2)A(an)66例:个体域D=a,b,c,则(x)(y)F(x,y)(x)(F(x,a)F(x,b)F(x,c)(F(a,a)F(a,b)F(a,c)(F(b,a)F(b,b)F(b,c)(F(c,a)F(c,b)F(c,c)示例：P65(2)a),b),(3
29、)a)67P65(2)a)(x)P(x)P(a)P(b)P(c)e)(x)R(x)(x)S(x)(R(a)R(b)R(c)(S(a)S(b)S(c)(3)a)(x)(P(x)Q(x)(P(1)Q(1)(P(2)Q(2)(TF)(FT)T682-4.5量词的次序命题中的多个量词，约定从左到右的次序读出。量词对变元的约束，量词的次序不能更改，否则与原命题意义不符。比如：对任意的x，存在y，使得x+y=5。取个体域为实数集。设：H(x,y)：x+y=5 则有：(x)(y)H(x,y)。这是一个真命题。但是如果将量词顺序颠倒，得 (y)(x)H(x,y)此式的含义为“存在着y，对于任意的x，都有x+y
30、=5”，这就成了假命题。69作业(2-4)P65(2)c)d)(4)(5)70公式赋值或解释 一般情况下，谓词逻辑中的公式常包含：客体常元、客体变元（约束变元或自由变元）、函数变元、谓词变元等，当客体变元由确定的客体所取代，谓词变元用特定的谓词所取代时，就称作对谓词公式赋值或者解释。一个谓词公式经过赋值以后，就成为具有确定真值T或F的命题。下面给出赋值的一般定义。2-5 2-5 谓词演算的等价式和蕴涵式71定义 谓词逻辑公式的一个解释I I，是由非空区域D D和对G G中常项符号、函数符号、谓词符号以下列规则进行的一组指定组成：（1 1）对每一个常项符号指定D D中一个元素。（2 2）对每一个
31、n n元函数符号，指定一个函数。（3 3）对每一个n n元谓词符号，指定一个谓词。显然，对任意公式G G，如果给定G G的一个解释I I，则G G在I I的解释下有一个真值，记作T TI I（G G）。72例 指出下面公式在解释I I下的真值。（1 1）G G x x（P P（f f（x x）QQ（x x，f f（a a）；（2 2）H H x x（P P（x x）QQ（x x，a a）。给出如下的解释I I：D=2D=2，33；a a：2 2；f f（2 2）=3=3、f f（3 3）=2=2；P P（2 2）=0=0、P P（3 3）=1=1；Q Q（2 2，2 2）=1=1、Q Q（2
32、2，3 3）=1=1、Q Q（3 3，2 2）=0=0、Q Q（3 3，3 3）=1=1；73解 （1 1）G G （P P（f f（2 2）QQ（2 2，f f（2 2）（P P（f f（3 3）QQ（3 3，f f（2 2）（P P（3 3）QQ（2 2，3 3）（P P（2 2）QQ（3 3，3 3）=（1111）（0101）=1=1（2 2）H=PH=P（2 2）QQ（2 2，2 2）PP（3 3）QQ（3 3，2 2）=0110=0=0110=074 定义2-5.12-5.1 给定任何两个谓词公式Wff Wff A A和Wff Wff B B，设他们有共同的个体域E E，若对A A和
33、B B的任一组变元进行赋值，所得命题的真值都相同，则称谓词公式A A和B B在E E上是等价的，并记作A A B B。定义2-5.02-5.0 给定个体域E E及公式A A中各谓词符号的解释I I，如果A A中个体变元x x1 1,x,xn n分别取值u u1 1,u,un n时A A为真，则称；当x x1 1,x,xn n无论取E E中任何个体u u1 1,u,un n,A A在u u1 1,u,un n处均为真，则称。75 定义2-5.32-5.3 一个谓词公式wffA，如果在所有赋值下都为假，则称该wffA为不的。公式A不可满足时也称A为。定义2-5.22-5.2 给定任意谓词公式wff
34、A,其个体域为E，对于A的所有赋值，wffA都为真，则称Wff 定义2-5.42-5.4 一个谓词公式wffA，如果至少在一种赋值为真，则称该wffA为的。有了谓词公式的等价和永真等概念，就可以讨论谓词演算的一些等价式和蕴含式。762-5.1命题公式的推广命题演算中的等价公式和蕴含公式都可以推广到谓词演算中使用。例1：AA,令A=(x)F(x),得到 (x)F(x)(x)F(x)例2：ABAB,令A=P(x),B=Q(y),得到 P(x)Q(y)P(x)Q(y)772-5.2 量词与联结词 之间的关系定理：量词否定等价式（P67）(1)(x)P(x)(x)P(x)(2)(x)P(x)(x)P(
35、x)可以在有限个体域中得到证明。78设P(x)(x)表示个体x x具有性质P P。于是下面的语句表示的意义是等价的：“不是所有的 x x 都具有性质P P。”“存在不具有性质P P的 x x 。”于是得到：（x x）P(x)P(x)（x x）P(x)P(x)同样，“不存在具有性质P P的 x x 。”“所有的 x x 都不具有性质P P。”于是得到：（x x）P(x)P(x)（x x）P(x)P(x)79 2-5.3 量词作用域的收缩与扩张 如果量词作用域内有命题（命题内已经无客体变元，真假值已经确定了），则该命题可以移到量词作用域的外边。称之为量词作用域的收缩。(x)x)(A(x)B)(A(
36、x)B)(x)A(x)x)A(x)B B (x)x)(A(x)B)(A(x)B)(x)A(x)x)A(x)B B (x)x)(A(x)B)(A(x)B)(x)A(x)x)A(x)B B (x)x)(A(x)B)(A(x)B)(x)A(x)x)A(x)B B 80例1:(x)(F(x)G(y)(x)F(x)G(y)例2:(x)(y)(F(x)G(y)(x)(F(x)(y)G(y)(x)F(x)(y)G(y)例3:(x)(F(x)G(y)(x)F(x)G(y)例4:(x)(y)(F(x)G(y)(x)(F(x)(y)G(y)(x)F(x)(y)G(y)81 量词作用域的扩张:(x)A(x)x)A(
37、x)B B)(x)x)(A(x)A(x)B B)(x)A(x)x)A(x)B B)(x)x)(A(x)A(x)B B)(B B (x)(A(x)x)(A(x)(x)x)(B B A(x)A(x)(B B (x)(A(x)x)(A(x)(x)x)(B B A(x)A(x)证明示例见P-68P-68页例2 2 82例1：(x)(A(x)B)(x)A(x)B证明:(x)(A(x)B)(x)(A(x)B)(x)A(x)B (x)A(x)B (x)A(x)B例2：(x)(BA(x)B(x)A(x)证明:(x)(BA(x)(x)(BA(x)B(x)A(x)B(x)A(x)B(x)A(x)83例3：(x)(
38、A(x)B)(x)A(x)B证明:(x)(A(x)B)(x)(A(x)B)(x)A(x)B (x)A(x)B (x)A(x)B例4：(x)(BA(x)B(x)A(x)证明:(x)(BA(x)(x)(BA(x)B(x)A(x)B(x)A(x)B(x)A(x)84 （4 4）量词与命题联结词之间的一些等价式 (x)x)(A(x)B(x)A(x)B(x)(x)A(x)x)A(x)(x)B(x)x)B(x)(x)x)(A(x)B(x)A(x)B(x)(x)A(x)x)A(x)(x)B(x)x)B(x)我们称(1)为“对满足分配律”，(2)为“对满足分配律”。但是要注意：“对”以及“对”不存在分配等价式
39、。85联欢会上所有人既唱歌又跳舞和联欢会上所有人唱歌且所有人跳舞。这两个语句意义相同。因此有：(x)(A(x)B(x)(x)A(x)(x)B(x)根据上式有：(x)(A(x)B(x)(x)(A(x)B(x)(x)(A(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)(x)A(x)(x)B(x)86（5 5）量词与命题联结词之间的一些蕴涵式 (x)A(x)x)A(x)(x)B(x)x)B(x)(x)x)（A(x)B(x)A(x)B(x)）(x)x)(A(x)B(x)A(x)B(x)(x)A(x)x)A(x)(x)B(x)x)B(x)(x)x)(A(x)A(x)B(x)B(x)
40、(x)A(x)x)A(x)(x)B(x)x)B(x)(x)x)(A(x)A(x)B(x)B(x)(x)A(x)x)A(x)(x)B(x)x)B(x)定义1-7.1 设A A为联结词 ，的谓词公式，A A*为将A A中符号，T T，F F，,分别换为，F F，T,T,，后所得的公式，那么称A A*为A A的。87（5 5）量词与命题联结词之间的一些蕴涵式 (x)A(x)x)A(x)(x)B(x)x)B(x)(x)x)（A(x)B(x)A(x)B(x)）(x)x)(A(x)B(x)A(x)B(x)(x)A(x)x)A(x)(x)B(x)x)B(x)(x)x)(A(x)A(x)B(x)B(x)(x)
41、A(x)x)A(x)(x)B(x)x)B(x)(x)x)(A(x)A(x)B(x)B(x)(x)A(x)x)A(x)(x)B(x)x)B(x)定义1-7.1 设A A为联结词 ，的谓词公式，A A*为将A A中符号，T T，F F，,分别换为，F F，T,T,，后所得的公式，那么称A A*为A A的。88（6 6）多个量词的使用 全称量词与存在量词在公式中出现的次序不能随意更换。具有两个量词的谓词公式有如下关系：(x)x)(y)A(x,y)A(x,y)(y)(x)A(x,y)x)A(x,y)(x)x)(y)A(x,y)A(x,y)(y)(x)A(x,y)x)A(x,y)(x)x)(y)A(x,
42、y)A(x,y)(y)(x)A(x,y)x)A(x,y)(y)(x)A(x,y)x)A(x,y)(x)x)(y)A(x,y)A(x,y)(y)(x)A(x,y)x)A(x,y)(x)x)(y)A(x,y)A(x,y)(x)x)(y)A(x,y)A(x,y)(y)(x)A(x,y)x)A(x,y)(x)x)(y)A(x,y)A(x,y)(y)(x)A(x,y)x)A(x,y)(y)(x)A(x,y)x)A(x,y)(x)x)(y)A(x,y)A(x,y)等价式蕴涵式89作业(2-5)P72(2)c)(4)(7)90它具有如下形式：(Q1x1)(Q2x2)(Qkxk)B 其中Qi(1ik)为或，B
43、为不含有量词的公式。称Q1x1Q2x2Qkxk为公式的首标。特别地，若中无量词，则也看作是前束范式。定义2-6.1 2-6.1 一个公式，如果量词均非否定地出现在公式的最前面，且它们的作用域，延伸到整个公式的末尾，则该公式叫做prenex normal forms)prenex normal forms)2-6 2-6 前束范式91 可见，前束范式的特点是，所有量词均非否定地出现在公式最前面，且它的辖域一直延伸到公式之末。例如，(x)(y)(z)(P(x,y)Q(y,z),R(x,y)等都是前束范式，而(x)P(x)(y)Q(y)，(x)(P(x)(y)Q(x,y)不是前束范式。92 定理2-
44、6.12-6.1（）任意一个谓词公式，均和一个前束范式等价。化WffWff为前束范式的步骤：（1）内移“”号 根据量词转化公式，利用德摩.根定律将“”号内移到命题变元或谓词填式的前面。（）利用换名、代入规则使所有约束变元均不同，并且自由变元及约束变元亦不同。（2）前移量词 根据量词辖域的收缩和扩张公式，把量词移到全式的最前面。见P-73页例题1、2、3和P-74页例题4。93 对任意公式P P，变元x x，若xPxP，则P P。记为：2-7 2-7 谓词演算的推理理论)()/()(可代入对xcxcPxxP94提问与解答环节Questions and answers95感谢参与本课程，也感激大家对我们工作的支持与积极的参与。课程后会发放课程满意度评估表，如果对我们课程或者工作有什么建议和意见，也请写在上边结束语96谢谢您的观看与聆听Thank you for watching and listening
