苏州大学离散数学-谓词逻辑.pptVIP

谓词逻辑(主要内容) 2-1谓词的概念及表示 2-2命题函数与量词 2-3谓词公式与翻译 2-4变元的约束 2-5谓词演算的等价式与蕴含式 2-6前束范式 2-7谓词演算的推理理论 * 第二章 谓词逻辑 由第一章命题逻辑的学习了解到：命题逻辑主要研 究命题和命题演算，研究的基本单位是原子命题，并认为 原子命题不能再分解，但进一步研究发现，某些情况下必 须对原子命题进行再次分析，否则某些推理无法用命题逻 辑表示。 如著名的“苏格拉底三段论”：所有的人都是要死的， 苏格拉底是人，所以苏格拉底总是要死的。直觉判断该结 论是真，但在命题逻辑中无法解决。故必须对原子命题的 成分，结构和命题间的共同属性等作进一步分析，而这正 是本章“谓词逻辑” 研究的主要内容。 谓词逻辑又称一阶谓词逻辑，狭谓词逻辑，初等逻 辑或量词理论等。 2-1 谓词的概念与表示 命题是反映判断的句子，具有真假意义；一般情况下，反映判 断的句子是由主语和谓语两部分组成。 如 “电子计算机是科学计算的工具”，其中“电子计算机” 是主语，又叫客体（或个体），可独立存在，即可以是具体的，又 可以是抽象的。 “是科学计算的工具”是谓语，又叫谓词，用以刻划客体的性 质和关系。 如：张三是个大学生，李四是个大学生。 此两命题可用两个不同的符号：P、Q来表示。但它们具有相 同属性，即“是个大学生”。故引入一符号表示“是个大学生”，再引 入一种方法表示客体名称，则能把“××是个大学生”命题本质属性 刻划出来。又如 (a)他是三好学生。 (b)7是质数。 (c)每天早晨做广播操是好习惯。 (d)5大于3。 (e)哥白尼指出地球绕着太阳转。 上述命题中“是三好学生” 、“是质数”、“是好习惯”、 “大于”、 “指出”均是谓词，其中前三个指明客体性质，后两个指明两个客体 之间关系。 用谓词表达命题，必须包括客体和谓词字母两部分。一般， “b是A”命题可用A(b)表达；“a是小于b”用B(a,b)表示，其中B表示 “是小于”，“点a在b与c之中”表示为：L(a,b,c)，其中L：…在…与… 之中。 单独一个谓词不是完整的命题。把谓词字母填以客体所得的 式子称为谓词填式。 一般，n元谓词需要n个客体名称插入到固定位置上，如果A 为n元谓词,a1,a2, …,an是客体名称，则A(a1,a2, …,an)即可成为命题。 注： 1、大写字母表示谓词，小写字母表示客体名称； 2、A(b)为一元谓词，B(a,b)为二元谓词，L(a,b,c)是三元谓词，依次类推； 3、代表客体名称的字母，在多元谓词中出现次序与事先约定有关； 4、一元谓词表达客体“性质”，而多元谓词表示客体之间的“关系”； 5、谓词与谓词填式不是相同的概念。 谓词逻辑 2-2 命题函数与量词 为说明命题函数概念，举例说明命题与谓词的关系： 设H是谓词“总是要死的”，个体分别为：j-张三；t-老虎；c-椅 子。则对应命题为H(j), H(t), H(c) 。这些命题有一共同形式：“x总是 要死的”，即H(x)。则x称作客体变元,H(x)为命题函数。 定义2-2.1 由一个谓词，一些客体变元组成的表达式称为简单命 题函数。由一个或几个简单命题函数以及逻辑联结词组成的表达式 称之为复合命题函数。 注： 1、n元谓词就是有n个客体变元的命题函数，当n=0时，称之为0元 谓词，其本身就是命题，命题本身即为特殊的命题函数； 2、谓词逻辑中联结词与命题逻辑中的一致； 3、命题函数本身不是命题，仅有客体变元取特定名称时，才能为 命题；但客体变元在哪些的取值范围内取特定的值，对是否成为命 题及命题的真值有很大影响。 例1 R(x)：x是大学生 1：若x范围是某大学班级学生，则R(x)永真。 2：若x范围是某中学班级学生，则R(x)永假。 例2 (P(x,y) ∧P(y,z)) →P(x,z) 1：若P(x,y)为“x小于y”，当x,y,z均属实数域，则该表达式永真。 2：若P(x,y) 为“x为y的儿子”，当x,y,z指人时，则该表达式为：“若x 是y的儿子，且y是z的儿子，则x是z的儿子”，显然，该式永假。 在命题函数中，客体变元论述范围称作个体域，可 以为有限，也可以为无限。把各种个体域综合在一起作为 论述范围的域称为全总个体域。 为避免出现对日常生活中各种命题的理解混乱，现在来刻划 “所有的”和“存在一些”不同概念。 例 (a)所有的人都是要呼吸的。 (b)每个学生都要参加考试。 (c)任