自考离散数学命题演算笔记.doc

自考离散数学命题演算笔记本章的重点是命题概念及其表示、命题公式化简、主范式及其互化、P规则、T规则以及CP规则。难点是推理理论及应用。一、命题概念(领会)学习本章首先要深刻理解命题的概念。理解原子命题与复合命题的关系，在了解复合命题的基础上，理解联结词的定义。命题：具有唯一真值的陈述句称为命题，又简称语句。注意，这里有两个条件，首先它是一个陈述句，其次，它具有唯一的一个真值。真值：就是语句为真或假的性质。一个语句的真值可以为真也可以为假。真值不是说该语句的值必为真。任一命题必有其真值，也称这个命题的值。既然是命题了，那它必有一个确定的真值，不管这个真值为真还是为假。当一个陈述句能够分辩其值的真假时(也就是说，总可以肯定是其中的某一个)，它就是命题，即使我们不知道它是真还是假。另外要理解命题常量、命题变元及指派的含义。复合命题就是一些原子命题经过一些联结词复合而成的命题。常用的联结词有：(1)否定、(2)合取、(3)析取、(4)条件、(5)双条件复合命题与联系词是密切相关的，不包含联结词的命题就是原子命题，至少包含一个联结词的命题才是复合命题。复合命题的真值只取决于构成它们的各原子命题的真值，而与它们的内容含义无关。对联结词所联结的两原子命题之间有无关系无关。(这一条很重要，因为一个命题用自然语言表达时，我们往往会受到自然逻辑的影响，比如我如果不上班，那么天下雨这种命题，在自然的逻辑里，是不成立的，一个人不上班怎么会导致天下雨呢? 但是在这里，这个复合命题的值实际上是由两个原子命题的真值决定的，与它的含义无关，这个复合命题是|P-Q ,前一个原子命题的真值为假，后一命题值为真，根据条件的定义，这个复合命题值为真)、具有对称性，|、无对称性，(教材提示，也可用iff表示双向箭头，由于字符集的限制，本网页在表示否定关联词时用|，请在书写时注意规范写法。对称性是指真值表中复合命题的真值与原子命题的真值之间的关系。)命题公式与命题不同，在一个由命题标识符组成的式子中，如果标识符表示确定的命题，则该式就是命题。如果标识符只表示命题的位置，可由任何命题代替，则该式子就为命题公式。命题变元P用特定命题替代时，称为对P的指派。不是所有由命题变元、联结词及有关括号组成的字符串都能成为命题公式。要成为一个命题公式(合式公式)，应当符合规定。这个规定是：(1)单个命题变元本身是一个合式公式。(2)如果A是合式公式，那么|A是合式公式。(3)如果A和B是合式公式，那么(AB)、(AB)、(AB)和(AB)都是合式公式。(4)当且仅当有限次地应用(1)(2)(3)所得到的包含命题变元、联结词和圆括号的符号串是合式公式。总的理解就是说，单个命题变元是合式公式，由合式公式作为命题变元，有限次地运用联结词及括号组成的符串才能是合式公式。即命题公式，简称公式。命题变元只有进行指派后才可能确定其所在命题公式的真值。当一个命公式中的所有命题变元用一组真值指定后，就称为对命题公式的指派。想一想，什么是真指派、什么是假指派? 这个比较简单。一个命题的真值表应该列出其所有指派的取值情况。一般来说，由n个命题变元组成的命题公式共有2n种真值情况。联结词的简化，按照两个等价的命题公式，可以看到一个有较多联结词的公式可以简化为含有一个联结词的公式。这里有两个等值公式应当记一下：(|PQ)(PQ)我们要弄清什么是重言式(永真式)、什么是矛盾式(永假式)以及可满足式。这其中涉及到指派及命题公式的取值，容易理解。课本中表1.3.6列出的常用的命题公式等价定理应该记住的.二、等价变换(简单应用)当两个合式公式中相应变元的任一种真值指派情况下，这两个公式的真值均相同，则这两个合式公式是等价的。可以相互置换。有两个命题公式A、B，AB，当且仅当AB为一重言式(永真式)。这是什么意思呢? 就是说，如果有两个命题A、B，只有在命题公式(AB)(双条件式)的值是永真的时候，这两个命题才是等价的。蕴含式又称永真条件式。永真条件式更清楚地表达了它的定义，就是一个条件式PQ，当且仅当它是重言式时，就称P蕴含Q (P=Q)。什么时候PQ不是蕴含式呢? 很明显，当P为真、Q为假时，它不是一个蕴含式。蕴含式有四个性质：(1) 对任意公式A,有A=A，即公式蕴含本身。(2) 对任意公式A，B和C，若A=B、B=C 则 A=C。(3) 对任意公式A，B和C，若A=B、A=C 则 A=(BC)证明如下：如果A的值为T，由AB、AC为重言式可得B为T、C为T，此时BC为T。如果A的值为F，则无论B、C为T或F，A(BC)为T，所以A(BC)是重言式，即A=(BC)。(4) 对任意公式A，B和C，若A=C、B=C 则 (AB)=C证明如下：如果A的真值为T，由AC为重言式可得C为T，此时不论B为何值，(AB)为T，(AB)-C为T。若B为T，由BC为重言式可得C为T，此时不论A为何值，(AB)为T，(AB)-C为T。若A和B均为F，则不论C为何值，(AB)C为T。所以(AB)=C。设P、Q为任意两个命题公式，PQ的充分必要条件是P=Q，Q=P.就是说，若要证明两个命题公式等价，只要证明两个公式互相蕴含。反过来，如果两个公式是互为蕴含的，那么，这两个公式是等价的。同样，第14页的表1.4.1也应记住。三、最小联结词组与范式：(简单应用)通过等价变换，我们可以把带、 的公式全部化成只带 |、或只带|、的命题公式，这种只带此两种联结词的公式就是标准形式，即范式。注意,单独的|、及、都不能是命题公式的最小联结词组。只有|、|、是命题公式的最小联结词组。范式根据其形式的不同又分为合取范式和析取范式。注意合取范式并不是只带|和的公式。它要求各个子公式均是由命题变元及其否定组成的析取式。而析取范式则恰恰相反。由n个命题变元(不是命题公式)组成的合取式，就称为布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者必须出现(其中之一)且仅出现一次。就是说每个变元或其否定必在一个小项内出现。小项的三个性质为：(1)每个小项具有一个相应编码，当该编码与其真实指派相同时，该小项真值为T。其余各种指派情况下均为F。(2)任意两个不同小项的合取式永假。因为每个小项有唯一不同的编码，当指派与一个小项的编码相同时，必与另一个小项的编码不同，所以总有一个小项为假。(3)全体小项的析取式为永真。因为在任一指派情况下，总有一个小项为真。主析取范式是对应于原命题公式而言的，它是原命题公式的一个等价公式，而且仅由小项的析取所组成。那么要最直接地找到一个命题公式的主析取范式，就可以应用真值表，一个使公式真值为T的指派所对应的小项的析取就是此公式的主析取范式。有了小项，则有大项(布尔析取),大项与小项定义的不同之处就是把合取变成了析取。在真值表中一个公式的值为F的指派所对应的大项的合取，即为此公式的合取范式。对于任意含有n个命题变元的非永真命题公式A，其合取范式是唯一的。下面我们将小项与大项作一对比，以利记忆。 小项(布尔合取)大项(布尔析取)定义n个命题变元的合取式n个命题变元的析取式形式PQ，P|Q，|PQ，|P|Q，PQ，P|Q，|PQ，|P|Q，主范式命题变换得主析取范式命题变换为主合取范式真值表法求主范式公式真值为T的指派所对应的小项的析取公式真值为F的指派所对应的大项的合取主范式形式m00m01m02 (0，1，2.)小项的m用小写，析取就是相当于连加M00M01M02 (0，1，2.)大项的M用大写，合取就相当于连乘 记忆变元合取是小项；小项尖尖头朝上；公式值真对主析；析取小项换命题。变元析取好大项，大项宽宽口朝天。公式值假对大项，合取大项主合范。对课本中的例题应认真学习掌握。1.6 推理理论(简单应用)推理就是把一些假设前提作为T，并使用一些公论的规则，得到另外的命题形成结论，这种过程很有意思，大侦探福尔摩斯就是深谙此道的人，如果我们学会了推理，那么在做一些智力题时是很有帮助的，就象是本章最后的那几道题，一般人要翻来覆去考虑很久，看看我们能不能用公式来解开它。对于推理理论，主要要掌握的是判别有效结论的过程也就是论证过程。有真值表法、主范式方法、等值演算法和构造论证法。其中构造论证法是本节的重点。使用构造论证法，首先要确定推理定律及等值定律，也就是我们前面学过的定律及公式可以直接应用的，其次是要确定已知的前提，假设其值为真。推理过程就是一系列命题公式序列，其中每个命题公式或者是已知的前提，或者是由某些前提应用推理规则得到的结论。那么常用的推理规则有：(1)P规则：前提引