2013级版第二章谓词逻辑

《2013级版第二章谓词逻辑》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、离散数学离散数学第二章第二章谓词逻辑谓词逻辑裘国永2013年8月24日本章内容及教学要点2.1基本概念教学内容：个体，谓词，全称量词，存在量词陕西师范大学计算机科学学院2.2谓词公式与翻译教学内容：谓词公式，命题谓词符号化陕西师范大学计算机科学学院2.3自由变元与约束变元教学内容：自由变元，约束变元，辖域，换名规则，代入规则陕西师范大学计算机科学学院2.4谓词公式的解释与分类教学内容：谓词公式的解释陕西师范大学计算机科学学院2.5谓词演算的等价式与蕴涵式教学内容：等价式，蕴涵式陕西师范大学计算机科学学院2.6谓词演算中的公式范式教学

2、内容：前束范式，柯林斯范式陕西师范大学计算机科学学院2.7谓词演算的推理理论教学内容：全称量词消去规则，存在量词消去规则，全称量词引入规则，存在量词引入规则，谓词演算的推理陕西师范大学计算机科学学院命题逻辑研究的对象是命题及命题之间的逻辑关系。命题逻辑认为命题不可分，命题之间的关系通过命题的真假值反映出来。这样虽然能进行简单的推理，但它的表达能力有限。例如下列简单的苏格拉底三段论就不能用命题逻辑进行推理：陕西师范大学计算机科学学院所有的人都是要死的。苏格拉底是人。所以苏格拉底是要死的。陕西师范大学计算机科学学院所以需要对命题的内部结

3、构进行细分研究。根据语法分析中将句子分成主语、谓语和宾语这样的成分的思想，我们引入谓词演算。陕西师范大学计算机科学学院2.1基本概念定义2.1.1在原子命题中，所描述的对象称为个体（Individual）；用以刻画个体的性质或个体间关系的词称为谓词（Predicate）。陕西师范大学计算机科学学院例（1）张三是大学生。（2）3大于5。个体：“张三”、“3”、“5”谓词：“…是大学生”（刻画个体“张三”的性质）“…大于…”（刻画个体“3”和“5”间的关系）陕西师范大学计算机科学学院有了个体和谓词的概念之后，可以进一步刻画命题的内在结构

4、和命题之间的关系。例如，“张三是大学生”和“李四是大学生”之间的关系是用命题逻辑无法表达的，现在可用谓词“…是大学生”及个体“张三”、“李四”刻画。陕西师范大学计算机科学学院定义2.1.2表示具体或特定个体的词称为个体常元，用小写字母a、b等表示。表示泛指个体的词称为个体变元，用x、y等表示。定义2.1.3表示具体性质或关系的谓词称为谓词常元，表示泛指的性质或关系的谓词称为谓词变元。谓词常元或谓词变元都用大写字母P、Q等表示。陕西师范大学计算机科学学院例2.1.1（1）x是大学生。x是个体变元。（2）3与5具有关系F。F是谓词变元。

5、陕西师范大学计算机科学学院定义2.1.4一个原子命题用一个谓词（如P）和n个有序个体常元（如a1,a2,…,an）表示成P(a1,a2,…,an)，称为该原子命题的谓词形式。若x1，x2，…，xn为个体变元，称P(x1,x2,…,xn)为n元谓词或n元命题函数。一般而言，一元谓词表达了个体的性质，而n元谓词表达了n个个体之间的关系。陕西师范大学计算机科学学院n元谓词不是命题。只有当个体变元用特定的个体替代时，才成为一个命题。但个体变元的取值范围，对命题的真值极有影响。陕西师范大学计算机科学学院例2.1.2F(x)表示x是大学生。当取

6、值范围限定为某大学的全体学生时，F(x)是真的，但当取值范围限定为某中学的所有学生时，则F(x)是假的。因此，在谓词逻辑中，我们要指定个体的取值范围。陕西师范大学计算机科学学院定义2.1.5个体的取值范围称为个体域或论域（Domain）；所有个体的取值范围称为全总个体域（Universaldomain）。注如果没有特别说明，个体的取值范围总是全总个体域。当给定个体域D后，个体常元就是D中的一个特定元素，个体变元则可以取D中任一个元素。陕西师范大学计算机科学学院例2.1.3将下列命题符号化：（1）张三和李四都是三好学生。（2）赵斌是象

7、棋迷或围棋迷。（3）李林比张强高。（4）如果你不出去，我就不进来。陕西师范大学计算机科学学院解（1）S(a)∧S(b)，其中S(x)：x是三好学生，a：张三，b：李四。（2）Q(a)∨R(a)，其中Q(x)：x是象棋迷，R(x)：x是围棋迷，a：赵斌。（3）T(a,b)，其中T(x,y)：x比y高，a：李林，b：张强。（4）F(a)G(b)，其中F(x)：x出去，G(x)：x进来，a：你，b：我。陕西师范大学计算机科学学院有了个体和谓词的概念之后，对有些命题仍然不能准确地符号化，如“所有人都是要死的”。原因是还缺少表示个体数量

8、关系的词。下面我们再引入量词的概念。陕西师范大学计算机科学学院定义2.1.6符号x表示“所有的x”、“每一个x”和“任意一个x”等词语，称x为全称量词（Universalquantifier）；符号x表示“对某一个x”、“至少存