左孝凌离散数学课件2.1谓词概念与表示-2.2命题函数与量词.ppt

离散数学离散数学( (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 calculus) 2.6前束范式(Prenex normal form) ) 2.7谓词演算的推理理论(Inference 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 谓词逻辑 RC要B 命题逻辑的局限性： 第二章第二章 谓词逻辑谓词逻辑 原因：在命题逻辑中，命题是命题演算 的基本单位，原子命题不再进行分解 ，因而无法研究命题的内部结构、成 分及命题之间的内在联系,因而不能将 命题之间的内在联系和数量关系反映 出来。 解决办法：将命题进行分解。 2.1谓词的概念与表示 原子命题客体谓词 独立存在的具 体事物的或抽 象的概念 刻画客体的 性质、特征 或关系 谓词逻辑 人总是要 死的 人是要死的 客体谓词 在谓词逻辑中，可将原子命题划分为客体和谓词两部分 例如，电子计算机、李明、玫瑰 花、黑板、实数、中国、思想、 唯物主义等 是（个大学生） 大于 绕着转 位于与之间 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) 一、基本概念 2.1谓词的概念与表示 4. 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元简单命题函数. 客体变元：常用小写英文字母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 复合命题函数:由一个或几个简单命题函数以 及逻辑联结词组合而成的表达式. 例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) 设 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是个大学生” 如果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。 x yz xyz P57-例5 若x，y，z R（实数），且P(x,y)：x小于y，则这个式子表 示“若x小于y且y小于z，则x小于z”。这是一永真式。 若 x，y，z 人，且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元谓词，是命题 命题函数是否能成为命题及命题的真值与客体变元 的取值范围有关。 说明 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(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.存在量词:用来表达“有一个”、“有的”、“存在着”、“ 至少有一个”、 “存在一些”等词，用符号“” 表示 表示存在个体域里的个体， ()表示存在个体域里的个体具有性质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）个体域为人 解： 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是人 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)为F 量词使用小结 2.2命题函数与量词 23 练习 例6：在谓词逻辑中将下列命题符号化. （1）所有的人都长头发。 （2）有的人吸烟。 （3）没有人登上过木星。 （4）清华大学的学生未必都是高素质的 。 24 解：令 M(x): x是人。（特性谓词） （1） 令F(x): x长头发。则符号化为：