《离散数学讲义(第2章)》由会员分享，可在线阅读，更多相关《离散数学讲义(第2章)（63页珍藏版）》请在金锄头文库上搜索。
1、1,天津财经大学 信息科学与技术系 王宁 ,Discrete Mathematics,离散数学讲义（电子版）,2,第二章 谓词逻辑,3,第二章 谓词逻辑,谓词演算(一阶谓词演算）是命题演算的扩充和发展,其本质同命题演算，是把数学中的逻辑论证加以符号化，可以刻划命题内部的逻辑结构。从而推动了这个数学分支的发展。,苏格拉底（Socrates）三段论：,. 所有的人都是要死的。,. 苏格拉底是人。,. 所以苏格拉底是要死的。,4,本章包括以下内容：,2-1 谓词的概念与表示 2-2 命题函数与量词 2-3 谓词公式与翻译 2-4 变元的约束 2-5 谓词演算的等价式与蕴含式 2-6 前束范式 2-7
2、 谓词演算的推理理论,第二章 谓词逻辑,5,在谓词演算中，将原子命题分解为 谓词 和 客体 两部分。,客体：可以独立存在的东西,它可以是一个具体的事物，也可以是一个抽象的概念。主语一般为客体。,2-1 谓词的概念与表示,例如：,谓词指明客体性质,谓词指明 客体间关系,谓词：用于刻划客体的性质或客体与客体之间的关系。,(a) 他是三好学生。,(b) 7是质数。,(c) 每天早晨做广播操是好习惯。,(d) 5大于3。,(e) 哥白尼指出地球绕着太阳转。,6,记号：,例如：,2-1 谓词的概念与表示（续）,大写字母：表示谓词。 小写字母：表示客体（个体）。,（1）用A表示“是个大学生”，c表示“张三
3、”，d表示“李四”，则：,A(c)：张三是个大学生。 A(d)：李四是个大学生。,（2）用B表示“大于”，e代表“5”，f代表“3”，则： B(e,f)：5大于3。,（3）用L表示“在和之间”，a表示“点a”，b表示“点b”，c表示“点c”，则：L(a,b,c)表示“a在b和c之间”。,7,记号：,一元谓词：A(b)。 二元谓词：B(a，b)。 三元谓词：L(a，b，c)。 n元谓词： A(c1， c2 ， ，cn)。,代表客体名称的字母，它在多元谓词表示式中出现的次序与事先约定有关。,2-1 谓词的概念与表示（续）,8,2-1 谓词的概念与表示（续）,通常，一元谓词表达了客体的“性质”，多元
4、谓词表达了客体之间的“关系”。,定义：单独一个谓词不是完整的命题，把谓词字母后填以客体所得的式子称为谓词填式。,谓词和谓词填式是两个不同的概念。,9,2-2 命题函数与量词,例：,H：“能够到达山顶”， l：“李四”，t：“老虎”，c：“汽车”。 则H(x)当x分别取l，t，c时表示“李四能够到达山顶”， “老虎能够到达山顶”， “汽车能够到达山顶”。,L(x, y)：“x小于y”。 则L(2, 3)表示“2小于3”， L(5, 1)表示“5小于1”。,A(x, y, z)：“x加y等于z”。 则A(3, 2, 5)表示“3加2等于5”， A(1, 2, 4)表示“1加2等于4”。,10,定义
5、：由一个谓词和一些客体变元所组成的表达式称为简单命题函数。,2-2 命题函数与量词（续）,例如：对于谓词P，P(x)是变元x的函数。,N元谓词是有n个客体变元的命题函数，n=0时，称为0元谓词，其本身是一个命题。,定义：由一个或多个简单命题函数以及逻辑联结词组合而成的表达式称为复合命题函数。,11,2-2 命题函数与量词（续）,例1：设S(x)：“x学习很好”，W(x)：“x工作很好”，,例2：H(x, y)：“x比y长得高”，l：“李四”，c：“张三”,则 S(x)：“x学习不是很好”；,S(x) W(x)：“x学习工作都很好”；,则 H(l, c)：“李四不比张三长得高”；, H(l, c
6、) H(c, l)：“李四不比张三长得高且张三不比李四长得高”，即“李四与张三一样高”。,12,2-2 命题函数与量词（续）,注：,例3：Q(x, y)：“x比y重”,当x，y指人或物时，它是一个命题，若x，y为实数时， Q(x, y)不是命题。,（1）命题函数不是命题，只有客体变元取特定名称时才能成为一个命题。,（2）客体变元在哪些范围内取特定的值对是否成为命题及命题的真值有影响。,13,2-2 命题函数与量词（续）,例4：R(x)：“x是大学生”，考虑x的讨论范围：,例5：(P(x, y) P(y, z) P(x, z)。考虑P(x, y)的解释：,（1）某大学里班级中的学生，则R(x)永
7、真。,（2）某中学里班级中的学生，则R(x)永假。,（3）某剧场中的观众，则R(x)对某些观众为真，对某些为假。,（1）“x小于y”，则P(x, y)永真。,（2）“x为y的儿子”，则P(x, y)永假。,（3）“x距离y10米”，则P(x, y)可能为真或假。,14,个体变元：函数P(x)中的x。,2-2 命题函数与量词（续）,说明： 逻辑联结词 的意义与命题演算中的解释相同。,个体域（论域）：个体变元的取值（论述）范围。,全总个体域：各种个体域综合在一起作为论述范围的域。,15,量词：,2-2 命题函数与量词（续）,注意：每个由量词确定的表达式都与个体域有关，因此在讨论带有量词的命题函数时
8、，必须确定其个体域。,全称量词：“”表示“对所有的”，“对每一 个”，“对任意一个”，等等。,存在量词：“”表示“存在一个”，“至少有一 个”，等等。,16,例1：有如下命题：,则上述三个命题可以表述为：,2-2 命题函数与量词（续）,（a）所有人都是要呼吸的。 （b）每个学生都要参加考试。 （c）任何整数或者是正的或者是负的。,设： M(x)：x是人。 P(x)：x是学生。 I(x)：x是整数。 H(x)：x要呼吸。 Q(x)：x要参加考试。 R(x)：x是正数。 N(x)：x是负数。,（a）(x)(M(x)H(x),（b）(x)(P(x)Q(x),（c）(x)(I(x) (R(x) N(x
9、),17,例2：有如下命题： （a）存在一个数是质数。 （b）一些人是聪明的。 （c）有些人早饭吃面包。,则上述三个命题可以表述为：,2-2 命题函数与量词（续）,设： M(x)：x是人。 P(x)：x是质数。 R(x)：x是聪明的。 E(x)：x早饭吃面包。,（a）(x)(P(x),（b）(x)(M(x) R(x),（c）(x)(M(x) E(x),18,合式公式：谓词演算公式的合式公式（wff）（简称谓词公式），可以由下述各条组成：,原子公式：A(x1,x2,xn)，这里x1,x2,xn是个体变元。,2-3 谓词公式与翻译,例如：Q，A(x), A(x, y), A(f(x), y), A
10、(x, y, z), A(a, y)等。,注意：量词后面若有括号不能省略。,基础,归纳,界限,（1）原子谓词公式是合式公式。,（2）若A是合式公式，则A也是合式公式。,（3）若A和B都是合式公式，则(AB)，(AB)，(AB)和(A B)都是合式公式。,（4）若A都是合式公式，x是出现在A中的任何变元，则(x)A和(x)A都是合式公式。,（5）只有经过有限次地应用规则(1)、(2)、(3)、(4)所得到的公式是合式公式。,19,2-3 谓词公式与翻译（续）,例1：并非每个实数都是有理数。(R(x), Q(x),用谓词公式表达下列命题。,例2：没有不犯错误的人。(F(x), M(x),例3：尽管
11、有些人聪明，但未必一切人都聪明。(P(x),M(x),解： (x)(R(x) Q(x),解： (x)(M(x) F(x),且该命题与“任何人都会犯错误”意义相同：,(x)(M(x) F(x),解： (x)(M(x) P(x) (x)(M(x) P(x),20,2-3 谓词公式与翻译（续）,例4：这支大红书柜摆满了那些古书。,解法1：设 F(x, y)：“x摆满了y” R(x)：“x是大红书柜”； Q(y)：“y是古书”,a：这只； b：那些,则 R(a) Q(b) F(a, b),解法2：设 A(x)：“x是书柜”； B(x)：“x是大的” C(x)：“x是红的”； D(y)：“y是古老的”
12、E(y)：“y是书”； F(x, y)：“x摆满了y” a：这只； b：那些,则 A(a) B(a) C(a) D(b) E(b) F(a, b),解法3：设 F(x, y)：“x摆满了y” a：这只大红书柜； b：那些古书,则 F(a, b),21,2-3 谓词公式与翻译（续）,可见，对于命题翻译成谓词演算公式，机动性很大，由于对个体描述性质刻画深度不同，就可翻译成不同形式的谓词公式。,例5：数学分析中极限的定义：任给0，存在0，使得当0|x-a|时有|f(x)-b|，则称b是f(x)在x a时的极限，记为f(x) b（当x a）或 。,解：下面用谓词公式表示以上定义：,设 P(x, y)：
13、“x大于y”， Q(x,y)：“x小于y”， 则以上定义的谓词公式表示如下：,()()(x) ( (P(, 0) P(, 0) Q(|x-a|, ) P(|x-a|,0) Q(|f(x)-b|, ) ),22,几个名词：,2-4 变元的约束,（1）指导变元（作用变元）：给定为一谓词公式，其中有一部分公式形如(x)P(x)或(x)P(x)，则，后面所跟的x叫做量词的指导变元（或作用变元）。,（2）作用域（辖域）：P(x),（3）约束出现：在作用域中x的一切出现,（4）约束变元：在作用域中出现的x,（5）自由变元：在谓词公式中除去约束变元以外所出现的变元。,23,例1：说明以下各公式的作用域与变元
14、约束的情况。,指导变元,作用域,2-4 变元的约束（续）,(x)(P(x)Q(y),(x)的作用域是：P(x)Q(y)，x为约束变元。,b) (x)(P(x)(y) R(x,y),(x)的作用域是：(P(x)(y)(R(x,y)，,(y)的作用域是：R(x,y)。,x,y为约束变元。,24,c) (x)(y)(P(x,y)Q(y,z)(x)P(x,y),2-4 变元的约束（续）,(x)(y)的作用域是：(P(x,y)Q(y,z),x,y为约束变元，z是自由变元。,(x)的作用域是P(x,y),x为约束变元，y是自由变元。,整个公式中x是约束出现，y既是约束出现又是自由出现，z是自由出现。,d)
15、 (x) ( P(x) (x)Q(x,z) (y)R(x,y) ) Q(x,y),(x)的作用域是： P(x) (x)Q(x,z) (y)R(x,y) x,y是约束变元，,但Q(x,z) 中的x受(x)约束而不受(x)约束。Q(x,y)中的x，y是自由变元。,25,2-4 变元的约束（续）,P(x1,x2,xn)是n元谓词，有n个相互独立的自由变元。若对其中k个进行约束，则成为n-k元谓词。,换名：为避免由于变元的约束与自由同时出现引起概念上的混乱，可对约束变元进行换名，使得一个变元在一个公式中只呈一种形式出现，即呈自由出现或呈约束出现。,例如： (x)(P(x, y, z)是二元谓词； (y)(x)(P(x, y, z)是一元谓词。,26,例2：对(x)(P(x)R(x,y) Q(x,y)换名。,2-4 变元的约束（续）,约束变元的换名规则：,（1）对于约束变元可以换名，其更改的变元名称范围是量词中的指导变元，以及该量词作用域中所出现的该变元，在公式的其余部分不变。,（2）换名时一定要改为作用域中没有出现的变元名称。,解：可换名为 (z)(P(z)R(z,y) Q(x,y),但不可换名为 (y)(P(y)R(y,y) Q(x,y) 或 (z)(P(z)R(x,y) Q(x,y),
