第01章 命题逻辑.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,离散数学,参考书,耿素云 高等教育出版社,李盘林 高等教育出版社（面向,21,世纪教材）,徐秋亮 山东大学出版社,2,3,第一篇 数理逻辑,逻辑学：,研究思维形式及思维规律的科学,辨证逻辑,形式逻辑（思维的形式结构和规律）,思维的形式结构：,概念,判断,推理,数理逻辑：用数学方法即通过引入表意符号研究推理的学问，又名为符号逻辑。,4,第一章命题逻辑,退出,命题逻辑是研究由命题为基本单位构成的前提和结论之间的,可推导关系,。,命题逻辑，也称命题演算，记为,Ls,。它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。,5,1.1,命题及其表示方法,1.2,联结词,1.3,命题公式与翻译,1.4,真值表与等价式,1.5,重言式与蕴含式,1.6,其他联结词,1.7,对偶与范式,1.8,推理理论,6,1-1,命题及其表示方法,例如：,1+2=3,。,一、命题的概念,一个命题，总是具有一个“值”，称为真值。,真值只有即“真”和“假”，记作,T(,真,),和,F(,假,),。,所谓命题，是指具有非真必假,（不可兼）,的,陈述句,。,7,例,（,1,）明天下雨。,（,2,）人有五指。,（,3,）,一个偶数可表示成两个素数之和,。,（,4,）我学英语，或者我学日语。,（,5,）,1,101=110,（6,）,x+y 5,（,7,）全体立正！,（,8,）,8,大于,12,吗？,（,9,）这句话是假的。,是,是,是,是,不是,是,不是,不是,不是,8,判断命题规则,：,2.,真值必须,唯一,，与是否知道其真值无关。,3.,命题的真值会因人因时因地因上下文而异。,5.,变量含义不确定的不是命题。,4.,自指谓的谬论（结论是对其自身而言的陈述句），不是命题。,1.,只有,具有,确定真值,的,陈述句,才是命题，如感叹句，疑问句，祈使句等都不能判断其真假，不是命题。,9,命题分类：原子命题、复合命题。,例如：,（,1,）我看书，或者我听音乐。,（,2,）如果今天不下雨，那么我去看电影。,原子命题：,不能分解为更简单的陈述句。,复合命题：,由联结词、标点符号和原子命,题复合构成的。,10,目标语言（形式语言）：,表达判断的一些字母和公式符号的汇集。它一方面反映了自然语言的特征，另一方面它没有自然语言的二义性。,二、命题的表示法,命题标识符：大写字母、带下标的大写字母、数字等表示命题的符号。,例如：,P,：北京是中国首都。,2,：,北京是中国首都。,11,命题常量：表示一个确定的命题的命题标识符。,命题变元：任意命题的位置标志。命题变元,不是,命题。,当命题变元,P,用一个特定的命题取代时，,P,才能确定真值，也称对,P,进行,指派,。,原子变元：命题变元表示原子命题。,12,1-2,联结词联结词是构成复合命题主要组成部分，其作用相当于初等数学里的实数集上定义的,、,、,等运算符。通过联结词便可定义新的命题，可由组成它的相应命题的真值确定复合命题的真值。,值得注意的是逻辑联结词与日常自然用语中的有关联结词的,共同点和不同点,。,下面介绍五个常用的逻辑联结词：,，,。,13,P,P,T,F,F,T,由于“否定”修改命题是对单个命题进行操作的，称它为一元联结词。,（,1,）否定联结词,(,一元运算,),14,例如：,P,：上海是一个大城市。,P,：上海并不是一个大城市。上海是一个不大的城市。,15,例如：,P,：,今天下雨。,Q,：明天下雨。,P,Q,PQ,T,T,T,T,F,F,F,T,F,F,F,F,（,2,）合取联结词（二元运算）,上述命题的合取为：,PQ,：今天下雨而且明天下雨。,今天与明天都下雨。,16,例如：,李文与李武是兄弟,王芳和陈兰是好朋友,这两个命题中分别有,“,和,”,及,“,与,”,字，可是它们都是简单命题而不是复合命题。,17,例如：,P,：,我们去看电影；,Q,：,2+2=4,。,合取联结词可以连接两个以上意义毫不相干的命题，新命题的真值可根据两个命题的真值和合取联结词的真值表确定。,在自然语言中，上述命题是没有意义的，但在数理逻辑中，,P,，,Q,分别取真值后，,PQ,真值也必确定。,则：,PQ,：我们去看电影与,2+2=4,。,18,（,3,）析取联结词（二元运算）,P,Q,PQ,T,T,T,T,F,T,F,T,T,F,F,F,汉语中的,“,或,”,可表示,“,排斥或,”,，也可表示,“,可兼或,”,。,19,例,1,：,第一节课上数学课或者上英语课。,例,2,：,他可能是,100,米或,400,米赛跑的冠军。,例,3,：,他昨天做了二十或三十道习题。,是原子命题，不是复合命题。,（排斥或）,（可兼或）,析取指的是“可兼或”。,例,1,可表示为,：,(,PQ)(P Q),例,2,可表示为：,PQ,20,与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系。,例如：,2,小于,3,或者雪是黑的。,P,：,2,小于,3 Q,：雪是黑的,上述命题表示为：,PQ,21,（,4,）条件联结词（二元运算）,P,Q,PQ,T,T,T,T,F,F,F,T,T,F,F,T,例,1,：,如果我饿了，那么我就吃饭。,例,2,：,如果月亮从西边出来，则太阳也从西边出来。,22,条件命题,PQ,有多种方式陈述：,条件命题中，当前提为假时，结论不管真假，规定为“善意的推定”，条件命题的真值都取为,T,。,“如果,P,，那么,Q”,；“,P,仅当,Q”,；“,Q,每当,P”,；“,P,是,Q,的充分条件”；“,Q,是,P,的必要条件”等。,23,（,5,）双条件联结词,（二元运算）,P,Q,P,Q,T,T,T,T,F,F,F,T,F,F,F,T,例,1,：,32,当且仅当,03-2,。,例,2,：,燕子飞回南方，春天来了。,例,3,：,2,2=4,当且仅当雪是白的。,24,根据命题的符号表示法和联结词，给出一个命题，我们可以把它符号化。,练习：,把下列命题符号化,（,1,）,2+3,不大于,1,（,2,）天气炎热且正在下雨。,（,3,）气候很好或很热。,（,4,）如果,a,和,b,是偶数，则,a+b,是偶数。,（,5,）,n,是偶数当且仅当,n,2,是偶数。,25,命题分为：原子命题、复合命题。,复合命题的真值，取决于原子命题的真值，与原子命题之间是否有关系无关，与复合命题本身内容、含义无关。,、,具有对称性，,、没有联结词具有运算和操作性，从已知命题得到新命题。,小结,26,作业：,P8(1),，,(3),27,1-3,命题公式与翻译,一、回顾,命题的概念，命题的判断，联结词。,例如：,设,P,、,Q,为任意两个命题，则,P,，,PQ,，,(PQ)(PQ),等都是复合命题。,原子命题：不包含任何联结词的命题。,复合命题：至少包含一个联结词的命题。,28,命题公式（合式公式）,：,由,命题变元,和,联结词,组,成的有意义的字符串。,例如,：,PQR,，,PQ,，,(PQ)(Q),是不是合式公式呢？,定义：,单个命题变元和命题常元称为原子命题公式，简称原子公式。,二、命题公式,29,(3),如果,A,和,B,是合式公式，那么,AB,，,AB,，,AB,，,A,B,都是合式公式。,定义,1-3.1,合式公式,(,wff,),是由下列规则形成的字符串：,（递归式定义）,(1),单个原子公式是合式公式。,(2),如果,A,是合式公式，那么,A,是合式公式。,(4),当且仅当能够,有限次,地应用,(1),，,(2),，,(3),所得到的包含命题变元，联结词和括号的符号串是合式公式。,30,约定：,例如：,下列公式是否合式公式,(P)Q,，,(P(QR),，,(PQ,，,PQ),，,(R),。,前两个是合式公式，后两个不是,(1),最外层括号可以省略；,(2),联结词运算的优先次序为，,；,(3),相同的联结词按从左至右次序计算时，圆括号可省略。,31,注意：,命题公式本身无真假值，仅当命题变元用确定命题代入时，才得到一个命题。命题的真值依赖于代换变元的那些命题的真值。,例：,PQ,，,P,：,2+2=4;Q,：雪是白的。,则,PQ,值为真。,可将自然语言中的语句翻译成合式公式。,32,三、命题的翻译,把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为,命题的符号化,。,符号化应该,注意,下列事项,:,确定给定,句子是否,为命题。,句子中,连词是否,为命题联结词。,要,正确表示,原子命题和,适当选择,命题联结词。,33,例,1,：,如果李明是体育爱好者但不是文艺爱好者，那么李明不是文体爱好者。,例,2,：,今晚我在家里看电视或去体育场看球赛,P,Q,命题,T,T,F,T,F,T,F,T,T,F,F,F,A,B,C,P,Q,(P,Q),T,F,F,T,F,T,T,F,34,例,3,：,既聪明又用功。,P,Q,命题,T,T,F,T,F,T,F,T,F,F,F,F,例,4,：,虽聪明但不用功。,PQ,P,：聪明,Q,：用功,P Q,Q,P,Q,F,F,T,T,F,F,T,F,35,例,5,：,今天我上班,除非今天我病了。,P,Q,命题,T,T,T,T,F,T,F,T,T,F,F,F,例,6,：,张三李四都可做这件事。,P,：今天我病了,Q,：今天我上班,PQ,PQ,P,P,Q,F,T,F,T,T,T,T,F,36,1-4,真值表与等价式,P,Q,T,T,T,F,F,T,F,F,一、真值表,例,1,：,构造,P,Q,的真值表,定义,1-4.1,：,对公式中命题变元的每一种可能的真值指派，以及由此确定出的命题公式的真值所列成的表，称为命题公式的真值表。,P,F,F,T,T,PQ,T,T,T,F,37,注：,n,个命题变元组成的命题公式，共有 种真值情况。,为方便构造真值表，特约定如下：,特例：,有一类公式不论命题变元作,何种,指派，其真值,永为真（假）,，这类公式记为,T(F),。,命题变元按字典序排列。,对每个指派，以二进制数从小到大或从大到小顺序列出。,若公式较复杂，可先列出各子公式的真值,(,若有括号，则应从里层向外层展开,),，最后列出所求公式的真值。,38,二、等价公式,P,Q,P,Q,T,T,T,T,F,F,F,T,F,F,F,T,P,Q,PQ,T,T,T,T,F,F,F,T,T,F,F,T,PQ,T,F,T,T,(PQ)(PQ),T,F,F,T,39,注：,证明等价式的方法有两种：,1.,真值表法,2.,公式证明法,定义,1-4.2,A,，,B,为两命题公式，所有出现于,A,，,B,中的原子变元的任一组真值指派，,A,和,B,的真值都相同，则称,A,和,B,是,等价的或逻辑相等,，记为,A,B,。,40,例,5,：,证明,P,Q,(,PQ)(QP),证明：列出真值表,教材,P15,表,1-4.8,列出的命题定律，都可以用真值表予以验证。,P,Q,PQ,QP,P,Q,T,T,T,T,T,T,F,F,T,F,F,T,T,F,F,F,F,T,T,T,1,、真值表法：,(PQ)(QP),T,F,F,T,41,定义,1-4.3,：,如果,X,是,合式公式,A,的一部分，且,X,本身也是一个合式公式，则称,X,为,公式,A,的子公式。,证明：,X,是,A,的一部分，在任意指派下,X,与,Y,真值相同，用,Y,置换,X,，,得到的,B,与,A,等价，,A,B,2,、公式证明法,定理,1-4.1,：,设,X,是合式公式,A,的子公式，若,X,Y,，如将,A,中的,X,用,Y,来置换，所得到的公式,B,与公式,A,等价，即,A,B,，该置换称为等价置换。,例如：,Q(P(PQ),P(PQ),42,例,7,：,证明,Q(P(PQ),QP,证明：,(P(PQ),P,（,吸收律）,例,8,：,证明,(PQ)(P,Q),P,证明：,(,PQ)(P,Q),P(Q,Q),PT,P,左,QP,左,右,43,例,10,：,证明：,(PQ)(P(QR)(PQ)(PR),T,证明：左,(PQ),(P(QR),),(P Q),(P R),(PQ)(P(QR)(PQ)(PR),(PQ),(PQ)(PR),),(PQ)(PR),(PQ)(PR),(PQ)(PR),T,44,如何判断合式公式。,如何翻译合式公式。,如何构造合式公式的真值表。,如何证明等价式。,小结,45,作业：,P12(5)a),，,b),，,P17(1)d),，,e),，,P19(7)e),46,1-5,重言式与蕴含式,一、回顾,命题公式与翻译，真值表与等价式。,命题公式的真值表有一种,特例,，记为,T(F),。,47,定义,1-5.1,：,设,A,为一个命题公式，对,A,的分量,所有可能的,指派：,二、定义和性质,若,A,的真值皆为真，称,A,为,永真,式（重言式）；,若,A,的真值皆为假，称,A,为,永假,式（矛盾式）；,若,A,的真值,至少存在一个,为真，称A,为,可满足,式。,48,P,Q,(PQ)P,T,T,F,T,F,F,F,T,F,F,F,F,P,Q,(PQ),(P Q),T,T,T,T,F,T,F,T,T,F,F,T,永真式,永假式,49,则不论,A,和,B,的分量指派任何真值，,总有,A,为,T,且,B,为,T,，,定理,1-5.1,：,任何两个,重言式,（矛盾式）的合取或析取，仍是一个,重言式,（矛盾式）。,证明：设,A,和,B,为两个重言式，,故,AB,T,，,AB,T,。,50,定理,1-5.2,：,一个重言式（矛盾式），对同一分量都用任何合式公式,置换,，其结果仍为一重言式（矛盾式）。,证明：由于重言式的真值与分量的,指派无关,，故对同一分量以任何合式公式置换后，重言式的真值仍永为,T,。,51,例,1,：,证明,(PS)R)(PS)R),为重言式。,证明：,PP,T,，,用,(PS)R),置换,P,，即得。,52,定理,1-5.3,：,设,A,B,为两个命题公式，,A,B,当且仅当,A,B,为一个重言式。,双条件重言式（,和,联系）,A,B,A,B,A,B,T,T,T,F,F,T,证明：若,A,B,，则,A,，,B,有,相同的,真值，即,A,B,永为,T,。,反之，若,A,B,为重言式，则,A,B,永为,T,，故,A,、,B,的真值相同，,A,B,。,53,证明：由上表可知：,(PQ),(P Q),为重言式，由定理可得。,例,2,：,证明,(PQ),(PQ),P,Q,P,Q,PQ,PQ,(PQ),(PQ),(PQ),F,T,F,F,F,T,F,T,T,F,F,T,T,F,T,T,F,T,T,T,T,F,T,T,F,F,T,T,T,F,T,T,54,条件重言式,(,蕴含式,),定义：,若,PQ,，则,QP,称为,逆换式,；,PQ,称为,反换式,；,QP,称为,逆反式,。,由真值表可知：,PQ,QP,QP,PQ,定义,1-5.3,：,当且仅当,PQ,是一个重言式时称,P,蕴含,Q,，记为,P,Q,。,55,方法,1,：,假使,P,为,真的指派，若推出,Q,也为真，则,PQ,为重言式。,P,Q,PQ,Q,P,T,T,T,T,T,F,F,F,F,T,T,T,F,F,T,T,蕴含式的证明方法：,方法,2,：,假使,Q,为假的指派，若推出,P,也为假，那么,QP,为重言式，则,PQ,为重言式。,56,例,3,：,推证：,Q(PQ),P,证法,1,：假定,Q(PQ),为,T,，,则,Q,为,T,且,(PQ),为,T,，,推出,Q,为,F,，由,PQ,为,T,，,推出,P,为,F,，即,P,为,T,。,证法,2,：假定,P,为,F,，则,P,为,T,。,P21,表,1-5.2,所列各蕴含式都可如上述推理方法证明。（记住）,若,Q,为,F,，则,PQ,为,F,，即,Q(PQ),为,F,。,若,Q,为,T,则,Q,为,F,，即,Q(PQ),为,F,。,57,证明：,P,Q,，则,P,Q,为重言式，,定理,1-5.4,：,设,P,，,Q,为任意两个命题公式，,P,Q,的,充分必要条件,是,P,Q,且,Q,P,。,双条件重言式和蕴含式之间的关系,P,Q,(PQ)(QP),，,PQ,为,T,，,QP,为,T,，,即,P,Q,，,Q,P,。,反之，,P,Q,，,Q,P,，,则,P,Q,为,T,，,P,Q,是重言式，,P,Q,。,58,设,A,、,B,、,C,为合式公式，,(1),若,A,B,且,A,是,重言式，则,B,必是重言式。,蕴含的性质,(2),若,A,B,，,B,C,，则,A,C,，即蕴含关系是,传递的,。,证明：,A,B,，,B,C,，,AB,，,BC,为重言式，,(AB)(BC),为重言式。,由基本蕴含,11,可得,(AB)(BC),AC,，,由性质,1,，可得,AC,为重言式。,59,(3),若,A,B,，且,A,C,，那么,A,(BC),。,证明：由已知得，,AB,和,AC,为重言式。,若,A,为,T,，则,B,和,C,都为,T,，即,BC,为,T,，,则,A(BC),为,T,。,若,A,为,F,，则,A(BC),必为,T,。,60,若,A,B,且,C,B,，则,AC,B,。,证明：,AB,为,T,，,CB,为,T,，,(AB)(CB),为,T,，,则,(AC)B,为,T,即,ACB,为,T,。,AC,B,。,61,1-6,其他联结词,(1)PQ,(P Q),；与非,(2)PQ,(P Q),；或非,(3)P,Q,(P Q),；条件否定,(4)P Q,(P,Q),：双条件否定,(,不可析取或，异或,),一、其他联结词,62,二、联结词的定义,P,Q,PQ,PQ,P,Q,P Q,T,T,F,T,F,F,T,F,T,T,T,T,F,T,T,T,F,T,F,F,T,F,F,F,63,三、各联结词的性质（,P24,，,P26,）,1,）不可兼析取的性质,（,1,）交换律,（,2,）结合律,（,3,）分配律,（,4,）,(P Q),(PQ)(P Q),（,5,）,(P Q),(P,Q),（,6,）,P P,F,，,P P,T,F P,P,，,T P,P,64,定理,1-6.1,：,设,P,，,Q,，,R,为命题公式。若,P Q,R,，则,P R,Q,，,Q R,P,且,P Q R,为一,矛盾式,。,证明：若,P Q,R,，,则,P R,P P Q,F Q,Q,Q R,Q P Q,F P,P,P Q R,R R,F,65,(1)PP,(PP),P,(2)(PQ)(PQ),(PQ),PQ,(3)(PP)(QQ),PQ,(PQ),PQ,2,）与非的性质,66,(1)PP,(PP),P,(2)(PQ)(PQ),(PQ),PQ,(3)(PP)(QQ),PQ,PQ,3,或非的性质,注意：,对于包含 ，,，的复合命题，其合式公式类似于定义,1-3.1,。,67,对于含有,n,个命题变元的命题公式，按真值表是否相同去分类，,n,个命题变元的命题公式共可以构成,个不同的真值表。,四、联结词功能完全组,2,个命题变元可组成多少个不等价（不同的真值表）的命题公式？,对于二元的命题公式，除命题常元,T,、,F,及命题变元本身外，命题联结词,9,个,就够了。,见表,1.6.5,。,68,P,Q,(PQ)(QP),PQ,PQ,PQ,(PQ),PQ,(PQ),反之，由所学的,9,个联结词能够描述所有的公式，但能否减少呢？,根据定义可知：,扩充的,4,个,联结词可用前面介绍的5,个,联结词描述，而又有下列命题公式。,69,定义：,联结词功能完全组,G,，,满足下列两个条件：,如常见的联结词功能完全组,(1)G,中联结词构成的公式能,等价表示,任意命题公式；,(2)G,中,任一,联结词,不能用其余,联结词等价表示。,70,1-7,对偶与范式,一、对偶,在前面介绍的命题定律中，大多是,成对,出现的，这些成对出现的定律就是对偶性质的反映。利用对偶式的命题定律，可以扩大等价式的个数。,定义,1-7.1,：,在给定的仅含有，,，的命题公式中，将换成，将换成，,T,和,F,互换，所得公式,A,*,称为,A,的对偶式。,71,例,1,：,求,(PQ),R,，,PT,的对偶式。解：对偶式分别为：,(PQ),R,，,PF,。,例,2,：,求,PQ,，,PQ,的对偶式。,解：,PQ,(PQ),，故对偶式为,(PQ),，即,PQ,。,72,定理,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,),证明：由德,摩根定律,PQ,(PQ),PQ,(PQ),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,),73,例,3,：,A(S,W,R),是,S(WR),，,证明,A,*,(S,W,R),S(WR),证明：,A,*(,S,W,R),A(S,W,R),(S(WR),S(WR),74,定理,1-7.2,：,设,P,1,P,2,P,n,是出现在公式,A,和,B,中的所有原子变元，如果,A,B,则,A*,B*,。,证明：设,A(P,1,P,2,P,n,),B(P,1,P,2,P,n,),A(P,1,P,2,P,n,),B(P,1,P,2,P,n,),A(P,1,P,2,P,n,),A,*(P,1,P,2,P,n,),B(P,1,P,2,P,n,),B,*(P,1,P,2,Pn,),A*(P,1,P,2,P,n,),B,*(P,1,P,2,P,n,),A*(P,1,P,2,P,n,),B,*(P,1,P,2,P,n,),75,例,4,：,A(P,Q,R),是,P(Q(RP),，求它的对偶式,A,*,(P,Q,R),（只含有,，,和,的公式,）。,解：由前面的知：,A,(P,Q,R),是,P(Q(RP),P(Q(RP),(P(Q(RP),P(Q(RP),(P(Q(RP),76,小结,1,、重言式包括双条件重言式（等价式）和条件重言式（蕴含式），如何证明。,2,、其他联结词如何转化为,4,个基本联结词，如何联结词完全功能组。,3,、如何求解对偶式和相关证明。,77,作业：,P23,（,1,）,d,）（,8,）,e,）,f,）,P39,（,6,）,78,同一命题公式可以有多种相互等价的表达形式，为了把命题公式规范化，需要讨论公式的标准型。,二、公式的标准型,范式,例如,：,P,Q,(PQ)(QP),(PQ)(QP),79,1,、范式,定义,1-7.2,：,一个命题公式称为合取范式，当且仅当它具有,A,1,A,2,A,n,其中,A,1,，,A,2,，,，,A,n,都是由,命题变元,P,或,其否定,P,所组成的,析取式（,P Q,）,。,80,定义,1-7.3,：,一个命题公式称为析取范式，当且仅当它具有,A,1,A,2,A,n,其中,A,1,，,A,2,，,A,n,都是由,命题变元,P,或,其否定,P,所组成的,合取式（,P Q,）,。,81,例如,：,(P,Q)(,PQR),Q,(PQ)(PQ)(PR),析取范式,合取范式,注意：,一个命题变元或其否定既可以是合取式，也可以是析取式。,如,P,，,Q,等。,82,是否任何一个命题公式都能求得它的合取范式或析取范式呢？,求范式算法：,使用命题定律，消去公式中除,，,和,以外的所出现联结词；,使用德,摩根律将公式中出现的联结词,都移到命题变元之前；,利用结合律、分配律等将公式化成析取范式或合取范式。,83,例,5,：,求,(P(Q,R),S,的析取范式和合取范式。,解：公式,(P(Q,R),S,P(QR)S,P(QR)S,析取范式,(,PSQ),(,PSR),合取范式,84,利用范式对公式进行,判断,。,2,、范式的应用,(1),公式,A,为,永假式,的充要条件,是,A,的,析取,范式中每个合取式中至少包含一个命题变元及其否定。,(2),公式,A,为,永真式,的充要条件,是,A,的,合取,范式中每个析取式至少包含一个命题变元及其否定。,85,(1)P(QR)(PR),(2)(PQ)P,解,：,(,1),P(QR)(PR),(2),(PQ)P,例如：,判断下列公式为何种公式,(,PQRP)(PQRR),永真式,(PQ)P,(PP)(QP),可满足式,86,P(QR),3,、范式不唯一性,(PQ)(PR),(PP)(PR)(QP)(QR),87,为识别公式间是否等价，需要进一步讨论主范式。,三、公式的主范式,1,、主析取范式,定义,1-7.4,：,在含有,n,个命题变元的合取式中，若每个命题变元与其否定,不同时存在,，但二者之一必须出现一次,且仅,一次，则称该合取式为小项。,(1),小项的概念,88,例：,PQ,，,PQ,，,PQ,，,PQ,问题：,n,个变元可有多少小项？,2,n,89,下标表示法：,命题变元按字典顺序排列，命题,变元,对应,1,，变元的,否定,对应,0,。对小项依二进制编码（或用十进制编码）。,例：,PQ,PQ,m,11,(m,3,),PQ,m,01,(m,1,),PQ,m,10,(m,2,),m,00,(m,0,),90,a,、每一小项当其真值指派与编码相同时，其值为,T,；,(2),小项的性质,b,、任意两个小项合取为假；,c,、全体小项的析取值永为真；,(PQ),(PQ),(PQ)(PQ),PQ m,11,(m,3,)PQ m,01,(m,1,),(PQ),(PQ),91,定理,1-7.3,：,在真值表中，一个公式的真值为,T,的指派所对应的小项的析取，即为此公式的主析取范式。,定义,1-7.5,：,在给定公式的析取范式中，其,合取式,都是,小项,，则称该范式为主析取范式。,(3),主析取范式的定义,(4),主析取范式的求解方法,例如：PQR)(PQR),a,、真值表法,永假式有没有主析取范式？,92,PQ,(PQ)(PQ)(PQ),P,Q,PQ,T,T,T,T,F,F,F,T,T,F,F,T,93,b,、等价公式法,a),划为析取式；,b),删除永假的合取式；,c),化简重复出现的变元（幂等律）；,d),补进未出现的变元（同一律）。,94,PQ,PQ,P,Q,PQ,T,T,T,T,F,F,F,T,T,F,F,T,(PQ)(PQ)(PQ),(,P(QQ),(Q(PP),(,(PQ)(PQ),(PQ)(PQ),m,00,m,01,m,11,95,注意：,任意含,n,个命题变元的非永假命题公式，其主析取范式是唯一的。,主析取范式唯一性说明，如果公式的主析取范式相同，则证明两个公式的等价。,96,(1),大项的概念,2,、主合取范式,定义,1-7.6,：,在含有,n,个命题变元的析取式中，若每个命题变元与其否定,不同时存在,，但二者之一必须出现一次,且仅,一次，则称该析取式为大项。,例：,PQ,，,PQ,，,PQ,，,PQ,n,个变元可有多少大项？,97,下标表示法：,命题变元按字典顺序排列，,命题变元,对应,0,，变元的,否定,对应,1,。对大项依二进制编码（或用十进制编码）。,例：,PQ,PQ,PQ,PQ,M,00,(M,0,),M,10,(M,2,),M,01,(M,1,),M,11,(M,3,),98,a,每一大项当其真值指派与编码相同时，其值为,F,；,(2),大项的性质,b,、任意两个大项析取为真；,c,、全体大项的合取值永为假。,99,定义,1-7.7,：,在给定公式的合取范式中，其析取式都是大项，则称该范式为主合取范式。,(3),主合取范式的定义,注意：,任意含,n,个命题变元的非永真命题公式,A,都存在与其等价的主合取范式。,100,(3),主合取范式的求法,P,Q,(PQ)Q,T,T,T,T,F,F,F,T,T,F,F,F,(PQ)Q,(PQ)(PQ),a,、真值表法,定理,1-7.4,：,在真值表中，一个公式的真值为,F,的指派所对应的大项的析取，即为此公式的主析取范式。,M,10,M,00,M,2,M,0,101,b,、公式法,a),划为合取范式；,b),删除永真的简单析取式；,c),化简重复出现的变元（幂等律）；,d),补进未出现的变元（同一律）。,102,例如,:,(PQ)Q,(PQ)Q,注意：,任意含,n,个命题变元的非永真命题公式，其主合取范式是唯一的。,(PQ)(Q(PP),(PQ)(PQ)(PQ),(,PQ)(PQ),M,2,M,0,103,3,、主析取范式与主合取范式之间的关系,例如：,(PQ)Q,m,1,m,3,由主析取范式求主合取范式,:,a),求出主析取范式中没有的小项；,b),对,a,中的小项，换成大项；,c),写出,b,大项的合取，即为该式的主合取范式。,则,(PQ)Q,M,0,M,2,104,(1),用以,判定,公式类型,4,、主范式的应用,设,A,为含,n,个变元的主范式：,a,、若,A,T,，或可化为与其等价的含,2,n,个小项的主析取范式，则,A,为永真式。,b,、若,A,F,，或可化为与其等价的含,2,n,个大项的主合取范式，则,A,为永假式。,c,、若,A,不与,F,等价，且又不含,2,n,个大项，则,A,为可满足式。,105,例：,判断下列公式为何类公式,(PQ)Q,？,(2),证明,等价式成立,(PQ)Q,M,0,M,2,m,1,m,3,；,大小项数目均不到,4,，故为可满足式。,分别求出两个给定公式的主范式，若范式相同，则给定的两公式等价。,106,范式,范式分析取范式和合取范式,主析取范式和主合取范式,小项和大项,m M,T,T m,11,（,m,3,）,M,11,（,M,3,）,T,F,m,10,（,m,2,）,M,10,（,M,2,）,F,T m,01,（,m,1,）,M,01,（,M,1,）,F,F,m,00,（,m,0,）,M,00,（,M,0,）,107,1-8,推理理论,在逻辑学中，把从,前提出发,，依据公认的推理,规则,，推导出一个,结论,，这一过程称为,有效推理或形式证明,。所得的结论叫,有效结论,。,在数理逻辑中，集中研究的是用来从前提导出结论的,推理规则,和,论证原理,。这里最关心的不是结论的真实性，而是,推理的有效性,。与这些规则有关的理论称为推理理论。,108,定义,1-8.1,：,设,A,和,C,是两个命题公式，当且仅当,AC,为一重言式，即,A,C,，称,C,是,A,的,有效结论,。,这个定义可,推广,到有,n,个前提的情况。,设,H,1,，,H,2,，,，,H,n,，,C,是命题公式，当且仅当,H,1,H,2,H,n,C,称,C,是一组前提,H,1,，,H,2,，,，,H,n,的有效结论。,一、基本定义,109,(1),真值表法,二、论证方法,判断有效结论的过程就是论证过程，,论证方法,基本分为,设,P,1,，,，,P,m,是出现于前提,H,1,，,，,H,n,和结论,C,中的全部命题变元，列出这个真值表，即可看出,H,1,H,2,H,n,C,是否成立。,110,例,1,：,一份统计报表的错误，或者是材料不可靠，或是因计算错误，这份报表有错不是材料不可靠，所以这份报表是由于计算有错误。,P,Q,P,PQ,(PQ),P,(PQ),P,Q,T,T,F,T,F,T,T,F,F,T,F,T,F,T,T,T,T,T,F,F,T,F,F,T,P(PQ),Q,解：,P,：材料不可靠,Q,：计算错误,111,例,2,：,如果今天我病了，那么我没来上课。今天我病了。所以今天我没来上课。,解：,P,：今天我病了，,Q,：我没来上课,(PQ),P)Q,112,由一组前提、公认的推理规则，利用已知的等价或蕴含公式，推出有效的结论。,(2),直接证法：,P,规则：前提在推导中的任何时候都可引入使用。常用的蕴含式和等价式见表,P43,。,T,规则：前面已导出的有效结论可作为后续推导引入。,113,例如：,证明,(PQ)(PR)(QS),SR,(1),PQ P,(2),PQ 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,114,定义,1-8.2,：,假设公式,H,1,，,H,2,，,，,H,n,中的命题变元为,P,1,，,P,2,，,，,P,m,的一些真值指派，如果能使,H,1,H,2,H,n,的真值为,T,，,则称公式,H,1,，,H,2,，,，,H,n,是,相容,的。如果对于,P,1,，,P,2,，,，,P,m,的每一组真值指派，使得,H,1,H,2,H,n,的真值均为,F,，,则称公式,H,1,，,H,2,，,，,H,n,是,不相容,的。,(3),间接证法,115,设要证：,H,1,H,2,H,n,C,，记为,S,C,。,即证其逆反式,CS,为永真，,即,CS,为永真，,故,CS,为永假，,所以要证,H,1,H,2,H,n,C,。,只要证明,C,与,H,1,H,2,H,n,是不相容的。,116,例,3,：,证明,AB,，,(BC)可逻辑推出,A,(1)AB P,(2)A P(,附加前提,),(3),(BC)P,(4),B C T(3)E,(5)B T(1),(2),I,(6),B T(4)I,(7)B,B T(5),(6)I,117,若要证：,H,1,H,2,H,n,(RC,),，,记为,S,RC,CP,规则：结论为,RC,时，,R,作为附加前提引入，推出后件,C,。,因为,S(RC),S(RC),(SR)C,(SR)C,(SR)C,将,R,作为附加前提，如有,(SR),C,，即证得,S,(RC),。,118,例,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,119,推理理论：,1,、真值表法：,2,、直接证法：,P,规则，,T,规则。,3,、间接证法：利用不相容的概念，,CP,规则。,120,小 结,1,、范式包括合取范式和析取范式，如何求公式的范式。,2,、主范式中的大，小项以及他们之间的关系。,3,、推理中的概念以及推理论证的方法和规则。（真值表法，直接法，间接法，,P,规则，,T,规则，,CP,规则）,121,作业：,P39,(,4,)a),，,(,5),a),，,P46(4),a),122,本章总结,本章首先引入命题及逻辑联结词，并在此基础上定义了公式以及公式的等价、蕴涵、范式等，然后用等价式、蕴涵式等进行命题演算和推理。,123,基本概念命题,命题的,判断,命题,符号化,翻译,合式公式,联结词,证明,等价式（双条件重言式）和重言式（条件重言式蕴含式）,求解,对偶式和,范式,（合取范式和析取范式以及主范式中的大，小项以及他们之间的关系），,利用公式的范式,判断公式,是恒真或恒假或可满足,推理论证的方法和规则,124,P8(1),a),真,命题，,b),不是命题，,c),是命题，真值不确定，,d),不是命题，,e),真命题，,f),真命题，,g),假命题，,h),不是命题，,i),不是命题,（,3,）,a)(,P,R)Q,，,b)Q,R,，,c),P,，,d),P,Q,P12(5),a),P,Q,，,P,：你给我写信，,Q,：它在土中丢失了。,b),P,Q,R,，,P,：张三去，,Q,：李四去，,R,他去。,c),(P,Q,),，,P,：我们划船，,Q,：我们跑步。,d),P,(Q,R),，,P,：你来了，,Q,：他唱歌，,R,：你伴奏。,125,P,Q,R,P,Q,(P,Q),R,T,T,T,T,T,T,T,F,T,F,T,F,T,T,T,T,F,F,T,F,F,T,T,F,F,F,T,F,F,F,F,F,T,T,T,F,F,F,T,F,P17(1)d,）,126,P,Q,