L2命题逻辑2 离散数学

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Lu Chaojun, SJTU,*,命题逻辑,二,Lu,Chaojun, SJTU,2,2,主要内容,命题与命题联结词,命题公式,等值演算,命题公式的范式,联结词的功能完全集,永真蕴涵式,命题逻辑推理,Lu,Chaojun, SJTU,3,等值关系,一种重要的数学论证方法是,:,将一个命题用另一个等值命题替换,.,两个命题公式,A,和,B,若在任一赋值下的真值都相同, 则称,A,和,B,等值,(,equivalence,).,记作,A,B,.,例如,:,a,b,(,a,),b,这两个公式语法上是不同的,但语义上相同,.,Lu,Chaojun, SJTU,4,与,的关系,等值定理,:,对公式,A,和,B,A,B,iff,A,B,是永真式,证明,:,若,A,B,永真,则在任一赋值下其真值都为,1,依,的定义知,A,和,B,真值相同,.,若,A,B,则在任一赋值下,A,和,B,都有相同的真值,依,的定义即,A,B,真值为,1.,注,:,教材中干脆用此关系作为等值的定义,.,Lu,Chaojun, SJTU,5,与,的不同,从形式系统角度看,是系统内的符号,A,B,是系统内的命题公式,.(,语法,),是,系统外的符号,A,B,不是命题公式,!,在系统外观察系统内两个公式是否等值,.(,语义,),从真假性来看,A,B,是表示,A,和,B,是否,等值的一个命题,.,只有,A,B,为真,才肯定,A,和,B,等值,.,但,A,B,可为假,.,A,B,则肯定地表示,A,和,B,等值,.,Lu,Chaojun, SJTU,6,补充,:,等值关系,的性质,和数学里的等号一样,具有下面三个性质,:,1.自反性,:,A,A,2.,对称性,:,若,A,B,则,B,A,3.,传递性,:,若,A,B,且,B,C,则,A,C,这三条性质刻画了两事物,“,等同,”,、,“,同一性,”,概念,.,满足这三条性质的关系称为,等价关系,.,在等值概念下,命题常量可看成只有两个,:1,0,6,Lu,Chaojun, SJTU,7,如何证明两公式等值,?,真值表技术,利用等值定理,利用基本等值式进行等值演算,7,Lu,Chaojun, SJTU,8,例,:,利用真值表证明等值,证明(,a,a,),b,b,.,证,:,列出真值表即可看出等式成立,.,a,b,a,a,(,a,a,),b,0,0,0,0,0,1,0,1,1,0,0,0,1,1,0,1,Lu,Chaojun, SJTU,9,例,:,利用等值定理证明等值,证明,(,a,b,),(,a,b,).,根据等值定理,可转化为证明,(,a,b,),(,a,b,),是永真式,.,比如列出此公式的真值表,.,这样本质上还是真值表技术,.,还可利用重言式推理系统,.,9,Lu,Chaojun, SJTU,10,基本等值式,1.,结合律,(,A,B,),C,A,(,B,C,),(,A,B,),C,A,(,B,C,),(,A,B,),C,A,(,B,C,),2,. 交换律,A,B,B,A,A,B,B,A,A,B,B,A,注意,:,没有,的结合律和交换律,.,Lu,Chaojun, SJTU,11,基本等值式,(,续,),3.,分配律,A, (,B,C,),(,A,B,), (,A,C,),A, (,B,C,),(,A,B,), (,A,C,),A,(,B,C,),(,A,B,),(,A,C,),4.,吸收律,A, (,A,B,),A,A, (,A,B,),A,Lu,Chaojun, SJTU,12,基本等值式,(,续,),5.,关于否定词的等值式,(,A,),A,(,对合律,),(,A,B,),A, ,B,(,De Morgan,律,),(,A,B,),A, ,B,(,De Morgan,律,),(,A,B,),A,B,(,A,B,),A,B,A, ,B,(,A, ,B,),(,A,B,),基本等值式,(,续,),6,.相同命题变量的等值式,A,A,A,(,等幂律,),A,A,A,(,等幂律,),A,A,1,A,A,1,A, ,A,1 (,排中律,),A, ,A,0 (,矛盾律,),A, ,A,A,A,A,A,A, ,A,0,此处的,1/0,代表任意真值恒为,1/0,的命题公式,.,Lu,Chaojun, SJTU,13,Lu,Chaojun, SJTU,14,基本等值式,(,续,),7,.部分赋值的等值式,A,0,A,A, 1,A,1,A,A,A,0,A,1,A,A,0,A,A,A,1,1,A,0,0,A,1,1,0,A,1,14,Lu,Chaojun, SJTU,15,基本等值式,(,续,),8.,关于,的等值式,A,B,(,A,),B,(,A, ,B,),A,B,B, ,A,假言易位,A,(,B,C,),(,A,B,),C,合取前提,A,(,B,C,),B,(,A,C,) ,交换前提,(,A,C,),(,B,C,),(,A,B,),C,析取前提,(,A,B,),(,A, ,B,),A,归谬论,A,(,B,C,),(,A,B,), (,A,C,),A,(,B,C,),(,A,B,), (,A,C,),基本等值式,(,续,),9.,关于,的等值式,A,B,A,B,A,B,(,A,B,),(,A,B,) ,同真或同假,A,B,(,A,B,),(,A,B,) ,一真一假,A,B,(,A,B,),(,B,A,) ,充分必要,由于,更易理解和处理,常利用,8,和,9,类的等值式将含,和,的公式改写成仅含有,的公式,.,Lu,Chaojun, SJTU,16,置换规则,定理,:,设,A,A,B,B,则有,(1),A,A,(2),A,B,A,B,(3),A,B,A,B,(4),A,B,A,B,(5),A,B,A,B,置换,:,将公式的一部分用等值公式替换,.,定理,(,置换规则,):,设,B,C.,若将,A,中出现的一个或几个,B,换成,C,后得到公式,A,则有,A,A,.,Lu,Chaojun, SJTU,17,Lu,Chaojun, SJTU,18,等值演算,等值演算,:,利用等值定律,基本等值式以及替换规则进行公式推演,.,一般是将,两边的公式推演成相同形状的公式,从而证明等值式成立,.,例,:,等值演算,证明(,a,(,b,c,),(,b,c,),(,a,c,),c,.,证明:左端,(,a,(,b,c,),(,b,a,),c,),(,分配律),(,(,a,b,),c,),(,b,a,),c,),(,结合律),(,(,a,b,),c,),(,b,a,),c,) (,德摩根律),(,(,a,b,),(,b,a,),c,(,分配律),(,(,a,b,),(,a,b,),),c,(,交换律),1,c,(,置换),c,Lu,Chaojun, SJTU,19,Lu,Chaojun, SJTU,20,对偶式和内否式,观察下面两个等值式,(,分配律,):,A, (,B,C,),(,A,B,), (,A,C,),A, (,B,C,),(,A,B,), (,A,C,),可见,命题逻辑公式存在,“,对偶,”,规律,.,限制性公式,:,公式中只用到联结词,.,将限制性公式,A,中的,1,0,分别以,0,1,替换, 所得公式称为,A,的,对偶式,A,*,.,将限制性公式,A,中所有肯定形式出现的变元,x,换成,x,所有否定形式出现的变元,x,换成,x,所得公式称为,A,的,内否式,A,.,其实,求,A,时,A,不必是限制性公式,即可包含,和,.,Lu,Chaojun, SJTU,21,A,*,和,A,的性质,定理,(1),(,A,*)*,A,(,A,),A,(2) (,A,B,)*,A,*,B,* (,A,B,),A,B,(3) (,A,B,)*,A,*,B,* (,A,B,),A,B,定理,(1),(,A,)*,(,A,*) (,A,),(,A,),(2),A,(,A,*),(,De Morgan,律的一般形式,),(3) (,A,*),(,A,)*,Lu,Chaojun, SJTU,22,命题公式的对偶性质,推论,:,若,A,B,则,(,A,*),(,B,*),.,推论,:,若,A,B,则,A,*,B,*.,一旦证明了两公式等值,则同时证明了它们的对偶式也等值,.,Lu,Chaojun, SJTU,23,23,主要内容,命题与命题联结词,命题公式,等值演算,命题公式的范式,联结词的功能完全集,永真蕴涵式,命题逻辑推理,Lu,Chaojun, SJTU,24,公式有没有标准形式,?,命题公式的数量是无穷多的,.,即便只有一个命题变量,x,也可以写出,x,x,x,x,x,x,x,x,x,x, ,但若按等值关系对全体公式进行划分,n,个命题变量所能形成的不同公式仅有2,2,n,个,.(Why?),问题,:,与命题公式,A,等值的公式能否都化为某种标准形式,?,借助于标准形容易判断两个公式是否等值,.,借助于标准形容易判断公式是否永真式或永假式,.,Lu,Chaojun, SJTU,25,简单析,(,合,),取式,一个命题符号,a,及其否定,a,统称为,文字,.,由文字利用,(),联结而成的公式称为,简单析,(,合,),取式,.,简单析取式例,:,x, ,x,x,y,x,y,x,简单合取式例,:,x, ,x,x,y,x,y,x,定理,(1),一个简单析取式是永真式,iff,它同时包含一个命题符号及其否定,.,(2),一个简单合取式是矛盾式,iff,它同时包含一个命题符号及其否定,.,析,(,合,),取范式,由若干个简单合取式利用,联结而成的公式称为,析取范式,.,形如,:,A,1,A,2,A,n,(,诸,A,i,是简单合取式,),由若干个简单析取式利用,联结而成的公式称为,合取范式,.,形如,:,A,1,A,2,A,n,(,诸,A,i,是简单析取式,),定理,(1),一个析取范式是矛盾式,iff,它的每个简单合取式都是矛盾式,.,(2),一个合取范式是永真式,iff,它的每个简单析取式都是永真式,.,Lu,Chaojun, SJTU,26,Lu,Chaojun, SJTU,27,范式存在定理及求法,范式定理,:,对任一命题公式都存在与之等值的析取范式和合取范式,.,等值变换法求范式,(1),消去,(2) ,深入到命题符号之前,(3) (),深入,至此已是范式,.,(4),(,可选,),化简,27,Lu,Chaojun, SJTU,28,求范式,(1):,消去,方法,:,利用下列等值式,A,B,A,B,A,B,(,A,B,),(,A,B,),用于求析取范式,A,B,(,A,B,),(,A,B,),用于求合取范式,例,:,求,(,x,y,)(,x,y,),的,析取范式,(,x,y,)(,x,y,),(,x,y,) (,x,y,) (,x,y,) (,x,y,),28,Lu,Chaojun, SJTU,29,求范式,(2):,否定词深入,方法,:,利用下列等值式,(,A,B,),A, ,B,(,A,B,),A, ,B,A,A,例,(,x,y,)(,x,y,),(,x,y,) (,x,y,) (,x,y,) (,x,y,),(,x,y,x,y,) (,(,x,y,),(,x,y,),),29,Lu,Chaojun, SJTU,30,求范式,(3):,合,(,析,),取词深入,方法,:,利用分配律,A,(,B,C,),(,A,B,),(,A,C,) ,用于求析取范式,A,(,B,C,),(,A,B,),(,A,C,) ,用于求合取范式,例,(,x,y,)(,x,y,),(,x,y,) (,x,y,) (,x,y,) (,x,y,),(,x,y,x,y,) (,x,y,) (,x,y,),(,x,y,x,y,) ,(,x,x,) (,x,y,) (,y,x,) (,y,y,),30,Lu,Chaojun, SJTU,31,求范式,(4):(,可选,),化简,方法,:,利用下列等值式消去矛盾式,A, 0,0,A, 0,A,例,(,x,y,)(,x,y,),(,x,y,) (,x,y,) (,x,y,) (,x,y,),(,x,y,x,y,) (,x,y,) (,x,y,),(,x,y,x,y,) ,(,x,x,) (,x,y,) (,y,x,) (,y,y,),(,x,y,) (,x,y,),31,Lu,Chaojun, SJTU,32,范式的用途,判断,A,是否永真式,求,A,的合取范式,若每个简单析取式都含有某个变元及其否定,(,如,x,和,x,),则,A,是永真式,.,判断,A,是否矛盾式,求,A,的析取范式,若每个简单合取式都含有某个变元及其否定,(,如,x,和,x,),则,A,是矛盾式,.,判断,A,B,?,求,A,和,B,的同一种范式,看是否相同,.,这里有问题,:,范式唯一吗,?,32,Lu,Chaojun, SJTU,33,极小项与极大项,设公式只涉及,n,个命题变量,x,1, ,x,n,.,极小项,:,n,个文字的简单合取式,诸,x,i,以,x,i,或,x,i,形式出现且只出现一次,且,x,i,出现在左起第,i,个位置,.,极小项有,2,n,个,:,根据对应的成真赋值,可记为,m,000,=,x,1,x,n,1,x,n,m,001,=,x,1,x,n,1,x,n,m,010,=,x,1,x,n,1,x,n,m,111,= x,1,x,n,1,x,n,设公式只涉及,n,个命题变量,x,1, ,x,n,.,极大项,:,n,个文字的简单析取式,诸,x,i,以,x,i,或,x,i,形式出现且只出现一次,且,x,i,出现在左起第,i,个位置,.,极大项有,2,n,个,:,根据对应的成假赋值,可记为,M,000,= x,1,x,n,1,x,n,M,001,= x,1,x,n,1,x,n,M,010,= x,1,x,n,1,x,n,M,111,=,x,1,x,n,1,x,n,Lu,Chaojun, SJTU,34,极小,/,大项的性质,每个极小项只在一个赋值下为真,.,一个赋值不能使两个极小项都为真,.,两个极小项的合取为,0,极小项两两不等值,.,若,A,由,k,个极小项的析取组成,则其余,2,n,k,个极小项的析取就是,A.,若,k,=,2,n,则,A,是重言式,.,每个极大项只在一个赋值下为假,.,一个赋值不能使两个极小项都为假,.,两个极大项的析取为,1,极大项两两不等值,.,若,A,由,k,个极大项的合取组成,则其余,2,n,k,个极大项的合取就是,A.,若,k,=,2,n,则,A,是矛盾式,.,34,Lu,Chaojun, SJTU,35,主范式,主析取范式,:,仅由极小项构成的析取范式,.,定理,:,任何非永假的命题公式都存在唯一与之等值的主析取范式,.,主合取范式,:,仅由极大项构成的合取范式,.,定理,:,任何非永真的命题公式都存在唯一与之等值的主合取范式,.,Lu,Chaojun, SJTU,36,主范式的求法,(1),利用基本等值式,(1),先求一个析取范式,.,(2),若简单合取式,A,中未出现命题变量,x,则通过,A,A,(,x,x,),(,A,x,) (,A,x,),来补足,x,.,(3),消去重复出现的变量,矛盾式及重复出现的极小项,.,利用基本等值式,(1),先求一个合取范式,.,(2),若简单析取式,A,中未出现命题变量,x,则通过,A,A,(,x,x,),(,A,x,) (,A,x,),来补足,x,.,(3),消去重复出现的变量,永真式及重复出现的极大项,.,36,Lu,Chaojun, SJTU,37,例,:,基本等值式方法,例,:,求,x,y,的主析取范式,(1),x,y,x,y,(2) ,x,x, (,y,y,),(,x,y,),(,x,y,),y,y, (,x, ,x,),(,x,y,),(,x,y,),(3),消去一个,(,x,y,),于是,:,x,y,m,00,m,01,m,11,例,:,求,(,x,y,),的主合取范式,(1) (,x,y,),x,y,(2),x,x, (,y, ,y,),(,x,y,), (,x,y,),y,y, (,x, ,x,),(,x,y,), (,x,y,),(3),消去一个,(,x,y,),于是,: (,x,y,),M,00,M,01,M,11,37,Lu,Chaojun, SJTU,38,主范式的求法,(2),利用真值表,(1),根据每个使,A,为真的赋值写一个包含各命题变量的合取式,(,即极小项,).,(2),写出各极小项的析取式,(,即主析取范式,),利用真值表,(1),根据每个使,A,为假的赋值写一个包含各命题变量的析取式,(,即极大项,).,(2),写出各极大项的合取式,(,即主合取范式,).,38,Lu,Chaojun, SJTU,39,例,:,真值表方法求主析取范式,例,:,A,有三个成真赋值,.,由,(,x,y,)=(0,0),可写出合取式,:,x, ,y,由,(,x,y,)=(0,1),可写出合取式,:,x,y,由,(,x,y,)=(1,1),可写出合取式,:,x,y,于是得到,A,: (,x,y,) (,x,y,) (,x,y,),39,x,y,A,0,0,1,0,1,1,1,0,0,1,1,1,Lu,Chaojun, SJTU,40,例,:,真值表方法求主合取范式,例,:,A,有两个成假赋值,.,由,(,x,y,)=(1,0),可写出析取式,:,x,y,由,(,x,y,)=(1,1),可写出析取式,:,x, ,y,于是得到,A,: (,x,y,) (,x, ,y,),40,x,y,0,0,1,0,1,1,1,0,0,1,1,0,逻辑题,:,如何活下来,?,一岛国国王规定,:,外地人来岛将被绞死,.,根据外乡人临死前说的一句话的真假来选择绞架,.,说真话就选真理绞架,说假话就选谎言绞架,.,有一次一个外乡人来到岛上,他说的一句话竟然让他活了下来,.,知道怎么说吗,?,Lu,Chaojun, SJTU,41,End,