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

《苏州大学离散数学-谓词逻辑》由会员分享，可在线阅读，更多相关《苏州大学离散数学-谓词逻辑（30页珍藏版）》请在金锄头文库上搜索。

1、第二章 谓词逻辑由第一章命题逻辑的学习了解到：命题逻辑主要研 究命题和命题演算，研究的基本单位是原子命题，并认为 原子命题不能再分解，但进一步研究发现，某些情况下必 须对原子命题进行再次分析，否则某些推理无法用命题逻 辑表示。如著名的“苏格拉底三段论”：所有的人都是要死的， 苏格拉底是人，所以苏格拉底总是要死的。直觉判断该结 论是真，但在命题逻辑中无法解决。故必须对原子命题的 成分，结构和命题间的共同属性等作进一步分析，而这正 是本章“谓词逻辑” 研究的主要内容。 谓词逻辑又称一阶谓词逻辑，狭谓词逻辑，初等逻 辑或量词理论等。谓词逻辑(主要内容)2-1谓词的概念及表示 2-2命题函数与量词 2

2、-3谓词公式与翻译 2-4变元的约束 2-5谓词演算的等价式与蕴含式 2-6前束范式 2-7谓词演算的推理理论2-1 谓词的概念与表示命题是反映判断的句子，具有真假意义；一般情况下，反映判 断的句子是由主语和谓语两部分组成。如“电子计算机是科学计算的工具”，其中“电子计算机” 是主语，又叫客体（或个体），可独立存在，即可以是具体的，又 可以是抽象的。 “是科学计算的工具”是谓语，又叫谓词，用以刻划客体的性 质和关系。 如：张三是个大学生，李四是个大学生。 此两命题可用两个不同的符号：P、Q来表示。但它们具有相 同属性，即“是个大学生”。故引入一符号表示“是个大学生”，再引 入一种方法表示客体名

3、称，则能把“是个大学生”命题本质属性 刻划出来。又如 (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：在与 之中。 单独一个谓词不是完整的命题。把谓词字母填以客体所得的 式子称为谓词填式

4、。 一般，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-椅 子。则对

5、应命题为H(j), H(t), H(c) 。这些命题有一共同形式：“x总是 要死的”，即H(x)。则x称作客体变元,H(x)为命题函数。 定义2-2.1由一个谓词，一些客体变元组成的表达式称为简单命 题函数。由一个或几个简单命题函数以及逻辑联结词组成的表达式 称之为复合命题函数。 注： 1、n元谓词就是有n个客体变元的命题函数，当n=0时，称之为0元 谓词，其本身就是命题，命题本身即为特殊的命题函数； 2、谓词逻辑中联结词与命题逻辑中的一致； 3、命题函数本身不是命题，仅有客体变元取特定名称时，才能为 命题；但客体变元在哪些的取值范围内取特定的值，对是否成为命 题及命题的真值有很大影响。例1R

6、(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)所有的人

7、都是要呼吸的。 (b)每个学生都要参加考试。 (c)任何整数或是正的或是负的。 均表示“对所有的”概念，为此引入符号(x ) 来表达“对所有的x”。 若设： M(x)：x是人，H(x)：x是要呼吸的，P(x)：x是学生， Q(x)：x是要参加考试的，I(x)：x是整数，R(x)：x是正数，N(x)：x是负数。 则上述例子记作： (a) (x)(M(x) H(x) (b) (x)(P(x) Q(x) (c) (x)(I(x) (R(x)N(x)符号“ ”为全称量词，来表达“对所有的”、“每一个”、“对任一 个”等。另外还有一类量词记作(x)，表示“存在一些x”。 例(a)存在一个数是质数。 (b

8、)一些人是聪明的。 (c)有些人早上喝豆浆。 设 P(x)：x是质数；M(x)：x是人；R(x)：x是聪明的；E(x)：x早上 喝豆浆。上述例子可表示为： (a)(x)P(x)； (b)(x)(M(x) R(x) (c)(x)(M(x) E(x) 符号“”称作存在量词，可用来表达“存在一些”、“至少一些”、“对 于一些”等。 注： 1、全程量词与存在量词通称为量词。 2、在不加以说明的条件下谓词逻辑中使用全总个体域。使用全总个体域，对每一个客体变元的变化范围，可以用特性谓词加以限制。一般地，对“”，此特性谓词常作蕴含前件；对“”，特性谓词常作合取项。如在全总个体域中：M(x)：x是人，H(x)

9、：x是要呼吸的。(x)H(x) 可写成 (x)(M(x) H(x) 其中M(x)为H(x)的特性谓词。(x)H(x) 可写成 (x)(M(x) H(x)，M(x)为特性谓词,限定了H(x)中变元范围 。谓词逻辑2-3 谓词公式与翻译通过谓词与量词，谓词表达式能够深入刻划日常命题。但怎 样的谓词表达式才能称为谓词公式并能进行谓词演算呢？下面介绍 谓词的谓词合式公式。 A(x1,x2, ,xn) 称作谓词演算的原子公式，其 中x1,x2, ,xn是客体变元，故原子谓词公式有下述特例：Q, A(x), A(x,y), A(f(x),y) 定义2-3.1谓词演算的合式公式，可由下述各条组成： (1)原

10、子谓词公式是合式公式。 (2)若A是合式公式，则A是一个合式公式。 (3)若A和B都是合式公式，则A B, A B，A B，A B 是合式公式。 (4)若A是合式公式，x是A中出现的任何变元，则(x)A 和(x)A 都是合式公式。 (5)只有经过有限次地应用规则(1)、(2)、(3)、(4)所得到的公式均是合式公式。例1尽管有人聪明，但未必一切人都聪明 解：设 P(x)：x很聪明M(x)：x是人x(M(x)P(x)(x(M(x)P(x) 例2这只大红书柜摆满了那些古书 解1：设F(x,y)：x摆满了y 解2：设A(x)：x是书柜 R(x)：x是大红书柜 B(x)：x是大的 Q(y)：y是古书

11、C(x)：x是红的 a：这只 b：那些 D(y)：y是古老的 R(a) Q(b) F(a,b) E(y)：y是图书F(x,y)：x摆满了ya：这只 b：那些A(a) B(a) C(a) D(b) E(b) F(a,b) 注： 1、谓词合式公式简称谓词公式； 2、谓词公式最外层的括号可以省略，但量词后面的非原子谓词公式的括号则 不能省略； 3、命题翻译成谓词演算公式，根据对个体描述性质的刻划深度不同，则可翻 译成不同形式的谓词公式。 谓词逻辑2-4 变元的约束谓词公式 有一部分形式为(x)P(x) 或(x)P(x) 。这里 , 后面所跟 的 x 叫做量词的指导变元或作用变元，P(x) 叫做相应量

12、词的作用域或辖域。 在作用域中 x 的一切出现，称为 x 在 中的约束出现, x 亦称为被相应量词中 的指导变元所约束。在 中除去约束变元以外所有出现的变元称作自由变元。 由于自由变元不受约束，故其可以看作公式中的参数。 例1a) (x) (y)(P(x,y)Q(y,z)(x)P(x,y) b) (x)(P(x)(x)Q(x,z)(y)R(x,y)Q(x,y)解：a)(x) 和(y) 的作用域是P(x,y) Q(y,z)，其中 x,y 是约束变元 ， z 是自由变元。(x) 的作用域是P(x,y)，其中 x 是约束变元, y 是自由变元。在整 个公式中, x 是约束出现, y 既是约束出现又是

13、自由出现, z 是自由出 现。 b) (x) 的作用域是P(x)(x)Q(x,z) (y)R(x,y) ，x 和 y 都是约束变 元，但Q(x,z) 中的 x 是受 (x) 的约束，而不是受(x) 的约束。 Q(x,y) 的 x,y 是自由变元。从约束变元概念可知, P(x1,x2, ,xn)是 n 元谓词，有 n 个相互独 立的自由变元，若对其中 k 个变元进行约束则成为 n-k 元谓词，故 谓词公式中没有自由变元时即可成为一个命题，P为谓词常量。 为避免自由变元与约束变元同时出现，可对公式中的约束 变元更改名称符号，这种遵守一定规则的更改，称为约束变元的换 名。 其规则为： (1)对于约束

14、变元可以换名，其更改的变元名称范围是量词中的指导 变元，以及该量词作用域中所出现的该变元，在公式的其余部分不 变。 (2)换名时一定要更改为整个公式中没有出现的变元名称。 例2对(x)(P(x) R(x,y)Q(x,y) 换名。 解可换名为： (z)(P(z)R(z,y)Q(x,y) ， 但不能改为：(y)(P(y)R(y,y)Q(x,y) 和(z)(P(z)R(x,y)Q(x,y) 因为这两种更改都对公式中量词约束范围有所改变。对于公式中自由变元也允许进行更改，这种更改叫做代入，亦 需遵循一定规则： (1)对于谓词公式中的自由变元可作代入，此时需对公式中出现该自 由变元的每一处进行。 (2)

15、用以代入的变元与原公式中所有变元的名称不能相同。 例3对(x)(P(y)R(x,y) 代入 解对 y 施行代入得： (x)(P(z)R(x,z) 。但是 (x)(P(x)R(x,x) 与 (x)(P(z)R(x,y) ， 这两种代入都是与规则不符。 需要指出：量词作用域中约束变元，当论域中元素有限时，客体变元 所有可能的取代可枚举。 设论域元素为： a1,a2, ,an 。 则 (x)A(x) A(a1)A(a2) A(an) (x)A(x) A(a1)A(a2)A(an)量词对变元约束与量词的次序有关。如： (y)(x)(xy-2) 表示 任何y 均有 x ，使得 xy-2。对于多个量词约定从左到右次序读出， 不能颠倒。谓词逻辑2-5 谓词演算的等价式与蕴含式定义2-5.1给定任意谓词公式wff A和wff B，设其具有共 同个体域E，若对A和B的任一组变元进行赋值，所