离散数学2.3 PPT课件.ppt

一阶逻辑等值式
等值式
基本等值式
量词否定等值式
量词辖域收缩与扩张等值式
量词分配等值式
前束范式
1
等值式与基本等值式
基本等值式:
命题逻辑中16组基本等值式的代换实例
如,xF(x)yG(y) xF(x)yG(y)
(xF(x)yG(y)) xF(x)yG(y) 等
消去量词等值式设D={a1,a2,…,an}
xA(x)A(a1)A(a2)…A(an)
xA(x)A(a1)A(a2)…A(an)
定义若AB为逻辑有效式,则称A与B是等值的,
记作 AB,并称AB为等值式.
2
基本等值式(续)
量词否定等值式
设A(x)是任意的公式
xA(x)x A(x)
xA(x)x A(x)
在D={a,b,c}时
(1)式左边xA(x) (A(a) A(b) A(c))
(1)式右边xA(x) A(a) A(b)A(c)
比较两公式可得(1)
3
基本等值式(续)
举例:A(x):x是男生
xA(x):“每个人均是男生此结论不对。”
此命题等价于“存在一个人,他不是男生”即xA(x)
通俗的说,“存在”的反向是“任意”, “任意”的反向是“存在”。
4
基本等值式(续)
量词辖域收缩与扩张等值式
设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)
5
基本等值式(续)
(1)x(A(x) B) xA(x) B
(2) x(A(x)  B) xA(x)  B
(3) x(A(x) B)x A(x) B
(4) x(A(x) B)x A(x) B
6
基本等值式(续)
说明:,在,逻辑词下,辖域可以扩充到一切不含该指导变元的任意原子公式上,推广的有xA(x) B(y)x (A(x) B(y))两个条件1、B中不含指导变元x
2、只能与,
7
基本等值式(续)
(5)x(A(x)  B) xA(x)  B
(6)x(B A(x) )  BxA(x)
(7)x(A(x)  B) xA(x)  B
(8)x(B A(x) )  BxA(x)
8
基本等值式(续)
说明:在(5)(7)中含有的公式中辖域的扩充与收缩时,和交换了,这是由于两次的辖域不同在用蕴含律时所处的位置不同。
x(A(x)  B)x(A(x) B)xA(x) B
而xA(x)  BxA(x) B
9
基本等值式(续)
举例:A(x):x献出一份爱
B:世界变得更美好
xA(x)  B:只要人人献出一份爱,世界变得更美好
x(A(x)  B):对于每一个人,只要他献出一份爱,世界就变得更美好
两句话意义不相同
10