《左孝凌离散数学课件2.1谓词概念与表示2.2命题函数与量词》由会员分享，可在线阅读，更多相关《左孝凌离散数学课件2.1谓词概念与表示2.2命题函数与量词（26页珍藏版）》请在金锄头文库上搜索。
1、离散数学(Discrete MathematicsDiscrete Mathematics)第二章第二章 谓词逻辑谓词逻辑2.1谓词的概念与表示(Predicate and its expression)Predicate and its expression)2.2命题函数与量词(Propositional functions & Quantifiers)2.3谓词公式与翻译(Predicate formulae) )2.4变元的约束(Bound of variable) )2.5谓词演算的等价式与蕴含式(Equivalences & implications of predicate ca
2、lculus)2.6前束范式(Prenex normal form) )2.7谓词演算的推理理论(Inference theory of predicate calculus) 著名的苏格拉底三段论著名的苏格拉底三段论所有的人都是要死的P，苏格拉底是人Q， 前提：前提：P Q所以苏格拉底总是要死的R结论：结论：R P Q R或或(P Q) R T命题逻辑命题逻辑R所有的人都是要死的,前提：所有A都要B苏格拉底是人， 前提：C是A所以苏格拉底总是要死的结论：结论：C是要是要B 所有所有A都要都要BC是是A谓词逻辑谓词逻辑RC要要B命题逻辑的局限性命题逻辑的局限性：第二章第二章 谓词逻辑谓词逻辑原
3、因：在在命命题题逻逻辑辑中中，命命题题是是命命题题演演算算的的基基本本单单位位，原原子子命命题题不不再再进进行行分分解解，因因而而无无法法研研究究命命题题的的内内部部结结构构、成成分分及及命命题题之之间间的的内内在在联联系系,因因而而不不能能将将命命题题之之间间的的内内在在联联系系和和数数量量关关系系反反映映出出来来。解决办法：将命题进行分解。 2.1谓词的概念与表示原子命题客体谓词独立存在的具独立存在的具体事物的或抽体事物的或抽象的概念象的概念刻画客体的刻画客体的性质、特征性质、特征或关系或关系谓词逻辑谓词逻辑人总是要人总是要死的死的人人是要死的是要死的客体客体谓词谓词在谓词逻辑中，可将在谓
4、词逻辑中，可将原子命题原子命题划分为划分为客体客体和和谓词谓词两部分两部分例如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等是（个大学生）大于绕着转位于与之间 2.1谓词的概念与表示1.客体2.谓词3.表示方法：谓词用大写字母，客体用小写字母例1、采用谓词表示下列命题1) 地球绕着太阳转； 2）济南位于北京与南京之间；3）张三是大学生，李四是工人解：1）设：L:绕着转，a：地球；b：太阳 即，L(a，b) 2）设：L：位于与之间，a：济南；b：北京；c：南京 即L(a，b，c) 3）设：A：是，a：张三，b：李四，s：大学生，w：工人 即A(a，s)，A(b,w)一、基本概念一
5、、基本概念 2.1谓词的概念与表示4. n元谓词 ：A是谓词，a1，a2，an是客体的名称，则A(a1，a2，an)是n元谓词，这里n个客体需要插入固定的位置 例例2 2、张三高于李四、张三高于李四 解：H：高于，a：张三，b：李四 即H(a,b)注：注：在多元谓词表达式中，客体字母出现的先后次序与事先约在多元谓词表达式中，客体字母出现的先后次序与事先约定有关定有关, ,一般不可以随意交换位置一般不可以随意交换位置，如，如H(a,b) H(b,a)H(a,b) H(b,a)一、基本概念一、基本概念8定义：由一个谓词H和n个客体变元组成的表达式H(x1, x2 , , xn)称为n元简单命题函数
6、.客体变元客体变元：常用小写英文字母常用小写英文字母x,y,z, x,y,z, 表示表示客体常元客体常元：表示具体或特定的客体，常用小写英文字表示具体或特定的客体，常用小写英文字母母a,b,c, a,b,c, 表示表示注注： H(x1, x2 , H(x1, x2 , , xn) , xn) 本身并本身并不是一个命题不是一个命题. .只只有用特定的客体取代客体变元有用特定的客体取代客体变元x,y,zx,y,z后，它们才成为后，它们才成为命题。命题。n元谓词：即有n个客体变元的命题函数.当n=0时,称为0元谓词，0元谓词是一个命题. 2.2命题函数与量词二、命题函数二、命题函数比对：比对：1）命
7、题逻辑中的）命题逻辑中的命题变元命题变元A和和命题常量（命题常量（A：人是会死的人是会死的）2）谓词逻辑）谓词逻辑中中 命题函数命题函数H(x1, x2 , , xn)将客体变元特别制定为客体常元后将客体变元特别制定为客体常元后H（a,b,c，），）9复合命题函数:由一个或几个简单命题函数以及逻辑联结词组合而成的表达式.例例3:3:若若x x的学习好的学习好, ,则则x x的工作好的工作好 设设S(x):xS(x):x学习好；学习好；W(x):xW(x):x工作好，工作好， 则有则有 S(x) S(x) W(x)W(x) 另外另外：S(x)S(x)表示表示“x x学习不是很好学习不是很好”。
8、S(x)W(x)S(x)W(x)表示表示“x x的学习，工作都很好的学习，工作都很好”。例4:将下列命题用谓词符号化.(1) 2(1) 2是素数且是偶数是素数且是偶数. .(2) (2) 如果如果2 2大于大于3,3,则则2 2大于大于4.4.(3) (3) 如果如果张明比李民高张明比李民高, , 李民比赵亮高李民比赵亮高, ,则张明比赵则张明比赵亮高亮高. 2.2命题函数与量词二、命题函数二、命题函数10解:(1) 设F(x): x是素数. G(x): x是偶数. 则命题符号化为： F(2)G(2) (2) 设L(x,y) ：x大于y. 则命题符号化为： L(2,3) L(2,4) (3)
9、设 H(x,y): x比y高. a:张明 b:李民 c：赵亮 则 命 题 符 号 化 为 ： H(a,b)H(b ,c)H(a,c) 另另：H(a,b)表示“张明不比李民长得高”。 2.2命题函数与量词11个体域：在命题函数中，客体变元的论述范围称作个体域。全总个体域:把各种个体域综合在一起作为论述范围的域（所有个体域的并）称为全总个体域。说明说明： 1) 1)命题函数不是一个命题，只有其中的个体命题函数不是一个命题，只有其中的个体变元用特定个体或个体常元替代时，才能成为一个变元用特定个体或个体常元替代时，才能成为一个命题。命题。 2)2)但是但是客体变元在哪些范围内取特定的值，客体变元在哪些
10、范围内取特定的值，对命题函数是否成为命题及命题的真值极有影响对命题函数是否成为命题及命题的真值极有影响。 2.2命题函数与量词二、命题函数二、命题函数P57-P57-例例4 R(x)4 R(x)表示表示“x x是个大学生是个大学生”如果如果x x的讨论范围为的讨论范围为某大学里班级的学生某大学里班级的学生，则，则R(x)R(x)是永真是永真式。式。如果如果x x的讨论范围为的讨论范围为某中学里班级的学生某中学里班级的学生，则，则R(x)R(x)是永假是永假式。式。如果如果x x的讨论范围为的讨论范围为一个剧场中的观众一个剧场中的观众，观众中有大学生，观众中有大学生也有非大学生，那么，对某些观众
11、，也有非大学生，那么，对某些观众，R(x)R(x)为真，对另一些为真，对另一些观众，观众，R(x)R(x)为假。为假。若若x x，y y，z z 地面上的房子，且地面上的房子，且P(x,y)P(x,y)：x x距离距离y 10y 10米，米，则这个式子表示则这个式子表示“x x距离距离y10y10米且米且y y距离距离z10z10米则米则x x距离距离z10z10米米”。这个命题的真值将由。这个命题的真值将由x x，y y，z z的具体位置而定，的具体位置而定，它可能它可能为为T T，也可能为，也可能为F F。 xyzxyzP57-P57-例例5 5若若x x，y y，z Rz R（实数），且
12、（实数），且P(x,y)P(x,y)：x x小于小于y y，则这个式子，则这个式子表示表示“若若x x小于小于y y且且y y小于小于z z，则，则x x小于小于z z”。这是一。这是一永真式永真式。 若若 x x，y y，z z 人，且人，且P P(x,y)(x,y)解释为：解释为：x x为为y y的儿子，则这个的儿子，则这个式子表示式子表示“若若x x为为y y的儿子且的儿子且y y是是z z的儿子则的儿子则x x是是z z的儿子的儿子”。这。这是一个是一个永假式永假式。P(x,z)一元谓词一元谓词P P（x x）表示客体的性质表示客体的性质；n n（n n 2 2）元谓）元谓词词表示客体
13、之间的关系表示客体之间的关系。n n元谓词元谓词P P（x1x1，x2x2，xnxn）是）是以客体变元的个体以客体变元的个体域为定义域域为定义域，以以0,1(F,T)0,1(F,T)为值域为值域的的n n元函数元函数。n n元谓词不是命题，只有将其中的客体变元替换为元谓词不是命题，只有将其中的客体变元替换为n n个客体常元才能成为命题。个客体常元才能成为命题。例：例：A(x,y):x A(x,y):x y y当当a=3a=3，b=4b=4时，时，A(aA(a，b)b)：3 3 4 4 为为T T当当a=5a=5，b=1b=1时，时，A(aA(a，b)b)：5 5 1 1 为为F F当当a=2a
14、=2时，时，A(2A(2，y)y)不是命题。不是命题。当当n=0n=0时，称为时，称为0 0元谓词，是命题元谓词，是命题命题函数是否能成为命题及命题的真值与命题函数是否能成为命题及命题的真值与客体变元客体变元的取值范围的取值范围有关。有关。说明说明15量词：全称量词全称量词( )和存在量词和存在量词( )1.全称量词：用来表达“一切”、“所有”、“凡”、“每一个”、“任意”等词，用符号“ ” 表示，表示对个体域里的所有个体()表示个体域里的所有个体具有性质F.符号“”称为存在量词. 2.2命题函数与量词三、量词三、量词16P58-例：在谓词逻辑中将下列命题符号化.（1）凡是人都呼吸。 （2）每
15、个学生都要参加考试。 (3) 任何整数或是正的或是负的。解: (1) 当个体域为人类集合时： 令F(x): x呼吸。则（1）符号化为xF(x) 当个体域为全总个体域时： 令M(x): x是人。则（1）符号化为 x(M(x) F(x). 2.2命题函数与量词17(2) 当个体域为全体学生的集合时： 令P(x): x要参加考试。则（2）符号化为xP(x). 当个体域为全总个体域时： 令S(x): x是学生。则（2）符号化为 x(S(x) P(x). (3) 当个体域为全体整数的集合时： 令P(x): x是正的。N(x): x是负的。则（3）符号化为 x(P(x)N(x) . 当个体域为全总个体域时
16、： 令I(x): x是整数。则（3）符号化为 x(I(x)(P(x)N(x). 2.2命题函数与量词182.存在量词:用来表达“有一个”、“有的”、“存在着”、“至少有一个”、 “存在一些”等词，用符号“” 表示 表示存在个体域里的个体， ()表示存在个体域里的个体具有性质F.符号“”称为存在量词.例4：在谓词逻辑中将下列命题符号化.（1）一些数是有理数。 （2）有些人活百岁以上。 三、量词三、量词 2.2命题函数与量词19解: (1)令Q(x): x是有理数。则（1）符号化为Q(x)。 （2）当个体域为人类集合时： 令G(x): x活百岁以上。则（2）符号化为xG(x)。 当个体域为全总个体
17、域时： 令M(x): x是人。则（2）符号化为 x(M(x) G(x) 2.2命题函数与量词203.特性谓词:限定客体变元变化范围的谓词，称作特性谓词。例：“有些人没有来上课”要求：1）个体域为全总个体域，2）个体域为人解：1）设M(x)：x是人，C(x)：x没来上课则命题符号化为：（x）(M(x) C(x)2)设C(x)：x没来上课则命题符号化为：（x）C(x)这里M(x)称作特性谓词，用来限定客体的取值范围 三、量词三、量词 2.2命题函数与量词21如果没有给出个体域，都应该以全总个体域为个体域。如果没有给出个体域，都应该以全总个体域为个体域。引入特性谓词后，使用全称量词与存在量词符号化的
18、形式是引入特性谓词后，使用全称量词与存在量词符号化的形式是不同的，一般：不同的，一般：全称量词全称量词( ( x)x)：特性谓词作为条件式的前件：特性谓词作为条件式的前件 例：所有的人都是要呼吸的 M(x)：x是人 H(x):x要呼吸 命题符号化为： (x)(M(x)M(x) H(x). 存在量词（存在量词（ x） ：特性谓词作为合取项：特性谓词作为合取项例：有些人没有来上课 M(x)：x是人 C(x):x没来上课命题符号化为： （x）(M(x) C(x)量词使用小结量词使用小结 2.2命题函数与量词22多个量词同时出现时，不能任意颠倒次序多个量词同时出现时，不能任意颠倒次序 例：“对任意的x
19、,存在y, 使得x+y=5”, 个体域为R, 则该命题符号化为: ( x)(x)( y)H(x,y).y)H(x,y).其中H(x,y): x+y=5. 为真而 ( y)(y)( x)H(x,y)x)H(x,y)表示“某个（些）数y与任意其 他数的和为5” 完全不同的命题，真值为假使一个命题函数成为命题，有两种方法：使一个命题函数成为命题，有两种方法：对客体变元进行指派。如：P(x)：x是素数，则P(5)为T,P(4)为F对命题函数进行量化如：P(x)：x是素数，则：（x）P(x)为T, （ x）P(x)为F量词使用小结量词使用小结 2.2命题函数与量词23练习练习 例6：在谓词逻辑中将下列命
20、题符号化.（1）所有的人都长头发。（2）有的人吸烟。（3）没有人登上过木星。（4）清华大学的学生未必都是高素质的。 24解：令M(x): x是人。（特性谓词）（1） 令F(x): x长头发。则符号化为：（x）(M(x) F(x)（2） 令S(x): x吸烟。则符号化为： （x）(M(x)S(x)（3） 令D(x): x登上过木星。则符号化为： （x）(M(x)D(x)（4）令Q(x):x是清华大学的学生。H(x):x是高素质的。则符号化为： （x）(Q(x) H(x)练习练习练习59页（1）题26小结:本节介绍了n元谓词、命题函数、全称量词和存在量词等概念。重点掌握全称量词和存在量词及量化命题的符号化。作业：P60 （2） 2.2命题函数与量词命题函数与量词
