离散数学L3_1.pdf

第3章一阶谓词逻辑演算系统 主要内容： 1）一阶谓词基本概念 2）自然语句的形式化 3）一阶谓词演算形式系统FC：组成、 公理、推理规则、定理 4）一阶谓词形式系统的语义 5）FC的性质定理 §3.1 一阶谓词基本概念 引言：为什么要引入谓词？ 命题逻辑中对客观命题（知识）的描 述过于简单，体现不出研究个体的特 性和共性，通过引入谓词来表达研究 对象（个体）性质或研究对象之间的 关系。 例1 描述哈工大学生： 1）张三是哈工大学生。 2）李四是哈工大学生。 例2 1）人终究会死的； 2）苏格拉底是人； 3）所以苏格拉底终究会死的。 例3 1）所有实数的平方都是非负的； 2）-3是一个实数； 3）所以-3的平方是非负的。 1.谓词：表示研究对象（或个体）的性质 或对象之间关系的词称为谓词。 常用大写字母表示。 一元谓词：仅含有一个变元的谓词。 n元谓词：含有n个变元的谓词。 例4 P(x)：x是有理数 P(3)：3是有理数 G(x,y)：实数x比实数y大。 2.个体词：研究的对象，分为个体常元 与个体变元。 常用字母表靠后的字母表示个体变元， 靠前的字母表示个体常元。 如例4中的x为个体变元，3为个体常元。 3.个体域（论域）：个体变元的取值范 围。通常用D表示。 4.函词：用于描述从一个个体域到另一 个个体域的映射。 注：同基本意义上的函数定义，作为谓 词的一部分，常用小写字母或小写英文 单词来表示。 例 P(x)：x是工程师 张三的父亲是工程师P(father(张三)) father(x):x的父亲 5.量词：用于限制个体词的数量。 1）全称量词():表任意的，从量上表 示“所有的”。 例：xP (x) ：表示对任意的x均有性 质或关系P 2）存在量词():表存在的，从量上表 示“至少有一个”。 例: xP (x) :表示至少存在一个x具有 性质或关系P。 全称量词与存在量词关系： xP xP xP xP xyP y xP xyP y xP 6.约束变元与自由变元 1)约束变元：受量词约束的个体变元. 例 xP (x), xQ (x) 2)自由变元：不受量词约束的个体变元. 例 xP (x) Q(y ) 7.辖域：量词所约束的范围. y [xP (x,y )] Q(y ) 例： 8.易名规则： xP (x) yP (y ), xP (x) yP (y ) 1)待改名的变元在其辖域内的此变 元应均改掉，其余不变. 2)修改后的变元符不应该已在该量 词的辖域内出现. 例 R(x,y ,z) xQ(x,y ) yP (y ) 则变元x，y既为自由变元又为约束 变元，易混淆故改名： R(x,y ,z) vQ(v,y ) uP(u) 9.项 1)个体变元(常元)是项； f 2）若 是一个 元函词， n t ,t ,,t 为项， 1 2 n 则 f (t ,t ,,t )是项.