《第二章 谓词逻辑(6学时)》由会员分享，可在线阅读，更多相关《第二章 谓词逻辑(6学时)（54页珍藏版）》请在金锄头文库上搜索。
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大于y
2、”这种两个个体之间关系的命题，可表达为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，y）：x小于
3、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）有的人天生就近视。其中：（a）个
5、体域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.1.3 谓词逻辑中命题的符号化,10,2.1 谓词逻辑命
6、题的符号化,例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）符号化分别为（1） x F（x）（2） x G（x）在个体域D2中命题（1）、（2
7、）都是真命题。,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）我们知道有的人头发是褐色的，所以x（M（x）H（x）为假，故命题（2）为真。,2.1 谓词逻辑命题的符号化,2.1.3
8、 谓词逻辑中命题的符号化,13,例2.1.5 将下列命题符号化。（1）火车比汽车跑得快。（2）有的火车比所有汽车跑得快。（3）并不是所有的火车比汽车跑得快。（4）不存在完全相同的两辆汽车。,2.1 谓词逻辑命题的符号化,2.1.3 谓词逻辑中命题的符号化,14,解 设个体域为全总个体域。令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）Q（x，y）； （4）（x）（ y）（G（x）G
9、（y）S（x，y）。,15,2.2 谓词逻辑公式与解释,2.2.1 谓词逻辑的合式公式 2.2.2 谓词的约束和替换 2.2.3 谓词逻辑公式的解释,16,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，x2，xn）是n元谓词公式，其中，x1x2，xn是个体变项，则称P（x1，x2，xn）为谓词演算的原子公式。,17,2
10、.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）构成的符号串才是合式公式。,18,例2.2.1 在谓词逻辑中将下列命题符号化。（1）不存在最大的数。（2）计算机系的学生都要学离散数学。解 取个体域为全总个体域。（1）令F（x）：x是数，L（x，y）：x大于y；则命题（1）符号化为x（F（x） y（F（y） L（x
11、，y）（2）令C（x）：x是计算机系的学生，G（x）：x要学离散数学;则命题（2）可符号化为：x（C（x） G（x）,2.2 谓词逻辑公式与解释,2.2.1 谓词逻辑的合式公式,19,例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）：x是大红书柜；Q（x）:x是古书；a：这只；b：那些。则命题（2）可符号化为R（a）Q（b）F（a，b）,2.2.1 谓词逻辑的合式公式,2.2 谓词逻辑公
12、式与解释,20,1约束变元与自由变元的概念定义 2.2.4 在公式x F（x）和x F（x）中，称x为指导变元，F（x ）为相应量词的辖域或作用域。在x和x的辖域中，x的所有出现都称为约束出现，F（x）中不是约束出现的其他变元均称为自由出现。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,21,例2.2.3 指出下列各式量词的辖域及变元的约束情况：（1）x（F（x，y） G（x，z）（2）x（P（x）y R（x，y）（3）x（F（x） G（y） y（H（x）M（x，y，z）,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,22,解 （1）对于x的辖域是A=（F（x，y）
13、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约束出现一次，自由出现一次，z仅自由出现一次。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,23,2约束变元的换名与自由变元的代入约束变元换名的规则： （1）将量词的作用变元及其辖域中所有
14、相同符号的变元用一个新的变元符号代替，公式的其余部分不变。（2）新的变元符号是原公式中没有出现的。（3）用（1）、（2）得到的新公式与原公式等值。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,24,例2.2.4 对公式x（P（x） R（x，y）Q（x，y）进行换名。解 对约束变元x换名为t后为t（P（t） R（t，y）Q（x，y）同理，对公式中的自由变元也可以更改，这种更改称作代入。自由变元的代入规则是：（1）对于谓词公式中的自由变元，可以代入，此时需要对公式中出现该自由变元的每一处进行代入。（2）用以代入的变元与原公式中所有变元的名称都不能相同。,2.2.2 谓词的约束和替换,2.2 谓词逻辑公式与解释,25,例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 谓词逻辑公式与解释,26,定义2.2.5 没有自由变元的公式称为闭式。例如：（x）（ y）（P（x） R（x，y）（x）（y）Q（x，y）是闭式。,
