《9.2 谓词逻辑的等价式和蕴涵式》由会员分享，可在线阅读，更多相关《9.2 谓词逻辑的等价式和蕴涵式（15页珍藏版）》请在金锄头文库上搜索。
1、9.2 谓词逻辑的等价式和蕴涵式 9.2.1 谓词公式的永真、永假与可 满足谓词公式x (P(x)Q(y)R (R为命题变元) 若在某一个体域中， 给个体变元x, y一个取值， 命题变元R一个真值，则可得该 谓词公式的真值，称为一个赋值谓词公式的所有赋值可分为 永真，永假，可满足 永真 定义 给定个体域D及谓词公式A 如果对A的所有赋值谓词公式A都 为真，则称A在D上永真。 例如，若M(x)：x是人D(x)：x是要死的，则x(M(x)D(x) 在全总个体域上永真 xD(x)在人类个体域上永真 P(x,y)P(x,y) 对任何个体域永真永假 定义 给定个体域D及谓词公式A 若对A的所有赋值，谓词
2、公式A都 为假，则称A在D上永假。 可满足定义 给定个体域D及谓词公式A 若对A的所有赋值，谓词公式A有 的为真，有的为假，则称A在D上 可满足。 例 设个体域为整数集， P(x,y)：x+y=1 说明下列命题的真假性。 (1) x y P(x,y)解 (1) x y P(x,y) 表示：对任意的整数x, 存在整数y 使得x+y=1。 此命题为永真，真值为1 (2) x yP(x,y) 解 (2) x yP(x,y)表示存在整数x,使对任意的整数y 都有x+y=1。 此命题为永假，真值为09.2.2 谓词逻辑的等价式和蕴涵式定义 给定个体域D及谓词公式 A，B，如果对A，B的所有赋值 谓词公式
3、A，B的真值都相同，则 称A与B在D上逻辑等价。记作A B 定义 若公式A，B在任何个体域D 上及对其谓词的任何解释AB都 为永真式时，称A逻辑蕴涵B。 记作A B。 注意：在命题逻辑中成立的等价 式与蕴涵式在谓词逻辑中仍成立 E1 E24，I1- I8。谓词逻辑所特有的等价和蕴涵式 (1)量词转化律E25 xA(x) x A(x) E26 xA(x) x A(x)(2)量词辖域的扩张与收缩 当公式B中不含自由变元x时， E27 x A(x)Bx (A(x)B) E28 x A(x)Bx (A(x)B)E29 x A(x)Bx (A(x)B) E30 x A(x)Bx (A(x)B)E31 x
4、 A(x) Bx(A(x)B)E32 x A(x) Bx(A(x)B)E33 Bx A(x) x(BA(x) E34 Bx A(x) x(BA(x)E35 x A(x)x B(x) x(A(x)B (x) (3)量词分配律 E36 x (A(x)B(x) x A(x)x B(x) E37 x (A(x)B(x)xA(x)x B(x) 谓词逻辑中特有的蕴涵式 I9 x A(x)x B(x) x (A(x)B(x)I10 x (A(x)B(x) x A(x)x B(x)例 x A(x)yB(y) x (A(x)yB(y) xy (A(x)B(y) 例 x A(x) Bx A(x) B xA(x)B
5、 x(A(x)B) x(A(x)B)上述等价式与蕴涵式也可以 采用消去量词的方法进行证明，或用下述例子进行说明。个体域为某联欢会上的所有人， A(x)：x在联欢会上唱歌， B(x)：x在联欢会上跳舞， 则x (A(x)B(x)表示联欢会上 的所有人既唱歌又跳舞， x A(x)x B(x) 表示联欢会上 的所有人唱歌，并且联欢会上的 所有人跳舞，因而等价。x (A(x)B(x) 表示联欢会上的 有人唱歌或跳舞， xA(x)x B(x) 表示联欢会上的 有人唱歌或联欢会上的有人跳舞, 因而等价。 x A(x)x B(x) 表示联欢会上 的所有人唱歌，或者联欢会上的 所有人跳舞，因而有上述蕴涵式。x (A(x)B(x) 表示联欢会 上有人既唱歌又跳舞， x A(x)x B(x) 表示联欢会上有 人唱歌，并且联欢会上有人跳 舞，因而有上述蕴涵式。
