《离散数学》课程教学课件（PPT讲稿）谓词逻辑初步与推理规则

谓词逻辑初步 与推理规则

谓词逻辑初步 与推理规则 1

回顾 问题1:什么是命题逻辑? 与命题真假有关的判断 问题2:如何判断命题表达式的真假? 真值表与常用逻辑等价 问题3:如何判定命题可满足? 范式与主范式

回顾 2 问题1：什么是命题逻辑？ - 与命题真假有关的判断 问题2：如何判断命题表达式的真假？ - 真值表 与 常用逻辑等价 问题3：如何判定命题可满足？ - 范式 与 主范式

本节提要 问题1:什么是(一阶〕谓词逻辑? 问题2:如何进行推理?

本节提要 问题1：什么是(一阶)谓词逻辑？ 问题2：如何进行推理？

引例 口人都要死的,苏格拉底是人,所以苏格拉底要 死的 a father(x, y)A father(y, z)->grandfather(x, z) 口命题逻辑无法处理上述推理!

引例  人都要死的，苏格拉底是人，所以苏格拉底要 死的  father(x, y)  father(y, z) → grandfather(x, z)  命题逻辑无法处理上述推理！

谓词( Predicate) 口如果x是整数,“x大于2”不是命题,它的真值 依赖于x的取值 口可以将“x大于2表示为P(x) 口谓词:P(x)可以视同关于x的一个属性的取值( 个函数) 口P的定义域是整数集,其值域是{TF} 口P(3)是一个取值为T的命题 口“for叫lIx,P(x)”是一个取值为F的命题 口“存在一个x,P(x)”是一个真值为T的命题

谓词（Predicate）  如果 x 是整数，“x 大于2” 不是命题，它的真值 依赖于 x 的取值  可以将“x 大于2”表示为 P(x)。  谓词：P(x)可以视同关于x的一个属性的取值(一 个函数）  P 的定义域是整数集，其值域是 { T, F }  P(3)是一个取值为T 的命题  “for all x, P(x)”是一个取值为 F 的命题  “存在一个x，P(x)”是一个真值为T 的命题

量词( Quantifier) 口若P(x)是谓词,∨xP(x)表示“对所有的x,P(x)y 称为全称量词 口若P(x)是谓词,彐xP(x)表示“存在某个x,P(x)彐 称为存在量词 口例:P(x)表示x>2,VxP(x)为假,彐xP(x)为真 口注1:量词必须指定论域(默认为实数域) 口注2:当论域元素可以一一列出时,量词(谓词公式) 可以转化成命题公式的合取、析取范式 口注3:量词的优先级高于其它逻辑运算符

量词（Quantifier）  若P(x) 是谓词, xP(x)表示 “对所有的x, P(x)”  称为 全称量词  若P(x) 是谓词, xP(x)表示 “存在某个x, P(x)”  称为 存在量词  例：P(x)表示x>2 ，xP(x)为假， xP(x)为真  注1：量词必须指定论域（默认为实数域）  注2：当论域元素可以一一列出时，量词（谓词公式） 可以转化成命题公式的合取、析取范式  注3：量词的优先级高于其它逻辑运算符

量词的论域 口符号化以下语句: 口P(x)表示x2>0,VxP(x)的真值? 口有的政治家诚实 口所有美国人都喜欢汉堡包

量词的论域  符号化以下语句：  P(x)表示x 2>0，xP(x)的真值？  有的政治家诚实  所有美国人都喜欢汉堡包

量词的作用域 口观察量化表达式: a Vx(P(x)Q(x)) n xP(x)AQ(x) aVx(P(x,y)入Q(xy) VxP(x)入VxQ(x) VxP(x)∧yQ(y) 口量化表达式中的变元:绑定、自由、作用域、替换

量词的作用域  观察量化表达式：  x(P(x)Q(x))  xP(x)Q(x)  x(P(x,y)Q(x,y))  xP(x)xQ(x)  xP(x)yQ(y)  量化表达式中的变元：绑定、自由、作用域、替换

量化表达式的逻辑等价 口逻辑表达式的逻辑等价: 都有相同的真值,无论变量设定在哪个论域上, 无论什么谓词代入。 口例 口Vx(P(x)∧Q(x)≡VxP(x)∧VxQ(x) 口3x(P(x)VQ(x))≡彐xP(x)V彐xQ(x)

 逻辑表达式的逻辑等价： 都有相同的真值，无论变量设定在哪个论域上， 无论什么谓词代入。  例：  x(P(x)  Q(x))  xP(x)  xQ(x)  x(P(x)  Q(x))  xP(x)  xQ(x) 量化表达式的逻辑等价

量化表达式的否定式 口VxF(x)≡彐x=F(x 口对所有的x,x的平方是正数 口否定:存在某个实数x,其平方不是正数。 口3xFx=VxP(x 口存在x满足5x=x 口否定:对任意的x,5x≠x 练习:表达语句xyxy=1)的否定

 xP(x)  xP(x)  对所有的x, x的平方是正数  否定：存在某个实数x, 其平方不是正数。  xP(x)  xP(x)  存在x, 满足 5x=x.  否定：对任意的x, 5xx. 量化表达式的否定式 练习：表达语句xy(xy=1)的否定