资源描述
单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第一章 命题逻辑,1,1,命题及其表示法,1.,什么是命题,命题：能判断真假的陈述句。,命题的值叫它的真值。,真值：“真”：表示判断正确。记作,True,，用,T,表示。,“假”：表示判断错误。记作,False,，用,F,表示。,例,1,判断下列句子中哪些是命题？,（,1,）,2,是素数。,（,2,）雪是黑色的。,（,3,）,2+3=5,（,4,）明年,10,月,1,日是晴天。,（,5,）,3,能被,2,整除。,（,6,）这朵花真好看呀！,（,7,）明天下午有会吗？,（,8,）请关上门！,（,9,）,X+Y5,（,10,）地球外的星球上也有人。,（,11,）我正在说谎。,2,命题的符号化表示,命题的符号化就是用符号表示命题。,简单命题（或原子命题）：简单陈述句表示的命题。用,P,，,Q,，,R,P,i,Q,i,R,i,表示。,例,P:2,是偶数。,Q:,雪是黑色的。,命题常量（或命题常元）：简单命题。,命题变项（或命题变元）：真值可以变化的简单陈述句。不是命题。,例：,x+y,5,命题变项也用,P,，,Q,，,R,P,i,Q,i,R,i,表示。,复合命题：由简单命题用联结词联结而成的命题。,例,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,（个表示如果,则,）,1,2.,联结词,定义,1,2.1,设,P,为任一命题，,P,的否定是一个新的命题，称为,P,的,否定式，,记作,P,。,为,否定联结词。,P,P,T,F,F,T,例,p,：,3,是偶数。,p,：,3,不是偶数。,定义,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,例,3,将下列命题符号化。,（,1,）李平既聪明又用功。,（,2,）李平虽然聪明，但不用功。,（,3,）李平不但聪明，而且用功。,（,3,）李平不是不聪明，而是不用功。,解：设,P,：李平聪明；,Q,：李平用功。,（,1,）,PQ,（,2,）,PQ,（,3,）,PQ,（,4,）,（,P,）,Q,注意：不是见到“和” 、“与”就用 。,例：“李文和李武是兄弟”，“王芳和陈兰是好朋友”是简单命题。,定义,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,析取式,PQ,表示的是一种相容性或，即允许,P,和,Q,同时为真。,例：“王燕学过英语或日语”,PQ,自然语言中的“或”具有二义性，有时表示不相容的或。,例：“派小王或小李中的一人去开会” 。为排斥性的或。,P,：派小王去开会；,Q,：派小李去开会。,（,PQ,）（,PQ,） ，,（,PQ,）,（,PQ,）,定义,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,在,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,为真。,例,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,定义,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,例,5,将下列命题符号化。,（,1,）,2+2,4,，当且仅当,3,是奇数。,（,2,）,2+2,4,，当且仅当,3,不是奇数。,（,3,）,2+24,，当且仅当,3,是奇数。,（,4,）,2+24,，当且仅当,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,假命题,4.5,种联结词的优先级顺序：,，,1-3,命题公式与翻译,1.,命题公式,命题公式：由命题常量、,命题变元,、联结词、括号 等组成的符号串。,命题公式中的命题变元称作命题公式的分量。,定义,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),不是公式。,2.,翻译,翻译就是把自然语言中的有些句子符号化。,复合命题符号化的基本步骤：,（,1,）分析出各简单命题，将它们符号化。,（,2,）使用合适的联结词，把简单命题逐个联结起来，组成复合命题的符号化表示。,例 将下列命题符号化。,（,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,(4),如果我上街，我就去书店看看，除非我很累。,R(PQ),或 （,RP,）,Q,（除非：如果不）,(5),王一乐是计算机系的学生，他生于,1968,年或,1969,年，他是三好学生。,P,（,Q R,）,S,（,6,）我们要做到身体好、学习好、工作好，为祖国四化建设而奋斗。,A,：我们要做到身体好,B,：我们要做到学习好,C,：我们要做到工作好,P,：我们要为祖国四化建设面奋斗。,命题符号化形式为：（,ABC,）,P,1,4,真值表与等价公式,1.,真值表,定义,1,4.1,含,n,个（,n1,）个命题变元（分量）的命题公式，共有,2,n,组真值指派。将命题公式,A,在所有真值指派之下取值的情况列成表，称为,A,的真值表。,构造真值表的步骤：,(1),找出命题公式中所含的所有命题变元,P1,P2,Pn,。列出所有可能的真值指派。,(2),对应每种真值指派，计算命题公式的各层次的值，直到最后计算出命题公式的值。,例,1,构造求,PQ,的真值表。,P,Q,P,PQ,T,T,F,T,T,F,F,F,F,T,T,T,F,F,T,T,例,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,例,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,例,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,2,等价公式,从真值表中可以看到，有些命题公式在分量的各种指派下，其对应的真值都完全相同，如,PQ,与,PQ,的对应真值相同。,P,Q,P,PQ,PQ,T,T,F,T,T,T,F,F,F,F,F,T,T,T,T,F,F,T,T,T,（,PQ,）（,PQ,）与,PQ,对应的真值相同。,定义,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,F,T,T,T,T,24,个重要的等价式,PP,双重否定律,PPP,等幂律,PPP,PQQP,交换律,PQQP,（,PQ,）,RP,（,QR,）结合律,（,PQ,）,RP,（,QR,）,P,（,QR,）（,PQ,）（,PR,）分配律,P,（,QR,）（,PQ,）（,PR,）,（,PQ,）,PQ,德,摩根律,（,PQ,）,PQ,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,代表任意的命题公式,。,例,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,定义,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,的置换称为等价置换（等价代换）,例,7,证明,PQ,（,PQ,）,证明,PQ PQ,， （根据蕴涵等价式）, PQ ,（,Pq,），（德,摩根律）,即,Pq,（,Pq,）,例,8,证明,P(QR) (PQ) R,证明,P,(QR),P(,QR,),（蕴涵等价式）,P(QR),（蕴涵等价式）,(PQ) R,（结合律）,(PQ) R,（德,摩根律）,(PQ) R,（蕴涵等价式）,例,9,证明,P(PQ) (PQ),证明,P,P,1,(,同一律,),P(QQ),（排中律）,(PQ) (PQ),（分配律）,练习,1.,证明,Q( (PQ) P)T;,2.,证明,(PP) ( (QQ) R) F,3.,证明,(PQ) PP,1,证明,Q( (PQ) P),Q( (PP) (PQ) ),（分配律）,Q( F (PQ) ),（矛盾律）,Q(PQ),（同一律）,Q(PQ),（德,摩根律）,(QQ) P,（结合律）,TP,（排中律）,T,（零律）,2.,证明,(PP) ( (QQ) R),T( (QQ) R),（排中律）,T(FR),（矛盾律 ）,TF,（零律）,TF,（蕴涵等值式）,FFF,（等幂律）,3.,证明,(PQ) P,(PQ) P,（蕴涵等价值式）,P,（吸收律）,1-5,重言式与蕴涵式,定义,1,5.1,给定一命题公式 ，若无论对分量作什么样的指,派，其对应的真值永为,T,，则称该命题公式 为,重言式,或,永真式,。,定义,1,5.2,给定一命题公式 ，若无论对分量作什么样的指,派，其对应的真值永为,F,，则称该命题公式 为,矛盾式,或,永假式,。,定理,1,5.1,任何两个重言式的合取或析取，仍然是一个重言式。,定理,1,5.2,一个 重言式，对同一分量，都 用任何合式公式 置换，其结果仍为一重言式。,证明,由于重言式的真值与分量的指派无关，帮对同一分量以任何合式公式置换后，重言式的真值仍永为真。,对于矛盾式也有类似于定理,1,5.1,和定理,5,1.2,的结果。,例,1,证明 （,PS,）,R,）,（,P,S,）,R,）为重言式。,证明 因为,PP,T,，用,（,PS,）,R,）置换,P,得,（,PS,）,R,）,（,PS,）,R,）,T,定理,1,5.3,设,A,、,B,为两命题公式,A,B,，当且仅当,A,B,为一个重言式。,证明 若,AB,，则,A,、,B,有相同的真值，即有,AB,永为,T,。,若,AB,为重言式，则,AB,永为,T,， 故,A,、,B,的真值相同，即,AB,。,例,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,）,定义,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,，反之亦然。,要证明,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,。,例,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,常用的蕴涵式如下：,PQ P,PQ Q,PPQ,PPQ,QPQ,（,PQ,） ,P,（,PQ,） ,Q,P,（,PQ,）,Q,Q,（,PQ,）,p,P,（,PQ,）,Q,（,PQ,）（,QR,）,PR,（,PQ,）（,PR,）（,QR,）,R,（,PQ,）（,RS,）（,PR,）（,QS,）,（,P,Q,）（,Q,R,）（,P,R,）,定理,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,这个定理也可以作为两个公式等价的定义。,蕴涵的几个常用的性质：,（,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,（,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,）,（,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,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,联结词“”的几个性质：,（,1,）,PP ,（,PP,）,p,（,2,） （,PQ,）（,PQ,）,（,PQ,）,PQ,（,3,）（,PP,）（,QQ,）,PQ,（,Pq,）,PQ,定义,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,联结词“,”的几个性质：,（,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,。,最小联结词组：对于任何一个命题公式，都能由仅含这些联结词的命题公式等价代换。,由于（,1,）（,P,Q,）,（,PQ,）（,QP,）,（,2,）（,PQ,）,PQ,（,3,）,PQ,（, P Q,）,（,4,）,PQ,（,Pq,）,故由“,”,、“”、“”，“”、“”这五个联结词组成的命题公式，必可以由,，,或,，,组成的命题公式所替代。,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 ),定理,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,Q,R) 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),定理,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*,例,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,）,),定义,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,),求合取范式或 析取范式的步骤：,（,1,）将公式中的联结词化归成,、。,（,2,）将,消去或内移。,（,3,）利用分配律、交换律求合取范式或析取范式。,（求合取范式：对；,求析取范式： 对 ）,注意任何命题的析取范式和合取范式都不是唯一的。,例求下面命题公式的合取范式和析取范式。,（,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),练习：求下面命题公式的合取范式和析取范式。,（,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),定义,1,7.4,n,个命题变元的合取式，称作布尔合取或小项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,n,个命题变元 共有,2,n,个小项。,例两个命题变元,P,和,Q,，其小项为：,PQ,，,PQ,，,PQ,，,PQ,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,小项的性质：,（,1,）每一个小项当其真值指派与编码相同时，其真值为,T,，其余均为,F,。,（,2,）任意两个不同小项的合取永为,F,。,（,3,）,m,0,m,1,m,2,m,3,m,4,m,5,m,6,m,7,T,定义,1,7.3,对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。,定理,1,7.3,在真值表中，一个 公式的真值为,T,的指派所对小项的析取，即为此公式的主析取范式。,例,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,）,例,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,）,例,8,求（,PQ,）（,PR,）（,QR,）的主析取范式。,解：原式（,PQ,（,RR,）,（,PR,（,QQ,）,（,QR,（,Pp,）,（,PQR,）（,PQR,）,（,PQR,）（,PQR,）,（,PQR,）（,PQR,）,（,PQR,）（,PQR,）,（,PQR,）（,PQR,）,例,9,求,P,（,P,Q,）,（,QP,）的主析取范式。,解：原式,P,（,P,Q,）,（,QP,）,P,（,PQP,）（,QQP,）,P,（,QP,）,P,（,QQ,）（,PQ,）,（,PQ,）（,PQ,）（,PQ,）,求主析取范式的步骤：,（,1,）求析取范式。,（,2,）去掉永假的析取项。,（,3,）去掉重复的合取项、合并相同变元。,（,4,）对合取项补入没出现的命题变元。（,PP,）,定义,1,7.6,n,个命题变元的析取式，称作布尔析取或大项，其中变元与它的否定不能同时存在，但两者必须出现且仅出现一次。,n,个命题变元 共有,2n,个小项。,例 两个命题变元,P,和,Q,，其小项为：,PQ,，,PQ,，,PQ,，,PQ,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,大项的性质：,（,1,）每一个大项当其真值指派与编码相同时，其真值为,F,，其余均为,T,。,（,2,）任意两个不同大项的析取永为,T,。,（,3,）,M,0,M,1,M,2,M,3,M,4,M,5,M,6,M,7,F,定义,1,7.7,对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。,定理,1,7.4,在真值表中，一个公式的真值为,F,的指派所对大项的合取，即为此公式的主合取范式。,例,10,利用真值表求（,PQ,）（,PR,）的主合取范式与主析取范式。,P,Q,R,P,Q,P,R,（,PQ,）（,PR,）,T,T,T,T,F,T,T,T,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,主合取范式：（,PQ,R,）（,PQR,）（,P,QR,）（,PQR,）,主析取范式：（,PQR,）（,PQR,）（,PQR,）（,PQR,）,求主合取范式的步骤：,（,1,）求合取范式。,（,2,）去掉所有为,T,的合取项。,（,3,）合并相同的析取项和变元。,（,4,）补入没出现的命题变元。（即添加,PP,）,例,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,）,用,表示小项的析取,用表示大项的合取,例如,（,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,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,真值表法,推理方法 直接证法,间接证法,（,1,）真值表法,若,H,1,，,H,2,，,，,H,n,都为,T,的行，,C,也为真；,或若,C,为假的行，,H,1,，,H,2,，,，,H,n,中至少有一个为假,则,H,1,H,2,H,n, C,成立。,例,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,例,2,如果张老师来了，这个问题可以得到解答，如果李老师来了，这个问题也可以得到解答，总之张老师或李老师来了，这个问题就可以得到解答。,解：设,P,：张老师来了。,Q,：李老师来了。,R,：这个问题可以得到解答。,本题可译为：,（,P R,）（,QR,）（,PQ,）,R,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,（,2,）直接证法,就是由一组前提，利用一些公认的推理规则，根据已知的等价公式或蕴涵公式，推出有效结论。,P,规则：前提在推导过程中随时可以引用。,T,规则：已经推出的公式在以后的推导过程中可随时引用。,常用蕴涵式见,43,页表,1,8.3,例,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,证法,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,例,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,(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,为矛盾式,.,例,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,例,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,(4),间接证法,2(,附加前提法,),要证,H1H2,Hn, RC,只要证,( H1H2,Hn,)(R C),为重言式,(H1H2,Hn,)(R C),( H1H2,Hn,) (R C),( H1H2,HnR,) C,( H1H2,Hn,R) C,只要证,( H1H2,Hn,R,) C,由,(SR) C,证得,S(R C),称为,CP,规则,。,例,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,例,6,设有下列情况,结论是否有效,?,(a),或者是天晴,或者是下雨。,(b),如果是天晴，我去看电影。,(c),如果我去看电影，我就不看书。,结论：如果我在看书则天在下雨。,解 若设,M,：天晴。,Q,：下雨 。,S,：我看电影。,R,：我看书。,即证：,M,Q,，,M,S,，,SR,，推出,RQ,其中,MQ (M,Q,）,(1) R P,（附加前提）,(2) SR P,(3) R S T(2) E,(
展开阅读全文