离散数学 贾振华 第二章 谓词逻辑

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

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

2、“x大于y”这种两个个体之间关系的命题，可表达为B（x，y），这里B表示“…大于…”谓词。我们把A（x）称为一元谓词，B（x，y）称为二元谓词，M（a，b，c）称为三元谓词，依次类推，通常把二元以上谓词称作多元谓词。2.1.1个体词与谓词1．个体词：个体词是指研究对象中不依赖于人的主观而独立存在的具体的或抽象的客观实体个体常项或个体常元：个体变项或个体变元：个体域或论域：52.1谓词逻辑命题的符号化解（1）设谓词G（x）：x是素数，a：4，b：8；（1）中的题符号化为谓词的蕴涵式：G（a）→G（b）由于此蕴涵式的前件为假，所

3、以（1）中的命题为真。（2）设谓词H（x，y）：x小于y，a：1，b：2，c：5，d：4（2）中的命题符号化为谓词的蕴涵式：H（a，b）→H（c，d）由于此蕴涵式的前件为真，后件为假，所以（2）中的命题为假。例2.1将下列命题在谓词逻辑中符号化，并讨论它们的真值：（1）只有4是素数，8才是素数。（2）如果1小于2，则5小于4。2.1.1个体词与谓词62.1谓词逻辑命题的符号化全称量词对于日常生活和数学中出现的“一切的”、“任意的”、“所有的”、“每一个”、“都”、“凡”等词统称为全称量词，用符号“”表示。并用x，y表示

4、个体域中的所有个体，用（x）F（x），（y）F（y）等表示个体域中的所有个体具有性质F。存在量词对日常生活和数学中常用的“存在”、“存在一个”、“有一个”、“至少有一个”、“有些”、“有的”等词统称为存在量词，用符号“”表示。并用x，y表示个体域中有的个体，用（x）F（x），（y）F（y）等表示个体域中有的个体具有性质F。2.1.2量词72.1谓词逻辑命题的符号化解（a）令F（x）：x要死的；G（x）：x天生就近视。（1）在个体域D1中除人外，没有其他的事物，因而（1）可符号化为：xF（x）（2）在个体域D1

5、中有些人是天生就近视，因而（2）可符号化为例2.1.2在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）所有人都是要死的。（2）有的人天生就近视。其中：（a）个体域D1为人类集合。（b）个体域D2为全总个体域。2.1.3谓词逻辑中命题的符号化82.1谓词逻辑命题的符号化谓词的蕴涵式：xG（x）（b）在个体域D2中除人外，还有其他的事物，因而在将（1）、（2）符号化时，必须考虑先将人分离出来，令M（x）：x是人。在D2中，（1）、（2）可分别描述如下：（1）对于宇宙间的一切事物，如果事物是人，则他是要死的。（

6、2）在宇宙间存在着天生就近视的人。将（1）、（2）分别符号化为：（1）x（M（x）F（x））（2）x（M（x）G（x））在个体域D1、D2中命题（1）、（2）都是真命题。2.1.3谓词逻辑中命题的符号化92.1谓词逻辑命题的符号化例2.1.3在个体域分别限制为（a）和（b）条件时，将下面的命题符号化：（1）对任意的x，都有x2-5x+6=（x-2）（x-3）（2）存在x，使得x+1=0。其中：（a）个体域D1为自然数集合。（b）个体域D2为实数集合。2.1.3谓词逻辑中命题的符号化10解（a）令F（x）：x2-5x+

7、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）都是真命题。2.1谓词逻辑命题的符号化2.1.3谓词逻辑中命题的符号化11例2.1.4将下列命题符号化，并指出真值情况。（1）没有人登上过月球。（2）所有人的头发未必都是黑色的。解个体域为全总个体域，令M（x）：x是人。（1）令F（x）：x登上过月球。命

8、题（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））为假