谓词逻辑初步 与推理规则
谓词逻辑初步 与推理规则 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) xP(x) 对所有的x, x的平方是正数 否定：存在某个实数x, 其平方不是正数。 xP(x) xP(x) 存在x, 满足 5x=x. 否定：对任意的x, 5xx. 量化表达式的否定式 练习：表达语句xy(xy=1)的否定