谓词演算(1-5节)-1.ppt

《谓词演算(1-5节)-1.ppt》由会员分享，可在线阅读，更多相关《谓词演算(1-5节)-1.ppt（20页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、 第二章第二章.谓词演算谓词演算 1.谓词谓词 量词量词 2.合式公式合式公式 解释解释 可满足性可满足性 逻辑蕴涵逻辑蕴涵 逻辑等价逻辑等价 替换定理替换定理 有效性有效性 3.代入代入 代入定理代入定理 4.前束范式前束范式(PNF)5.谓词演算的形式推理谓词演算的形式推理11.谓词谓词 量词量词1.谓词与个体谓词与个体(1)苏格拉底苏格拉底(SocratesSocrates)论断论断 命题逻辑的基本单位，局限性 苏格拉底(SocratesSocrates)论断：凡人都是要死的,苏格拉底是人,所以苏格拉底是要死的。注注.苏格拉底苏格拉底(SocratesSocrates，公元前，公元前46

2、9-399469-399年年):):古希腊哲学家古希腊哲学家.西方三圣之一。西方三圣之一。三段论三段论是是形式逻辑的一种最重要的推理形式。是逻辑之父形式逻辑的一种最重要的推理形式。是逻辑之父亚里士多亚里士多德德在他的代表著作工具论最早提出的。在他的代表著作工具论最早提出的。(2)谓词谓词(predicate)命题是可分辨真假的陈述语句（形式逻辑）。主语部分+谓语部分主语(被陈述的对象,个体)谓语(陈述部分,谓词)2在形式逻辑里,谓词就是谓语;在数理逻辑里,个体是关系的定义域中的元素,个体之间的联系就是关系,称为谓词。1.谓词谓词 量词量词个体个体(individual,object):个体是谓

3、词所描述的对象。用d表示。论域论域(domain)：由所讨论的个体(对象)组成的集合称为论域。用表示。注注.论域也称为论域也称为个体域个体域(individual domain)。个体常项个体常项 (individual constant)：个体常项是取值于个体域上的常项。个体变项个体变项 (individual variable)：个体变项是取值于个体域上的变项。注注.个体常项和个体变项统称为称为项项(term)。31.谓词谓词 量词量词一元谓词一元谓词(unary predicate)：一元谓词是描述一个个体的特征的谓词。通常称为性质(nature,character,quaility)。

4、二元谓词二元谓词(binary predicate)：二元谓词是描述两个个体间的联系的谓词。通常称为(二元)关系(binary)relation)。三元谓词三元谓词(binary predicate)：三元谓词是描述三个个体间的联系的谓词。通常称为三元关系(ternary relation)。n元谓词元谓词(n-ary predicate)：n元谓词是描述n个个体间的联系的谓词。通常称为n元关系(n-ary relation)。41.谓词谓词 量词量词 (3)形式化方法形式化方法 个体常项符号个体常项符号：表示个体常项,解释后为个体。用a,b,c表示。个体变项符号个体变项符号：表示个体变项,解

5、释后为个体。用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 个空位来表示n元谓词P为:P(_,_,_)。51.谓词谓词 量词量词谓词填式谓词填式 设t1,t2,tn是n个项,P(e1,e2,en)是n元谓词P的命名式,则P(t1,t2,tn)称为谓词填式。若ti(1in)全是个体常项,则谓词填式P(

6、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个空位(empty)。61.谓词谓词 量词量词(5)形式化举例形式化举例例例1 1.如果老张是小张的父亲,则小张是老张的儿子。解解.令:F(e1,e2)e1是e2的父亲 S(e1,e2)e1是e2的儿子 a老张 b小张 形式化:F(a,b)S(b,a)。例例2 2.如果x是小张的父亲,而且y是小张的

7、兄弟,则x也是y的父亲。解解.令:F(e1,e2)e1是e2的父亲 B(e1,e2)e1是e2的兄弟 a小张形式化:F(x,a)B(y,a)F(x,y)。71.谓词谓词 量词量词例例3.如果x+y0,而y+z0,则x+z0。解解.(a)令:G(e1,e2)e1+e20 形式化: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 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,

8、3)。81.谓词谓词 量词量词2.量词量词(quantifier)量词是描述个体域的某些整体性质的词汇。(1)全称量词全称量词(universal(generalitygenerality)quantifier)quantifier)：描述个体域全体性质的词汇“对于每一个”，“所有的”，“凡是”，,统称为全称量词。记为(for all)。设(e)是个体域上的一个复合谓词,则表达式x(x)表示个体域上的全体性质。其中:指导变项:全称量词x中的个体变项x。辖域(scope):复合谓词(填式)(x)。辖域也称为作用域。表达式x(x)可能表示命题,也可能表示命题函数(高一层次上的复合谓词)。若表达式x

9、(x)表示命题，命题x(x)为真 对某个个体域,当个体变项x遍历上的每一个元素(个体)时,复合谓词(填式)(x)都为真。91.谓词谓词 量词量词例例5.(a)令:(e)=P(e,a)Q(e,b),则表达式 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,令:同上 但表

10、达式 xG(0,x)却表示假命题;而表达式 xG(2,x)仍表示假命题。101.谓词谓词 量词量词(2)存在量词存在量词(existential quantifierexistential quantifier)：描述个体域存在性质的词汇“存在着某一个”，“至少有一个”，“有些”，“有”，,统称为存在量词。记为(there exists)。设(e)是个体域上的一个复合谓词,则表达式x(x)表示个体域上的存在性质。其中:指导变项:存在量词x中的个体变项x。辖域(scope):复合谓词(填式)(x)。辖域也称为作用域。表达式x(x)可能表示命题,也可能表示命题函数(高一层次上的复合谓词)。若表达式

11、x(x)表示命题,则 命题x(x)为真 对某个个体域,当个体变项x遍历上的元素(个体)时,有一个使得复合谓词(填式)(x)为真。111.谓词谓词 量词量词例例6.(a)令:(e)=P(e,a)Q(e,b),则表达式 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

12、)却表示真命题;而xG(x,2)仍表示真命题。121.谓词谓词 量词量词 (e)设:=N=0,1,2,令:G(e1,e2)e1e2 yxG(x,y)表示命题 xyG(x,y)表示命题(3)形式化中形式化中多个论域的统一问题多个论域的统一问题：(a)问题的提出问题的提出:对命题“每个人都拥有一张桌子”进行形式化,令:P(e1,e2)e1拥有e2,形式化：xyP(x,y)拥有关系将会产生四种情况:人拥有人;人拥有桌子;桌子拥有人;桌子拥有桌子。问题：一个正确的命题,在混合论域上形式化。131.谓词谓词 量词量词(c)特征谓词方法特征谓词方法:若所考虑的问题涉及若干个论域:1,2，,m,则将它们并起

13、来，形成一个理想的论域：=12 m 称为全总论域(或全总个体域)。并对每个论域i 定义一个一元特征谓词:Pi(e):ei (1in)用它来指明个体变项(或个体常项)属于那一个论域。(b)受囿量词方法受囿量词方法:实用上常采用受囿量词方法,又称为相对化量词方法。命题“每个人都拥有一张桌子”令:M=人,T=桌子,P(e1,e2)e1拥有e2,形式化为(xM)(yT)P(x,y)或(x)M(y)TP(x,y)。141.谓词谓词 量词量词例：对命题“每个人都拥有一张桌子”进行形式化。令:M=人，T=桌子，全总论域=M T，M(e)e M(或e是一个人)，T(e)e T(或e是一张桌子)，P(e1,e2

14、)e1拥有e2，形式化为 x(M(x)y(T(y)P(x,y)。对于全称量词,应将特征谓词作为蕴涵前件放在该量词的辖域中;对于存在量词,应将特征谓词作为合取项放在该量词的辖域中。15(4)形式化举例形式化举例例例7.著名的苏格拉底(SocratesSocrates)三段论：凡人都是要死的,苏格拉底是人,所以苏格拉底是要死的。解解.令:D(e)e是要死的 M(e)e是人 s苏格拉底 形式化:x(M(x)D(x)M(s)D(s)。这里：一元谓词M是特征谓词。该命题的全总论域=动物。1.谓词谓词 量词量词161.谓词谓词 量词量词例例8.离散数学是计算机系学生的必修课。即所有计算机系的学生都要学习离

15、散数学。解解.(a)简单化:令:C(e)e是计算机系的学生 D(e)e学习离散数学 形式化:x(C(x)D(x)。这里：特征谓词，该命题的全总论域。(b)复杂化:令:C(e)e是计算机系的学生 T(e)e是一门大学课程 D(e1,e2)e1学习e2 d e是离散数学形式化:T(d)x(C(x)D(x,d)。这里：特征谓词，命题的全总论域。171.谓词谓词 量词量词例例9.尽管有些勤奋的人很聪明，但未必所有勤奋的人都很聪明。解解.令:D(e)e勤奋 C(e)e聪明 形式化:x(D(x)C(x)x(D(x)C(x)。这里：一元谓词D是特征谓词。命题的全总论域=人。例例1010.半序集(P,)的子集

16、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。181.谓词谓词 量词量词例例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)形

17、式化:(a)x(S(x)P(x)。(b)x(S(x)P(x)。(c)x(S(x)P(x)。(d)x(S(x)P(x)。例子例子2191.谓词谓词 量词量词注注.一般直言判断由四部分组成:量项,主项,联项,谓项。量项就是量词。主项是反映判断中的思想对象,通常记为S(拉丁文subjectum)。联项是连词,直言判断的连词为“是”或“不是”。谓项是反映判断中思想对象具有或不具有的性质,通常记为P(拉丁文praedicatum)。四大格:A,E,I,O的含义如下:A为拉丁文affirmo的第一个元音字母,意指“我肯定”;E为拉丁文nego的第一个元音字母,意指“我否定”;I为拉丁文affirmo的第二个元音字母,意指“我肯定(特定的)”;O为拉丁文nego的第二个元音字母,意指“我否定(特定的)”。四大格:A,E,I,O可衍生出关系格16种(内),三段论格64种(内)。这节的内容实际上是从形式逻辑到数理逻辑的过渡。20