[工学]05一阶逻辑等值演算与推理.pptVIP

离 散 数 学 第5讲 一阶逻辑等值演算与推理 本章说明 本讲的主要内容 – 一阶逻辑等值式与基本等值式 – 置换规则、换名规则、代替规则 – 前束范式 – 一阶逻辑推理理论 本讲与其他各讲的关系 – 本讲先行基础是前四讲 – 本讲是集合论的先行基础 2010-10-9 2 本讲主要内容 5.1 一阶逻辑等值式与置换规则 5.2 一阶逻辑前束范式 5.3 一阶逻辑的推理理论 2010-10-9 3 5.1 一阶逻辑等值式与置换规则 在一阶逻辑中，有些命题可以有不同的符号化形式。 例如：没有不犯错误的人 令 M(x):x是人。 F(x):x犯错误。 则将上述命题的符号化有以下两种正确形式： (1) ┐∃x(M(x)∧┐F(x)) (2) ∀x(M(x)→F(x)) 说明 我们称(1)和(2)是等值的。 2010-10-9 4 说明 5 等值式的定义 定义5.1 设A，B是一阶逻辑中任意两个公式，若 A↔B是永 真式，则称A与B是等值的。 记做A⇔B，称 A⇔B 是等值式。 例如： ¬∃x(F(x) ∧ ¬G(x)) ⇔ ∀x(F(x) → G(x)) 判断公式A与B是否等值，等价于判断公式 A↔B是否为永真式。 谓词逻辑中关于联结词的等值式与命题逻 2010-10-9 辑中相关等值式类似。 一阶逻辑中的一些基本而重要等值式 代换实例 消去量词等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式 2010-10-9 6 代换实例 由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永 真式，因而P9的24个等值式给出的代换实例都是一阶逻辑 的等值式的模式。 例如： (1)∀xF(x) ⇔ ┐┐∀xF(x) (2)F(x)→G(y) ⇔ ┐F(x)∨G(y) (3)∀x(F(x)→G(y))→ ∃zH(z) ⇔ ┐∀x(F(x)→G(y))∨∃zH(z) （双重否定律） （蕴涵等值式） （蕴涵等值式） 2010-10-9 7 消去量词等值式 设个体域为有限集D={a1,a2,…,an},则有 （1）∀xA(x) ⇔ A(a1)∧A(a2)∧…∧A(an) （2）∃xA(x) ⇔ A(a1)∨A(a2)∨…∨A(an) （5.1） 2010-10-9 8 说明 9 量词否定等值式 设A(x)是任意的含自由出现个体变项x的公式，则 （1）┐∀xA(x) ⇔ ∃x┐A(x) （2）┐∃xA(x) ⇔ ∀x┐A(x) （5.2） “并不是所有的x都有性质A”与“存在x没有性 质A”是一回事。 ”不存在有性质A的x”与”所有X都没有性质A” 2010-10-9 是一回事。 量词辖域收缩与扩张等值式 设A(x)是任意的含自由出现个体变项x的公式，B中不含x 的出现，则 （1） ∀x(A(x)∨B) ⇔ ∀xA(x)∨B ∀x(A(x)∧B) ⇔ ∀xA(x)∧B ∀x(A(x)→B) ⇔ ∃xA(x)→B ∀x(B→A(x)) ⇔ B→∀xA(x) （2） ∃x(A(x)∨B) ⇔ ∃xA(x)∨B ∃x(A(x)∧B) ⇔ ∃xA(x)∧B ∃x(A(x)→B) ⇔ ∀xA(x)→B ∃x(B→A(x)) ⇔ B→∃xA(x) （5.3） （5.4） 2010-10-9 10 证明: ∀xA(x)→B ⇔ ∃x(A(x)→B) ∀xA(x)→B ⇔ ┐∀xA(x)∨B ⇔ ∃x┐A(x)∨B ⇔ ∃x(┐A(x)∨B) ⇔ ∃x(A(x)→B) 2010-10-9 11 2010-10-9 12 量词分配等值式 设A(x)，B(x)是任意的含自由出现个体变项x的公式，则 （1）∀x(A(x)∧B(x)) ⇔ ∀xA(x)∧∀xB(x) （5.5） （2）∃x(A(x)∨B(x)) ⇔ ∃xA(x)∨ ∃xB(x) 例如，“联欢会上所有人既唱歌又跳舞”和“联欢会上所有人 唱歌且所有人跳舞” ，这两个语句意义相同。故有(1)式。 由(1)式推导(2)式 ∀x(A(x)∧B(x)) ⇔ ∀xA(x)∧∀xB(x) ∀x(┐A(x)∧┐B(x)) ⇔ ∀x┐A(x)∧∀x┐B(x) ┐∃x(A(x)∨B(x)) ⇔ ┐(∃xA(x)∨∃xB(x)) ∃x(A(x)∨B(x)) ⇔ ∃xA(x)∨ ∃xB(x) 说明 13 一阶逻辑等值演算的三条原则 置换规则：设Φ(A)是含公式A的公式，Φ(B)是用公式B取代 Φ(A)中所有的A之后的公式，若A⇔B，则Φ(A)⇔Φ(B)。 换名规则：设A为一公式，将A中某