第2章 谓词逻辑.

Presentation on theme: "第2章 谓词逻辑."— Presentation transcript:

1 第2章 谓词逻辑

2 在命题逻辑中，我们把命题分解到原子命题为止，认为原子命题是不能再分解的，仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。
实际上，简单命题还可以进行分解，例如，“王平是大学生”这一简单命题可以分解为主语(王平)和谓语(是大学生)，命题逻辑反映不出这一特点。 其次，如下两个简单命题“王平是大学生”和“李明是大学生”，有一个共同特点——是大学生，这一共性在命题逻辑中也表示不出来。因此，有必要推广命题逻辑。 第 2 章 谓词逻辑

3 第 2 章 谓词逻辑 第三，有些简单而正确的推理过程在命题演算里不能得到证明。例如著名的苏格拉底三段论：
“人都是要死的，苏格拉底是人，所以苏格拉底是要死的。” 在命题逻辑中，三个原子命题分别用P，Q，R表示，现在要证明PQR，即证明PQR是重言式，但这在命题逻辑中是不可能的。因此从推理的角度看，也有必要推广命题逻辑。 谓词逻辑就是命题逻辑的自然推广。本章介绍的谓词逻辑内容仅限于一阶谓词逻辑或狭义谓词逻辑，即谓词中的变元不再是谓词变元。 第 2 章 谓词逻辑

4 第 2 章 谓词逻辑 本章内容提要： 1.个体、谓词和量词的概念 2.谓词演算公式 3.谓词演算的等值公式 4.前束范式 5.推理理论
6.谓词逻辑在计算机科学中的应用 第 2 章 谓词逻辑

5 2.1.1 个体 2.1 个体 、谓词和量词 定义2.1 可以独立存在的物体称为个体，它可以是一个具体的事物，也可以是一个抽象的概念。
定义2.1 可以独立存在的物体称为个体，它可以是一个具体的事物，也可以是一个抽象的概念。 如王平，李明，计算机，离散数学，精神等都可以作为个体。 定义2.2 将表示具体的或确定的个体称为个体常元，而将表示抽象的或泛指的（或者说取值不确定的）个体称为个体变元。 个体常元一般用小写英文字母a,b,c…或带下标的ai,bi,ci…表示，个体变元一般用小写英文字母x,y,z…或带下标的xi,yi,zi…表示。 2.1 个体 、谓词和量词

6 2.1.1 个体 2.1 个体 、谓词和量词 定义2.3 个体变元的取值范围称为个体域或论域，把宇宙间一切事物组成的个体域称为全总个体域。
定义2.3 个体变元的取值范围称为个体域或论域，把宇宙间一切事物组成的个体域称为全总个体域。 个体域可以是有穷集合，例如{1,2,3,4,5}，{a,b,c}等，也可以是无穷集合，例如自然数集，实数集等。同时约定，本书在论述或推理中如无指明所采用的个体域，则都是使用全总个体域。 2.1 个体 、谓词和量词

7 2.1.2 谓词 2.1 个体 、谓词和量词 定义2.4 表示单个个体的性质或两个以上个体关系的词叫谓词。
定义2.4 表示单个个体的性质或两个以上个体关系的词叫谓词。 定义2.5 表示具体性质或关系的谓词称为谓词常元，表示抽象的或泛指的性质或关系的谓词称为谓词变元。 无论是谓词常元或变元都用大写英文字母P,Q,R…或带下标的Pi,Qi,Ri…表示，要根据上下文区分。 2.1 个体 、谓词和量词

8 2.1.2 谓词 定义2.6 由一个谓词(如P)和n个个体变元(如x1，x2，…，xn)组成的P(x1，x2，…，xn)，称它为n元原子谓词或n元命题函数，简称n元谓词。 当n=1时，称一元谓词；当n=2时，称为二元谓词，…。特别地，当n=0，称为零元谓词，即不带个体变元的谓词为零元谓词。零元谓词是命题，这样命题与谓词就得到了统一，因而可将命题看成特殊的谓词。 2.1 个体 、谓词和量词

9 2.1.2 谓词 例2.1 分析下列命题的个体与谓词。 （1）5是质数。 解 “5”是个体常元，“…是质数”是谓词，记为P。这里的谓词是一元谓词，属于谓词常元。 2.1 个体 、谓词和量词

10 2.1.2 谓词 （2）张三与李四是同学。 解 “张三”与“李四”是个体常元，分别记为a，b，“…与…是同学”是谓词，记为Q。这里的谓词是二元谓词，属于谓词常元。 （3）x与y具有关系R。 解 “x”与“y”是个体变元，谓词为R。这里的谓词是二元谓词，属于谓词变元。 2.1 个体 、谓词和量词

11 2.1.2 谓词 2.1 个体 、谓词和量词 例2.2 用个体，谓词表示下列命题。 （1）张华是大学生。
例2.2 用个体，谓词表示下列命题。 （1）张华是大学生。 解 令a：张华； S(x)：x是大学生。整个命题可表示为：S(a)。 说明： ①若x的个体域为某大学计算机系的全体学生，则S(a)为真； ②若x的个体域为某中学的全体学生，则S(a)为假； ③若x的个体域为某电影院中的观众，则S(a)真值不确定。所以个体变元在哪些个体域取特定的值，对命题的真值极有影响。 2.1 个体 、谓词和量词

12 2.1.2 谓词 （2）武汉位于重庆和上海之间。 解 令a：武汉； b：重庆； c：上海； P(x,y,z)：x位于y和z之间。整个命题可表示为P(a,b,c)。 说明：显然P(a,b,c)为真，但P(b,a,c)为假。所以个体变元的顺序影响命题真值，不能随意改动。 2.1 个体 、谓词和量词

13 2.1.3 量词 定义2.7 表示个体常元或变元之间数量关系的词叫量词；表示“全部”，“所有的”，“一切的”，“每一个”，“任意的”等数量关系的词叫全称量词，用符号“”表示；表示“存在一些”，“有一些”，“至少有一个”等数量关系的词叫存在量词，用符号“”表示；表示“存在惟一”，“恰有一个”等数量关系的词叫存在惟一量词，用符号“！”表示。 2.1 个体 、谓词和量词

14 2.1.3 量词 2.1 个体 、谓词和量词 注意：量词的优先级高于任何联结词，所以(x)P(x1,x2,…,xn)、(x)P(x1,x2,…,xn)、可分别写成xP(x1,x2,…,xn)、xP(x1,x2,…,xn)，但要注意明确量词的辖域（辖域将在下一节讨论）。

15 2.1.3 量词 2.1 个体 、谓词和量词 例2.3 符号化下列命题（设个体域为整数集合）。 （1）所有的整数都是有理数。
例2.3 符号化下列命题（设个体域为整数集合）。 （1）所有的整数都是有理数。 （2）有些整数是奇数。 （3）存在着惟一的偶素数。 解 （1）令P(x)：x是有理数，则命题可表示为：xP(x)。 （2）令Q(x)：x是奇数，则命题可表示为：xQ(x)。 （3）令R(x)：x是偶数，S(x)：x是素数，则命题可表示为！x(R(x)S(x))。 2.1 个体 、谓词和量词

16 2.1.3 量词 定义2.8 若一个谓词P(x)是用来限制个体变元的取值范围，那么称谓词P(x)为特性谓词。 在使用全总个体域时，对个体变化的真正取值范围，用特性谓词加以限制。一般地，对全称量词，将特性谓词作蕴含的前件；对存在量词，将特性谓词作合取项。 2.1 个体 、谓词和量词

17 2.1.3 量词 例2.4 用全总个体域对例2.3中的所有命题进行符号化。 解 在例2.3的基础上增加一个特性谓词I(x)：x是整数。则各命题可表示为： （1）x(I(x)P(x)) （2）x(I(x)Q(x)) （3）！x(I(x)R(x)S(x)) 2.1 个体 、谓词和量词

18 2.1.3 量词 练习 将下列命题符号化。 (1)天下乌鸦一般黑。 (2)任何金属都可以溶解在某种液体中。 2.1 个体 、谓词和量词

19 2.1.3 量词 在谓词前加上量词，称为谓词的量化。若一个谓词中所有个体变元都量化了，则该谓词就变成了命题。这是因为在谓词被量化后，可以在整个个体域中考虑命题的真值了。这如同数学中的函数f(x)， 的值是不确定的，但 可确定其值。 2.1 个体 、谓词和量词

20 2.2.1 谓词公式与翻译 定义2.9 由n元谓词P和n个个体变元x1，x2，…，xn所构成的不含命题联结词和量词的谓词表达式P(x1，x2，…，xn)称为谓词逻辑中的原子谓词公式，简称原子公式。 由定义可知，一个命题或一个命题变元也称为原子公式，也就是说，当n=0时，P(x1，x2，…，xn)为原子命题P。 2.2 谓词 公式

21 2.2.1 谓词公式与翻译 2.2 谓词 公式 定义2.10 谓词公式归纳定义如下： （1）原子公式是谓词公式；
定义2.10 谓词公式归纳定义如下： （1）原子公式是谓词公式； （2）如果α是谓词公式，则α也是谓词公式； （3）如果α和β是谓词公式，则αβ，αβ，β→α和αβ也都是谓词公式； （4）如果α是谓词公式，x是个体变元，则xα(x)，xα(x)和！xα(x)也都是谓词公式； （5）只有有限次地应用（1）～（4）构成的符号串才是谓词公式。 2.2 谓词 公式

22 2.2.1 谓词公式与翻译 由定义可知，谓词公式是由原子公式、命题联结词、量词以及圆括号按照上述规则组成的一个符号串。因此，命题逻辑中的命题公式是谓词公式的一个特例。 为叙述方便，我们下面讨论只含“x”和“x”的谓词公式，事实上，量词“！x”可以通过量词“x”和“x”来表示。 2.2 谓词 公式

23 2.2.1 谓词公式与翻译 2.2 谓词 公式 一般来说，将自然语言翻译成谓词公式主要有以下几个步骤：
一般来说，将自然语言翻译成谓词公式主要有以下几个步骤：  （1）确定个体域，如无特别说明，一般使用全总个体域； （2）根据个体域，分析命题中的个体、个体性质以及各个个体间的关系，确定谓词； （3）根据表示数量的词确定量词； （4）利用联结词将整个命题符号化。 2.2 谓词 公式

24 2.2.1 谓词公式与翻译 例2.5 将下列命题符号化。 （1）教室里有同学在讲话。 解 因为题中没有特别指明个体域，所以这里采用全总个体域。 令S(x)：x是同学， R(x)：x在教室里，T(x)：x在讲话，则命题可符号化为：x(S(x)R(x)T(x))。 2.2 谓词 公式

25 2.2.1 谓词公式与翻译 （2）在我们班中，并非所有同学都能取得优秀成绩。 解 令S(x)：x是同学， C(x)：x在我们班中， E(x)：x能取得优秀成绩，则命题可符号化为：x((S(x)C(x))E(x))。或者，此命题也可以理解为“在我们班中存在不能取得优秀成绩的同学”，则该命题也可符号化为：x(S(x)C(x)E(x))。 2.2 谓词 公式

26 2.2.1 谓词公式与翻译 （3）没有最大的自然数。 解 命题中“没有最大的”显然是对所有的自然数而言，所以可理解为“对任意的自然数x，存在着比x更大的自然数”。令N(x):x是自然数， G(x,y):x大于y，则命题可符号化为：x(N(x)y(N(y)G(y,x)))。 2.2 谓词 公式

27 2.2.1 谓词公式与翻译 （4）今天有雨雪，有些人会跌跤。 解 令R：今天下雨， S：今天下雪，M(x)：x是人，F(x)：x会跌跤，则命题可符号化为：(RS)x(M(x)F(x))。 2.2 谓词 公式

28 2.2.1 谓词公式与翻译 定义2.11 设α是谓词公式，β是α中连续的符号串且也是谓词公式，则称β是α的子公式。 例如，α=x(P(x)y(Q(y)R(x,y)))，β=y(Q(y)R(x,y))，则β是α的子公式。而P(x)y不是谓词公式，因而也不是α的子公式。 2.2 谓词 公式

29 自由变元与约束变元 定义2.11 设α是一个谓词公式，xβ(x)和xγ(x)是α的子公式，则称xβ(x)与xγ(x)是α的约束部分，x称为是约束出现的。约束出现的变元称为约束变元，不是约束出现的变元称为自由变元。β(x)称为是x在α中的辖域（或作用域），γ(x)称为是x在α中的辖域。 2.2 谓词 公式

30 2.2.2 自由变元与约束变元 2.2 谓词 公式 确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体地讲：
自由变元与约束变元 确定一个量词的辖域即是找出位于该量词之后的相邻接的子公式，具体地讲：   ① 若量词后有括号，则括号内的子公式就是该量词的辖域； ② 若量词后无括号，则与量词邻接的子公式为该量词的辖域。 另外，当多个量词连续出现，它们之间无括号分隔时，后面的量词在前面量词的辖域之中，且量词对变元的约束与量词的次序有关，一般不能随意调动。 2.2 谓词 公式

31 2.2.2 自由变元与约束变元 2.2 谓词 公式 例2.6 指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域。
自由变元与约束变元 例2.6 指出下列谓词公式中的自由变元和约束变元，并指明量词的辖域。 （1）x(P(x)y(Q(y)R(x,y))) （2）x(P(x)Q(y))yR(x,y) 解 （1）量词x的辖域是P(x)y(Q(y)R(x,y))，y的辖域是Q(y)R(x,y)；x和y的所有出现都是约束出现。 （2）量词x的辖域是P(x)Q(y)，这里的x是约束变元，y是自由变元；y的辖域是R(x,y)，这里的x是自由变元，y是约束变元。 2.2 谓词 公式

32 自由变元与约束变元 从上面的例子中可以看出，一个个体变元在谓词公式中既可以自由出现，又可以约束出现。但是，在一个公式里每个变元最好以一种形式出现。这就需要对谓词公式进行改名和代入。 所谓改名就是把一变元改为另一变元，并要求改名后的式子与原式同真假。 所谓代入就是把一变元代以公式(公式的值的变域应与变元的变域相同)，并要求代入后的公式为原式的特例。 2.2 谓词 公式

33 2.2.2 自由变元与约束变元 2.2 谓词 公式 改名的规则如下： (1)改名只对约束变元进行，不对自由变元进行；
自由变元与约束变元 改名的规则如下： (1)改名只对约束变元进行，不对自由变元进行； (2)改名必须处处进行，即对某量词约束的变元改名时，必须对原式中该变元的一切受该量词约束的约束出现改名； (3)对受某量词约束的变元改名时新名决不能与该量词的辖域中的其它自由变元同名； (4)改名前与改名后的约束关系保持不变。 总之，正确的改名结果是每个变元只以一种形式出现，最多只受一个量词约束。 2.2 谓词 公式

34 自由变元与约束变元 例2.7 对公式x(P(x,y)∧yQ(y)∧M(x,y))∧(xR(x)Q(x))中的约束变元进行改名。使每个变元在公式中只以一种形式出现（即约束出现或自由出现）。 解 在该公式中，将P(x,y)和M(x,y)中的约束变元x改名为z，R(x)中的x改名为S，Q(y)中的y改名为t，改名后为： z(P(z,y)tQ(t)M(z,y))(SR(S) Q(x))。 2.2 谓词 公式

35 2.2.2 自由变元与约束变元 2.2 谓词 公式 代入的规则如下： (1)代入只对自由变元进行；
自由变元与约束变元 代入的规则如下： (1)代入只对自由变元进行； (2)代入必须处处进行，即对某自由变元施行代入时，必须对该自由变元的一切自由出现施行代入； (3)代入前后的约束关系保持不变； (4)代入前先对原式改名，使原式中所有约束变元名与代入式中所有变元名互不相同，然后施行代入； (5)对命题变元和谓词变元也可施行代入，但必须保持代入前后约束关系不变。 2.2 谓词 公式

36 自由变元与约束变元 例2.8 对公式(yA(x,y)(xB(x,z)C(x,y,z)))xzC (x,y,z)中的自由变元进行代入, 使每个变元在公式中只以一种形式出现（即约束出现或自由出现）。 解 将该公式中的自由变元x用t代入，y用u代入，z用v代入，代入后为： (yA(t,y)(xB(x,v)C(t,u,v))) xzC(x,u,z)。 2.2 谓词 公式

37 2.2.3 谓词公式的分类 定义2.12 设有一谓词公式α，其自由个体变元为x1,x2,…,xh；命题变元为P1,P2,…,Pk，则我们把α表示为： α(x1,x2,…,xh；P1,P2,…,Pk) 如果对个体域指定以D，对x1,x2,…,xh在个体域上分别指派以个体a1,a2,…,ah；对P1,P2,…,Pk分别指派以P1*,P2*,…,Pk*(其中Pi*或为0,或为1，i=1,2,…,k)，则称对α作了一个个体域D上的指派，记为α(a1,a2,…,ah； P1*,P2*,…,Pk*)。如果该值为真，则该指派为α的成真指派；如果该值为假，则该指派称为α的成假指派。 2.2 谓词 公式

38 2.2.3 谓词公式的分类 例2.9 求公式α=x(P(x)Q(x,y))R的成真指派和成假指派，其中P(x)表示“x是偶数”，Q(x,y)表示“y能整除x”,α的个体域D={3,4}，R是命题变元。 解 2.2 谓词 公式 y R x(P(x)Q(x,y))  3 0 3 1 4 0 4 1 1

39 2.2.3 谓词公式的分类 定义2.13 如果公式α对个体域D中任何指派均取得真值，则称α为D中的永真式；如果均取得假值，则称α为D中的永假式；如果至少有一个指派取得真值，则称α为D中的可满足式。 2.2 谓词 公式

40 2.2.3 谓词公式的分类 例2.10 判断下列公式的类型。 （1）xyG(x-y,x+y)(QQ) （2）G(x-y,x+y) （3）xy(G(x,y)G(x,y))Q 其中x,y的个体域为整数集I，Q为命题变元， G(x,y)表示xy。 2.2 谓词 公式

41 2.2.3 谓词公式的分类 解 (1)无论对Q指派何种命题常元，QQ的真值总为1，而在I中对任意的x，总存在y=1使x-1x+1成立，所以xyG(x-y,x+y)在I中总为真，因此xyG(x-,x+y)(QQ)对任意的指派总为真，是永真式。 2.2 谓词 公式

42 2.2.3 谓词公式的分类 （2）因为x-yx+y在I中的真值不确定，当指派x=1,y=1时，02，即x-yx+y取值为真；当指派x=1,y=-1时，20不成立，即x-yx+y取值为假，所以，公式G(x-y,x+y)是可满足式。 （3）无论在个体域I中对x，y指派什么个体常元，G(x,y)G(x,y)总为假，从而xy(G(x,y)G(x,y))Q总为假，所以该公式是永假式。 2.2 谓词 公式

43 2.3.1 等值式的基本概念 定义2.14 设α，β为任意两个谓词公式，它们有共同的个体域D，若在D中αβ为永真式，则称公式α和β在D上等值，记为αβ，称αβ为等值式。 2.3 等值演算

44 2.3.2 常用等值式及等值演算 2.3 等值演算 1. 由命题公式推广的等值式
利用代入定理将命题演算中的等值公式推广而得到谓词演算中的等值公式。 例如，在命题演算中有公式：PQPQ，可推广而得：P(x)Q(x)P(x)Q(x)， xP(x)xQ(x)xP(x)xQ(x)等等。 利用以上方法，可得一类公式。 2.3 等值演算

45 2.3.2 常用等值式及等值演算 2.3 等值演算 2. 关于量词与联结词的一元谓词等值式 1）消去量词等值式
  设个体域为有限集D={a1,a2,…,an}，则有 （1）xA(x)A(a1)A(a2)…A(an) （2）xA(x)A(a1)A(a2)…A(an) 2）量词转换律 （1）xA(x)xA(x) （2）xA(x)xA(x) 2.3 等值演算

46 2.3.2 常用等值式及等值演算 2.3 等值演算 3）量词辖域的收缩与扩张律（下述等值式中，变元x不在B中出现）
（1）x(A(x)B)xA(x)B （2）x(A(x)B)xA(x)B （3）x(A(x)B)xA(x)B （4）x(BA(x))BxA(x) （5）x(A(x)B)xA(x)B （6）x(A(x)B)xA(x)B （7）x(A(x)B)xA(x)B （8）x(BA(x))BxA(x) 2.3 等值演算

47 要特别注意的是，量词分配律中的“”和“”联结词不要记错。 2.3 等值演算
2.3.2 常用等值式及等值演算 4）量词分配律 （1）x(A(x)B(x))xA(x)xB(x) （2）x(A(x)B(x))xA(x)xB(x) 要特别注意的是，量词分配律中的“”和“”联结词不要记错。 2.3 等值演算

48 2.3.2 常用等值式及等值演算 2.3 等值演算 例2.11 证明x(A(x)B(x))xA(x)xB(x)
证明 令个体域为D，设在任一指派下，左式T，则在D中存在一个个体c使得A(c)B(c)T，从而A(c)T或B(c)T，因此有xA(x)T或xB(x)T，所以xA(x)xB(x)T。 反之，设在任一指派下，右式T，则xA(x)T或xB(x)T，即在D中存在两个个体c，d使得A(c)T或B(d)T，从而在D中存在一个个体c或d（不妨设c）使得A(c)B(c)T，所以x(A(x)B(x))T。 由以上两方面知等值式成立。 2.3 等值演算

49 2.3.2 常用等值式及等值演算 思考 判断以下两个式子是否成立？ 2.3 等值演算
思考 判断以下两个式子是否成立？ (1)xA(x)∧xB(x)x(A(x)∧B(x)) (2)xA(x)∨xB(x)x(A(x)∨B(x)) 2.3 等值演算

50 2.3.2 常用等值式及等值演算 2.3 等值演算 3. 关于二元谓词的等值式
在上一节我们曾指出，量词出现的次序直接关系到命题的意义，但也有例外，相同量词间的次序是可以任意调动的，不同量词间的次序则不能随意调动。因此有下面两个等值式成立。 （1）xy(A(x,y))yx(A(x,y)) （2）xy(A(x,y))yx(A(x,y)) 2.3 等值演算

51 2.3.2 常用等值式及等值演算 思考 判断式子xyP(x,y)yxP(x,y)是否成立？ 2.3 等值演算

52 2.3.2 常用等值式及等值演算 证明 x(A(x)B(x)) 2.3 等值演算 例2.12 证明下列等值式。
例2.12 证明下列等值式。 （1）x(A(x)→B(x))xA(x)→xB(x) 证明 x(A(x)B(x)) x(A(x)B(x)) xA(x)xB(x) xA(x)xB(x) xA(x)xB(x) 2.3 等值演算

53 2.3.2 常用等值式及等值演算 2.3 等值演算 （2）xy(P(x)→Q(y))xP(x)→yQ(y)

54 2.4.1 前束范式 定义2.16 一个谓词公式，如果量词均在全式的开头，它们的辖域延伸到整个公式的末尾，则称该公式为前束范式，其标准形式为： L1x1L2x2…Lnxnα 其中：Li(i=1,2,…,n)为或，xi为个体变元，α为不含量词的谓词公式。 例如，yuv(A(x,y)B(u,y)→R(u,v))是前束范式。 2.4 范式

55 2.4.1 前束范式 2.4 范式 定理2.3（前束范式存在定理） 任意一个谓词公式都存在着与之等值的前束范式。
定理2.3（前束范式存在定理） 任意一个谓词公式都存在着与之等值的前束范式。 下面给出将谓词公式化为前束范式的步骤： (1)消去联结词→，及多余的量词； (2)将联结词向内深入，使之只作用于原子谓词公式； (3)利用改名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同； (4)利用量词辖域的扩张与收缩律，扩大量词的辖域至整个公式。 2.4 范式

56 2.4.1 前束范式 2.4 范式 例2.16 将公式xy(z(P(x,z)P(y,z))→zQ(x,y,z))化为前束范式。
xy(z(P(x,z)P(y,z))uQ(x,y,u)) （改名） xyzu(P(x,z)P(y,z)Q(x,y,u)) （量词前移） 2.4 范式

57 2.4.1 前束范式 2.4 范式 定义2.17 一个公式α，如果具有形式：
定义2.17 一个公式α，如果具有形式： L1x1L2x2…Lnxn((α11α12…α1l1)(α21α22…α2l2)…(αm1αm2…αmlm)) 则称该式为前束合取范式。 一个公式α，如果具有形式： L1x1L2x2…Lnxn((α11α12…α1l1)(α21α22…α2l2)…(αm1αm2…αmlm)) 则称该式为前束析取范式。 其中：Li(i=1,2,…,n)为或，xi为 个体变元，αij为原子谓词公式或其否定。 2.4 范式

58 2.4.1 前束范式 定理2.4 任意一个谓词公式都存在着与之等值的前束合取（析取）范式。 将一个谓词公式化为前束合取范式或前束析取范式时，只需在前面求前束范式的（1）～（4）四个步骤基础上再增加一个步骤： （5）利用分配律将公式化为前束合取范式或前束析取范式。 2.4 范式

59 例2.14 将公式x(yA(x,y)→xy(B(x,y)y
2.4.1 前束范式 例2.14 将公式x(yA(x,y)→xy(B(x,y)y (A(y,x)→B(x,y))))化为前束合取范式和前束析取范式。 2.4 范式

60 2.4.2 司柯伦范式 前束范式的优点是全部量词集中在公式前面，其缺点是全称量词与存在量词的排列无一定规则，这样当把一个公式化为前束范式时，其表达形式会显现多种情形，不便应用。1920年司柯伦(Skolem)提出对前束范式中量词出现的次序给出规定：每个存在量词均在全称量词之前。按此规定得到的范式形式，称为司柯伦范式。显然，任意一个谓词公式均可化为司柯伦范式。它的优点是：全公式按顺序可分为三部分，公式的所有存在量词、所有全称量词和辖域。这给谓词逻辑的研究提供了一定的方便。 例如，xyz(P(x,y)(Q(y,z)R(x)))是司柯伦范式。 2.4 范式

61 2.5.1 推理定律 2.5 谓词逻辑的推理演算 1. 由命题逻辑推理定律推广而来的谓词逻辑推理定律
利用代入定理将命题逻辑中的推理定律推广而得到谓词逻辑中的推理定律。 如在命题逻辑中有公式： αβα，ααβ， 可推广而得： xA(x)yB(y)xA(x)， xA(x)xA(x)yB(y) 等等。 2.5 谓词逻辑的推理演算

62 2.5.1 推理定律 2.5 谓词逻辑的推理演算 2. 由基本等值式生成的推理定律
2.3节给出的等值式中的每个等值式可生成两个推理定律。例如， xA(x)xA(x)，xA(x)xA(x) 和xA(x)xA(x), xA(x)xA(x) 等等。 2.5 谓词逻辑的推理演算

63 2.5.1 推理定律 2.5 谓词逻辑的推理演算 3. 一些特有的重要推理定律 （1）xA(x)xB(x)x(A(x)B(x))
（2）x(A(x)B(x))xA(x)xB(x) （3）x(A(x)B(x))xA(x)xB(x) （4）x(A(x)B(x))xA(x)xB(x) 等等。

64 2.5.2 推理规则 2.5 谓词逻辑的推理演算 1. 全称量词消去规则（US） （1）xA(x)A(y) 或
（2）xA(x)A(c) 2. 全称量词引入规则（UG） A(y)xA(x) 3. 存在量词消去规则（ES） xA(x)A(c) 4. 存在量词引入规则（EG） A(c)xA(x) 2.5 谓词逻辑的推理演算

65 2.5.3 推理方法 在谓词逻辑中，常用的推理方法有两种：直接证法和间接证法，其内容与命题逻辑中的类似。 1．直接证法 例2.15 证明苏格拉底三段论：“人都是要死的，苏格拉底是人，所以苏格拉底是要死的。” 2.5 谓词逻辑的推理演算

66 2.5.3 推理方法 2.5 谓词逻辑的推理演算 解 个体域取全总个体域，令F(x)：x是人，G(x)：x是要死的，a:苏格拉底，则
前提：x(F(x)G(x)), F(a) 结论：G(a) 推理形式：x(F(x)G(x)), F(a)G(a) (1) x(F(x)G(x)) P (2) F(a)G(a) US,(1) (3) F(a) P (4) G(a) T,I,(2),(3) 2.5 谓词逻辑的推理演算

67 2.5.3 推理方法 2.5 谓词逻辑的推理演算 例2.18 指出下列推导中的错误，并加以改正。 (1) xP(x) P
例2.18 指出下列推导中的错误，并加以改正。 (1) xP(x) P (2) P(c) ES,(1) (3) xQ(x) P (4) Q(c) ES,(2) 解 第二次使用存在量词消去规则时，所指定的特定个体应该是证明序列以前公式中没有出现过的，正确的推理是： (1) xP(x) P (2) P(c) ES,(1) (3) xQ(x) P (4) Q(d) ES,(2) 2.5 谓词逻辑的推理演算

68 2.5.3 推理方法 2.5 谓词逻辑的推理演算 2. 间接证法 间接证法主要有两种，反证法和CP规则。 1）反证法
例2.19 将下列推理符号化并给出形式证明: 晚会上所有人都唱歌或跳舞了，因此或者所有人都唱歌了，或者有些人跳舞了。（个体域为参加晚会的人） 2.5 谓词逻辑的推理演算

69 2.5.3 推理方法 2.5 谓词逻辑的推理演算 解 设P(x)：x唱歌了，Q(x)：x跳舞了，则 前提：x(P(x)Q(x))
结论：xP(x)xQ(x) 推理形式：x(P(x)Q(x))xP(x)xQ(x) (1) (xP(x)xQ(x)) P(附加) (2) xP(x)xQ(x) R,E,(1) (3) xP(x) T,I,(2) (4) P(a) ES,(3) (5) xQ(x) T,I,(2) (6) Q(a) US,(5) (7) x(P(x)Q(x)) P (8) P(a)Q(a) US,(7) (9) Q(a) T,I,(4),(8) (10) Q(a)Q(a) T,I,(6),(9),矛盾 因此，假设不成立，原推理形式正确。 2.5 谓词逻辑的推理演算

70 2.5.3 推理方法 2）CP规则 2.5 谓词逻辑的推理演算 例2.20 将下列推理符号化并给出形式证明:
例2.20 将下列推理符号化并给出形式证明: 每一个大学生不是文科生就是理科生；有的大学生是优等生；小张不是文科生但他是优等生。因此，如果小张是大学生，他就是理科生。 2.5 谓词逻辑的推理演算

71 2.5.3 推理方法 解 个体域取全总个体域，设P(x)：x是大学生，Q(x)：x是文科生，S(x)：x是理科生，T(x)：x是优等生，c：小张，则 前提：x(P(x)(Q(x)S(x)))，x(P(x)T(x))，Q(c)T(c) 结论：P(c)S(c) 推理形式：x(P(x)(Q(x)S(x)))，x(P(x)T(x))，Q(c)T(c)P(c)S(c) (1) x(P(x)(Q(x)S(x))) P (2) P(c)(Q(c)S(c)) US(1) (3) P(c) P(附加) (4) Q(c)S(c) T,I,(2),(3) (5) Q(c)T(c) P (6) Q(c) T,I,(5) (7) S(c) T,I,(4),(6) (8) P(c)S(c) CP 2.5 谓词逻辑的推理演算

72 2.5.3 推理方法 练习 符号化下述命题并推出其结论。 如果一个人怕困难就不会获得成功，每一个人或者是获得成功的或者是失败的，有的人没有失败，所以，存在着不怕困难的人。(个体域是人的集合) 2.5 谓词逻辑的推理演算

73 谓词逻辑与数据子语言 谓词逻辑与逻辑程序设计语言 （见教材，自学） 2.6 谓词逻辑在计算机科学 中的应用

74 知识回顾 1. 基本概念 个体、个体变元、个体常元、个体域、全总个体域、谓词、量词（全称和存在）、谓词公式、自由变元、约束变元、量词的辖域、换名、代入、指派（成真和成假）、永真式、永假式、可满足式、前束（析取或合取）范式 习题课

75 知识回顾 2. 命题公式间的关系 等值、蕴含、等值定律、推理定律 3. 推理理论（规则、方法） 习题课

76 课堂练习题 习题课 1.将下列命题符号化。 （1）有人勇敢，但不是所有的人都勇敢。 （2）没有不犯错误的人。
（3）凡是实数，或者大于零，或者等于零，或者小于零。 （4）每人都有自己喜欢的水果，有人喜欢所有的水果。 （5）一个数是偶数当且仅当它可被2整除。 （6）并不是火车都比汽车跑得快，有的汽车比有的火车跑得快。 习题课

77 课堂练习题 2. 求下列公式的前束析取范式和前束合取范式。 （1）xF(x,y)(xG(x)yF(y,z)) （2） xy(z(P(x,z)∧P(y,z))→ zQ(x,y,z)) 习题课

78 课堂练习题 3. 将下列推理符号化并给出形式证明。 （1）没有不守信用的人是可以信赖的；有些可以信赖的人是受过教育的。因此，有些受过教育的人是守信用的。 习题课

79 课堂练习题 （2）所有的有理数都是实数；所有的无理数也是实数；虚数不是实数。因此，虚数既不是有理数，也不是无理数。 （3）每个旅客或者坐头等舱或者坐二等舱；每个旅客当且仅当他富裕时坐头等舱；有些旅客富裕但并非所有的旅客都富裕。因此，有些旅客坐二等舱。 习题课

80 课外作业 教材P51-53 6，13(1)(3)(5)(7)，15