自考离散数学串讲.ppt

离散数学【02324】主讲：王喜斌希赛网专业的在线教育平台概述p离散数学课程包括数理逻辑、集合论、代数结构、图论等部分。p数理逻辑包括命题演算和谓词演算，重点是公式演算与推理证明；p集合论的重点是关系理论与映射的描述；p代数结构主要是从系统宏观的代数方法去研究客观事物的各种性质与特征；p图论则着重于数形结合的描述以及各种实际应用。概述p国家自学考试时间为150分钟，在这段时间内，如果不对离散数学的基础知识有扎实的功底，就不可能得到理想的成绩。p考生一定要培养对概念、知识的熟练运用。p真值表、主析取和主合取范式、集合关系运算、群环域及图论几部分，容易出现考试内容，所占分值较高，考生要重点掌握。概述p最后还要再提一下，基础知识是参加离散数学自学考试的关键，考查基础知识的基本题大约占试卷的百分之八十左右，要求我们一定要重点掌握。前面的选择和填空题都是考察对基本概念和原理的掌握情况，后面的分析计算题是考查理解和运用能力。考核内容与考核要求1.命题与命题联结词，要求达到“领会”层次。能对命题进行符号化；掌握命题联结词，能够使用联结词熟练构造复合命题。2.命题公式的等值演算，要求达到“简单应用”层次。掌握命题公式的概念，能够构造命题公式的真值表，能够正确判断重言式、矛盾式和可满足公式。熟记常用的命题定律和蕴含式，掌握命题公式的等值关系和蕴含关系，能够进行简单的公式论证。3.联结词完备集，要求达到“领会”层次。第1章命题与命题公式重点：1.命题与命题联结词，2.将命题进行符号化，3.命题公式的真值表，4.命题公式的化简及命题的等值演算。难点：1.命题公式的化简2.等值演算及其应用第1章命题与命题公式1.1命题与命题联结词命题基本概念数理逻辑的任务是采用数学方法研究抽象的思维规律，研究的中心问题是推理，而推理基本要素是命题。具有确切真值的陈述句称作命题。所谓真值就是命题为真或为假的性质。判断一个语句是否为命题，首先要判断它是否是陈述句，然后判断是否具有唯一的真假值。在判断一个陈述句是否具有唯一的真假时，要注意：一个陈述句的真假暂时不能唯一地确定，但总有一天可以唯一确定，与一个陈述句的真假不能唯一确定是两件事。1.1命题与命题联结词例如：明年国庆节是个晴天。虽然现在谁也不知道它的真值，但是到了明年国庆节，就能判断真假，因此它的真值仍然是唯一的。例如：这个语句是错的。不能判断真值。真命题，假命题原子命题：不能再分解更简单的命题，也称为简单命题。复合命题：能够分解为更简单的命题。命题联结词：否定，合取，析取，条件，双条件1.1命题与命题联结词例1.1判断下列句子中哪些构成命题。(1)8不是素数;(2)雪是黑的;(3)到2049年世界人口将超过90亿;(4)每台计算机都有唯一的IP地址;(5)喜马拉雅山好高啊!(6)基本粒子是不可分的;(7)离散数学难学吗?(8)请遵守交通规则(9)x+1=2。1.1命题与命题联结词例1.2将下面命题符号化,并指出它们的真值。(1)丌是有理数;(2)所有的素数都是奇数;(3)6是一个合数。解:分别使用P、Q和R来表示上述三个命题:P:丌是有理数。Q:所有的素数都是奇数。R:6是一个合数。丌是无理数,所以P的真值为F。2是素数,也是偶数,除此之外,其他的素数都是奇数。Q的真值为F。因为2和3都是6的因子,所以6是合数,R的真值为T。1.1命题与命题联结词PPTFTFFTFT1.否定的定义五个命题联结词例1.3给出命题P：“今天是星期五”的否定，并用自然语言表示出来。解P：今天不是星期五1.1命题与命题联结词2.合取的定义PQPQTTTTFFFTFFFFl“并且”l“既又”l“不但而且”l“虽然但是”l“一面一面”具有对称性PQ=QP1.1命题与命题联结词例1.4将下面命题符号化。(1)2既是偶数,也是素数;(2)我今天不但听了离散数学课,还听了数据结构课(3)今天的离散数学课停上,美元上涨。解:(1)设P:2是偶数,Q:2是素数。故(1)可表示为PQ(2)设P:我今天听了离散数学课,Q:我今天听了数据结构课。故(2)可表示为PQ。(3)设P:今天的离散数学课停上,Q:今天美元上涨故(3)可表示为PQ。1.1命题与命题联结词3.析取的定义PQPQTTTTFTFTTFFF具有对称性PQ=QPl“同或”l非“异或”1.1命题与命题联结词例1.5将下面命题符号化。(1)王小林是本年度校运动会的跳高或100米短跑的冠军(2)我今天或者去听离散数学课,或者去听数据结构课。解:(1)设P:王小林是本年度校运动会的跳高冠军,Q:王小林是本年度校运动会的100米短跑的冠军。故(1)可表示为PVQ。这个命题表达的是王小林或者是跳高冠军,或者是短跑冠军,也有可能是两个项目的冠军。(2)设P:我今天去听离散数学课,Q:我今天去听数据结构课。故(2)可表示为PVQ。这个命题表达的是我今天可能去听离散数学或者数据结构课,也可能两门课都去听。1.1命题与命题联结词此处,“或”表示的是“相容”的含义,也称为“同或”,即两者并不互相排斥,可能同时成立。自然语言中有时会使用“或”来表示“相斥”的含义,即用“或”连接的两者不能同时成立,这样的语句不能表示为析取。例1.6分析以下的复合命题。(1)王小林今天或者去美国,或者去欧洲。(2)王小林或者是坐火车去北京,或者是乘飞机去北京。1.1命题与命题联结词解:(1)设P:王小林今天去美国,Q:王小林今天去欧洲。显然,如果王小林今天去了美国,他就不可能去欧洲,反之也是一样。王小林没有分身术,他只能去一个地方。所以(1)不能简单地表示为PVQ(2)设P:王小林坐火车去北京,Q:王小林乘飞机去北京。这个命题假设王小林只需乘坐一种交通工具即可到达北京。与(1)类似,王小林不能同时既坐火车又乘飞机。PVQ也不能精确地表达(2)中命题的含义。(1)和(2)所表述的这两个例子有一个共同的特点,即复合命题中的两个原子命题不会同时成立，它们之间具有相斥性，这样的“或”表示的是“异或”。实际上，（1）和（2）均可表示为：(PQ)V(PQ)1.1命题与命题联结词4.PQ的定义PQPQTTTTFFFTTFFT不具有对称性注意：条件（蕴含）l“如果，则”l“若，则”l除非Q否则P；lPQ为假当且仅当P为真且Q为假。1.1命题与命题联结词例1.7将下面命题符号化。(1)如果今天不下雨,我就去公园锻炼。(2)如果我考试通过,就能拿到合格证书解:(1)设P:今天下雨,Q:我去公园锻炼故(1)可表示为PQ。注意：仅当今天没有下雨而我没去公园锻炼时,命题(1)为F(2)设P:我考试通过,Q:我拿到合格证书。故(2)可表示为PQ。1.1命题与命题联结词需要注意,条件命题的前件和后件之间可以在语义上不存在逻辑关系。这与我们日常的表述是有差异的。例1.8如果雪是黑的,则房间里有20张桌子解:设P:雪是黑的;Q:房间里有20张桌子。本例还是可以符号化为:PQ。命题pq表示“q是p的必要条件”。自然语言中表示“q是p的必要条件”有许多不同的叙述方式,例如,“只要p,就q”,“因为p,所以q”,“p仅当q”,“只有q才p”,等等。1.1命题与命题联结词例1.9将下列命题符号化。(1)如果今天不下雨而且不刮风,我会去爬山;(2)若今天是星期一,则明天是星期二。(3)只有今天是星期一,明天才是星期二。解:(1)设P:今天下雨,Q:今天刮风,R:我去爬山则(1)可表示为(PQ)R(2)设P:今天是星期一,Q:明天是星期二。则(2)可表示为PQ本例还隐含着另一层意思,即如果今天不是星期一(前件为假时),则明天可能是星期二,也可能不是星期二,不得而知。或者反过来说,如果明天是星期二,则不表明今天一定是星期一。要注意,命题的含义一定要和我们日常的概念分开。(3)设P:今天是星期一,Q:明天是星期二。则(3)可表示为QP本例中表述的另一层含义是“明天是星期二”的话,“今天一定是星期一”。1.1命题与命题联结词PQTTTTFFFTFFFT具有对称性PQ=QPl“等价”l“充分必要条件”l“当且仅当”5.1.1命题与命题联结词例1.10将下面命题符号化,并指出其真值(1)当且仅当实数R可以表示为分数时,R是有理数;(2)3是无理数当且仅当加拿大位于亚洲。解:(1)设P:实数R可以表示为分数,Q:实数R是有理数。则(1)可表示为PQ。由数学知识可知,(1)所表述的即是有理数的定义,所以它的真值为T。(2)设P:3是无理数,Q:加拿大位于亚洲则(2)可表示为PQ。由数学知识知,P为T,而由地理知识知,Q为F,所以(2)的真值为F1.1命题与命题联结词综合练习设P:今天下雨,Q:今天刮风,R:我去爬山。将下面命题用自然语言表述。(PVQ)R;R(PQ);PQPQ;QP表示:今天要是下雨或者刮风,我就不去爬山了;表示:如果我去爬山了,则今天既没下雨也没刮风表示:今天下雨了,但没有刮风;表示:如果今天下雨,就不会刮风;表示:如果今天刮风,就会下雨。1.2命题公式的等值演算命题公式命题符号化的过程中,可以用一个符号表示一个命题。当符号P代表一个具体的命题时,符号P称为命题常项,此时P的真值是确定的,所以称为“常”项。这类似于数学表达式中的一个常数。而当符号P仅仅表示是一个命题,但并没有指明是哪个命题时,P为命题变元。命题变元P可以代表任一个命题,正如数学表达式中的一个变量一样。如果给P代入一个真值为T的命题,P的真值为T;如果代入一个真值为F的命题,P的真值为F。在代入之前,P的值是不确定的,所以称为“变”元。一般地,命题变元不是命题。1.2命题公式的等值演算在表示数学操作时,我们可以用操作符将操作数连接起来,得到一个数学表达式,比如a+3。同时可以使用圆括号改变操作符的运算次序,比如2*(x+3)。在命题逻辑中也是一样,可以使用联结词将命题连接起来,得到一个更复杂的命题,即复合命题。这里,命题类似于表达式中的操作数,联结词类似于表达式中的操作符。联结词连接的命题符号既可以是命题常项,也可以是命题变元。同样,也可以在这样的式子中添加圆括号。将命题用联结词和圆括号按一定的逻辑关系联结起来的符号串称为合式公式1.2命题公式的等值演算1.2命题公式的等值演算例1.12设P、Q、R分别代表命题变元或命题常项,给定以下字符串,判断哪些是合式公式。(P Q)(P Q)V(PQ)P QV(PQ)PVQ解:、都是合式公式。不是合式公式。实际上,合式公式最外层的括号是可以省略的,所以还可以表示为:PQ。本身已去掉了最外层的括号。有意思的是与相比,它去掉了第一对括号。数理逻辑中规定,不影响运算次序的括号也可以省去。与数学表达式一样,合式公式中的括号可以改变运算次序与相差的只是第一对括号,去掉它会不会改变运算次序呢?这要看各联结词的优先级了。命题逻辑中规定,联结词优先次序依次为:,V,。的优先级高于V的优先级,有没有括号,都要先计算运算。1.2命题公式的等值演算定义设Ai是公式A的一部分,且Ai是一个合式公式,称Ai是A的子公式,或公式分量。例1.13指出合式公式(PVQ)(R(PQ)中的子公式有哪些。解:它的子公式有以下一些:A1:PA2:QA3:RA4:PA5:PVQA6:PQA7:R(PQ)1.2命题公式的等值演算在命题公式中,由于有命题变元的出现,因而真值是不确定的。用命题常项替换公式中的命题变元称作指派。当将公式中出现的全部命题变元都指派成具体的命题常项之后,公式就成了真值确定的命题。1.2命题公式的等值演算2、指派与真值表一个含有命题变元的命题公式是没有确定真值的。只有在命题公式中每个命题变元用指定的命题常量代替后，命题公式才有确定的真值，成为命题。设P为一命题公式，P1，P2，Pn为出现在P中的所有命题变元，对P1，P2，Pn指定一组真值称为对P的一种指派（解释或赋值）。若指定的一种指派，使P的值为真，则称这组值为成真指派；使P的值为假，则称这组值为成假指派。含n个命题变元的命题公式，共有2n组指派。将命题公式P在所有指派下取值情况，列成表，称为P的真值表。1.2命题公式的等值演算真值表构造方法：如果公式A中有n个命题符（命题变元），则A的真值表共有2n+1行。第一行称为表头，在表头的第一列写出所有的命题符，从表头第二列开始，依次写上公式A的生成过程中生成的子串（这些子串也是子公式）。剩下的2n行，每一行对应一个指派。一般按二进制的加法顺序依次赋值。对于每一个指派，依次求出各个子串的值，直到最后求出A的值。1.2命题公式的等值演算例如：给出(PQ)(PQ)的真值表。PQPQPQPQ(PQ)(PQ)11001011001000011000000110111.2命题公式的等值演算3公式分类设A为一命题公式，若A在它的各种指派情况下，其取值均为真，则称公式A为重言式或永真式。设A为一命题公式，若A在它的各种指派情况下，其取值均为假，则称公式A为矛盾式或永假式。设A为一命题公式，若A在各种真值指派下至少存在一组成真指派，称A是可满足式。若可满足式A至少存在一个成假赋值，则A称为非重言式的可满足式。1.2命题公式的等值演算1.2命题公式的等值演算公式G，H是等价的，如果在其任意的指派下其真值相同。证明两个公式等价或永真永假或可满足式，可用等值演算或真值表法。常用的命题定律如下表(P.28P.29)：1.2命题公式的等值演算1.2命题公式的等值演算1.3联结词完备集1.3联结词完备集考核内容与考核要求1.范式，要求达到“领会”层次。范式的概念，掌握范式的概念与性质，能够正确计算给定公式的范式。小项与大项，掌握小项与大项的概念与性质，能够正确计算给定公式的成真赋值、成假赋值及对应的编码。2.主范式，要求达到“简单应用”层次。主析取范式，掌握主析取范式的概念及性质，能够正确计算给定公式的主析取范式。主合取范式，掌握主合取范式的概念及性质，能够正确计算给定公式的主合取范式。3.自然推理系统，要求达到“简单应用”层次。第2章命题逻辑的推理理论第2章命题逻辑的推理理论重点：1.命题公式的主范式表示及相互转换，2.使用P规则、T规则、CP规则进行命题推理。难点：命题推理及其应用2.1范式范式的概念：命题变项及其否定统称作文字。仅有有限个文字构成的析取式称作简单析取式。仅有有限个文字构成的合取式称作简单合取式。p,q等为一个文字构成简单析取式，pp，pq等为2个文字构成的简单析取式，pqr,pqr等为3个文字构成的简单析取式。p,q等为一个文字构成的简单合取式，pp，pq等为2个文字构成的简单合取式,pqr,ppq等为3个文字构成的简单合取式。2.1范式应该注意，一个文字既是简单析取式，又是简单合取式。为方便起见，有时用A1,A2,As表示s个简单析取式或s个简单合取式。简单合取式的重要特点是它的成真指派很容易找到，且它的永假性也容易判定一个简单合取式是永假的，当且仅当它至少含一个变元及其否定2.1范式定理：（1）一个简单析取式是重言式当且仅当它同时含某个命题变项及它的否定式。（2）一个简单合取式是矛盾式当且仅当它同时含有某个命题变项及它的否定式。证明：设Ai是含n个文字的简单析取式，若Ai中既含有某个命题变项pj，又含有它的否定式pj，由交换律、排中律和零律可知，Ai为重言式。反之，若Ai为重言式，则它必同时含某个命题变项及它的否定式，否则，若将Ai中的不带否定号的命题变项都取0，带否定号的命题变项都取1，此赋值为Ai的成假赋值，这与Ai是重言式相矛盾。类似的讨论可知，若Ai是含n个命题变项的简单合取式，且Ai为矛盾式，则Ai中必同时含有某个命题变项及它的否定式，反之亦然。2.1范式如：pp，ppr都是重言式。pq，pqr都不是重言式2.1范式小项：n个命题变员的合取式，称作布尔合取或小项，其中每个变元与它的否定不能同时存在，但两者之一必须出现且仅出现一次。两个命题变元P和Q，其小项为PQ，PQ，PQ，PQ2.1范式2.1范式2.1范式三个命题变元的大项：M000=PQRM001=PQRM010=PQRM011=PQRM100=PQRM101=PQRM110=PQRM111=PQR或记为Mi(i=0，1，2，3，4，5，6，7)。2.2主范式主析取范式：对于给定的命题公式，如果有一个等价公式，它仅由小项的析取所组成，则该等价式称作原式的主析取范式。主合取范式：对于给定的命题公式，如果有一个等价公式，它仅由大项的合取所组成，则该等价式称作原式的主合取范式。2.2主范式真值表法：在真值表中，一个公式的真值为T的指派所对应的小项的析取，即为此公式主析取范式。在真值表中，一个公式的真值为F的指派所对应的大项的合取，即为此公式主合取范式。除了真值表法外，还可以用等值演算法求主析取范式和主合取范式。2.2主范式2.2主范式例写出公式(pq)(qp)的主析取范式解：方法一，真值表法：列出真值表从真值表看出，真值为1的小项有m00，m01，m10三项，故原式的析取范式为m00m01m10=(pq)(pq)(pq)2.2主范式2.2主范式例求pqr的主合取范式。解：方法一，真值表法：列出真值表:PqrPqpqr00000001010100001101100001010111011111112.2主范式从表中可以看出，真值为F所对应的大项编码有M000，M010，M100，所以与原式等价的主合取范式为M000M010M100=(0,2,4)2.2主范式方法二，等值演算法：pqr(pq)r(pr)(qr)(p(qq)r)(pp)qr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)(pqr)M000M010M100M0M2M4=(0,2,4)2.2主范式主范式之间的关系：设命题公式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)。2.2主范式从A的主析取范式求其主合取范式步骤为：（1）求出A的主析取范式中未包含小项的下标。（2）把（1）中求出的“下标”写成对应大项。（3）做（2）中写成的大项合取，即为A的主合取范式。例(PQ)Q主析取范式(1,3)=m01m11(PQ)Q主合取范式(0,2)=M00M102.3自然推理系统（1）真值表法（2）主范式方法及等值演算法（3）构造论证法（4）间接证明法这部分常出大题考查2.3自然推理系统（1）等值公式表整理归纳(P.48)2.3自然推理系统（2）推理定律表整理归纳(P.32或P.48-P.49)2.3自然推理系统（3）构造论证法常用的推理规则有：前提引入规则：在证明的任何步骤上，都可以引入前提，简称P规则。结论引入规则：在证明的任何步骤上，所证明的结论都可作为后续证明的前提，称为T规则。置换规则：在证明的任何步骤上，命题公式中的任何子命题公式都可以用与之等值的命题公式置换。亦记为T规则。2.3自然推理系统例证明：(PQ)(PR)(QS)SR。证明：（1）PQP（步骤1，引用P规则得PQ）（2）PQT.（1）E（步骤2，由（1），根据等价公式表E，引用T规则得PQ）（3）QSP（4）PST.（2）（3）I（步骤4，由（2）（3），根据蕴含公式表I，引用T规则得PS）2.3自然推理系统（5）SPT.（4）E（6）PRP（7）SRT.（5）（6）I（8）SRT.（7）E（步骤8，SR是有效结论）2.3自然推理系统（4）间接证明法：包括附加前提和CP规则法。要注意的是，这两种方法都要引入附加的前提，但是附加前提的引入是有目的的，不是随心所欲的。附加前提。引入结论的否定作为前提，导致最后推出F，则得证。这实际上是一种反证法，有的书上也叫反证推理规则。CP规则。常用于结论为蕴涵式情况。引入结论的前件作为前提，最后推出后件。等价证明考核内容与考核要求1.谓词的概念与表示，要求达到“领会”层次。理解谓词、个体词、命题函数的概念;能使用谓词表示相关命题。2.量词与合式公式，要求达到“识记”层次。理解全称量词、存在量词的概念，能够使用谓词与恰当的量词表示命题；理解合式公式并能够正确判别，能指明合式公式中的指导变元、量词的辖域、个体变元的自由出现和约束出现等；能使用约束变元改名规则和自由变元代入规则改写命题公式。第3章谓词逻辑考核内容与考核要求3.谓词演算的等价式与蕴含式，要求达到“领会”层次。理解对谓词公式赋值的含义，掌握谓词演算的规则；熟记谓词演算的等值式与蕴含式。4.前束范式，要求达到“简单应用”层次。理解前束范式的概念；能够将所给公式变换为等值的前束范式。5.谓词演算的推理理论，要求达到“简单应用”层次。掌握谓词演算的推理理论；能够进行正确的构造推理证明。第3章谓词逻辑第3章谓词逻辑重点：1.使用谓词及量词表示相关命题并能确定量词的辖域，2.能将带量词的公式变换为等价的前束范式，3.能进行正确的谓词演算推理。难点：1.带量词的公式变换，即将公式变换为等价的前束范式，2.能够进行谓词演算推理。学习指导p谓词演算引进了客体和谓词概念，并讨论谓词公式中引入量词及其辖域的概念，为此，谓词逻辑能处理更为复杂的问题。p本章的学习主要是在掌握命题逻辑的基础上，理解个体，谓词，量词等概念，学会将命题进一步用谓词逻辑表示；在熟记谓词逻辑中的等价式和蕴含式的基础上，将一个谓词演算公式化为与它等价的前束范式；并能运用US、UG、ES、EG等规则，进行谓词演算的推理。第3章谓词逻辑3.1谓词的概念与表示一、谓词的概念与表示客体（个体）和谓词例如，王强是个大学生；其中“是个大学生”是谓词；而“王强”是客体（主语、宾语）。个体变项的取值范围称为个体域(或称论域)。3.1谓词的概念与表示全总个体域。当我们讨论问题时，作为讨论对象的非空集合就称为论域（个体域），论域中的元素就是我们要讨论的对象，这就是个体。在简单命题中，表示一个个体性质或多个个体之间关系的词称为谓词。谓词和个体一起，就构成了简单命题中的主谓结构。由一个谓词，一些个体变元组成的表达式简称为谓词变项或称为命题函数。3.1谓词的概念与表示命题函数不是命题，只有命题函数中的变元都取为特定具体的个体时，才是确定的命题。例如L(x,y)：x小于y。若x，y为有理数，则L(x,y)为谓词变项即命题函数；若x，y取3，5，则L(3,5)是谓词常项，即L(3,5)是命题。3.1谓词的概念与表示谓词变项中，个体变员的数目称为谓词变项的元数。如P(x1,x2,xn)为n元谓词，但是当n元谓词中某一个体变项取作常量时，即P(a,x1,x2,xn-1)，其中a是常量，x1，x2，xn-1为变项，则上式成为n1元谓词。不带个体变项的谓词称为0元谓词。3.1谓词的概念与表示用谓词符号化命题：先把语句分析成几个简单命题与联结词的联结；然后对每个简单命题，用大写字母表示谓词，小写字母表示客体；最后把已符号化的简单命题用正确的联结词联结起来。例如，用0元谓词符号化下述命题。如果3小于4，且4小于5，则3小于5。解：设L(x,y)：x小于yL(3，4)L(4，5)L(3，5)3.1谓词的概念与表示3.2量词与合式公式二、合式公式对命题符号化用量词时，首先要考虑论域的情况。用来指明论域的谓词，称为特性谓词。如果事先没有明确出个体域，则认为个体域是全总个体域，才产生特性谓词；如果事先规定了个体域，则可免去特性谓词。在全称量词中，特性谓词是条件式的前件；在存在量词中，特性谓词后跟一个合取项。3.2量词与合式公式例2有些自然数是偶数。在例1，例2中，N(x)和S(x)等都是特性谓词例1每个自然数都是实数。3.2量词与合式公式形如A(x1,x2,xn)称作谓词的原子公式。为由一个谓词，一些个体变元组成的表达式称为原子命题函数。由一个或几个原子命题函数以及逻辑联结词组合而成表达式称为复合命题函数。3.2量词与合式公式3.2量词与合式公式3.2量词与合式公式3.2量词与合式公式在谓词合式公式中，有的个体变元既可以是约束出现，又可以是自由出现，为了避免混淆采用下面两个改名规则：约束变元改名规则：将量词辖域中，某个约束出现的个体变元及相应指导变元改成本辖域中未曾出现过的个体变元，其余不变。自由变元代入规则：对某自由出现的个体变元可用个体常元或用在原子公式中和所有个体变元不同的个体变元去代入，且处处代入。3.2量词与合式公式3.2量词与合式公式3.3谓词演算的等价式与蕴含式3.3谓词演算的等价式与蕴含式3.3谓词演算的等价式与蕴含式3.3谓词演算的等价式与蕴含式此定理可在有限论域D=a1,a2,an上证明，参考教材P.603.3谓词演算的等价式与蕴含式常见谓词演算的等值式与蕴含式（P.61）3.4前束范式3.4前束范式前束范式的转换步骤：先将蕴含或等价联结词转换；利用量词否定等值式，把否定深入到命题变元和谓词公式前面；换名或替换利用量词辖域的收缩与扩张等值式，把量词提到前面。3.4前束范式求下列公式的前束公式3.5谓词演算的推理理论谓词演算的推理理论谓词演算的推理方法，可以看作是命题演算推理方法的扩张。命题演算中的推理规则如P，T和CP规则等亦可在谓词演算推理理论中应用。但是在谓词推理中，必须有消去和添加量词的规则。加入或消去量词时，量词必须在公式的最前端全称量词消去规则US全称量词引入规则UG存在量词消去规则ES存在量词引入规则EG3.5谓词演算的推理理论如果同时有全称，存在量词，则先消存在量词，再消全称量词，即先应用ES规则，再应用US规则。因为ES中c是论域中的某些个体，而US中c是全部个体.推理过程中综合使用P,T,(CP),ES,US,EG,UG.例专业委员会成员都是教授，并且是计算机设计师，有些成员是资深专家，所以有些成员是计算机设计师，且是资深专家。请用谓词推理理论证明上述推理。3.5谓词演算的推理理论考核内容与考核要求1.集合的基本概念，要求达到“领会”层次。集合的概念，了解可数集与不可数集及基数的比较;集合的表示法，包括列举法、描述法及图示法，了解子集的概念，能判别集合之间的相等、包含等关系。2.集合的运算，要求达到“简单应用”层次。集合的基本运算，能正确计算集合的并、交、补及差，能正确求出集合的幂，领会集合运算满足的性质；集合运算的恒等式，掌握集合运算的相关公式，能运用集合的运算定律进行集合恒等式的证明。第4章集合考核内容与考核要求3.有序对与笛卡尔积，要求达到“简单应用”层次。有序对，掌握有序对、有序n元组的概念，掌握有序对的集合性定义及相关定理；笛卡尔积，掌握笛卡尔积的定义及性质。第4章集合第4章集合重点：1.集合的表示，2.集合的幂集及集合的运算，3.集合恒等式的证明。难点：1.集合的运算，2.集合恒等式的证明。4.1集合的基本概念集合的概念集合是指具有某种特定性质的具体的或抽象的对象汇总而成的集体。其中，构成集合的这些对象则称为该集合的元素，例如，全中国人的集合，它的元素就是每一个中国人。通常用大写字母如A,B,S,T,.表示集合，而用小写字母如a,b,x,y,.表示集合的元素。若x是集合S的元素，则称x属于S，记为xS。若y不是集合S的元素，则称y不属于S，记为y S。4.1集合的基本概念4.1集合的基本概念4.1集合的基本概念集合的表示法：图像法，又称韦恩图法、韦氏图法，是一种利用二维平面上的点集表示集合的方法。一般用平面上的矩形或圆形表示一个集合，是集合的一种直观的图形表示法，符号法，有些集合可以用一些特殊符号表示4.1集合的基本概念常用符号表示的集合N：非负整数集合或自然数集合0,1,2,3,N*或N+：正整数集合1,2,3,Z：整数集合,-1,0,1,Q：有理数集合Q+：正有理数集合Q-：负有理数集合R：实数集合(包括有理数和无理数）R+：正实数集合R-：负实数集合C：复数集合：空集（不含有任何元素的集合）4.1集合的基本概念空集有一类特殊的集合，它不包含任何元素，如x|xRx+1=0，称之为空集，记为。空集是个特殊的集合它有2个特点：空集 是任意一个非空集合的真子集。空集是任何一个集合的子集。4.1集合的基本概念4.1集合的基本概念全集在一定范围内，如果所有集合均为某一集合的子集，则称该集合为全集，一般记为E或U。全集概念相当于论域，例如考虑某大学的系或班级的学生时，该大学的全体学生组成了全集。4.1集合的基本概念4.2集合的运算集合的基本运算交集定义：由属于A且属于B的相同元素组成的集合，记作AB（或BA），读作“A交B”（或“B交A”），即AB=x|xA,且xB，如右图所示。注意交集越交越少。若A包含B，则AB=B，AB=A。并集定义：由所有属于集合A或属于集合B的元素所组成的集合，记作AB（或BA），读作“A并B”（或“B并A”），即AB=x|xA,或xB，如右图所示。注意并集越并越多，这与交集的情况正相反。4.2集合的运算集合的基本运算补集补集又可分为相对补集（差集）和绝对补集。相对补集定义：由属于A而不属于B的元素组成的集合，称为B关于A的相对补集，记作A-B或AB，即A-B=x|xA，且x B。绝对补集定义：A关于全集合U的相对补集称作A的绝对补集，记作A或 u（A）或A。有U=；=U。4.2集合的运算集合运算的恒等式（P.71P.72)幂等律结合律交换律分配律包含律同一律零律排中律矛盾律吸收律德摩根律双重否定律4.2集合的运算4.3有序对与笛卡尔积有序对（序偶）：两个元素x和y按一定顺序组成的序列，称为序偶或二元组，记作或(x，y)。其中x是该序偶的第一元素，y是该序偶的第二元素。序偶与两个元素的集合不同，对集合来说，不要规定元素的次序，例如x，y和y，x是两个相同的集合，而对序偶来说，元素的次序是重要的，当xy时，例如：二维平面上的一个点的坐标(x,y)。4.3有序对与笛卡尔积笛卡尔积：设A，B为集合，如果序偶的用第一元素x是A的元素，第二元素y是B的元素，所有这样的序偶组成的集合，叫做A和B的笛卡尔积，记作AB例如，A=0，1，2，B=a，b，AB=，BA=，。ABBA。4.3有序对与笛卡尔积注意n元组是个序偶，它的第一元素本身也是序偶，是一个n-1元组。两个集合的笛卡儿积不服从交换律，三个集合的笛卡儿积不服从结合律。集合(AB)C的元素都是三元组，而集合A(BC)的元素不符合三元组的定义。第5章关系与函数考核内容与考核要求1.关系与关系的性质，要求达到“领会”层次。关系的定义及表示，掌握关系的定义及三种表示方法，掌握关系的定义域与值域；关系的性质，理解关系的性质，包括自反性、对称性、传递性、反自反性和反对称性，能进行正确的判断。2.关系的运算，要求达到“领会”层次。关系的常规运算，能正确进行关系的运算；复合运算，理解复合关系概念，能正确进行关系的复合运算；关系矩阵的布尔运算，理解关系矩阵的定义，熟练进行关系矩阵的计算；关系的闭包，理解关系的自反、对称、传递闭包，能正确进行计算、表示及判别。第5章关系与函数考核内容与考核要求3.等价关系与序关系，要求达到“简单应用”层次。等价关系，掌握等价关系、等价类、划分等概念，能对给定的关系进行正确判别；序关系，掌握偏序关系、拟序关系及全序关系，能正确画出表示偏序关系的哈斯图，能给定的关系正确判断，正确求出偏序关系中的极大（小）元，最大（小）元。4.函数的概念，要求达到“领会”层次。函数的概念，掌握函数的概念，能正确判别所给关系是否为函数，是否是单射、满射和双射等；复合函数，理解复合函数概念，能正确计算函数的复合。第5章关系与函数重点1.集合上的关系与运算2.集合上的函数与运算难点1.等价关系的判定与证明2.相容关系的判定与证明3.序关系的判定与证明5.1关系与关系的性质关系设A，B是任意两个集合，AB的子集R称为从A到B的二元关系。属于R的序偶，称a与b有关系R，记作aRb；不属于R的序偶，则称a与b没有关系R，记作aRb。对集合A，可构成A到A的二元关系R，或称R是集合A上的关系。关系与笛卡尔积是不同的。关系可能在两个集合的部分元素之间有定义，没有定义的元素之间不存在关系。而笛卡尔积是两个集合全部元素之间都有定义。5.1关系与关系的性质例设B=1，2，3，6，求B上整除关系。5.1关系与关系的性质5.1关系与关系的性质5.1关系与关系的性质前域也称定义域5.1关系与关系的性质例设A=a，b，c，e，B=a，b，d，在AB上关系R定义为：R=，。求：domR，ranR，fldR。解：domR=a，b，c，ranR=b，d，fldR=a，b，c，d。5.1关系与关系的性质5.1关系与关系的性质解集合表示：5.1关系与关系的性质解关系矩阵表示：5.1关系与关系的性质解关系图表示：5.1关系与关系的性质5.1关系与关系的性质集合X上二元关系R的性质自反性反自反性5.1关系与关系的性质集合X上二元关系R的性质对称性反对称性5.1关系与关系的性质集合X上二元关系R的性质传递性5.1关系与关系的性质注意不是自反的关系，并不一定是反自反的。例如集合A=1，2，3，A上的关系R=,，它既不是自反的，也不是反自反的。不是对称的关系，并非就是反对称的。例如R=,既不是对称的，也不是反对称的；但是有的关系既是对称的，又是反对称的，例如R=,。5.1关系与关系的性质常见关系的性质汇总表5.2关系的运算关系的常规运算若Z和S是从集合X到Y的两个关系，则Z，S的并、交、补、差仍是X到Y的关系。因为关系也是集合，它的元素是序偶，所以集合的各种运算都可以应用于同一域上的关系运算。5.2关系的运算例设集合X=a，b，c，集合Y=x，y，z，R是集合X到集合Y的关系R=，求从集合Y到集合X的逆关系5.2关系的运算5.2关系的运算5.2关系的运算5.2关系的运算5.2关系的运算5.2关系的运算其中,5.2关系的运算5.2关系的运算关系的闭包运算关系的闭包运算是将已知的关系R，增加必要的序偶组成新的关系R，使R包含R并且具备一定的性质（如自反性、对称性、传递性等），而且添加的序偶要尽可能少。5.2关系的运算5.2关系的运算关系的闭包运算定理设R为非空有穷集合A上的二元关系，（1）r(R)=RIA（2）s(R)=RR-1（3）t(R)=RR2Rn，其中n是集合A中元素的数目.例 设A=a,b,c，给定A上二元关系R=,，求 r(R)，s(R)，t(R)5.2关系的运算为了求出t(R)，先写出：5.2关系的运算5.3等价关系与序关系相容关系设R是集合A上的关系，若R是自反的和对称的，则称R是A上的相容关系。相容关系的关系矩阵是主对角线元素全为1的对称矩阵.5.3等价关系与序关系5.3等价关系与序关系5.3等价关系与序关系例设集合A=1，2，3中的一个覆盖为B=1，2，2，3，求由B确定的相容关系。5.3等价关系与序关系等价关系设R为集合A上的一个关系，若R是自反的、对称的和传递的，则R是等价关系。5.3等价关系与序关系例在整数集Z上同余模4的集合，可以分为4类：在整数集中以模4同余关系的数集只有上述四类，就是Z的一种划分。5.3等价关系与序关系例设R是模4同余关系，则0R=-4R=4R=8R=，1R=-7R=-3R=5R=，2R=-6R=-2R=6R=，3R=-5R=-1R=7R=。5.3等价关系与序关系5.3等价关系与序关系集合A上的任一等价关系R可以唯一确定A上的一个划分：商集A/R就是这个划分；任一划分，可以唯一地确定A上的等价关系：定义一个关系R，aRb当且仅当a，b在同一分块中，R就是这个等价关系。即集合A上给出一个划分和给出一个等价关系是一一对应的。5.3等价关系与序关系相容关系和等价关系区别与联系相容关系和覆盖是自反的、对称的集合中的相容关系能构成该集合的覆盖相容关系不一定是等价关系覆盖不一定是划分等价关系和划分是自反的、对称的和传递的集合中的等价关系能构成该集合的划分等价关系一定是相容关系划分一定是覆盖5.3等价关系与序关系5.3等价关系与序关系5.3等价关系与序关系5.3等价关系与序关系解：m=12其因子集合A=1，2，3，4，6，12，=，5.3等价关系与序关系COVA=，。哈斯图如下5.3等价关系与序关系整除关系的最小元是1，最大元是12;如