离散数学 第一章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,第一章 命题逻辑,1.,命题及其表示法,2.,命题联结词,3.,命题公式与翻译,4.,真值表与等价公式,5.,重言式与蕴含式,6.,其他联结词,7.,对偶与范 式,8.,推理理论,第一讲,1.,命题及其表示法,2.,命题联结词,1,命题及其表示法,定义,：,具有唯一真值的陈述句叫命题,。,讨论定义：,（）命题可以是真的，也可以是假的，但不能同时为真又为假。,（）命题分类：,),原子命题,（基本命题、本原命题）：一个命题，不能分解成为更简单的命题。,例：我是一位学生。,),分子命题,（复合命题）：,若干个原子命题使用适当的联结词,所组成的新命题,例：我是一位学生和他是一位工人,(3),命题的表示：常用,26,个大写的英文字母表示命题。用、表示。,(4),命题中所有的“真”用“”表示，,命题中所有的“假”用“”表示。,1,命题及其表示法,例,：判断下列语句是否为命题。,陈述句一般为命题,（,1,）十是整数。（）,（,2,）上海是一个村庄。（）,（,3,）今天下雨。,（,4,）加拿大是一个国家。（）,（,5,）是偶数而是奇数。,（,6,）她不是护士。,（,7,）,（,8,）今天是星期天。,1,命题及其表示法,命令句，感叹句，疑问句均不是命题。,（,1,）把门关上！,（,2,）你到哪里去？,语句既为真，同时又包含假的不是命题，这样的句子称为“,悖论,”。,（,3,）我正在说谎。,（在命题逻辑中不讨论这类问题）,1,命题及其表示法,2,命题联结词,下面先介绍五个常用的命题联结词。,否定词,：,（否定运算、非运算）,（）符号,读作“非”，“否定”,设命题为，则,读做“的否定”或“非”,（）定义：由真值表定义,P,P,T,F,F,T,2,命题联结词,（）举例：,：北京是一座城市。,：北京不是一座城市。,：每一种生物均是动物。,F,：有一些生物不是动物。,T,这里,不能讲成“每一种生物都不是动物”为假命题了。,对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。,2,命题联结词,合取词,（“合取”、“积”、“与”运算）,符号“,”,设，为两个命题，则,称与的合取，读作：“与”、“与的合取”、“并且”等。,定义（由真值表给出）：,2,命题联结词,P,Q,P,Q,Q,P,F,F,F,F,F,T,F,F,T,F,F,F,T,T,T,T,真值表如下,：,2,命题联结词,当且仅当和的真值均为“”，则（,）的真值为“”。否则，其真值为“”。,注意,：和是互为独立的；地位是平等的，和的位置可以交换而不会影响,的结果。,2,命题联结词,举例：,(a)P,：,王华的成绩很好,Q,：,王华的品德很好。,则,：王华的成绩很好并且品德很好。,(b)P,：,我们去种树,Q,：,房间里有一台电视机,则,：我们去种树与房间里有一台电视机。,2,命题联结词,(c)P,：,今天下大雨,Q,：,3+3=6,则,：今天下大雨和,3+3=6,由例,(b)(c),可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。,2,命题联结词,(d),下列语句不是合取联结词组成的命题。,P:,王大和王二是亲兄弟。,2,命题联结词,析取词,（或运算）,（）符号“,”,设、为二个命题，则（,）称作与的“析取”，读作：“或”。,（）定义（由真值表给出）：,2,命题联结词,当且仅当、均为“”时，（,）为“”。否则，其真值为“”,P,Q,P Q,F,F,F,F,T,T,T,F,T,T,T,T,真值表,如右：,2,命题联结词,区分“可兼或”与“不可兼或（异或，排斥或）”,析取词为,可兼或,即,:P,和,Q,均为“,T”,时（,PQ,）,为“,T”,例如：,灯泡有故障或开关有故障。,今晚写字或看书。,今天下雨或打雷。,以上例句均为可兼或。,2,命题联结词,“不可兼或”中当,P,和,Q,均为“,T”,时，则,P,异或,Q,为“,F”,。,（,异或用“,”,表示）,P,Q,P,Q,F,F,F,F,T,T,T,F,T,T,T,F,2,命题联结词,例：,他通过电视看杂技,或,到剧场看杂技。,他乘火车去北京,或,乘飞机去北京。,以上两句均为不“可兼或”。,2,命题联结词,单条件联结词：,（“蕴含”联结词、蕴含词）,（）符号“,”,，读作：“如果,则,”,、“蕴含”,、为二个命题，（,）为新的命题，读作：“如果则”，“蕴含”，“仅当”，“当且”，“是的充分条件”。,：称为前件、条件、前提、假设,：称为后件、结论。,2,命题联结词,（）定义,:,由真值表定义,P,Q,PQ,F,F,T,F,T,T,T,F,F,T,T,T,当为“”，为“”时，则（）为“”，否则（）均为“”。,2,命题联结词,（）举例：,P,：我拿起一本书,Q,：我一口气读完了这本书,PQ,：,如果我拿起一本书，则我一口气读完了这本书。,(b)P,：,月亮出来了,Q,：,33=9,PQ,：,如果月亮出来了，则33=9,。,2,命题联结词,双条件联结词,（“等价”词）,（）符号“,”,设、为二个命题，则,读作：“当且仅当”，“等价”,“,是的充分必要条件”。,（）定义（见真值表）：,2,命题联结词,真值表,:,每当和的真值相同时，则（,）的真值为“”，否则（,）的真值为“”。,P,Q,P,Q,F,F,T,F,T,F,T,F,F,T,T,T,2,命题联结词,（）举例：,（,a,）,设,：,ABC,是等腰三角形,：,ABC,有两只角相等,：,ABC,是等腰三角形当且仅当,ABC,中有两只角相等。,2,命题联结词,（,b,）,下面均为等价联结词：,春天来了当且仅当燕子飞回来了。,平面上二直线平行，当且仅当这二直线不相交。,当且仅当雪是白色的。,2,命题联结词,（）,中，、的地位是平等的，、交换位置不会改变真值表中的值。,（）当且仅当 ,仅当,当且,2,命题联结词,命题联结词在使用中的优先级,（）先括号内，后括号外,（）运算时联结词的优先次序为：,（,由高到低）,2,命题联结词,（）联结词按从左到右的次序进行运算,例,（,）可省去括号,因为“”运算是可结合的。,（,）,可省去括号,因为符合上述规定,而,（,）,中的括号不能省去，因为“,”,不满足结合律。,2,命题联结词,（）最外层的括号一律均可省去,（,）可写成,命题联结词小结：,（,1,）“或”可分为可兼或（,）和异或（,）（不可兼或）,2命题联结词,(2),除“,”,为一元运算外，其余四个均为二元运算。,(3)“P,Q,”,当前件,P,为“”时，不论后件,Q,怎样，则单条件命题,“,P,Q,”,的真值均为“”。,(4),命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。,第二讲,3.,命题公式与翻译,4.,真值表与等价公式,命题公式与翻译,命题公式,命题常元：表示确定的命题,T,，,F,。,命题变元：没有指定真值的命题。常用大写英文字母,表示。,由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串称为,命题公式,。,命题公式与翻译,命题公式可按下述法则来生成,：,）孤立的命题变元是一个命题公式。,）若是命题公式，,也为命题公式。,）若、是命题公式，则（,）、（,）、（,）、（,）均为命题公式。,命题公式与翻译,）当且仅当有限次使用,（）（）（）所生成的公式才是命题公式。,例如：,(,(P Q),，,(P,(Q R),，,(PQ),R),，,P,都是命题公式。而,(P,),，,(P,),都不是命题公式,2.,翻译,步骤如下：,找出各简单命题，分别符号化。,找出各联结词，把简单命题逐个联结起来。,命题公式与翻译,例,.,将下列命题符号化：,（,1,）李明是计算机系的学生，他住在,312,室或,313,室。,解：首先用字母表示简单命题。,P,：,李明是计算机系的学生。,Q,：,李明住在,312,室。,R,：,李明住在,313,室。,该命题符号化为：,P,（,QR,）,（,2,）,张三和李四是朋友。是一个简单句,该命题符号化为：,P,命题公式与翻译,（,3,）虽然交通堵塞，但是老王还是准时到达了车站。,首先用字母表示简单命题。,P,：,交通堵塞。,Q,：,老王准时到达了车站。,该命题符号化为：,P,Q,命题公式与翻译,（,4,）只有一个角是直角的三角形才是直角三角形。,首先用字母表示简单命题。,P,：,三角形的一个角是直角。,Q,：,三角形是直角三角形。,该命题符号化为：,P,Q,命题公式与翻译,（,5,）老王或小李中有一个去上海出差。,首先用字母表示简单命题。,P,：,老王去上海出差。,Q,：,小李去上海出差。,该命题符号化为：,P,Q,也可符号化为：,（,P,Q,）（,PQ,）,命题公式与翻译,4,真值表与等价公式,1,命题公式的真值表,:,命题变元用特定的值来取代，这一过程称为对该命题变元进行,指派或赋值。,定义,：命题公式,A,在其所有可能的赋值下取得的值列成的表称为,A,的真值表。,构造真值表的步骤如下,：,1),找出给定命题公式中所有的命题变元，列出所有可能的赋值。,2),按照从低到高的顺序写出命题公式的各层次。,3),对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。,4,真值表与等价公式,P,Q,P Q,（,）,（,）,）,F,F,F,F,T,F,T,T,F,T,T,F,T,T,F,T,T,T,T,F,例构造命题公式,（,）,）的真值表：,4,真值表与等价公式,例写出命题公式,（,）的真值表,由上二例可见，个命题变元有组真值指派；个命题变元有,2,3,组真值指派，个则有个,2,n,个,真值指派。,P,Q,R,（,),F,F,F,F,F,F,T,F,F,T,F,F,F,T,T,T,T,F,F,T,T,F,T,T,T,T,F,T,T,T,T,T,4,真值表与等价公式,4,真值表与等价公式,2,等价公式,定义,：,如果对两个公式，不论作何种指派，它们真值均相同，则称，是逻辑等价的,.,并记作：,例：,P Q,P,P,QQ,F F,T,T,F T,T,T,T F,T,T,T T,T,T,4,真值表与等价公式,例：可以证明：,Q,P,原命题 逆反命题,逆命题 反命题,4,真值表与等价公式,列出真值表,由真值表得：,原命题,逆反命题；逆命题,反命题。,P,Q,PQ,Q,P,P,F,F,T,T,T,T,F,T,T,T,F,F,T,F,F,F,T,T,T,T,T,T,T,T,4,真值表与等价公式,由等价定义可知：,若,，则,若,，,C,，,则,4,真值表与等价公式,下面列出,13,组等价公式,（,1,）,双重否定律,（,2,）,幂等律,；,（,3,）,结合律,（）,（）；,（,）,（,）；,（,）,（,）,（,4,交换律,；,；,4,真值表与等价公式,（,5,）,分配律,（,）,（,）,（,）；,（,）,（,）,（,）,（,6,）,摩根律,（,）,；,（,）,（,7,）,吸收律,（,）,；,（,）,4,真值表与等价公式,（,8,）,蕴含律,（,9,）,等价律,（,）,（,）,（,10,）,零律,；,（,11,）,同一律,；,（,12,）,否定律,；,（,13,）,逆反律,4,真值表与等价公式,说明：,（）证明上述,3,组等价公式的方法可用真值表法,。,（,2,）,、,均满足结合律，,则在单一用,、,联结词组成的命题公式中，括号可以省去,。,4,真值表与等价公式,3,置换规则,定义,：,给定一命题公式A,，其中,P,1,、,P,2,P,n,是中的原子命题变元，,若（,1,）用某些命题公式代换,A,中的一些原子命题变元,P,i,（,2,）,用命题公式,B,i,代换,P,i,，,则必须用,B,i,代换,A,中的所有,P,i,由此而得到的新的命题公式,B,称为命题公式,A,的,代换实例,。,4,真值表与等价公式,讨论定义：,（）用命题公式只能代换原子命题变元，而不能去代换分子命题公式,。,（）要用命题公式同时代换同一个原子命题变元。,（,3,）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式,4,真值表与等价公式,例,设,A,：,（,Q,）若用（,）代换,A,中的，,得,B,：（Q,（,）是,A,的代换实例,.,而,B,：（,）,（,Q,）不是,A,的代换实例。,例,的代换实例有：（,）,，（,）,，,（,）等,所以，一个命题公式的代换实例有无限个。,4,真值表与等价公式,4.,等价置换,定义,：,给定一命题公式，是的任何部分，若也是一命题公式，则称是的,子命题公式,。,例：,：（,）,（,（,）,的子命题公式有：、,、（,）、,（,）、（,（,）、,（,）,（,（,）等。,4,真值表与等价公式,定理,：给定一命题公式，是的子公式。设,B,是一命题公式，若,B,，,并用,B,取代中的，从而生成一新的命题公式,B,，,则,B,。,从定理可见：一个命题公式,A,经多次取代，所得到的新公式与原公式等价。,例：证明：,（,）,（,）,4,真值表与等价公式,第三讲,5.,重言式与蕴含式,6.,其他联结词,P,P,P,P,P,P,F,T,T,F,T,F,T,F,定义,：,设公式中有,n,个不同的原子变元,p,1,p,n,(n,为正整数,),。该变元组的任意一组确定的值（,u,1,u,n,）,称为关于,p,1,p,n,的一个,完全指派,，其中,u,i,或为，或为。,5,重言式与蕴含式,1,命题公式的永真式、永假式和可满足式,例：举最简单例子：,定义,：,如果一个命题公式的所有完全指派均,使该公式取真值,，则该公式称为,永真式或重言式,。如果一个命题公式的所有完全指派均使,该公式取假值,，则该公式称为,永假式,。,既不是永真式，又不是永假式，则称此命题公式是,可满足式。,讨论：,二个永真式的析取、合取、蕴含、等价均为永真式。,5,重言式与蕴含式,5,重言式与蕴含式,定义,：当且仅当是一个永真式，我们称永真蕴含，记作：,说明：“,”读作“永真蕴含”，“蕴含”,“,”是关系符，,不为命题公式。,例：证明：,；,P,（）,列出真值表,证明：,（,）和（,）,为永真式,（,2,）用等价公式证：,（,）,（,）,T,（,）,（,）,T,P,Q,（,）,（,）,F,F,T,T,F,T,T,T,T,F,T,T,T,T,T,T,5,重言式与蕴含式,定理,：,命题公式,的充要条件是,为永真式。,5,重言式与蕴含式,证明：,（）充分性：,为永真式，即、有相同的真值，所以,。,（）必要性：,，即、有相同的真值表，所以,为永真式。,定理,：设、是二个命题公式,的充分必要条件是,且,。,证明：若,，则,为一永真式,由定律：,（,）,（,）,（,）,（,）且,（,）也为一永真式,即：,且,成立,反之若,且,，则,（）和（）为一永真式，所以,为一永真式，,则,也成立。,此定理把“,”和“,”之间建立了相应的关系。,5,重言式与蕴含式,下面给出常用的永真蕴含式,I,1,（,）,I,2,（,）,I,3,（,）,I,4,（,）,I,5,（,）,I,6,（,）,（,）,（I,7,（,）,（,）,（,）,I,8,（,）,（,）,（,）,I,9,P,5,重言式与蕴含式,I,10,I,11,（,）,I,12,（,）,I,13,（,）,（,）,（,）,证明上述永真蕴含式的方法为：把“,”关系符改为“,”,联结词，证明它为永真式。而证明永真式又有四种具体方法：,(1),真值表法,(2),等价公式法,5,重言式与蕴含式,（,3,）找出使单条件命题前件为“”的所有真值指派，试看能否导致后件均为“”，若为“”，则永真蕴含关系成立。,P,Q,PQ,F,F,T,F,T,T,T,F,F,T,T,T,5,重言式与蕴含式,例：,（,）,前件为“”的所有指派为、（,）均为“”，,为为“”，,也应为“”，,（,）,成立,（,4,）找出使单条件命题的后件均为“”的所有真值指派，试看前件的所有真值是否为“”，若是，则蕴含成立。,5,重言式与蕴含式,例：,（,）,后件为“”的所有条件是：为“”，,代入前件得,（,）若为，则,（,）为“”；,（,）若为，则,（,）为“”；,（,）,成立,若后件简单则可选用,(4),；若前件简单则可选用,(3),。,5,重言式与蕴含式,定理,：给定命题公式、，,若,，且,，则,。,证明：,，且,，,（,）,（,）为永真式，,由,I,6,：（,）,（,）,（,），,（,）也为永真式；即，,成立,5,重言式与蕴含式,推论,：,若,B,1,、,B1,B,2,B,m,，则,。,定理,：,给定一个命题公式、，若,，则,（,）,证明：,，,（,）,（,）为永真式，,由条件，若一定为“”，则、均为“”，,（,）也为“”，,结论：,（,）为“”。,5,重言式与蕴含式,6,其他命题联结词,其他命题联结词：,（）不可兼或（异或）,(a),符号：“,”（,），,，读作“异或”,(b),定义：（由真值表）,(c),异或的性质：,（,）,（,）,（,）,（,）,（,）,（可交换的）,（,）,（,）（可结合的）,P,Q,P,Q,F,F,F,F,T,T,T,F,T,T,T,F,6,其他命题联结词,（,）,（,）,（,）,（,对,可分配的）,若,，则有：,，6,其他命题联结词,（）“与非”联结词：,(a),符号“,”,，（,）读作：“与的否定”或“与非”,(b),定义：（由真值表）,（,）,（,）,P,Q,P,Q,F,F,T,F,T,T,T,F,T,T,T,F,6,其他命题联结词,(c),性质：,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）不可结合的,（,）,（,）,不可结合的,，,6,其他命题联结词,（）“或非”联结词：,(a),符号：“,”,（,）读作：“或的否定”或“或非”,(b),定义（由真值表给出）：,（,）,（,）,P,Q,F,F,T,F,T,F,T,F,F,T,T,F,6,其他命题联结词,c),性质：,（可交换的）,（,）,（,）,（,）,（,）,（,）,（,）不可结合的,（,）,（,）,不可结合的,；,(d),由（）和（）中的性质可见，,和,是互为对偶的。,6,其他命题联结词,（,4,）“蕴含否定”联结词：,(a),符号：,(b),定义,（由真值表给出）：,P Q,(PQ),“”,c,P,Q,P Q,T,T,F,T,F,T,F,T,F,F,F,F,c,c,第四讲,7.,对偶与范式,-,对偶式与析,(,合,),取范式,1,对偶原理（对偶定律）,定义,：,给定命题公式，若用,代换,，用,代换,，,用代换，用代换，得到另一个命题公式,A,*,，则称和,A,*,是互为对偶的。,例：写出下列命题公式的对偶式：,（,）,（,）,对偶式,A,*,7,对偶与,范式,讨论定义：,（）若命题公式中有联结词,，,，则必须把化成由联结词,，,组成的等价的命题公式，然后求它的对偶式；,例,：求,(P,Q),(P,R),的对偶式,7,对偶与,范式,（）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。,例：（,）,对偶式写成,（,）,，而不能写成,7,对偶与,范式,定理,：,（摩根推广定理）,设和,A,*,为对偶式,P,1,P,2,P,n,是出现在和,A,*,中的所有原子命题变元，于是有：,（,P,1,，,P,2,P,n,）,A,*,（,P,1,，,P,2,P,n,）,（,1,）,（,P,1,，,P,2,P,n,）,A,*,（,P,1,，,P,2,P,n,）,（）,7,对偶与,范式,证明,：由摩根定理,（,）,（）,（,）,（）,例：,设（，）,（,），验证上述定理：,7,对偶与,范式,证明：,(,),（，）,（，）,A,*,（,，）,A,*,（,，,，,）,有,（，）,=A,*,（,，,，,）,（）（,，,，,）,A,*,（,，）,（,）,有（,，,，,）,A,*,（,，）,7,对偶与,范式,定理,：若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若,，则,A*,B*,成立。,证明：,设：,P,1,、,P,2,P,n,是出现在和中的原子命题变元，,7,对偶与,范式,由,，,即（,P,1,，,P,2,P,n,）,（,P,1,，,P,2,P,n,）,（,P,1,，,P,2,P,n,）,（,P,1,，,P,2,P,n,）,由,摩根推广定理,*,（,P,1,，,P,2,P,n,）,*,（,P,1,，,P,2,P,n,）,7,对偶与,范式,*,（,P,1,，,P,2,P,n,）,*,（,P,1,P,2,P,n,）,为永真式,由于永真式的代换实例仍为永真式，所以用,P,i,代换,A*,和,B*,中的,P,i,（,1,in),则得：,*,（,P,1,，,P,2,P,n,）,*,（,P,1,，,P,2,P,n,）,即为：,*,P,1,，,P,2,P,n,）,*,（,P,1,，,P,2,P,n,）,7,对偶与,范式,7,对偶与范式,1.,范式,：把命题公式化归为一种标准的形式，称此标准形式为范式。,2,析取范式和合取范式：,定义,一个命题公式称为析取范式，当且仅当它具有形式：,A1A2An(n1),其中,A1,，,A2,，,，,An,都是由命题变元或其否定所组成的合取式。,如：（）（,）（,）是一个析取范式,求析取范式的方法可按下列三步（或四步）进行：,判定二个命题公式等价，,还可以使用范式方法。,7,对偶与,范式,（）利用等价公式：化去“,”,、“,”联结词，把命题公式变为与其等价的用,，,表达的公式。,例,:将“,”,深入到原子命题变元之前，并使变元之前最多只有一个“,”,词。,例：,（,）,7,对偶与,范式,（）利用“,”,对“,”,的分配，将公式化为析取范式。,（）除去永假项得最简析取范式。,例：求,（,）,（,）的析取范式,讨论定义：,从上例看出，一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等价的。,7,对偶与,范式,定义,一个,命题公式称为合取范式，当且仅当它具有形式：,A,1,A,2,A,n,(n1),其中,A,1,，,A,2,，,，,A,n,都是由命题变元或其否定所组成的析取式。,如：（）,（,）（,）是一个合取范式,7,对偶与,范式,求一个命题公式的合取范式的方法和求析取范式的方法类同：,（）利用等价公式：化去“”、“,”联结词，把命题公式变为与其等价的用,，,表达的公式。,（）将“,”,深入到原子命题变元之前，并使变元之前最多只有一个“,”,词。,（）利用“,”,对“,”,的分配就行；,（）去掉永真的析取项。,7,对偶与,范式,例：求,（,）,（,）的合取范式,原式,（,）,（,）,化去“,”,词,（,）,（,）,“,”,深入到变元前，并最多保留一个,（,）,（,）,（,）,“”,对“,”,的分配,（,）,（,）,（,）,（,）,（最简合取范式）,注：给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。,第四讲,7.,对偶与范式,-,主析取范式与主合取范式,7,对偶与,范式,3,主析取范式,定义,在个变元的合取项中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一次，则称此合取项为,小项,。,例,:,对二个命题变元讲,小项有,2,2,=4,个,即,、,、,、,对一个命题变元讲,小项有,2,1,=2,个,即,:,、,7,对偶与,范式,对三个命题变元讲，小项有,2,3,=8,个，,即：,、,、,、,、,、,、,、,推广到一般：个命题变元构成的不同小项有,2,n,个（,n,I,+,）。,7,对偶与,范式,定义,对给定的命题公式来讲，若干个,小项的析取,称为给定命题公式的,主析取范式。,定理,在真值表中，一个命题公式的所有真值为的指派所对应的小项的析取，即为此命题公式的主析取范式。,7,对偶与,范式,例：求出,、,、,（,）、,的主析取范式,T,F,F,T,T,T,F,T,T,T,F,T,T,F,T,F,T,F,T,F,T,T,F,F,（,）,7,对偶与,范式,则可直接写出各命题公式的主析取范式：,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,7,对偶与,范式,讨论此定理：,（,1,）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该命题公式真值为“”的行，对应写出小项的析取式，且一定是唯一的2,）,由真值表找小项的方法为：将表中值为“,T”,的对应真值指派中，,T,对应变元本身，,F,对应变元的否定。,（,3,）命题公式的主析取范式中小项的个数一定等于对应真值表中真值为“”的个数。,（,4,）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。,7,对偶与,范式,7,对偶与,范式,下面介绍不用真值表，直接求命题公式主析取范式的方法，分四步：,（）将命题公式化归为与其等价的析取范式；,（）除去永假项，合并合取项中相同项（例：,），变为最简析取范式。,（）对合取项补入没有出现的命题变元，即添加,（,P,），并应用分配律展开公式。,7,对偶与,范式,例：二个变元、利用“,”,对或“,”,的分配添项,（,）,（,）,（,）,（,）,（,）,（,）,（）合并相同的小项变为一项。,例：求（,（,）,的主析取范式,解：原式,（,）,（,）,-,（,1,）化为析取范式,7,对偶与,范式,（,）,-,（,2,）消去永假项，变为最简析取范式,（,）,（,（,）,（,）,（,）,（,）,-,（,3,）添项,（,）,（,）,-,（,4,）合并相同小项,7,对偶与,范式,例：证明,（,）,证明方法是写出二命题公式的主析取范式，看其是否相同：,（,）,（,）,（,）,（,）,（,）,而,（,（,）,（,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,主析范式相同，,有,（,）,7,对偶与,范式,4,主合取范式,定义,在个变元的析取项中，若每个变元与其否定，并不同时存在，且二者之一出现一次且仅出现一次，则称这种析取项为,大项,。,例：有二个变元,的大项有,2,2,=4,个，（,）、（,）、（,）、（,）,有个变元，则有,2,n,个大项（,n,I,+,）。,7,对偶与,范式,定义,对给定的命题公式来讲，若干个,大项的合取,称为给定命题公式的,主合取范式。,定理,在真值表中，一个命题公式的所有真值为,F,的指派所对应的,大项的合取,，即为此命题公式的主合取范式。,在真值表中真值为“”的个数等于主合取范式中大项的个数。,例：求出（,）、（,）、,（,）的主合取范式,7,对偶与,范式,（,）,T,T,F,T,T,T,F,F,T,T,F,T,T,F,T,T,T,F,T,F,T,F,F,F,直接写出其主合取范式：,（,）,（,）（大项）,（,）,（,）,（,）,7,对偶与,范式,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,7,对偶与,范式,讨论,（）与命题公式等价的主合范式中大项的个数等于其真值表中真值为“”的个数。,（,2,）由真值表找大项的方法为：将表中值为“”的对应真值指派中，,T,对应变元的否定，,F,对应变元本身。,（,3,）只要命题公式不是永真式，则一定可以写出对应与其等价的唯一的主合取范式。,7,对偶与,范式,（）可用主合取范式判定二个命题公式是否等价。,（）已知一个命题公式的主析取范式，则一定可以直接写出与其等价的主合取范式来。反之也行。,例：,（,）,（,）,（,）,主析取范式,（,）,主合取范式,7,对偶与,范式,（）对应于有个变元的命题公式，则一定有：,主析范式小项数主合范式大项数,2,n,下面介绍不用真值表求一命题公式主合取范式的方法：,（,1,）化为与命题公式等价的合取范式；,（,2,）除去真值为“,T,”,的析取项和除去析取项中相同变元且只保留一个，变为最简合取式；,（,3,）,对,析取项,补入没有出现的命题变元，即添加,（,P,），并应用分配律展开公式。,7,对偶与,范式,例如：、为二个变元，,即：,（,）,（,）,（,）,（,4,）合并相同的大项，保留一项。,例：求,（,）,的主合取范式,解：原式,（,）,（,）,（,）,（,）,（,）,7,对偶与,范式,5,主析,(,合,),取范式的编码表示,为了确保主析,(,合,),取范式的唯一性，作以下二个安排：,（,a,）各命题变元的位置安排一固定次序；,（,b,）对小项、大项安排一个次序。,（）小项极其编码,对于有个变元的命题公式，则最多可有,2,n,个,小项，用,m,0,m,1,m,2,n,-1,来表示。,下面列出三个变元，且、的位置已排定，则,P Q R,111,7,m,(7)十,P Q,R,110,6,m,(6),十,P,Q R,101,5,m,(5),十,P,Q,R,100,4,m,(4),十,P,Q,R,011,3,m,(3),十,P Q,R,010,2,m,(2),十,P,Q R,001,1,m,(1),十,P,Q,R,000,0,m,(0),十,小项表示,二进制数,十进制数,m,(i),十,7,对偶与范式,7,对偶与,范式,例：设一命题公式有五个变元，,P,0,P,1,P,2,P,3,P,4,（,次序已定），则必可写出,2,5,=32,个小项，,下列出,m,(11),十,和,m,(18),十,的小项表示：,即，,m,(11),十,m,(01011),二,P,0,P,1,P,2,P,3,P,4,）,m,(18),十,m,(10010),二,（,P,0,P,1,P,2,P,3,P,4,）,7,对偶与,范式,通过上例归纳出一通过小项,m,(i),十,求其,对应的小项的方法：,(a),把,(i),十,变换成等价的,(,J,0,J,1,J,n-1,),二,(b),由二进制写出其对应的小项：,例：求,（,）,（,）的编码表达式：（设、次序已定）,解：原式,（,）,（,）,（,）,（,）,7,对偶与,范式,m,(001),二,m,(010),二,m,(100),二,m,(101),二,m,(1),十,m,(3),十,m,(7),十,m,(6),十,m,1,m,3,m,7,m,6,1,3,6,7,（,）大项及其编码,用,M,0,M,1,M,2,n,-1,表示个变元的命题公式的大项。,求大项的方法：,7,对偶与,范式,(a),把,(i),十,变换成等价的,(,J,0,J,1,J,n-1,),二,(b),由二进制数写出其对应的大项：,例：求（,）,（,）的大项编码表示（设、次序已定）,7,对偶与,范式,解：原式,（,）,（,）,（,）,（,）,M,(000),二,M,(010),二,M,(100),二,(110),二,M,(0),十,M,(2),十,M,(4),十,M,(5),十,M0,M2,M4,M5,0,2,4,5,7,对偶与,范式,大项和小项编码约定刚好相反，,从上例中，（,）,（,）,1,3,6,7,0,2,4,5,例：写出（,）的主析和主合编码表示,7,对偶与,范式,T,T,T,T,F,T,F,T,F,T,F,F,P,Q,Q,P,P,Q1 0,2,3,主析取范式为,:(,）,（,）,（,）,主合取范式为：,P,Q,且,P,Q(,）,（,）,（,）,8,推理理论,按公认的推论规则，从前提集合中推导出一个结论来，这样的推导过程称为,演绎,，或者叫,形式证明,。,根据逻辑规则推导出来的任何结论称为,有效结论,。,8,推理理论,定义,：给定二个命题公式和，当且仅当,是一个永真式，即,A,B,，才可以说是从推导出来的，或称是前提的有效结论。,定义,：设,H,1,，,H,2,H,m,都是命题公式，当且仅当,H,1,H,2,H,m,，才可以说是前提集合,H,1,，,H,2,H,m,的有效结论。,8,推理理论,判别有效结论的过程就是论证过程，论证方法归纳分成三类：,（一）真值表技术；,（二）直接证明法；,（三）间接证明法。,真值表技术的主要依据是“,”,的真值表定义。,若,当且仅当,（,）为永真式。,P,Q,F,F,T,F,T,T,T,F,F,T,T,T,8,推理理论,真值表技术：,从给定真值表常用的判断方法有二种,：,（）检查真值表中,H,1,，,H,2,H,m,全部为“”的所有行，看结论是否也均为“”，若均为“”，则结论有效否则结论无效。,（）看结论为“”的所有行，检查每行前提,H,1,，,H,2,H,m,中是否至少有一个为，若有“”，则结论有效；若有均为“”的行，则结论无效。,例：试证明下列结论是否有效：,画出真值表：,8,推理理论,由真值表可见：,（），,有效,（）,，,无效,（）,，,（,）,有效,（）,，,（,）有效,（），,无效,P,Q,Q,（,）,F,F,T,T,T,T,T,F,T,T,T,F,T,F,T,F,F,F,T,T,F,T,T,T,F,F,F,T,8,推理理论,直接证明法,：,我们只讨论命题论证的有效性，而不去讨论命题的真假值；,在推论规则中不需要有真值表，也不需要对命题进行真值指派。,直接证明法,的依据是常用的永真蕴含式和等价公式。,8,推理理论,下面介绍二个规则：,P,规则：在推导的任何步骤上都可以引入前提（条件）,T,规则：在推导过程中，如果前面有一个或多个公式永真蕴含,S,，,则可以把,S,引入推导过程之中。或两个公式等价，将等价的公式引入推导过程之中。,例,1,：证明：,P,Q,Q R,PR,证：,8,推理理论,(1),P,Q,P,(2)P P,(3)Q T(1)(2),(4),Q R P,(5)R T(3)(4),也可以这样推理：,(1)P,Q,P,(2),Q R P,(3),P,R,T(1)(2),(4)P P,(5)R T(3)(4),8,推理理论,例,2,证明P,Q),(P,R,),(Q,S)S,R,证,:(1),(P,Q),P,(2),P,Q T,(1),(3),Q,S,P,(4),P,S T,(2)(3),(5),S,P T,(4),(6),P,R P,(7),S,R T,（,5,）,(6),(8)S,R,T,(7),8,推理理论,CP,规则：,要证明,P,(Q,R),，只要证明,PQ,R,就可以了。,即,:,如果能从,Q,和给定的前提集合,P,中推导出,R,来，则就能从前提集合中推导出（,Q,R,）,来。,8,推理理论,例,1,：,P,(Q S),R,P,Q,R,S,证,:(1)R,附加前提,(2),R,P P,(3),R,P T(2)4)P T(1)(3),(5)P,(Q S)P,(6),Q S T(4)(5),(7)Q P,(8)S T(6)(7),(9),R,S CP,8,推理理论,例,2:PQ,P,(P,Q),证,:,(1)P,附加前提,(2),PQ P,(3)Q T(1)(2),(4)P,Q T(1)(3),(5)P,(P,Q)CP,8,推理理论,3,间接证明法,：（反证法、归谬法）,定义,给出命题公式,H,1,H,2,H,m,，,H,1,H,2,H,m,具有真值为“,T,”,，,则命题公式集合,H,1,H,2,H,m,称为是一致的。否则称,H,1,H,2,H,m,是非一致的。,8,推理理论,定理,设,H,1,H,2,H,m,是一致的，同时设,C,是一个命题公式，如果前提集合,H,1,H,2,H,m,C,是非一致的，则一定有,H,1,H,2,H,m,C,成立。,证明：由条件,H,1,H,2,H,m,C,F,H,1,H,2,H,m,C,必定为永假式。而,H,1,H,2,H,m,是一致的，即为永真式，从而只有,C,为永假式，则,C,一定为永真式，,故,H,1,H,2,H,m,C,成立。,8,推理理论,例：证明,P,Q,(P,Q),证,:(1),(,(P,Q),假设前提,(2),P,Q T(1),(3)P T(2),(4),P,Q P,(5),P T(4),(6)P,P T(3)(5),(7)F,8,推理