文档介绍：离散数学
DISCRETE MATHEMATICS
教师:石兵
Email:******@.
二零一三
重点掌握
谓词的合适公式
上次课重点:
本次课重点
公式的等价
公式的范式表达
公式的蕴涵
第三节谓词WFF的等价
一、定义:设A和B是论域上的两个
WFF,如果对论域上的任何解释, A
和 B都取相同的值, 就说A和B
在论域上是等价的。
如果论域是全总个体域,就说A和
B是等价的。
A和B等价记为A B。
二、定理: A B当且仅当A B
是永真式。
证明要点:同命题公式等价情形证明相似,
对于任何论域,当A B时,在任何
解释下A和 B取值相同,因而A
B恒取值 1 ,即为永真式。反之也对。
三、基本等价式
命题逻辑中的等价式在谓词逻辑中依然有效。
1、量词的否定
1) ( x) A(x) ( x)[ A(x)]
证明要点:当左端取值 1时,( x) A(x)取值
0,因而存在客体 c使A(c) =0,于是右端必
取值 1。
当左端取值 0时,( x) A(x)取值1,因而
对论域中所有客体 x使A(x) =1,于是右端
必取值 0。
2) ( x) A(x) ( x)[ A(x)]
这个等价式可类似地证明。
可见,对量词的否定包括量词互换和辖
域的否定两个方面。
量词的转换可以推广到含多个量词的谓词公式。
~(x)(y)(z)P(x,y,z)
(x)~(y)(z)P(x,y,z)
(x)(y)~(z)P(x,y,z)
(x)(y)(z)~P(x,y,z)
2、量词辖域的扩充与收缩(一)
设A(x) 和B都是WFF,且B不含变元 x,则
1) ( x) [A(x) B]( x) A(x) B
2) ( x) [A(x) B]( x) A(x) B
3) ( x) [A(x) B]( x) A(x) B
4) ( x) [A(x) B]( x) A(x) B
证明要点:因为 B不含变元 x,不受量词的约
束,其取值独立于指导变元。(举例:所有的同学选离散,学校明年校庆)
3、量词辖域的扩充与收缩(二)
( x) [A(x) B(x)]( x) A(x) ( x) B(x)
证明要点:当左端取值 1时,对论域中任何客体x,A(x)和 B(x)必须取值 1,从而右端取值1。当左端取值 0时,必存在客体 c使A(c) =0或者B(c)=0,于是右端必取值 0。