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

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的所有赋值，谓词公式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。,此命题为永假，真值为0,9.2.2 谓词逻辑的等价式和蕴涵式,定义 给定个体域D及谓词公式,A，B，如果对A，B的所有赋值,谓词公式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 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 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)表示联欢会上有,人唱歌，并且联欢会上有人跳,舞，因而有上述蕴涵式。,