资源描述
,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,第1-3讲 蕴含式,1.蕴含式,2.证明蕴含式的方法,3.证明蕴含式的例子,4.,基本蕴含式,5.,蕴含式的性质,6.等价式和,蕴含式的联系,7.,其它联结词,8.,最小联结词集,9.作业,1,第1-3讲 蕴含式1.蕴含式1,1、,蕴含式,定义,设、为命题公式，当且仅当是一个重言式，称“蕴含”，记作,。,对而言，称为逆换式，,为反换式，,为逆反式,。,由上表中可以看出：,PQ,Q,P；QP,P,Q。,如同等价,一样，,也不是逻辑联结词。,仅仅表示是永真式。,2,1、蕴含式定义设、为命题公式，当且仅当是一个重言,2、,证明蕴含式的方法,分析：要证,，即要证为重言式。对来说，除为真、为假时，的真值为假外，其余情况的真值皆为真。故要证,，只须对条件命题的前提指定其真值为真，若由此推出后件亦为真，则 为重言式。即,成立。另一方面，由,，要证为重言式，只需证,为重言式。即证,为真时，,为真。亦即证为假时，为假。,证明给定的蕴含式的正确性的方法：,.假定前件是真,若能推出后件是真,则此蕴含式为真。,.假设后件是假,若能推出前件亦假,则此蕴含式为真。,3,2、证明蕴含式的方法分析：要证，即要证为重言式。,例,证明,(),证：设,()为真，则,和皆为真，那麽为假。再由为真,得知应为真。,或证为：设为假（那麽等值于），那麽，,(),(F),即前件为假。,例 2,证明,(PQ)(QR),PR,证：,设PR为假，则为真，R为假。如Q为真，则QR为假；若Q为假，则PQ为假。,故(PQ)(QR)为假。,3、证明蕴含式的例子,4,例 证明()例 2 证明(PQ),4、,基本蕴含式,(1)PQ,P (PQ,Q),(2)P,PQ (Q,PQ),(3),P,PQ,(,因为,P,PQ,PQ),(4)Q,PQ,(,因为,Q,PQ,PQ),(5),(PQ),P,(,因为,(PQ),P,Q,P),(6),(PQ),Q,(7)P(PQ),Q,(8),Q(PQ),P,(9),P(PQ),Q,(10)(PQ)(QR),PR,(11)(PQ)(PR)(QR),R,(,设前件为真去证,),(12)(P,Q)(Q,R),P,R,(设前件为真，分P为真和为假两种情况讨论),5,4、基本蕴含式(1)PQP (PQQ),5、,蕴含式的性质,若,且是重言式，则必为重言式。,证明：因为为永真式，当为永真时，如果对某一指派，的真值为假，则与为永真相矛盾，故永真。,若,，,，则,。,证明：因,，,，所以，为永真式，那麽（）（）亦为永真式。另外，由I,10,，可知(AB)(BC),(AC)那麽由性质是永真式，亦即,。,6,5、蕴含式的性质若且是重言式，则必为重言式。若,5、,蕴含式的性质,（续）,若,且,，则,。,证明：设的真值为真，由于,，,，则，的真值亦为真，从而的真值为真，故为永真，从而,。,若,且,，则,。,证明：因和为永真，那麽永真。而(AB)(CB),(,AB)(,CB),(,A,C)B,(AC)B,(AC)B。,故为永真，从而,。,7,5、蕴含式的性质（续）若且，则。,6、等价式和,蕴含式的联系,联结词“,”,和“,”,有如下关系：,A,B,(A,B)(B,A)，,等价式和蕴含式之间也有着紧密的联系，如下所述。,定理 设、为任意两个命题公式，,的充分必要条件是,且,。,证明：若,，则,为重言式，因为,（）（），故和皆为真，即,和,成立。,反之，若,且,，则和皆为真，从而,为真，即,为重言式，亦即,。,8,6、等价式和蕴含式的联系联结词“”和“”有如下关系：定理,7、,其它联结词,给定个命题变元，按命题公式的形成规则可以得到无数多个命题公式。但在这些无穷尽的命题公式之中，是否其真值都不同（指真值表最后一列不同）呢?或者说它们都是彼此不等价的呢?,回答是否定的!,这是因为对个变元只能有2,N,个不同的真值指派，在每一种真值指派下该命题公式只有真假两个可能，对于2,N,个不同的真值指派就只有2的2,N,个不同的真假二值的排列。一个排列相当于某一个由个变元生成的命题公式的真值表中的最后一列。,例如包含两个命题变元、的不同命题公式只有2的2,2,个，即个。其它命题公式必定与这个之中的某一个有相同的真值。或者说与这十六个命题之一等价。,9,7、其它联结词给定个命题变元，按命题公式的形成规则可以得到,包含两个命题变元P和Q的不同命题公式,10,包含两个命题变元P和Q的不同命题公式10,7、,其它联结词,（续1）,从包含两个命题变元、的不同命题公式表不难看出，表示这个真值不同的公式，如果每个公式只准用一个联结词，则定义九个联结词已足够使用。或者说对一个或两个命题进行运算（连接），有九个运算符就足够了。当然，这并不是必须的。,定义,设,、,是两个命题公式，复合命题,称为,与,的不可兼析取。,为真，当且仅当,、,真值不同。,11,7、其它联结词（续1）从包含两个命题变元、的不同命题公式,7、,其它联结词,（续2）,联结词,有以下性质：,(1)P,Q,(P,Q)（双条件否定）,(2)P,Q,(P,Q)(,PQ),(3)P,Q,Q,P (4)(P,Q),R,P,(Q,R),(5)P(Q,R),(PQ),(PR),(6)P,P,F (7)F,P,P (8)T,P,P,关于联结词,的定理,定理 设、是命题公式，如果,，则,，,，且,。,证明：如果,，则,=,12,7、其它联结词（续2）联结词有以下性质：关于联结词的定,7、,其它联结词,（续3）,定义,设、是两个命题公式，复合命题,称为与的条件否定，,为真，当且仅当的真值为真，的真值为假。,从上述定义可知，P,Q,(PQ)，故联结词,称为“条件否定”。,定义,设、是两个命题公式，复合命题称为与的“与非”。当且仅当和真值皆为真时，为假，否则为真。,从上述定义可知，PQ,(PQ)，故联结词称为“与非”,联结词有以下性质,：,(1)PP,(PP),P,(2)(PQ)(PQ),(PQ),PQ,(3)(PP)(QQ),P,Q,(,P,Q),PQ,13,7、其它联结词（续3）定义 设、是两个命题公式，复合命,7、,其它联结词,（续4）,定义4,设、是两个命题公式，复合命题,称为与的“或非”,。当且仅当和真值皆为假时，,为真，否则为假。,从上述定义可知，,PQ,(PQ)，故联结词称为“或非”。,联结词,有以下性质,：,(1)PP,(PP),P,(2)(PQ)(PQ),(PQ),PQ,(3),(PP)(QQ),P,Q,(,P,Q),PQ,包含,、,、的复合命题，其合式公式的定义与以前的定义类似。,14,7、其它联结词（续4）定义4 设、是两个命题公式，复合命,8、,最小联结词集,从基本恒等式可以发现，九个联结词并不都是必需的。,由PQ,(,P,Q)，PQ,(,P,Q)可知，,和可以互相替代,。,由P,Q,PQ可知，,可用,和替代,；,由P,Q,(P,Q)(Q,P)可知，,可用,和替代,；,所以,、,、,可用,，或,，代替,。,由于P,Q,(P,Q)，P,Q,(P,Q)，,PQ,(PQ)，PQ,(PQ)，,所以,、,、,可用,、,、,替代。,结论：,任意命题公式都可由仅包含,、或,、的命题公式等价地表示出来,。,15,8、最小联结词集从基本恒等式可以发现，九个联结词并不都是必需,8、,最小联结词集(续),联结词组,，或,，能否再归结为,、呢？,设,P,(.(PR).),对右边所出现的变元都指派真值，则右边命题公式的真值必为，但此时左边命题公式的真值为。这一矛盾说明,不能由、的复合所代替。,，和,，称为最小联结词组,任何命题公式都能由仅含这些联结词的命题公式等价代换,并且最小联结词组中没有多余的联结词。,因,联结词,、可分别用或来代替，所以，和也是最小联结词组。,16,8、最小联结词集(续)联结词组，或，能否再归,第1-3讲 作业,P23 1,bc,，2,bc,，7，8,ce,，9,b,P29,1,c,，,3，,9,17,第1-3讲 作业P23 1bc，2 bc，7，8,
展开阅读全文