离散数学(贾振华主编)教学课件 第二章谓词逻辑.ppt

《离散数学(贾振华主编)教学课件 第二章谓词逻辑.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、第二章谓词逻辑本章学习目标命题逻辑中原子命题是最小的单位，不能够再进行分解，这给推理带来了很大局限性，本章引入谓词逻辑。学习关于谓词逻辑的相关概念和定理，解决实际问题。1第二章谓词逻辑2.1谓词逻辑命题的符号化2.2谓词逻辑公式与解释2.3谓词逻辑约束公式的等价与蕴涵2.4前束范式2.5谓词演算的推理理论2第二章谓词逻辑2．谓词：用来刻画个体词的性质或个体词之间关系的词一般来说，“x是A”类型的命题可以用A（x）表达。对于“x大于y”这种两个个体之间关系的命题，可表达为B（x，y），这里B表示“…大于…”谓词。我们把A（x）称为一元谓词，B（x，y）称为二元谓词，M（a，b，

2、c）称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。2.1谓词逻辑命题的符号化1．个体词：个体词是指研究对象中不依赖于人的主观而独立存在的具体的或抽象的客观实体个体常项或个体常元：个体变项或个体变元：个体域或论域：3第二章谓词逻辑2.1谓词逻辑命题的符号化解（1）设谓词G（x）：x是素数，a：4，b：8；（1）中的题符号化为谓词的蕴涵式：G（a）→G（b）由于此蕴涵式的前件为假，所以（1）中的命题为真。（2）设谓词H（x，y）：x小于y，a：2，b：3，c：8，d：7（2）中的命题符号化为谓词的蕴涵式：H（a，b）→H（c，d）由于此蕴涵式的前件为真，后件为假，所以（

3、2）中的命题为假。例2.1将下列命题在谓词逻辑中符号化，并讨论它们的真值：（1）只有4是素数，8才是素数。（2）如果2小于3，则8小于7。4第二章谓词逻辑2.1谓词逻辑命题的符号化解（a）令F（x）：x要死的；G（x）：x天生就近视。（1）在个体域D1中除人外，没有其他的事物，因而（1）可符号化为：xF（x）（2）在个体域D1中有些人是天生就近视，因而（2）可符号化为例2.2在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）所有人都是要死的。（2）有的人天生就近视。其中：（a）个体域D1为人类集合。（b）个体域D2为全总个体域。5第二章谓词逻辑2.1谓词逻辑

4、命题的符号化谓词的蕴涵式：xG（x）（b）在个体域D2中除人外，还有其他的事物，因而在将（1）、（2）符号化时，必须考虑先将人分离出来，令M（x）：x是人。在D2中，（1）、（2）可分别描述如下：（1）对于宇宙间的一切事物，如果事物是人，则他是要死的。（2）在宇宙间存在着天生就近视的人。将（1）、（2）分别符号化为：（1）x（M（x）F（x））（2）x（M（x）G（x））在个体域D1、D2中命题（1）、（2）都是真命题。6第二章谓词逻辑2.1谓词逻辑命题的符号化例2.3在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x，都有x2-5x+6=

5、（x-2）（x-3）（2）存在x，使得x+1=0。其中：（a）个体域D1为自然数集合。（b）个体域D2为实数集合。7第二章谓词逻辑2.1谓词逻辑命题的符号化解（a）令F（x）：x2-5x+6=（x-2）（x-3）；G（x）：x+1=0。（1）可符号化为：xF(x)（2）可符号化为：xG（x）在个体域D1中命题（1）为真命题，命题（2）为假命题。（b）在个体域D2中（1）、（2）符号化分别为（1）xF（x）（2）xG（x）在个体域D2中命题（1）、（2）都是真命题。8第二章谓词逻辑2.1谓词逻辑命题的符号化例2.4将下列命题符号化，并指出真值情况。（1）没有人登上过月球

6、。（2）所有人的头发未必都是黑色的。解个体域为全总个体域，令M（x）：x是人。（1）令F（x）：x登上过月球。命题（1）符号化为：x（M（x）∧F（x））设a是1969年登上月球完成阿波罗计划的一名美国人，则M（a）∧F（a）为真，故命题（1）为假。（2）令H（x）：x的头发是黑色的。命题（2）可符号化为：x（M（x）H（x））我们知道有的人头发是褐色的，所以x（M（x）H（x））为假，故命题（2）为真。9第二章谓词逻辑2.1谓词逻辑命题的符号化例2.5将下列命题符号化。（1）猫比老鼠跑得快。（2）有的猫比所有老鼠跑得快。（3）并不是所有的猫比老鼠跑得快。（4）

7、不存在跑得同样快的两只猫。解设个体域为全总个体域。令C（x）：x是猫；M（y）：y是老鼠；Q（x，y）：x比y跑得快；L（x，y）：x和y跑得同样快。这4个命题分别符号化为：（1）xy（C（x）∧M（y）Q（x，y））；（2）x（C（x）∧y（M（y）Q（x，y）））；（3）xy（C（x）∧M（y）Q（x，y））；（4）xy（C（x）∧C（y）∧L（x，y）））。10第二章谓词逻辑2.2谓词逻辑公式与解释2.2.1谓词逻辑的合式公式定义2.1设P（x1，x2，…，xn）是n元谓