哈尔滨理工大学：《离散数学 Discrete Mathematics》课程教学资源（PPT课件讲稿）05 一阶逻辑等值演算与推理

哈尔滨理工大学呻斛生課程 离影数 第5章一阶逻缉等值演算与推理 O计算机系

第5章 一阶逻辑等值演算与推理 离 散 数 学 哈尔滨理工大学本科生课程 计算机系

本章说可 口本章的主要内容 一阶逻辑等值式与基本等值式 置换规则、换名规则、代替规则 前束范式 一阶逻辑推理理论 口本章与其他各章的关系 本章先行基础是前四章 本章是集合论各章的先行基础

本章说明 ❑ 本章的主要内容 –一阶逻辑等值式与基本等值式 –置换规则、换名规则、代替规则 –前束范式 –一阶逻辑推理理论 ❑ 本章与其他各章的关系 –本章先行基础是前四章 –本章是集合论各章的先行基础

本章主要内容 5.1—阶逻辑等值式与置换规则 5.2一阶逻辑前束范式 5.3一阶逻辑的推理理论

本章主要内容 5.1 一阶逻辑等值式与置换规则 5.2 一阶逻辑前束范式 5.3 一阶逻辑的推理理论

5,1一阶逻辑等值式与置换规则 口在一阶逻辑中,有些命题可以有不同的符号化形式。 口例如:没有不犯错误的人 令M(x):x是人。F(x):x犯错误。 则将上述命题的符号化有以下两种正确形式: (1)-彐x(M(x)∧-F(x)) (2)Vx(M(x)→F(x)) 游》口我们称()和(2)是誊值的

5.1 一阶逻辑等值式与置换规则 ❑ 在一阶逻辑中，有些命题可以有不同的符号化形式。 ❑ 例如：没有不犯错误的人 令 M(x):x是人。 F(x):x犯错误。 则将上述命题的符号化有以下两种正确形式： (1) ┐x(M(x)∧┐F(x)) (2) x(M(x)→F(x)) ❑我们称(1)和(2)是等值的。 说 明

等值式的定义 定义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是否为永真式。 口调词逻辑中关于联结词的等值式与命题逻 辑中相关值式类似

等值式的定义 定义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是否为永真式。 ❑ 谓词逻辑中关于联结词的等值式与命题逻 辑中相关等值式类似。 说 明

阶遇辑中的一些基本而重要等值式 口代换实例 口消去量词等值式 口量词否定等值式 口量词辖域收缩与扩张等值式 口量词分配等值式

一阶逻辑中的一些基本而重要等值式 ❑ 代换实例 ❑ 消去量词等值式 ❑ 量词否定等值式 ❑ 量词辖域收缩与扩张等值式 ❑ 量词分配等值式

代换变例 口由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永 真式,因而第二章的16组等值式模式给出的代换实例都是 阶逻辑的等值式的模式。 口例如: (1)VxF(x)分11VxF(x) (双重否定律) (2)F(x)→G(y)分1F(x)∨G(y)(蕴涵等值式) (3)∨x(F(x)→G(y))→彐zH(z) 台→-Vx(F(x)→G(y))∨彐zH(z) (蕴涵等值式)

代换实例 ❑ 由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永 真式，因而第二章的16组等值式模式给出的代换实例都是 一阶逻辑的等值式的模式。 ❑ 例如： (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) （蕴涵等值式）

消去量词等值式 设个体域为有限集D={a1,a2,…,an},则有 (1)VxA(x)分A(a1)∧A(a2)∧…AAan) (5.1) (2)彐xA(x)分A(a1)∨A(a2)V…VAa

消去量词等值式 设个体域为有限集D={a1,a2,…,an},则有 （1）xA(x)  A(a1 )∧A(a2 )∧…∧A(an ) （2）xA(x)  A(a1 )∨A(a2 )∨…∨A(an ) （5.1）

量词否定等值式 设A(x)是任意的含自由出现个体变项x的公式,则 (1)-VxA(x)分彐x1A(x) (5.2) (2)3xA(x)分Vx1A(x) 说明》口“并不是所有的x都有性质A”与“夺在x没有性 质A”是一回事。 口”不存在有性质A的x”与”所有X都没有性质 A”是一回事

量词否定等值式 设A(x)是任意的含自由出现个体变项x的公式，则 （1）┐xA(x)  x┐A(x) （2）┐xA(x)  x┐A(x) 说明 ❑ “并不是所有的x都有性质A”与“存在x没有性 质A”是一回事。 ❑ ”不存在有性质A的x”与”所有X都没有性质 A”是一回事。 （5.2）

量词转城收缩与扩张等值式 设A(x)是任意的含自由出现个体变项x的公式,B中不含x 的出现,则 (1)Vx(A(x)∨B)◇VxA(x)VB Vx(A(x)AB)分VxA(x)∧B (5.3) Vx(A(x)→B)分彐xA(x)→B Vx(B→A(x))分B→VxA(x) (2)彐x(A(x)∨VB)分彐xA(x)VB 彐x(A(x)∧B)兮彐xA(x)∧B (5.4) 彐x(A(x)→B)xA(x)→B 彐X(B→A(x)B→彐xA(x)

量词辖域收缩与扩张等值式 设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）