离散数学第4章讲义-2.ppt

Click to edit Master text styles,Second Level,Third Level,Fifth Level,Fourth Level,第,*,页,第,*,页,*,上海金融学院信息管理学院 元如林,第五章,数理逻辑,（,mathematical logic,）,逻辑学,:,关于思维形式及其规律的科学,形式逻辑,:,研究思维形式结构及其规律和规则,数理逻辑,:,用数学方法研究形式逻辑和数学基础,辩证逻辑,:,研究辩证思维形式及其规律,思维,:,人对客观世界的理性认识,(,或反映,),，即人对事物的间接的、概括的映射过程，是在感性认识之后，对感性材料进行比较、分析、综合、抽象、概括等去粗取精、去伪存真的活动。,思维的,内容,、思维的,形式,、思维形式的,结构,概念,思维的,形式：,思维形式的,结构：,判断,推理,S,是,P,所有,S,是,M,；,所有,M,是,P,；,所以，所有,S,是,P,；,思维的基本,规律,：,同一律、矛盾律、排中律、充足理由律等,认识客观现实的,方法,：,下定义、划分、观察、实验、假说、,论证,概念,：内涵、外延,对象（属性、共同属性、特有属性）,概念的种类、概念间的关系、,概念的推演、划分、定义,语言、文字 字 词,判断,：对思维对象有所肯定或有所否定的思想,语句,命题,直言判断：,关系判断：,联言判断：,选言判断：,假言判断：,负判断：,模态判断 时态判断,推理,：演绎推理 归纳推理 类比 假说,演绎,：直接推理、简单判断推理,（三段论、关系推理）,复合判断推理,（联言推理、选言推理、假言推理、,二难推理、模态推理等）,归纳,：完全归纳推理、不完全归纳推理、,科学归纳推理、求因果联系、,提炼经验材料,推理,：演绎推理 归纳推理 类推 假说,类推,：根据同类的已知情况而推测其未知情况,假说,：对事物存在的原因或规律作出有根据的,假定说明,逻辑思维的,规律,：,同一律,：,在正确的思维过程中，所运用的同一概念必须保持同一意义。,（保持思维的准确性）,矛盾律,：,在同一时间、同一关系上，不能对同一对象作出不同的判断。,（保持思维的一贯性）,排中律,：,在同一时间、同一关系上，对关于同一事物的两个矛盾论断，必须明确选择其一。,（保持思维的明确性）,充足理由律,：,任何正确的思想，都应该有真实性已经在人们的实践中被证实了的其它思想作根据,（保持思维的根据性）,论证,：根据某个或某些判断的真实性，来判定另一判断的真实性的一种思维过程。,证明的,种类,：演绎证明、归纳证明、,直接证明、间接证明（反证法）,反驳的,方法,：直接反驳、归纳反驳、归谬反驳,论证的,规则,：,论题：,1,、清楚明确；,2,、首尾一贯,论据：,1,、已确知为真；,2,、其真实性不依靠论题来证明,论证方式：,必须遵守正确的推理规则,数理逻辑,（,mathematical logic,）,是用数学方法研究人类推理过程的一门数学学科。,又称,符号逻辑、现代逻辑,。,其显著特征是符号化和形式化，即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划,并基于符号串形式的演算来描述推理过程的一般规律。,逻辑演算四个分支：,公理集合论、证明论、模型论和递归论。,5.1,命题及联结词,一、命题,（,propositions,or,statements,）,命题,：能判断真假的陈述句。,例如,，,“,北京是中国的首都。,”,命题 真,（,true,）,“,长春是中国最大的城市。,”,命题，假,（,false,）,“请关门,!”,不是命题,“你去哪里,?”,不是命题,。,5.1,命题及联结词,一、命题,（,propositions,or,statements,）,命题,：能判断真假的陈述句。,例如,，,“,北京是中国的首都。,”,命题 真,（,true,）,“,长春是中国最大的城市。,”,命题，假,（,false,）,“请关门,!”,不是命题,“你去哪里,?”,不是命题,。,命题的真值,：命题的判断结果,如果一个命题是真的，就说它的真值是,1,；,如果一个命题是假的，就说它的真值是,0,。,用,1,代表一个抽象的真命题，,用,0,代表一个抽象的假命题。,1,、,T,、真、,（,true,）,0,、,F,、假、,（,false,）,命题的标示符,:,用大写英文字母,P,，,Q,，,，,P,1,，,P,2,，,，表示命题。表示命题的符号称为命题的标示符。,命题常元,：当命题标示符标示一个具体命题时，称为命题常元。,（,proposition constants,）,是命题,命题变元,：当命题标示符标示一组命题中的任一个时，称为命题变元。,（,proposition variable,）,不是命题,例,1,：分析下列自然语句哪些是命题,1,、今天我休息。,是命题,2,、昨天下雨。,3,、雪是白色的。,4,、我是学生。,5,、,6,不是偶数。,6,、今天我休息。,7,、你好吗？,8,、请坐下。,9,、真好啊！,不是命题,疑问句,祈使句,感叹句,例,2,：分析下列自然语句哪些是命题,1,、火星上有生命。,是命题,2,、,1+1=10,。,3,、雪是黑色的。,4,、这盘菜太咸。,5,、,x1,。,6,、我正在说谎。,不是命题,模糊逻辑,与,x,有关,悖论,不是命题,是命题,不是命题,不是命题,二、联结词,定义,5.1.1,设,P,是一个命题，定义命题,P,，称为,P,的否定式，称符号,为否定联结词,并规定,P,是真的当且仅当,P,是假的。,例,P,：,上海是一个城市。,P,：,上海不是一个城市。,“非”“不”,“并非”（,not all,），,1,、否定,（,negation,）,P,读作非,P,。,p,1,0,p,1,0,定义,5.1.2,设,P,，,Q,是两个命题，命题“,P,并且,Q”,称为,P,，,Q,的合取，记以,P,Q,，,读作,P,且,Q,。,规定,P,Q,是真的当且仅当,P,和,Q,都是真的。,2,、合取,（,conjunction,）,Q,1,0,P,Q,0,0,P,0,1,1,0,0,1,0,1,例如，,P,：,2,2=5,，,Q,：,雪是黑的，,P,Q,：,2,2=5,并且雪是黑的。,例如，,P,：,今天下雨，,Q,：,今天刮风，,P,Q,：,今天下雨又刮风。,虽然,，但是,。,不仅,，而且,。,既,，也,。,一面,，一面,。,“与”,“和”,“并且”（,and,）,定义,5.1.3,设,P,，,Q,是两个命题，命题“,P,或者,Q”,称为,P,，,Q,的析取，记以,P,Q,，,读作,P,或,Q,。,规定,P,Q,是真的当且仅当,P,，,Q,中至少有一个是真的。,3,、析取,（,disjunction,）,Q,1,0,P,Q,0,1,P,0,1,1,0,0,1,1,1,“或”（,or,）,定义,5.1.3,例如，,P,：,今天下雨，,Q,：,今天刮风，,P,Q,：,今天下雨或者刮风。,例如，,P,：,2,2=5,，,Q,：,雪是黑的，,P,Q,：,2,2=5,或者雪是黑的。,例如，,P,：小李爱唱歌。,Q,：小李爱跳舞。,P,Q,：小李爱唱歌或跳舞。,例如，,P,：小李是北京人。,Q,：小李是上海人。,小李是北京人或上海人,。,P,Q,：,可兼或,不可兼或、异或,小李是北京人或上海人。,(P,Q),定义,5.1.4,设,P,，,Q,是两个命题，命题“如果,P,，则,Q”,称为,P,蕴含,Q,，,记以,P,Q,。,规定，,P,Q,是假的当且仅当,P,是真的而,Q,是假的。,4,、,蕴含,（,implication,),Q,1,0,P,Q,1,1,P,0,1,1,0,0,1,0,1,P,称为前件，,Q,称为后件。,例如，,P,：,f(x),是可微的，,Q,：,f(x),是连续的，,P,Q,：若,f(x),是可微的，则,f(x),是连续的。,例如，,P,：,2,2=5,，,Q,：,雪是黑的，,P,Q,：若,2,2=5,，,则雪是黑的。,如果,，则,。,P,Q,（,ifthen,）,只要,，就,。,P,Q,因为,，所以,。,P,Q,只有,，才,。,Q,P,除非,，才,。,Q,P,除非,，否则不,。,Q,P,，,P,Q,P,是,Q,的充分条件：,P,Q,P,是,Q,的必要条件：,Q,P,例：,P,：我努力学习。,Q,：我会通过考试。,只要,我努力学习,，,我就会通过考试,。,P,Q,如果,我努力学习,，,我就会通过考试,。,P,Q,只有,努力学习,，我才,会通过考试,。,Q,P,除非,努力学习,，我才,会通过考试,。,Q,P,除非,努力学习,，否则我不,会通过考试,。,Q,P,，,P,Q,例：如果明天不下雨，我就去市图书馆。,P,：明天不下雨。,Q,：我去市图书馆。,P,Q,：如果明天不下雨，我就去市图书馆。,P,：,0,明天下雨。,Q,：,1,我去市图书馆。,P,：,0,明天下雨。,Q,：,0,我没有去市图书馆。,P,：,1,明天不下雨。,Q,：,1,我去市图书馆。,P,：,1,明天不下雨。,Q,：,0,我没有去市图书馆。,定义,5.1.5,设,P,，,Q,是两个命题，命题“,P,当且仅当,Q”,称为,P,等价,Q,，,记以,P,Q,。,规定，,P,Q,是真的当且仅当,P,，,Q,或者都是真的，或者都是假的。,5,、,等价,(,two-way-implication,),Q,1,0,P,Q,1,0,P,0,1,1,0,0,1,0,1,“,充分必要,”,“,当且仅当,”,“,If and only if”,iff,例如，,P,：,a,2,+b,2,=a,2,，,Q,：,b=0,，,P,Q,：,a,2,+b,2,=a,2,当且仅当,b=0,。,原子命题,：不能分解成其它命题的命题,（,atoms propositions,）,复合命题,：有若干个原子命题经过联结词复合而成的命题,（,compositive,propositions,or,compound statements,）,命题连接词的,优先级,：,例,如果你走路时看书，那么你一定会成为近视眼。,解,：令,P,：,你走路；,Q,：,你看书；,R,：,你是近视眼。,于是，上述语句可表示为（,P,Q,）,R,。,例,除非他以书面或口头的方式正式通知我，否则我不参加明天的会议。,解,：令,P,：,他书面通知我；,Q,：,他口头通知我；,R,：,我参加明天的会议。,于是，上述语句可表示为,R,(P,Q),。,(P,Q),R,P,Q,R,例,设,P,，,Q,，,R,的意义如下：,P,：,苹果是甜的；,Q,：,苹果是红的；,R,：,我买苹果。试用日常语言复述下述复合命题：,(1)(P,Q),R(2)(,P,Q),R,解,：,(1),如果苹果甜且红，那么我买。,(2),我没买苹果，因为苹果不甜也不红。,5.2,命题公式及公式的等值和蕴含关系,一、,命题公式,定义,1,：由命题变元、联结词和圆括号按下列规则组成的符号串称为,合式公式,：,(1),单一命题变元是合式公式；,(2)0,、,1,是合式公式；,(3),若,A,，,B,是合式公式，则,(,A),，,(A,B),，,(A,B),，,(A,B),，,(A,B),是合式公式；,(4),所有有限次使用,(1),，,(2),，,(3),得到的符号串才是合式公式。,合式公式也称为,命题公式,，简称为,公式,，,（,proposition formula,）,规定：,公式,(,A),的括号可以省略，写成,A,。,整个公式的最外层括号可以省略。,五种逻辑联结词的优先级按如下次序：,，,，,，,，,例如，我们写符号串,P,Q,R,Q,S,R,就意味着是如下公式：,(P,(Q,R),(,(Q,(,S),R),定义,2,设,A,是命题公式，,P,1,P,n,是出现在,A,中的所有命题变元。对,P,1,P,n,指定一组真值，则这组真值称为,A,的一个,赋值,或,指派,。,（,assignment,s,）,成真指派,成假指派,设,A,为命题公式：,A,（,P,1,P,n,）,称为,n,元命题公式。,有,n,个不同原子的公式，共有,2,n,个不同的,真值指派,。,A,在其所有可能的真值指派下所取真值的表，称为,G,的,真值表,。,（,truth table,）,例：,A=(P,Q),R,，,其真值表如下：,P,Q,R,A,0,0,0,1,0,0,1,1,0,1,0,1,0,1,1,1,1,0,0,1,1,0,1,1,1,1,0,0,1,1,1,1,例：,A=(P,Q),R,，,其真值表如下：,P,Q,R,P,Q,A,0,0,0,0,1,0,0,1,0,1,0,1,0,0,1,0,1,1,0,1,1,0,0,0,1,1,0,1,0,1,1,1,0,1,0,1,1,1,1,1,p,q,r,q,r,p,(q,r),(p,(q,r),0,0,0,0,1,1,1,1,0,0,1,1,0,0,1,1,0,1,0,1,0,1,0,1,0,0,0,1,0,0,0,1,1,1,1,1,0,0,0,1,0,0,0,0,1,1,1,0,求,(P,（,Q,R,）的,真值表。,语句的形式化,语句形式化,主要是以下几个方面：,要准确确定原子命题，并将其形式化。,要选用恰当的联结词，尤其要善于识别自然语言中的,联结词（有时它们被省略），否定词的位置要放准确。,必要,时可以进行改述，即改变原来的叙述方式，,但要保证表达意思一致,。,需要的括号不能省略，而可以省略的括号，,在需要提高公式可读性时亦可不省略。,要注意语句的形式化未必是唯一的。,定义,3,：,对命题公式,A,，,如果对,A,中命题变元的一切指派均为真，,则,A,称为,重言式,（,tautology,），,又称,永真式,.,如果至少有一个指派为真，,则,A,称为,可满足式,，,（,satisfactable,formula,or,contingency,）。,如果对,A,中命题变元的一切指派均为假，,则,A,称为,矛盾式,（,contradiction,or,absurdity,），,又称,永假式,.,我们常把重言式记为,1,把矛盾式记为,0,矛盾式,可满足式,重言式,例,:,用真值表判断下列公式的类型,.,(1)(P,Q),P,Q,(P,Q),Q,(P,Q),R,重言式,矛盾式,可满足式,P,Q,p,Q,P,P,Q,A,0,0,1,1,1,1,0,1,1,1,1,1,1,0,0,0,0,1,1,1,1,0,1,1,(1),A=,(P,Q),P,Q,重言式,P,Q,P,Q,(P,Q),A,0,0,1,0,0,0,1,1,0,0,1,0,0,1,0,1,1,1,0,0,A=,(P,Q),Q,矛盾式,P,Q,R,Q,P,Q,A,0,0,0,1,0,1,0,0,1,1,0,1,0,1,0,0,0,1,0,1,1,0,0,1,1,0,0,1,1,0,1,0,1,1,1,1,1,1,0,0,0,1,1,1,1,0,0,1,可满足式,A=(P,Q),R,二、命题公式的等值式,设,A,为,n,元,命题公式：,A,（,P,1,P,n,）,A,共有,2,n,个不同的,真值指派,。,A,共有 个不同的,真值表,。,二、命题公式的等值式,定义,4,设,A,，,B,是命题公式，若,A,B,是重言式，则称,A,与,B,是等值的，记为,A,B,。,几点说明：,1,、定义中，,A,B,均为元语言符号,2,、,A,或,B,中可能有哑元出现,.,例如,(,p,q,),(,p,q,),(,r,r,),r,为左边公式的哑元,.,3,、用真值表可检查两个公式是否等值,请验证：,p,(,q,r,),(,p,q,),r,p,(,q,r,),不与,(,p,q,),r,等值,(,P,Q,),(,P,Q,),(,R,R,),Q,1,0,P,Q,1,1,P,0,1,1,0,0,1,0,1,P,Q,R,P,P,Q,R,R,A,0,0,0,1,1,0,1,0,0,1,1,1,0,1,0,1,0,1,1,0,1,0,1,1,1,1,0,1,1,0,0,0,0,0,0,1,0,1,0,0,0,0,1,1,0,0,1,0,1,1,1,1,0,1,0,1,A=,(,P,Q,),(,R,R,),(,P,Q,),2,、,A,或,B,中可能有哑元出现,.,例,1,判断下列各组公式是否等值,:,(1),p,(,q,r,),与,(,p,q,),r,1,1,1,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,(,p,q,),r,p,(,q,r,),q,r,p q r,p,q,0,0,0,0,0,0,1,1,结论,:,p,(,q,r,),(,p,q,),r,(2),p,(,q,r,),与,(,p,q,),r,0,1,0,1,1,1,0,1,1,1,1,1,1,1,0,1,1,1,0,1,1,1,0,1,0 0 0,0 0 1,0 1 0,0 1 1,1 0 0,1 0 1,1 1 0,1 1 1,(,p,q,),r,p,(,q,r,),q,r,p q r,p,q,1,1,1,1,0,0,1,1,结论,:,p,(,q,r,),与,(,p,q,),r,不等值,二、命题公式的等值式,设,A,，,B,，,C,是命题公式，则：,（,1,）自反性：,A,A,（,2,）对称性：若,A,B,，则,B,A,（,3,）传递性：若,A,B,，且,B,C,，则,A,C,P=,A|A,是 命题公式,（,P,，,）是等价关系,基本等值式,1,、双重否定律,A,A,2,、幂等律,A,A,A,A,A,A,3,、交换律,A,B,B,A,A,B,B,A,4,、结合律,(,A,B,),C,A,(,B,C,),(,A,B,),C,A,(,B,C,),5,、分配律,A,(,B,C,),(,A,B,),(,A,C,),A,(,B,C,),(,A,B,),(,A,C,),6,、德摩根律,(,A,B,),A,B,(,A,B,),A,B,7,、吸收律,A,(,A,B,),A,A,(,A,B,),A,基本等值式,8,、零律,A,1,1,A,0,0,9,、同一律,A,0,A,.,A,1,A,10,、排中律,A,A,1,（互否律）,11,、矛盾律,A,A,0,12,、蕴涵等值式,A,B,A,B,13,、等价等值式,A,B,(,A,B,),(,B,A,),14,、假言易位,A,B,B,A,15,、等价否定等值式,A,B,A,B,16,、归谬论,(,A,B,),(,A,B,),A,特别提示：必须牢记这,16,组等值式，这是继续学习的基础,等值演算与置换规则,1.,等值演算,由已知的等值式推演出新的等值式的过程,2.,等值演算的基础：,(1),等值关系的性质：自反性、对称性、传递性,(2),基本的等值式,(3),置换规则（见,3,）,等值演算与置换规则,子公式：,设,A,i,是公式,A,的一部分，,A,i,也是一个公式，则称,A,i,是,A,的子公式,例：,A=,P,(,Q,R,),A,1,=,Q,R,A,2,=,P,A,3,=,Q,A,4,=,R,A,5,=,P,(,Q,R,),等值演算与置换规则,3.,置换规则,设,X,是公式,A,的子公式，,Y,也一个,公式，且,X,Y,如果用,Y,置换,A,中所有的,X,后得到的命题公式,B,则,A,B,。,4,、,代入规则,在重言式中，将某一命题变元全用同一命题公式代入后，得到的公式是重言式。,等值演算的应用举例,证明两个公式等值,例,2,证明,p,(,q,r,),(,p,q,),r,证,p,(,q,r,),p,(,q,r,)(,代入规则）,p,(,q,r,),（蕴涵等值式，置换规则）,(,p,q,),r,（结合律，置换规则）,(,p,q,),r,（德摩根律，置换规则）,(,p,q,),r,（蕴涵等值式，置换规则）,今后在注明中省去置换规则,注意：用等值演算不能直接证明两个公式不等值,证明两个公式不等值,例,3,证明,p,(,q,r,),与,(,p,q,),r,不等值,证 方法一 真值表法,见例,1(2),方法二 观察法,.,观察到,000,010,是左边的成真赋值，是右 边的成假赋值,方法三 先用等值演算化简公式，然后再观察,p,(,q,r,),p,q,r,(,p,q,),r,(,p,q,),r,(,p,q,),r,更容易看出前面的两个赋值分别是,左边的成真赋,值和右边的成假赋值,等值演算的应用举例,判断公式类型,:,A,为矛盾式当且仅当,A,0,A,为重言式当且仅当,A,1,例,4,用等值演算法判断下列公式的类型,(1),q,(,p,q,),(2)(,p,q,),(,q,p,),(3)(,p,q,),(,p,q,),r,),等值演算的应用举例,(1),q,(,p,q,),等值演算的应用举例,解,(1),q,(,p,q,),q,(,p,q,),（蕴涵等值式）,q,(,p,q,),（德摩根律）,p,(,q,q,),（交换律，结合律）,p,0,（矛盾律）,0,（零律）,矛盾式,判断公式类型,(2)(,p,q,),(,q,p,),(,p,q,),(,q,p,),（蕴涵等值式）,(,p,q,),(,p,q,),（交换律）,1,重言式,(3)(,p,q,),(,p,q,),r,),(,p,(,q,q,),r,（分配律）,p,1,r,（排中律）,p,r,（同一律）,可满足式，,101,和,111,是成真赋值，,000,和,010,等是成假赋值,.,三、,公式的蕴含关系,逻辑的一个重要功能是研究推理。固然，依靠等价关系可以进行推理。但是，进行推理时，不必一定要依靠等价关系，只需是,蕴涵关系,就可以了。,例如，若三角形等腰，则两底角相等，这个三角形等腰，所以，这个三角形两底角相等。,又如，若行列式两行成比例，则行列式值为,0,，这个行列式两行成比例，所以，这个行列式值为,0,。,上面两个例子的推理关系涵义不同，但依据的推理规则相同，推理形式为：,若,P,则,Q,，,P,，,所以,Q,。,推理的正确性与命题,P,，,Q,涵义无关，只决定于逻辑形式，命题逻辑中用公式表示命题，命题间演绎推理关系，反映为公式间逻辑蕴含关系。,定义,5,（,蕴含）,设,A,，,B,是两个命题公式，若,A,B,是重言式，则称,A,永真蕴含,B,记为,A,B.,注意：,符号“,”和“,”一样，它们都不是逻辑联结词，因此，,A,B,，,A,B,也都不是公式。,公式,A,蕴含公式,B,的充要条件是：公式,A,B,是永真式。,例如：,(P,Q),P,，,(P,Q),Q,P,Q,P,Q,(P,Q),P,(P,Q),Q,0,0,0,1,1,0,1,0,1,1,1,0,0,1,1,1,1,1,1,1,设,A,，,B,，,C,是命题公式，则：,（,1,）自反性：,A,A,（,2,）反对称性：若,A,B,，,B,A,，则,A,B,（,3,）传递性：若,A,B,，且,B,C,，则,A,C,P=,A|A,是 命题公式,（,P,，,）是偏序关系,基本蕴涵式,P,Q,P,化简率,P,Q,Q,P,P,Q,附加率,Q,P,Q,(P,Q),P,Q,假言推理,(P,Q),Q,P,析取三段论,(P,Q),(Q,R),P,R,假言三段论,基本蕴涵式,(P,Q),Q,P,拒取式,(P,R),(,Q,S),(P,Q),R,S,构造性二难,(P,R),(,P,R),(P,P),R,P,(P,Q),变形附加率,Q,P,Q,(,P,Q),P,变形简化率,(,P,Q),Q,P,Q,(,P,R),(,Q,R),前后件附加率,P,Q,(,P,R),(,Q,R),定理,:,设,A,B,为任意两个命题,A,B,的充分必要条件是,A,B,且,B,A.,每个等值式可产生两个推理定律,如,由,A,A,可产生,A,A,和,A,A,公式蕴涵的证明方法,真值表法证,A,B,是永真式；,利用一些基本等值式证,(A,B),1,利用一些蕴涵式进行推导；,(1),假设前件为真,推出后件也为真,.,(2),反证法，设后件为假，往证前件也为假。,要证明,A,B,可用以下方法,:,例,1:,证明附加率,:P,P,Q,Q,P,Q,P,Q,P,Q,P,(,P,Q),Q,(,P,Q),0,0,0,1,1,0,1,1,1,1,1,0,1,1,1,1,1,1,1,1,(P,(,P,Q),P,(,P,Q),(,P,P),Q,1,Q,1,(Q,(,P,Q),Q,(,P,Q),(,Q,Q),P,1,Q,1,P,P,Q,Q,P,Q,若,P,为真,则,P,Q,为真,所以,P,(,P,Q),若,Q,为真,则,P,Q,为真,所以,Q,P,Q,若,P,Q,为假,则,P,为假,所以,P,(,P,Q),若,P,Q,为假,则,Q,为假,所以,Q,(,P,Q),P,P,Q,Q,P,Q,例,2:,证明假言推理,:(P,Q),P,Q,P,Q,P,Q,(P,Q),P,(P,Q),P,Q,0,0,1,0,1,0,1,1,0,1,1,0,0,0,1,1,1,1,1,1,(P,Q),P,Q,(,P,Q),P),Q,(,(,P,P),(,Q,P),Q,(0(,Q,P),Q,(,Q,P),Q,(,Q,P),Q,(,Q,Q),P,1 ,P,1,例,2:,证明假言推理,:(P,Q),P,Q,证,:,(P,Q),P,(,P,Q),P,(,P,P),(,Q,P),0(,Q,P),Q,P,Q,例,2:,证明假言推理,:(P,Q),P,Q,证,:,若,(P,Q),P,为真,则,P,为真,且,(P,Q),为真,所以,Q,为真,反证法,:,若,Q,为假,若,P,为真,则,(P,Q),为假,所以,(P,Q),P,为假,.,若,P,为假,则,(P,Q),为真,所以,(P,Q),P,为假,.,例,2:,证明假言推理,:(P,Q),P,Q,证,:,(P,Q),(Q,R),(,P,Q),(,Q,R),(,P,Q),Q),(,P,Q),R),(,P,Q),(,P,R),(,Q,R),(,P),(,P),R,P,R,P,R,例,2:,证明假言三段论,(P,Q),(Q,R),P,R,5.3,对偶与范式,一、对偶,设公式,A,仅含联结词,，,，,，,A*,为,将,A,中符号,，,，,1,，,0,分别改换为,，,，,0,，,1,后所得的公式，那么称,A*,为,A,的,对偶,（,dual,）。,定义,1,分配律,A,(,B,C,),(,A,B,),(,A,C,),A,(,B,C,),(,A,B,),(,A,C,),（,3,）,C =,0(,Q,P),解：,（,3,）,C*=,1(,Q,P),(2)B =,(,P,Q),(,P,R),(,Q,R),解：,(2)B*=,(,P,Q),(,P,R),(,Q,R),例：试写出下列命题公式的对偶式：,（,1,）,A=,(,P,Q),P,解：,（,1,）,A*=,(,P,Q),P,定理,1,：,设公式,A,中仅含命题变元,p,1,p,n,，,及联结词,，,，,，,A*,为,A,的,对偶，,那么,A,(p,1,p,n,),A*(,p,1,p,n,),对偶原理,德摩根律,(,A,B,),A,B,(,A,B,),A,B,例,:,设,A=(,P,Q,),(,S,T,),R,),求,A.,解,:,A=(,P,Q,),(,S,T,),R,),对偶原理,定理,2,：,设,A,，,B,为仅含联结词，和命题变元,p1,pn,的命题公式，且满足,A(p,1,p,n,),B(p,1,p,n,),，,那么有,A*(p,1,p,n,),B*(p,1,p,n,),。,分配律,A,(,B,C,),(,A,B,),(,A,C,),A,(,B,C,),(,A,B,),(,A,C,),例,:,设,A=(,P,Q,),(,P,Q,),R,),B=(,P,R),.,解,:,A,B,(,P,Q,),(,P,Q,),R,),(,P,R),.,结合律,(,A,B,),C,A,(,B,C,),(,A,B,),C,A,(,B,C,),吸收律,A,(,A,B,),A,A,(,A,B,),A,5.4,命题演算的推理规则,定义,1,设,A,1,A,2,A,n,B,为命题公式,.,如果,A,1,A,2,A,n,B,为重言式,则称,B,为由,前提,A,1,A,2,A,n,推出的,有效结论,.,由命题公式,A,1,A,2,A,n,推,B,的推理正确当且仅当若对于每组赋值，,A,1,A,2,A,n,为假，或当,A,1,A,2,A,n,为真时，,B,也为真,.,注意,:,推理正确不能保证结论一定正确,称由前提,A,1,A,2,A,n,推出结论,B,的,推理是有效的或正确的,.,说明,1.,若,A,1,A,2,A,n,B,是重言式,记为,A,1,A,2,A,n,B,2.,由前提,A,1,A,2,A,n,推结论,B,的推理记为,A,1,A,2,A,n,B,若推理,是,有效的,则记为,:,A,1,A,2,A,n,B,否则记为,:,A,1,A,2,A,n,B,判断推理是否有效,就是判断,A,1,A,2,A,n,B,是否重言式,即,A,1,A,2,A,n,B,所以判断推理是否有效的方法,:,1,、真值表法,2,、等值演算法,3,、蕴含演算法,4,、主析取范式法,推理实例,例,1,判断下面推理是否有效,(1),若今天是,1,号，则明天是,5,号,.,今天是,1,号,.,所以,明天是,5,号,.,(2),若今天是,1,号，则明天是,5,号,.,明天是,5,号,.,所以,今天是,1,号,.,解：,设,P,：今天是,1,号，,Q,：明天是,5,号,.,(1),推理的形式结构,:,P,Q,P,|-,Q,(,P,Q,),P,Q,推理实例,用等值演算法,(,P,Q,),P,Q,(,P,Q,),P,),Q,P,Q,Q,1,所以,推理有效,因为,P,Q,不真，结论,Q,并不真,推理实例,(2),推理的形式结构,:,(,P,Q,),Q,P,(,P,Q,),Q,P,(,P,Q,),Q,P,(,P,Q,),Q,),P,(,(,P,Q,),Q),P,(,(,P,Q,),Q),P,Q,P,P,Q,故,01,是成假赋值，所以,推理不正确,推理定律,1.,A,(,A,B,),附加律,2.(,A,B,),A,化简律,3.(,A,B,),A,B,假言推理,4.(,A,B,),B,A,拒取式,5.(,A,B,),B,A,析取三段论,6.(,A,B,),(,B,C,),(,A,C,),假言三段论,7.(,A,B,),(,B,C,),(,A,C,),等价三段论,8.(,A,B,),(,C,D,),(,A,C,),(,B,D,),构造性二难,(,A,B,),(,A,B,),B,构造性二难,(,特殊形式,),9.(,A,B,),(,C,D,),(,B,D,),(,A,C,),破坏性二难,每个等值式可产生两个推理定律,(,见,163,页表,5-14,）,（,1,）前提引入规则（简称,P,规则,）：,在证明的任何步骤上都可引入前提。,（,2,）结论引入规则（简称,T,规则,）：,在证明的任何步骤上得到的结论都可作为后续证明的前提。,（,3,）,置换规则,在证明的任何步骤上，命题公式中的子公式都可作用与之等价的公式置换。,推理规则,形式证明法,一、直接证明法,利用表,5-14,、,P,规则、,T,规则、置换规则来构造命题公式序列以证明,A,1,A,2,A,n,B,这种方法称为,直接证明法,。,例,(1),推理的形式结构,:,P,Q,P,|-,Q,用等值演算法：,(,P,Q,),P,Q,(,P,Q,),P,),Q,P,Q,Q,1,所以推理有效,用直接证明法：,（,1,）,(,P,Q,),p,规则,（,2,）,P,p,规则,（,3,）,Q,T(1)(2),所以,(,P,Q,),P,Q,推理有效,例,2,构造下面推理的证明：,若明天是星期一或星期三，我明天就有课,.,若我明天有课，今天必备课,.,我今天没备课,.,所以，明天不是星期一、也不是星期三,.,解,(1),设命题并符号化,设,p,：明天是星期一，,q,：明天是星期三，,r,：我明天有课，,s,：我今天备课,直接证明法,(2),写出证明的形式结构,前提：,(,p,q,),r,r,s,s,结论：,p,q,(3),证明,r,s,P,规则,s,P,规则,r,T,(,p,q,),r,P,规则,(,p,q,)T,p,q,T,前提：,(,p,q,),r,r,s,s,结论：,p,q,证明,:,(,p,q,),r,),(,r,s,),s,),(,p,q,),(,(,p,q,),r),(,r,s,),s,),(,p,q,),(,(,p,q,),r),(,r,s,),s,),(,p,q,),(,(,p,r),(,q,r),(,r,s,),(,p,q,),(,p,r),r,(,q,r),r,s,),(,p,q,),(,p,r,q,r,s,),(,p,q,),(,p,r,q,r,s,p),(,p,r,q,r,s,q),1,1 1,等值演算法,前提：,(,p,q,),r,r,s,s,结论：,p,q,证明,:(,p,q,),r,),(,r,s,),s,(,p,q,),r,),r,(,p,q,),p,q,蕴含演算法,二、间接证明法,1,、附加前提证明法,适用于结论为蕴涵式,欲证 前提：,A,1,A,2,A,n,结论：,C,B,等价地证明 前提：,A,1,A,2,A,n,C,结论：,B,理由：,(,A,1,A,2,A,n,),(,C,B,),(,A,1,A,2,A,n,),(,C,B,),(,(,A,1,A,2,A,n,),C),B,(,A,1,A,2,A,n,C,),B,(,A,1,A,2,A,n,C,),B,附加前提证明法实例,例,3,构造下面推理的证明,2,是素数或合数,.,若,2,是素数，则 是无理数,.,若 是无理数，则,4,不是素数,.,所以，如果,4,是素数，则,2,是合数,.,解 用附加前提证明法构造证明,(1),设,p,：,2,是素数，,q,：,2,是合数，,r,：是无理数，,s,：,4,是素数,(2),推理的形式结构,前提：,p,q,p,r,r,s,结论：,s,q,附加前提证明法实例,(3),证明,s,附加前提引入,p,r,前提引入,r,s,前提引入,p,s,假言三段论,p,拒取式,p,q,前提引入,q,析取三段论,2,、归谬法,(,反证法,),欲证,前提：,A,1,A,2,A,n,结论：,B,做法 在前提中加入,B,，推出矛盾,.,理由,A,1,A,2,A,n,B,(,A,1,A,2,A,n,),B,(,A,1,A,2,A,n,B,),(,A,1,A,2,A,n,B,),0,A,1,A,2,A,n,B,0,归谬法实例,例,4,前提：,(,p,q,),r,r,s,s,p,结论：,q,证明 用归缪法 ,q,结论否定引入,r,s,前提引入,s,前提引入,r,拒取式,(,p,q,),r,前提引入,(,p,q,),析取三段论,p,q,置换,p,析取三段论,p,前提引入,p,p,合取,判断推理是否正确,1.,判断下面推理是否正确,:,(,1),前提：,p,q,q,结论：,p,解,:,推理的形式结构,:,(,p,q,),q,p,方法一：等值演算法,(,p,q,),q,p,(,p,q,),q,),p,(,p,q,),q,p,(,p,q,),(,q,q,),p,p,q,易知,10,是成假赋值，不是重言式，所以推理不正确,.,方法二,真值表法,不是重言式,推理不正确,1,1,1,0,0,1,1,1,0,1,0,0,(,p,q,),q,p,q,p,p,q,0,1,1,1,(,p,q,),q,0,0,1,0,方法三 直接观察出,10,是成假赋值,方法四 形式证明法,前提：,p,q,q,结论：,p,证：,（,1,）,p,q,p,规则,（,2,）,q,p,规则,（,3,）,(,p),T(1)(2),（,4,）,p,T(3),推理不正确,用等值演算法,(,q,r,),(,p,r,),(,q,p,),(,q,r,)(,p,r,),(,q,p,),(,q,r,)(,p,r