多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 第二章 谓词逻辑 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 主要内容 谓词逻辑的基本概念 谓词公式 谓词逻辑等值式 谓词逻辑推理 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 命题逻辑的不足之处 命题逻辑研究的对象为命题(为一个完整的陈述句)，对于原子命题不可分。 例 鱼儿离不开水。 鲫鱼是鱼。 所以鲫鱼离不开水。 简单命题之间的内在联系需要通过进一步分析原子命题中主、谓等之间的关系。 个体 谓词 量词 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 个体 定义：可以独立存在的客观实体称为个体。 具体事物 抽象概念 例 小王和小明是同学。 a能被2整除。 x是有理数。 个体常项：表示具体或特定的个体，常用字母a,b,c...表示； 个体变项：表示抽象或泛指的个体，常用字母x,y,z...表示； 个体域：个体变项的取值范围，也称论域。 全总个体域：宇宙间一切事物组成的个体域。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词 定义：刻画个体具有的性质或个体之间关系的词。 谓词常项：表示具体性质或关系的谓词。 谓词变项：表示抽象的或泛指的谓词。 谓词符号通常用大写字母表示。 例： F：...和...是同学。 G：...能被...整除。 H：...是有理数。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词 元数：谓词中包含的个体变项数。含n个个体变项的谓词称为n元谓词。 0元谓词：不带个体变项的谓词。 命题均可以表示成0元谓词。 例： 4=3+1 如果2是素数，则3是素数。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 量词 定义：表示个体常项或变项之间数量关系的词。 全称量词：一切的、所有的、每一个、任意的、都...。符号化为“”。表示个体域里的所有个体关系。 存在量词：存在、有一个、有的、至少有一个...。符号化为“”。表示个体域里有的个体关系。 例 所有人都需要呼吸空气。 有的人没来上课。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 量词 量词需要注意个体域的问题。在不同的个体域内，命题的真值可能不同。 例：存在x，使得x+3=2。 个体域为自然数 个体域为整数 特性谓词：将某类个体从个体域中区分出来的谓词。 M(x)：x是人； F(x)：x是鱼； Z(x)：x是整数。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 命题符号化 明确命题个体域，分别找出个体常项、个体变项、量词和谓词； 按照命题的意思用逻辑联结词将其组合； 注意： 引入特性谓词时，全称量词的特性谓词作为命题的前提引入，而存在量词的特性谓词作为命题的合取项引入； 多个量词同时出现，需要注意量词的顺序不能随意颠倒。 例： 并非所有的人都爱看电视。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 一阶谓词的例 火车比汽车跑得快。 有理数可以表示成分数。 有的女孩不喜欢穿裙子。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词公式 谓词公式的符号集 个体常项：a,b,c,... 个体变项：x,y,z,... 函数符号：f,g,h,... 谓词符号：F,G,H,... 量词：, ; 联结词符号：¬,∧,∨,→,↔; 括号：),( 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词公式 谓词公式的项的递归定义 个体常项和个体变项是项； 若f(x1,x2,...,xn)是任意的n元函数，t1,t2,...,tn是任意n个项，则f(t1,t2,...,tn)是项； 所有的项都由有限次使用上述两条规定得到。 原子公式：设R(x1,x2,...,xn)是符号集上任意n元谓词，t1,t2,...,tn是符号集的任意n个项，则称R(t1,t2,...,tn)为原子公式。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 合式公式 定义 (1)原子公式是合式公式； (2)若A是合式公式，则(¬A)也是合式公式 (3)若A，B是合式公式，则(A∧B)，(A∨B)，(A→B)，(A↔B)也是合式公式； (4)若A是合式公式，则xA，xA也是合式公式； (5)只有有限次的应用(1)-(4)得到的符号串才是合式公式。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 约束变项及自由变项 定义： xF，xF中，x称为指导变项，F称为相应量词的辖域。辖域中x的所有出现称为约束出现，x称为约束变项，F中不是约束出现的其他变项称为自由变项。 例 x F(x)→y G(x,y) x(F(x,y)∧y(G(x,y)) xy(F(x,y)∧G(y,z))∨H(x,y) 闭式：若合式公式中无自由出现的个体变项，则称A为封闭的公式，简称闭式。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 变项替换规则 变项替换的目的：为了避免个体变项的混淆。 规则 约束变项换名规则：将量词辖域中出现的某个约束变项及其对应的指导变项改成公式中未出现的个体变项符号，其余部分不变。 自由变项代替规则：将公式中某自由变项用原公式中未出现过的某个个体变项符号代替，且处处代替。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词公式的解释 定义：为使公式成为真值确定的命题而指定的有关规定，称为谓词公式的一个解释。 解释I的组成 特定的个体域D D中一部分特定元素 D上每个函数变项所取得的具体函数 D上每个谓词变项所取的具体谓词 例： x(F(f(x))→G(x)) 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词公式的分类 谓词公式的分类： 如果A在任何解释下都为真，则称A为永真式（逻辑有效式）。 如果A在任何解释下都为假，则称A为永假式（矛盾式）。 若至少存在一组A的解释使A为真，则称A为可满足式。 代换实例：设A0是含命题变项p1,p2,...,pn的命题公式，A1,A2,...,An是n个谓词公式。用Ai代换A0中的每一个pi，所得的公式A称为A0的代换实例。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词公式的定理 定理： 命题公式中的重言式的代换实例在谓词公式中为逻辑有效式； 命题公式中的矛盾式的代换实例是谓词公式中仍为矛盾式。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词逻辑等值式 等值式的定义：设谓词逻辑中任意两个公式A和B，若A↔B是是逻辑有效式，则称A与B为等值式。记作AB。 原命题等值式的代换实例都是等值式。 消去量词等值式：设个体域D＝{a1,a2,...,an} xA(x)A(a1)∧A(a2)∧...∧A(an) xA(x)A(a1)∨A(a2)∨...∨A(an) 量词否定等值式 ¬xA(x) x¬A(x) ¬xA(x) x¬A(x) 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词逻辑等值式 量词辖域扩张和伸缩等值式 x(A(x)∨B)xA(x)∨B x(A(x)∨B)xA(x)∨B x(A(x)∧B)xA(x)∧B x(A(x)∧B)xA(x)∧B x(A(x)→B)xA(x)→B x(A(x)→B)xA(x)→B x(B→A(x))B→xA(x) x(B→A(x))B→xA(x) 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 谓词逻辑等值式 量词分配等值式 x(A(x)∧B(x))xA(x)∧xB(x) x(A(x)∨B(x))xA(x)∨xB(x) 量词交换等值式 xyA(x,y) yxA(x,y)  xyA(x,y) yxA(x,y) 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 前束范式 定义：设A为谓词逻辑公式，若A具有形式Q1x1Q2x2...QnxnB，其中Qi 为或 ，B为不含量词的公式。 存在定理：任何谓词逻辑公式都存在与之等值的前束范式。 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 前束范式 例： xF(x)→xG(x) (xF(x,y)→yG(y))→xH(x,y) 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 作业(1) P53 2.1 (2)(3)(4) P53 2.2 (2)(3) P53 2.3 (3)(4) P54 2.5 (1) 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn

多媒体中心 庄伯金 bjzhuang@bupt.edu.cn 作业(2) P54 2.7 (1) P54 2.11 (1)(2) P54 2.12 (2) P55 2.13 (2) P55 2.14 (2) 多媒体中心 庄伯金 bjzhuang@bupt.edu.cn