谓词逻辑的等价式和蕴涵式

《谓词逻辑的等价式和蕴涵式》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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若对

2、A的所有赋值，谓词公式A都为假，则称A在D上永假。可满足定义给定个体域D及谓词公式A若对A的所有赋值，谓词公式A有的为真，有的为假，则称A在D上可满足。例设个体域为整数集，P(x,y)：x+y=1说明下列命题的真假性。(1)xyP(x,y)解(1)xyP(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上及对其谓词的任何解释A→B都为永真式时，称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xA(x)∨Bx(A(x)∨B)E28xA(x)∧Bx(A(x)∧B)E29xA(x)∨Bx(A(x)∨

4、B)E30xA(x)∧Bx(A(x)∧B)E31xA(x)→Bx(A(x)→B)E32xA(x)→Bx(A(x)→B)E33B→xA(x)x(B→A(x))E34B→xA(x)x(B→A(x))E35xA(x)→xB(x)x(A(x)→B(x))(3)量词分配律E36x(A(x)∧B(x))xA(x)∧xB(x)E37x(A(x)∨B(x))xA(x)∨xB(x)谓词逻辑中特有的蕴涵式I9xA(x)∨xB(x)x(A(x)∨B(x))I10x(A(x)∧B(x))xA(x)∧xB

5、(x)例xA(x)∧yB(y)x(A(x)∧yB(y))xy(A(x)∧B(y))例xA(x)→BxA(x)∨BxA(x)→Bx(A(x)→B)x(A(x)→B)上述等价式与蕴涵式也可以采用消去量词的方法进行证明，或用下述例子进行说明。个体域为某联欢会上的所有人，A(x)：x在联欢会上唱歌，B(x)：x在联欢会上跳舞，则x(A(x)∧B(x))表示联欢会上的所有人既唱歌又跳舞，xA(x)∧xB(x)表示联欢会上的所有人唱歌，并且联欢会上的所有人跳舞，因而等价。x(A(x)∨B(x))表示联欢会上的有人唱

6、歌或跳舞，xA(x)∨xB(x)表示联欢会上的有人唱歌或联欢会上的有人跳舞,因而等价。xA(x)∨xB(x)表示联欢会上的所有人唱歌，或者联欢会上的所有人跳舞，因而有上述蕴涵式。x(A(x)∧B(x))表示联欢会上有人既唱歌又跳舞，xA(x)∧xB(x)表示联欢会上有人唱歌，并且联欢会上有人跳舞，因而有上述蕴涵式。