交大离散数学复习课.ppt

复习,重点章节：第1、2、3、5章选择复习章节：第4、7、8章,考试形式,闭卷，90分钟题型：选择题（30分，152分）计算（50分）证明（20分）,考题示例,选择题：1、设R是X=1,2,3,4上的关系，x,yX，如果xy，则(x,y)R。R=(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)，则关系R是（）A)自反的、B)传递的、C)等价的D)对称的2、设B是不含变元x的公式，谓词公式(x)(A(x)B)等价于（）A)(x)(A(x)BB)(x)(A(x)BC)A(x)BD)(x)A(x)(x)B3.设G是连通简单平面图，G中有11个顶点5个面，则G中的边是（）A)10B)12C)16D)14,计算题1假设p为真，q为假，并且r为真，求下列表达式的真值：（1）pqr（2）pqr(a)用ABCDE五个字母可以组成多少个不重复的长度为4的字符串？(a)中有多少个字符串以字母B开头？,考题示例,知识点提示,1逻辑与证明,6,1.2命题,命题是一个陈述句，或真或假，不可以既真又假。命题是逻辑的基本构成单元下列句子(a)(e)哪个为真，哪个为假（不能既真又假）(a)能整除7的正整数只有1和7本身。(b)多伦多是加拿大的首都。(c)对于每个正整数n，存在一个大于n的素数。(d)地球是宇宙中惟一存在生命的星球。(e)买两张星期五去“大剧院”音乐会的票。,(a)真(b)假(c)真(d)不知真假，但一定是非真即假。因此是命题(e)不是命题,7,真值表,复合命题的真值可以由真值表来表达。用T代表真，F代表假。,复合命题pq，pq的真值由下列真值表,8,p:天正在下雨q:天很冷pq:天正在下雨并且天很冷pq:天正在下雨或者天很冷,例如：命题“天正在下雨”与“天很冷”可以连接成单一命题形式“天正在下雨与天很冷”。“与”和“或”的形式化定义。,9,9,条件命题的真值表,10,例,考察：“如果今天天晴，那么我们将去海滩”只有当今天天晴，而我们不去海滩时，这个命题为假，否则上述命题成立。考察：“如果今天是星期五，那么2+3=5”该命题总是成立，因为2+3=5总是为真考察“如果今天是星期五，那么2+3=6”该命题当今天不是星期五时，成立,11,1.1.4逻辑运算符的优先级,优先级:()假设：p真q假r真，给出下面每个命题的真值(pq)r(pq)rp(qr)p(qr),1.1.5复合命题的真值表,构造真值表(pq)(pq),12,1.1.6翻译语句形式化表示,“只有你主修计算机科学或不是新生，才可以从校园网访问因特网”设：a:你可以从校园网访问因特网c:你主修计算机科学f:你是个新生问题：该语句的等价说法（）：A“如果你主修计算机科学，或者你不是新生，那么你可以从校园网访问因特网”B“如果你可以从校园网访问因特网，那么你主修了计算机科学，或者你不是新生”所以，形式化表示为：a(cf),13,证明命题:p(qr)与(pq)(pr)等价,14,1.2.3德摩根定律的运用,用德摩根律表达“麦克有一部手机和一台电脑”的否定解：p麦克有一部手机，q麦克有一台电脑那么原命题表示为：pq则其否定（pq）等价于pq即：“麦克没有一部手机或没有一台电脑”用德摩根律表达“John或者Jessi将去看电影”的否定解：p:John去看电影，q：Jessi去看电影那么原命题表示为：pq则其否定（pq）等价于pq即：“John和Jessi都不去看电影”,15,16,1.3.3量词,量化：谓词在一定范围内的取值谓词演算：处理谓词和量词的逻辑领域全称量词：P(x)的全称量化表示语句“P(x)对x在其论域中的所有值都为真”存在量词：P(x)的存在量化表示语句“论域中至少有一个值满足P(x)为真”,17,例：P(x)表示语句“x20”，论域为不超过4的正整数，xP(x)的真值是什么？解：论域为1，2，3，4，P(1),P(2),P(3)为真。,17,例P(x)表示语句“x20”，论域为不超过4的正整数，则：xP(x)的真值是什么？解：xP(x)就是合取式P(1)P(2)P(3)P(4)由于P(4)为假，所以xP(x)为假,18,1.3.5约束论域量词,x0)x(x0)y0(y30)y(y0y30)全称量词的约束等价于一个条件语句的全称量化z0(z2=2)z(z0z2=2)存在量词的约束等价于一个合取的存在量化,19,1.3.8涉及量词的逻辑等价,定义3：涉及量词的语句是逻辑等价的，当且仅当无论什么谓词代入这个语句，也不论用哪个个体论域于这些命题函数里的变量上，它们都有相同的真值。x(P(x)Q(x)xP(x)xQ(x)x(P(x)Q(x)xP(x)xQ(x)x(P(x)Q(x)与xP(x)xQ(x)不逻辑等价x(P(x)Q(x)与xP(x)xQ(x)不逻辑等价,19,1.3.9否定量化词表达式,考虑语句的否定：“班里每个学生都学过微积分”即xP(x)其中P(x)：x学过离散数学其否定：“并非班里每个学生都学过微积分”也就是：“班里有学生没有学过微积分”，即xP(x)等价关系：xP(x)xP(x),20,21,1.4.3将数学语句翻译成嵌套量词语句,翻译语句“两个正整数的和是正数”xy(x0)(y0)(x+y0)嵌套语句翻译成数学语句：考虑命题xy(xy0)论域为实数域。这个命题为真，因为对每个实数x，至少存在一个y（可选取y=-x），使x+y=0为真。这个命题用文字表达为：对每个实数x，存在一个实数y，可使x与y的和为零。,22,例,确定论证pq,p/q是否有效,注意：只要前提pq和p为真，结论q就为真。所以论证过程是有效的。,23,1.5.3命题逻辑的推理规则,假言推理/分离定律,合取,拒取,附加,化简,假设段论,析取段论,qpq_p,ppq_q,Pq_pq,pq_p,p_pq,pqqr_pr,pqp_q,pqpr_qr,消解,例,给出定理“若3n+2是奇数，则n是奇数”的证明若用直接法证明，设3n+2是奇数，则存在k使得3n+2=2k+1能否从中得出n是奇数的结论？反正法：第一步：假设条件语句结论是假，即“3n+2是奇数，n不是奇数”，那么n是偶数。即：n=2k+1,第二步：根据上面的假设，则3n+2=3(2k)+2=6k+2=2(3k+1),也就是得出3n+2是偶数，这与原命题的假设“3n+2”是奇数”矛盾所以原来的条件语句为真，定理得证。,24,反例证明法,反驳xP(x)只需在论域内找到一个x，使P(x)为假。例1.5.19命题“n(2n+1)是素数”为假。反例为n3时，239，不是素数,25,2.集合、函数、数列与求和,2.1.2幂集,如X是Y的子集但X不等于Y,则X是Y的一个真子集空集是任何集合的子集定义7：集合X的所有子集的集合，称为X的幂集，用P(X)表示,28,28,例,如A=a,b,cP(A)的成员：,a,b,c,a,b,a,c,b,c,a,b,cA=3，P(A)=23=8,29,2.1.3笛卡儿积,一个由两个元素组成的有序对(或序偶)，写为(a,b)(a,b)=(c,d)当且仅当a=c,b=d.定义8：有序n元组（a1,a2,an）是以a1为第一个元素，a2为第二个元素，an为第n个元素的有序组定义9：X,Y集合，XY称为X和Y的笛卡儿积，是所有有序对(x,y)的集合，其中xX,yY。即XY=(x,y)|xX,yY,30,例,X=1,2,3Y=a,bXY=1,a,1,b,2,a,2,b,3,a,3,bYX=a,1,a,2,a,3,b,1,b,2,b,3XX=1,1,1,2,1,3,2,1,2,2,2,3,3,1,3,2,3,3YY=a,a,a,b,b,a,b,b,31,Venn图：关于集合的形象化表示,1,2,4,3,A,B,1,2,4,3,A,B,32,划分,一个由集合X的非空子集的整体组成的S，如X的每个元素都只属于S的某一个元素，S就称为X的一个划分。,例：集合X=1,2,3,4,5,6,7,8S=1,4,5,2,6,3,7,8S是X的一个划分,2.3.2一对一函数和映上函数,单射,满射函数,映上函数,一对一的,例,证明从正整数集合到正整数集合的函数f(n)=2n+1是一对一的。张明：必须证明对所有正整数n1和n2，如果f(n1)=f(n2)，则n1=n2。先假定f(n1)=f(n2)，依据f的定义，将这个等式变形为2n1+1=2n2+1将两边同时减1，然后同除以2，可得n1=n2所以，f是一对一的。,例,定义序列s为sn=2n+43n，n0(a)求s0。(b)求s1。(c)求si的公式。(d)求sn-1的公式。(e)求sn-2的公式。(f)证明序列sn满足sn=5sn-1-6sn-2，对所有n2,3、计数,乘法原理,乘积法则：假定一个过程可以被分解成两个任务，完成第一个任务有n1种方式，在第一个任务完成之后有n2种方式完成第二个任务，那么完成这个过程有n1n2种方式。如果一种活动由连续t步组成，第一步有n1种方法，第二步有n2种方法，.第t步有nt种方法，那么不同的活动数目有n1*n2*.*nt,当一活动由连续几步组成时，把每一步的方法数乘起来.,例题讲解,例1用一个字母和一个不超过100的正整数给礼堂的座位编号。那么不同编号的座位最多有多少？解：给一个座位编号的过程分两个任务：从26个字母中选取一个字母；从100个正整数中选取一个整数。根据乘法原理，座位的编号方式可以有：26*100=2600种例2有多少个不同的7位二进制串？解：7位二进制串的每一位都可以有两种选择，因此有27,例,如果不允许重复，用ABCDE可以组成多少长度为4的字符串？其中有多少是以B开头的？1*4*3*2=24,例,如果不允许重复，用ABCDE可以组成多少长度为4的字符串？其中有多少不是以B开头的？4*4*3*2=96120-24,加法原理,假设X1,.,Xt是集合且第i个集合有ni个元素，如果X1,.,Xt两两不相交，则可以从X1或X2或.Xt选择元素的可能性有n1+.+nt,当被计数的元素可以被分解到不相交的子集时，可将每个子集的元素数相加得到总的元素数.,例,由A、B、C、D、E、F6人委员会要选一个主席，一个秘书，一个书记有多少种选法？如果A或B必须是主席，有多少种？如果E必须任3职之一，有多少种？如果D和F必须任职，有多少种？,3.2.1鸽巢原理,定理1：如果k+1个或更多的物体放入k个盒子，那么至少有一个盒子包含了2个或更多的物体第一种形式如果n只鸽子飞入k个巢且kn,则某些巢至少有两只鸽子。解题关键：鸽子？鸽巢？,一组367个人中一定至少有2个人有相同的生日。有366个不同的生日。（367人鸽子，366个生日鸽巢）27个英文单词中一定至少有2个单词以同一个字母开始。26个英文字母如果考试给分从0100，班上必须有多少学生才能保证这次期末考试中至少有2个学生得到相同的分数？101个分数，至少102个学生,3.2.3巧妙使用鸽巢原理,例：在30天的一个月里，某棒球队一天至少打一场比赛，但至多打45场。证明一定有连续的若干天内这个对恰好打了14场。解：令aj是第j天之前（包括第j天）所打的场数，则a1,a2,a30是严格递增序列，且1aj45那么a1+14,a2+14,a30+14也是严格递增的，且14aj+1459则：在1，59的60个正整数a1,a2,a30，a1+14,a2+14,a30+14根据鸽巢原理，必然有两个正整数相等。aj+14=ai也就是说：从第j+1天到第i天，恰好打了14场,3.3.2排列,n个不同的元素x1,.xn的一个排列就是这n个元素的一个次序。定理：具有n个不同元素的集合的r排列是P(n,r)=n(n-1)(n-2)(n-r+1)推论：如果n和r都是整数，且1rn，则,例,字母ABCDEF中有多少个包含DEF的排列？,A,B,C,DEF,例,字母ABCDEF中有多少个包含DEF任意顺序的排列？,A,B,C,DEF,3！*4！,3.3.3组合,不考虑顺序的对象的选取叫做组合,例,5个学生想和校长谈奖学金的事，校长办公室安排3个人去谈，问有多少种方法从5选3？C(5，3)=10,3.5广义的排列组合,有重复元素允许重复元素多重集的排列组合问题,3.5.2有重复的排列,当元素允许重复时，使用乘积法则很容易计数排列数例：用英文字母可以构成多少个r位字符串26r定理：具有n个物体的集合允许重复的r排列数是nr,3.5.3有重复的组合,例：考虑3本书(计算机，数学、历史)，每本书图书馆有6本拷贝，选择6本书有多少种可能？,分析计算机|数学|历史*|*|*计算机|数学|历史|*|*8个元素中6个*2个|的排列数,例,（1）满足x1+x2+x3+x4=29的非负整数解有多少种？解：每一个解相当于从4类元素中选取29个，其中从第i类元素中选取xi个，i=1,2,3,4。29个1，4-1个|，C(29+4-1，4-1),可辨别的物体可辨别的盒子例：有多少种方式把52张标准的扑克牌发给4个人使得每人5张牌,不可辨物体可辨的盒子例：将10个相同的球放入8个可辨别的桶，共有多少种方法？解：从8个元素的集合中取出的10组合的个数,可辨别的物体不可辨别的盒子例：将4个不同的雇员安排在3间不可辨别的办公室，有多少种方式？其中每间办公室可以安排任意个数的雇员。解：C(4,4)+C(4,3)+C(4,2)+C(3,1),不可辨别的物体不可辨别的盒子例：将同一本书的6个副本放到4个相同的盒子里，其中每个盒子都能放下6个副本,5、高级计数问题,60,4.1递推关系基础,以5开始给定了某一项，+3得到下一项,581114172023,a1=5an=an-1+3n2a2=a1+3=5+3=8a3=a2+3=8+3=11递推关系是由数列第n项前的若干项确定第n项，并由此确定数列。,例,确定an是否为递推关系an=2an-1-an-2,n=2,3,4，的解，其中an=3n,n是非负整数。解：2an-1-an-2=2*3(n-1)-3(n-2)=3n=an若an=2n2an-1-an-2=2*2n-1-2n-2=2n-2n-2an若an=5，2an-1-an-2=2*5-5=5=an,61,62,例,投资$1000,利息12%An第n年底的总金额，AnAn=An-1+(0.12)An-1=1.12An-1n1A0=1000A3=1.12A2=1.12*1.12A1=1.12*1.12*1.12A0=1.123(1000)An=1.12An-1=1.12n(1000)通项公式,63,4.2求解线性递推关系,数列a0,a1,.的通项公式an代入法定义：一个k阶常系数线性齐次递推关系：an=c1an-1+c2an-2+ckan-k其中c1,c2,ck是实数，ck0例：cn=1.12cn-1是一阶线性齐次递推关系fn=fn-1+fn-2是二阶线性齐次递推关系an=2an-5是5阶线性齐次递推关系an=an-1+an-12不是线性的；Hn=2Hn-1+1不是齐次的。,求递推关系的显示表达式an=an-1+2an-2,其中a0=2，a1=7，解：递推关系的特征方程是：r2-r-2=0r1=2,r2=-1因此an=b2n+d(-1)n根据初始条件可得：b+d=22b-d=7得出b=3,d=-1因此an=32n-(-1)n,64,65,an=5an-1-6an-2其中a0=7a1=16,解：递推关系的特征方程为：t2-5t+6=0t=2,t=3an=b2n+d3n是解根据初始条件：7=a0=b20+d30=b+d16=a1=b21+d31=2b+3db=5,d=2因此：an=5*2n+2*3n,66,例,鹿群n=0:200n=1:220从n-1到n的增长头数为n-2到n-1的增长头数的两倍，写出递推关系，求通项公式。,解：设dn为时间n时数目d0=200，d1=220dn-dn-1=2(dn-1-dn-2)递推关系：dn=3dn-1-2dn-2t2-3t+2=0r1=1，r2=2dn=br1n+dr2n=b1n+d2n200=d0=b+d220=d1=b+2db=180,d=20,dn=180+20*2n,4.5.2容斥原理,|AB|=|A|+|B|-|AB|例：一个离散数学班包括25个计算机专业的学生，13个数学专业的学生，8个同时主修计算机和数学两个专业的学生。如果每个学生主修数学专业、计算机专业或者同时主修这两个专业，那么班里有多少个学生解：25+13-8=30,67,5关系,5.1.4关系的性质,集合X上的关系R，如果对于每个xX都有(x,x)R，则称R是自反的。例7：下面是集合1，2，3，4上的关系R1=(1,1),(1,2),(2,1),(2,2),(3,4),(4,1),(4,4)R2=(1,1),(1,2),(2,1)R3=(1,1),(1,2),(1,4),(2,1),(2,2),(3,3),(4,1),(4,4)R4=(2,1),(3,1),(3,2),(4,1),(4,2),(4,3)R5=(1,1),(1,2),(1,3),(1,4),(2,2),(2,3),(2,4),(3,3),(3,4),(4,4)R6=(3,4)其中R3,R5是自反的。,对称关系，反对称关系,集合A上的关系R，如果对于每个a,bA，如(a,b)R必有(b,a)R,则称R是对称的。集合A上的关系R，如果对于每个a,bA，仅当a=b时，(a,b)A有(b,a)R,则称R是反对称的。,反对称：如果对于每个a,bA,如(a,b)R且ab,必有(b,a)R,例11下列关系哪些是对称的，哪些是反对称的？R1=(a,b)|abR2=(a,b)|abR3=(a,b)|a=b或a=bR4=(a,b)|a=bR5=(a,b)|a=b+1R6=(a,b)|a+b3解：R3,R4,R6是对称的R1,R2,R4，R5是反对称的。,传递关系,集合A上的关系R，如果对于每个a,b,cA，如(a,b)R,且(b,c)R,必有(a,c)R,则称R是传递的。,例：正整数集合上的“整除”关系是自反的？对称的？反对称的？传递的？解：对于任意正整数a，a|a，自反的对于任意两个正整数，ab,如果a|b,那么b不能整除a.不是对称的，是反对称的。对于三个正整数a,b,c,如果a|b,b|c,那么a|c.所以是传递的。,例,X=1,2,3,4到Y=a,b,c,d的关系R=(1,b),(1,d),(2,c),(3,c),(3,b),(4,a)关系矩阵为,关系矩阵依赖于X和Y的顺序,例,a,b,c,d上的关系R=(a,a),(b,b),(c,c),(d,d),(b,c),(c,b)对应于顺序a,b,c,d的矩阵是其平方是可见，只要A2的ij项非零，A的ij项就非零。所以R是传递的。,76,5.4关系的闭包,R是集合A上的关系。如果存在包含R的具有性质P的关系S,并且S是包含R且具有性质P的每个关系的子集。S叫做R的关于P的闭包。自反闭包，对称闭包传递闭包,例1：整数集上的关系R=(a,b)|ab的自反闭包是什么？包含R的自反闭包是R=(a,b)|ab(a,a)|aZ=(a,b)|ab,集合A=1,2,3上的关系R=(1,1),(1,2),(2,2),(2,3),(3,1),(3,2)不是对称的。产生一个包含关系R的尽可能小的对称关系R=(1,1),(1,2),(2,2),(2,3),(3,1),(3,2),(2,1),(1,3)R的自反闭包为：RR-1R-1=(b,a)|(a,b)R,例：正整数集合上的关系R=(a,b)|ab的对称闭包？RR-1=(a,b)|ab(b,a)|ab=(a,b)|ab,5.5等价关系基础,等价关系等价类划分,例：1,2,3,4,5,6上的一个等价关系R=(1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5),(2,2),(2,6),(6,2),(6,6),(4,4),定义3.4.3,5.5.2等价关系定义1：集合X上的一个自反的、对称的和传递的关系称为X上的等价关系定义2：等价元素，ab,例：考虑1,2,3,4,5上的关系R=(1,1),(1,3),(1,5),(2,2),(2,4),(3,1),(3,3),(3,5),(4,2),(4,4),(5,1),(5,3),(5,5)因为(1,1),(2,2),(3,3),(4,4),(5,5)R，所以R是自反的。因为只要(x,y)在R中，则(y,x)也在R中，所以R是对称的。最后，因为只要(x,y)和(y,z)在R中，则(x,z)也在R中，所以R是传递的。所以R是1,2,3,4,5上的等价关系。,例,X=1,2,3,4,5,6上的关系R=(1,1),(1,3),(1,5),(3,1),(3,3),(3,5),(5,1),(5,3),(5,5),(2,2),(2,6),(6,2),(6,6),(4,4)是等价关系。包含的等价类1由所有使得(x,1)R的x组成。所以1=1,3,5类似地可以找出其余的等价类：3=5=1,3,5，2=6=2,6，4=4,5.6偏序,定义1：集合S上的关系R,如果它是自反的、反对称的、传递的，那么就称之为偏序。集合S和偏序R一起叫做偏序集，记作(S,R)例：证明“大于等于”（）关系R是整数集合上的偏序。证明：自反的，aa反对称的，(a,b)R,ab，那么b不大于等于a，即(b,a)R传递的，ab,bc,则ac,例,正整数集合上的”整除”关系R是偏序。自反的，反对称的和传递的。如果R是集合X上的