- 1、下载文档前请自行甄别文档内容的完整性，平台不提供额外的编辑、内容补充、找答案等附加服务。
- 2、"仅部分预览"的文档,不可在线预览部分如存在完整性等问题,可反馈申请退款(可完整预览的文档不适用该条件!)。
- 3、如文档侵犯您的权益，请联系客服反馈,我们会尽快为您处理(人工客服工作时间：9:00-18:30)。
代换实例 消去量词等值式 量词否定等值式 量词辖域收缩与扩张等值式 量词分配等值式
代换实例
由于命题逻辑中的重言式的代换实例都是一阶逻辑中的永 真式，因而第二章的16 16组等值式模式给出的代换实例都是 真式，因而第二章的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))∨∃ ⇔ ┐∀x(F(x)→G(y))∨∃zH(z) （蕴涵等值式） 蕴涵等值式） （双重否定律） 双重否定律） （蕴涵等值式） 蕴涵等值式）
解答 (1)∀xF(x,y,z)→ ∃yG(x,y,z) (1)∀ F(x
tF(t,y,z)→∃ G(x,y ⇔ ∀tF(t,y,z)→∃yG(x,y,z) tF(t,y,z)→∃ ⇔ ∀tF(t,y,z)→∃wG(x,w,z) 或∀xF(x,y,z)→∃yG(x,y,z) xF(x,y,z)→∃ xF(x,t,z)→∃yG(x ⇔ ∀xF(x,t,z)→∃yG(x,y,z) F(x,t,z)→∃ ⇔ ∀xF(x,t,z)→∃yG(w,y,z)
离散数学
第5章 一阶逻辑等值演算与推理
本章说明
本章的主要内容 –一阶逻辑等值式与基本等值式 一阶逻辑等值式与基本等值式 –置换规则、换名规则、代替规则 置换规则、换名规则、 置换规则 –前束范式 前束范式 –一阶逻辑推理理论 一阶逻辑推理理论 本章与其他各章的关系 –本章先行基础是前四章 本章先行基础是前四章 –本章是集合论各章的先行基础 本章是集合论各章的先行基础
说明
如果不用公式(5.3)将量词的辖域缩小， 如果不用公式(5.3)将量词的辖域缩小，演算过程较 (5.3)将量词的辖域缩小 注意，此时∃yG(y)是与 无关的公式B 是与x 长。注意，此时∃yG(y)是与x无关的公式B。
例5.3—消去量词 5.3 消
(3) ∃x∀yF(x,y) ⇔ ∃x(F(x,a)∧F(x,b)∧F(x,c)) (F(a,a)∧F(a,b)∧F(a,c)) ∨(F(b,a)∧F(b,b)∧F(b,c)) ∨(F(c,a)∧F(c,b)∧F(c,c)) 在演算中先消去存在量词也可以，得到结果是等值的。 在演算中先消去存在量词也可以，得到结果是等值的。 ∃x∀yF(x,y) ⇔∀yF(a,y)∨ ∀yF(b,y) ∨ ∀yF(c,y) ⇔ (F(a,a)∧F(a,b)∧F(a,c)) ∨(F(b,a)∧F(b,b)∧F(b,c)) ∨(F(c,a)∧F(c,b)∧F(c,c)) ⇔
→ 例如： ¬∃x(F(x) ¬G(x))⇔ ∀x(F(x) G(x)) 例如： ∧
说 明
判断公式A与B是否等值，等价于判断公式 判断公式A 是否等值， 是否为永真式。 A↔B是否为永真式。 谓词逻辑中关于联结词的等值式与命题逻 辑中相关等值式类似。 辑中相关等值式类似。
一阶逻辑中的一些基本而重要等值式
证明: ∀xA(x)→B ⇔ ∃x(A(x)→B) 证明:
∀xA(x)→B ⇔ ┐∀xA(x)∨B ⇔ ∃x┐A(x)∨B x(┐ ⇔ ∃x(┐A(x)→B) ⇔ ∃x(A(x)→B)
量词分配等值式
设A(x)，B(x)是任意的含自由出现个体变项x的公式，则 A(x)，B(x)是任意的含自由出现个体变项x的公式， 是任意的含自由出现个体变项 xA(x)∧∀ （1）∀x(A(x)∧B(x)) ⇔ ∀xA(x)∧∀xB(x) （2）∃x(A(x)∨B(x)) ⇔ ∃xA(x)∨ ∃xB(x) 例如，“联欢会上所有人既唱歌又跳舞”和“联欢会上所 例如， 联欢会上所有人既唱歌又跳舞” 有人唱歌且所有人跳舞” 这两个语句意义相同。 有人唱歌且所有人跳舞” ，这两个语句意义相同。故有 (1)式 (1)式。 由(1)式推导(2)式 (1)式推导(2)式 式推导(2) xA(x)∧∀ ∀x(A(x)∧B(x)) ⇔ ∀xA(x)∧∀xB(x) A(x)∧∀ ∀x(┐A(x)∧┐B(x)) ⇔ ∀x┐A(x)∧∀x┐B(x) x(┐A(x)∧┐ ┐(∃xA(x)∨∃ ┐∃x(A(x)∨B(x)) ⇔ ┐(∃xA(x)∨∃xB(x)) ∃x(A(x)∨B(x)) ⇔ ∃xA(x)∨ ∃xB(x) （5.5） 5.5）
消去量词等值式
设个体域为有限集D={a 设个体域为有限集D={a1,a2,…,an},则有 ,a },则有 )∧… （1）∀xA(x) ⇔ A(a1)∧A(a2)∧…∧A(an) )∨… （2）∃xA(x) ⇔ A(a1)∨A(a2)∨…∨A(an) （5.1） 5.1）
量词否定等值式
设A(x)是任意的含自由出现个体变项x的公式，则 A(x)是任意的含自由出现个体变项x的公式， 是任意的含自由出现个体变项 （1）┐∀xA(x) ⇔ ∃x┐A(x) （2）┐∃xA(x) ⇔ ∀x┐A(x) （5.2） 5.2）
说明
一阶逻辑中的置换规则与命题逻辑中的置换 规则形式上完全相同，只是在这里A 规则形式上完全相同，只是在这里A，B是一 阶逻辑公式。 阶逻辑公式。
例5.1
将下面公式化成与之等值的公式，使其没有既是约束 例5.1 将下面公式化成与之等值的公式，使其没有既是约束 出现又是自由出现的个体变项。 出现又是自由出现的个体变项。 (1)∀xF(x,y,z)→ (1)∀xF(x,y,z)→∃yG(x,y,z) (2)∀x(F(x,y)→ (2)∀x(F(x,y)→ ∃yG(x,y,z))
说明
“并不是所有的x都有性质A”与“存在x没有性 并不是所有的x都有性质A 与 存在x 并不是所有的 是一回事。 质A”是一回事。 是一回事 不存在有性质A ”不存在有性质A的x”与”所有X都没有性质 与 所有X 是一回事。 A”是一回事。 是一回事
量词辖域收缩与扩张等值式
设A(x)是任意的含自由出现个体变项x的公式，B中不含x A(x)是任意的含自由出现个体变项x的公式， 中不含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 B→∃ ∃x(B→A(x)) ⇔ B→∃xA(x) （5.4） 5.4） （5.3） 5.3）
说明
全称量词“∀”对“∨”无分配律。 全称量词“ 无分配律。 存在量词“ 无分配律。 存在量词“∃”对“∧”无分配律。 B(x)换成没有 出现的B 换成没有x 当B(x)换成没有x出现的B时，则有 ∀x(A(x)∨B) ⇔ ∀xA(x)∨B ∃x(A(x)∧B) ⇔ ∃xA(x)∧B
例5.3—消去量词 5.3 消
设个体域为D {a,b,c}，将下面各公式的量词消去： 例5.3 设个体域为D＝{a,b,c}，将下面各公式的量词消去： (1) ∀x(F(x)→G(x)) (2) ∀x(F(x)∨ ∃yG(y)) (3) ∃x∀yF(x,y)
解答 (1)∀x(F(x)→G(x))
⇔(F(a)→G(a)) ∧ (F(b)→G(b)) ∧ (F(c)→G(c)) (2)∀x(F(x)∨ ∃yG(y)) xF(x)∨∃ ⇔ ∀xF(x)∨∃yG(y) (公式5.3) 公式5 ⇔(F(a)∧F(b)∧F(c))∨(G(a)∨G(b)∨G(c))
(代替规则) 代替规则)
(换名规则) 换名规则)
例5.2
例5.2 证明 xA(x)∨∀ （1） ∀x(A(x)∨B(x)) <≠> ∀xA(x)∨∀xB(x) xA(x)∧∃ （2） ∃x(A(x)∧B(x)) <≠> ∃xA(x)∧∃xB(x) 其中A(x)，B(x)为含x自由出现的公式。 其中A(x)，B(x)为含x自由出现的公式。 A(x) 为含
例5.4
例5.4 给定解释I如下： 给定解释I如下： （a）个体域 D＝{2,3} （b）D中特定元素 a = 2 ， 。 上的特定函数(x) (x)为 （c）D上的特定函数(x)为：f (2) = 3 f (3) = 2 （d）D的特定谓词 ， G (x,y)为：G (2,2) =G (2,3) =G (3,2) = 1 G (3,3) = 0。
一阶逻辑等值演算的三条原则
置换规则： Φ(A)是含公式A的公式，Φ(B)是用公式B 置换规则：设Φ(A)是含公式A的公式，Φ(B)是用公式B取代 是含公式 是用公式 Φ(A)中所有的 之后的公式， 中所有的A Φ(A)⇔Φ(B)。 Φ(A)中所有的A之后的公式，若A⇔B，则Φ(A)⇔Φ(B)。 换名规则： 换名规则：设A为一公式，将A中某量词辖域中某约束变项的 为一公式， 所有出现及相应的指导变元改成该量词辖域中未曾出现过的 某个体变项符号，公式的其余部分不变，设所得公式为A' A'， 某个体变项符号，公式的其余部分不变，设所得公式为A'， A'⇔ 则A'⇔A。 代替规则： 代替规则：设A为一公式，将A中某个自由出现的个体变项的 为一公式， 所有出现用A中未曾出现过的个体变项符号代替， 所有出现用A中未曾出现过的个体变项符号代替，A中其余部 分不变，设所得公式为A' A'， A'⇔ 分不变，设所得公式为A'，则A'⇔A。
证明
只要证明在某个解释下两边的式子不等值。 只要证明在某个解释下两边的式子不等值。 取解释I 个体域为自然数集合N 取解释I：个体域为自然数集合N； (1)取F(x)：x是奇数，代替A(x)； (1)取F(x)： 是奇数，代替A(x)； A(x) G(x)： 是偶数，代替B(x) B(x)。 取G(x)：x是偶数，代替B(x)。 则∀x(F(x)∨G(x))为真命题， x(F(x)∨G(x))为真命题， 为真命题 为假命题。 而∀xF(x)∨∀ xG(x)为假命题。 xF(x)∨∀ xG(x)为假命题 两边不等值。 两边不等值。
