离散数学教案

离散数学教案PAGEPAGE10《离散数学》教学教案第一部分课程总论一、课程简介课程名称：离散数学英文名称：DiscreteMathematics离散数学：离散数学是现代数学的一个重要分支，是计算机科学的核心课程。以研究离散量的结构和相互间的关系为主要目标，其研究对象是有限个或无限个元素。离散数学与计算机科学中的数据结构、操作系统、编译理论、算法分析、逻辑设计、系统结构、容错诊断、机器定理证明等课程紧密相关。是一门重要的基础课程。教学内容：数理逻辑、集合论、代数结构与布尔代数、图论和在计算机中的应用共五部分。其中第五部分不做考试要求，不占计划内学时，可在第三学期安排讲座课讲授。教学要求：通过该课程的学习，培养和锻炼抽象思维和缜密概括的能力，为专业基础课和专业课的学习打下坚实的理论基础。授课总学时：3学时/周18周=54学时二、适用对象本课程教学教案主要针对计算机科学与技术本科专业三、学习要领概念（正确）：必须掌握好离散数学中大量的概念判断（准确）：根据概念对事物的属性进行判断推理（可靠）：根据多个判断推出一个新的判断四、离散数学与计算机的关系第一部分数理逻辑计算机是数理逻辑和电子学相结合的产物第二部分集合论集合：一种重要的数据结构关系：关系数据库的理论基础函数：所有计算机语言中不可缺少的一部分第三部分代数系统计算机编码和纠错码理论数字逻辑设计基础计算机使用的各种运算第四部分图论数据结构、操作系统、编译原理、计算机网络原理的基础五、教材及主要参考书教材：离散数学（第四版）耿素云曲婉玲张立昂参考书：[1] 王元元、张桂芸，离散数学导论，科学出版社，2002[2] 左孝凌、李为鑑、刘永才，离散数学，上海科学技术出版社，1982年9月第1版。[3] 王元元、张桂芸，计算机科学中的离散结构，机械工业出版社，2004[4]BernardKolman,RobertC.Busby,SharonRoss,DiscreteMathematicalStructures(FourthEdition),高等教育出版社，2001[5] 孙吉贵杨凤杰欧阳丹彤李占山，离散数学，高等教育出版社，2002[6] 马振华，离散数学导引，清华大学出版社，1993[7] 王树禾，离散数学引论，中国科技大学出版社，2001[8]AndrewSimpon著冯速译离散数学导学机械工业出版社2005第二部分课程内容与要求《离散数学》为计算机科学与技术专业的一门重要基础理论课。它以研究离散量的结构和相互关系为主要目标。离散数学的内容十分丰富和广泛，本课程选择与计算机科学中相关的最基本最重要的数学课题进行系统的论述，为研究计算机科学提供理论基础和工具，为学习有关专业课，如数据结构、操作系统、编译原理、人工智能等，作必要的数学准备。同时，通过离散数学的学习，培养学生抽象思维和逻辑推理的能力。课程内容对每一个从事计算机技术的人都要求掌握和了解。因为在形式证明、验证、密码学的研究与学习中要有理解形式证明的能力；图论的概念被用于计算机网络、操作系统和程序设计语言的编译系统等领域；集合论的概念、关系代数等在软件工程和数据库中也会用到。总之，为了适应计算技术的要求及将来的发展，学生需要对离散结构有比较深入的理解。000本课程教学内容注重培养学生抽象思维能力和逻辑推理的能力。在教学中把教改、教研最新的研究成果及本学科最新发展成果引入教学，不断地修改和调整教学内容，取得了良好的效果。第一篇数理逻辑逻辑学（logic）是一门研究思维形式及思维规律的科学。数理逻辑（mathematicallogic)是用数学的方法来研究人类推理过程的一门数学学科。其显著特征是符号化和形式化，即把逻辑所涉及的“概念、判断、推理”用符号来表示，用公理体系来刻划,并基于符号串形式的演算来描述推理过程的一般规律。数理逻辑又称符号逻辑、现代逻辑。命题逻辑一、学习目的与要求本章目的是介绍命题逻辑的基本概念。掌握利用命题逻辑表示自然语言，描述概念、判断和推理。建立初步的语言形式化方法。二、知识点1．命题的概念、表示方法；联结词的逻辑意义。2．命题公式的递归定义，自然语言翻译成命题公式3．真值表的构造、命题公式等价的概念。4．重言式与蕴涵式的定义、逻辑意义，逻辑等价与逻辑蕴涵的意义和证明方法。常用的逻辑等价公式和逻辑蕴涵公式。5．命题公式的对偶式、合取范式、析取范式、主合取范式、主析取范式。逻辑小项、逻辑大项。任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。6．命题逻辑的推理理论，主要的推理方法：真值表法、直接证明法、间接证明法。常用推理规则：P规则、T规则、CP规则。7．命题逻辑的应用示例。三、要求1．识记命题表示方法、真值判断、命题公式的递归定义。2．领会联结词真值确定、翻译、命题公式的等价性和蕴涵性证明、任给公式化为析取范式、任给公式化为主析取范式、任给公式化为合取范式、任给公式化为主合取范式。3．简单应用命题逻辑推理规则，命题逻辑设计简单的开关电路。四、主要内容第1章 命题逻辑命题逻辑，也称命题演算，记为Ls。它与谓词逻辑构成数理逻辑的基础，而命题逻辑又是谓词逻辑的基础。数理逻辑是用数学方法即通过引入表意符号研究推理的学问。因此，数理逻辑又名为符号逻辑。命题逻辑是研究由命题为基本单位构成的前提和结论之间的可推导关系。1.1 命题与联结词１.命题的概念所谓命题，是指具有非真必假的陈述句。而疑问句、祈使句和感叹句等因都不能判断其真假，故都不是命题。命题仅有两种可能的真值—真和假，且二者只能居其一。真用1或T表示，假用0或F表示。由于命题只有两种真值，所以称这种逻辑为二值逻辑。命题的真值是具有客观性质的，而不是由人的主观决定的。如果一陈述句再也不能分解成更为简单的语句，由它构成的命题称为原子命题。原子命题是命题逻辑的基本单位。命题分为两类：第一类是原子命题，原子命题用大写英文字母P，Q，R…及其带下标的Pi，Qi，Ri，…表示。第二类是复合命题，它由原子命题、命题联结词和圆括号组成。２.命题联结词定义1.1.1 设P表示一个命题，由命题联结词┐和命题P连接成┐P，称┐P为P的否定式复合命题，┐P读“非P”。称┐为否定联结词。┐P是真，当且仅当P为假；┐P是假，当且仅当P为真。否定联结词“┐”的定义可由表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连接成PQ，称PQ为命题P和Q的双条件式复合命题，简称双条件命题，PQ读做“P当且仅当Q”，或“P等价Q”。称为双条件联结词。当P和Q的真值相同时，PQ的真值为真；否则，PQ的真值为假。双条件联结词的定义由表1.1.5表示之。在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的，请读者认真去领会。1.2命题变元和合式公式１.命题变元在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元指派真值。命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下：定义1.2.1 以真或1、假或0为其变域的变元，称为命题变元；真或1、假或0称为命题常元。2. 合式公式通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的公式称为合式公式。定义1.2.2 单个命题变元和命题常元称为原子命题公式，简称原子公式。定义1.2.3 合式公式是由下列规则生成的公式：①单个原子公式是合式公式。②若A是一个合式公式，则(lA)也是一个合式公式。③若A、B是合式公式，则(A∧B)、(A∨B)、(A→B)和(AB)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：①规定联结词的优先级由高到低的次序为：┐、∧、∨、→、②相同的联结词按从左至右次序计算时，圆括号可省略。③最外层的圆括号可以省略。为了方便计，合式公式也简称公式。３. 公式真值表定义1.2.4 对于公式中命题变元的每一种可能的真值指派，以及由它们确定出的公式真值所列成的表，称为该公式的真值表。定义1.2.5 如果B是公式A中的一部分，且B为公式，则称B是公式A的子公式。用归纳法不难证明，对于含有n个命题变元的公式，有2n个真值指派，即在该公式的真值表中有2n行。为方便构造真值表，特约定如下：①命题变元按字典序排列。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。4. 命题的符号化把一个用文字叙述的命题相应地写成由命题标识符、联结词和圆括号表示的合式公式，称为命题的符号化。符号化应该注意下列事项:①确定给定句子是否为命题。②句子中连词是否为命题联结词。③要正确地表示原子命题和适当选择命题联结词。命题符号化是很重要的，一定要掌握好，在命题推理中常常最先遇到的就是符号化一个问题，解决不好，等于说推理的首要前提没有了。1.3公式分类与等价公式１.公式分类定义1.3.1 设A为任意公式，则①对应每一个指派，公式A均相应确定真值为真，称A为重言式，或永真式。②对应每一个指派，公式A均相应确定真值为假，称A为矛盾式，或永假式。③至少存在一个指派，公式A相应确定真值为真，称A为可满足式。由定义可知，重言式必是可满足式，反之一般不真。重点将研究重言式，它最有用，因为它有以下特点：①重言式的否定是矛盾式，矛盾式的否定是重言式，这样只研究其一就可以了。②两重言式的合取式、析取式、条件式和双条件式等都仍是重言式。于是，由简单的重言式可构造出复杂的重言式。③由重言式使用公认的规则可以产生许多有用等价式和蕴涵式。判定给定公式是否为永真式、永假式或可满足式的问题，称为给定公式的判定问题。在Ls中，由于任何一个命题公式的指派数目总是有限的，所以Ls的判定问题是可解的。其判定方法有真值表法和公式推演法。２. 等价公式定义1.3.2 设A和B是两个命题公式，如果A、B在其任意指派下，其真值都是相同的，则称A和B是等价的，或逻辑相等，记作AB，读作A等价B，称AB为等价式。显然，若公式A和B的真值表是相同的，则A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。在这里，请读者注意和的区别与联系。区别：是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。联系：可用下面定理表明之。定理1.3.1 AB当且仅当AB是永真式。有时也称AB是永真双条件式。等价式有下列性质：①自反性，即对任意公式A，有AA。②对称性，即对任意公式A和B，若AB，则BA。③传递性，即对任意公式A、B和C，若AB、BC，则AC。３.基本等价式——命题定律在判定公式间是否等价，有一些简单而又经常使用的等价式，称为基本等价式或称命题定律。牢固地记住它并能熟练运用，是学好数理逻辑的关键之一，读者应该注意到这一点。现将这些命题定律列出如下：(1)双否定：AA。(2)交换律：A∧BB∧A，A∨BB∨A，ABBA。(3)结合律：(A∧B)∧CA∧(B∧C)，(A∨B)∨CA∨(B∨C)，(AB)CA(BC)。(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∧AA，A∨AA。(7)同一律：A∧TA，A∨FA。(8)零律：A∧FF，A∨TT。(9)吸收律：A∧(A∨B)A，A∨(A∧B)A。(10)互补律：A∧AF，(矛盾律)，A∨AT。(排中律)(11)条件式转化律：A→BA∨B，A→BB→A。(12)双条件式转化律：AB(A→B)∧(B→A)(A∧B)∨(A∧B)AB(AB)(13)输出律：(A∧B)→CA→(B→C)。(14)归谬律：(A→B)∧(A→B)A。上面这些定律，即是通常所说的布尔代数或逻辑代数的重要组成部分，它们的正确性利用真值表是不难给出证明的。４.代入规则和替换规则在定义合成公式时，已看到了逻辑联结词能够从已知公式形成新的公式，从这个意义上可把逻辑联结词看成运算。除逻辑联结词外，还要介绍“代入”和“替换”，它们也有从已知公式得到新的公式的作用，因此有人也将它们看成运算，这不无道理，而且在今后讨论中，它的作用也是不容忽视的。(1)代入规则定理1.3.2在一个永真式A中，任何一个原子命题变元R出现的每一处，用另一个公式代入，所得公式B仍是永真式。本定理称为代入规则。(2)替换规则定理1.3.3设A1是合式公式A的子公式，若A1B1，并且将A中的A1用B1替换得到公式B，则AB。称该定理为替换规则。满足定理1.3.3条件的替换，称为等价替换。代入和替换有两点区别：①代入是对原子命题变元而言的，而替换可对命题公式实行。②代入必须是处处代入，替换则可部分替换，亦可全部替换。1.4对偶式与蕴涵式１. 对偶式在上节介绍的命题定律中，多数是成对出现的，这些成对出现的定律就是对偶性质的反映，即对偶式。利用对偶式的命题定律，可以扩大等价式的个数，也可减少证明的次数。定义1.4.1在给定的仅使用联结词、∧和∨的命题公式A中，若把∧和∨互换，F和T互换而得到一个命题公式A*，则称A*为A的对偶式。显然，A也是A*的对偶式。可见A与A*互为对偶式。定理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是两个命题公式，若A→B是永真式，则称A蕴涵B，记作AB，称AB为蕴涵式或永真条件式。符号→和的区别与联系类似于和的关系。区别：→是逻辑联结词，属于对象语言中的符号，是公式中的符号；而不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。联系：AB成立，其充要条件A→B是永真式。蕴涵式有下列性质：①自反性，即对任意公式A，有AA。②传递性，即对任意公式A、B和C，若AB，BC，则AC。③对任意公式A、B和C，若AB，AC，则A(B∧C)。④对任意公式A、B和C，若AC，BC，则A∨BC。下面给出等价式与蕴涵式之间的关系。定理1.4.3设A和B是两命题公式，AB的充要条件是AB且BA。３.蕴涵式证明方法除真值表外，还有两种方法：①前件真导后件真方法设公式的前件为真，若能推导出后件也为真，则条件式是永真式，故蕴涵式成立。因为欲证AB，即证AB是永真式。对于AB，除在A取真和B取假时，AB为假外，余下AB皆为真。所以，若AB的前件A为真，由此可推出B亦为真，则AB是永真式，即AB。②后件假导前件假方法设条件式后件为假，若能推导出前件也为假，则条件式是永真式，即蕴涵式成立。因为若A→B的后件B取假，由此可推出A取假，即推证了：BA。又因A→BB→A，故AB成立。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连接成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为Ｆ。“双条件非”又常称为“异或”，也常用符号表示之。上面4个联结词构成的复合命题，其真值表如下：由表可知，①PQ(PQ) ②PQ(PQ) ③PQ(PQ) ④PQ(PQ)２.与非、或非和异或的性质与非、或非以及异或在计算机科学中是经常使用的3个联结词，因此，掌握它们的性质是十分必要的。令P、Q和R是原子命题变元。①与非的性质(a)P↑QQ↑P(b)P↑PP(c)(P↑Q)↑(P↑Q)P∧Q(d)(P↑P)↑(Q↑Q)P∨Q②或非的性质(a)P↓QQ↓P(b)P↓PP(c)(P↓Q)↓(P↓Q)P∨Q(d)(P↓P)↓(Q↓Q)P∧Q从上述的性质可知，联结词、和可分别用联结词或者取代，读者可以自行验证，和都不满足结合律。③异或的性质(a)PQQP(b)P(QR)(PQ)R(c)P∧(QR)(P∧Q)(P∧R)(d)PPF，FPP，TPP(e)若PQR，则QRP，PPQ，且PQRF。以上所有性质，用真值表或命题定律都是不难证明的。至此，已有了9个联结词，是否还需要扩充呢？事实上，两上命题变无P和Q，与9个联结词一共可构成 类命题公式，如下表示之：从列表可知，除命题常元F，T及命题变元本身外，命题联结词一共有9个就够了。为了方便，可规定其优先级，由高到低次序为，，，，等。３.联结词功能完全组已知有9个联结词就够用了，能不能少呢？若能少，表明有些联结词的逻辑功能可由其他联结词替代。事实上，也确实如此，因为有下列等价式：PQ(PQ)PQ(PQ)PQ(PQ)PQ(PQ)可见，扩充的4个联结词，，和能由原有5个联结词分别替代之。又由命题定律：PQ(PQ)(QP)PQPQPQ(PQ)PQ(PQ)可知，原有5个联结词，，，和又能由联结词组{，}或{，}取代。那么，究竟最少用几个联结词？就是说，用最少的几个联结词就能等价表示所有的命题公式。或者说，用最少的几个联结词就能替代所有联结词的功能。这便是所要定义的联结词功能完全组。定义1.5.2称G为联结词功能完全组，如果G满足下列两条件：①由G中联结词构成的公式能等价表示任意命题公式；②G中的任一联结词不能用其余下联结词等价表示。可以证明，{，}，{，}，{，}，{}，{}都是联结词功能完全组；而{，}，{}，{}，{}，{，}都不是联结词功能完全组，但为了表示方便，仍经常使用联结词组{，，}。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简单合取式为永假式的充要条件是：它同时含有某个命题变元及其否定。定理1.6.2简单析取式为永真式的充要条件是：它同时含有某个命题变元及其否定。２.析取范式与合取范式定义1.6.3一个命题公式A称为析取范式，当且仅当A可表为简单合取式的析取，即AAi；其中Ai为简单合取式，i=1，2，…，n。定义1.6.4一个命题公式A称为合取范式，当且仅当A可表为简单析取式的合取，即AAi；其中Ai为简单析取式，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，其构成的小项有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的小项真值表。从表1.7.1，表1.7.2可看出，小项有如下性质：(a)没有两个小项是等价的，即是说各小项的真值表都是不同的；(b)任意两个不同的小项的合取式是永假的：mi∧mjＦ，i≠j。(c)所有小项之析取为永真：miＴ。(d)每个小项只有一个解释为真，且其真值1位于主对角线上。(2)主析取范式定义与存在定理定义1.7.2在给定公式的析取范式中，若其简单合取式都是小项，则称该范式为主析取范式。定理1.7.1任意含n个命题变元的非永假命题公式A都存在与其等价的主析取范式。(3)主析取范式的求法主析取范式求法有两种：真值表法和公式化归法。定理1.7.1的证明已给出了用真值表求主析取范式的方法，而公式化归法给出如下：(a)把给定公式化成析取范式；(b)删除析取范式中所有为永假的简单合取式；(c)用等幂律化简简单合取式中同一命题变元的重复出现为一次出现，如P∧PP。(d)用同一律补进简单合取式中未出现的所有命题变元，如Q，则PP∧Q∨Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取范式。(4)主析取范式的惟一性定理1.7.2任意含n个命题变元的非永假命题公式，其主析取范式是惟一的。２.主合取范式(1)大项的概念和性质定义1.7.3在n个命题变元的简单析取式中，若每个命题变元与其否定不同时存在，而二者之一必出现一次且仅出现一次，则称该简单析取式为大项，或布尔和。例如，由两个命题变元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)任何两个不同大项之析取是永真的，即Mi∨MjＴ，i≠j。(c)所有大项之合取为永假，即MiＦ。(d)每个大项只有一个解释为假，且其真值0位于主对角线上。(2)主合取范式的定义与其存在定理定义1.7.4在给定公式的合取范式中，若其所有简单析取式都是大项，称该范式为主合取范式。定理1.7.3任意含有n个命题变元的非永真命题公式A，都存在与其等价的主合取范式。定理1.7.4任意含n个命题变元的非永真命题公式A，其主合取范式是唯一的。上述两定理的证明，类似于定理1.7.1和定理1.7.2。主合取范式的求法也有两种，类似于主析取范式的求法。３.主析取范式与主合取范式之间的关系由于主范式是由小项或大项构成，从小项和大项的定义，可知两者有下列关系：miMiMimi因此，主析取范式和主合取范式有着“互补”关系，即是由给定公式的主析取范式可以求出其主命取范式。从A的主析取范式求其主合取范式的步骤为：(a)求出A的主析取范式中设有包含的小项。(b)求出与(a)中小项的下标相同的大项。(c)做(b)中大项之合取，即为A的主合取范式。例如，(PQ)Qm1m3，则(PQ)QM４.主范式的应用利用主范式可以求解判问题或者证明等价式成立。（1）判定问题根据主范式的定义和定理，也可以判定含n个命题变元的公式，其关键是先求出给定公式的主范式Ａ；其次按下列条件判定之：(a)若AＴ，或A可化为与其等价的、含2n个小项的主析取范式，则A为永真式。(b)若AＦ，或A可化为与其等价的、含2n个大项的主合取范式，则A为永假式。(c)若A不与Ｔ或者Ｆ等价，且又不含2n个小项或者大项，则A为可满足的。（2）证明等价式成立由于任一公式的主范式是唯一的，所以将给定的公式求出其主范式，若主范式相同，则给定两公式是等价的。1.8命题逻辑的推理理论在逻辑学中，把从前题（又叫公理或假设）出发，依据公认的推理规则，推导出一个结论，这一过程称为有效推理或形式证明。所得结论叫做有效结论，这里最关心的不是结论的真实性而是推理的有效性。前提的实际真值不作为确定推理有效性的依据。但是，如果前提全是真，则有效结论也应该真而绝非假。在数理逻辑中，集中注意的是研究和提供用来从前提导出结论的推理规则和论证原理，与这些规则有关的理论称为推理理论。提请注意，必须把推理的有效性和结论的真实性区别开。有效的推理不一定产生真实的结论，产生真实结论的推理过程未必一定是有效的。再说，有效的推理中可能包含假的前提；而无效的推理却可能包含真的前提。可见，推理的有效性是一回事，前提与结论的真实与否是另一回事。所谓推理有效，指它的结论是它的前提的合乎逻辑的结果，也即，如果它的前提都为真，那么所得结论也必然为真，而并不是要求前提或结论一定为真或为假。如果推理是有效的话，那么不可能它的前提都为真时而它的结论为假。１.推理的基本概念和推理形式推理也称论证，它是指由已知命题得到新的命题的思维过程，其中已知命题称为推理的前提或假设，推得的新命题称为推理的结论。在数理逻辑中，前提H是一个或者n个命题公式H1,H2,···Hn；结论是一个命题公式C。由前提到结论的推理形式可表为H1,H2,···,HnC，其中符号表示推出···。可见，推理形式是命题公式的一个有限序列，它的最后一个公式是结论，余下的为前提或假设。定义1.8.1如果存在H1，H2，…，Hn，C的一个指派，使得每个Hi(1≤i≤n)为真而C为假推理形式H1，H2，…，HnC是无效的；否则，推理是有效的，此时称C是H1，H2，…，Hn的有效结论，或称C是从前提H1，H2，…，Hn逻辑推出的结论。定理1.8.1推理形式H1，H2，…，HnC是有效的，当且仅当命题公式(H1∧H2∧…∧Hn)→C是永真式，亦即(H1∧H2∧…∧Hn)C。２.推理规则在数理逻辑中，从前提推导出结论，要依据事先提供的公认的推理规则，它们是：①Ｐ规则(也称前提引入规则)：在推导过程中，前提可视需要引入使用。②Ｔ规则(也称结论引入规则)：在推导过程中，前面已导出的有效结论都可作为后续推导的前提引入。此外，在从前提推出的结论为条件式时，还需要下面规则：③ＣＰ规则(也称条件证明引入规则)：若推出有效结论为条件式R→C时，只需将其前件R加入到前提中作为附加前提且再去推出后件C即可。ＣＰ规则的正确性可由下面定理得到保证：定理1.8.2若H1，H2，…，Hn，RC，则H1，H2，…，HnR→C。３.推理定律在推理过程中，除使用推理规则后，还需要使用许多条推理定律，这些定律可由以前讲过的命题定律、蕴涵式及运用定理1.8.1而得到。下面只给出了由蕴涵式得出的推理定律，它们是：(1)P，QP(2)P，QQ(3)PP∨Q(4)PP→Q(5)QP→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)(PQ)，(QR)PR(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→