离散数学第01章

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,人民邮电出版社,高等学校21世纪教材,高等学校21世纪教材,电子教案,离散数学,人民邮电出版社,10/1/2024,1,第一章命题逻辑,命题逻辑，也称命题演算，记为,Ls。,它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。数理逻辑是用数学方法即通过引入表意符号研究推理的学问。因此，数理逻辑又名为符号逻辑。,命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。,退出,1.1 命题与联结词,1.2 命题变元和合式公式,1.3 公式分类与等价公式,1.4 对偶式与蕴涵式,1.5 联结词的扩充与功能完全组,1.6 公式标准型范式,1.7 公式的主范式,1.8 命题逻辑的推理理论,1.1 命题与联结词,. 命题的概念,所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值,真和假，且二者只能居其一。真用1或,T,表示，假用0或,F,表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。,如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。,命题分为两类，第一类是原子命题，原子命题用大写英文字母,P，Q，R,及其带下标的,P,i,，Q,i,，R,i,，,表示。,第二类是复合命题，它由原子命题、命题联结词和圆括号组成。,. 命题联结词,定义1.1.1,设,P,表示一个命题，由命题联结词,l,和命题,P,连接成,l,P,，,称,l,P,为,P,的否定式复合命题，,l,P,读“非,P,”。,称,l,为否定联结词。,l,P,是真，当且仅当,P,为假；,l,P,是假，当且仅当,P,为真。否定联结词“,l,”,的定义可由表1.1.1表示之。,由于否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。,定义1.1.2,设,P,和,Q,为两个命题，由命题联结词将,P,和,Q,连接成,P,Q,，,称,P,Q,为命题,P,和,Q,的合取式复合命题，,P,Q,读做“,P,与,Q,”，,或“,P,且,Q,”。,称为合取联结词。,当且仅当,P,和,Q,的真值同为真，命题,P,Q,的真值才为真；否则，,P,Q,的真值为假。合取联结词的定义由表1.1.2表示之。,定义1.1.3,设,P,和,Q,为两个命题，由命题联结词把,P,和,Q,连接成,P,Q,，,称,P,Q,为命题,P,和,Q,的析取式复合命题，,P,Q,读做“,P,或,Q,”。,称为析取联结词。,当且仅当,P,和,Q,的真值同为假，,P,Q,的真值为假；否则，,P,Q,的真值为真。析取联结词的定义由表1.1.3表示之。,由定义可知，析取联结词表示“可兼和”，“不可兼和”另有别的联结词定义之。,与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系，有关例子就不再给出了。,定义1.1.4,设,P,和,Q,为两个命题，由命题联结词把,P,和,Q,连接成,P,Q,，,称,P,Q,为命题,P,和,Q,的条件式复合命题，简称条件命题。,P,Q,读做“,P,条件,Q,”,或者“若,P,则,Q,”。,称为条件联结词。当,P,的真值为真而,Q,的真值为假时，命题,P,Q,的真值为假；否则，,P,Q,的真值为真。条件联结词的定义由表1.1.4表示之。,在条件命题,P,Q,中，命题,P,称为,P,Q,的前件或前提，命题,Q,称为,P,Q,的后件或结论。条件命题,P,Q,有多种方式陈述：,“如果,P,，,那么,Q,”；“,P,仅当,Q,”；“,Q,每当,P,”；“,P,是,Q,的充分条件”；“,Q,是,P,的必要条件”等。,在日常生活中，用条件式表示前提和结论之间的因果或实质关系，如例1.1.4中的，这种条件式称为形式条件命题。然而在命题逻辑中，一个条件式的前提并不要求与结论有任何关,系，这种条件式称为实质条件命题。,采用实质条件式作定义，不单是出于“善意推断”，主要是因为前提与结论间有无因果和实质关系难以区分，而且实质条件式已包含了形式条件式，更便于应用。,定义1.1.5,令,P,、,Q,是两个命题，由命题联结词,把,P,和,Q,连接成,P,Q,，,称,P,Q,为命题,P,和,Q,的双条件式复合命题，简称双条件命题，,P,Q,读做“,P,当且仅当,Q,”，,或“,P,等价,Q,”。,称,为双条件联结词。,当,P,和,Q,的真值相同时，,P,Q,的真值为真；否则，,P,Q,的真值为假。双条件联结词,的定义由表1.1.5表示之。,在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的，请读者认真去领会。,1.2 命题变元和合式公式,. 命题变元,在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元指派真值。,命题常元和命题变元均可用字母,P,等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下：,定义1.2.1,以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。,2.合式公式,通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的公式称为合式公式。,定义1.2.2,单个命题变元和命题常元称为原子命,题公式，简称原子公式。,定义1.2.3,合式公式是由下列规则生成的公式：,单个原子公式是合式公式。,若,A,是一个合式公式，则(,l,A,),也是一个合式公式。,若,A,、,B,是合式公式，则(,A,B,)、(,A,B,)、(,A,B,),和(,A,B,),都是合式公式。,只有有限次使用、和生成的公式才是合式公式。,当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：,规定联结词的优先级由高到低的次序为：,l,、,相同的联结词按从左至右次序计算时，圆括号可省略。,最外层的圆括号可以省略。,为了方便计，合式公式也简称公式。,.公式真值表,定义1.2.4,对于公式中命题变元的每一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式的真值表。,定义1.2.5,如果,B,是公式,A,中的一部分，且,B,为公式，则称,B,是公式,A,的子公式。,用归纳法不难证明，对于含有,n,个命题变元的公式，有2,n,个真值指派，即在该公式的真值表中有2,n,行。,为方便构造真值表，,特约定如下：, 命题变元按字典序排列。, 对每个指派，以二进制数从小到大或从大到小顺序列出。, 若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。,4.命题的符号化,把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为,命题的符号化。符号化应该注意下列事项:, 确定给定句子是否为命题。, 句子中连词是否为命题联结词。, 要正确地表示原子命题和适当选择命题联结词。,命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。,1.3 公式分类与等价公式,. 公式分类,定义1.3.1,设,A,为任意公式，则, 对应每一个指派，公式,A,均相应确定真值为真，称,A,为重言式，或永真式。, 对应每一个指派，公式,A,均相应确定真值为假，称,A,为矛盾式，或永假式。, 至少存在一个指派，公式,A,相应确定真值为真，称,A,为可满足式。,由定义可知，重言式必是可满足式，反之一般不真。,重点将研究重言式，它最有用，因为它有以下特点：,重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。,两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。,由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。,判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。,在,Ls,中，由于任何一个命题公式的指派数目总是有限的，所以,Ls,的判定问题是可解的。其判定方法有真值表法和公式推演法。,.等价公式,定义1.3.2,设,A,和,B,是两个命题公式，如果,A、B,在其任意指派下，其真值都是相同的，则称,A,和,B,是等价的，或逻辑相等，记作,A,B，,读作,A,等价,B,，,称,A,B,为等价式。,显然，若公式,A,和,B,的真值表是相同的，则,A,和,B,等价。因此，验证两公式是否等价，只需做出它们的真值表即可。,在这里，请读者注意,和,的区别与联系。,区别：,是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；,不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。,联系：可用下面定理表明之。,定理1.3.1,A,B,当且仅当,A,B,是永真式。 有时也称,A,B,是永真双条件式。,等价式有下列性质：, 自反性，即对任意公式,A,，,有,A,A,。,对称性，即对任意公式,A,和,B,，,若,A,B,，,则,B,A,。,传递性，即对任意公式,A,、,B,和,C,，,若,A,B,、,B,C,，,则,A,C,。,.基本等价式,命题定律,在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一，读者应该注意到这一点。现将这些命题定律列出如下：,(1)双否定：,A,A,。,(2),交换律：,A,B,B,A,，,A,B,B,A,，,A,B,B,A,。,(3) 结合律：(,A,B,),C,A,(,B,C,)，(,A,B,),C,A,(,B,C,)，(,A,B,),C,A,(,B,C,)。,(4),分配律：,A,(,B,C,),(,A,B,)(,A,C,)，,A,(,B,C,),(,A,B,)(,A,C,)。,(5),德,摩根律：,(,A,B,),A,B,，,(,A,B,),A,B,。,(6),等幂律：,A,A,A,，,A,A,A,。,(7) 同一律：,A,T,A,，,A,F,A,。,(8),零 律：,A,F,F,，,A,T,T,。,(9),吸收律：,A,(,A,B,),A,，,A,(,A,B,),A,。,(10),互补律：,A,A,F,，(,矛盾律),A,A,T,。(,排中律),(11) 条件式转化律：,A,B,A,B,，,A,B,B,A,。,(12) 双条件式转化律：,A,B,(,A,B,)(,B,A,),(,A,B,)(,A,B,),A,B,(,A,B,),(13),输出律：(,A,B,),C,A,(,B,C,)。,(14),归谬律：(,A,B,)(,A,B,),A,。,上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。,.代入规则和替换规则,在定义合成公式时，已看到了逻辑联结词能够从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介绍,“,代入,”,和,“,替换,”,，它们也有从已知公式得到新的公式的作用，因此有人也将它们看成运算，这不无道理，而且在今后讨论中，它的作用也是不容忽视的。,(1),代入规则,定理,1.3.2,在一个永真式,A,中，任何一个原子命题变元,R,出现的每一处， 用另一个公式代入，所得公式,B,仍是永真式。本定理称为代入规则。,(2)替换规则,定理1.3.3,设,A,1,是合式公式,A,的子公式，若,A,1,B,1,，,并且将,A,中的,A,1,用,B,1,替换得到公式,B,，,则,A,B,。,称该定理为替换规则。,满足定理1.3.3条件的替换，称为等价替换。,代入和替换有两点区别：, 代入是对原子命题变元而言的，而替换可对命题公式实行。, 代入必须是处处代入，替换则可部分替换，亦可全部替换。,1.4 对偶式与蕴涵式,.对偶式,在上节介绍的命题定律中，多数是成对出现的，这些成对出现的定律就是对偶性质的反映，即对偶式。利用对偶式的命题定律，可以扩大等价式的个数，也可减少证明的次数。,定义1.4.1,在给定的仅使用联结词,、和的命题公式,A,中，若把和互换，,F,和,T,互换而得到一个命题公式,A,*,，,则称,A,*,为,A,的对偶式。,显然，,A,也是,A,*,的对偶式。可见,A,与,A,*,互为对偶式。,定理1.4.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,),表明，公式,A,的否定等价于其命题变元否定的对偶式；表明，命题变元否定的公式等价于对偶式之否定。,定理1.4.2,设,A,和,B,为两个命题公式，若,A,B,则,A,*,B,*,。,有了等价式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明更多的等价式，使化简命题公式更为方便。,.蕴涵式,定义1.4.2,设,A,和,B,是两个命题公式，若,A,B,是永真式，则称,A,蕴涵,B,，,记作,A,B,，,称,A,B,为蕴涵式或永真条件式。,符号和,的区别与联系类似于,和,的关系。区别：是逻辑联结词，属于对象语言中的符号，是公式中的符号；而,不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。联系：,A,B,成立，其充要条件,A,B,是永真式。,蕴涵式有下列性质：, 自反性，即对任意公式,A,，,有,A,A,。,传递性，即对任意公式,A,、,B,和,C,，,若,A,B,，,B,C,，,则,A,C,。,对任意公式,A,、,B,和,C,，,若,A,B,，,A,C,，,则,A,(,B,C,)。,对任意公式,A,、,B,和,C,，,若,A,C,，,B,C,，,则,A,B,C,。,这些性质的正确性，请读者自己验证。,下面给出等价式与蕴涵式之间的关系。,定理1.4.3,设,A,和,B,是两命题公式，,A,B,的充要条件是,A,B,且,B,A,。,.蕴涵式证明方法,除真值表外，还有两种方法：, 前件真导后件真方法,设公式的前件为真，若能推导出后件也为真，则条件式是永真式，故蕴涵式成立。,因为欲证,A,B,，,即证,A,B,是永真式。对于,A,B,，,除在,A,取真和,B,取假时，,A,B,为假外，余下,A,B,皆为真。所以，若,A,B,的前件,A,为真，由此可推出,B,亦为真，则,A,B,是永真式，即,A,B,。, 后件假导前件假方法,设条件式后件为假，若能推导出前件也为假，则条件式是永真式，即蕴涵式成立。,因为若,A,B,的后件,B,取假，由此可推出,A,取假，即推证了：,B,A,。,又因,A,B,B,A,，,故,A,B,成立。,1.5 联结词的扩充与功能完全组,. 联结词的扩充,定义1.5.1,设,P,和,Q,是任两个原子命题，,由合取非联结词和,P,，,Q,连接成,P,Q,，,称它为,P,和,Q,的合取非式复合命题，读作“,P,合取非,Q,”。,P,Q,的真值由命题,P,和,Q,的真值确定：当且仅当,P,和,Q,均为,时，,P,Q,为,，否则,P,Q,为,。“合取非”又常称为“与非”。,由析取非联结词和,P,，,Q,连接成,P,Q,，,称它为,P,和,Q,的析取非式复合命题，读作“,P,析取非,Q,”。,P,Q,的真值由,P,和,Q,的真值确定：当且仅当,P,和,Q,均为,时，,P,Q,为,，否则,P,Q,为,。“析取非”又常称为“或非”。,由条件非联结词,和,P,，,Q,连接成,P,Q,，,称它为,P,和,Q,的条件非式复合命题，读作“,P,条件非,Q,”。,P,Q,的真值由,P,和,Q,的真值确定：当且仅当,P,为,而,Q,为,时，,P,Q,为,；否则,P,Q,为,。,由双条件非联结词,把,P,，,Q,连接成,P,Q,，,称它为,P,和,Q,的双条件非式复合命题，读作“,P,双条件非,Q,”。,P,Q,的真值由,P,和,Q,的真值确定：当且仅当,P,和,Q,的真值不同时，,P,Q,为,，否则,P,Q,为,。“双条件非”又常称为“异或”，也常用符号,表示之。,上面4个联结词构成的复合命题，其真值表如下：,由表可知，,P,Q,(,P,Q,),P,Q,(,P,Q,),P,Q,(,P,Q,),P,Q,(,P,Q,),.与非、或非和异或的性质,与非、或非以及异或在计算机科学中是经常使用的3个联结词，因此，掌握它们的性质是十分必要的。令,P,、,Q,和,R,是原子命题变元。, 与非的性质,(,a,),P,Q,Q,P,(,b,),P,P,P,(,c,) (,P,Q,)(,P,Q,),P,Q,(,d,) (,P,P,)(,Q,Q,),P,Q, 或非的性质,(,a,),P,Q,Q,P,(,b,),P,P,P,(,c,)(,P,Q,)(,P,Q,),P,Q,(,d,) (,P,P,)(,Q,Q,),P,Q,从上述的性质可知，联结词,、,和,可分别用联结词,或者,取代，读者可以自行验证，,和,都不满足结合律。, 异或的性质,(,a,),P,Q,Q,P,(,b,),P,(,Q,R,),(,P,Q,),R,(,c,),P,(,Q,R,),(,P,Q,),(,P,R,),(,d,),P,P,F,，,F,P,P,，,T,P,P,(,e,),若,P,Q,R,，,则,Q,R,P,，,P,P,Q,，,且,P,Q,R,F,。,以上所有性质，用真值表或命题定律都是不难证明的。,至此，已有了9个联结词，是否还需要扩充呢？事实上，两上命题变无,P,和,Q,，,与9个联结词一共可构成 类命题公式，如下表示之：,从列表可知，除命题常元,F,，,T,及命题变元本身外，命题联结词一共有9个就够了。为了方便，可规定其优先级，由高到低次序为,，,，,，,，,等。,.联结词功能完全组,已知有9个联结词就够用了，能不能少呢？若能少，表明有些联结词的逻辑功能可由其他联结词替代。事实上，也确实如此，因为有下列等价式：,P,Q,(,P,Q,),P,Q,(,P,Q,),P,Q,(,P,Q,),P,Q,(,P,Q,),可见，扩充的4个联结词,，,，,和,能由原有5个联结词分别替代之。,又由命题定律：,P,Q,(,P,Q,),(,Q,P,),P,Q,P,Q,P,Q,(,P,Q,),P,Q,(,P,Q,),可知，原有5个联结词,，,，,，,和,又能由联结词组,，,或,，,取代。那么，究竟最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公式。或者说，用最少的几个联结词就能替代所有联结词的功能。这便是所要定义的联结词功能完全组。,定义1.5.2,称,G,为联结词功能完全组，如果,G,满足下列两条件：由,G,中联结词构成的公式能等价表示任意命题公式；,G,中的任一联结词不能用其余下联结词等价表示。,可以证明，,，,，,，,，,，,，,，,都是联结词功能完全组；而,，,，,，,，,，,，,都不是联结词功能完全组，但为了表示方便，仍经常使用联结词组,，,，,。,1.6 公式标准型范式,.简单合取式与简单析取式,定义1.6.1,在一公式中，仅由命题变元及其否定构成的合取式， 称该公式为简单合取式，其中每个命题变元或其否定，称为合取项。,定义1.6.2,在一公式中，仅由命题变元及其否定构成的析取式， 称该公式为简单析取式，其中每个命题变元或其否定，称为析取项。,例如，公式,P,，,Q,，,P,Q,和,P,Q,P,等都是简单合取式，而,P,，,Q,和,P,为相应的简单合取式的合取项；公式,P,，,Q,，,P,Q,，,P,Q,P,等都是简单析取式，而,P,，,Q,和,P,为相应简单析取式的析取项。,注意，一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如例中,P,，,Q,等。,定理1.6.1,简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。,定理1.6.2,简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。,.析取范式与合取范式,定义1.6.3,一个命题公式,A,称为析取范式，当且仅当,A,可表为简单合取式的析取，即,A,A,i,；,其中,A,i,为简单合取式，,i,=1，2，,n,。,定义1.6.4,一个命题公式,A,称为合取范式，当且仅当,A,可表为简单析取式的合取，即,A,A,i,；,其中,A,i,为简单析取式，1,i,n,。,定理1.6.3,对于任何一命题公式，都存在与其等价的析取范式和合取范式。,求范式算法： 使用命题定律，消去公式中除,、,和,以外公式中出现的所有联结词；, 使用,(,P,),P,和德摩根律，将公式中出现的联结词,都移到命题变元之前；, 利用结合律、分配律等将公式化成析取范式或合取范式。,.范式的应用,利用析取范式和合取范式可对公式进行判定。,定理1.6.4,公式,A,为永假式的充要条件是,A,的析取范式中每个简单合取式至少包含一个命题变元及其否定。,定理1.6.5,公式,A,为永真式的充要条件是,A,的合取范式中每个简单析取式至少包含一个命题变元及其否定。,.范式不唯一性,1.7 公式的主范式,范式基本解决了公式的判定问题。但由于范式不唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决了这个问题。下面将分别讨论主范式中的主析取范式和主合取范式。,.主析取范式,(1) 小项的概念和性质,定义1.7.1,在含有,n,个命题变元的简单合取式中， 若每个命题变元与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为小项，或布尔积。,例如，两个命题变元,P,和,Q,，,其构成的小项有,P,Q,，,P,Q,，,P,Q,和,P,Q,；,而三个命题变元,P,、,Q,和,R,，,其构成的小项有,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,。,可以证明，,n,个命题变元共形成2,n,个小项。,如果将命题变元按字典序排列，并且把命题变元与1对应，命题变元的否定与0对应，则可对2,n,个小项依二进制数编码，记为,m,i,，,其下标,i,是由二进制数转化的十进制数。用这种编码所求得2,n,个小项的真值表，可明显地反映出小项的性质。,表1.7.1和表1.7.2分别给出了2个命题变元,P,和,Q,、3,个命题变元,P,、,Q,和,R,的小项真值表。,从表1.7.1，表1.7.2可看出，小项有如下性质：,(,a,),没有两个小项是等价的，即是说各小项的真值表都是不同的；,(,b,),任意两个不同的小项的合取式是永假的：,m,i,m,j,，,i,j,。,(,c,),所有小项之析取为永真：,m,i,。,(,d,),每个小项只有一个解释为真，且其真值1位于主对角线上。,(2) 主析取范式定义与存在定理,定义1.7.2,在给定公式的析取范式中，若其简单合取式都是小项， 则称该范式为主析取范式。,定理1.7.1,任意含,n,个命题变元的非永假命题公式,A,都存在与其等价的主析取范式。,(3) 主析取范式的求法,主析取范式求法有两种：真值表法和公式化归法。定理1.7.1的证明已给出了用真值表求主析取范式的方法，而公式化归法给出如下：,(,a,),把给定公式化成析取范式；,(,b,),删除析取范式中所有为永假的简单合取式；,(,c,),用等幂律化简简单合取式中同一命题变元的重复出现为一次出现，如,P,P,P,。,(,d,),用同一律补进简单合取式中未出现的所有命题变元，如,Q,，,则,P,P,Q,Q,)，,并用分配律展开之，将相同的简单合取式的多次出现化为一次出现， 这样得到了给定公式的主析取范式。,(4) 主析取范式的惟一性,定理1.7.2,任意含,n,个命题变元的非永假命题公式，其主析取范式是惟一的。,.主合取范式,(1) 大项的概念和性质,定义1.7.3,在,n,个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该简单析取式为大项，或布尔和。,例如，由两个命题变元,P,和,Q,，,构成大项有,P,Q,，,P,Q,，,P,Q,，,P,Q,；,三个命题变元,P,，,Q,和,R,，,构成,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,，,P,Q,R,。,能够证明，,n,个命题变元共有2,n,个大项。,如果将,n,个命题变元排序，并且把命题变元与对应，命题变元的否定与对应，则可对2,n,个大项按二进制数编码，记为,M,i,，,其下标,i,是由二进制数化成的十进制数。用这种编码所求的2,n,个大项的真值表，能直接反映出大项的性质。,表1.7.3给出了2个命题变元,P,和,构成所有大项的真值表。,类似可给出个命题变元,、,和,的所有大项的真值表，留给读者完成。,从表1.7.3可看出大项的性质：,(,a,),没有两个大项是等价的。,(,b,),任何两个不同大项之析取是永真的，即,M,i,M,j,，,i,j,。,(,c,),所有大项之合取为永假，即,M,i,。,(,d,),每个大项只有一个解释为假，且其真值0位于主对角线上。,(2) 主合取范式的定义与其存在定理,定义1.7.4,在给定公式的合取范式中，若其所有简单析取式都是大项， 称该范式为主合取范式。,定理1.7.3,任意含有,n,个命题变元的非永真命题公式,A,，,都存在与其等价的主合取范式。,定理1.7.4,任意含,n,个命题变元的非永真命题公式,A,，,其主合取范式是唯一的。,上述两定理的证明，类似于定理1.7.1和定理1.7.2。,主合取范式的求法也有两种，类似于主析取范式的求法。,.主析取范式与主合取范式之间的关系,由于主范式是由小项或大项构成，从小项和大项的定义，可知两者有下列关系：,m,i,M,i,M,i,m,i,因此，主析取范式和主合取范式有着“互补”关系，即是由给定公式的主析取范式可以求出其主命取范式。,设命题公式,A,中含有,n,个命题变元，且,A,的主析取范式中含有,k,个小项 ， ， ，则,A,的主析取范式中必含有2,n,-,k,个小项，不妨含为 ， ， ，即,A, 。,于是,A,A,( ), ,由此可知，从,A,的主析取范式求其主合取范式的步骤为：,(,a,),求出,A,的主析取范式中设有包含的小项。,(,b,),求出与(,a,),中小项的下标相同的大项。,(,c,),做(,b,),中大项之合取，即为,A,的主合取范式。,例如，(,P,Q,),Q,m,1,m,3,，,则(,P,Q,),Q,M,0,M,2,。,.主范式的应用,利用主范式可以求解判问题或者证明等价式成立。,（1）判定问题,根据主范式的定义和定理，也可以判定含,n,个命题变元的公式，其关键是先求出给定公式的主范式,；其次按下列条件判定之：,(,a,),若,A,，或,A,可化为与其等价的、含2,n,个小项的主析取范式，则,A,为永真式。,(,b,),若,A,，或,A,可化为与其等价的、含2,n,个大项的主合取范式，则,A,为永假式。,(,c,),若,A,不与,或者,等价，且又不含2,n,个小项或者大项，则,A,为可满足的。,（2）证明等价式成立,由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。,1.8 命题逻辑的推理理论,在逻辑学中，把从前题（又叫公理或假设）出发，依据公认的推理规则，推导出一个结论，这一过程称为有效推理或形式证明。所得结论叫做有效结论，这里最关心的不是结论的真实性而是推理的有效性。前提的实际真值不作为确定推理有效性的依据。但是，如果前提全是真，则有效结论也应该真而绝非假。,在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，与这些规则有关的理论称为推理理论。,提请注意，必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。,可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。,.推理的基本概念和推理形式,推理也称论证，它是指由已知命题得到新的命题的思维过程，其中已知命题称为推理的前提或假设，推得的新命题称为推理的结论。,在数理逻辑中，前提,H,是一个或者,n,个命题公式,H,1,H,2,H,n,；,结论是一个命题公式,C,。,由前提到结论的推理形式可表为,H,1,H,2,H,n,C,，,其中符号,表示推出。可见，推理形式是命题公式的一个有限序列，它的最后一个公式是结论，余下的为前提或假设。,定义1.8.1,如果存在,H,1,，,H,2,，,H,n,，,C,的一个指派，使得每个,H,i,(1,i,n,),为真而,C,为假推理形式,H,1,，,H,2,，,H,n,C,是无效的；否则，推理是有效的，此时称,C,是,H,1,，,H,2,，,Hn,的有效结论，或称,C,是从前提,H,1,，,H,2,，,H,n,逻辑推出的结论。,定理1.8.1,推理形式,H,1,，,H,2,，,Hn,C,是有效的，当且仅当命题公式(,H,1,H,2,H,n,),C,是永真式，亦即(,H,1,H,2,H,n,),C,。,.推理规则,在数理逻辑中，从前提推导出结论，要依据事先提供的公认的推理规则，它们是：,规则(也称前提引入规则)：在推导过程中，前提可视需要引入使用。,规则(也称结论引入规则)：在推导过程中，前面已导出的有效结论都可作为后续推导的前提引入。,此外，在从前提推出的结论为条件式时，还需要下面规则：,规则(也称条件证明引入规则)：若推出有效结论为条件式,R,C,时，只需将其前件,R,加入到前提中作为附加前提且再去推出后件,C,即可。,规则的正确性可由下面定理得到保证：,定理1.8.2,若,H,1,，,H,2,，,H,n,，,R,C,，,则,H,1,，,H,2,，,H,n,R,C,。,.推理定律,在推理过程中，除使用推理规则后，还需要使用许多条推理定律，这些定律可由以前讲过的命题定律、蕴涵式及运用定理1.8.1而得到。下面只给出了由蕴涵式得出的推理定律，它们是：,(1),P,，,Q,P,(2),P,，,Q,Q,(3),P,P,Q,(4),P,P,Q,(5),Q,P,Q,(6),(,P,Q,),P,(7),(,P,Q,),Q,(8),P,，(,P,Q,),Q,(9),Q,，(,P,Q,),P,(10),P,，(,P,Q,),Q,(11) (,P,Q,)，(,Q,R,),P,R,(12) (,P,Q,)，(,Q,R,),P,R,(13) (,P,Q,)，(,R,S,)，(,P,R,),Q,S,(14) (,P,Q,)，(,R,S,)(,P,R,),Q,S,特别当,Q,=,S,时，有,(,P,Q,)，(,R,Q,)，(,P,R,),Q,(,P,Q,)，(,R,S,)，(,P,R,),Q,(15),P,Q,(,P,R,)(,Q,R,),P,Q,(,P,R,)(,Q,R,),此外，每个命题定律也可应得出两个推理定律，这些请读者补全。,由于推理定律是确定有效结论的不可缺少的重要根据，因此要牢记并熟练运用它们。,.判断有效结论的常用方法,判断有效结论的常用方法有真值表法，演绎法和间接证法。下面分别讨论之。,(1)真值表法,根据给定前提,H,1,，,H,2,，,H,n,和结论,C,，,构造条件式(,H,1,H,2,H,n,),C,的真值表，若它为永真式，则结论,C,是有效的。,为了简便，根据条件式,D,：(,H,1,H,2,H,n,),C,的真值定义，只需列出待证命题公式,D,的前件和后件的真值表，就可判断结论,C,的有效性。方法有二：(,a,),在真值表中，先找出前提,H,1,，,H,2,，,H,n,的真值均为真的行，若相应行中结论,C,的真值也都为真，则,D,为真，即,C,为有效结论。(,b,),在真值表中，先找出结论,C,的真值为假的所有行，若这些行中，前提,H,1,，,H,2,，,H,n,的真值都至少有一个为假，则,D,为真，即,C,为有效结论。,（2）演绎法,列出待证推理形式中前提和结论的真值表，原则上可以解决推理的有效性问题。但当出现在公式中的命题变元数目很大时，真值表法又显得不切实用，而使用演绎法却能比较好地解决这个问题。,定义1.8.2,从前提,H,推出结论,C,的一个演绎是构造命题公式的一个有限序列：,A,1,，,A,2,，,A,n,其中，,A,1,是前提,H,中的某个前提,H,i,；,A,i,(,i,2),或者是,H,中某个前提,H,i,，,或者是某些,A,j,(,j,i,的有效结论，并且,A,n,就是,C,，,则称公式,C,为该演绎的有效结论，或者称从,H,演绎出,C,。,通过下面例子来说明演绎具体是如何进行。,例1.8.3,求证,D,是前提,A,，,A,B,，,B,C,和,C,D,的有效结论。,证明,1 (1),A,B,P,2 (2),B,C,P,1,2 (3),A,C,T,(1)(2),I,8,4 (4),A,P,1,2,4 (5),C,T,(3)(4),I,8,6 (6),C,D,P,1,2,4,6 (7),D,T,(5)(6),I,8, ,第1列 第2列 第3列 第4列,演绎法的具体操作可用4列若干行构成的一张表来表示。第1列是花括号序列； 第2列是圆括号序列；第3列是推导行即命题公式序列；第4列是注释行序列。 推导行表明是前提或从部分前提推出的中间逻辑结论或最终所求的有效结论。花括号内一些数字表明该推导行是由哪些前提推出的。圆括号中数字是对推导行按增序列统一编号。注释行表示所引用推理规则和该推导行是由哪些公式和运用怎样推理定律得来的。,间接证法,间接证法即是反证法，它是把结论的否定作为附加前提，与给定前提一起推证，若能引出矛盾，则说明结论是有效的。,定义1.8.3,设,H,1,，,H,2,，,H,n,为公式，如果对任意公式,R,，,有,H,1,H,2,H,n,R,R,，,则称公式,H,1,，,H,2,，,H,n,是不相容的；否则称为是相容的。,显然，由定理1.8.1，,H,1,H,2,H,n,R,R,可记为,H,1,，,H,2,，,H,n,R,R,定理1.8.3,设,H,1,，,H,2,，,H,n,，,C,为公式，且,H,1,，,H,2,，,H,n,是相容的。若,H,1,，,H,2,，,H,n,，,C,是不相容的，则公式,C,是,H,1,，,H,2,，,H,n,的有效结论。,