天津理工大学：《离散数学》课程教学资源（PPT课件）第二章 谓词逻辑 Predicate Logic 2.5 谓词演算的等价式与蕴含式（2/2）、2. 6 前束范式（Prenex normal form）

第二章谓词逻辑（PredicateLogic）谓词演算的等价式与蕴含式■定义2.10:给定任何两个谓词公式A、B设它们有共同的个体域E，若对A和B的任一组变元进行赋值，所得命题的真值相同，则称谓词公式A和B在E上等价并记为A台B■定义 若AB为逻辑有效式，则称A与B是等值的，记作A>B，并称A>B为等值式2026/3/151计算机科学与工程系

2026/3/15 计算机科学与工程系 1 第二章 谓词逻辑（Predicate Logic） 谓词演算的等价式与蕴含式 ◼ 定义2.10:给定任何两个谓词公式A、 B设它 们有共同的个体域E，若对A和B的任一组变 元进行赋值，所得命题的真值相同，则称谓 词公式A和B在E上等价,并记为A  B ◼ 定义 若AB为逻辑有效式，则称A与B是等 值的，记作 AB，并称AB为等值式

等值式与基本等值式基本等值式：命题逻辑中24组基本等值式及其代换实例如，VxF(x)→3yG(y) 台-VxF(x)vyG(y)-(VxF(x)VEyG()-VxF()A-EyG(y)等VxA(x) VxA(x) ^ VxA(x)22026/3/15计算机科学与工程系

2026/3/15 计算机科学与工程系 2 等值式与基本等值式 基本等值式: 命题逻辑中24组基本等值式及其代换实例 如，xF(x)→yG(y)  xF(x)yG(y) (xF(x)yG(y))  xF(x)yG(y) xA(x) xA(x)  xA(x ) 等

等值式与基本等值式消去量词等值式设D={a,a.....an)VxA(x)A(a)A(a,)^...NA(anExA(x)A(a)VA(a,)V...VA(an)2026/3/153计算机科学与工程系

2026/3/15 计算机科学与工程系 3 等值式与基本等值式 消去量词等值式 设D={a1 ,a2 ,.,an } xA(x)A(a1 )A(a2 ).A(an ) xA(x)A(a1 )A(a2 ).A(an )

基本的等值式（续）量词否定等值式设A(x)是含x自由出现的公式-VxA(x) 3x -A(x) 3xA(x)Vx -A(x)2026/3/154计算机科学与工程系

2026/3/15 计算机科学与工程系 4 基本的等值式(续) 量词否定等值式 设A(x)是含x自由出现的公式 xA(x) x A(x)  xA(x)x A(x)

基本等值式（续）量词辖域收缩与扩张等值式设A(x)是含x自由出现的公式，B中不含x的出现关于存在量词的：关于全称量词的：x(A(x)VB)xA(x)VBVx(A(x)vB)VxA(x)vBx(A(x)AB)xA(x)BVx(A(x)B)VxA(x)Bx(A(x)→B)VxA(x)BVx(A(x)-→B)3xA(x)→B3x(BA(x)B-→xA(Vx(B-→A(x))B-→VxA(x)2U20/T厂算机科学与工程系

2026/3/15 计算机科学与工程系 5 基本等值式(续) 量词辖域收缩与扩张等值式 设A(x)是含x自由出现的公式，B中不含x的出现 关于全称量词的： 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) 关于存在量词的: 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)

基本的等值式（续）量词分配等值式Vx(A(x)B(x)VxA(x)AVxB()3x(A(x)vB(x)<>xA(x)v日xB(x)注意：V对V无分配律，3对无分配律2026/3/156计算机科学与工程系

2026/3/15 计算机科学与工程系 6 基本的等值式(续) 量词分配等值式 x(A(x)B(x))xA(x)xB(x) x(A(x)B(x))xA(x)xB(x) 注意： 对无分配律，对无分配律

第二章谓词逻辑（PredicateLogic)■量词分配等值式设A(x)、B(x)是任意的含自由出现个体变元x的公式，则(1)Vx(A(x) ^B(x))台V x A(x) ^ Vx B(x)(2)3x(A(x) VB(x)) x A(x) V x B(x)(3)Vx(A(x)VB(x)) ± Vx A(x)V Vx B(x)(4)x(A(x) ^B(x)) ≠ x A(x)^ x B(x)2026/3/157计算机科学与工程系

2026/3/15 计算机科学与工程系 7 第二章 谓词逻辑（Predicate Logic） ◼ 量词分配等值式 设A(x)、B(x)是任意的含自由出现个体变元x的公 式，则 (1) x(A(x)∧B(x)) x A(x) ∧ x B(x) (2)x(A(x)∨B(x)) x A(x) ∨  x B(x) (3)x(A(x)∨B(x)) ≠ x A(x)∨ x B(x) (4)  x(A(x)∧B(x)) ≠ x A(x)∧ x B(x)

基本的等值式（续）例将下面命题用两种形式符号化(1)没有不犯错误的人(2）不是所有的人都爱看电影解(1)令F(x)：x是人，G(x)：x犯错误x(F(x)-G(x)Vx(F(x)→G(x)请给出演算过程，并说明理由。(2)令F(x)：x是人，G(x)：爱看电影-Vx(F(x)→G(x)x(F()A-G(x))给出演算过程，并说明理由

2026/3/15 计算机科学与工程系 8 基本的等值式(续) 例 将下面命题用两种形式符号化 (1) 没有不犯错误的人 (2) 不是所有的人都爱看电影 解 (1) 令F(x)：x是人，G(x)：x犯错误. x(F(x)G(x)) x(F(x)→G(x)) 请给出演算过程，并说明理由. (2) 令F(x)：x是人，G(x)：爱看电影. x(F(x)→G(x)) x(F(x)G(x)) 给出演算过程，并说明理由

前束范式定义设A为一个一阶逻辑公式，若A具有如下形式QxiQ2x2...Qx,B,则称A为前束范式,其中Q;(1Ey(G(y)^H(x,y)3x(F(x)^G(x)) 不是前束范式2026/3/159计算机科学与工程系

2026/3/15 计算机科学与工程系 9 前束范式 例如，xy(F(x)→(G(y)H(x,y))) x(F(x)G(x)) 是前束范式, 而 x(F(x)→y(G(y)H(x,y))) x(F(x)G(x)) 不是前束范式. 定义 设A为一个一阶逻辑公式, 若A具有如下形式 Q1 x1Q2 x2.Qk xkB, 则称A为前束范式, 其中Qi (1ik) 为或，B为不含量词的公式. ◼说明:前束范式的量词均在全式的开头,它们的作用域延伸到整个公 式的末尾

第二章谓词逻辑（PredicateLogic)任何一个谓词公式,均和一个前束范式等7价。注意：公式的前束范式不惟一求公式的前束范式的方法：利用重要等值式、置换规则、换名规则、代替规则进行等值演算102026/3/15计算机科学与工程系

2026/3/15 计算机科学与工程系 10 第二章 谓词逻辑（Predicate Logic） ◼ 任何一个谓词公式,均和一个前束范式等 价。 注意: 公式的前束范式不惟一 求公式的前束范式的方法: 利用重要等值式、 置换规则、换名规则、代替规则进行等值演算