第一章 命题逻辑.ppt

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