离散数学教程.ppt

《离散数学教程.ppt》由会员分享，可在线阅读，更多相关《离散数学教程.ppt（113页珍藏版）》请在课桌文档上搜索。

1、,高等学校21世纪教材,电子教案,离散数学,第一章命题逻辑,命题逻辑，也称命题演算，记为Ls。它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。数理逻辑是用数学方法即通过引入表意符号研究推理的学问。因此，数理逻辑又名为符号逻辑。命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。,退出,1.1 命题与联结词1.2 命题变元和合式公式1.3 公式分类与等价公式1.4 对偶式与蕴涵式1.5 联结词的扩充与功能完全组1.6 公式标准型范式1.7 公式的主范式1.8 命题逻辑的推理理论,1.1 命题与联结词,.命题的概念所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹

2、句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。,如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。命题分为两类，第一类是原子命题，原子命题用大写英文字母P，Q，R及其带下标的Pi，Qi，Ri，表示。第二类是复合命题，它由原子命题、命题联结词和圆括号组成。,.命题联结词定义1.1.1设P表示一个命题，由命题联结词l和命题P连接成lP，称lP为P的否定式复合命题，lP读“非P”。

3、称l为否定联结词。lP是真，当且仅当P为假；lP是假，当且仅当P为真。否定联结词“l”的定义可由表1.1.1表示之。,由于否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。,定义1.1.2设P和Q为两个命题，由命题联结词将P和Q连接成PQ，称PQ为命题P和Q的合取式复合命题，PQ读做“P与Q”，或“P且Q”。称为合取联结词。当且仅当P和Q的真值同为真，命题PQ的真值才为真；否则，PQ的真值为假。合取联结词的定义由表1.1.2表示之。,定义1.1.3设P和Q为两个命题，由命题联结词把P和Q连接成PQ，称PQ为命题P和Q的析取式复合命题，PQ读做“P或Q”。称为析取联结词。当且仅当P和Q

4、的真值同为假，PQ的真值为假；否则，PQ的真值为真。析取联结词的定义由表1.1.3表示之。,由定义可知，析取联结词表示“可兼和”，“不可兼和”另有别的联结词定义之。与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系，有关例子就不再给出了。,定义1.1.4设P和Q为两个命题，由命题联结词把P和Q连接成PQ，称PQ为命题P和Q的条件式复合命题，简称条件命题。PQ读做“P条件Q”或者“若P则Q”。称为条件联结词。当P的真值为真而Q的真值为假时，命题PQ的真值为假；否则，PQ的真值为真。条件联结词的定义由表1.1.4表示之。,在条件命题PQ中，命题P称为PQ的前件或前提，命题Q称为PQ

5、的后件或结论。条件命题PQ有多种方式陈述：“如果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的双条件式复合命题，简称双条件命题，

6、P Q读做“P当且仅当Q”，或“P等价Q”。称为双条件联结词。当P和Q的真值相同时，P Q的真值为真；否则，P Q的真值为假。双条件联结词的定义由表1.1.5表示之。,在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的，请读者认真去领会。,1.2 命题变元和合式公式,.命题变元在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元

7、指派真值。,命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下：定义1.2.1以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。,2.合式公式通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的公式称为合式公式。定义1.2.2单个命题变元和命题常元称为原子命题公式，简称原子公式。,定义1.2.3合式公式是由下列规则生成的公式：单个原子公式是合式公式。若

8、A是一个合式公式，则(lA)也是一个合式公式。若A、B是合式公式，则(AB)、(AB)、(AB)和(A B)都是合式公式。只有有限次使用、和生成的公式才是合式公式。,当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：规定联结词的优先级由高到低的次序为：l、相同的联结词按从左至右次序计算时，圆括号可省略。最外层的圆括号可以省略。为了方便计，合式公式也简称公式。,.公式真值表定义1.2.4对于公式中命题变元的每一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式的真值表。定义1.2.5如果B是公式A中的一部分，且B为公式，则称B是公式A的子公式。,用归

9、纳法不难证明，对于含有n个命题变元的公式，有2n个真值指派，即在该公式的真值表中有2n行。为方便构造真值表，特约定如下：命题变元按字典序排列。对每个指派，以二进制数从小到大或从大到小顺序列出。若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。,4.命题的符号化把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为命题的符号化。符号化应该注意下列事项:确定给定句子是否为命题。句子中连词是否为命题联结词。要正确地表示原子命题和适当选择命题联结词。,命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题

10、，解决不好，等于说推理的首要前提没有了。,1.3 公式分类与等价公式,.公式分类定义1.3.1设 A 为任意公式，则 对应每一个指派，公式 A 均相应确定真值为真，称 A 为重言式，或永真式。对应每一个指派，公式 A 均相应确定真值为假，称 A 为矛盾式，或永假式。至少存在一个指派，公式 A 相应确定真值为真，称 A 为可满足式。,由定义可知，重言式必是可满足式，反之一般不真。重点将研究重言式，它最有用，因为它有以下特点：重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。由重言

11、式使用公认的规则可以产生许多有用等价式和蕴涵式。,判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。在Ls中，由于任何一个命题公式的指派数目总是有限的，所以Ls的判定问题是可解的。其判定方法有真值表法和公式推演法。,.等价公式定义1.3.2设A和B是两个命题公式，如果A、B在其任意指派下，其真值都是相同的，则称A和B是等价的，或逻辑相等，记作AB，读作A等价B，称AB为等价式。显然，若公式A和B的真值表是相同的，则A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。,在这里，请读者注意和的区别与联系。区别：是逻辑联结词，属于目标语言中的符号，它出现在命题公式

12、中；不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。联系：可用下面定理表明之。,定理1.3.1A B当且仅当AB是永真式。有时也称A B是永真双条件式。等价式有下列性质：自反性，即对任意公式A，有A A。对称性，即对任意公式A和B，若A B，则B A。传递性，即对任意公式A、B和C，若A B、B C，则A C。,.基本等价式命题定律在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一，读者应该注意到这一点。现将这些命题定律列出如下：(1)双否定：AA。(2)交

13、换律：ABBA，ABBA，ABBA。,(3)结合律：(AB)CA(BC)，(AB)CA(BC)，(AB)CA(BC)。(4)分配律：A(BC)(AB)(AC)，A(BC)(AB)(AC)。(5)德摩根律：(AB)AB，(AB)AB。(6)等幂律：AAA，AAA。,(7)同一律：ATA，AFA。(8)零 律：AFF，ATT。(9)吸收律：A(AB)A，A(AB)A。(10)互补律：AAF，(矛盾律)AAT。(排中律)(11)条件式转化律：ABAB，ABBA。,(12)双条件式转化律：AB(AB)(BA)(AB)(AB)AB(AB)(13)输出律：(AB)CA(BC)。(14)归谬律：(AB)(A

14、B)A。上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。,.代入规则和替换规则在定义合成公式时，已看到了逻辑联结词能够从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介绍“代入”和“替换”，它们也有从已知公式得到新的公式的作用，因此有人也将它们看成运算，这不无道理，而且在今后讨论中，它的作用也是不容忽视的。,(1)代入规则定理1.3.2 在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式。本定理称为代入规则。(2)替换规则定理1.3.3 设A1是合式公式A的子公式，若

15、A1B1，并且将A中的A1用B1 替换得到公式B，则AB。称该定理为替换规则。满足定理1.3.3条件的替换，称为等价替换。,代入和替换有两点区别：代入是对原子命题变元而言的，而替换可对命题公式实行。代入必须是处处代入，替换则可部分替换，亦可全部替换。,1.4 对偶式与蕴涵式,.对偶式在上节介绍的命题定律中，多数是成对出现的，这些成对出现的定律就是对偶性质的反映，即对偶式。利用对偶式的命题定律，可以扩大等价式的个数，也可减少证明的次数。,定义1.4.1 在给定的仅使用联结词、和的命题公式A中，若把和互换，F和T互换而得到一个命题公式A*，则称A*为A的对偶式。显然，A也是A*的对偶式。可见A与A

16、*互为对偶式。,定理1.4.1(对偶定理)设A和A*互为对偶式，P1，P2，Pn是出现A和A*中的原子命题变元，则 A(P1，P2，Pn)A*(P1，P2，Pn)A(P1，P2，Pn)A*(P1，P2，Pn)表明，公式A的否定等价于其命题变元否定的对偶式；表明，命题变元否定的公式等价于对偶式之否定。,定理1.4.2 设A和B为两个命题公式，若AB则A*B*。有了等价式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明更多的等价式，使化简命题公式更为方便。,.蕴涵式定义1.4.2 设A和B是两个命题公式，若AB是永真式，则称A蕴涵B，记作AB，称AB为蕴涵式或永真条件式。符号和的区别与

17、联系类似于和的关系。区别：是逻辑联结词，属于对象语言中的符号，是公式中的符号；而不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。联系：AB成立，其充要条件AB是永真式。,蕴涵式有下列性质：自反性，即对任意公式A，有AA。传递性，即对任意公式A、B和C，若AB，BC，则AC。对任意公式A、B和C，若AB，AC，则A(BC)。对任意公式A、B和C，若AC，BC，则ABC。,这些性质的正确性，请读者自己验证。下面给出等价式与蕴涵式之间的关系。定理1.4.3 设A和B是两命题公式，AB的充要条件是AB且BA。,.蕴涵式证明方法除真值表外，还有两种方法：前件真导后件真方法设公式

18、的前件为真，若能推导出后件也为真，则条件式是永真式，故蕴涵式成立。因为欲证AB，即证AB是永真式。对于AB，除在A取真和B取假时，AB为假外，余下AB皆为真。所以，若AB的前件A为真，由此可推出B亦为真，则AB是永真式，即AB。,后件假导前件假方法设条件式后件为假，若能推导出前件也为假，则条件式是永真式，即蕴涵式成立。因为若AB的后件B取假，由此可推出A取假，即推证了：BA。又因ABBA，故AB成立。,1.5 联结词的扩充与功能完全组,.联结词的扩充定义1.5.1 设P和Q是任两个原子命题，由合取非联结词和P，Q连接成PQ，称它为P和Q的合取非式复合命题，读作“P合取非Q”。PQ的真值由命题P

19、和Q的真值确定：当且仅当P和 Q均为时，PQ为，否则PQ为。“合取非”又常称为“与非”。,由析取非联结词和P，Q连接成PQ，称它为P和Q的析取非式复合命题，读作“P析取非Q”。PQ的真值由P和Q的真值确定：当且仅当P和Q均为时，PQ为，否则PQ为。“析取非”又常称为“或非”。由条件非联结词和P，Q连接成PQ，称它为P和Q的条件非式复合命题，读作“P条件非Q”。PQ的真值由P和Q的真值确定：当且仅当P为而Q为时，PQ为；否则PQ为。,由双条件非联结词把P，Q连接成PQ，称它为P和Q的双条件非式复合命题，读作“P双条件非Q”。PQ的真值由P和 Q的真值确定：当且仅当P和Q的真值不同时，PQ为，否则

20、PQ为。“双条件非”又常称为“异或”，也常用符号表示之。上面4个联结词构成的复合命题，其真值表如下：,由表可知，PQ(PQ)PQ(PQ)PQ(PQ)PQ(PQ),.与非、或非和异或的性质与非、或非以及异或在计算机科学中是经常使用的3个联结词，因此，掌握它们的性质是十分必要的。令P、Q和R是原子命题变元。与非的性质(a)PQQP(b)PPP(c)(PQ)(PQ)PQ(d)(PP)(QQ)PQ,或非的性质(a)PQQP(b)PPP(c)(PQ)(PQ)PQ(d)(PP)(QQ)PQ从上述的性质可知，联结词、和可分别用联结词或者取代，读者可以自行验证，和都不满足结合律。,异或的性质(a)PQQP(b

21、)P(QR)(PQ)R(c)P(QR)(PQ)(PR)(d)PPF，FPP，TPP(e)若PQR，则QRP，PPQ，且PQRF。,以上所有性质，用真值表或命题定律都是不难证明的。至此，已有了9个联结词，是否还需要扩充呢？事实上，两上命题变无P和Q，与9个联结词一共可构成 类命题公式，如下表示之：,从列表可知，除命题常元F，T及命题变元本身外，命题联结词一共有9个就够了。为了方便，可规定其优先级，由高到低次序为，等。,.联结词功能完全组已知有9个联结词就够用了，能不能少呢？若能少，表明有些联结词的逻辑功能可由其他联结词替代。事实上，也确实如此，因为有下列等价式：PQ(PQ)PQ(PQ)PQ(PQ

22、)PQ(PQ)可见，扩充的4个联结词，和能由原有5个联结词分别替代之。,又由命题定律：PQ(PQ)(QP)PQPQPQ(PQ)PQ(PQ)可知，原有5个联结词，和又能由联结词组，或，取代。那么，究竟最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公式。或者说，用最少的几个联结词就能替代所有联结词的功能。这便是所要定义的联结词功能完全组。,定义1.5.2 称G为联结词功能完全组，如果G满足下列两条件：由G中联结词构成的公式能等价表示任意命题公式；G 中的任一联结词不能用其余下联结词等价表示。可以证明，都是联结词功能完全组；而，都不是联结词功能完全组，但为了表示方便，仍经常使用联

23、结词组，。,1.6 公式标准型范式,.简单合取式与简单析取式定义1.6.1 在一公式中，仅由命题变元及其否定构成的合取式，称该公式为简单合取式，其中每个命题变元或其否定，称为合取项。定义1.6.2 在一公式中，仅由命题变元及其否定构成的析取式，称该公式为简单析取式，其中每个命题变元或其否定，称为析取项。,例如，公式P，Q，PQ和PQP等都是简单合取式，而P，Q和P为相应的简单合取式的合取项；公式P，Q，PQ，PQP等都是简单析取式，而P，Q和P为相应简单析取式的析取项。注意，一个命题变元或其否定既可以是简单合取式，也可是简单析取式，如例中P，Q等。,定理1.6.1 简单合取式为永假式的充要条件

24、是：它同时含有某个命题变元及其否定。定理1.6.2 简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。,.析取范式与合取范式定义1.6.3 一个命题公式A称为析取范式，当且仅当A可表为简单合取式的析取，即AAi；其中Ai为简单合取式，i=1，2，n。定义1.6.4 一个命题公式A称为合取范式，当且仅当A可表为简单析取式的合取，即AAi；其中Ai为简单析取式，1in。,定理1.6.3 对于任何一命题公式，都存在与其等价的析取范式和合取范式。求范式算法：使用命题定律，消去公式中除、和以外公式中出现的所有联结词；使用(P)P和德摩根律，将公式中出现的联结词都移到命题变元之前；利用结合律

25、、分配律等将公式化成析取范式或合取范式。,.范式的应用利用析取范式和合取范式可对公式进行判定。定理1.6.4 公式A为永假式的充要条件是A 的析取范式中每个简单合取式至少包含一个命题变元及其否定。定理1.6.5 公式A为永真式的充要条件是A 的合取范式中每个简单析取式至少包含一个命题变元及其否定。,.范式不唯一性,1.7 公式的主范式,范式基本解决了公式的判定问题。但由于范式不唯一性，对识别公式间是否等价带来一定困难，而公式的主范式解决了这个问题。下面将分别讨论主范式中的主析取范式和主合取范式。,.主析取范式(1)小项的概念和性质定义1.7.1 在含有n个命题变元的简单合取式中，若每个命题变元

26、与其否定不同时存在，而二者之一出现一次且仅出现一次，则称该简单合取式为小项，或布尔积。,例如，两个命题变元P和Q，其构成的小项有PQ，PQ，PQ和PQ；而三个命题变元P、Q和R，其构成的小项有PQR，PQR，PQR，PQR，PQR，PQR，PQR，PQR。可以证明，n个命题变元共形成2n个小项。,如果将命题变元按字典序排列，并且把命题变元与1对应，命题变元的否定与0对应，则可对2n个小项依二进制数编码，记为mi，其下标i是由二进制数转化的十进制数。用这种编码所求得2n个小项的真值表，可明显地反映出小项的性质。表1.7.1和表1.7.2分别给出了2个命题变元P和Q、3个命题变元P、Q和R的小项真

27、值表。,从表1.7.1，表1.7.2可看出，小项有如下性质：(a)没有两个小项是等价的，即是说各小项的真值表都是不同的；(b)任意两个不同的小项的合取式是永假的：mimj，ij。(c)所有小项之析取为永真：mi。(d)每个小项只有一个解释为真，且其真值1位于主对角线上。,(2)主析取范式定义与存在定理定义1.7.2 在给定公式的析取范式中，若其简单合取式都是小项，则称该范式为主析取范式。定理1.7.1 任意含n个命题变元的非永假命题公式A 都存在与其等价的主析取范式。,(3)主析取范式的求法主析取范式求法有两种：真值表法和公式化归法。定理1.7.1的证明已给出了用真值表求主析取范式的方法，而公

28、式化归法给出如下：(a)把给定公式化成析取范式；(b)删除析取范式中所有为永假的简单合取式；,(c)用等幂律化简简单合取式中同一命题变元的重复出现为一次出现，如PPP。(d)用同一律补进简单合取式中未出现的所有命题变元，如Q，则PPQQ)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取范式。,(4)主析取范式的惟一性定理1.7.2 任意含n个命题变元的非永假命题公式，其主析取范式是惟一的。,.主合取范式(1)大项的概念和性质定义1.7.3 在n个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该简单析取式为

29、大项，或布尔和。,例如，由两个命题变元P和Q，构成大项有PQ，PQ，PQ，PQ；三个命题变元P，Q和R，构成PQR，PQR，PQR，PQR，PQR，PQR，PQR，PQR。能够证明，n个命题变元共有2n个大项。,如果将n个命题变元排序，并且把命题变元与对应，命题变元的否定与对应，则可对2n个大项按二进制数编码，记为Mi，其下标i是由二进制数化成的十进制数。用这种编码所求的2n个大项的真值表，能直接反映出大项的性质。表1.7.3给出了2个命题变元P和构成所有大项的真值表。,类似可给出个命题变元、和的所有大项的真值表，留给读者完成。从表1.7.3可看出大项的性质：(a)没有两个大项是等价的。(b)

30、任何两个不同大项之析取是永真的，即MiMj，ij。(c)所有大项之合取为永假，即Mi。(d)每个大项只有一个解释为假，且其真值0位于主对角线上。,(2)主合取范式的定义与其存在定理定义1.7.4 在给定公式的合取范式中，若其所有简单析取式都是大项，称该范式为主合取范式。定理1.7.3 任意含有n个命题变元的非永真命题公式A，都存在与其等价的主合取范式。定理1.7.4 任意含n个命题变元的非永真命题公式A，其主合取范式是唯一的。上述两定理的证明，类似于定理1.7.1和定理1.7.2。,主合取范式的求法也有两种，类似于主析取范式的求法。.主析取范式与主合取范式之间的关系由于主范式是由小项或大项构成

31、，从小项和大项的定义，可知两者有下列关系：miMi Mimi因此，主析取范式和主合取范式有着“互补”关系，即是由给定公式的主析取范式可以求出其主命取范式。,设命题公式A中含有n个命题变元，且A的主析取范式中含有k个小项，则A的主析取范式中必含有2n-k个小项，不妨含为，即A。于是AA(),由此可知，从A的主析取范式求其主合取范式的步骤为：(a)求出A的主析取范式中设有包含的小项。(b)求出与(a)中小项的下标相同的大项。(c)做(b)中大项之合取，即为A的主合取范式。例如，(PQ)Qm1m3，则(PQ)QM0M2。,.主范式的应用利用主范式可以求解判问题或者证明等价式成立。（1）判定问题根据主

32、范式的定义和定理，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式；其次按下列条件判定之：(a)若A，或A可化为与其等价的、含2n个小项的主析取范式，则A为永真式。,(b)若A，或A可化为与其等价的、含2n个大项的主合取范式，则A为永假式。(c)若A不与或者等价，且又不含2n个小项或者大项，则A为可满足的。（2）证明等价式成立由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。,1.8 命题逻辑的推理理论,在逻辑学中，把从前题（又叫公理或假设）出发，依据公认的推理规则，推导出一个结论，这一过程称为有效推理或形式证明。所得结论叫做有效结论

33、，这里最关心的不是结论的真实性而是推理的有效性。前提的实际真值不作为确定推理有效性的依据。但是，如果前提全是真，则有效结论也应该真而绝非假。,在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，与这些规则有关的理论称为推理理论。提请注意，必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。,可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然

34、为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。,.推理的基本概念和推理形式推理也称论证，它是指由已知命题得到新的命题的思维过程，其中已知命题称为推理的前提或假设，推得的新命题称为推理的结论。在数理逻辑中，前提H是一个或者n个命题公式H1,H2,Hn；结论是一个命题公式C。由前提到结论的推理形式可表为H1,H2,HnC，其中符号表示推出。可见，推理形式是命题公式的一个有限序列，它的最后一个公式是结论，余下的为前提或假设。,定义1.8.1 如果存在H1，H2，Hn，C的一个指派，使得每个Hi(1in)为真而C为假推理形式H1，H2，HnC

35、是无效的；否则，推理是有效的，此时称C是H1，H2，Hn的有效结论，或称C是从前提H1，H2，Hn逻辑推出的结论。定理1.8.1 推理形式H1，H2，HnC是有效的，当且仅当命题公式(H1H2Hn)C是永真式，亦即(H1H2Hn)C。,.推理规则在数理逻辑中，从前提推导出结论，要依据事先提供的公认的推理规则，它们是：规则(也称前提引入规则)：在推导过程中，前提可视需要引入使用。规则(也称结论引入规则)：在推导过程中，前面已导出的有效结论都可作为后续推导的前提引入。,此外，在从前提推出的结论为条件式时，还需要下面规则：规则(也称条件证明引入规则)：若推出有效结论为条件式RC时，只需将其前件R加入

36、到前提中作为附加前提且再去推出后件C即可。规则的正确性可由下面定理得到保证：定理1.8.2 若H1，H2，Hn，RC，则H1，H2，HnRC。,.推理定律在推理过程中，除使用推理规则后，还需要使用许多条推理定律，这些定律可由以前讲过的命题定律、蕴涵式及运用定理1.8.1而得到。下面只给出了由蕴涵式得出的推理定律，它们是：(1)P，QP(2)P，QQ(3)PPQ(4)PPQ,(5)QPQ(6)(PQ)P(7)(PQ)Q(8)P，(PQ)Q(9)Q，(PQ)P(10)P，(PQ)Q(11)(PQ)，(QR)PR(12)(PQ)，(QR)PR(13)(PQ)，(RS)，(PR)QS,(14)(PQ)

37、，(RS)(PR)QS特别当Q=S时，有(PQ)，(RQ)，(PR)Q(PQ)，(RS)，(PR)Q(15)PQ(PR)(QR)PQ(PR)(QR)此外，每个命题定律也可应得出两个推理定律，这些请读者补全。由于推理定律是确定有效结论的不可缺少的重要根据，因此要牢记并熟练运用它们。,.判断有效结论的常用方法判断有效结论的常用方法有真值表法，演绎法和间接证法。下面分别讨论之。(1)真值表法根据给定前提H1，H2，Hn和结论C，构造条件式(H1H2Hn)C的真值表，若它为永真式，则结论C是有效的。,为了简便，根据条件式D：(H1H2Hn)C的真值定义，只需列出待证命题公式D的前件和后件的真值表，就可

38、判断结论C的有效性。方法有二：(a)在真值表中，先找出前提H1，H2，Hn的真值均为真的行，若相应行中结论C 的真值也都为真，则D为真，即C为有效结论。(b)在真值表中，先找出结论C的真值为假的所有行，若这些行中，前提H1，H2，Hn的真值都至少有一个为假，则D为真，即C为有效结论。,（2）演绎法列出待证推理形式中前提和结论的真值表，原则上可以解决推理的有效性问题。但当出现在公式中的命题变元数目很大时，真值表法又显得不切实用，而使用演绎法却能比较好地解决这个问题。,定义1.8.2 从前提H推出结论C的一个演绎是构造命题公式的一个有限序列：A1，A2，An其中，A1是前提H中的某个前提Hi；Ai

39、(i2)或者是H中某个前提Hi，或者是某些Aj(ji的有效结论，并且An就是C，则称公式C为该演绎的有效结论，或者称从H演绎出C。通过下面例子来说明演绎具体是如何进行。,例1.8.3 求证D是前提A，AB，BC和CD的有效结论。证明1(1)AB P2(2)BC P1,2(3)AC T,(1)(2)I84(4)A P1,2,4(5)C T,(3)(4)I86(6)CD P1,2,4,6(7)D T,(5)(6)I8 第1列 第2列 第3列 第4列,演绎法的具体操作可用4列若干行构成的一张表来表示。第1列是花括号序列；第2列是圆括号序列；第3列是推导行即命题公式序列；第4列是注释行序列。推导行表明

40、是前提或从部分前提推出的中间逻辑结论或最终所求的有效结论。花括号内一些数字表明该推导行是由哪些前提推出的。圆括号中数字是对推导行按增序列统一编号。注释行表示所引用推理规则和该推导行是由哪些公式和运用怎样推理定律得来的。,间接证法间接证法即是反证法，它是把结论的否定作为附加前提，与给定前提一起推证，若能引出矛盾，则说明结论是有效的。定义1.8.3 设H1，H2，Hn为公式，如果对任意公式R，有H1H2HnRR，则称公式H1，H2，Hn是不相容的；否则称为是相容的。显然，由定理1.8.1，H1H2HnRR可记为H1，H2，HnRR定理1.8.3 设H1，H2，Hn，C为公式，且H1，H2，Hn是相容的。若H1，H2，Hn，C是不相容的，则公式C是H1，H2，Hn的有效结论。,