,#,单击此处编辑母版标题样式,会计学,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,会计学,1,命题逻辑与谓词逻辑,会计学1命题逻辑与谓词逻辑,2.1,命 题 逻 辑,1,命题,定义,2-1,命题,：具有真假意义的语句。,定义,2-2,原子命题：,如果一个命题不能被进一步分解成更为简单的命题，则该命题就称为原子命题。,第1页/共47页,2.1 命 题 逻 辑 1命题第1页/共47页,2,连接词,：称为“非”或“否定”。,：称为“析取”，,P,Q,读作“,P,或,Q,”,。,：称为“合取”，,P,Q,读作“,P,与,Q,”,。,：称为“条件”。,P,Q,。,：称为“双条件”。,P,Q,“,P,当且仅当,Q,”,。,连接词优先级：，,第2页/共47页,2连接词第2页/共47页,3,合式公式,定义,2-3,合式公式（,Well-Formed Formula,，,WFF,）,孤立的命题变元或逻辑常量（,T,，,F,）是合式公式；,如果,A,是一个合式公式，则,A,也是一个合式公式；,如果,A,、,B,是合式公式，则,A,B,，,A,B,，,A,B,，,A,B,也都是合式公式；,当且仅当有限次使用规则后得到的公式才是合式公式。,第3页/共47页,3合式公式第3页/共47页,永真式（或重言式）,：给定一个公式，如果对于所有的真值指派，它的值都为真（,T,），则称该公式为永真式（或重言式）；,永假式（或称该公式为不可满足的）：,如对于所有的真值指派，它的值都为假（,F,），则称该公式为永假式（或称该公式为不可满足的）。,非永假的公式称为,可满足的公式,。,第4页/共47页,永真式（或重言式）：给定一个公式，如果对,4,等价和永真蕴涵,定义,2-4,等价,：设,A,，,B,是两个命题公式，,P,1,，,P,2,，,，,Pn,是出现在,A,、,B,中的所有命题变元。如果对于这,n,个变元的任何一个真值指派的集合，,A,和,B,的真值都相等，则称公式,A,等价于公式,B,，记作,A,B,。,“等价”又可定义为：,A,B,当且仅当,A,B,是一个永真式。,第5页/共47页,4等价和永真蕴涵第5页/共47页,定义,2-5,永真蕴涵,：命题公式,A,永真蕴涵命题公式,B,，当且仅当,A,B,是一个永真式，记作,A,B,，读作“,A,永真蕴涵,B,”,，简称“,A,蕴涵,B,”,。,第6页/共47页,定义2-5 永真蕴涵：命题公式A永真蕴,2.2,谓 词 逻 辑,1,谓词与个体,原子命题被分解为谓词和个体两部分。,个体,是指可以单独存在的事物，它可以是一个抽象的概念，也可以是一个具体的东西。,谓词,是用来刻画个体性质或个体间关系的词。,如：,POET(libai),POET(dufu),GREAT(libai,dufu),一般用大写字母表示谓词，小写字母表示个体。,第7页/共47页,2.2 谓 词 逻 辑1谓词与个体如：第7页/共47页,元数,:,谓词中包含的个体数目称为谓词的。,一元谓词,:,与一个个体相连的谓词，如,POET(,x,),；,多元谓词,:,与多个个体相连的谓词叫，如,GREAT(,x,y,)(,二元谓词,),。,个体域,:,任何个体的变化都有范围。,谓词变元命名式,:,一个,n,元谓词常被表示成,P,(,x,1,x,2,x,n,),。,第8页/共47页,元数:谓词中包含的个体数目称为谓词的。第8页/共,2,量词,全称量词,:“,(,x,),P,(,x,)”,表示命题“对个体域中所有的个体,x,，谓词,P,(,x,),均为,T”,。,存在量词,:“,(,x,),Q,(,x,)”,表示命题“在个体域中存在某个个体使谓词,Q,(,x,),为,T”,。其中“,”叫存在量词。,设,x,的取值范围是,甲，乙，丙,三人，,y,的取值范围是,bora,jetta,santana,三种车型。,(,x,)(,y,)LIKE(,x,y,),表示甲、乙、丙三人都喜爱,bora,jetta,santana,中的某一种车型；,(,x,)(,y,)LIKE(,x,y,),表示甲、乙、丙三人都喜爱,bora,jetta,santana,三种车型。,第9页/共47页,2量词设x的取值范围是甲，乙，丙三人，y的取值范,3,合式谓词公式,原子公式,:,若,P,为不能再分解的,n,元谓词变元，,x,1,x,2,x,n,是个体变元，则称,P,(,x,1,x,2,x,n,),为,原子公式,或,原子谓词公式,。当,n,=0,时，,P,表示,命题变元,或,原子命题公式,。所以命题逻辑是谓词逻辑的特例,第10页/共47页,3合式谓词公式第10页/共47页,定义,2-6,谓词合式公式,（简称,公式,）的定义如下：,原子公式是合式公式；,若,A,是合式公式，则,A,也是合式公式；,若,A,和,B,都是合式公式，则,(,A,B,),，,(,A,B,),，,(,A,B,),，,(,A,B,),也都是合式公式；,若,A,是合式公式，,x,是任意变元，且,A,中无,(,x,),或,(,x,),出现，则,(,x,),A,或,(,x,),A,也都是合式公式；,当且仅当有限次使用规则得到的公式是合式公式。,第11页/共47页,定义2-6 谓词合式公式（简称公式）的,4,量词的辖域与变元的约束,约束变元,自由变元,。,公式 约束变元 自由变元,(,x,),P,(,x,y,),x y,(,x,),Q,(,y,),无,y,(,x,)(,P,(,x,)(,y,),Q,(,x,y,),x,y,(,y,),P,(,x,),Q,(,x,),y x,第12页/共47页,4量词的辖域与变元的约束第12页/共47页,5,谓词公式的解释,谓词公式中的谓词变元、命题变元和自由个体变元，个体常量和函数的,一种指派就是一个解释。,在每一种解释下，谓词公式都具有一种真值（,T,或,F,）。,第13页/共47页,5谓词公式的解释第13页/共47页,定义,2-7,设,D,为谓词公式,P,的个体域，若对,P,中的个体常量、函数和谓词按照如下规定赋值：,（,a,）为每个个体常量指派,D,中的一个元素；,（,b,）为每个,n,元函数指派一个从,D,n,到,D,的映射，其中,D,n,=(,x,1,x,2,x,n,)|,x,1,x,2,x,n,D,（,c,）为每个,n,元谓词指派一个从,D,n,到,F,，,T,的映射；,则称这些指派为公式,P,在,D,上的一个解释,I,。,第14页/共47页,定义2-7 设D为谓词公式P的个体域，,例,2-1,给定公式,B,=(,x,)(,y,),P,(,x,y,),和个体域,D1,=1,，,2,。,求：公式,B,的解释及在该解释下,B,的真值。,解：,x,y,都可以取,D1,中的任何值，于是可有以下几种情况：,P,(1,1),，,P,(1,2),，,P,(2,1),，,P,(2,2),。,对这,4,个公式，每一个都可以指派真假（,T,，,F,）两个值，则共有,2,4,=16,个不同的组合，构成,16,个不同的解释。,第15页/共47页,例2-1 给定公式B=(x)(,P,(1,1),P,(1,2),P,(2,1),P,(2,2),I,1,T T T T,I,2,T T T F,I,3,T T F T,I,4,T T F F,I,5,T F T T,I,6,T F T F,I,7,T F F T,I,8,T F F F,I,9,F,T,T,T,I,10,F,T,T,F,I,11,F,T,F,T,I,12,F,T,F,F,I,13,F,F,T,T,I,14,F,F,T,F,I,15,F,F,F,T,I,16,F,F,F,F,如对,I,6,，则有,B,(,I,6)=T,。因为：对,x,=1,时，存在一个,y,=1,，有,P,(,x,y,)=,P,(1,1)=T,。对,x,=2,时，存在一个,y,=1,，有,P,(,x,y,)=,P,(2,1)=T,。所以在,I,6,解释下，公式,B,为真。,第16页/共47页,P(1,1)P(1,2),如,D,2,=1,，,2,，,3,根据上面的分析，在,D,2,上的解释应有,2,9,个。,下面是其中的一个解释：,I,:,P,(1,1),P,(1,2),P,(1,3),P,(2,1),P,(2,2),P,(2,3),P,(3,1),P,(3,2),P,(3,3),T,T,T,F,F,T,F,F,F,由于,x,=3,时，不存在一个,y,使,P,(,x,y,)=T,。所以在这个解释下公式,B,为假，即,B,(,I,)=F,。,第17页/共47页,如 D2=1，2，3第17页/共47页,例,2-2,给定公式,A,=(,x,)(,P,(,x,),Q,(,f,(,x,),a,),和个体域,D,=0,，,1,。公式中有个体常量,a,和一元函数,f,(,x,),，所以按定义可以如下构造对它的解释,I,1,：,（,a,）给个体常量,a,赋一个,D,中的元素如：,（,b,）给一元函数,f,(,x,),指派一个由,D,1,到,D,的映射，如：,第18页/共47页,例2-2 给定公式第18页/共47页,（,c,）对每个谓词符号指派一个由,D,1,到,F,，,T,的映射（对,P,(,x,),）或,D,2,到,F,，,T,的映射（对,Q,(,f,(,x,),a,),），如：,P,(0),P,(1),Q,(0,0),Q,(0,1),Q,(1,0),Q,(1,1),F,T,T,(T),F,(T),其中（,T,）表示不可能出现的状态，因为,a,已经取值,0,，不可能再取值,1,，所以不可能出现,Q,(0,1),或,Q,(1,1),这两种状态。,要考察在这个解释下公式,A,的真假，根据量词,(,x,),要对所有,x,进行考察。由于：对,x,=0,时，,P,(,x,),Q,(,f,(,x,),a,)=,P,(0),Q,(,f,(0),0)=,P,(0),Q,(1,0)=FF=T,对,x,=1,时,P,(,x,),Q,(,f,(,x,),a,)=,P,(1),Q,(,f,(1),0)=,P,(1),Q,(0,0)=TT=T,所以在此解释下，公式,A,为真，即,A,(,I,1,)=T,。,第19页/共47页,（c）对每个谓词符号指派一个由D1到F，T的映射（对P(,还可以在,D,上定义如下的解释,I,2,：,f,(0),f,(1),0,1,a,1,P,(0),P,(1),Q,(0,0),Q,(0,1),Q,(1,0),Q,(1,1),T,F,(T),F,(T),F,则当,x,=0,时，,P,(,x,),Q,(,f,(,x,),a,)=,P,(0),Q,(,f,(0),1)=,P,(0),Q,(0,1)=TF=F,当,x,=1,时，,P,(,x,),Q,(,f,(,x,),a,)=,P,(1),Q,(,f,(1),1)=,P,(1),Q,(1,1)=FT=T,所以在解释,I,2,下公式,A,为假，即,A,(,I,2,)=F,。,第20页/共47页,还可以在D上定义如下的解释I2：f(0)f(1,在上述个体域,D,上，公式,A,有多少种解释？,对,a,有两种解释，对,f,(,x,),有,2,2,种解释（,n,n,），对,P,(,x,),有,2,2,种解释（,2,n,），对,Q,(,f,(,x,),a,),有,2,2,种解释（,2,n,），则在,D,上，,A,共有,2,2,2,2,2,2,2,=2,7,种有意义的解释。,如果,D,中含有,n,个元素，则公式,A,的有意义解释的个数为：,n,n,n,2,n,2,n,=2,2,n,n,n,+1,将解释中各个值一一代入,P,(,x,),Q,(,f,(,x,),a,),中就可得出其真值。,第21页/共47页,在上述个体域D上，公式A有多少种解释？第21,定义,2-8,公式,B,是,相容,的（又叫可满足的或非永假的），当且仅当存在一个解释,I,，使得,B,在,I,下为,T,，即,B,相容（可满足）,(,I,),B,(,I,),这时就称,I,满足,B,，又称,