离散数学课堂PPT.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 命题逻辑,1,1,命题及其表示法,1.,什么是命题,命题：能判断真假的陈述句。,命题的值叫它的真值。,真值：“真”：表示判断正确。记作,True,，用,T,表示。,“假”：表示判断错误。记作,False,，用,F,表示。,1,例,1,判断下列句子中哪些是命题？,（,1,）,2,是素数。,（,2,）雪是黑色的。,（,3,）,2+3=5,（,4,）明年,10,月,1,日是晴天。,（,5,）,3,能被,2,整除。,（,6,）这朵花真好看呀！,（,7,）明天下午有会吗？,（,8,）请关上门！,（,9,）,XY5,（,10,）地球外的星球上也有人。,（,11,）我正在说谎。,2,2,命题的符号化表示,命题的符号化就是用符号表示命题。,简单命题（或原子命题）：简单陈述句表示的命题。用,P,，,Q,，,R,P,i,Q,i,R,i,表示。,例,P:2,是偶数。,Q:,雪是黑色的。,命题常量（或命题常元）：简单命题。,命题变项（或命题变元）：真值可以变化的简单陈述句。不是命题。,例：,x+y5,3,命题变项也用,P,，,Q,，,R,P,i,Q,i,R,i,表示。,复合命题：由简单命题用联结词联结而成的命题。,4,例,2,将下列命题符号化。,（,1,）,3,不是偶数。,（,2,）,2,是素数和偶数。,（,3,）林芳学过英语或日语。,（,4,）如果角,A,和角,B,是对顶角，则角,A,等于角,B,。,解：（,1,）设,P,：,3,是偶数。,P,（,：表示并非）,（,2,）设,P,：,2,是素数；,Q,：,2,是偶数。,PQ(:,表示和,),（,3,）设,P,：林芳学过英语；,Q,：林芳学过日语。,PQ(:,表示或,),（,4,）设,P,：角,A,和角,B,是对顶角；,Q,：角,A,等于角,B,。,PQ,（个表示如果,则,）,5,1,2.,联结词,定义,1,2.1,设,P,为任一命题，,P,的否定是一个新的命题，称为,P,的,否定式，,记作,P,。,为,否定联结词。,P,P,T,F,F,T,例,p3,是偶数。,p,：,3,不是偶数。,6,定义,1,2.2,设,P,、,Q,为两命题，复合命题“,P,并且,Q”,（或“,P,和,Q”,）称为,P,与,Q,的,合取式，,记作,PQ,，为,合取联结词。,表示自然语言中的“既,又,”,，,“不仅,而且,”,，,“虽然,但是”,P,Q,P Q,T,T,T,T,F,F,F,T,F,F,F,F,7,例,3,将下列命题符号化。,（,1,）李平既聪明又用功。,（,2,）李平虽然聪明，但不用功。,（,3,）李平不但聪明，而且用功。,（,3,）李平不是不聪明，而是不用功。,解：设,P,：李平聪明；,Q,：李平用功。,（,1,）,PQ,（,2,）,PQ,（3,）,PQ,（,4,）,（,P,）,Q,注意：不是见到“和”、“与”就用。,例：“李文和李武是兄弟”，“王芳和陈兰是好朋友”是简单命题。,8,定义,1,2.3,设,P,、,Q,为两命题，复合命题“,P,或,Q”,称为,P,与,Q,的,析取式，,记作,PQ,，为,析取联结词。,P,Q,P Q,T,T,T,T,F,T,F,T,T,F,F,F,9,析取式,PQ,表示的是一种相容性或，即允许,P,和,Q,同时为真。,例：“王燕学过英语或日语”,PQ,自然语言中的“或”具有二义性，有时表示不相容的或。,例：“派小王或小李中的一人去开会”。为排斥性的或。,P,：派小王去开会；,Q,：派小李去开会。,（PQ,）（,PQ,），,（,PQ,）,（,PQ,）,10,定义,1,2.4,设,P,、,Q,为两命题，复合命题“如果,P,，则,Q”,称作,P,与,Q,的,蕴涵式，,记作,PQ,，为,蕴涵联结词。,P,Q,P Q,T,T,T,T,F,F,F,T,T,F,F,T,11,在,PQ,中，,Q,是,P,的必要条件，,P,是,Q,的充分条件。表示自然语言,“只要,P,就,Q”,，,“,P,仅当,Q”,，,“只有,Q,，才,P”,注意：,1.,在自然语言中，“如果,P,，则,Q”,中的,P,与,Q,往往有某 种内在的联系，但在数理逻辑中，,PQ,中的,P,与,Q,不一定有内在的联系。,2.,在数学中，“如果,P,，则,Q”,表示,P,为真，,Q,为真的逻辑关系，但在数理逻辑中，当,P,为假时,PQ,为真。,12,例,4,将下列命题符号化。,(1),只要不下雨，我就骑自行车上班。,(2),只有不下雨，我才骑自行车上班。,(3),若,2+2,4,，则太阳从东方升起。,(3),若,2+24,，则太阳从东方升起。,(4),若,2+2,4,，则太阳从西方升起。,(5),若,2+24,，则太阳从西方升起。,解：在（,1,）、（,2,）中，设,P,：天下雨；,Q,：我骑自行车上班。,（,1,）,PQ,（,2,）,Q P,在（,3,）（,6,）中，设,P,：,2+2,4,；,Q,：太阳从东方升起；,R:,太阳从西方升起。,（,1,）,PQ,，真值为,T,（,2,）,PQ,，真值为,T,（,3,）,PR,，真值为,F,（,4,）,PR,真值为,T,13,定义,1-2.5,设,P,、,Q,为两命题，复合命题“,P,当且仅当,Q”,称作,P,与,Q,的,等价式，,记作,P,Q,，,为,等价联结词。,PQ,表示,P,与,Q,互为充分必要条件,。,P,Q,P Q,T,T,T,T,F,F,F,T,F,F,F,T,14,例,5,将下列命题符号化。,（,1,）,2+2,4,，当且仅当,3,是奇数。,（,2,）,2+2,4,，当且仅当,3,不是奇数。,（,3,）,2+24,，当且仅当,3,是奇数。,（,4,）,224,，当且仅当,3,不是奇数。,（,5,）两圆的面积相等，当且仅当它们的半径相同。,（,6,）两角相等当且仅当它们是对顶角。,解：（,1,）（,4,）设,P,：,2+2,4,；,Q,：,3,是奇数。,（,1,）,PQ,真命题,（,2,）,PQ,假命题,（,3,）,PQ,假命题,（,4,）,PQ,真命题,（,5,）设,P,：两圆的面积相等；,Q,：两圆的面积相同。,PQ,真命题,（,6,）设,P,：两角相等；,Q,：它们是对顶角。,PQ,假命题,15,4.5,种联结词的优先级顺序：,，,16,1-3,命题公式与翻译,1.,命题公式,命题公式：由命题常量、,命题变元,、联结词、括号 等组成的符号串。,命题公式中的命题变元称作命题公式的分量。,17,定义,1,3.1,（,1,）单个命题常量或命题变 元,Q,R,Pi,Qi,Ri,，,F,，,T,是合式公式。,（,2,）如果,A,是合式公式，则（,A,）也是合式公式。,（,3,）如果,A,、,B,是合式公式，则（,AB,）、（,A B,）、（,AB,）、（,AB,）也是合式公式。,（,4,）只有有限次地应用（,1,）（,3,）组成的符号串才是合式公式。,例：,P,P,(P),(0P),P(PQ),(PQ)R)(R),是公式；,PQR,(P),PQ),不是公式。,18,2.,翻译,翻译就是把自然语言中的有些句子符号化。,复合命题符号化的基本步骤：,（,1,）分析出各简单命题，将它们符号化。,（,2,）使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。,19,例 将下列命题符号化。,（,1,）小王是游泳冠军或是百米冠军。,PQ,（,2,）小王现在在宿舍或在图书馆。,PQ,（排斥性或，不可能同时为真）,(3),选小王或小李中的一人当班长。,（,P Q,）（,PQ,）或,（,PQ,）,（排斥性或，可能同时为真）,P,Q,原命题,PQ,（,PQ,）,T,T,F,T,F,T,F,T,F,T,F,T,T,F,T,F,F,F,T,F,20,(4),如果我上街，我就去书店看看，除非我很累。,R(PQ),或（,RP,）,Q,（除非：如果不）,(5),王一乐是计算机系的学生，他生于,1968,年或,1969,年，他是三好学生。,P,（,Q R,）,S,（,6,）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。,A,：我们要做到身体好,B,：我们要做到学习好,C,：我们要做到工作好,P,：我们要为祖国四化建设面奋斗。,命题符号化形式为：（,ABC,）,P,21,1,4,真值表与等价公式,1.,真值表,定义,1,4.1,含,n,个（,n1,）个命题变元（分量）的命题公式，共有,2,n,组真值指派。将命题公式,A,在所有真值指派之下取值的情况列成表，称为,A,的真值表。,构造真值表的步骤：,(1),找出命题公式中所含的所有命题变元,P1,P2,Pn,。列出所有可能的真值指派。,(2),对应每种真值指派，计算命题公式的各层次的值，直到最后计算出命题公式的值。,22,例,1,构造求,PQ,的真值表。,P,Q,P,PQ,T,T,F,T,T,F,F,F,F,T,T,T,F,F,T,T,23,例,2,给出（,PQ,）,P,的真值表。,P,Q,PQ,P,（,PQ,）,P,T,T,T,F,F,T,F,F,F,F,F,T,F,T,F,F,F,F,T,F,24,例,3,给出（,PQ,）（,PQ,）的真值表。,P,Q,P,Q,PQ,PQ,（,PQ,）（,PQ,）,T,T,F,F,T,F,T,T,F,F,T,F,F,F,F,T,T,F,F,F,F,F,F,T,T,F,T,T,25,例,4,给出,（,PQ,）（,PQ,）的真值表。,P,Q,PQ,（,PQ,）,P,Q,PQ,（,PQ,）（,PQ,）,T,T,T,F,F,F,F,T,T,F,F,T,F,T,T,T,F,T,F,T,T,F,T,T,F,F,F,T,T,T,T,T,由以上例子可以看出有一类命题公式不论各命题变元作何种批派，其值永为真（假），我们把这类公式记为,T,（,F,）。如例,4,和例,2,26,2,等价公式,从真值表中可以看到，有些命题公式在分量的各种指派下，其对应的真值都完全相同，如,PQ,与,PQ,的对应真值相同。,P,Q,P,PQ,PQ,T,TF,T,T,T,F,F,F,F,F,T,T,T,T,F,F,T,T,T,（,PQ,）（,PQ,）与,PQ,对应的真值相同。,27,定义,1,4.2,给定两个命题公式,A,和,B,，设,P,1,，,P,2,，,，,P,n,为所有出现于,A,和,B,中的原子变元,若给,P,1,，,P,2,，,，,P,n,任一组真值指派,A,和,B,的真值都相同,则称,A,和,B,是,等价,的或,逻辑相等,。记作,AB,。,例,5,证明,PQ,（,PQ,）（,QP,）,证明 列出真值表,P,Q,PQ,QP,(PQ,）,(QP,）,PQ,T,T,T,T,T,T,T,F,F,T,F,F,F,T,T,F,F,F,F,FT,T,T,T,28,24,个重要的等价式,PP,双重否定律,PPP,等幂律,PPP,PQQP,交换律,PQQP,（,PQ,）,RP,（,QR,）结合律,（,PQ,）,RP,（,QR,）,P,（,QR,）（,PQ,）（,PR,）分配律,P,（,QR,）（,PQ,）（,PR,）,（,PQ,）,PQ,德,摩根律,（,PQ,）,PQ,29,P,（,PQ,）,P,吸收律,P,（,PQ,）,P,PT T,零律,PF F,PFP,同一律,PT P,PP T,排中律,PP F,矛盾律,PQ PQ,蕴涵等价式,P,Q,（,PQ,）（,QP,）等价等价式,PQ QP,假言易位,P,Q P,Q,等价否定等价式,PQ,）（,PQ,）,P,归谬论,其中,P,、,Q,和,R,代表任意的命题公式,。,30,例,6,验证吸收律,P,（,PQ,）,P,和,P,（,PQ,）,P,P,Q,P,Q,P,（,PQ,）,PQ,P,（,PQ,）,T,T,T,T,T,T,T,F,F,T,T,T,F,T,F,F,T,F,F,F,F,F,F,F,31,定义,1-4.3,如果,X,是合式公式,A,的一部分,且,X,本身也是一个合式 公式,则称,X,为公式,A,的子公式。,定理,1,4.1,如果,X,是合式公式,A,的子公式，若,XY,，如果将,A,中的,X,用,Y,来置换，所得到公式,B,与公式,A,等价，即,AB,。,证明,因为在相应变元的任一种指派下，,X,与,Y,的真值相同，故以,Y,取代,X,后，公式,B,与公式,A,在相应的指派下，其真值必相同，故,AB,。,满足定理,1,4.1,的置换称为等价置换（等价代换）,32,例,7,证明,PQ,（,PQ,）,证明,PQ PQ,，（根据蕴涵等价式）,PQ,（,Pq,），（德,摩根律）,即,Pq,（,Pq,）,33,例,8,证明,P(QR)(PQ)R,证明,P,(QR),P(,QR,),（蕴涵等价式）,P(QR),（蕴涵等价式）,(PQ)R,（结合律）,(PQ)R,（德,摩根律）,(PQ)R,（蕴涵等价式）,34,例,9,证明,P(PQ)(PQ),证明,P,P,1,同一律,),P(QQ),（排中律）,(PQ)(PQ),（分配律）,35,练习,1.,证明,Q(PQ)P)T;,2.,证明,(PP)(QQ)R)F,3.,证明,(PQ)PP,36,1,证明,Q(PQ)P),Q(PP)(PQ),（分配律）,Q(F(PQ),（矛盾律）,Q(PQ),（同一律）,Q(PQ),（德,摩根律）,(QQ)P,（结合律）,TP,（排中律）,T,（零律）,37,2.,证明,(PP)(QQ)R),T(QQ)R),（排中律）,T(FR),（矛盾律）,TF,（零律）,TF,（蕴涵等值式）,FFF,（等幂律）,38,3.,证明,(PQ)P,(PQ)P,（蕴涵等价值式）,P,（吸收律）39,1-5,重言式与蕴涵式,定义,1,5.1,给定一命题公式，若无论对分量作什么样的指,派，其对应的真值永为,T,，则称该命题公式 为,重言式,或,永真式,。,定义,1,5.2,给定一命题公式，若无论对分量作什么样的指,派，其对应的真值永为,F,，则称该命题公式 为,矛盾式,或,永假式,。,40,定理,1,5.1,任何两个重言式的合取或析取，仍然是一个重言式。,定理,1,5.2,一个 重言式，对同一分量，都 用任何合式公式 置换，其结果仍为一重言式。,证明,由于重言式的真值与分量的指派无关，帮对同一分量以任何合式公式置换后，重言式的真值仍永为真。,对于矛盾式也有类似于定理,1,5.1,和定理,5,1.2,的结果。,41,例,1,证明（,PS,）,R,）,（,P,S,）,R,）为重言式。,证明 因为,PP,T,，用,（,PS,）,R,）置换,P,得,（,PS,）,R,）,（,PS,）,R,）,T,42,定理,1,5.3,设,A,、,B,为两命题公式,A,B,，当且仅当,A,B,为一个重言式。,证明 若,AB,，则,A,、,B,有相同的真值，即有,AB,永为,T,。,若,AB,为重言式，则,AB,永为,T,，故,A,、,B,的真值相同，即,AB,。,43,例,2,证明,（,PQ,）（,PQ,）,证明 做,（,PQ,）（,PQ,）的真值表。,P,Q,PQ,P,Q,（,PQ,）,PQ,PQ,）,PQ,T,T,T,F,F,F,F,T,T,F,F,F,T,T,T,T,F,T,F,T,F,T,T,T,F,F,F,T,T,T,T,T,由以上真值表可知，,（,PQ,）,PQ,为重言式，根据定理,1,5.3,得,（,PQ,）（,PQ,）,44,定义,1,5.3,当且仅当,P,Q,是重言式时，我们称,“,P,蕴涵,Q,”,，并记作,PQ,。,做,PQ QP,，,PQ,，,Qp,的真值表,P,Q,P,Q,PQ,Q,P,QP,P,Q,T,T,F,F,T,T,T,T,T,F,F,T,F,F,T,T,F,T,T,F,T,T,F,F,F,F,T,T,T,T,T,T,由此得,PQ QP,，,QP PQ,，因此要,PQ,，只要证明,QP,，反之亦然。,45,要证明,PQ,，即证,PQ,是重言式，对于,PQ,来说，除,P,的真值取,T,，,Q,的真值取,F,这样一种指派时，,PQ,的真值为,F,外，其余情况,PQ,的真值为,T,，故要征,PQ,，只要对条件,PQ,的前件,P,，指定真值为,T,，若由此指出,Q,的真值为,T,，则,PQ,为重言式，即,PQ,成立；同理，如对条件命题,PQ,中，假定后件,Q,的真值为,F,，若由此推出,P,的真值为,F,，即推证了,QP,。故,PQ,成立。即,若,P,为,T,时，推出,Q,为,T,或若,Q,为,F,时，推出,P,为,F,则,PQ,。,46,例1,推证,Q,（,PQ,）,P,证法,1,假定,Q,（,PQ,）为,T,，则,Q,为,T,，且,PQ,为,T,。,所以,Q,为,F,，,PQ,为,T,，,所以,P,为,F,，故,P,为,T,。,证法,2,假定,P,为,F,，则,P,为,T,，,若,Q,为,F,，则,PQ,为,F,，,Q,（,PQ,）为,F,，,若,Q,为,T,，则,Q,为,F,，,Q,（,PQ,）为,F,，,所以,Q,（,PQ,）,P,47,常用的蕴涵式如下：,PQ P,PQ Q,PPQ,PPQ,QPQ,（,PQ,）,P,（,PQ,）,Q,P,（,PQ,）,Q,Q,（,PQ,）,p,P,（,PQ,）,Q,（,PQ,）（,QRPR,（,PQ,）（,PR,）（,QR,）,R,（,PQ,）（,RS,）（,PR,）（,QS,）,（,P,Q,）（,Q,R,）（,P,R,）,48,定理,1,5.4,设,P,、,Q,为任意两个 命题公式，,P,Q,的充分,必要条件是,P,Q,且,Q,P,证明 若,PQ,，则,P,Q,为重言式。,因为,PQ ,（,P,Q,）（,QP,），,故,PQ,为,T,，且,QP,为,T,，,因为,PQ,且,QP,成立。,反之，若,PQ,且,QP,，,则,PQ,为,T,，且,QP,为,T,，,因此,PQ,（,PQ,）（,QP,）为,T,，,即,PQ,这个定理也可以作为两个公式等价的定义。,49,蕴涵的几个常用的性质：,（,1,）设,A,、,B,、,C,为合式公式，若,AB,且,A,为重言式，则,B,也是重 言式。,证明 因为,AB,永为,T,，所以当,A,为,T,时，,B,必,T,。,（,2,）若,AB,，,BC,，则,AC,证明 由,AB,，,BC,得,AB,，,BC,为重言式,所以（,AB,）（,BC,）为重言式，,根据（,PQ,）（,QR,）,PR,所以（,AB,）（,BC,）,AC,，,由性质（,1,）得：,AC,为重言式，即,AC,50,（,3,）,AB,，且,AC,，那么,A,（,BC,）,证明 由假设知,AB,，,AC,为重言式。,设,A,这,T,，则,B,、,C,为,T,，故,BC,为,T,，,因此,A,（,BC,）为,T,，,若,A,为,F,，则,A,（,BC,）为,T,，,所以,A,（,B,C,）,51,（,4,）若,AB,且,CB,，则,AC,B,证明 因为,AB,为,T,，,CB,为,T,，,故（,A,B,）（,C B,）为,T,，,则（,AC,）,B,为,T,，,即,（,AC,）,B,为,T,，,即 （,AC,）,B,为,T,，,所以（,AC,）,B,52,1,6,其他联结词,定义,1,6.3,设,P,、,Q,是两个命题公式，复合命题,P Q,称作,P,和,Q,的“与非”。,PQ,（,PQ,）,P,Q,P Q,T,T,F,T,F,T,F,T,T,F,F,T,53,联结词“”的几个性质：,（,1,）,PP ,（,PP,）,p,（,2,）（,PQ,）（,PQ,）,（,PQ,）,PQ,（,3,）（,PP,）（,QQ,）,PQ,（,Pq,）,PQ,54,定义,1,6.3,设,P,、,Q,是两个命题公式，复合命题,P,Q,称作,P,和,Q,的“或非”。,P,Q,（,P,Q,）,P,Q,P Q,T,T,F,T,F,F,F,T,F,F,F,T,55,联结词“,”的几个性质：,（,1,）,P,P ,（,PP,）,p,（,2,）（,P Q,）,（,PQ,）,（,PQ,）,PQ,（,3,）（,PP,）（,QQ,）,PQ PQ,当有,n,个命题变元时，可构成,2,2,n,种不等价的命题公式，如,n,2,时，有,16,种不等价的命题公式。，见,27,页表,1,6.5,。,56,最小联结词组：对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。,由于（,1,）（,P,Q,）,（,PQ,）（,QP,）,（,2,）（,PQ,）,PQ,（,3,）,PQ,（,P Q,）,（,4,）,PQ,（,Pq,）,故由“,”,、“”、“”，“”、“”这五个联结词组成的命题公式，必可以由,，,或,，,组成的命题公式所替代。,57,1,7,对偶与范式,定义,1,7.1,在给定的命题公式,A,中，将换成，换成，若有特殊变元,F,和,T,亦相互取代，所得命题公式,A*,称为,A,的对偶式。,A,和,A*,互为对偶式。,例,1:PQ,与,PQ,(PQ),与,(PQ),(PQ)R,与,(PQ)R,(PT)Q,与,(P F)Q,均为对偶式,.,例,2,：,PQ,、,P Q,的对偶式。,解：,PQ(PQ),，,PQ,的对偶式为,(PQ),P Q,（,PQ,）,，,P Q,的对偶式为,(PQ),58,定理,1,7.1,设,A,和,A*,互为对偶式,P,1,P,2,P,n,，是出现在,A,和,A*,中的全部的命题变元,则,A(P,1,P,2,P,n,)A*(P,1,P,2,P,n,),A(P,1,P,2,P,n,)A*(P,1,P,2,P,n,),例,:,设,A(P,QR)P(QR),得,:A*(P,Q,R)P(QR),(1),由知,:A(P,Q,R)P(QR),由知,:A*(P,Q,R)P(QR),所以,:A(P,Q,R)A*(P,Q,R),类似地,有,A(P,Q,R)A*(P,Q,R),59,定理,1,7.2,设,P,1,P,2,P,n,是出现有命题公式,A,和,B,中的所有命题变元，若,A B,，则,A*B*,。,证明：因为,A B,，,即,A(P1,P2,Pn)B(P1,P2,Pn),是重言式，,A(P1,P2,Pn)B(P1,P2,Pn),是重言式，,故,A(P1,P2,Pn)B(P1,P2,Pn),由定理,1,7.1,得,A*(P1,P2,Pn)B*(P1,P2,Pn),因此,A*B*,60,例,4,如果,A(P,Q,R),是,P,（,Q,（,RP,），求它的对偶式,A*(P,Q,R),。并求与,A,及,A*,等价，但仅包含联结词“,”,、“”、“”的公式。,解：因,A(P,Q,R),是,P,（,Q,（,RP,）,故,A*(P,Q,R),是,P,（,Q,（,RP,）,但,P,（,Q,（,RP,）,P,（,Q,（,R,P,）,（,P,（,Q,（,RP,）,所以,P,（,Q,（,RP,）,(P,（,Q,（,RP,）,),61,定义,1,7.2,一个命题公式 称为,合取范式,，当且仅当它具有形式,A,1,A,2,A,n,（,n1,）。其中A,1,，,A,2,，,，,A,n,都是命题变元或其否定所组成的析取式。,例,P(PQ)(PP)(PR),定义,1,7.3,一个命题公式 称为,析取范式,，当且仅当它具有形式,A,1,A,2,A,n,（,n1,）。其中,A,1,，,A,2,，,，,A,n,都是命题变元或其否定所组成的合取式。,例,(PQR),(PQ),(,PQR,),62,求合取范式或 析取范式的步骤：,（,1,）将公式中的联结词化归成,、。,（,2,）将,消去或内移。,（,3,）利用分配律、交换律求合取范式或析取范式。,（求合取范式：对；,求析取范式：对 ）,注意任何命题的析取范式和合取范式都不是唯一的。,63,例求下面命题公式的合取范式和析取范式。,（,PQ,）,R,）,P,解（,1,）求合取范式,（,PQ,）,R,）,P,（,（,PQ,）,R,）,P,(PQ)R)P,(PQ)R)P,(PQ)R)P,(PQ)R)P,(PQ)R)P,(PQP)(RP),（,PQ,）,(RP),(2),求析取范式,(PQ)R)P,(PR)(QR)P,P,（,P,R,）,(QR),P(QR),64,练习：求下面命题公式的合取范式和析取范式。,（,1,）求合取范式,(PQ),R,(PQ),R,(PQ)R)(R(PQ),(PQ)R)(R(PQ),(PQ)R)(RPQ),(PR)(QR)(RPQ),（,2,）求析取范式,(PQ,),R)RPQ),（,(PQ)(RPQ),）,(R(RPQ),(PQ)R)(PQ)P)(PQ)Q),(RR)(RP)(RQ),(PQR),(PPQ),(,PQQ,),(RR),(PR)(QR),(PQR)(PR)(QR),65,定义,1,7.4,n,个命题变元的合取式，称作布尔合取或小项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,n,个命题变元 共有,2,n,个小项。,例两个命题变元,P,和,Q,，其小项为：,PQ,，,PQ,，,PQ,，,PQ,66,3,个命题变项,P,、,Q,、,R,可形成,8,个小项：,m,000,PQR,m,001,PQR,m,010,PQR,m,011,PQR,m,100,PQR,M,101,PQR,m,110,PQR,m,111,PQR,67,小项的性质：,（,1,）每一个小项当其真值指派与编码相同时，其真值为,T,，其余均为,F,。,（,2,）任意两个不同小项的合取永为,F,。,（,3,）,m,0,m,1,m,2,m,3,m,4,m,5,m,6,m,7,T,68,定义,1,7.3,对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。,定理,1,7.3,在真值表中，一个 公式的真值为,T,的指派所对小项的析取，即为此公式的主析取范式。,69,例,6,给定,P Q,，,PQ,和,（,PQ,），求这些公式的主析取范式。,解：真值表如下：,P,Q,P,Q,PQ,（,PQ,）,T,T,T,T,F,T,F,F,T,T,F,T,T,T,T,F,F,T,F,T,故,P Q,（,PQ,）（,PQ,）（,PQ,）,PQ,（,PQ,）（,PQ,）（,PQ,）,（,PQ,）（,PQ,）（,PQ,）（,PQ,）,70,例,7,设一公式,A,的真值表如下，求公式,A,的主析取范式。,P,Q,R,A,T,T,T,T,T,T,F,F,T,F,T,F,T,F,F,T,F,T,T,F,F,T,F,F,F,F,T,F,F,F,F,T,解 公式,A,的主析取范式 为：,A,（,PQ,R,）（,PRR,）（,PQR,）,71例,8,求（,PQ,）（,PR,）（,QR,）的主析取范式。,解：原式（,PQ,（,RR,）,（,PR,（,QQ,）,（,QR,（,Pp,）,（,PQR,）（,PQR,）,（,PQR,）（,PQR,）,（,PQR,）（,PQR,）,（,PQR,）（,PQR,）,（,PQR,）（,PQR,）,72,例,9,求,P,（,P,Q,）,（,QP,）的主析取范式。,解：原式,P,（,P,Q,）,（,QP,）,P,（,PQP,）（,QQP,）,P,（,QP,）,P,（,QQ,）（,PQ,）,（,PQ,）（,PQ,）（,PQ,）,73,求主析取范式的步骤：,（,1,）求析取范式。,（,2,）去掉永假的析取项。,（,3,）去掉重复的合取项、合并相同变元。,（,4,）对合取项补入没出现的命题变元。（,PP,）,74,定义,1,7.6,n,个命题变元的析取式，称作布尔析取或大项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,n,个命题变元 共有,2n,个小项。,例 两个命题变元,P,和,Q,，其小项为：,PQ,，,PQ,，,PQ,，,PQ,75,3,个命题变项,P,、,Q,、,R,可形成,8,个大项：,M,000,PQR,M,001,PQ,R,M,010,P,QR,M,011,P,Q,R,M,100,PQR,M,101,PQ,R,M,110,P,QR,M,111,P,Q,R,76,大项的性质：,（,1,）每一个大项当其真值指派与编码相同时，其真值为,F,，其余均为,T,。,（,2,）任意两个不同大项的析取永为,T,。,（,3,）,M,0,M,1,M,2,M,3,M,4,M,5,M,6,M,7,F,77,定义,1,7.7,对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。,定理,1,7.4,在真值表中，一个公式的真值为,F,的指派所对大项的合取，即为此公式的主合取范式。,78,例,10,利用真值表求（,PQ,）（,PR,）的主合取范式与主析取范式。,P,Q,R,P,Q,P,R,（,PQ,）（,PR,）,T,T,T,T,F,T,TT,F,T,F,T,T,F,T,F,F,F,T,F,F,F,F,F,F,T,T,F,T,T,F,T,F,F,F,F,F,F,T,F,T,T,F,F,F,F,F,F,79,主合取范式：（,PQ,R,）（,PQR,）（,P,QR,）（,PQR,）,主析取范式：（,PQR,）（,PQR,）（,PQR,）（,PQR,）,80,求主合取范式的步骤：,（,1,）求合取范式。,（,2,）去掉所有为,T,的合取项。,（,3,）合并相同的析取项和变元。,（,4,）补入没出现的命题变元。（即添加,PP,）,81,例,11,求,（,PQ,）（,PR,）的主合取范式。,解：原式（,PQ,）,P,）（,PQ,）,R,Pp,）（,Qp,）（,PR,）（,QR,）,（,Qp,）（,PR,）（,QR,）,（,QP,（,RR,）,（,PR,（,QQ,）,（,QR,（,PP,）,（,QPR,）（,QPR,）,（,PRQ,）（,PRQ,）,（,QRP,）（,QRP,）,（,PQ,R,）（,P,Q,R,）,（,P,Q,R,）（,PQR,）,82,用,表示小项的析取,用表示大项的合取,例如,（,PQ,）（,PR,）,（,PQR,）（,PQR,）,（,PQR,）（,PQR,）,M,000,M,010,M,100,M,101,0,2,4,5,m,001,m,011,m,110,m,111,1,3,6,7,83,1-8推理理论,推理是从前提推出结论的思维过程,前提是指已知的命题公式,结论是从前提出发应用推理规则推出来的命题公式。前提可以是多个。,定义,1,8.1,设,H,1,，,H,2,，,，,H,n,，,C,是命题公式，若（,H,1,H,2,H,n,）,C,为重言式,则称,C,是一组前提,H,1,H,2,H,n,的有效结论。记作：,H,1,H,2,H,n,C,真值表法,推理方法 直接证法,间接证法,84,（,1,）真值表法,若,H,1,，,H,2,，,，,H,n,都为,T,的行，,C,也为真；,或若,C,为假的行，,H,1,，,H,2,，,，,H,n,中至少有一个为假,则,H,1,H,2,H,n,C,成立。,85,例,1,一份统计表格的错误或者是由于材料不可靠，或者是由于计算有错误；这份统计表格的错误不是由于材料不可靠，所以这份统计表格是由于计算有错误。,解：设,P,：统计表格的错误是由于材料不可靠。,Q,：统计表格的错误是由于计算不可靠。,前提是：,PQ,，,P,，结论是：,Q,，即证明,（,PQ,）,P Q,P,Q,PQ,P,T,T,T,F,T,F,T,F,F,T,T,T,F,F,F,T,故（,PQ,）,P Q,86,例,2,如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可以得到解答。,解：设,P,：张老师来了。,Q,：李老师来了。,R,：这个问题可以得到解答。,本题可译为：,（,P R,）（,QR,）（,PQ,）,R,87,P,Q,R,P,R,Q,R,PQ,T,T,T,T,T,T,T,T,F,F,F,T,T,F,T,T,T,T,T,F,F,F,T,T,F,T,T,T,T,T,F,T,F,T,F,T,F,F,T,T,T,F,F,F,F,T,T,F,88,（,2,）直接证法,就是由一组前提，利用一些公认的推理规则，根据已知的等价公式或蕴涵公式，推出有效结论。,P,规则：前提在推导过程中随时可以引用。,T,规则：已经推出的公式在以后的推导过程中可随时引用。,常用蕴涵式见,43,页表,1,8.3,89,例,1,证明（PQ,）,（,P,R,）,（,QS,）,S,R,证法,1,（,1,）,PQ P,（,2,）,P,Q T,（,1,）,E,（,3,）,QS P,（,4,）,PS T,（,2,），（,3,）,I,（,5,）,SP T,（,4,）,E,（,6,）,PR P,（,7,）,SR T,（,5,），（,6,）,I,（,8,）,SR T,（,7,）,E,90,证法,2,（,1,）,PR P,（,2,）,PQRQ T,（,1,）,I,（,3,）,QS P,（,4,）,QRSR T,（,3,）,I,（,5,）,PQSR T,（,2,），（,4,）,I,（,6,）,PQ P,（,7,）,SR T,（,5,），（,6,）,I,91,例,2,证明（,WR,）,V,，,VCS,，,SU,，,C U W,证明,（,1,）,C U P,（,2,）,U T,（,1,）,I,（,3,）,SU P,（,4,）,S T,（,2,）,（,3,）,I,(5)C T,（,1,）,I,(6)C S T(4),(5)I,(7)(C S)T(6)E,(8),（,WR,）,V P,(9)V(CS)P,(10),（,WR,）,(CS)T(8),(9)I,(11)(,（,WR,）,T(7),(10)I,(12)W R T(11)E,(13)W T(12)E,92,(3),间接证法,1(,归谬法,),要证,H,1,H,2,H,n,C,即要证,H,1,H,2,H,n,C,为重言式,H,1,H,2,H,n,C,(H,1,H,2,H,n,)C,(H,1,H,2,H,n,C),因此只要证,H,1,H,2,H,n,C,为矛盾式,.,93,例,3,证明,AB,(BC),可逻辑推出,A,证明,(1)AB P,(2)A P(,附加前提,),(3)(BC)P,(4)BC T(3)E,(5)B T(1),(2)I,(6)B T(4)I,(7)BB(,矛盾,)T(5),(6)I,94,例,4,证明,(PQ)(PR)(QS)SR,证明,(1)(SR)P,(2)SR T(1)E,(3)PQ P,(4)PQ T(3)E,(5)QS P,(6)PS T(4),(5)I,(7)SP T(6),(8)(S,R,)(P,R,)T(7)I,(9)PR T(2),(8)I,(10)PR P,(11)P R T(10)E,(12)(P R,)T(11)E,(13),(P R,),(P R,)(,矛盾,)T(9),(12)I,95,(4),间接证法,2(,附加前提法,),要证,H1H2Hn RC,只要证,(H1H2Hn)(R C),为重言式,(H1H2Hn)(R C),(H1H2Hn)(R C),(H1H2HnR)C,(H1H2Hn R)C,只要证,(H1H2Hn,R,)C,由,(SR)C,证得,S(R C),称为,CP,规则,。,96,例,5,证明,A(BC),DA,B,重言蕴涵,DC,证明,(1)D P(,附加前提,),(2)DA P,(3)A T(1),(2)I,(4)A(BC)P,(5)BC T(3),(4)I,(6)B P,(7)C T(5),(6)I,(8)DC CP,97,例,6,设有下列情况,结论是否有效,?,(a),或者是天晴,或者是下雨。,(b),如果是天晴，我去看电影。,(c),如果我去看电影，我就不看书。,结论：如果我在看书则天在下雨。,解 若设,M,：天晴。,Q,：下雨。,S,：我看电影。,R,：我看书。,即证：,M,Q,，,M,S,，,SR,，推出,RQ,其中,MQ(M,Q,）,98,(1)R P,（附加前提）,(2)