离散数学-方世昌主编-第1章---数理逻辑-谓词逻辑.ppt

第一章 数理逻辑 Mathematics Logic 1.6~1.8 谓词逻辑Predicate Logic 问题的提出：(命题逻辑的局限性) 例：苏格拉底论断 前提 “所有的人总是要死的” “苏格拉底是人” 结论 “所以苏格拉底是要死的” 命题逻辑中原子命题不可再分 例 Ｐ1：小张是大学生 Ｐ2：小李是大学生 Q1 ：2大于3 Q2 ：6大于4 命题逻辑无法反映不同原子命题间的内在共性 解决问题的方法 分析原子命题，分离其主语和谓语 考虑一般和个别，全称和存在 1.6 谓词和量词 1.6.1 谓词 谓词的概念和表示 在原子命题中，用来刻划一个个体的性质或个体之间关系的成分称为谓词，刻划一个个体性质的词称为一元谓词；刻划n个个体之间关系的词称为n元谓词 常用大写英文字母表示 个体 能够独立存在的事物 通常用小写英文字母a、b、c、...表示个体常量 用小写英文字母x、y、z...表示任何个体，则称这些字母为个体变元 例 1 (a) 5 是质数 (b) 张明生于北京 (c) 7=3×2 F(x)：x是质数 G(x, y)： x生于y ，a：张明，b：北京 H(x, y, z) ：x=y×z 谓词常元 一个字母代表一特定谓词, 例如F代表“是质数”, 则称此字母为谓词常元 谓词变元 若字母代表任意谓词, 则称此字母为谓词变元 论域 个体域 谓词命名式中个体变元的取值范围 空集不能作为论域 命题函数 谓词命名式不是命题 若谓词是常元 个体词是常元 谓词命名式才成为一个命题 谓词函数 由一个谓词和若干个个体变元组成的命题形式称为简单命题函数，表示为P(x1,x2,…,xn)。由一个或若干个简单命题函数以及逻辑联结词组成的命题形式称为复合命题函数 n=0时 命题变元 例 A(x)：x身体好 B(x)：x学习好 C(x)：x工作好 如果x身体不好，则x的学习与工作都不会好复合命题函数 ?A(x)→(?B(x)∧?C(x)) 1.6.2 量词 例 “所有的正整数都是素数” “有些正整数是素数” 假设 只有两个正整数a和b 个体域为{a,b} P(x)：x是素数 全称量词 记作? 表示“每个”、“任何一个”、“一切”、“所有的”、“凡是”、“任意的”等 ?x读作“任意x”， “所有x”， “对一切x ” 量词后边的个体变元，指明对哪个个体变元量化，称为量词后的指导变元 例 所有人都是要死的 D(x)：x是要死的 个体域：所有人构成的集合 ?x D(x) 存在量词 记作? 表示“有些”、“一些”、“某些”、“至少一个”等 ?x读作“存在x”，“对某些x”或“至少有一x” 指导变元 例 有些有理数是整数 Ｉ(x)：x是整数 个体域：有理数集合 ?xＩ(x) 全总个体域（全总域） 含有量词的命题的真值与论域有关 含有量词的命题的表达式的形式与论域有关 全总个体域 宇宙间所有的个体聚集在一起所构成的集合 约定 除特殊说明外，均使用全总个体域 对个体变化的真正取值范围，用特性谓词加以限制 例 所有的人都是要死的 有的人活百岁以上 D(x)：x是要死的 G(x) ：x活百岁以上 个体域E为全体人组成的集合 ?x D(x) ?x G(x) 全总个体域 引入特性谓词 M(x)：x是人 ?x(M(x)? D(x)) ?x (M(x)∧G(x)) 特性谓词添加规则 对全称量词, 特性谓词作为条件式之前件加入 对存在量词, 特性谓词作为合取项而加入 例 (a) 没有不犯错误的人 F(x)：x犯错误 M(x)：x是人 ? ?x (M(x)∧?F(x)) (b) 凡是实数, 不是大于零就是等于零或小于零 R(x)：x是实数 L(x, y)：x＞y E (x, y) ： x = y S(x, y)：x ＜ y ?x(R(x)? L(x, 0)∨ E (x, 0) ∨ S (x, 0)) 1.6.3 量化断言和命题的关系 假设论域有限, 不妨设论域D={1, 2, 3} ?xP(x)?？ ?xP(x)? P(1)∧ P(2) ∧ P(3) ?xP(x)?？ ?xP(x)? P(1)∨ P(2) ∨P(3) 若论域无限可数，概念可以推广 1.6.4 谓词公式 个体函数（函词） 例 小王比他的父亲高 T(x，y)：x比y高 a：小王 b：小王的父亲 T(a，b) 无法显示个体之间的依赖关系 定义函数 f(x)=x的父亲 T(a， f(a)) 函词与谓词的区别 函词中的个体变元用个体带入后的结果依然是个体 f(a)=小王的父亲 谓词中的个体变元用确定的个体带入后就变成了命题 M(x)：x是人 M(a)：小王是人 函词是论域到论域的映射 f : D→D 谓词是从论域到{T,F}的映射 M :