湖南大学离散数学教案命题逻辑

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,Click to edit Master title style,Click to edit Master text styles,Second level,Third level,Fourth level,Fifth level,*,湖南大学离散数学教案命题逻辑,引言,逻辑学,是推理的基础，在,社会学,、,自然科学,尤其计算机学科中得到普遍应用。,数理逻辑,是逻辑学的一个分支，也是数学的分支，它用数学方法研究推理规律，它采用符号的方法来描述和处理思维形式、思维过程和思维规律，它在,程序设计,、,数字电路,设计、,计算机,原理、,人工智能,等计算机课程得到了广泛应用。,命题逻辑,是,数理逻辑,的基础部分，,但究竟什么是,命题,？,如何,表示,命题？,如何,构造,出复杂的命题？,在本章将,讨论,这些问题。,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 命题及联结词,： 当,p、q都对,，即取值为真(,T或1,)时，“p,合取,q”的值为,真,.,1.1 命题及联结词,： 当,p、q都对,，即取值为真(,T或1,)时，“p,合取,q”的值为,真,，其他情况为,假,。,逻辑运算符,“合取”，,与汉语中,“并且、而且、同时”,含义相当,1.1 命题及联结词,： 当,p、q都不对,，即取值为假(,F或0,)时，“p,析取,q”的值为,假,，其他情况为,真,。,逻辑运算符,“析取”，,与汉语中,“或”,含义相当，但有细微的区别,1.1 命题及联结词,逻辑运算符“析取” 与汉语的“或”几乎一致但有区别：,(16)“,讲离散数学的老师是杨老师或刘老师,”，可以表示为“,讲离散数学的老师是杨老师,”“,讲离散数学的老师是刘老师,”，这两个原子命题有可能,都是对,的，这种“或”称为“,可同时为真的或,”，或简称为“,可兼或,”。,(17)“,离散数学的教室是102或302,”，,不可以,表示为“,离散数学的教室是102,”“,离散数学的教室是302,”，因为这两个原子命题,不可能都对,，只能这二种情况之一，这种“,或,”称为“,不可同时为真的或,”，或简称为“,不可兼或,”、“,排斥或,”.,这种“或”表示,不能简单,表示为“析取”，需要联合使用下面将要介绍的“,否定,”与“析取”符号，才能准确表达。,1.1 命题及联结词,:当,p是1,，p的否定,p,即为0。,逻辑运算符,“否定”，,与汉语中,“否定”,含义相当.,“,我不是数学院的学生,”可表示为“,我是数学院的学生,”,“,离散数学的教室是102或302,”,表示,离散数学的教室是102不是302,或,离散数学的教室是302不是102,p:离散数学的教室是102,q:离散数学的教室是302,上面的语句表示: (p,q)(pq),1.1 命题及联结词,:当,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 命题及联结词,:当,p与,q值相同0时,pq,为1,不同为0。 称p与q的等价式,“,我明年赚了10万当且仅当我买彩票中了大奖,”，,可以表示为“,我明年赚了10万,我买彩票中了大奖,”,对错明确的陈述语句称为,命题，其真值确定，又称为,命题常元,或,命题常项,，相当于初等数学中的“,常数,”。,数学的运算符号为“加+、减-、乘x、除、幂”，,命题逻辑的符号“合取、析取、否定、条件、双条件”,数学中用,变量x,表示,某些数,，如x,2,+x+10是代数式，,命题逻辑,用,变量,表示,任意一个命题,，如p,q,r,这时由符号与变量所构成命题表达式，简称为“,命题公式,”。,代数式的书写有规律，命题公式也有规律与约束，称满足这些规则的公式为“合式公式”，也称为“命题公式”，简称为“公式”。,定义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不是合法公式。,对于代数式x,2,+y+10，当x与y的值不确定时，该代数式的值是不确定的。,对于公式 (p1)q，由于p与q值不确定时，公式(p1)q的值不确定，因而不是命题。,只有当p与q的值确定后，公式(p1)q的值才能确定，我们可能像表1.2到表1.5一样，给出公式在各种情况下的取值，即得到这个公式的真值表。,p与q每一种取值称为p、q的一种解释,公式(pq)、pq的真值表如下表。,真值表的构造方法,：,(1),命题变元,的取值从全0开始，依次加1，直到全1，当有n个变元时，则共有,2,n,种不同的取值情况。,(2),分步骤,计算公式的值,(3)见,黑板,上写,成真赋值:如,pq为(0,0),(0,1),(1,1),成假赋值:如,pq为(1,0),公式(pq)(qp)、pq的真值表。,无论p/q取何值，这两个公式的值总相等。,公式 (pq)、 p q的真值表。,无论p/q取何值，这两个公式的值总相等。,公式pq、 pq的真值表。,无论p/q取何值，这两个公式的值总相等。,1,公式pq、qp的真值表。,无论p/q取何值，这两个公式的值总相等，若前者称为原命题，后者为逆否命题,1,公式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),的真值表完全一样，称为等值。,设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个，它们,各不相,同。,每一行,来看，命题变元的每个指派中，只有,一个,小项的值为1。,每一列,来看，每个小项仅在,一个指派中值,为1，其余7种指派中均为0。,值为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，MC，CFFR,(MR)(MR) ，MC，CFFR,应用题,MR，MC，CFFR,(1)F为真,附件前提,(2)CF为真,前提条件,(3)FC为真,(2)的等值式,(4) FC为真,(3)的等值式,(5) C为真,(1)(4)的假言推理,(6) MC为真,前提条件,(7)CM为真,(6)的等值式,(8) M为真,(5)(7)的假言推理,(9) MR为真,前提条件,(10) MR为真,(9)的等值式,(11) R为真,(8)(10)的假言推理,应用题,MR，MC，CFFR,(1)F为真,附件前提,(2)CF为真,前提条件,(3)FC为真,(2)的等值式,(4) FC为真,(3)的等值式,(5) C为真,(1)(4)的假言推理,(6) MC为真,前提条件,(7)CM为真,(6)的等值式,(8) M为真,(5)(7)的假言推理,(9) (MR)(MR)为真,前提条件,(10) (MR) (MR)为真,(9)的等值式,(11) MR (MR)为真,(10)的等值式,(12), MR为真(8)与析取的定义,(13) (MR)为真,(11)(12)的假言推理,(14),R为真(13)与合取的定义,定义2,证明推理式的规律,(1),利用“,条件等值式,”，尽可能将前提、中间结论及最终结论中的“,析取式,”转换为“,条件式,”，以便可引用,假言推理、传递律,。,(2),如果结论为,条件式,，则将条件式的,前件,做为,附加前提,。,CP原则,(3),如果,结论的否定,在前提中,多次,出现，可采 用,反证,法。,(4),每一步的推理理由可简化，如“,前提条件,”简写为“,P,”，“假言推理”可简写“M”，等值式只写“等值”或简写“E”。,(5),这种从前提出发，应用已证明的推理式，不断推出中间结论，最后推出结论的方式，称为,自然推理,，这是最常见的方式。,消解规则,证明,(AC)(BC)AB,(1) (AC),为真,前提条件,(2) A C,为真,与(1)等值,(3) BC,为真,前提条件,(4) C B,为真,与(3)等值,(5)CB,为真,与(4)等值,(6) AB,为真,(2)(5)传递律,(7) AB,为真,与(6)等值,因此当,(AC)(BC),为真时，,AB,为真。,由于,(AC(BC),中,互补,的公式,C、C,同时消失了，称“,AB,”为 “,(AC)，(BC)”,的,消解式,。,因此在采用,定义,2,进行推理时，只要,(AC)、(BC),同时为真，则可直接写出,AB,为真，从而节省大量的中间环节，提高了证明效率。,消解规则,例题,(AB)(CD)(BD)AC,利用条件式的等值式，则此题等价于证明,(AB)(CD)(BD)AC,(1) (AB)为真,前提条件,(2) (BD)为真,前提条件,(3) AD为真,当(1)(2)为真消解式AD为真,(4) CD为真,前提条件,(5) AC为真,当(3)(4)为真消解式AC为真,采用,假言推理,原则时，尽可能将,析取,转换为,条件式,。,采用,消解法,时，尽可能将,条件,式转换为,析取,。,消解法是一种,高效,的方法。,所有,推理式,消解规则,采用,定,传递律,证明了,(AC)(BC)AB,因,AB AB,故可用假言推理及CP原则证明,(1) A为真附加前提,(2) (AC),为真,前提条件,(3) A C,为真,与(1)等值,(4) C,为真,(1)(3)假言推理,(5) B C,为真,前提条件,(6)CB,为真,与(4)等值,(7) B,为真,(4)(6)假言推理,用假言推理证明了消解规则，反过来,用消解规则可证明假言推理,消解规则,用假言推理证明了消解规则,证明了,(AC)(BC)AB,反过来，用消解规则可证明假言推理,A(AB)B,AB,为真前提条件,A B,为真与,(1),等值,A,为真前提条件,B,为真,(2)(3),消解得到,“假言推理”与“消解规则”可以互相推出，因此一方推出的结论另一方也可以推出,因此习题三可由消解规则推导出来呀,Thank You !,不尽之处，恳请指正！,