文档介绍：离散数学教学课件
济南大学信息学院
软件教研中心
王新红
ftp://./
上节回顾
在谓词公式中常包含命题变元合客体变元,当客体变元由确定的客体所取代,命题变元由确定的命题所取代,就称作对谓词公式的赋值。
一个谓词公式经过赋值后,就成为具有确定真值(T或F)的命题。
上节回顾
2。谓词公式的等价
定义2- 给定任两个谓词公式wff A和wff B,设它们有共同的个体域E ,若对A和B的任一组变元进行赋值,所得命题的真值相同,则称谓词公式A和B在E上是等价的,记作:A B。
注意:定义1-,它与这个定义的区别在哪?
上节回顾
定义2-
给定任意谓词公式wff A,其个体域为E ,对于A的所有赋值,wff A都为真,则称wff A在E上是有效的或永真的。
定义2-
一个谓词公式wff A,如果对所有赋值下都为假,则称wff A是不可满足的或永假的。
定义2-
一个谓词公式wff A,如果至少在一种赋值下为真,则称wff A是可满足的。
上节回顾
二、谓词演算的等价式与蕴含式
(1)命题公式的推广
(2)量词与联结词ר之间的关系
(3)量词作用域的扩张与收缩
(4)量词与命题联结词之间的一些等价式
(5)量词与命题联结词之间的一些蕴含式
(6)多个量词的使用
上节回顾
(一):命题公式的推广
例如: P Qר P Q
推广为:
(x)P(x) (x) Q(x)(x)P(x) (x)Q(x)
上节回顾
(二):量词与联结词之间的关系
量词转化律
(x) P(x) (x) P(x)
(x) P(x) (x) P(x)
上节回顾
(三) 、量词辖域的收缩与扩张(等价式)
(1) (x)(A(x)∨B)(x) A(x)∨B
(x)(A(x)∧B)(x) A(x)∧B
(x)(A(x)∨B)(x) A(x)∨B
(x)(A(x)∧B)(x) A(x)∧B
上节回顾
(三) 、量词辖域的收缩与扩张(等价式)
(2)当谓词的变元与量词的指导变元不同时,亦有类似于上述的公式。
(x)(A(x)∨ B(y)) (x) A(x)∨ B(y)
(x)(A(x)∧ B(y)) (x) A(x)∧ B(y)
(x)(A(x)∨ B(y)) (x) A(x)∨ B(y)
(x)(A(x)∧ B(y)) (x) A(x)∧ B(y)
上节回顾
(三) 、量词辖域的收缩与扩张(等价式)
(3) 如果量词的作用域中含有条件联结词,且其中一项为命题,则可做相应的扩张或收缩。
(x)(A(x)B) (x)A(x) B
(x)(A(x)B) (x)A(x) B
(x)(B A(x)) B x A(x)
(x)(B A(x)) B (x) A(x)
谓词在前,量词变
谓词在后,量词不变