离散数学教程

高等学校21世纪教材电子教案人民邮电出版社第一章命题逻辑命题逻辑，也称命题演算，记为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…及其带下标的Pi，Qi，Ri，…表示。第二类是复合命题，它由原子命题、命题联结词和圆括号组成。２.定义1.1.1设P表示一个命题，由命题联结词l和命题P连接成lP，称lP为P的否定式复合命题，lP读“非P”。称l为否定联结词。lP是真，当且仅当P为假；lP是假，当且仅当P为真。否定联结词“l”的定义可由表1.1.1表示之。表1.1.1的定义PP1001由于否定”修改了命题，它是对单个命题进行操作，称它为一元联结词。定义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.2∧的定义PQP∧Q000110110001定义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.3∨的定义PQP∨Q000110110111由定义可知，析取联结词表示“可兼和”，“不可兼和”另有别的联结词定义之。与合取联结词一样，使用析取联结词时，也不要求两命题间一定有任何关系，有关例子就不再给出了。定义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表示之。表1.1.4PQP→Q000110111101在条件命题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.1.5的定义PQPQ000110111001在本节结束时，应强调指出的是：复合命题的真值只取决于各原子命题的真值，而与它们的内容、含义无关，与原子命题之间是否有关系无关。理解和掌握这一点是至关重要的，请读者认真去领会。1.2命题变元和合式公式１.在命题逻辑中，命题又有命题常元和命题变元之分。一个确定的具体的命题，称为命题常元；一个不确定的泛指的任意命题，称为命题变元。显然，命题变元不是命题，只有用一个特定的命题取代才能确定它的真值：真或假。这时也说对该命题变元指派真值。命题常元和命题变元均可用字母P等表示。由于在命题逻辑中并不关心具体命题的涵义，只关心其真值，因此，可以形式地定义它们如下：定义1.2.1以真或1、假或0为其变域的变元，称为命题变元；真或1、假或02.通常把含有命题变元的断言称为命题公式。但这没能指出命题公式的结构，因为不是所有由命题变元、联结词和括号所组成的字符串都能成为命题公式。为此常使用归纳定义命题公式，以便构成的公式有规则可循。由这种定义产生的公式称为合式公式。定义1.2.2单个命题变元和命题常元称为原子命题公式，简称原子公式。定义1.2.3合式公式是由下列规则生成的公式：①单个原子公式是合式公式。②若A是一个合式公式，则(lA)也是一个合式公式。③若A、B是合式公式，则(A∧B)、(A∨B)、(A→B)和(AB)都是合式公式。④只有有限次使用①、②和③生成的公式才是合式公式。当合式公式比较复杂时，常常使用很多圆括号，为了减少圆括号的使用量，可作以下约定：①规定联结词的优先级由高到低的次序为：l、∧、∨、→、②相同的联结词按从左至右次序计算时，圆括号可省略。③最外层的圆括号可以省略。为了方便计，合式公式也简称公式。３.定义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是等价的，或逻辑相等，记作AB，读作A等价B，称AB为等价式。显然，若公式A和B的真值表是相同的，则A和B等价。因此，验证两公式是否等价，只需做出它们的真值表即可。在这里，请读者注意和的区别与联系。区别：是逻辑联结词，属于目标语言中的符号，它出现在命题公式中；不是逻辑联结词，属于元语言中的符号，表示两个命题公式的一种关系，不属于这两个公式的任何一个公式中的符号。联系：可用下面定理表明之。定理1.3.1A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设A1是合式公式A的子公式，若A1B1，并且将A中的A1用B1替换得到公式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*互为对偶式，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为两个命题公式，若AB则A*B*。有了等价式、代入规则、替换规则和对偶定理，便可以得到更多的永真式，证明更多的等价式，使化简命题公式更为方便。２.蕴涵式定义1.4.2设A和B是两个命题公式，若A→B是永真式，则称A蕴涵B，记作AB，称AB为蕴涵式或永真条件式。符号→和的区别与联系类似于和的关系。区别：→是逻辑联结词，属于对象语言中的符号，是公式中的符号；而不是联结词，属于元语言中的符号，表示两个公式之间的关系，不是两公式中符号。