资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,1,第,1,章 命题逻辑,1.1,命题符号化及联结词,1.2,命题公式及分类,1.3,等值演算,1.4,范式,1.5,联结词完备集,1.6,推理理论,2,1.1,命题符号化及联结词,命题与真值,原子命题,复合命题,命题常元,命题变元,联结词,3,命题与真值,命题,:,判断结果惟一的陈述句,命题的真值,:,判断的结果,，非,真即假,真命题,:,真值为真的命题,假命题,:,真值为假的命题,注意,:,感叹句、祈使句、疑问句都不是命题,陈述句中的悖论以及判断结果不惟一确定的也不是,命题,4,例,下列句子中那些是命题？,(,1),是无理数,.,(,2) 2 + 5,8.,(,3),x,+ 5,3.,(4),你有铅笔吗？,(,5),这只兔子跑得真快呀！,(6),请不要讲话！,(7),我正在说谎话,.,真命题,假命题,真值不确定,疑问句,感叹句,祈使句,悖论,(3)(7),都不是命题,5,命题的分类,简单命题,(,原子命题,),：,简单陈述句构成的命题,复合命题,：,由简单命题与联结词按一定规则复合,而成的命题,6,简单命题符号化,用小写英文字母,p, q, r,p,i,q,i,r,i,(,i,1,）表示,简单命题,真值的符号化：用,“,1,”,表示真，用,“,0,”,表示假,例如，令,p,： 是有理数，则,p,的真值为,0,q,：,2 + 5 = 7,，则,q,的真值为,1,7,复合命题及其符号化：联结词,1.,否定式复合命题与否定联结词“,”,定义,设,P,为任意命题，复合命题,“,非,P,”(,或,“,p,的否定,”,),称,为,P,的,否定式,，记作,P,。其中符号,表示“非”，,称作,否定联结词,。,P,为真当且仅当,P,为假（根据联结词的涵义）,2.,合取式复合命题与合取联结词“”,定义,设,P,Q,为任意两个命题,复合命题,“,P,且,Q,”,(,或,“,P,与,Q,”,),称为,P,与,Q,的,合取式,，记作,P,Q,。其中符号,表示,“,且,”,，称作,合取联结词,。,P,Q,为真当且仅当,P,与,Q,均为真。,注意：合取式描述方式的灵活性与多样性,分清简单命题与复合命题,8,例,将下列命题符号化,.,(1),王晓既用功又聪明,.,(2),王晓不仅聪明，而且用功,.,(3),王晓虽然聪明，但不用功,.,(4),张辉与王丽都是三好生,.,(5),张辉与王丽是同学,.,解,令,p,：王晓用功，,q,：王晓聪明，则,(1),p,q,(2),p,q,(3),q,p,.,9,例,(,续,),令,r,:,张辉是三好学生，,s,:,王丽是三好学生,(,4),r,s,.,(5),令,t,:,张辉与王丽是同学，,t,是简单命题,.,说明,:,(,1),(,4),说明描述合取式的灵活性与多样性,.,(5),中“与”联结的是两个名词（而不是两个命题），整个句子是一个简单命题,.,10,联结词与复合命题,(,续,),定义,设,P,Q,为任意两个命题，复合命题,“,P,或,Q,”,称作,P,与,Q,的,析取式,，记作,P,Q,。其中符合,，表示,“,相容或,”,，称作,析取联结词。,P,Q,为假当且仅当,p,与,q,均为假,.,例,将下列命题符号化,(1) 2,或,4,是素数,.,(2) 2,或,3,是素数,.,(3) 4,或,6,是素数,.,(4),小,元元只能拿一个苹果或一个梨,.,(5),王晓红生于,1995,年或,1996,年,.,3.,析取式与析取联结词“”,11,解,令,p,:,2,是素数,q,:,3,是素数,r,:4,是素数,s,:,6,是素数,则,(1), (2), (3),均为,相容或,.,分别符号化为,:,p,r,p,q,r,s,它们的真值分别为,1, 1, 0.,(,4), (5),为,排斥或,.,令,t,:,小,元元拿一个苹果，,u,:,小,元元拿一个梨，,则,(,4),符号化为,(,t,u,),(,t,u,).,令,v,:,王晓红生于,1995,年,w,:,王晓红生于,1996,年,则,(,5),可符号化为,(,v,w,),(,v,w,),。注：在不强调只能生于一个年份时，也,可符号化为,v,w,.,12,联结词与复合命题,(,续,),定义,设,P,Q,为任意两个命题，复合命题,“,若,P,则,Q,”,称作,P,与,Q,的,蕴涵式,，记作,P,Q,，并称,P,是蕴涵式的,前件或前提,，,q,为蕴涵式的,后件或结论,.,符号,表示,“,若，则,”,（形式推论关系），,称作,蕴涵联结词,。,根据形式推论的涵义，,P,Q,为假当且仅当,P,为真且,Q,为假。,4.,蕴涵式与蕴涵联结词“,”,13,P,Q,的逻辑关系：,P,为,Q,的充分条件,，,Q,为,P,的必要条件,“,若,P,，则,Q ”,的不同表述法很多：,若,P,，就,Q,只要,P,，就,Q,P,仅当,Q,只有,Q,才,P,除非,Q,才,P,或 除非,Q,否则非,P,.,当,P,为假时，,P,Q,为真,常出现的错误：不分充分与必要条件,联结词与复合命题,(,续,),14,例,设,p,:,天冷，,q,:,小王穿羽绒服，,将下列命题符号化,(1),只要天冷，小王就穿羽绒服,.,(2),因为天冷，所以小王穿羽绒服,.,(3),若小王不穿羽绒服，则天不冷,.,(4),只有天冷，小王才穿羽绒服,.,(5),除非天冷，小王才穿羽绒服,.,(6),除非小王穿羽绒服，否则天不冷,.,(7),如果天不冷，则小王不穿羽绒服,.,(8),小王穿羽绒服仅当天冷的时候,.,注意：,p,q,与,q,p,等值（真值相同）,p,q,p,q,p,q,p,q,q,p,q,p,q,p,q,p,15,联结词与复合命题,(,续,),定义,设,P,，,Q,为任意两个命题，复合命题 “,P,当且仅当,Q,”,称作,P,与,Q,的,等价式,，记作,P,Q,.,称作,等价联结词,.,P,Q,为真当且仅当,P,与,Q,真值相同,.,说明,:,(1),P,Q,的逻辑关系,:,P,与,Q,互为充分必要条件,(2),P,Q,为真当且仅当,P,与,Q,同真或同假,5.,等价式与等价联结词“,”,16,例,求下列复合命题的真值,(,1) 2 + 2,4,当且仅当,3 + 3,6.,(,2) 2 + 2,4,当且仅当,3,是偶数,.,(,3) 2 + 2,4,当且仅当 太阳从东方升起,.,(,4) 2 + 2,4,当且仅当 美国位于非洲,.,(,5),函数,f,(,x,),在,x,0,可导的充要条件是它在,x,0,连续,.,1,1,0,0,0,例,17,联结词与复合命题,(,续,),以上给出了,5,个联结词：,，组成,一个联结词集合,，,联结词的优先顺序为：,;,如果出,现的联结词同级，又无括号时，则按从左到右,的顺序运算,;,若遇有括号时，应该先进行括号,中的运算,.,注意,:,本书中使用的,括号全为圆括号,.,18,1.2,命题公式及分类,命题变元与合式公式,公式的赋值,真值表,命题的分类,重言式,矛盾式,可满足式,真值函数,19,命题变元与合式公式,命题常元,：具体的简单命题，真值确定,命题变元,：可表示任意简单命题，真值不确定,定义,合式公式,(,命题公式,公式,),递归定义如下：,(1),单个命题常元或变元,p,q,r,p,i,q,i,r,i,0,1,是,合式公式,(2),若,A,是合式公式，则,(,A,),也是合式公式,(3),若,A,B,是合式公式，则,(,A,B,), (,A,B,), (,A,B,), (,A,B,),也是合式公式,(4),只有有限次地应用,(1)(3),形成的符号串才是合式公式,说明,:,外层括号可以省去,20,合式公式的层次,定义,(1),若公式,A,是单个命题常,/,变元,则称,A,为,0,层公式,.,(2),称,A,是,n,+1(,n,0),层公式是指下面情况之一：,(,a,),A,=,B,B,是,n,层公式；,(,b,),A,=,B,C,其中,B,C,分别为,i,层和,j,层公式，且,n,=max(,i,j,),；,(,c,),A,=,B,C,其中,B,C,的层次及,n,同,(,b,),；,(,d,),A,=,B,C,其中,B,C,的层次及,n,同,(,b,),；,(,e,),A,=,B,C,其中,B,C,的层次及,n,同,(,b,).,21,合式公式的层次,(,续,),例如 公式,p,0,层,p,1,层,p,q,2,层,(,p,q,),r,3,层,(,p,q,),r,),(,r,s,) 4,层,22,公式的赋值,定义,给公式,A,中的命题变元,p,1,p,2, ,p,n,指定,一组真值，称为对,A,的一个,赋值,或,解释,成真赋值,:,使公式为真的赋值,成假赋值,:,使公式为假的赋值,说明,：,赋值,=,1,2,n,之间不加标点符号，,i,=0,或,1.,A,中仅出现,p,1,p,2, ,p,n,，给,A,赋值,1,2,n,是,指,p,1,=,1,p,2,=,2, ,p,n,=,n,A,中仅出现,p,q,r, ,给,A,赋值,1,2,3,是指,p,=,1,q,=,2,r,=,3,含,n,个变元的公式有,2,n,个赋值,.,23,真值表,真值表,:,公式,A,在所有赋值下的取值情况列成的表,例 给出公式的真值表,A,= (,q,p,),q,p,的,真值表,p q,q,p,(,q,p,),q,(,q,p,),q,p,0 0,0 1,1 0,1 1,1,0,1,1,0,0,0,1,1,1,1,1,24,例,B,= ,(,p,q,),q,的,真值表,p q,p,p,q,(,p,q,),(,p,q,),q,0 0,0 1,1 0,1 1,1,1,0,0,1,1,0,1,0,0,1,0,0,0,0,0,实例,25,例,C,= (,p,q,),r,的,真值表,p q r,p,q,r,(,p,q,),r,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,0,0,1,1,1,1,1,1,1,0,1,0,1,0,1,0,1,1,1,0,1,0,1,0,26,公式的类型,定义,设,A,为一个命题公式,(1),若,A,无成假赋值，则称,A,为,重言式,(,也称,永真式,),(2),若,A,无成真赋值，则称,A,为,矛盾式,(,也称,永假式,),(3),若,A,不是矛盾式，则称,A,为,可满足式,注意：重言式是可满足式，但反之不真,.,上例中,A,为重言式，,B,为矛盾式，,C,为可满足式,A,= (,q,p,),q,p,，,B,=,(,p,q,),q,，,C,= (,p,q,),r,27,真值函數,问题：含,n,个命题变元的所有公式共产生多少个互,不相同的真值表？,定义,称定义域为,00,0, 00,1, 11,1,，值域,为,0,1,的函数是,n,元真值函数,，定义域中的元素是,长为,n,的,0,1,串,，若将所有这些串的集合记为,0,1,n,，则,F,:0,1,n,0,1,表示,一个,n,元真值函数,F,.,共有 个,n,元真值函数,.,2,元真值域函数的例子：,F,:0,1,2,0,1,，,且,F,(00)=,F,(01)=,F,(11)=0,，,F,(01)=1,。,28,命题公式与真值函数,对于任何一个含,n,个命题变元的命题公式,A,，都存在,惟一的一个,n,元真值函数,F,，,F,就是,A,的真值表,.,两个等值的公式，其真值函数相同,.,下表给出所有,2,元真值函数对应的真值表,每一个含,2,个命题变元的公式的真值表都可以在下表中找到,.,例如：,p,q,p,q, (,p,q,),(,(,p,q,),q,),等,都对应,表中的,29,2,元真值函数对应的真值表,p q,0 0,0 1,0 1,1 1,0 0 0 0 0 0 0 0,0 0 0 0 1 1 1 1,0 0 1 1 0 0 1 1,0 1 0 1 0 1 0 1,p q,0 0,0 1,0 1,1 1,1 1 1 1 1 1 1 1,0 0 0 0 1 1 1 1,0 0 1 1 0 0 1 1,0 1 0 1 0 1 0 1,30,1.3,命题逻辑等值演算,等值式,基本等值式,等值演算,置换规则,31,等值式,定义,若等价式,A,B,是重言式，则称,A,与,B,等值,，,记作,A,B,，并称,A,B,是,等值式,说明：,A,或,B,中可能有哑元,(,非,A,和,B,的共同变元,),出现,.,例如，在,(,p,q,),(,p,q,),(,r,r,),中，,r,为左边,公式的哑元,.,用真值表来验证两个公式是否等值，,并取两个者命题变元的并集，则可避免由哑元带来的,不一致,(,例：写出,p,q,在,p,q,r,三个变元下的真值表，,并与,(,p,q,),(,r,r,),的真值表比较,),。练习：请验证,p,(,q,r,) (,p,q,),r,p,(,q,r,),(,p,q,),r,32,基本等值式,双重否定律,:,A,A,幂等律,：,A,A,A,A,A,A,交换律,:,A,B,B,A,A,B,B,A,结合律,: (,A,B,),C,A,(,B,C,),(,A,B,),C,A,(,B,C,),分配律,:,A,(,B,C,),(,A,B,),(,A,C,),A,(,B,C,),(,A,B,),(,A,C,),33,基本等值式,(,续,),德,摩根律,:,(,A,B,),A,B,(,A,B,),A,B,吸收律,:,A,(,A,B,),A,A,(,A,B,),A,零律,:,A,1,1,A,0,0,同一律,:,A,0,A,A,1,A,排中律,:,A,A,1,矛盾律,:,A,A,0,34,基本等值式,(,续,),蕴涵等值式,:,A,B,A,B,等价等值式,:,A,B,(,A,B,),(,B,A,),假言易位,:,A,B,B,A,等价否定等值式,:,A,B,A,B,归谬论,: (,A,B,),(,A,B,),A,注意,:,A,B,C,代表任意的命题公式,牢记这些等值式是继续学习的基础,35,等值演算与置换规则,等值演算,:,由已知的等值式推出新的等值式的过程,置换规则,：若,A,B,则,(,B,),(,A,),把公式,(,A,),当中,A,的某个出现替换成与之等值的,B,，得到的,(,B,),与原来的,(,A,),等值。,等值演算的基础：,(,1),等值关系的性质：自反、对称、传递,(,2),基本的等值式,(,3),置换规则,36,应用举例,证明两个公式等值,例,1,证明,p,(,q,r,),(,p,q,),r,证,p,(,q,r,),p,(,q,r,),（蕴涵等值式，置换规则）,(,p,q,),r,（结合律）,(,p,q,),r,（德,摩根律，置换规则）,(,p,q,),r,（蕴涵等值式）,说明,:,也可以从右边开始演算（请做一遍）,37,应用举例,证明两个公式不等值,例,2,证明,:,p,(,q,r,) (,p,q,),r,用等值演算不能直接证明两个公式不等值,证明两,个公式不等值的基本思想是找到一个赋值使一个成,真,另一个成假,.,方法一 真值表法（自己证）,方法二 观察赋值法,.,容易看出,000, 010,等是左边的,的成真赋值，是右边的成假赋值,.,方法三 用等值演算先化简两个公式，再观察,.,38,应用举例,判断公式类型,例,3,用等值演算法判断下列公式的类型,(1),q,(,p,q,),解,q,(,p,q,),q,(,p,q,),（蕴涵等值式，置换规则）,q,(,p,q,),（德,摩根律，置换规则）,p,(,q,q,),（交换律，结合律）,p,0,（矛盾律，置换规则）,0,（零律）,由最后一步可知，该式为矛盾式,.,39,例,3 (,续,),(,2) (,p,q,),(,q,p,),解,(,p,q,),(,q,p,),(,p,q,),(,q,p,),（蕴涵等值式）,(,p,q,),(,p,q,),（交换律）,1,由最后一步可知，该式为重言式,.,问：最后一步为什么等值于,1,？,40,例,3 (,续,),(3) (,p,q,),(,p,q,),r,解,(,p,q,),(,p,q,),r,(,p,(,q,q,),r,（分配律，置换规则）,p,1,r,（排中律）,p,r,（同一律）,这不是矛盾式，也不是重言式，而是非重言式的可,满足式,.,如,101,是它的成真赋值,000,是它的成假赋值,.,总结：,A,为矛盾式当且仅当,A,0,A,为重言式当且仅当,A,1,说明：演算步骤不惟一,应尽量使演算短些,第,4,次作业题,1.,判别下列公式的类型，并写出它们的真值表,(1) (,p,q,),(,q,r,),(,p,r,),(2) (,p,q,),p,(3) (,p, ,q,),(,(,q,q,),r,),2.,（选做）,A,、,B,、,C,、,D,四人参加百米赛跑。观众甲、乙、丙预测比赛名次如下。比赛结束后发现三个人每人预测对了一半，问实际名次如何（假设无并列）？,甲：,C,第一，,B,第二,乙：,C,第二，,D,第三,丙：,A,第二，,D,第四,提示：可设,p,i,q,i,r,i,s,i,分别表示,A,第,i,名，,B,第,i,名，,，这里,i=1,2,3,4.,该题实际是给出若干命题的合取，求一个成真赋值使所有命题为真。可以用等值演算法逐步化简，直至得到单一而且形式简单的命题，能看出其成真赋值。,
展开阅读全文