全书电子课件：离散数学.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第一章 命题逻辑,引言,逻辑学,是推理的基础，在,社会学,、,自然科学,尤其计算机学科中得到普遍应用。,数理逻辑,是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在,程序设计,、,数字电路,设计、,计算机,原理、,人工智能,等计算机课程得到了广泛应用。,命题逻辑,是,数理逻辑,的基础部分，,但究竟什么是,命题,？,如何,表示,命题？,如何,构造,出复杂的命题？,在本章将,讨论,这些问题。,1.1,命题及联结词,对错,确定,的,陈述语句,称为命题,。如：,(1),湖南大学是一本学校。,(2),命题逻辑是计算机科学的基础课程。,(3,),命题及联结词是命题逻辑的最基础的内容。,(4),4,是素数。,(5),湖南大学坐落于湘江以东。,(6),2011,年湖南长沙轻轨通车。,其中,(1),、,(2),、,(3),与事实相符，是对的、正确的，称为,真命题,，或者称命题的值为“真”，简记为,T,或数字,1,。,而,(4),、,(5),明显与事实不相符，是错的、不正确，称为,假命题,，或称命题的值为“假”，简记为,F,或数字,0,。,陈述句,(6),的正确性，到,2011,年,12,月时能确定的，若届时开通了则它是对的、为真命题，否为假命题。,1.1,命题及联结词,对错,确定,的,陈述,语句称为命题,。如：,(7),x,与,y,之和为,100,，其中,x,为整数，,y,为整数,(8),1,加,1,等于,10,(7),的对错,不确定,的。当,x,为,50,、,y,为,50,时是对的，当,x,为,51,、,y,为,52,时是错的。,(8),的对错是,不确定,的，为二进制时正确，当为八进制、十进制时是错的，因此这两个陈述句,不是命题,。,(9),岳麓山的红叶真美呀！,(10),动作快点！,(11),你是离散数学老师吗？,这三个语句,不是陈述语句,，因此不是命题。,1.1,命题及联结词,对错,确定,的,陈述,语句称为命题,。如：,(12),我在说假话。,(13),我只给自己不能理发的人理发。,(14),派出所说,:,必须先房子再能上户口,单位后勤说,:,必须先有户口才能分房,你能上到户口与要到房子吗,?,这是一个悖论，其真值不能确定，故不是命题。,1.1,命题及联结词,对错,确定,的,陈述,语句称为命题,。如：,(13),我既要学程序设计，又要学离散数学。,(14),我们早餐在公寓食堂或外面早点摊上吃。,(15),我不是数学院的学生,这三个陈述句都与事实相符，是对的，是真命题，其值为真,(T/1),。,其中,(13),与,(14),可分解为另外二句话的组合，,而,(15),是对“我是数学院学生”的否定，这些语句称为“,复合命题,”，不能再分解的语句称为“,简单命题,”或“,原子命题,”，为了便于推理与书写，常用,小写字母,表示,简单命题,或,原子命题,。,1.1,命题及联结词,简单命题,组合成,复杂命题,时所使用的辅助词称为“,联结词,”。,命题逻辑中的联结词归纳为以下,5,种。,合取,：,C,语言中,&and,并且,析取,：,C,语言中,|or,或,否定,：,C,语言中,!not,非,不是,否定,条件式,：,C,语言中,if(),如果,那么 如,p,则,q,双条件式,：如,p,则,q,且如,q,则,p,当且仅当,1.1,命题及联结词,定义,1.1,合取,：当,p,、,q,都对,，即取值为真,(,T,或,1,),时，“,p,合取,q”,的值为,真,.,1.1,命题及联结词,定义,1.1,合取,：当,p,、,q,都对,，即取值为真,(,T,或,1,),时，“,p,合取,q”,的值为,真,，其他情况为,假,。,逻辑运算符,“合取”，,与汉语中,“并且、而且、同时”,含义相当,1.1,命题及联结词,定义,1.2,析取,：当,p,、,q,都不对,，即取值为假,(,F,或,0,),时，“,p,析取,q”,的值为,假,，其他情况为,真,。,逻辑运算符,“析取”，,与汉语中,“或”,含义相当，但有细微的区别,1.1,命题及联结词,逻辑运算符“析取”与汉语的“或”几乎一致但有区别：,(16)“,讲离散数学的老师是杨老师或刘老师,”，可以表示为“,讲离散数学的老师是杨老师,”“,讲离散数学的老师是刘老师,”，这两个原子命题有可能,都是对,的，这种“或”称为“,可同时为真的或,”，或简称为“,可兼或,”。,(17)“,离散数学的教室是102或302,”,，,不可以,表示为“,离散数学的教室是102,”“,离散数学的教室是,3,02,”,，因为这两个原子命题,不可能都对,，只能这二种情况之一，这种“,或,”称为“,不可同时为真的或,”，或简称为“,不可兼或,”、“,排斥或,”,.,这种“或”表示,不能简单,表示为“析取”，需要联合使用下面将要介绍的“,否定,”与“析取”符号，才能准确表达。,1.1,命题及联结词,定义,1.3,否定,:,当,p,是,1,，,p,的否定,p,即为,0,。,逻辑运算符,“否定”，,与汉语中,“否定”,含义相当,.,“,我不是数学院的学生,”可表示为“,我是数学院的学生,”,“,离散数学的教室是102或302,”,表示,离散数学的教室是,102,不是,302,或,离散数学的教室是,3,02不是,1,02,p:,离散数学的教室是,102,q:,离散数学的教室是,302,上面的语句表示,:(p,q)(pq),1.1,命题及联结词,定义,1.4,条件,:,当,p,是,1,q,是,0,时,pq,为,0,即,10,为,0,其他情况为,1,。,逻辑运算符,“如果,那么”，,它是用单个运算符表示一个复合语句。,如老妈说：“,如果期终考了年级前,10,名，那么奖励,1000,元,”。,p:,期终考了年级前10名,q:,奖励,1000,元,则上面的语句表示为,pq,。,当,p,为,1,即“,期终考了年级前,10,”,，,且,q,为,0,即“,没有奖励,1000,元,”,这时老妈的话是假话空话，,故,pq,为,0,1.1,命题及联结词,定义,1.4,条件式,(,蕴含式,),:,当,p,是,1,q,是,0,时,pq,为,0,即,10,为,0,其他情况为,1,。,p,为前件,q,为后件,(1),当,p,为,1,即“,我期终考了年级前,10,”,q,为,0,即“,我老妈没有奖励,1000,元,”,这时老妈的话为假，即,pq,为,0,(2),当,p,为,1,即“,我期终考了年级前,10,”,q,为,1,即“,我老妈奖励,1000,元,”,这时妈妈的话就对了，即,pq,为,1,(3),至于,p,为,0,即“,我期终考了年级不是前,10,”,时,无论,q,为,1,或为,0,，即无论,我老妈,奖励,1000,元,或,不奖励,，都不能说老妈的话是,假的,，故可,善意,的认为,pq,为,1,均为,1,1.1,命题及联结词,定义,1.5,双条件,:,当,p,与,q,值相同,0,时,pq,为,1,不同为,0,。称,p,与,q,的等价式,“,我明年赚了,10,万当且仅当我买彩票中了大奖,”，,可以表示为“,我明年赚了,10,万,我买彩票中了大奖,”,1.2,公式及其赋值,对错明确的陈述语句称为,命题，其真值确定，又称为,命题常元,或,命题常项,，相当于初等数学中的“,常数,”。,数学的运算符号为“加,+,、减,-,、乘,x,、除、幂”，,命题逻辑的符号“合取、析取、否定、条件、双条件”,数学中用,变量,x,表示,某些数,，如,x,2,+x+10,是代数式，,命题逻辑,用,变量,表示,任意一个命题,，如,p,q,r,这时由符号与变量所构成命题表达式，简称为“,命题公式,”。,代数式的书写有规律，命题公式也有规律与约束，称满足这些规则的公式为“合式公式”，也称为“命题公式”，简称为“公式”。,1.2,公式及其赋值,定义,1.2.1,合式公式的生成规则,(1),单个,命题变元、命题常元为合式公式,(,原子公式,),。,(2),若,A,是,合式公式,，则,A,、,(A),也是合式公式。,(3),若,A,、,B,是,合式公式,，则,AB,、,AB,、,AB,、,AB,是合式公式。,(4),有限次使用,(2)(3),形成的字符串均为,合式公式,。,如,：,(p1)q,是合式公式。,因为,p,、,1,是合公式，则,(p1),是合式公式，而,r,是合式公式，故,(p1)q,是合式公式。,(p1)r,不是合式公式。,因为,p,、,1,是合公式，则,(p1),是合式公式，而,r,是合式公式，但,(p1)r,不是合法公式。,1.2,公式及其赋值,对于代数式,x,2,+y+10,，当,x,与,y,的值不确定时，该代数式的值是不确定的。,对于公式,(p1)q,，由于,p,与,q,值不确定时，公式,(p1)q,的值不确定，因而不是命题。,只有当,p,与,q,的值确定后，公式,(p1)q,的值才能确定，我们可能像表,1.2,到表,1.5,一样，给出公式在各种情况下的取值，即得到这个公式的真值表。,p,与,q,每一种取值称为,p,、,q,的一种解释,1.2,公式及其赋值,公式(pq)、pq,的真值表如下表,。,真值表的构造方法,：,(1),命题变元,的取值从全,0,开始，依次加,1,，直到全,1,，当有,n,个变元时，则共有,2,n,种不同的取值情况。,(2),分步骤,计算公式的值,(3),见,黑板,上写,成真赋值,:,如,pq,为,(0,0),(0,1),(1,1),成假赋值,:,如,pq,为,(1,0),1.2,公式及其赋值,公式(pq),(,qp),、,pq,的真值表,。,无论,p/q,取何值，这两个公式的值总相等。,1.2,公式及其赋值,公式,(pq),、,p q,的真值表,。,无论,p/q,取何值，这两个公式的值总相等。,1.2,公式及其赋值,公式pq,、,pq,的真值表,。,无论,p/q,取何值，这两个公式的值总相等。,1,1.2,公式及其赋值,公式pq,、,q,p,的真值表,。,无论,p/q,取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否命题,1,1.2,公式及其赋值,公式p(qr),、,(,pq)(pr),的真值表,。,无论,p/q,取何值，这两个公式的值，与前面各例不同，此表是将运算结果写在联结词的下方！,1.3,等值式,一、复习,由前节可知：,p,q,与,pq,、,q,p,p,q,与,(p,q)(q,p),、,(p,q)(p,q),(p,q),与,p q,p(qr),、,(,pq)(pr),的真值表完全一样，称为等值。,定义,1.3.1,设,A,、,B,是两个合法的命题公式，无论其中的命题变元取何值，这两个公式的总相等，称为两个公式等值，记为,AB,由定义及前节习题有：,(1)pqpqqp,条件式的等值式,(2)pq(pq)(qp)(pq)(pq),双条件,(3)pp,双重否定律,(4)ppppp,幂等律,(5)pq qp,，,pq qp,交换律,(6)p(qr)(pq)r,结合律,p(qr)(pq)r,(7)p(qr)(pq)(pr),分配律,p(qr)(pq)(pr),(8)p(pr)p,吸收律,(,多吃少,),p(pr)p,(9)(pq)pq,德摩律,(pq)pq,将以上等值式中的变元换成合式公式仍等值！,如：,p,q pq,则有,A,B AB,尽管,A/B,可能很复杂，但是公式值也只有,0,、,1,二种,可能，公式,A/B,的组合只有,0/0,0/1,1/0,1/1,四种，如下表所示,显然有,A,B AB,置换规则,：当将公式,A,中的子公式,B,换成,C,得到公式,D,后，若,BC,，那么,AD,。,因为,A,、,D,除了“,A,中,B,所在之处、,D,中,C,所在之处”外，其他地方均相同，而不同之处的,B,与,C,等值，所以公式,A,、公式,D,的真值表应该完全他相同，故,AD,。,当将一个公式的,局部进行等值,替换后，,仍与,原公式,等值，这也是数学中最常见的方法，不断对,局部进行等值替换,的操作，称为“等值演算”。,利用该规则及前述的等值式，可进行等值演算，从而推导出新的公式。,求证,(pq)r(pr)(qr),(pq)r,(pq)r,条件式的等值式,(pq)r,利用德摩律,r(pq),交换律,(rp)(rq),分配律,(p r)(qr),交换律,(pr)(qr),条件式等值式,等值演算的基本套路,(1),转换,：,A,BAB,(2),恰当转换,：,A,B(AB)(AB),(AB)(AB),确保公式只保留,联结词,(3),否定到底：,A,(A,B),(A,B),(4),恰当使用分配律、吸收律。,利用等值演算，判断公式的类型,(pq)p)q,(pq)p)q,(pq)p)q (,条件式的等值式,),(pq)p)q (,条件式的等值式,),(pq)p)q (,德摩律,),(pq)p)q (,德摩律,),(pq)(pq)(,结合律,),(pq)(pq)(,逆用德摩律,),AA (,A=(pq),1,称为永真式或重言式，,即利用等值演算，可以判断公式的类型。,利用等值演算判断公式类型,：,(p(pq)r,解：,(p(pq)r,(p(pq)r (,条件式的等值式,),(pp)q)r (,结合律,),(1q)r (,析取的性质即析取定义真值表,),1r (,析取的性质即析取定义真值表,),0r (,否定的定义,),0 (,析取的性质即析取定义真值表,),永假式或矛盾式。,问题,：尽管有套路可行，但是随意性还是比较大，能否有某种方式肯定能成功呢？,1.4,析取范式与合取范式,文字,：命题变项,(,变元,),及其否定称为文字,.,如,:p,q,r,p,q,r,简单析取式,:,仅由有限个,文字,构成的析取式,.,如,:pq,pq,pq,p q,pqr,简单合取式,:,仅由有限个,文字,构成的合取式,.,如,:pq,pq,pq,pq,pqr,定理,：简单,析取,式与简单,合取式,(1),一个简单析取式,Ai,是重言式,含有某个命题变元及其否定式，如,Ai=,p,p,(2),一个简单合取式,Ai,是矛盾式,含有某个命题变元及其否定式，如,Ai=,p,p,1.4,析取范式与合取范式,析取范式,：由有限个,简单合取,式的,析取,构成的,命题公式,称为,析取范式,。,总体是,析取,式，每对括号内是,合取,式,A=(p,q)(p,r),合取范式,：由有限个,简单析取,式的,合取,构成的,命题公式,称为,合取范式,。,总体是,合取,式，每对括号内是,析,取式,A=(p,q)(p,r),1.4,析取范式与合取范式,总体是,析取,式，每对括号内是,合取,式,A=(p,q)(p,r),析取范式,总体是,合取,式，每对括号内是,析,取式,A=(p,q)(p,r),合取范式,定理,：,析取范,式与,合取范式,(1),一个,析取范式,A,是矛盾式,每个简单合取式是矛盾式。,A=(p,q)(p,r),(2),一个,合取范式,A,是重言式,每个简单析取式是重言式。,A=(p,q)(p,r),1.4,析取范式与合取范式,(1),转换,：,A,BAB,(2),恰当转换,：,A,B(AB)(AB),(AB)(AB),(3),否定到底：,A,(A,B),(A,B),(4),适当使用分配律：,A,(BC),A,(BC).,经过第,1,步、第,2,步转换后，公式中只有、三种运算符。,经过第,3,步后，从括号外深入到变元的前面，与变元结合成文文字，文字之间只有、。,1.4,析取范式与合取范式,(1),转换,：,A,BAB,(2),恰当转换,：,A,B(AB)(AB),(AB)(AB),(3),否定到底：,A,(A,B),(A,B),(4),适当使用分配律：,A,(BC),A,(BC).,如果外层运算符全部是，而内层子公式全部是简单析取式，则已经是合取范式。,如果内层某子公式形如,A(BC),，,不是,简单析取式，则转换为,(AB)(AC),。,1.4,析取范式与合取范式,(1),转换,：,A,BAB,(2),恰当转换,：,A,B(AB)(AB),(AB)(AB),(3),否定到底：,A,(A,B),(A,B),(4),适当使用分配律：,A,(BC),A,(BC).,如果外层运算符全部是，而内层子公式全部是简单合取式，则已经是析取范式。,如果内层某子公式形如,A(BC),，,不是,简单合取式，则转换为,(AB)(AC),。因此有：,(1),不是,永假,的命题公式，存在析取范式。,(2),不是,永真,的命题公式，存在合取范式。,1.4,析取范式与合取范式,(1),转换,：,A,BAB,(2),恰当转换,：,A,B(AB)(AB),(AB)(AB),(3),否定到底：,A,(A,B),(A,B),(4),适当使用分配律：,A,(BC),A,(BC).,如,析取式范式,：,(pq)r,(pq)r,(pq)r)(,(pq),r),(p r)(qr)(pq,r),1.4,析取范式与合取范式,求,(pq)r,的析取范式、合取范式,解：,(1),求析取范式,。即外层是，内层是，所以转换模式为,AB(AB)(AB),(pq)r,(pq)r)(pq)r)(,整体为析取,),(,pq,)r)(,pq,)r)(,ABAB,),(pq)r)(,(pq),r)(,德摩律,),(,(p r)(qr),)(pq)r)(,分配律,),(p r)(qr)(pq r)(,结合律,),1.4,析取范式与合取范式,解：,(1),求合取范式,。,所以,转换模式为,AB(AB)(AB),(pq)r,(pq)r)(pq)r)(,整体为合取,),(,pq,)r)(,pq,)r)(,条件等价式,),(,pq,)r)(pq)r)(,德摩律,),(,(pr)(qr),)(pq)r)(,分配律,),(pr)(qr)(pq r)(,结合律,),1.4,析取范式与合取范式,小项,：在含有,n,个变元的,简单合取式,中,每个,命题变元或其否定,仅出现,一次,且各变元按其字母顺序出现,则该简单合取式为,(,极,),小项,。,如：,pqr,pqr,pqr,pqr,(p r),(qr),非小项,大项,：在含有,n,个变元的,简单析取式,中,每个,命题变元或其否定,仅出现,一次,且各变元按其字母顺序出现,则该简单析取式为,(,极,),大项,。,如：,pqr,pqr,pqr,pqr,(pr),(qr),非大项,1.4,析取范式与合取范式,主析取范式,：一个析取范式中，如果所有,简单合取式,均为,(,极,),小项，,则称,为主析取范式,。,(pq)r,(p r)(qr)(pq,r),不是,(p,q,r)(p,q,r),(,p,qr)(pqr),是主析取范式,1.4,析取范式与合取范式,主合取范式,：一个合取范式中，如果所有,简单析取式,均为,(,极,),大项，,则称为主合取范式。,(pq)r,(pr)(qr)(pqr),不是,(p,q,r)(p,q,r),(,p,qr)(,p,qr),是主合取范式,1.4,析取范式与合取范式,获取方法,通过转换联结词,、,“,到底,”,及,适当,使用分配律，可以得到,合取,范式与,析取,范式，这时可能还缺少某个变元，,因为,pp1,，,1r1,，,可在缺少变元的,小项,中加入形如,“,pp,”,的公式。,如小项,(pr),缺少变元,q,，加入,qq,，即,pr,p,1,r,p(,qq,)r,(pqr)(pqr),。,1.4,析取范式与合取范式,获取方法,通过转换联结词,、,“,到底,”,及,适当,使用分配律，可以得到,合取,范式与,析取,范式，这时可能还缺少某个变元，,因为,pp1,，,1r1,，,可在缺少变元的,小项,中加入形如,“,pp,”,的公式。,(pq)r,(pr)(qr)(pqr),(p(,qq,)r)(,pp,)qr)(pqr),(pqr)(pqr)(pqr),(pqr),(pqr),(pqr)(pqr)(pqr)(pqr),1.4,析取范式与合取范式,获取方法,通过转换联结词,、,“,到底,”,及,适当,使用分配律，可以得到,合取,范式与,析取,范式，这时可能还缺少某个变元，,因为,pp0,，,0pp,，可在缺少变元的,大项,中加入形如,“,pp,”,的公式。,如,pr,p,0,r,p(,qq,)r,(pqr)(pqr),1.4,析取范式与合取范式,获取方法,通过转换联结词,、,“,到底,”,及,适当,使用分配律，可以得到,合取,范式与,析取,范式，这时可能还缺少某个变元，,因为,pp0,，,0pp,，可在缺少变元的,大项,中加入形如,“,pp,”,的公式。,(pq)r,(pr)(qr)(pqr),(p(,qq,)r)(,pp,)qr)(pqr),(pqr)(pqr)(pqr)(pqr)(pqr),(pqr)(pqr)(pqr)(pqr),1.4,析取范式与合取范式,当一个公式比较复杂时，得到其,析取范式、合取范式,的演算量比较大，再将简单析取式转换为大项，或简单合取式转换为小项，又需要进一步演算，能否直接基于原公式，不进行等值演算直接得到，或者能按某种统一的方式得到其主析取范式、主合取范式呢？,通过,真值表,可以实现！为此先研究小项与大项的性质,。,1.4,析取范式与合取范式,通过,真值表,可以实现！为此先研究小项与大项的性质，下表是,各小项,的真值表。,1.,3,个变元,的小项共有,8,个，它们,各不相,同。,2.,从,每一行,来看，命题变元的每个指派中，只有,一个,小项的值为,1,。,3.,从,每一列,来看，每个小项仅在,一个指派中值,为,1,，其余,7,种指派中均为,0,。,4.,小项,值为,1,(,如,pqr=1),时，,p,q,r,均为,1,，即,(p,q,r)=(0,0,0),，,取该值为小项编号，如最后一行。,(5),根据,小项的编号,，可写出,小项的具体,形式。,如小项,m,101,，其编号为,101,，表示,(p,q,r)=(1,0,1),时该小项的值为,1,，而小项是文字的合取，故小项的各个文字必须为,1,则文字只能是,p,、,q,、,r,故该小项为,pqr,。,规则,：,1,对应变元本身,(,如,p,),，,0,对应其否定,(,如,p,),。,如,m,00,为,pq,、,m,01,为,pq,、,m,10,为,pq,、,m,11,为,pq,。,很重要！,(1),三个变元,的大项共有,8,个。,(2),每一行,:,每个指派中，只有一个大项的值为,0,。,(3),每一列,:,每个大项仅在一个指派下值为,0,。,(4),大项值为,0(,如,pqr=0),时，,p,、,q,、,r,均为,0,，则,(p,q,r)=(1,1,1),，将其记为大项编号,如表最后行。,(5),根据,大项,的编号，可写出大项的具体形式。,如大项,M,101,其编号为,101,，表示,(p,q,r)=(1,0,1),时该大项的值为,0,，而大项是文字的析取，故各个文字必须为,0,，文字只能是,p,、,q,、,r,，故该大项为,pqr,。,规则,：,1,对应变元的,否定,(,如,p),，,0,对应变元,(,如,p),如,M,00,为,pq,M,01,为,pq,M,10,为,pq,M,11,为,pq,。,1.4,析取范式与合取范式,获取方法,1,、先转换,析取式,或,合取式,，再,合取,1,或,析取,0,。,2,、先建立,真值表,，,取出所有,成真赋值,对应的小项，析取所有小项得主析取范式。,小项与成真赋值对应,。,取出所,有成假赋值,对应的大项，合取所有大项得主合取范式。,大项与成假赋值对应。,如用真值表求主范式,:,(pq)r,pq,pq,(pq)q,p(pq),(pq)r,的,主析,取范式、,主合,取范式,主析取,范式,公式值为,1,的指派对应小项的析取,m,001,m,011,m,100,m,111,1,变元,0,变元否定,使小项,=1,(pqr)(pqr)(pqr)(pqr),(pq)r,的,主析,取范式、,主合,取范式,主合取式,范式,公式值为,0,的指派对应,大项,的合取,M,000,M,010,M,101,M,110,1,变元否定,0,变元,使大项,=0,(pqr)(pqr)(pqr)(pqr),(pq)r,、,与其主析取范式、主合取范式的真值完全一样，说明三者互相等值，一般情况下有如下定理,：,(1),不是,永假,的命题公式，有等值的,主析取范式,。,(2),不是,永真,的命题公式，有等值的,主合取范式,。,由于永假没有取值为,1,的解释，故无相应小项，故没有主析取范式。永真无取值为,0,的解释,故没有主合取范式,.,设计一个电子评分系统，,3,位专家打分，如果有,2,位以上专家打分为,“,通过,”,，则总成绩为,“,通过,”,。,对应的主析取范式,值为,1,的指派对应的小项的析取,m,011,m,101,m,110,m,111,(x1x2x3)(x1x2x3)(x1x2x3)(x1x2x3),(,(x1x2x3)(x1x2x3),)(x1x2x3),(x1x2x3),(,(x1x2)(x1x2),)x3)(x1x2(x3x3),(x1x2)(x1x2)x3)(x1x2),(x1x2)(x1x2)x3)(x1x2),与非或门表示,某公司要从曹、乔、宋、黎、邹,5,人中，选择一些人承包一项工程，考虑到人与人组合优化的问题，需满足如下约束条件：,(1),如果曹去，那么乔也去；,(2),黎、邹两人中必有一人去；,(3),乔、宋两人中去且仅去一人；,(4),宋、黎两人同去或同时不去；,(5),若邹去，则曹、乔也同去；,解：用小写字母表示：,c:,曹去，,q,：乔去,s,：宋去,l,：黎去,z,：邹去时，以上,5,句话可表示为如下的公式：,(cq),、,(lz),、,(qs)(qs),、,(sl),、,(z(qc),，,5,句话同时成立即每句话的值均为,1,，也即其合取式,(cq)(lz)(qs)(qs)(sl)(z(qc),为,1,(cq)(lz)(qs)(qs)(sl)(z(qc),(cq)(lz)(qs)(qs)(sl)(sl)(z(qc),(cq)(lz)(z(qc)(qssl)(qssl)(qssl)(qssl),(cq)(lz)(z(qc)(qsl)(qsl),(cq)(lz)(zqsl)(zqsl)(qcsl),(cq)(zqsl)(zqcsl),(czqsl)(zqcsl),因,(cq)(lz)(qs)(qs)(sl)(z(qc),为,1,，故,1(czqsl)(zqcsl),，,故,1(czqsl),或,1(zqcsl),故,方案一是：曹不去、邹不去、乔不去，宋与黎去。,方案二是：曹去、乔去、邹去，宋与黎均不去,在某班班委的选举中，该班的甲、乙、丙学生预言：,甲说：王娟为班长、刘强为生活委员；,乙说：金鑫为班长、王娟为生活委员；,丙说：刘强为班长、王娟为学习委员；,结果公布后，发现甲、乙、丙三人都恰好对了一半，请问王娟、刘强、金鑫各任何职？,解,：,p1,q1,r1:,表示王娟，刘强，金鑫是,班长,；,p2,q2,r2:,分别表示王娟，刘强，金鑫是,学习,委员；,p3,q3,r3:,分别表示王娟，刘强，金鑫是,生活,委员；,“每个人说法对一半”将是一个非常复杂的公式,(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2)(p1q3r1p3q1p2),，要构造这,9,个变元的真值表，将需要,2,9,=512,行，工作量实在太大了，！,参考,“,真值表,”,，设计如下的判断表,1.6,推理理论,从,已知条件,、,假设,、,前提,或,公理,出发，根据推理规则,推出,结论、定理的过程，称为,推理,。,定义,1,设,A,与,C,是两个命题公式，若,AC,为,永真式,(,重言式,),，则称,C,是,A,的,有效结论,，或称,A,可以,逻辑推出,C,，记为,AC,.,由“,”的定义可知，当,A,为,假,时，,AC,肯定为,真,，故只要考虑,A,为,真,时,C,是否,为,真,即可，故有,:,定义,2,设A与C是两个命题公式，若当,A为真,时,C也为真,，则称C是A的,有效结论,，或称A可以逻辑推出C，记为,AC,。,一般情况下，利用定义,2,去证明要简单些，我们在其他学科中遇到的证明都是基于定义,2,的。,判断,AC,为,永真,可用等值演算、真值表等方法,例题 求证：,A,(A,B),B,(A,(A,B),B,(A,(A,B),B (,的等值式,),(A,(,A,B),B (,的等值式,),(A,A),(A,B),B (,分配律,),(0,(A,B),B (,合取的性质,),(A,B),B (,析取的性质,),(,A,B),B (,德摩律,),A,(,B,B)(,结合律,),A,1 (,析取的性质,),1(,析取的性质,),所以,(A,(A,B),B,是,重言式,，真值表也证永真,所以,A,(A,B),B,。,这是有名的,“,假言推理,(modus ponens)”,，或“,分离原则,”,假如,我今年进入年级前,10,名老爸给我买,iphone 4;,期末考试后我为年级第,8,名，所以老爸应该给我买,iphone4,。这是,假言推理,。,A,(A,B),B,从形式上看，,结论,B,是,A,B,的,后件,，推导的,结果,是将,后件分离,出来，故也称为,分离原则,。,利用假言推理规则或分离规则，结合析取、合取、否定的定义，只要不歉麻烦，几乎可推出所有的结论。,为了提高推理效率，还需要学习、掌握某些推理规则,。,例题 求证,A,A,B,采用定义,1,来证明，即证明,A,A,B,为,永真式,。,A,A,B,A,(A,B)(,的等值式,),(,A,A),B (,结合律,),1,B (,析取的性质,),1 (,析取的性质,),所以,A,A,B,例题 求证,A,B,A,A,B,A,(A,B),A (,的等值式,),(,A,B),A (,德摩律,),A,B,A (,结合律,),1,B (,析取的性质,),1 (,析取的性质,),类似,A,B,B,根据,的定义可知,A,B,为真时，,A,与,B,均为真，因此由推理定义,2,可知,A,B,A,，,A,B,B,。,同样由,的定义可知,A,为真时,A,B,为真，故由推理定义,2,可知,A,A,B,。,然这,3,个推理式不必记忆！推理定义,2,效率较高,例题 求证,(A,B),(B,C),(A,C),根据定义,1,，要证明下式为永真式。,(AB)(BC)(AC),(AB)(BC)(AC)(,的等值式,),(AB)(BC)(AC)(,的等值式,),(AB)(BC)(AC)(,德摩律,),(,(A B)(A C)(B B)(BC),)(AC)(,分配律,),(A B)(A C)1(BC)(AC)(,析取的性质,),(A B)(A C)(BC)(AC)(,析取的性质,),(A B,AC,)(A C,AC,)(BC,AC,)(,分配律,),(1 BC)(1 CC)(BA1)(,析取的性质,),111 (,析取的性质,),1 (,析取的性质,),判断公式的类型，除等值演算外，还有真值表与范式等方法。,例题 求证,(A,B),(B,C),(A,C),由上表可知，,(A,B),(B,C),(A,C),为重言式，,由定义,1,可知,(A,B),(B,C),(A,C),。,这是有名的传递律，要记住呀！,例题 求证,(AB)(CD)(AC)BD,利用,定义,1,证明了假言推理规则,(AB)AB,传递规则,(A,B),(B,C),(A,C),。,有了这,2,条规则后,可用,定义,2,来证明推理式了。,由于这,2,条规则的结论中没有析取式，只有条件式，因此将题中结论,转换为,B,D,题设中,转换为,(1)(AB)(CD)(AC),为真前提条件,(,定义,2,的套路,),(2)(AB),为真,(1),及合取的性质,(3)(CD),为真,(1),及合取的性质,(4)(AC),为真,(1),及合取的性质,(5)(BA),为真,(2),及,(AB)(BA),(6)(AC),为真,(4),及,(AC)(AC),(7)(BC),为真,(5),、,(6),及推理传递律,(8)(BD),为真,(7),、,(3),及推理传递律,(9)BD,为真,(8),及,(BD)BD,例题 求证,(AB)(CD)(BD)AC,可用传递律来证明，还有更高效的方法,由定义,1,只要证,(AB)(CD)(BD)(AC),为重言式,，而,(AB)(CD)(BD)(AC),(,(AB)(CD)(BD),)(AC),(,(AB)(CD)(BD),A)C),(AB)(CD)(BD)A)C),(AB)(CD)(BD)A)C,故只需证,(AB)(CD)(BD)A)C,为,重言式,即只需证明,(AB)(CD)(BD)AC,A,从结论中挪到前提中，这种技巧称为,附加条件,(CP),法，适合于,结论,为,条件式,的情形。,例题 求证,(AB)(CD)(BD)AC,(1)(AB)(CD)(BD)A,为真,CP,规则及前提,(2)AB,为真,(1),及合取的性质,(3)A,为真,(1),及合取的性质,(4)B,为真,(2)(3),及假言推理式,(AB)AB,(5)BD,为真,(1),及合取的性质,(6)BD,为真,(5),及,BDBD,(7)D,为真,(4)(6),及假言推理式,(BD)BD,(8)CD,为真,(1),及合取的性质,(9)DC,为真,(8),及原命题逆否命题,(10)C,为真,(7)(9),假言推理式,(DC)DC,提示：熟练后可不写,(1),式，直接引用,(2)(3)(5)(8),！,例题 求证,(AB)(CD)(BD)AC,(1)AB,为真,前提条件,(2)A,为真,附加前提,(3)B,为真,(1)(2),及假言推理式,(AB)AB,(4)BD,为真,前提条件,(5)BD,为真,(4),及,BDBD,(6)D,为真,(3)(5),及假言推理式,(BD)BD,(7)CD,为真,前提条件,(8)DC,为真,(7),及原命题逆否命题,(9)C,为真,(6)(8),假言推理式,(DC)DC,求证,(WR)V,V(CS),SU,C,UW,提示,：此处用逗号简写前述各例中的合取式，从而鼓励大家直接引用前提。,利用假言推理、传递律及前面所学的等值式，可以推出结论。在黑板上演示一番,考虑到本题的结论是,W,，可采用,反证法,。,根据,定义,2,可知,“,当前提为真时结论也为真,”，,反证法是“,前提,为,真,时，假设,结论,不为,真,即结论的,否定为真,”。,即基于,前提,、,结论否定,进行推理。,如果推出了一个,矛盾的结论,出来，则,说明,“假设结论不为真”是,错误,的，即表示结论只能为真了,求证,(WR)V,V(CS),SU,C,UW,(1)W,为真,假设结论,W,为,0,即,W,为,1(,真,),(2)W,为真,(1),与否定的性质,(3)(WR),为真,(2),与析取的性质,(4)(WR)V,为真,前提条件,(5)V,为真,(4)(3),假言推理,(WR)V)(WR)V,(6)V(CS),为真,前提条件,(7)(CS),为真,(5)(6),假言推理,(V(CS)V(CS),(8)CS,为真,(7),与条件式的等值式,CSCS,(9)C,为真,前提条件,(10)S,为真,(8)(9),与假言推理,(CS)(C)S,(11)SU,为真,前提条件,(12)U,为真,(10)(11),假言推理,(SU)SU,(13)U,为真,前提条件,显然,(12),与,(13),矛盾，故假设有误！,应用题,天气情况,要么天晴，要么天下雨；如果天晴我去爬山，如果我去爬山那么我回来后不做饭，,结论是：如果我已做饭那么肯定天下雨了。,解：用,M,表示天晴，,R,表示天下雨，,C,表示爬山，,F,表示做饭，则问题可表示为,MR,，,