谓词演算（15节）课件

《谓词演算（15节）课件》由会员分享，可在线阅读，更多相关《谓词演算（15节）课件（20页珍藏版）》请在金锄头文库上搜索。

1、1,第二章.谓词演算 1.谓词 量词 2.合式公式 解释 可满足性 逻辑蕴涵 逻辑等价 替换定理 有效性 3.代入 代入定理 4.前束范式(PNF) 5.谓词演算的形式推理,2,1.谓词 量词,1.谓词与个体 (1)苏格拉底(Socrates) 论断 命题逻辑的基本单位，局限性 苏格拉底(Socrates) 论断：,凡人都是要死的,苏格拉底是人,所以苏格拉底是要死的。 注. 苏格拉底(Socrates，公元前469-399年):古希腊哲学家.西方三圣之一。 三段论是形式逻辑的一种最重要的推理形式。是逻辑之父亚里士多 德在他的代表著作工具论最早提出的。,(2)谓词(predicate) 命题是可

2、分辨真假的陈述语句 （形式逻辑）。 主语部分 + 谓语部分 主语(被陈述的对象,个体 )谓语 (陈述部分,谓词),3,在形式逻辑里,谓词就是谓语; 在数理逻辑里,个体是关系的定义域中的元素,个体之间的联系就是关系,称为谓词。,1.谓词 量词,个体(individual,object): 个体是谓词所描述的对象。用d表示。,论域(domain) ：由所讨论的个体(对象)组成的集合称为论域。 用表示。 注.论域也称为个体域(individual domain)。,个体常项 (individual constant) ：个体常项是取值于个体域上的常项。,个体变项 (individual variab

3、le) ： 个体变项是取值于个体域上的变项。 注.个体常项和个体变项统称为项(term)。,4,1.谓词 量词,一元谓词(unary predicate)： 一元谓词是描述一个个体的特征的谓词。通常称为性质 (nature,character,quaility)。 二元谓词(binary predicate)： 二元谓词是描述两个个体间的联系的谓词。通常称为(二元) 关系(binary)relation)。 三元谓词(binary predicate)： 三元谓词是描述三个个体间的联系的谓词。通常称为三元关 系(ternary relation)。 n元谓词(n-ary predicate)：

4、 n元谓词是描述n个个体间的联系的谓词。通常称为n元关系 (n-ary relation)。,5,1.谓词 量词,(3)形式化方法 个体常项符号 ： 表示个体常项,解释后为个体。用a,b,c表示。 个体变项符号： 表示个体变项,解释后为个体。用x,y,z,u,v,w表示。 n元谓词符号： 表示n元谓词,解释后为n元关系。用Pn,Qn,Rn表示。 当n=1时,为命题变项符号。表示命题变项,解释后为命题(即,命题是特殊的谓词)。用p,q,r表示。 当上下文已经指明时,可省略其上标, n元谓词记为P,Q,R。,(4)n元谓词的三种表示形式 谓词空位式 用n 个空位来表示n元谓词P为:P( _ , _

5、 , , _ ) 。,6,1.谓词 量词,谓词填式 设t1 , t2 , , tn是n个项, P(e1 , e2 , , en)是n元谓词P的命名式, 则P(t1 , t2 , , tn) 称为谓词填式。 若ti (1in)全是个体常项,则谓词填式P(t1 , t2 , , tn)表示命题。 例如 P(a,b,c) 表示一个命题。 若ti (1in)中有k个是个体变项,则谓词填式P(t1 , t2 , , tn)表 示k元命题函数。 例如 P(a,x,y) 表示一个二元命题函数。,谓词命名式 表示n元谓词P的谓词命名式为:P(e1 , e2 , , en) 其中: ei称为命名变项,代表第i个

6、空位(empty)。,7,1.谓词 量词,(5)形式化举例 例1.如果老张是小张的父亲,则小张是老张的儿子。 解.令:F(e1 , e2) e1是e2的父亲 S(e1 , e2) e1是e2的儿子 a老张 b小张 形式化: F(a , b)S(b , a) 。,例2.如果x是小张的父亲,而且y是小张的兄弟,则x也是y的父亲。 解.令:F(e1 , e2) e1是e2的父亲 B(e1 , e2) e1是e2的兄弟 a小张 形式化: F(x , a)B(y , a)F(x , y) 。,8,1.谓词 量词,例3.如果x+y0,而y+z0,则x+z0。 解.(a)令:G(e1 , e2) e1+e2

7、0 形式化: G(x , y)G(y , z)G(x , z) 。 (b)令:G(e1 , e2 , e3) e1+e2 e3 0 0 形式化: G(x , y , 0)G(y , z , 0) G(x , z , 0) 。,例4.如果x+y0,而y+z3,则x+z3。 解.令:G(e1 , e2 , e3) e1+e2 e3 0 0 3 3 形式化: G(x , y , 0)G(y , z , 3) G(x , z , 3) 。,9,1.谓词 量词,2.量词(quantifier) 量词是描述个体域的某些整体性质的词汇。,(1)全称量词(universal(generality) quant

8、ifier)： 描述个体域全体性质的词汇“对于每一个”，“所有的”，“凡是”，,统称为全称量词。记为 (for all)。 设(e)是个体域上的一个复合谓词,则表达式x(x)表示个体域上的全体性质。其中: 指导变项:全称量词x中的个体变项x。 辖域(scope):复合谓词(填式) (x)。辖域也称为作用域。 表达式x(x)可能表示命题,也可能表示命题函数(高一层次上的复合谓词)。 若表达式x(x) 表示命题，命题x(x)为真 对某个个体域,当个体变项x遍历上的每一个元素(个体)时,复合谓词(填式) (x)都为真。,10,1.谓词 量词,例5.(a)令: (e)=P(e,a)Q(e,b),则表达

9、式 x(x)=x(P(x,a)Q(x,b) 表示命题。 (b)令: (e)=P(e,a)Q(e,y)R(e,z),则表达式 x(x)=x(P(x,a)Q(x,y)R(x,z) 表示命题函数(新的复合谓词)。 (c )设:=N=0,1,2, 令: G(e1 , e2) e1e2 0 0, 2 2 则表达式 xG(0,x)表示真命题;表达式 xG(2,x)表示假命题。 (d)设:=I=,-2,-1,0,1,2, 令: 同上 但表达式 xG(0,x)却表示假命题;而表达式 xG(2,x)仍表示假命题。,11,1.谓词 量词,(2)存在量词(existential quantifier)： 描述个体域

10、存在性质的词汇“存在着某一个”，“至少有一个”，“有 些”， “有”，,统称为存在量词。记为 (there exists)。 设(e)是个体域上的一个复合谓词,则表达式x(x)表示个体域上的存 在性质。其中: 指导变项:存在量词x中的个体变项x。 辖域(scope):复合谓词(填式) (x)。辖域也称为作用域。 表达式x(x)可能表示命题,也可能表示命题函数(高一层次上的复合谓词)。 若表达式x(x) 表示命题,则 命题x(x)为真 对某个个体域,当个体变项x遍历上的元素(个体)时,有一个使得复合谓词(填式) (x)为真。,12,1.谓词 量词,例6.(a)令: (e)=P(e,a)Q(e,b

11、),则表达式 x(x)=x(P(x,a)Q(x,b) 表示命题。 (b)令: (e)=P(e,a)Q(e,y)R(e,z),则 x(x)= x(P(x,a)Q(x,y)R(x,z) 表示命题函数(新的复合谓词)。 (c )设:=N=0,1,2, 令: G(e1 , e2) e1e2 0 0, 2 2 xG(x, 0)表示假命题；表达式 xG(x, 2)表示真命题。 (d)设:=I=,-2,-1,0,1,2, 令: 同上 xG(x, 0)却表示真命题;而xG(x, 2)仍表示真命题。,13,1.谓词 量词,(e)设:=N=0,1,2, 令: G(e1 , e2) e1e2 yxG(x,y)表示命

12、题 xyG(x,y)表示命题,(3)形式化中多个论域的统一问题： (a)问题的提出: 对命题“每个人都拥有一张桌子”进行形式化, 令:P(e1 , e2) e1拥有e2, 形式化：xyP(x,y),拥有关系将会产生四种情况: 人拥有人;人拥有桌子;桌子拥有人;桌子拥有桌子。,问题：一个正确的命题,在混合论域上形式化。,14,1.谓词 量词,(c )特征谓词方法: 若所考虑的问题涉及若干个论域:1,2，,m,则将它们 并起来，形成一个理想的论域： =12 m 称为全总论域(或全总个体域)。 并对每个论域i 定义一个一元特征谓词: Pi(e):ei (1in) 用它来指明个体变项(或个体常项)属于

13、那一个论域。,(b)受囿量词方法: 实用上常采用受囿量词方法,又称为相对化量词方法。 命题“每个人都拥有一张桌子” 令:M=人,T=桌子,P(e1 , e2) e1拥有e2, 形式化为 (xM)(yT)P(x,y) 或 (x)M(y)TP(x,y) 。,15,1.谓词 量词,例：对命题“每个人都拥有一张桌子”进行形式化。 令:M=人，T=桌子，全总论域= M T ， M(e) e M (或e是一个人)， T(e) e T (或e是一张桌子)， P(e1 , e2) e1拥有e2 ， 形式化为 x(M(x)y(T(y)P(x,y)。,对于全称量词,应将特征谓词作为蕴涵前件放在该量词的辖域中; 对

14、于存在量词,应将特征谓词作为合取项放在该量词的辖域中。,16,(4)形式化举例 例7.著名的苏格拉底(Socrates) 三段论： 凡人都是要死的,苏格拉底是人,所以苏格拉底是要死的。 解.令:D(e) e是要死的 M(e) e是人 s苏格拉底 形式化: x(M(x)D(x)M(s)D(s) 。 这里：一元谓词M是特征谓词。该命题的全总论域=动物。,1.谓词 量词,17,1.谓词 量词,例8.离散数学是计算机系学生的必修课。即所有计算机系的学生都要学习离散数学。 解.(a)简单化: 令:C(e) e是计算机系的学生 D(e) e学习离散数学 形式化: x(C(x)D(x)。 这里：特征谓词，该

15、命题的全总论域。 (b)复杂化: 令:C(e) e是计算机系的学生 T(e) e是一门大学课程 D(e1 , e2) e1学习e2 d e是离散数学 形式化: T(d)x(C(x)D(x,d)。 这里：特征谓词，命题的全总论域。,18,1.谓词 量词,例9.尽管有些勤奋的人很聪明，但未必所有勤奋的人都很聪明。 解.令:D(e) e勤奋 C(e) e聪明 形式化: x(D(x)C(x)x(D(x)C(x) 。 这里：一元谓词D是特征谓词。命题的全总论域=人。,例10.半序集(P, )的子集Q中必有极大元。即Q中必有这样的元素，使得Q中任何元素都不比该元素大。 解.令:Q(e) eQ G(e1 , e2) e1e2 E(e1 , e2) e1= e2 形式化: x(Q(x)y(Q(y)G(x , y)E(x , y) 。 这里：一元谓词Q是特征谓词。命题的全总论域=P。,19,1.谓词 量词,例11.逻辑之父亚里士多德提出的形式逻辑著名的直言判断四大格式：A,E,I,O。其中: (a)全称肯定判断(SAP):凡S都是P; (b)全称否定判断(SEP):凡S都不是P; (c )特称肯定判断(SIP):有些S是P; (d)特称否定判断(SOP):有些S不是P。 解.令:S(e) e是S (或eS) P(e) e是P (或eP) 形式化: (a) x(S(x)P(x)。 (