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

1第二章.谓词演算§1.谓词量词§2.合式公式解释可满足性逻辑蕴涵逻辑等价替换定理有效性§3.代入代入定理§4.前束范式(PNF)§5.谓词演算的形式推理2§1.谓词量词1.谓词与个体(1)苏格拉底(Socrates)论断–命题逻辑的基本单位，局限性–苏格拉底(Socrates)论断：凡人都是要死的,苏格拉底是人,所以苏格拉底是要死的。注.苏格拉底(Socrates，公元前469-399年):古希腊哲学家.西方三圣之一。三段论是《形式逻辑》的一种最重要的推理形式。是逻辑之父亚里士多德在他的代表著作《工具论》最早提出的。(2)谓词(predicate)命题是可分辨真假的陈述语句（形式逻辑）。主语部分+谓语部分主语(被陈述的对象,个体)谓语(陈述部分,谓词)3在形式逻辑里,谓词就是谓语;在数理逻辑里,个体是关系的定义域中的元素,个体之间的联系就是关系,称为谓词。§1.谓词量词个体(individual,object):个体是谓词所描述的对象。用d表示。论域(domain)：由所讨论的个体(对象)组成的集合称为论域。用表示。注.论域也称为个体域(individualdomain)。个体常项(individualconstant)：个体常项是取值于个体域上的常项。个体变项(individualvariable)：个体变项是取值于个体域上的变项。注.个体常项和个体变项统称为项(term)。4§1.谓词量词一元谓词(unarypredicate)：一元谓词是描述一个个体的特征的谓词。通常称为性质(nature,character,quaility)。二元谓词(binarypredicate)：二元谓词是描述两个个体间的联系的谓词。通常称为(二元)关系((binary)relation)。三元谓词(binarypredicate)：三元谓词是描述三个个体间的联系的谓词。通常称为三元关系(ternaryrelation)。n元谓词(n-arypredicate)：n元谓词是描述n个个体间的联系的谓词。通常称为n元关系(n-aryrelation)。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(_,_,,_)。6§1.谓词量词谓词填式设t1,t2,,tn是n个项,P(e1,e2,,en)是n元谓词P的命名式,则P(t1,t2,,tn)称为谓词填式。若ti(1in)全是个体常项,则谓词填式P(t1,t2,,tn)表示命题。例如P(a,b,c)表示一个命题。若ti(1in)中有k个是个体变项,则谓词填式P(t1,t2,,tn)表示k元命题函数。例如P(a,x,y)表示一个二元命题函数。谓词命名式表示n元谓词P的谓词命名式为:P(e1,e2,,en)其中:ei称为命名变项,代表第i个空位(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+y0,而y+z0,则x+z0。解.(a)令:G(e1,e2)—e1+e20形式化:G(x,y)G(y,z)G(x,z)。(b)令:G(e1,e2,e3)—e1+e2e30—0形式化:G(x,y,0)G(y,z,0)G(x,z,0)。例4.如果x+y0,而y+z3,则x+z3。解.令:G(e1,e2,e3)—e1+e2e30—03—3形式化:G(x,y,0)G(y,z,3)G(x,z,3)。9§1.谓词量词2.量词(quantifier)量词是描述个体域的某些整体性质的词汇。(1)全称量词(universal(generality)quantifier)：描述个体域全体性质的词汇“对于每一个”，“所有的”，“凡是”，,统称为全称量词。记为(forall)。设(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),则表达式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)—e1e20—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)存在量词(existentialquantifier)：描述个体域存在性质的词汇“存在着某一个”，“至少有一个”，“有些”，“有”，,统称为存在量词。记为(thereexists)。设(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),则表达式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)—e1e20—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)—e1e2yxG(x,y)表示命题xyG(x,y)表示命题(3)形式化中多个论域的统一问题：(a)问题的提出:对命题“每个人都拥有一张桌子”进行形式化,令:P(e1,e2)—e1拥有e2,形式化：xyP(x,y)‘拥有关系’将会产生四种情况:人拥有人;人拥有桌子;桌子拥有人;桌子拥有桌子。问题：一个正确的命题,在混合论域上形式化。14§1.谓词量词(c)特征谓词方法:若所考虑的问题涉及若干个论域:1,2，,m,则将它们并起来，形成一个理想的论域：=12m称为全总论域(或全总个体域)。并对每个论域i定义一个一元特征谓词:Pi(e):ei(1in)用它来指明个体变项(或个体常项)属于那一个论域。(b)受囿量词方法:实用上常采用受囿量词方法,又称为相对化量词方法。命题“每个人都拥有一张桌子”令:M={人},T={桌子},P(e1,e2)—e1拥有e2,形式化为(xM)(yT)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)))。对于全称量词,应将特征谓词作为蕴涵前件放在该量词的辖域中;对于存在量词,应将特征谓词作为合取项放在该量词的辖域中。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))。这里：特征谓词，该命题的全总论域。(b)复杂化:令:C(e)—e是计算机系的学生T(e)—e是一门大学课程D(e1,e2)—e1学习e2d—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)—eQG(e1,e2)—e1≼e2E(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(或eS)P(e)—e是P(或eP)形式化:(a)x(S(x)P(x))。(b)x(S(x)P(x))。(c)x(S(x)P(x))。(d)x(S(x)P(x))。例子例子220§1.谓词量词注.一般直言判断由四部分组成:量项,主项,联项,谓项。量项就是量词。主项是反映判断中的思想对象,通常记为S(拉丁文subjectum)。联项是连词,直言判断的连词为“是”或“不是”。谓项是反映判断中思想对象具有或不具有的性质,通常记为P(拉丁文praedicatum)。四大格:A,E,I,O的含义如下:A为拉丁文affirmo的第一个元音字母,意指“我肯定”;E为拉丁文nego的第一个元音字母,意指“我否定”;I为拉丁文affirmo的第二个元音字母,意指“我肯定(特定的)”;O为拉丁文nego的第二个元音字母,意指“我否定(特定的)”。四大格:A,E,I,O可衍生出关系格16种(内),三段论格64种(内)。这节的内容实际上是从形式逻辑到数理逻辑的过渡。