《离散数学教学课件贾振华第二章谓词逻辑》由会员分享，可在线阅读，更多相关《离散数学教学课件贾振华第二章谓词逻辑（78页珍藏版）》请在金锄头文库上搜索。
1、1,第二章 谓词逻辑,2,本章学习目标,命题逻辑中原子命题是最小的单位，不能够再进行分解，这给推理带来了很大局限性，本章引入谓词逻辑。学习关于谓词逻辑的相关概念和定理，解决实际问题。,3,主要内容,2.1 谓词逻辑命题的符号化 2.2 谓词逻辑公式与解释 2.3 谓词逻辑约束公式的等价与蕴涵 2.4 前束范式 2.5 谓词演算的推理理论,4,2.1 谓词逻辑命题的符号化,2.1.1 个体词与谓词 2.1.2 量词 2.1.3 谓词逻辑中命题的符号化,5,2.1 谓词逻辑命题的符号化,2谓词：用来刻画个体词的性质或个体词之间关系的词 一般来说，“x是A”类型的命题可以用A（x）表达。对于 “x大
2、于y”这种两个个体之间关系的命题，可表达为B（x，y） ，这里B表示“大于”谓词。我们把A（x）称为一元谓词， B（x，y）称为二元谓词，M（a，b，c）称为三元谓词，依次 类推，通常把二元以上谓词称作多元谓词。,2.1.1个体词与谓词,1个体词 ：个体词是指研究对象中不依赖于人的主观而独立存 在的具体的或抽象的客观实体 个体常项或个体常元 ： 个体变项或个体变元 ： 个体域或论域 ：,6,2.1 谓词逻辑命题的符号化,解（1）设谓词G（x）：x是素数，a：4，b：8；（1）中的 题符号化为谓词的蕴涵式： G（a）G（b） 由于此蕴涵式的前件为假，所以（1）中的命题为真。 （2）设谓词H（x，
3、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个体词与谓词,7,2.1 谓词逻辑命题的符号化,全称量词 对于日常生活和数学中出现的“一切的”、“任意的”、“所有的”、“每一个”、“都”、“凡”等词统称为全称量词，用符号“”表示。并用x，y表示个体域中的所有个体，用（x ）F（x），（y）F（y）等表示个体域中的所有个体具有性质F。 存
4、在量词 对日常生活和数学中常用的“存在”、“存在一个”、“有一个”、“至少有一个”、“有些”、“有的”等词统称为存在量词，用符号“”表示。并用x，y表示个体域中有的个体，用（x）F（x），（y）F（y）等表示个体域中有的个体具有性质F。,2.1.2 量词,8,2.1 谓词逻辑命题的符号化,解（a）令F（x）：x要死的；G（x）：x天生就近视。 （1）在个体域D1中除人外，没有其他的事物，因而（1）可符号 化为： x F（x） （2）在个体域D1中有些人是天生就近视，因而（2）可符号化为,例 2.1.2 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化： （1）所有人都是要死的。 （2
5、）有的人天生就近视。 其中：（a）个体域D1为人类集合。 （b）个体域D2为全总个体域。,2.1.3 谓词逻辑中命题的符号化,9,2.1 谓词逻辑命题的符号化,谓词的蕴涵式： x G（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）都是真命题。,2.
6、1.3 谓词逻辑中命题的符号化,10,2.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 谓词逻辑中命题的符号化,11,解 （a）令F（x）：x2-5x+6 =（x-2）（x-3）；G（x）：x+1=0。 （1）可符号化为： x F(x) （2）可符号化为： x G（x） 在个体域D1中命题（1）为真命题，命题（2）为假命题。 （b）在个体域D2中（1）、（2）符号化
7、分别为 （1） x F（x） （2） x G（x） 在个体域D2中命题（1）、（2）都是真命题。,2.1 谓词逻辑命题的符号化,2.1.3 谓词逻辑中命题的符号化,12,例2.1.4 将下列命题符号化，并指出真值情况。 （1）没有人登上过月球。 （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） 我们知道有的人头
8、发是褐色的，所以x（M（x）H（x）为 假，故命题（2）为真。,2.1 谓词逻辑命题的符号化,2.1.3 谓词逻辑中命题的符号化,13,例2.1.5 将下列命题符号化。 （1）火车比汽车跑得快。 （2）有的火车比所有汽车跑得快。 （3）并不是所有的火车比汽车跑得快。 （4）不存在完全相同的两辆汽车。 解 设个体域为全总个体域。令C（x）：x是火车；M（y）：y是汽车；Q（x，y）：x比y跑得快；L（x，y）：x和y跑得同样快。 这4个命题分别符号化为： （1）（x）（y）（C（x）G（y）Q（x，y）； （2）（x）（C（x）（y）（G（y）Q（x，y）； （3）（x）（y）（C（x）G（y）
9、Q（x，y）； （4）（x）（ y）（G（x）G（y）S（x，y）。,2.1 谓词逻辑命题的符号化,2.1.3 谓词逻辑中命题的符号化,14,2.2 谓词逻辑公式与解释,2.2.1 谓词逻辑的合式公式 2.2.2 谓词的约束和替换 2.2.3 谓词逻辑公式的解释,15,2.2 谓词逻辑公式与解释,2.2.1 谓词逻辑的合式公式,定义2.2.1 谓词逻辑中项的定义： （1）任何一个个体变元或个体常元是项； （2）若f（x1，x2，xn）是任意的n元函数，t1，t2，tn是任意的n个项，则f（t1，t2，tn）是项； （3）由有限次使用（1），（2）得到的表达式是项； 定义2.2.2 设P（x1，
10、x2，xn）是n元谓词公式，其中，x1x2， xn是个体变项，则称P（x1，x2，xn）为谓词演算的原子公式。,16,2.2 谓词逻辑公式与解释,2.2.1 谓词逻辑的合式公式,定义2.2.3 谓词演算的合式公式定义如下： （1）原子公式是合式公式； （2）若A是合式公式，则（A）也是合式公式； （3）若A，B是合式公式，则（AB）、（AB）、（AB）、 （AB）是合式公式； （4）若A是合式公式，则x A、x A是合式公式； （5）只有有限次地应用（1）（4）构成的符号串才是合式公式。,17,例2.2.1 在谓词逻辑中将下列命题符号化。 （1）不存在最大的数。 （2）计算机系的学生都要学离散
11、数学。 解 取个体域为全总个体域。 （1）令F（x）：x是数，L（x，y）：x大于y；则命题（1）符号 化为 x（F（x） y（F（y） L（x，y） （2）令C（x）：x是计算机系的学生，G（x）：x要学离散数学; 则命题（2）可符号化为：x（C（x） G（x）,2.2 谓词逻辑公式与解释,2.2.1 谓词逻辑的合式公式,18,例2.2.2 将下列命题符号化。 （1）尽管有人聪明，但并非所有人都聪明。 （2）这只大红书柜摆满了那些古书。 解 （1）令C（x）：x聪明；M（x）：x是人。则命题（1）可符 号化为 x（M（x）C（x）x（M（x）C（x） （2）令F（x，y）：x摆满了y；R（x
12、）：x是大红书柜；Q（x）: x是古书；a：这只；b：那些。则命题（2）可符号化为 R（a）Q（b）F（a，b）,2.2.1 谓词逻辑的合式公式,2.2 谓词逻辑公式与解释,19,1约束变元与自由变元的概念 定义 2.2.4 在公式x F（x）和x F（x）中，称x为指导变元，F （x ）为相应量词的辖域或作用域。在x和x的辖域中，x的所有 出现都称为约束出现，F（x）中不是约束出现的其他变元均称为自 由出现。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,20,例2.2.3 指出下列各式量词的辖域及变元的约束情况： （1）x（F（x，y） G（x，z） （2）x（P（x）y R（
13、x，y） （3）x（F（x） G（y） y（H（x）M（x，y，z）,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,21,解 （1）对于x的辖域是A=（F（x，y） G（x，z），在A 中，x是约束出现的，而且约束出现两次，y，z均为自由出现， 而且各自由出现一次。 （2）对于x的辖域是（P（x）y R（x，y），y的辖域是 R（x，y），x，y均是约束出现的。 （3）对于x的辖域是（F（x） G（y），其中x是约束出现 的，而y是自由出现的。对y的辖域是（H（x）M（x，y， z），其中y是约束出现的，而x，z是自由出现的。在整个公式 中，x约束出现一次，自由出现两次，y约束出现
14、一次，自由出现 一次，z仅自由出现一次。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,22,2约束变元的换名与自由变元的代入 约束变元换名的规则： （1）将量词的作用变元及其辖域中所有相同符号的变元用一个新的变元符号代替，公式的其余部分不变。 （2）新的变元符号是原公式中没有出现的。 （3）用（1）、（2）得到的新公式与原公式等值。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,23,例2.2.4 对公式x（P（x） R（x，y）Q（x，y）进行换名。 解 对约束变元x换名为t后为 t（P（t） R（t，y）Q（x，y） 同理，对公式中的自由变元也可以更改，这种更改称
15、作代入。自 由变元的代入规则是： （1）对于谓词公式中的自由变元，可以代入，此时需要对公式 中出现该自由变元的每一处进行代入。 （2）用以代入的变元与原公式中所有变元的名称都不能相同。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,24,例2.2.5 对公式x（F（x） G（x，y）y H（y）代入。 解 对y实施代入，经过代入后原公式为 x（F（x） G（x，t） y H（y） 另外，量词作用域中的约束变元，当论域的元素是有限时，个体 变元的所有可能的取代是可以枚举的。 设论域元素为a1，a2，an， 则 x A（x） A（a1）A（a2）A（an） x A（x） A（a1）A（a2）A（an）。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,25,定义2.2.5 没有自由变元的公式称为闭式。 例如：（x）（ y）（P（x） R（x，y）（x）（y）Q（x，y）是闭式。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,26,2.2.3 谓词逻辑公式的解释,定义2.2.6 谓词逻辑公式的一个解释I，是由非空区域D和对G中常 项符号、函数符号、谓词符号以下列规则进行的一组指定组成： （1）对每一个常项符号指定D中一个元素。 （2）对每一个n元函数符号，指定一个
