《《离散数学(贾振华主编)》电子教案 第二章 谓词逻辑》由会员分享，可在线阅读，更多相关《《离散数学(贾振华主编)》电子教案 第二章 谓词逻辑（57页珍藏版）》请在金锄头文库上搜索。
1、1,第二章 谓词逻辑,本章学习目标 命题逻辑中原子命题是最小的单位，不能够再进行分解，这给推理带来了很大局限性，本章引入谓词逻辑。学习关于谓词逻辑的相关概念和定理，解决实际问题。,2,第二章 谓词逻辑,2.1 谓词逻辑命题的符号化 2.2 谓词逻辑公式与解释 2.3 谓词逻辑约束公式的等价与蕴涵 2.4 前束范式 2.5 谓词演算的推理理论,3,第二章 谓词逻辑,2谓词：用来刻画个体词的性质或个体词之间关系的词 一般来说，“x是A”类型的命题可以用A（x）表达。对于 “x大于y”这种两个个体之间关系的命题，可表达为B（x，y） ，这里B表示“大于”谓词。我们把A（x）称为一元谓词， B（x，y
2、）称为二元谓词，M（a，b，c）称为三元谓词，依次 类推，通常把二元以上谓词称作多元谓词。,2.1 谓词逻辑命题的符号化,1个体词 ：个体词是指研究对象中不依赖于人的主观而独立存 在的具体的或抽象的客观实体 个体常项或个体常元 ： 个体变项或个体变元 ： 个体域或论域 ：,4,第二章 谓词逻辑,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）
3、H（c，d） 由于此蕴涵式的前件为真，后件为假，所以（2）中的命题为假。,例2.1 将下列命题在谓词逻辑中符号化，并讨论它们的真值： （1）只有4是素数，8才是素数。 （2）如果2小于3，则8小于7。,5,第二章 谓词逻辑,2.1 谓词逻辑命题的符号化,解（a）令F（x）：x要死的；G（x）：x天生就近视。 （1）在个体域D1中除人外，没有其他的事物，因而（1）可符号 化为： x F（x） （2）在个体域D1中有些人是天生就近视，因而（2）可符号化为,例 2.2 在个体域分别限制为（a）和（b）条件时，将下面的命题符号化： （1）所有人都是要死的。 （2）有的人天生就近视。 其中：（a）个体域
4、D1为人类集合。 （b）个体域D2为全总个体域。,6,第二章 谓词逻辑,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）都是真命题。,7,第二章 谓词逻辑,2.1 谓词逻辑命题的符号化,例2.3
5、在个体域分别限制为（a）和（b）条件时，将下面的命题 符号化： （1）对任意的x，都有x2-5x+6 =（x-2）（x-3） （2）存在x，使得x+1=0。 其中：（a）个体域D1为自然数集合。 （b）个体域D2为实数集合。,8,第二章 谓词逻辑,2.1 谓词逻辑命题的符号化,解 （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中命题（
6、1）、（2）都是真命题。,9,第二章 谓词逻辑,2.1 谓词逻辑命题的符号化,例2.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）为真。,10,第二章 谓词逻辑,2.1
7、谓词逻辑命题的符号化,例2.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）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）。,11,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.1 谓词逻辑的合式公式
8、,定义2.1 设P（x1，x2，xn）是n元谓词公式，其中，x1x2， xn是个体变项，则称P（x1，x2，xn）为谓词演算的原子公式。,定义2.2 谓词演算的合式公式定义如下： （1）原子公式是合式公式； （2）若A是合式公式，则（A）也是合式公式； （3）若A，B是合式公式，则（AB）、（AB）、（AB）、 （AB）是合式公式； （4）若A是合式公式，则x A、x A是合式公式； （5）只有有限次地应用（1）（4）构成的符号串才是合式公式。,12,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.1 谓词逻辑的合式公式,例2.5 在谓词逻辑中将下列命题符号化。 （1）不存在最大的数。
9、（2）计算机系的学生都要学离散数学。 解 取个体域为全总个体域。 （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）,13,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.1 谓词逻辑的合式公式,例2.6 将下列命题符号化。 （1）尽管有人聪明，但并非所有人都聪明。 （2）这只大红书柜摆满了那些古书。 解 （1）令C（x）：x聪明；M（x）：x是人。则命题（1）可符 号化为 x（M（x）C（x）x（M（x）C（x
10、） （2）令F（x，y）：x摆满了y；R（x）：x是大红书柜；Q（x）: x是古书；a：这只；b：那些。则命题（2）可符号化为 R（a）Q（b）F（a，b）,14,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.2 约束变元与自由变元,1约束变元与自由变元的概念 定义 2.3 在公式x F（x）和x F（x）中，称x为指导变元，F （x ）为相应量词的辖域或作用域。在x和x的辖域中，x的所有 出现都称为约束出现，F（x）中不是约束出现的其他变元均称为自 由出现。,15,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.2 约束变元与自由变元,例2.7 指出下列各式量词的辖域及变元的约
11、束情况： （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）,16,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.2 约束变元与自由变元,解 （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），其中
12、y是约束出现的，而x，z是自由出现的。在整个公式 中，x约束出现一次，自由出现两次，y约束出现一次，自由出现 一次，z仅自由出现一次。,17,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.2 约束变元与自由变元,2约束变元的换名与自由变元的代入 例2.8 对公式x（P（x） R（x，y）Q（x，y）进行换名。 解 对约束变元x换名为t后为 t（P（t） R（t，y）Q（x，y） 同理，对公式中的自由变元也可以更改，这种更改称作代入。自 由变元的代入规则是： （1）对于谓词公式中的自由变元，可以代入，此时需要对公式 中出现该自由变元的每一处进行代入。 （2）用以代入的变元与原公式中所有变
13、元的名称都不能相同。,18,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.2 约束变元与自由变元,2约束变元的换名与自由变元的代入 例2.9 对公式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）。,19,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.3 谓词逻辑公式的解释,定义2.4
14、 谓词逻辑公式的一个解释I，是由非空区域D和对G中常 项符号、函数符号、谓词符号以下列规则进行的一组指定组成： （1）对每一个常项符号指定D中一个元素。 （2）对每一个n元函数符号，指定一个函数。 （3）对每一个n元谓词符号，指定一个谓词。 显然，对任意公式G，如果给定G的一个解释I，则G在I的解释下 有一个真值，记作TI（G）。,20,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.3 谓词逻辑公式的解释,例2.10 指出下面公式在解释I下的真值。 （1）G=x（P（f（x）Q（x，f（a）； （2）H=x（P（x）Q（x，a）。 给出如下的解释I： D=2，3； a：2； f（2）：
15、3、f（3）：2； P（2）：0、P（3）：1； Q（2，2）：1、Q（2，3）：1、Q（3，2）：0、Q（3，3）：1；,21,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.3 谓词逻辑公式的解释,解 （1）TI（G）= TI（P（f（2）Q（2，f（2） （P（f（3）Q（3，f（2） = TI（P（3）Q（2，3）（P（2）Q（3，3） = （11）（01） = 1 （2）TI（H）= TI（P（2）Q（2，2）P（3）Q（3，2） =0110 =0,22,第二章 谓词逻辑,2.2 谓词逻辑公式与解释 2.2.3 谓词逻辑公式的解释,定义2.5 若存在解释I，使得G在解释I下取值为真，则称公式G为 可满足的，简称I满足G。,定义2.6 若不存在解释I，使得I满足G，则称公式G为永假式（或 矛盾式）。若G的所有解释I都满足G，则称公式G为永真式（或 重言式）。,23,第二章 谓词逻辑,2.3 谓词逻辑约束公式的等价与蕴涵 2.3.1 谓词逻辑的等价公式,定义2.7 设A、B是命题逻辑中的任意两个公式，设它们有共同的 个体域E，若对任意的解释I都有TI（A）= TI（B），则称公式A 、B在E上是等价的，记作AB。,24,第二章 谓词逻辑,2.3 谓词逻辑约束公式的等价与蕴涵
