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

离散数学(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谓词演算的推理理论(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都要B C是A 谓词逻辑 R ?C要B 命题逻辑的局限性： 第二章 谓词逻辑 原因：在命题逻辑中，命题是命题演算的基本单位，原子命题不再进行分解，因而无法研究命题的内部结构、成分及命题之间的内在联系,因而不能将命题之间的内在联系和数量关系反映出来。 解决办法：将命题进行分解。 2.1谓词的概念与表示 原子命题 客体 谓词 独立存在的具体事物的或抽象的概念 刻画客体的性质、特征或关系 谓词逻辑 人总是要死的 人 是要死的 客体 谓词 在谓词逻辑中，可将原子命题划分为客体和谓词两部分 例如，电子计算机、李明、玫瑰花、黑板、实数、中国、思想、唯物主义等 是（个大学生） 大于 ……绕着……转 ……位于……与……之间 2.1谓词的概念与表示 客体 谓词 表示方法：谓词用大写字母，客体用小写字母 例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谓词的概念与表示 n元谓词 ：A是谓词，a1，a2，…an是客体的名称，则A(a1，a2，…an)是n元谓词，这里n个客体需要插入固定的位置 例2、张三高于李四 解：H：高于，a：张三，b：李四 即H(a,b) 注：在多元谓词表达式中，客体字母出现的先后次序与事先约定有关,一般不可以随意交换位置，如H(a,b) ≠H(b,a) 一、基本概念 * 定义：由一个谓词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……，） * 复合命题函数:由一个或几个简单命题函数以及逻辑联结词组合而成的表达式. 例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命题函数与量词 二、命题函数 * 解:(1) 设F(x): x是素数. G(x): x是偶数. 则命题符号化为： F(2)∧G(2) (2) 设L(x,y) ：x大于y. 则命题符号化为： L(2,3) ? L(