离散数学第二章 谓词逻辑

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

1、第二章谓词逻辑离散数学陈志奎主编人民邮电出版社前言命题逻辑对于反映在自然语言中的逻辑思维进行了精确的形式化描述，能够对一些比较复杂的逻辑推理，用形式化方法进行分析。在命题逻辑中，把命题分解到原子命题为止，认为原子命题是不能再分解的，仅仅研究以原子命题为基本单位的复合命题之间的逻辑关系和推理。但这对科学中的演绎推理和数学中的推理是不够的，有些推理用命题逻辑就难以确切地表示出来。要求在命题逻辑中，试进行下列推理:“苏格拉底三段论”：凡人都是要死的，P苏格拉底是人，Q所以苏格拉底是要死的。R(PΛQ)→R命题逻辑中，命题

2、被当作一个基本的，不可分割的单位，只研究由原子命题和联接词所组成的复合命题，没有研究命题内部的内部结构以及命题之间的内在关系。教材及资料类似的还有很多，例如：所有的人都要呼吸，李华是人，所以李华要呼吸。所有的正整数都大于0，3是正整数，所以3大于0。本章介绍的谓词逻辑，对原子命题的成份、结构和原子命题间的共同特性等作了进一步分析。引入了个体词、谓词、量词、谓词公式等概念，在此基础上研究谓词公式间的等值关系和蕴含关系，并且对命题逻辑中的推理规则进行扩充和进行谓词演绎。PART01基本概念和表示主要内容PART02PA

3、RT03谓词逻辑的等价式与蕴涵式PART04PART05格的定义与性质谓词逻辑的翻译与解释谓词逻辑中的推论理论2.1基本概念和表示在命题逻辑中，命题是具有真假意义的陈述句。从语法上分析，一个陈述句由主语和谓语两部分组成。在谓词逻辑中，为揭示命题内部结构及不同命题的内部结构关系，就按照这两部分对命题进行分析，并且把主语称为个体或者客体，把谓语称为谓词。62.1基本概念和表示定义2.1在原子命题中，所描述的对象称为个体；用以描述个体的性质或个体间关系的部分，称为谓词。个体，是指可以独立存在的事物。它可以是抽象的概念，也

4、可以是一个具体的实体。如计算机，自然数，智能，情操等。表示特定的个体，称为个体常元，以a，b，c，…或带下标的ai，bi，ci，…表示。任何个体的变化都有一个范围，这个变化范围称为个体域(或论域)。个体域可以是有限的，也可以是无限的。所有个体域的总和叫作全总个体域。以某个个体域为变化范围的变元叫个体变元。以x，y，z，…或者xi，yi，zi，…表示。7个体、谓词和谓词表示2.1基本概念和表示谓词，当与一个个体相联系时，刻画了个体的性质；当与两个或多个个体相联系时，刻画了个体之间的关系。通常都用大写英文字母，如P，Q

5、，R，…来表示。例如有以下两个命题：小明是大学生。刘亮是大学生。其中“…是大学生”是谓词，“小明”、“刘亮”是个体。谓词在这里是用来刻划个体的性质的。如用S(x)表示“x是大学生”，a表示李洪，b表示张宾，则上述三个命题可以表示成S(a)，S(b)。8个体、谓词和谓词表示2.1基本概念和表示定义2.2一个原子命题用一个谓词（如P）和n个有次序的个体常元（如a1，a2，…，an）表示成P(a1，a2，…，an)，称它为该原子命题的谓词形式或命题的谓词形式。应注意：命题的谓词形式中个体的出现顺序影响命题的真值，不能随意

6、变动。否则真值会变化，如上面所举的例子中L(b，a，c)为假。在谓词中包含的个体数目称为谓词的元数。与一个个体变元相联系的谓词叫一元谓词，与多个个体变元相联系的谓词叫多元谓词。例如S(x)是一元谓词，L(x，y)是二元谓词。9个体、谓词和谓词表示2.1基本概念和表示一个n元谓词常可以表示成P(x1，x2，…，xn)，一般讲它是一个以变元的个体域为定义域，以{T,F}为值域的n元泛函。常称P(x1，x2，…，xn)为n元谓词变元命名式。它还不是一个命题，仅告诉我们该谓词变元是n元的以及个体变元之间的顺序如何。只有将其

7、中的谓词赋予确定的含意，给每个个体变元都代之以确定的个体后，该谓词才变成一个确定的命题，有确定的真值。10个体、谓词和谓词表示2.1基本概念和表示定义2.3全称量词、存在量词、存在唯一量词。（1）符号称为全称量词符，用来表达“对所有的”、“任意的”、“每一个”等词语。“(x)P(x)”表示命题：“对于个体域中所有个体x，谓词P(x)均为T”。其中“(x)”称为全称量词，读作“对于所有的x”。谓词P(x)称为全称量词(x)的辖域或作用范围。（2）符号称为存在量词符，用来表达“存在一些”、“对于一些”、“至少有一个”

8、等词语。“(x)Q(x)”表示命题:“在个体域中存在某些个体使谓词Q(x)为T”。其中“(x)”称为存在量词，读作“存在x”。谓词Q(x)称为存在量词(x)的辖域或存在范围。（3）符号!称为存在唯一量词符，用来表达“恰有一个”、“存在唯一”等词语。“(!x)R(x)”表示命题：“在个体域中恰好有一个个体使谓词R(x)为T”。其中“(!x)”称为存