离散数学 第2章

1、 Discrete MathematicsLecturer： 王振宏Email: mobile:ffice Address： 北7-1203D第第2 2章章 谓词逻辑谓词逻辑第二章第二章 谓词逻辑谓词逻辑n1 谓词的概念与表示法n2 命题函数与量词n3 谓词公式与翻译n4 变元的约束n5 谓词演算的等价式与蕴含式n6 前束范式n7 谓词演算的推理理论第二章第二章 重点问题重点问题（1）命题与符号之间的相互翻译（谓词逻辑）（2）运用谓词逻辑推理规则进行推理1 谓词的概念与表示法逻辑学中著名的苏格拉底三段论逻辑学中著名的苏格拉底三段论 ：n大前提大前提p： 凡人都是要死的

2、，凡人都是要死的，n小前提小前提q: 苏格拉底是人，苏格拉底是人，n结结 论论r： 所以苏格拉底是要死的所以苏格拉底是要死的在命题逻辑中就无法表示这种推理过程在命题逻辑中就无法表示这种推理过程。命题逻辑命题逻辑命题被当作一个基本的命题被当作一个基本的，不可分割的单位。，不可分割的单位。研究由原子命题和联接词所组成的复合命题。研究由原子命题和联接词所组成的复合命题。无法研究命题的内部结构及命题之间内在的联系。无法研究命题的内部结构及命题之间内在的联系。谓词逻辑谓词逻辑对原子命题的成份、结构和原子命题间的共同特对原子命题的成份、结构和原子命题间的共同特性等作进一步分析。性等作进一步分析。引入了个体

3、词、谓词、量词、谓词公式等概念。引入了个体词、谓词、量词、谓词公式等概念。研究谓词公式间的等价关系和蕴涵关系。研究谓词公式间的等价关系和蕴涵关系。对命题逻辑中的推理规则进行扩充和进行谓词演对命题逻辑中的推理规则进行扩充和进行谓词演算算。在谓词逻辑中，可将原子命题分解为个体词、在谓词逻辑中，可将原子命题分解为个体词、谓词、量词三部分。谓词、量词三部分。例例 苏格拉底苏格拉底三段论三段论 ： 凡人都是要死的，凡人都是要死的， 苏格拉底是人，苏格拉底是人， 所以苏格拉底是要死的。所以苏格拉底是要死的。 1 谓词的概念与表示法可将以上句子分解为：可将以上句子分解为：个体词：个体词：苏格拉底苏格拉底谓词

4、：谓词：X是要死的，是要死的，X是人是人量词：量词：凡（所有的）凡（所有的）一、个体词定义定义 个体个体是指可以独立存在的客体是指可以独立存在的客体1.个体可以是抽象的，也可是具体的。个体通常在个体可以是抽象的，也可是具体的。个体通常在一个命题里表示思维对象。一个命题里表示思维对象。2.将表示具体或特定的客体的个体词称作将表示具体或特定的客体的个体词称作个体常量个体常量，一般用小写英文字母一般用小写英文字母a，b，c表示。表示。3.将表示抽象或泛指的个体词称为将表示抽象或泛指的个体词称为个体变个体变元元，常用，常用x，y，z表示。表示。4.称个体变项的取值范围为称个体变项的取值范围为个体域个体

5、域(或称或称论域论域)。有。有一个特殊的个体域，它是由宇宙间一切事物组成一个特殊的个体域，它是由宇宙间一切事物组成的，称它为的，称它为全总个体域全总个体域。在论述或推理中如没有。在论述或推理中如没有指明所采用的个体域，都是使用指明所采用的个体域，都是使用全总个体域全总个体域。定义定义 用来刻划个体的性质或个体之间关系的词称为用来刻划个体的性质或个体之间关系的词称为谓词。谓词。刻划一个个体性质的词称为刻划一个个体性质的词称为一元谓词一元谓词；刻划；刻划n个个体个个体之间关系的词称为之间关系的词称为n元谓词元谓词。注意：注意：这里的这里的“元元”指的是自由变元指的是自由变元例例 （1）李明是学生；

6、）李明是学生； （2）张亮比陈华高；）张亮比陈华高； （3）陈华坐在张亮与李明之间。）陈华坐在张亮与李明之间。 在这三个命题中，李明、张亮、陈华都是个体；在这三个命题中，李明、张亮、陈华都是个体；“是学生是学生”是一元谓词，是一元谓词， “比比高高”是二元谓词，是二元谓词， “坐坐与与之之间间”是三元谓词。是三元谓词。二、谓词通常用大写字母表示谓词，小写字母表示个体。通常用大写字母表示谓词，小写字母表示个体。1、Q(x): x是学生；是学生；P(x,y): x比比y高；高；R(x,y,z): x坐坐y与与z之间；之间；a:李明；李明； b:张亮；张亮； c:陈华陈华上述上述命题可分别表示为命题

7、可分别表示为 Q(a), P(b,c), R(c,b,a)2、一般地，一个由、一般地，一个由n个个体和个个体和n元谓词所组成的命元谓词所组成的命题可表示为题可表示为F(a1,a2, ,an)，其中，其中F表示表示n元谓词元谓词, a1,a2, ,an 分别表示分别表示n个个体。个个体。 3、注意：、注意：a1,a2, ,an的排列次序是重要的。的排列次序是重要的。n元谓词元谓词的概念的概念元：指自由变元元：指自由变元 n: 指自由变元的个数指自由变元的个数如：如： Q(x)，P(x,y)， R(x,y,z)n元谓词元谓词不是命题！不是命题！谓词谓词填式：填式：n元谓词元谓词中的变元填入具体的客

8、体中的变元填入具体的客体如：如： Q(a)，P(b,c)， R(c,b,a) ， R(c,y,z)其中其中a:李明；李明； b:张亮；张亮； c:陈华陈华谓词谓词填式填式可能是命题，可能是命题， 如：如：Q(a)，P(b,c)，R(c,b,a) 也可能不是命题！也可能不是命题！如：如：R(c,y,z)2 命题函数与量词命题函数与量词1. 命题函数命题函数定义：定义：由一个谓词字母和一个非空的客体变元的集合所组成的表达式，称为简单命题函数简单命题函数。讨论定义：（a）当简单命题函数仅有一个客体变元时，称为一元简单命题函数；（b）若用任何客体去取代客体变元之后，则命题函数就变为命题；（c）命题函数

9、中客体变元的取值范围称为个体域（论述域）。（d）“简单简单”的含义是指不含联结词2 量词量词量词 在命题里表示数量的词。在命题里表示数量的词。对命题对命题 “ 所有的正整数都是素数所有的正整数都是素数 ” 和和“ 有些正整数是素数有些正整数是素数 ”仅用个体词和谓词仅用个体词和谓词是很难表达的。是很难表达的。 n全称量词 “ x”例 所有人都是要死的。解 个体域为全体人的集合。D(x)：x是要死的。 命题可以表示为 x D(x)n存在量词 “ x ” 例 有些有理数是整数。解 个体域为有理数集合。令I(x)：x是整数。命题可以表示为 x I(x)3 命题符号化n在命题符号化时，除特殊说明外，均

10、使用全在命题符号化时，除特殊说明外，均使用全总个体域。而对个体变化的真正取值范围，总个体域。而对个体变化的真正取值范围，用用特性谓词特性谓词加以限制。加以限制。n特性谓词特性谓词 ：把命题的所讨论的个体从全总：把命题的所讨论的个体从全总个体域中剥离出来的谓词。个体域中剥离出来的谓词。特性谓词的使用特性谓词的使用l对全称量词，特性谓词作条件式的前件。对全称量词，特性谓词作条件式的前件。l对存在量词，特性谓词作合取项。对存在量词，特性谓词作合取项。例 (1) 所有的人都是要死的。 (2) 有的人活百岁以上。n当x的个体域E为全体人组成的集合时，符号化上述命题。令D(x)：x是要死的。则(1)可表示

11、为 x D(x)。令G(x)：x活百岁以上。则(2)可表示为 xG(x)。n当取x的个体域为全总个体域时，必须引入一个特性谓词将人从全宇宙的一切事物中分离出来。 令H(x)：x是人。（1） x( H(x)D(x) ) （2） x( H(x)G(x) ) 例 将下列命题符号化，并讨论真值。1.所有的人都长着黑头发。2.有的人登上过月球。3.没有人登上过木星。4.在美国留学的学生未必都是亚洲人。解：1.所有的人都长着黑头发。令 F(x)：x是人。G(x)：x长着黑头发。则命题符号化为：则命题符号化为： x( F(x)G(x) )。2.有的人登上过月球。令 F(x)：x是人。G(x)：x登上过月球。

12、则命题符号化为：则命题符号化为： x( H(x)G(x) ) 。 3.没有人登上过木星。令F(x)：x是人。G(x)：x登上过木星。则命题符号化为：则命题符号化为： x( H(x)G(x) ) 。4.在美国留学的学生未必都是亚洲人。令 F(x)：x在美国留学。G(x)：x是亚洲人。则命题符号化为：则命题符号化为： x( F(x)G(x) ) 。例 将下列命题符号化。1.兔子比乌龟跑得快。2.有的兔子比所有的乌龟跑得快。3.并不是所有的兔子都比乌龟跑得快。4.不存在跑得同样快的两只兔子。1.兔子比乌龟跑得快。令 F(x)：x兔子。G(x)：x是乌龟。H(x,y)：x比y跑的快则命题符号化为：x(

13、 F(x)y(G(y)H(x,y)。 2.有的兔子比所有的乌龟跑得快。令 F(x)：x兔子。G(x)：x是乌龟。H(x,y)：x比y跑的快则命题符号化为：x( F(x)y(G(y)H(x,y)。3.并不是所有的兔子都比乌龟跑得快。令 F(x)：x兔子。G(x)：x是乌龟。H(x,y)：x比y跑的快则命题符号化为：x( F(x)y(G(y)H(x,y)4.不存在跑得同样快的两只兔子。令 F(x)：x兔子。H(x,y)：x与y跑的一样快则命题符号化为：x( F(x)y(F(x)H(x,y)练习题P59 （1）P60 （2）3谓词公式与翻译谓词公式与翻译1.谓词公式 原子谓词公式：不出现命题联结词和

14、量词的谓词命名式称为原子谓词公式原子谓词公式，并用P(x1xn)来表示。P称为n元谓词， x1xn称为客体变元）。 当n=0时称为零元谓词公式零元谓词公式。定义：（谓词公式的归纳法定义谓词公式的归纳法定义） 原子谓词公式是谓词公式； 若A是谓词公式，则A也是谓词公式； 若A, B都是谓词公式，则(AB),(AB),(AB),(AB)都是谓词公式； 若A是谓词公式，x是任何变元，则xA, xA也都是谓词公式； 只有按-所求得的那些公式才是谓词公式谓词公式（谓词公式又简称“公式”）。3谓词公式与翻译谓词公式与翻译例1：任何整数或是正的，或是负的任何整数或是正的，或是负的。解：设：I(x): x是整

15、数； R1(x)：x是正数；R2(x)：x是负数。此句可写成： x(I(x)(R1(x) R2(x) )。例2：试将苏格拉底论证符号化：“所有的人总是要死的。所有的人总是要死的。因为苏格拉底是人，所以苏格拉底是要死的因为苏格拉底是人，所以苏格拉底是要死的。”解：设M(x)：x是人；D(x)：x是要死的； M(s)：苏格拉底是人；D(s)：苏格拉底是要死的。 写成符号形式： x(M(x) D(x)， M(s) D(s)2.由于对个体描述性质的刻划深度不同，可翻译成不同形式的谓词公式。练习题P63 （5）P63 （6）例题P61 例例3、44变元的约束变元的约束1.辖域：紧接在量词后面括号内的谓词

16、公式。 例： xP(x) , x(P(x) Q(x) 。 若量词后括号内为原子谓词公式，则括号可以省去。2.自由变元与约束变元约束变元约束变元：在量词的辖域内，且与量词下标量词下标相同的变元。 自由变元自由变元：当且仅当不受量词的约束。 例： xP(x,y) , x(P(x) yP(x,y) 。例 指出下列各公式的量词下标量词下标、辖域、约束变辖域、约束变元与自由变元元与自由变元。(1) x(P(x,y)Q(x,z)R(x) (2) x(P(x)xQ(x,z)yR(x,y)Q(x,y) 在一个公式中，一个变元是约束的，如果它至少有一次出现时约束的；一个变元是自由的，如果它至少有一次出现是自由的

17、。4变元的约束变元的约束3.约束变元的换名规则（a）在换名中要把公式中所有相同的约束变元全部同时改掉；（b）换名时所用的变元符号在量词辖域内未出现的。换名的目的在于消除歧义，任何谓词公式对约束变元可以换名的目的在于消除歧义，任何谓词公式对约束变元可以换名。换名。 我们认为xP(x,y)和zP(z,y)是一等价的谓词公式，但是需注意，不能用同一变元去表示同一谓词公式中的二个变不能用同一变元去表示同一谓词公式中的二个变元元。例： yP(y,y)是不正确的。例： xP(x) yR(x,y)可改写成xP(x) zR(x,z) ，但不能改成不能改成xP(x) xR(x,x) ， xR(x,x)中前面的x

18、原为自由变元，现在变为约束变元了。4 代入规则：代入规则：对公式中的自由变元的更改叫做代入代入。 (a)对公式中出现该自由变元的每一处进行代入(b)用以代入的变元与原公式中所有变元的名称不能相同。练习题P66（4）a） P66（5）a）4变元的约束变元的约束5.区别是命题还是命题函数的方法区别是命题还是命题函数的方法（a）若在谓词公式中出现有自由变元，则该公式为命题函数；（b）若在谓词公式中的变元均为约束出现，则该公式为命题。例： xP(x,y,z)是二元谓词， yxP(x,y,z)是一元谓词，而谓词公式中如果没有自由变元出现，则该公式是一个命题。4变元的约束变元的约束举例：例1：“没有不犯错

19、的人。”解：设F(x)为“x犯错误”，M(x)为“x是人”（特性谓词）。可把此命题写成： x(M(x) F(x) x(M(x)F(x)（命题）（命题）例2：“x是y的外祖父” “x是z的父亲且z是y的母亲”设P(z)：z是人；F(x,z)：x是z的父亲；M(z,y)：z是y的母亲则可写成：z(P(z) F(x,z) M(z,y) 。（含有自由变元，故为命题函数）（含有自由变元，故为命题函数）6 . 个体域不同，则表示同一命题的值不同。Q(x): x3 ,则可写出： xP(x)P(0) P(1) P(i) xP(x) P(0)P(1) P(i) 对于全称量词，其特性谓词以前件的方式加入；对于全称

20、量词，其特性谓词以前件的方式加入；对于存在量词，其特性谓词以与的形式加入。对于存在量词，其特性谓词以与的形式加入。例：设个体域为: 白猫，黄猫，白猫，黄猫， ， ，同时令C(x)：x是猫（特性谓词）；B(x)：x是黑色的； A(x)：x是动物。（）描述命题：“所有的猫都是动物所有的猫都是动物”。 即： x(C(x) A(x)（T）（真命题）写成x(C(x) A(x) （F）则为假命题了。 x(C(x) A(x)TT T TT x(C(x) A(x) TT F FF（）描述命题：“一些猫是黑色的一些猫是黑色的” 。 x(C(x) B(x) FF F F F而 x(C(x) B(x)F F T T

21、T3 .量词否定等价式（量词转换律）：量词否定等价式（量词转换律）： E25(Q3) xP(x) xP(x) E26(Q4) xP(x) xP(x) 下面证明：设个体域为： S=a1,a2,an xP(x) (P(a1) P(a2) P(an) P(a1) P(a2) P(an) xP(x)5谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式4 . 量词辖域的扩张及其收缩律量词辖域的扩张及其收缩律 E27(Q6) xA(x) P x(A(x) P) (Q7) xA(x) P x(A(x) P)E28(Q9) xA(x) P x(A(x) P) (Q8) xA(x) P x(A(x) P) P为不

22、含有变元的任何谓词公式为不含有变元的任何谓词公式 E30 (Q14) xA(x)B x(A(x)B) E31 (Q15) xA(x)B x(A(x)B) E32(Q16) AxB(x) x(AB (x) E33 (Q17) A x B(x) x(AB (x)5谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式5.量词分配律量词分配律E23 (Q11) x (A(x) B(x) xA(x) xB(x) E24(Q10) x(A(x)B(x) xA(x) xB(x)E29(Q18) x (A(x) B(x) xA(x) xB(x)I17(Q13) xA(x) xB(x) x(A(x) B(x) I1

23、8(Q12) x (A(x) B(x) xA(x) xB(x)I19(Q19) xA(x) xB(x) x(A(x) B(x)5谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式6.含有多个量词的永真式：含有多个量词的永真式：约定从左到右读出，同时要注意约定从左到右读出，同时要注意量词出现的次序直接量词出现的次序直接关系到命题的含义：关系到命题的含义：“xy”表示：“无论选定一个什么样的x值总能找到一个y能使x和y”“yx”表示：“只选取一个y值，以致无论怎样选定一个x，能够使y和x”5谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式例：x,y的个体域鞋子，P(x,y):和配成一双鞋子。 xyP

24、(x,y) T yxP(x,y) F量词转换律的推广应用:把深入到谓词公式前面去的方法。 xyzP(x,y,z) x yzP(x,y,z) xyzP(x,y,z) xyzP(x,y,z) 5谓词演算的等价式与蕴含式谓词演算的等价式与蕴含式6 前束范式前束范式定义：定义：一个公式，如果量词均非否定地在全式的开头，它们的作用域延伸到整个公式的末尾，则称此公式叫前束范式前束范式。例： xyz( Q(x,y) R(z) (前束范式) 定理：定理： 任何一个谓词公式均和一个前束范式等价任何一个谓词公式均和一个前束范式等价。证明：利用量词转换把深入到原子谓词公式利用约束变元的换名规则，利用量词辖域的扩张收

25、缩律,把量词移到全式的最前面，这样一定可得到等价的前束范式。6 前束范式前束范式例：例： xP(x) R(x) yP(y) R(x) y(P(y) R(x) 例：把例：把 xP(x) xQ(x) 变成前束范式。变成前束范式。 xP(x) xQ(x) xP(x) xQ(x) xP(x) xQ(x) x(P(x) Q(x) 7 谓词演算的推理理论谓词演算的推理理论1 四个推理规则（1）全称指定规则（全称指定规则（US规则）规则）。如果对个体域中所有客体x, A(x)成立，则对个体域中某个任意客体c， A(c) 成立。该规则表示成： xA(x) A(c) (x,c个体域) （2）全称推广规则（全称推

26、广规则（UG规则）规则） 如果能够证明对个体域中每一个客体c，命题A(c) 都成立，则可得到结论xA(x) 成立。该规则表示成： A(c) xA(x) 7 谓词演算的推理理论谓词演算的推理理论（3）存在指定规则（存在指定规则（ES规则）规则）如果对于个体域中某些客体A(x)成立，则必有某个特定的客体c，使A(c)成立。该规则表示成： xA(x) A(c) 例：x的个体域为I=整数，P(x):x是偶数，Q(x): x是奇数。 xP(x) xQ(x) T 但P(c) Q(c) F（4）存在推广规则（存在推广规则（EG规则）规则）如果对个体域中某个特定客体c，有A(c) 成立，则在个体域中，必存在x

27、，使A(x)成立。该规则表示成： A(c) xA(x) 符号记忆方法:nUuniversal nSspecify nEexistence nGgeneralize 7 谓词演算的推理理论谓词演算的推理理论2 推论规则及使用说明推论规则及使用说明（1）命题逻辑中的P,T,CP规则和间接证明法，都可以引用到谓词逻辑的推论规则中来。（2）不过要注意对量词做适当处理，其方法是：用US,ES在推导中去掉量词，用UG,EG使结论量化。7谓词演算的推理理论谓词演算的推理理论规则使用说明：（1）在使用在使用ES,USES,US时一定要是前束范式时一定要是前束范式（2）推导中连续使用推导中连续使用USUS规则可

28、用相同变元规则可用相同变元 xP(x) P(c), xQ(x) Q(c), （3）推导中既推导中既ESES用，又用用，又用USUS， 则必须先用则必须先用ES ES ，后用后用USUS方可取相同变元，反之不行。方可取相同变元，反之不行。 xP(x) P(c) xQ(x) Q(c)（举例）（4）推导中连续使用推导中连续使用ESES规则时，使用一次更改规则时，使用一次更改一个变元。一个变元。7谓词演算的推理理论谓词演算的推理理论例：证明苏格拉底论证x(M(x)D(x)M(s) D(s)证：(1) M(s) P (2) x(M(x)D(x) P (3) M(s)D(s) US(2) (4) D(s) T(1)(3)I7谓词演算的推理理论谓词演算的推理理论例：证明： x(H(x)M(x)