自学考试专题：离散数学课件

离散数学串讲概述离散数学课程包括数理逻辑、集合论、代数结构、图论等部分。数理逻辑包括命题演算和谓词演算，重点是公式演算与推理证明；集合论的重点是关系理论与映射的描述；代数结构主要是从系统宏观的代数方法去研究客观事物的各种性质与特征；图论则着重于数形结合的描述以及各种实际应用。离散数学国家自学考试时间为150分钟，在这段时间内，如果不对离散数学的基础知识有扎实的功底，不可能得到理想的成绩。因此，考生一定要培养对概念性知识的熟练运用，其中真值表、主析取和主合取范式、集合关系运算、群环域及图论几部分，容易出现考试内容，所占分值较高，考生要重点掌握。概述最后还要再提一下，基础知识是参加离散数学自学考试的关键，考查基本知识的基本题大约占试卷的百分之八十左右，要求我们一定要重点掌握。前面的选择和填空题都是考察对基本概念和原理的掌握情况，后面的分析计算题是考查理解和运用能力。第一章命题演算一、命题概念数理逻辑的任务是采用数学方法研究抽象的思维规律，研究的中心问题是推理，而推理基本要素是命题。具有确切真值的陈述句称作命题。所谓真值就是命题为真或为假的性质。判断一个语句是否为命题，首先要判断它是否是陈述句，然后判断是否具有唯一的真假值。在判断一个陈述句是否具有唯一的真假时，要注意：一个陈述句的真假暂时不能唯一地确定，但总有一天可以唯一确定，与一个陈述句的真假不能唯一确定是两件事。第一章命题演算例如：明年国庆节是个晴天。虽然现在谁也不知道它的真值，但是到了明年国庆节，就能判断真假，因此它的真值仍然是唯一的。例如：这个语句是错的。不能判断真值。真命题，假命题原子命题：不能再分解更简单的命题，也称为简单命题。复合命题：能够分解为更简单的命题。命题联结词：否定，合取，析取，条件，双条件第一章命题演算注意：条件（蕴含）数理逻辑中蕴含命题P→Q是对“如果……，则……”的一种逻辑抽象；（除非Q否则￢P）。P→Q为假当且仅当P为真且Q为假。第一章命题演算二、命题公式1、命题演算的合式公式规定为：（1）单个命题变元或命题常量（含1或0）本身是一个合式公式。（2）如果A是合式公式，那么￢A是合式公式。（3）如果A和B是合式公式，那么(A∧B)、(A∨B)、(A→B)和(A≒B)都是合式公式。（4）当且仅当有限次地应用（1）（2）（3）所得到的包含命题变元，联结词和圆括号的符号串是合式公式。合式公式亦称作命题公式或简称公式。第一章命题演算2、指派与真值表一个含有命题变元的命题公式是没有确定真值的。只有在命题公式中每个命题变元用指定的命题常量代替后，命题公式才有确定的真值，成为命题。设P为一命题公式，P1，P2，…，Pn为出现在P中的所有命题变元，对P1，P2，…，Pn指定一组真值称为对P的一种指派（解释或赋值）。若指定的一种指派，使P的值为真，则称这组值为成真指派；使P的值为假，则称这组值为成假指派。含n个命题变元的命题公式，共有2n组指派。将命题公式P在所有指派下取值情况，列成表，称为P的真值表。第一章命题演算真值表方法：（1）如果公式A中有n个命题符，则A的真值表共有2n+1行。第一行称为表头，在表头的第一列写出所有的命题符，从表头第二列开始，依次写上公式A的生成过程中生成的子串（这些子串也是公式）。（2）剩下的2n行，每一行对应一个指派。对于每一个指派，依次求出各个子串的值，知道最后求出A的值。例如：给出(P∧Q)∨(￢P∧￢Q)的真值表。PQ￢P￢QP∧Q￢P∧￢Q(P∧Q)∨(￢P∧￢Q)1100101100100001100000011011第一章命题演算3．公式分类设A为一命题公式，若A在它的各种指派情况下，其取值均为真，则称公式A为重言式或永真式。设A为一命题公式，若A在它的各种指派情况下，其取值均为假，则称公式A为矛盾式或永假式。设A为一命题公式，若A在各种真值指派下至少存在一组成真指派，称A是可满足式。三、等价公式与演算公式G，H是等价的，如果在其任意的指派下其真值相同。此表中最后两个重点记忆。证明两个公式等价或永真永假或可满足式，可用等值演算或真值表法。第一章命题演算第一章命题演算四、主析取和主合取范式由“￢”，“∧”，“∨”，“→”，“≒”这五个联结词中若干个组成的命题公式，必可由{￢，∨}或{￢，∧}组成的命题公式所替代。我们把{￢，∨}及{￢，∧}称作命题公式的最小联结词组。（1）主析取范式小项：n个命题变员的合取式，称作布尔合取或小项，其中每个变员与它的否定不能同时存在，但两者之一必须出现且仅出现一次。两个命题变员P和Q，其小项为P∧Q，P∧￢Q，￢P∧Q，￢P∧￢Q。第一章命题演算n个命题变元共有2n个小项，可以用二进制编码表示。下面以三个变元为例：m000=￢P∧￢Q∧￢Rm100=P∧￢Q∧￢Rm001=￢P∧￢Q∧Rm101=P∧￢Q∧Rm010=￢P∧Q∧￢Rm110=P∧Q∧￢Rm011=￢P∧Q∧Rm111=P∧Q∧R或记为mi(i=0，1，2，3，4，5，6，7)。主析取范式：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。第一章命题演算真值表法：在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式主析取范式。除了真值表法外，还可以用等值演算法求主析取范式。第一章命题演算例写出公式(￢p→q)→(q→￢p)的主析取范式。解：方法一，真值表法：列出真值表1表1从真值表看出，真值为1的小项有m00，m01，m10三项，故原式的析取范式为m00∨m01∨m10=(￢p∧￢q)∨(￢p∧q)∨(p∧￢q)。第一章命题演算方法二，等值演算法：(￢p→q)→(q→￢p)(p∨q)→(￢q∨￢p)￢(p∨q)∨(￢q∨￢p)(￢p∧￢q)∨￢q∨￢p￢q∨￢p(￢p∧(￢q∨q))∨((￢p∨p)∧￢q)(￢p∧￢q)∨(￢p∧q)∨(￢p∧￢q)∨(p∧￢q)(￢p∧￢q)∨(￢p∧q)∨(p∧￢q)=m00∨m01∨m10=∑(0,1,2)。第一章命题演算等值法求主（析取或合取）范式：（1）利用等价式P→Q￢P∨Q，P≒Q(P→Q)∧(Q→P)消去公式中的联结词→和≒；（2）利用德·摩根律将公式中的联结词￢移至命题符前，并利用对合律消去两个连续的联结词￢；（3）利用分配律P∧(Q∨R)(P∧Q)∨(P∧R)将公式化为基本积的析取。（4）其关键是，在求出析取范式后，对基本积补入没有出现的命题符（例如把￢p置换称￢p∧(￢q∨q)），然后再用分配律展开。第一章命题演算（2）主合取范式大项：n个命题变元的析取式称作布尔析取或大项。其中每个变元与它的否定不能同时存在，但两者之一必须出现且仅出现—次。两个命题变元P和Q构成的大项有P∨Q，P∨￢Q，￢P∨Q，￢P∨￢Q。每个大项也可以编码，首先将n个命题变元排序，把每个命题变元对应为0，将命题变元的否定对应为1，则可将2n个大项按二进制数编码。记为Mi，其下标i是由二进制数化为十进制数。第一章命题演算三个命题变元的大项：M000=P∨Q∨RM100=￢P∨Q∨RM001=P∨Q∨￢RM101=￢P∨Q∨￢RM010=P∨￢Q∨RM110=￢P∨￢Q∨RM010=P∨￢Q∨￢RM110=￢P∨￢Q∨R或记为Mi(i=0，1，2，3，4，5，6，7)。第一章命题演算真值表法：在真值表中一个公式的真值为F的指派所对应的大项的合取，即为此公式的主合取范式。例5求p∧q∨r的主合取范式。解：方法一，真值表法：列出真值表:PqRP∧qp∧q∨r0000000101010000110110000101011101111111第一章命题演算从表中可以看出，真值为F所对应的大项编码有M000，M010，M100，所以与原式等价的主合取范式为M000∧M010∧M100=∏(0,2,4)。方法二，等值演算法：p∧q∨r(p∧q)∨r(p∨r)∧(q∨r)(p∨(q∧￢q)∨r)∧((p∧￢p)∨q∨r)(p∨q∨r)∧(p∨￢q∨r)∧(p∨q∨r)∧(￢p∨q∨r)(p∨q∨r)∧(p∨￢q∨r)∧(￢p∨q∨r)M000∧M010∧M100M0∧M2∧M4=∏(0,2,4)。第一章命题演算设命题公式A中含有n个命题变元，且A的主析取范式中含有k个小项mi1，mi2，…，mik，则A的主合取范式必含有2n-k个大项。如果命题公式A的主析取范式为∑(i1,i2,…,ik)，则A的主合取范式为：∏(0，1，2，…，i1-1，i1+1，…，ik-1，ik+1，…，2n-1)。从A的主析取范式求其主合取范式步骤为：（1）求出A的主析取范式中未包含小项的下标。（2）把（1）中求出的“下标”写成对应大项。（3）做（2）中写成的大项合取，即为A的主合取范式。例(P→Q)∧Q∑(1,3)=m01∨m11，(P→Q)∧Q∏(0,2)=M00∧M10。第一章命题演算五、推理理论这部分常出大题考查。（1）真值表法（2）主范式方法及等值演算法第一章命题演算等值公式表和蕴含公式表整理归纳如表1.表2第一章命题演算（3）构造论证法常用的推理规则有：（1）前提引入规则：在证明的任何步骤上，都可以引入前提，简称P规则。（2）结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提，称为T规则。（3）置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以用与之等值的命题公式置换。亦记为T规则。第一章命题演算例证明：(P∨Q)∧(P→R)∧(Q→S)├S∨R。证明：（1）P∨QP（步骤1，引用P规则得P∨Q）（2）￢P→QT.（1）E（步骤2，由（1），根据等价公式表E，引用T规则得￢P→Q）（3）Q→SP（4）￢P→ST.（2）（3）I（步骤4，由（2）（3），根据蕴含公式表I，引用T规则得￢P→S）第一章命题演算（5）￢S→PT.（4）E（6）P→RP（7）￢S→RT.（5）（6）I（8）S∨RT.（7）E（步骤8，S∨R是有效结论）。第一章命题演算间接证明法：包括附加前提和CP规则法。要注意的是，这两种方法都要引入附加的前提，但是附加前提的引入是有目的的，不是随心所欲的。（1）附加前提。引入结论的否定作为前提，导致最后推出F，则得证。这实际上是一种反证法，有的书上也叫反证推理规则。（2）CP规则。常用于结论为蕴涵式情况。引入结论的前件作为前提，最后推出后件。等价证明1,2,GGGnPS1,2,GGGnPS第二章谓词演算谓词演算引进了客体和谓词概念，并讨论谓词公式中引入量词及其辖域的概念，为此，谓词逻辑能处理更为复杂的问题。本章的学习主要是在掌握命题逻辑的基础上，理解个体，谓词，量词等概念，学会将命题进一步用谓词逻辑表示；在熟记谓词逻辑中的等价式和蕴含式的基础上，将一个谓词演算公式化为与它等价的前束范式；并能运用US、UG、ES、EG等规则，进行谓词演算的推理。本章的重点是带量词的公式变换，即前束范式。难点是谓词演算的推理理论。第二章谓词演算一、谓词的概念与表示客体（个体）和谓词例如，王强是个大学生；其中“是个大学生”是谓词；而“王强”是客体（主语、宾语）。个体变项的取值范围称为个体域(或称论域)。第二章谓词演算全总个体域。当我们讨论问题时，作为讨论对象的非空集合就称为论域（个体域），论域中的元素就是我们要讨论的对象，这就是个体。在简单命题中，表示一个个体性质或多个个体之间关系的词称为谓词。谓词和个体一起，就构成了简单命题中的主谓结构。由一个谓词，一些个体变元组成的表达式简称为谓词变项或称为命题函数。命题函数不是命题，只有命题函数中的变元都取为特定具体的个体时，才是确定的命题。例如L(x,y)：x小于y。若x，y为有理数，则L(x,y)为谓词变项即命题函数；若x，y取3，5，则L(3,5)是谓词常项，即L(3,5)是命题。第二章谓词演算谓词变项中，个体变员的数目称为谓词变项的元数。如P(x1,x2,…,xn)为n元谓词，但是当n元谓词中某一个体变项取作常量时，即P(a,x1,x2,…,xn-1)，其中a是常量，x1，x2，…，xn-1为