《离散数学》（7） 谓词逻辑
发布人： 日期：2012-03-14 00:00浏览次数：7352点赞次数：0
湛江开大,湛江开放大学,湛江市财政职业技术学校,湛江市广播电视大学,湛江电大,中专教育,中职教育,成人教育,成人大专,成人本科，官网,教育部电子注册，国际学历绿卡。湛江开放大学（湛江市广播电视大学）办学三十年来...
第2章 谓词逻辑
一、教学要求
1. 理解谓词、量词、个体词、个体域、原子公式、谓词公式和变元等概念。会将不太复杂的命题符号化。
2. 掌握在有限个体域下求公式的真值和某些公式在给定解释下真值的方法，判别公式类型(永真式、永假式和可满足式)的方法。
3. 掌握谓词演算的等值式和重言蕴含式 (六种情况：(1)命题公式的推广；(2)量词否定式的等值式；(3)量词辖域扩张和收缩的等值式；(4)量词与联结词Ú，Ù，®的等值式；(5)量词与联结词的重言蕴含式；(6)两个量词公式间的等值式与重言蕴含式)。会进行谓词公式的等值演算。
4. 了解前束范式的概念，会求公式的前束范式。
5. 了解谓词逻辑推理的规则：全量词消去规则(US规则)；全量词附加规则(UG规则)；存在量词消去规则(ES规则)；存在量词附加规则(EG规则)
本章重点：谓词与量词，公式与解释，前束范式，谓词逻辑推理证明。
二、学习辅导
在命题逻辑中，我们把原子命题作为基本研究单位，对原子命题不再进行分解，只有复合命题才可以分解，揭示了一些有效的推理过程. 但是进一步研究发现，仅有命题逻辑是无法把一些常见的推理形式包括进去. 例如 “凡人要死，张三是人，张三要死”显然是正确推理. 用命题逻辑解释三段式. 设 P：人要死；Q张三是人；R：张三要死。要反映这种内在联系，就要对命题逻辑进行分析，分析出其中的个体词、谓词和量词，再研究它们之间的逻辑关系，总结出正确的推理形式和规则，这就是谓词逻辑的研究内容。
1. 谓词与量词
学习这一部分要反复理解谓词和量词引入的意义，概念的含义。
在谓词逻辑中，原子命题分解成个体词和谓词。个体词是可以独立存在的客体，它可以是具体事物或抽象的概念，如小张，房子，南京，大米，思想，实数2等等。谓词是用来刻划个体词的性质或事物之间的关系的词。
例如 (1) ln5是无理数；
(2) 高可比李木相高4cm；
(3) 郑州位于北京和广州之间。
这时三个简单命题，其中ln5，高可，李木相，郑州，北京，广州等都是个体词，而“是无理数”，“……比……高4cm”，“……位于……和……之间”等都是谓词。
个体词分个体常项(用a,b,c,d,…表示)和个体变项(用x,y,z,…表示)；谓词分谓词常项(表示具体性质和关系的词)和谓词变项(表示抽象的或泛指的谓词)，用F,G,P,…表示。
个体常项a和个体变项都具有性质F，记作F(a)或F(x);个体常项a,与b或个体变项x与y具有关系L,记作L(a,b)或L(x,y)。一般地，用F(a)表示a是无理数，其中a表示ln5，F表示的是“…是无理数”。当F的含义不变时，则F(x)表示x是无理数，x是个体变项，F谓词常项，F(x)不是命题，而是命题变项，F(a)是命题。用M(x,y,z)表示“z=x×y”，M(x,y,z)不是命题。a表示3，b表示5，c表示15，M(a,b,c)表示“15＝3×5”。M(a,b,c)是命题，真值为1，若c=12，那么M(a,b,c)是命题，真值为0。
注意，单独的个体词和谓词不能构成命题，将个体词和谓词分开不是命题。
例2.1 将下列命题符号化：
(1) 丘华和李兵都是学生；
(2) 2既是偶数又是素数；
(3) 如果张华比黎明高，黎明比王宏高，则张华比王宏高。
解 (1) 设个体域是人的集合。
P(x)：:x是学生。
a：丘华
b：黎兵 该命题符号化为P(a)ÙP(b)
(2) 设个体域为正整数集合N＋。
F(x)：x是偶数，
Q(x)：x是素数
a：2 该命题符号化为F(a)ÙQ(a)
(3) 设个体域是人的集合。
G(x,y)：x比y高。
a：张华
b：黎明
c：王宏 该命题符号化为G(a,b)ÙG(b,c)®G(a,c)
量词是在命题中表示数量的词，量词有两类：全称量词"，表示“所有的”或“每一个”；存在量词$，表示“存在某个”或“至少有一个”。
例2.2 将下列命题符号化
(1) 每个母亲都爱自己的孩子；
(2) 所有的人都呼吸；
(3) 有某些实数是有理数。
解 (1) 设个体域是所有母亲的集合。
M(x)：x表示爱自己的孩子；
该命题符号化为"xM(x)。
(2) 设个体域为人的集合。
H(x)：x表示要呼吸。 该命题符号化为"xH(x) 或设个体域为生物集合，
M(x)：x是人。
H(x)：x表示要呼吸。 该命题符号化为"x(M(x)®H(x))
(3) 设个体域为数的集合。
R(x)：x表示实数
Q(x)：x表示有理数。 该命题符号化$x(R(x)ÙQ(x))。
在谓词逻辑，使用量词应注意以下几点：
(1) 在不同个体域中，命题符号化的形式可能不同，命题的真值也可能会改变。
(2) 在考虑命题符号化时，如果对个体域未作说明，一律使用全个体域。
(3) 多个量词出现时，不能随意颠倒它们的顺序，否则可能会改变命题的涵义。
2. 公式与解释
学习这一部分内容要侧重于能将谓词逻辑公式表达式中，量词消除写成与之等值的公式，然后将解释中的数值代入，求出真值，并着重理解在谓词和量词的作用下变元的自由性、约束性和更名规则、代入规则等。
我们将命题常数0，1，一个命题和命题变元以及一个命题函数P(x1,x2,…,xn)，统称原子公式，由原子公式、联结词和量词可构成谓词公式(严格定义见教材)。命题的符号化结果都是谓词公式，例如"x(F(x)®G(x))，$x(F(x)ÙG(x))，"x"y(F(x)ÙF(y)ÙL(x,y)®H(x,y))等都是谓词公式，当然$x(F(x)ÙG(x,y)),"x(F(x)®G(x,y))等也是谓词公式。
在谓词公式"xA和$xA中，x是指导变元，A是相应量词的辖域。在"x和$x的辖域A中，x的所有出现都是约束出现，即x是约束变元，不是约束出现的变元，就是自由变元。也就是说，量词后面的式子是辖域。量词只对辖域内的同一变元有效。
换名规则，就是把公式中量词的指导变元及其该量词的辖域中的该变元换成该公式中没有出现的个体变元，公式的其余部分不变。
代入规则，就是把公式中的某一自由变元，用该公式中没有出现的个体变元符号替代，且要把该公式中所有的该自由变元都换成新引入的该符号。
谓词公式只是一个符号串，没有什么意义，但我们给这个符号串一个解释，使它具有真值，就变成一个命题。所谓解释就是使公式中的每一个变项都有个体域中的元素相对应。
解释有四部分组成：
(1) 非空个体域D；
(2) D中有一部分特定元素，用来解释个体常项；
(3) D上一些特定函数，用来解释出现的函数变项；
(4) D上一些特定谓词，用来解释谓词变项。
和命题逻辑一样，在谓词逻辑中，有的公式在任何解释下都真，也有的公式在任何解释下都假。以此，把公式分为三类：在任何解释下公式A为真，或者公式A的真值表全为1，这就是永真式；在任何解释下公式A为假，或者公式A的真值表全为0，这就是永假式；公式A不总是假，或者公式A的真值表至少有一个1，这就是可满足式。由此可见，永真式也是可满足式。
一般地，判定一个公式是不是可满足式，还没有一定的算法。但是，可以证明，重言式的代换实例一定是永真式。而矛盾式的代换实例均为矛盾式。
3. 前束范式
一个谓词公式的前束范式，仍然是谓词公式，只是把谓词公式的所有量词均提到公式的开头，而且它的辖域一直延伸到公式的末尾。
每个谓词公式F都可以变换成与它等值的前束范式。其步骤如下：
① 消去联结词®，«，`Ú；
② 将联结词Ø向内深入，使之只作用于原子谓词公式；
③ 利用换名或代入规则使所有约束变元的符号均不同，并且自由变元与约束变元的符号也不同；
④ 利用量词辖域的扩张和收缩律，扩大量词的辖域至整个公式；
⑤ 利用分配律将公式化为前束范式。
重要的是弄清楚前束范式的定义，求前束范式主要是利用基本等值式、蕴含式和换名规则，把一个谓词公式化为前束范式，虽然前束范式是谓词公式的一种标准形式，但是一般一个谓词公式的前束范式并不是唯一的。
4.谓词逻辑的推理理论
谓词演算的推理是命题演算推理的推广和扩充，命题演算中的一些规则，如基本等值公式，重言蕴含式以及P，T，CP规则在谓词演算中仍然使用。但是在谓词演算推理中，某些前提和结论可能受到量词的限制，为了使用这些推理，必须在推理过程中，有消去和附加量词的规则，即US规则(全称量词消去规则)，UG规则(全称量词附加规则)，ES规则(存在量词消去规则)，EG规则(存在量词附加规则)等，以便使谓词演算公式的推理过程可类似于命题演算的推理进行。