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

离散数学(DiscreteMathematics谓词演算的等价式与蕴含式2026/3/15

2026/3/15 1 离散数学(Discrete Mathematics) 谓词演算的等价式与蕴含式

解释定义解释I由下面4部分组成：(a)非空个体域D(b) D,中一些特定元素 a 等(c) D,上一些特定函数 等JF等(d) D,上一些特定谓词说明：若A中含个体常项a、函数f谓词F.就分别解释成a、f、F2026/3/152计算机科学与工程系

2026/3/15 计算机科学与工程系 2 解释 F a f F a 定义 解释I由下面4部分组成： (a) 非空个体域DI (b) DI中一些特定元素 等 (c) DI上一些特定函数 等 (d) DI上一些特定谓词 等 说明： 若A中含个体常项a、 函数f、 谓词F, 就分别解释 成 、f

代换实例（续）例1给定解释I如下：(a)个体域D-N(b) a = 2(c) f(x, y) =x+y, g(x,y) =xy(d) 谓词 F(x,J):x= J说明下列公式在I下的涵义，并讨论真值(1) VxF(g(x,a),x)假命题Vx(2x=x)(2) VxVy(F(f(x,a),y)-→F(f(y,a),x))假命题VxVy(x+2=y->y+2=x)2026/3/153计算机科学与工程系

2026/3/15 计算机科学与工程系 3 代换实例(续) 例1 给定解释I 如下: (a) 个体域 D=N (b) (c) (d) 谓词 说明下列公式在 I 下的涵义,并讨论真值 (1) xF(g(x,a),x) a = 2 f (x, y) = x + y, g(x, y) = xy F(x, y): x = y x(2x=x) 假命题 (2) xy(F(f(x,a),y)→F(f(y,a),x)) xy(x+2=y→y+2=x) 假命题

例1(续)(3) VxVy3zF(f(x,y),z)真命题VxVyEz (x+y=z)(4) xF(f(x,x),g(x,x)真命题3x(2x=x2)(5) ExVyVzF(f(y,z),x)假命题ExVyVz(+z=x)两点说明：5个小题都是闭式在I下全是命题(3)与(5)说明，量词顺序不能随意改变2026/3/154计算机科学与工程系

2026/3/15 计算机科学与工程系 4 例1(续) (3) xyzF(f(x,y),z) 两点说明: 5个小题都是闭式,在I下全是命题 (3)与(5)说明，量词顺序不能随意改变 (5) xyzF(f(y,z),x) xyz (y+z=x) 假命题 (4) xF(f(x,x),g(x,x)) x(2x=x 2 ) 真命题 xyz (x+y=z) 真命题

解释（续）被解释的公式不一定全部包含解释中的4部分闭式在任何解释下都是命题，注意不是闭式的公式在某些解释下也可能是命题2026/3/155计算机科学与工程系

2026/3/15 计算机科学与工程系 5 解释 (续) 被解释的公式不一定全部包含解释中的4部分. 闭式在任何解释下都是命题， 注意不是闭式的公式在某些解释下也可能是命题

公式的分类永真式（逻辑有效式）：无成假赋值矛盾式（永假式）：无成真赋值可满足式：至少有一个成真赋值几点说明：永真式为可满足式，但反之不真谓词公式的可满足性（永真性，永假性）是不可判定的（没有一个可行的算法能够判断任一公式是否可满足）利用代换实例可判某些公式的类型2026/3/156计算机科学与工程系

2026/3/15 计算机科学与工程系 6 公式的分类 永真式（逻辑有效式）：无成假赋值 矛盾式（永假式）：无成真赋值 可满足式：至少有一个成真赋值 几点说明： 永真式为可满足式，但反之不真 谓词公式的可满足性（永真性,永假性)是不可判定的 （没有一个可行的算法能够判断任一公式是否可满足） 利用代换实例可判某些公式的类型

代换实例定义设A是含命题变项p1,P2，…,Pn的命题公式，Ai,A2…An是n个谓词公式，用A,处处代替A.中的p(1≤n)，所得公式A称为A.的代换实例定理重言式的代换实例都是永真式，矛盾式的代换实例都是矛盾式。例如：F(x)→G(x),VxF(x)→3yG(y)等都是p→>g的代换实例，Vx(F(x)→>G(x))等不是p>g的代换实例.2026/3/157计算机科学与工程系

2026/3/15 计算机科学与工程系 7 代换实例 定义 设A0是含命题变项p1 , p2 , .,pn的命题公式， A1 ,A2 ,.,An是n个谓词公式，用Ai处处代替A0中的pi (1in)，所得公式A称为A0的代换实例. 定理 重言式的代换实例都是永真式，矛盾式的代换实例 都是矛盾式. 例如: F(x)→G(x), xF(x)→yG(y) 等都是p→q的代换实例， x(F(x)→G(x)) 等不是 p→q 的代换实例

代换实例（续）例1(1) VxF(x) → ExF(x)(2) VxF(x) →(Vx3yG(x,y) → VxF(x))2026/3/158计算机科学与工程系

2026/3/15 计算机科学与工程系 8 代换实例(续) 例1 (1) xF(x) → xF(x) (2) xF(x) → (xyG(x,y) → xF(x) )

代换实例（续）例2证明下面公式既不是永真式，也不是矛盾式(1) Vx(F(x) →G(x)(2) 3x(F(x)^G(x)(3) VxVy(F(x)^G(y)-→>H(x,y)不难对每一个公式给出一个成假解释和一个成真解释，从而证明它们既不是永真式，也不是矛盾式.2026/3/159计算机科学与工程系

2026/3/15 计算机科学与工程系 9 代换实例(续) 例2 证明下面公式既不是永真式，也不是矛盾式 (1) x(F(x) →G(x)) (2) x(F(x)G(x)) (3) xy(F(x)G(y)→H(x,y)) 不难对每一个公式给出一个成假解释和一个成真 解释, 从而证明它们既不是永真式，也不是矛盾 式