离散数学第一章.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,第一章 命题逻辑,1.,命题,2.,命题联结词,3.,命题变元与命题公式,4.,等价式,5.,永真蕴含式,6.,命题联结词总结,7.,范 式 和 判 定,8.,推论规则和证明方法,1,1,命题,定义,：,具有唯一真值的陈述句叫命题,。,讨论定义：,（）命题可以是真的，或者是假的，但不能同时为真又为假。,（）命题分类：,),原子命题,（基本命题、本原命题）：一个命题，不能分解成为更简单的命题。,例：我是一位学生。,2,1,命题,),分子命题,（复合命题）：,若干个原子命题使用适当的联结词,所组成的新命题,例：我是一位学生和他是一位工人,(3),命题所用符号：常用大写个英文字母表示命题。用、表示。,(4),命题中所有的“真”用“”表示，,命题中所有的“假”用“”表示。,3,1,命题,例,：判断下列语句是否为命题。,陈述句一般为命题,（,1,）十是整数。（）,（,2,）上海是一个村庄。（）,（,3,）今天下雨。,（,4,）加拿大是一个国家。（）,（,5,）是偶数而是奇数。,（,6,）她不是护士。,（,7,）,（,8,）今天是星期天。,4,1,命题,命令句，感叹句，疑问句均不是命题。,（,1,）把门关上！,（,2,）你到哪里去？,语句既为真，同时又包含假的不是命题，这样的句子称为“,悖论,”。,（,3,）他正在说谎。,（在命题逻辑中不讨论这类问题）,5,2,命题联结词,在命题演算中也有类似的日常生活中的联结词称做：,“命题联结词”,下面先介绍五个常用的命题联结词。,否定词,：,（否定运算、非运算）,（）符号,读作“非”，“否定”,设命题为，则在的前面加否定词,，变成,，,读做“的否定”或“非”,6,2,命题联结词,（）定义：严格由真值表定义,（）举例：,：北京是一座城市。,：北京不是一座城市。,：每一种生物均是动物。,F,：有一些生物不是动物。,T,这里,不能讲成“每一种生物都不是动物”为假命题了。,对量化命题的否定，除对动词进行否定外，同时对量化词也要加以否定。,P,P,T,F,F,T,7,2,命题联结词,合取词,（“合取”、“积”、“与”运算）,符号“,”,设，为两个命题，则,称与的合取，读作：“与”、“与的合取”、“并且”等。,定义（由真值表给出）：,8,2,命题联结词,P,Q,P,Q,Q,P,F,F,F,F,F,T,F,F,T,F,F,F,T,T,T,T,真值表如下,：,9,2,命题联结词,当且仅当和的真值均为“”，则（,）的真值为“”。否则，其真值为“”。,注意,：和是互为独立的；地位是平等的，和的位置可以交换而不会影响,的结果。,10,2,命题联结词,举例：,(,a)P：,王华的成绩很好,Q：,王华的品德很好。,则,：王华的成绩很好并且品德很好。,(,b)P：,我们去种树,Q：,房间里有一台电视机,则,：我们去种树与房间里有一台电视机。,11,2,命题联结词,(,c)P：,今天下大雨,Q：3+3=6,则,：今天下大雨和,3+3=6,由例,(,b)(c),可见，在日常生活中，合取词应用在二个有关系的命题之间。而在逻辑学中，合取词可以用在二个毫不相干的命题之间。,12,2,命题联结词,(,d),下列语句不是合取联结词组成的命题。,P:,王大和王二是亲兄弟。,Q:,他打开箱子然后（而后）拿出一件衣服来。,13,2,命题联结词,析取词,（或运算）,（）符号“,”,设、为二个命题，则（,）称作与的“析取”，读作：“或”。,（）定义（由真值表给出）：,14,2,命题联结词,当且仅当、均为“”时，（,）为“”。否则，其真值为“”,P,Q,P Q,F,F,F,F,T,T,T,F,T,T,T,T,真值表,如右：,15,2,命题联结词,区分“可兼或”与“不可兼或（异或，排斥或）”,析取词为可兼或即,:,P,和,Q,均为“,T”,时（,PQ）,为“,T”,例如：,灯泡有故障或开关有故障。,今晚写字或看书。,今天下雨或打雷。,以上例句均为可兼或。,16,2,命题联结词,“不可兼或”中当,P,和,Q,均为“,T”,时，则,P,异或,Q,为“,F”。,（,异或用“,”,表示）,P,Q,P,Q,F,F,F,F,T,T,T,F,T,T,T,F,17,2,命题联结词,例：,他通过电视看杂技,或,到剧场看杂技。,他乘火车去北京,或,乘飞机去北京。,以上两句均为不“可兼或”。,18,2,命题联结词,单条件联结词：,（“蕴含”联结词、蕴含词）,（）符号“,”,，读作：“如果,则”,、“蕴含”,、为二个命题，（,）为新的命题，读作：“如果则”，“蕴含”，“仅当”，“当且”，“是的充分条件”。,（）定义,19,2,命题联结词,（由真值表定义）：,P,Q,PQ,F,F,T,F,T,T,T,F,F,T,T,T,20,2,命题联结词,当为“”，为“”时，则,（,）为“”，否则（,）均为“”。,：称为前件、条件、前提、假设,：称为后件、结论。,（）举例：,P：,我拿起一本书,Q：,我一口气读完了这本书,21,2,命题联结词,PQ：,如果我拿起一本书，则我一口气读完了这本书。,(,b)P：,月亮出来了,Q：33=9,PQ：,如果月亮出来了，则,33=9,。,通常称：,(,a),为形式条件命题。,前提和结果有某种形式和内容上的联系。,22,2,命题联结词,(,b),为实质条件命题。,前提和结果可以有联系，也可以没有联系，只要满足单条件命题的定义。,所以,是形式条件命题一定是实质条件命题,反之不一定。“,”,是实质条件命题。,例：,：我买到了鱼；,:,我吃鱼。,23,2,命题联结词,：如果我买到了鱼，则我吃鱼。,但“如果我没买到鱼，则我吃鱼”，这在日常生活中是不可能的，但在单条件命题的定义中是允许的。,24,2,命题联结词,可以证明：,Q,P,原命题 逆反命题,逆命题 反命题,25,2,命题联结词,列出真值表,由真值表得：,原命题,逆反命题；逆命题,反命题。,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,26,2,命题联结词,双条件联结词,（“等价”词、“同”联结词、“等同”词）,（）符号“,”,设、为二个命题，则,读作：“当且仅当”，“等价”,“,是的充分必要条件”。,（）定义（见真值表）：,27,2,命题联结词,真值表,:,每当和的真值相同时，则（,）的真值为“”，否则（,）的真值为“”。,P,Q,P,Q,F,F,T,F,T,F,T,F,F,T,T,T,28,2,命题联结词,（）举例：,（,a）,设,：,ABC,是等腰三角形,：,ABC,有两只角相等,：,ABC,是等腰三角形当且仅当,ABC,中有两只角相等。,29,2,命题联结词,（,b）,下面均为等价联结词：,春天来了当且仅当燕子飞回来了。,平面上二直线平行，当且仅当这二直线不相交。,当且仅当雪是白色的。,30,2,命题联结词,（）,中，、的地位是平等的，、交换位置不会改变真值表中的值。,（）当且仅当,仅当,当且,31,2,命题联结词,命题联结词在使用中的优先级,（）先括号内，后括号外,（）运算时联结词的优先次序为：,（,由高到低）,32,2,命题联结词,（）联结词按从左到右的次序进行运算,例,（,）可省去括号,因为“”运算是可结合的。,（,）,可省去括号因为符合上述规定,而,（,）,中的括号不能省去，因为“,”,不满足结合律。,33,2,命题联结词,（）最外层的括号一律均可省去,（,）可写成,命题联结词小结：,（）五个联结词的含义与日常生活中的联结词的含义大致相同。,（）“或”可分为可兼或（,）和异或（,）（不可兼或）,34,2,命题联结词,(3),除“,”,为一元运算外，其余四个均为二元运算。,(4)“,”,分为形式条件和实质条件命题，,当前件为“”时，不论后件怎样，则单条件命题的真值均为“”,。,(5),命题联结词是命题或命题之间的联结词，而不是名词之间、数字之间和动词之间的联结词。,35,2,命题联结词,以上介绍了五种常用的联结词及其相应的复合命题形式。数理逻辑的特点是把逻辑推理变成类似数学演算的完全形式化了的逻辑演算，为此，首先要把推理所涉及到的各命题符号化。,步骤如下：,找出各简单命题，分别符号化。,找出各联结词，把简单命题逐个联结起来。,36,2,命题联结词,例.,将下列命题符号化：,（,1,）李明是计算机系的学生，他住在,312,室或,313,室。,（,2,）张三和李四是朋友。,（,3,）虽然交通堵塞，但是老王还是准时到达了车站。,（,4,）只有一个角是直角的三角形才是直角三角形。,（,5,）老王或小李中有一个去上海出差。,37,2,命题联结词,解：,（,1,）首先用字母表示简单命题。,P：,李明是计算机系的学生。,Q：,李明住在,312,室。,R：,李明住在,313,室。,该命题符号化为：,P,（Q,R）,（2）,张三和李四是朋友。是一个简单句,该命题符号化为：,P,38,2,命题联结词,（3,）首先用字母表示简单命题。,P：,交通堵塞。,Q：,老王准时到达了车站。,该命题符号化为：,P,Q,（4）,首先用字母表示简单命题。,P：,三角形的一个角是直角。,Q：,三角形是直角三角形。,该命题符号化为：,P,Q,39,2,命题联结词,（5,）首先用字母表示简单命题。,P：,老王去上海出差。,Q：,小李去上海出差。,该命题符号化为：,P,Q,也可符号化为：,（,P,Q）（PQ）,或者,（,P,Q）（PQ）,40,命题公式,约定：,（）我们只注意命题的真假值，而不再去注意命题的汉语意义。,（）对命题联结词，我们只注意真值表的定义，而不注意它日常生活中的含义。,命题公式,命题常元：表示确定的命题,T，F。,命题变元：以真假为其变域之变元，或没有指定真值的命题。常用大写英文字母,表示。,41,命题公式,命题公式,：由命题变元、常元、联结词、括号，以规定的格式联结起来的字符串。,定义,：命题公式可按下述法则来生成：,）孤立的命题变元是一个命题公式。,）若是命题公式，,也为命题公式。,）若、是命题公式，则（,）、（,）、（,）、（,）均为命题公式。,42,命题公式,）当且仅当有限次使用,（）（）（）所生成的公式才是命题公式。,例如：,(,(,P Q)，(P,(Q R)，(PQ),R)，P,都是命题公式。而,(,P,)，(P,),都不是命题公式,命题公式的真值表,:,命题变元用特定的命题来取代，这一过程称为对该命题变元进行,指派。,命题公式可以看成是一个以真假值为定义域和真假值为值域的一个函数。,写成,(,x),43,命题公式,例如：公式,P,(Q R),定义三元函数,Y(P，Q，R),P,(Q R),定义,：命题公式,A,在其所有可能的赋值下取得的值列成的表称为,A,的真值表。,构造真值表的步骤如下：,1),找出给定命题公式中所有的命题变元，列出所有可能的赋值。,2),按照从低到高的顺序写出命题公式的各层次。,3),对应每个赋值，计算命题公式各层次的值，直到最后计算出整个命题公式的值。,44,命题公式,P,Q,P Q,（,）,（,）,）,F,F,F,F,T,F,T,T,F,T,T,F,T,T,F,T,T,T,T,F,例构造命题公式,（,）,）的真值表：,45,命题公式,例写出命题公式,（,）的真值表,P,Q,R,（,),F,F,F,F F,F,F,T,F F,F,T,F,F F,F,T,T,T T,T,F,F,T F,T,F,T,T F,T,T,F,T F,T,T,T,T T,46,命题公式,由上二例可见，个命题变元有组真值指派；个命题变元有,2,3,组真值指派，,个则有个,2,n,个,真值指派。,命题公式的永真式、永假式和可满足式,例：举最简单例子：,47,命题公式,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,或为，或为。如果对于中部分变元赋以确定值，其余变元没有赋以确定的值，则这样的一组值称为公式的关于该变元组的,部分指派,。,定义,：,凡使公式取真的指派称为的,成真指派,。,48,命题公式,定义,：,如果一个命题公式的所有完全指派均为成真指派，则该公式称为,永真式,。如果一个命题公式的所有完全指派均为成假指派，则该公式称为,永假式,。既不是永真式，又不是永假式，则称此命题公式是,可满足式。,讨论：,（）永真式的否定为永假式（,）；永假式的否定为永真式（,）。,（）二个永真式的析取、合取、蕴含、等价均为永真式。,49,4,等价式,等价式,定义,：,如果对两个公式，不论作何种指派，它们真值均相同，则称，是逻辑等价的，亦说（）等价于（）。,并记作：,50,4,等价式,例：,P Q,P,P,Q,Q,F F,T,T,F T,T,T,T F,T,T,T T,T,T,51,4,等价式,例：判断公式,A：(P,Q)(PQ),与,B：,(P,R)(PR),是否等价。,解：,列该公式的真值表：,52,4,等价式,P,Q,R,Q,P,Q,PQ,R,P,R,PR,A,B,T,T,T,F,T,T,F,T,T,T,T,T,T,F,F,T,T,T,T,T,T,T,T,F,T,T,T,T,F,T,T,T,T,T,F,F,T,T,T,T,T,T,T,T,F,T,T,F,F,T,F,F,T,F,F,F,T,F,F,F,T,T,T,F,F,F,F,F,T,T,T,F,F,F,T,F,F,F,F,F,T,T,F,T,T,F,F,F,53,4,等价式,定理,：,命题公式,的充要条件是,为永真式。,说明：,“,”,为等价关系符，,表示和有等价关系。,不为命题公式,“,”,为等价联结词（运算符），、为命题公式，则（,）也为一命题公式。,54,4,等价式,证明：,（）充分性：,为永真式，即、有相同的真值，所以,。,（）必要性：,，即、有相同的真值表，所以,为永真式。,例：证明,；,55,4,等价式,P,Q,P,P,P,Q,P,Q,F,F,F T F,T T T,F,T,F T F,T T T,T,F,T T T,F T F,T,T,T T T,T T T,由定理可知：,若,，则,若,，,C，,则,56,4,等价式,下面列出组等价公式,（,1,）,双重否定律,（,2,）,同等律,；,（,3,）,交换律,；,；,（,4,）,结合律,（,）,（,）；,（,）,（,）；,（,）,（,）,57,4,等价式,（5,）,分配律,（,）,（,）,（,）；,（,）,（,）,（,）,（,6,）,摩根律,（,）,；,（,）,（,7,）,吸收律,（,）,；,（,）,58,4,等价式,（8,）,蕴含律,（,9,）,等价律,（,）,（,）,（,10,）,零律,；,（,11,）,同一律,；,（,12,）,互补律,；,（,13,）,输出律,（,）,59,4,等价式,（14,）,归缪律,（,）,（,）,（,15,）,逆反律,说明：,（）证明上述组等价公式的方法可用真值表法，把,改为,所得的命题公式为永真式，则,成立。,60,4,等价式,（2,）,、,均满足结合律，,则在单一用,、,联结词组成的命题公式中，括号可以省去,。,（,3,）每个等价模式实际给出了无穷多个同类型的具体的命题公式。,例如：,(,PQ),(P Q)，,(PQ)(RS),(P Q)(R S)，,(PQ)R),(P Q)R),61,4,等价式,置换规则,定义,：,给定一命题公式，其中,P,1,、,P,2,P,n,是中的原子命题变元，,若（,1,）用某些命题公式代换中的一些原子命题变元,P,i,（2）,用命题公式,i,代换,P,i,，,则必须用,i,代换中的所有,P,i,由此而得到的新的命题公式称为命题公式的,代换实例,62,4,等价式,讨论定义：,（）用命题公式只能代换原子命题变元，而不能去代换分子命题公式,。,（）要用命题公式同时代换同一个原子命题变元。,（）永真式的代换实例仍为永真式；反之代换实例为永真式时，则不能断定原公式也一定是永真式。,63,4,等价式,例：,为一永真式，若用任何命题公式代换，则仍为永真式,为一个可满足的命题公式，若用代换，则得（,）为永真式，但（,）并不是永真式。,（）一个命题公式的代换实例有许多个，但不一定都等价于原来的命题公式,64,4,等价式,例,设：,（,Q,）若用（,）代换中的，,得：（,）,（,Q,（,）是的代换实例，,而：（,）,（,Q,）不是,B,的代换实例。,例,的代换实例有：（,）,，（,）,，,（,）等,所以，一个命题公式的代换实例有无限个。,65,4,等价式,下面讨论取代过程（置换规则）：,定义,：,给定一命题公式，是的任何部分，若也是一命题公式，则称是的,子命题公式,。,例：,：（,）,（,（,）,的子命题公式有：、,、（,）、,（,）、（,（,）、,（,）,（,（,）等。,66,4,等价式,定理,：给定一命题公式，是的子公式。设,B,是一命题公式，若,B，,并用,B,取代中的，从而生成一新的命题公式,B，,则,B。,从定理可见：一个命题公式,A，,经多次取代，所得到的新公式与原公式等价。,例：证明：,（,）,（,）,67,4,等价式,（,）,（,）,例：证明：,（,）,（,（,）,（,）,（,）为一永真式,68,4,等价式,证明：,原式：（,）,（,（,）,（,）,（,）,（,）,（,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,它是,（永真式）的代换实例，永真式的代换实例仍为永真式！,69,4,等价式,对偶原理（对偶定律）,定义,：,给定二个命题公式和,A,*,，,若用,代换,，用,代换,，,用代换，用代换，其中一个命题公式由另一个命题公式得来，则称和,A,*,是互为对偶的，而联结词,和,也是互为对偶的,例：写出下列命题公式的对偶式：,（,）,（,）,对偶式,A,*,70,4,等价式,讨论定义：,（）若命题公式中有联结词,，,，则必须把化成由联结词,，,组成的等价的命题公式，然后求它的对偶式；,例,：求,(,P,Q),(P,R),的对偶式,71,4,等价式,（）在写对偶式时，原命题公式中括号不能省去，必须按优先级的次序画上括号，并在求其对偶式时仍将保留括号。,例：（,）,对偶式写成,（,）,，而不能写成,72,4,等价式,定理,：,（摩根推广定理）,设和,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,）（）,73,4,等价式,证明,：由摩根定理,（,）,（）,（,）,（）,不难看出：,一个命题公式的否定等价于它的对偶式，且把变元的否定代替每一个变元。,例：,设（，）,（,），验证上述定理：,74,4,等价式,证明：,(),（，）,（，）,A,*,（,，）,A,*,（,，,，,）,（）（,，,，,）,A,*,（,，）,（,）,有（,，,，,）,A,*,（,，）,75,4,等价式,定理,：若二个命题公式互为等价，则它们的对偶式也互为等价，亦即若,，则,A*,B*,成立。,证明：,已知：、为任一命题公式，且,，要证明,A,*,B,*,设：,P,1,、,P,2,P,n,是出现在和中的原子命题变元，,76,4,等价式,由,，,即（,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,）,77,4,等价式,*,（,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,）,78,4,等价式,例：证明：,（）,（,）,（,（,）,（,）,（）（,）,（,（,）,（,）,证明：（）左边,（,）,（,（,）,（,）,（,）,（,）,（,）,（,）,79,4,等价式,（）左边,（,）,（,）,（,）,（,）,（,）,结论：（）和（）是互为对偶的。,80,5,永真蕴含式,定义,：命题公式,称为永真蕴含命题公式，当且仅当,是一个永真式，,记作：,说明：“,”读作“永真蕴含”，“蕴含”，“能推得”,“,”是关系符，,不为命题公式。,例：证明：,；,P,（）,列出真值表,证明：,（,）和（,）,为永真式,81,5,永真蕴含式,（）可用等价公式证：,（,）,（,）,T,（,）,（,）,T,P,Q,（,）,（,）,F,F,F T F,F T F,F,T,F T T,F T F,T,F,T T T,F T T,T,T,T T T,T T T,82,5,永真蕴含式,定理,：设、是二个命题公式,的充分必要条件是,且,。,证明：若,，则,为一永真式,由定律：,（,）,（,）,（,）,（,）且,（,）也为一永真式,即：,且,成立,反之,且,则,也成立,此定理把“,”和“,”之间建立了相应的关系。,83,5,永真蕴含式,下面给出常用的永真蕴含式,I,1,（,）,I,2,（,）,I,3,（,）,I,4,（,）,I,5,（,）,I,6,（,）,（,）,（,）,I,7,（,）,（,）,（,）,I,8,（,）,（,）,（,）,I,9,P,84,5,永真蕴含式,I,10,I,11,（,）,I,12,（,）,I,13,（,）,（,）,（,）,证明上述永真蕴含式的方法有三种：,（）把“,”关系符改为“,”,联结词，证明它为永真式。,(,a),真值表法,(,b),命题演算法,85,5,永真蕴含式,（）找出使单条件命题前件为“”的所有真值指派，试看能否导致后件均为“”，若为“”，则永真蕴含关系成立。,P,Q,PQ,F,F,T,F,T,T,T,F,F,T,T,T,86,5,永真蕴含式,例：,（,）,前件为“”的所有指派为、（,）均为“”，,为“”，,为“”，,也应为“”，,（,）,成立,（）找出使单条件命题的后件均为“”的所有真值指派，试看前件的所有真值是否为“”，若是，则蕴含成立。,87,5,永真蕴含式,例：,（,）,后件为“”的所有条件是：为“”，,代入前件得,（,）若为，则,（,）为“”；,（,）若为，则,（,）为“”；,（,）,成立,若后件简单则可选用,(3),；若前件简单则可选用,(2),。,二种方法是互为独立的，只需使用一种证明就行。,88,5,永真蕴含式,讨论一下永真式,可得出三个结论：,（）若一个命题公式等价于一个永真式，则该公式一定为永真式。,（）若一个永真的命题公式永真蕴含一个命题公式，则此命题公式一定也为永真式。,（）若一个永假的命题公式永真蕴含一个命题公式，则该公式可能是永真式、永假式或可满足的。,89,5,永真蕴含式,定理,：给定命题公式、，,若,，且,，则,。,证明：,，且,，,（,）,（,）为永真式，,由,I,6,：（,）,（,）,（,），,（,）也为永真式；即，,成立,90,5,永真蕴含式,推论,：,若,B,1,、B,1,B,2,B,m,，则,。,定理,：,给定一个命题公式、，若,，则,（,）,证明：,，,（,）,（,）为永真式，,由条件，若一定为“”，则、均为“”，,（,）也为“”，,结论：,（,）为“”。,91,5,永真蕴含式,上述也可用等价公式证明它：,（,）,（,）,（,）,（,）,（,）,（,）也为永真式,（,）成立,定义,：,设,H,1,H,2,.,H,m,均为命题公式，若,（,H,1,H,2,H,m,）,，则称：,H,1,H,2,.,H,m,共同蕴含，并记作：,H,1,H,2,.,H,m,。,92,5,永真蕴含式,定理,：若（,H,1,H,2,H,m,）,P,，,则（,H,1,H,2,H,m,）,（,）。,证明：,（,H,1,H,2,H,m,P,）,（,H,1,H,2,H,m,P,）Q,（,H,1,H,2,H,m,）,（,P,Q）,（,H,1,H,2,H,m,）,（,P,Q）,H,1,H,2,.,H,m,（,）也为永真式,（,H,1,H,2,.,H,m,）,（,）,成立,93,6,命题联结词总结,其他命题联结词：,（）不可兼或（异或，异）,(,a),符号：“,”（,），,，读作“异或”,(,b),定义：（由真值表）,(,c),异或的性质：,（,）,（,）,（,）,（,）,（,）,（可交换的）,（,）,（,）（可结合的）,P,Q,P,Q,F,F,F,F,T,T,T,F,T,T,T,F,94,6,命题联结词总结,（,）,（,）,（,）,（,对,可分配的）,若,，则有：,，,95,6,命题联结词总结,（）“与非”联结词：,(,a),符号“,”,，（,）读作：“与的否定”或“与非”,(,b),定义：（由真值表）,（,）,（,）,P,Q,P,Q,F,F,T,F,T,T,T,F,T,T,T,F,96,6,命题联结词总结,(,c),性质：,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）不可结合的,（,）,（,）,不可结合的,，,97,6,命题联结词总结,（）“或非”联结词：,(,a),符号：“,”,（,）读作：“或的否定”或“或非”,(,b),定义（由真值表给出）：,（,）,（,）,P,Q,F,F,T,F,T,F,T,F,F,T,T,F,98,6,命题联结词总结,(,c),性质：,（可交换的）,（,）,（,）,（,）,（,）,（,）,（,）不可结合的,（,）,（,）,不可结合的,；,(,d),由（）和（）中的性质可见，,和,是互为对偶的。,99,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,100,6,命题联结词总结,（）不同真值表的命题公式：,按命题公式的生成规则，用联结词可组成无限个命题公式。下面讨论这些命题公式有多少种不同的真值表：,(,a),若命题变元只有一个，则用联结词组成的命题公式由四种不同的真值表，即为：,P,0,1,2,3,F,F,F,T,T,T,F,T,F,T,101,6,命题联结词总结,所有依赖于的命题公式均等价于这四个中的一个,(,b),若有二个命题变元、，则命题公式的不同真值表有：,2,2,2,=2,4,=16,种。,推广到一般：若有个变元的命题公式，则可构成不同的真值表为,2,2,n,（,个）。,102,6,命题联结词总结,（）二元运算中的全部联结词总结：,、,、,是五个基本联结词。,到此为止，一个符号系统已定义完毕，它们是：,命题变元,:,、,、,值,:,、,运算符,:,、,、,、,、,、,括号,:,（）,关系符,:,、,。,C,103,6,命题联结词总结,全功能联结词集合：,定义,：,一个联结词集合，用其中联结词构成的式子足以把一切命题公式等价的表达出来，则称此联结词集合为全功能联结词集合。,定义,：,设有一联结词集合，,若（）用中的联结词的等价式能表达任何的一个命题公式；,104,6,命题联结词总结,（）删除中的任一联结词，从而形成一个新的联结词集合，至少有一个命题公式不能用中的联结词的等价式来表示，则称,A,为,最小的全功能联结词集合,。,我们可以证明：,，；,，；,，；,均为全功能联结词集合，且均是,最小的全功能联结词集合,。,例：用上述最小全功能联结词集合中的联结词单一表达下述命题公式：,105,6,命题联结词总结,（,）,，,（,）,（,）,，,（,）,，,(,),，,（,）,（,）,）,（,）,）,（,）,（,）,（,）,c,c,106,7,范式和判定,如何判定命题公式为永真式、永假式和可满足的呢或二个命题公式等价，归纳有三种方法：,（,1,）真值表法：对于变元的所有真值指 派，看对应命题公式的真值。,（,2,）命题演算方法,：,化简命题公式至最简式，看是否存在和 （,）、（,）等价，若不则为可满足的。,（,3,）范式方法：本节就介绍此法。,107,7,范式和判定,什么叫范式,把命题公式化归为一种标准的形式，称此标准形式为范式。,什么叫判定,以有限次步骤来决定命题公式是否为永真式、永假式，还是可满足的，或者判定二个命题公式是否等价等这一类的问题，统称为判定问题。,讨论范式和主范式的目的就是为了进行判定。,108,7,范式和判定,析取范式和合取范式：,设命题变元为：、，则：（,）的析取式称为“和”；（,）的合取式称为“积”。,定义,：命题公式的变元和变元的否定之积称为,基本积,，而变元和变元的否定之和称为,基本和,。,109,7,范式和判定,例：设、为二个命题变元，则：,，,，,，,，,，,称为基本和；,，,，,，,，,，,称为基本积。,若“基本和”或“基本积”中的子公式”，称为此基本积（和）的,因子,。,例：,的因子有：,、,、,、,110,7,范式和判定,定理,：,一个基本积必定是永假式，,它的充分必要条件是，它至少包含一对因子，其中一个是另一个的否定。,证明：,（,）充分条件：、,为基本积中一对因子,该基本积一定为永假式。,（,）,（,）,（,（,）,（,）必要条件：基本积为永假式,基本积中包含、,这对因子。,111,7,范式和判定,反证法：假设基本积中不包含、,这样的因子，且为永假式。若给基本积中的命题变元指派“”，而命题变元的否定指派为“”，,在基本积中不包含、,这对因子，,基本积得到的真值为“”，这和假设相矛盾；,基本积中必然包含、,这对因子才能使基本积为“”。,112,7,范式和判定,定理,：,一个“基本和”必定为永真式，,其充要条件（当且仅当）是，它至少包含一对因子，其中一个是另一个的否定。,定义,：,与给定命题公式等价的一个公式，如果是由基本积之和组成，则称它为命题公式的,析取范式,。并记为：,P,P,1,P,2,P,n,（n,I,+,）。,其中,P,1,，P,2,P,n,均为基本积。,方法可按下列三步（或四步）进行：,113,7,范式 和判定,（）利用等价公式：化去“,”,、“,”联结词，把命题公式变为与其等价的用,，,表达的公式。,例,:,，,（,）,（,）,（,）,（,）,（）将“,”,深入到原子命题变元之前，并使变元之前最多只有一个“,”,词。,例：,（,）,114,7,范式和判定,（）利用“,”,对“,”,的分配，将公式化成为析取范式。,（）除去永假项得最简析取范式。,例：求,（,）,（,）的析取范式：,解：原式,(,（,）,（,）,),(,（,）,（,）,),115,7,范式和判定,(,（,）,（,）,),(,（,）,（,）,),-（1,）,化去,词,（,）,（,）,（,）,-（2,）,将“,”,深入到变元前面，并最多保留一个,（,）,（,）,（,）,（,）,（,）,-（3,）“,”,对或“,”,的分配，化成为析取范式,（,）,（,）,-（4,）最简析取范式,116,7,范式 和判定,讨论定义：,（）从上例看出，一个命题公式的析取范式不是唯一的，但同一命题公式的析取范式一定是等价的。,（）若一个命题公式的析取范式中每一个基本积均为永假式，则该公式也一定为永假式。,即，,P,P,1,P,2,P,n,（P,1,，P,2,P,n,均为基本积）,则,，,当,P,1,P,2,P,n,F,时,，,一定为永假式。,(,可用来判定是否为永假式,),117,7,范式和判定,例,：（析取范式）,（,）,（,）,永假式,定义,：,与给定命题公式等价的一个公式，如果它是由基本和之积所组成，则称它是给定命题公式的,合取范式,。,并表示成：,Q Q1 Q2,Qn,，,(n,I,+,),其中,Q,!,Q,2,Q,n,均为基本和。,118,7,范式和判定,求一个命题公式的合取范式的方法和求析取范式的方法类同：,第（）、（）步相同；,第（）利用“,”,对“,”,的分配就行；,第（）去掉永真的析取项。,119,7,范式和判定,例：求,（,）,（,）的合取范式,原式,（,）,（,）,化去“,”,词,（,）,（,）,“,”,深入到变元前，并最多保留一个,（,）,（,）,（,）,“”,对“,”,的分配,（,）,（,）,（,）,（,）,（最简合取范式）,120,7,范式和判定,讨论定义：,（）给定一命题公式的合取范式不是唯一的，但同一命题公式的合取范式一定是等价的。,（）若一个命题公式的合取范式中的各基本和的真值为“”，则该命题公式一定是永真式。,(,可用来判定是否为永真式,),例：（,）,（,）,（,）,121,7,范式和判定,主析取范式。,定义,：,在个变元的基本积中，若每个变元及其否定并不同时存在，且二者之一出现一次且仅出现一次，则称此基本积为,极小项,。,例：对二个命题变元讲，极小项有,2,2,=4,个,，即,：,、,、,、,对一个命题变元讲，极小项有,2,1,=2,个，即：、,122,7,范式和判定,对三个命题变元讲，极小项有,2,3,=8,个，,即：,、,、,、,、,、,、,、,推广到一般：个命题变元构成的不同极小项有,2,n,个（,n,I,+,）。,使得每个极小项为真的赋值仅有一个。,123,7,范式和判定,定义,：,对给定的命题公式来讲，仅含有极小项的析取的等价式称为给定命题公式的,主析取范式。,定理,：,在真值表中，一个公式的真值为的指派所对应的极小项的析取，即为此公式的主析取范式。,124,7,范式和判定,例：求出,、,、,（,）、,的主析取范式,（,）,F,F,T,T,F,T,F,T,F,T,F,T,T,F,T,T,T,F,T,T,T,F,F,T,125,7,范式和判定,则可直接写出各命题公式的主析取范式：,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,讨论此定理：,（,1,）只要命题公式不是永假式，则一定可以根据该命题公式的真值表直接写出其主析取范式，其方法是找出该公式为“”的行，对应写出极小项的析取式，且一定是唯一的。,126,7,范式和判定,（2,）若命题公式是含有,n,个变元的永真式，则它的主析取范式一定含有,2,n,个极小项。,（,3,）若二个命题公式对应的主析取范式相同，则此二个命题公式一定是等价的。,（,4,）命题公式的主析取范式中极小项的个数一定等于对应真值表中真值为“”的个数。,127,7,范式和判定,下面介绍不用真值表，直接求命题公式主析取范式的方法，分四步：,（）将命题公式化归为与其等价的析取范式；,（）除去永假项，合并基本积中相同项（例：,），变为最简析取范式。,（）利用添变元的方法，将所有基本积变为极小项。,128,7,范式和判定,例：二个变元、，利用“,”,对或“,”,的分配添项,（,）,（,）,（,）,（,）,（,）,（,）,（）合并相同的极小项变为一项。,例：求（,（,）,的主析取范式,解：原式,（,）,（,）,-（1,）化为析取范式,129,7,范式和判定,（,）,-（2,）消去永假项，变为最简析取范式,（,）,（,（,）,（,）,（,）,（,）,-（3,）添项,（,）,（,）,-（4,）合并相同最小项,130,7,范式和判定,例：证明,（,）,证明方法是写出二个命题公式的主析范式，看其是否相同：,（,）,（,）,（,）,（,）,（,）,而,（,（,）,（,（,）,（,）,（,）,（,）,（,）,（,）,（,）,（,）,主析范式相同，,有,（,）,131,7,范式和判定,主合取范式,定义,：,在个变元的基本和中，若每个变元与其否定，并不同时存在，且二者之一出现一次且仅出现一次，则称这种基本和为极大项