北京航空航天大学离散数学课件2. 第二章 谓词逻辑.pdf

离散数学(1): 数理逻辑 Discrete Mathematics (1): Mathematical Logic 第二章 谓词逻辑 赵永望 zhaoyw@buaa.edu.cn 北京航空航天大学计算机学院 命题逻辑的表达能力 Τ • 自然语言：凡有理数都是实数， 是有理 Τ 数，所以 是实数 • 这个逻辑命题成立，但从命题逻辑分析 – p:凡有理数都是实数 Τ – q: 是有理数 Τ – r: 是实数 – 根据命题逻辑，我们不能得出, ⊨ • 存在问题：自然语言表达的永真命题，表 达为命题逻辑子句不是永真式。命题逻辑 不能表达 “任意”、“存在某个”等含义 《离散数学》课程 北京航空航天大学计算机学院赵永望(zhaoyw@buaa.edu.cn) 2 引入谓词 • 命题逻辑中的简单命题，不再进行内部结 构分析 • 考虑以下两个命题： – (1) 是无理数 – (2) 是无理数 • 命题逻辑将它们作为独立的命题看待 • 实际上，它们有相同的谓词“是无理数”， 只是主词不同 • 谓词P(x)表示x是无理数 《离散数学》课程 北京航空航天大学计算机学院赵永望(zhaoyw@buaa.edu.cn) 3 引入量词 • 量化语句是用任意 、存在等量词约束陈述 句或复合语句。 – 用“所有...”，“存在...”进一步修饰一个陈述句 的主语或宾语。 – 如果每个是 ，并且是 ，那么，是 。 • ∀( → ∨()) • ∃( ∧ ) 《离散数学》课程 北京航空航天大学计算机学院赵永望(zhaoyw@buaa.edu.cn) 4 内容 • 2.1. 谓词和量词 • 2.2. 项和公式 • 2.3. 解释和赋值 • 2.4. 永真式 • 2.5. 等值演算 • 2.6. 逻辑推论 《离散数学》课程 北京航空航天大学计算机学院赵永望(zhaoyw@buaa.edu.cn) 5 主词和谓词 • 是无理数 • 是无理数 • 主词： 和 • 谓词：是无理数，P(x)表示x是无理数 • 上述命题表示为P(a)和P(b)，a和b分别表示 两个主词 《离散数学》课程 北京航空航天大学计算机学院赵永望(zhaoyw@buaa.edu.cn) 6 个体和论域 • 数理逻辑中，一般将主词称为个体，它是 一个命题里表示思维对象的词 • 例如 和 是研究的个体 • 研究个体时，一定有一个讨论的范围，这 个范围是一个集合，称为论域 – 例如所有正整数的集合 – 所有人的集合、这个教室里在座学生的集合 《离散数学》课程 北京航空航天大学计算机学院赵永望(zhaoyw@buaa.edu.cn) 7 谓词 • 一元谓词 – P(x), Q(x), …