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