大学离散数学总复习题

大学离散数学总复习题（推荐9篇）

大学离散数学总复习题 篇1

一、选择题

1．设A={{1，2，3}，{4，5}，{6，7，8}}，下列各式中____D______是错的。

A、A； B、{6，7，8}A； C、{{4，5}}A； D、{1，2，3}A。

2.已知集合A={a,b,c},B={b,c,e},则 A⊕B=___C___________ A.{a,b} B={c} C={a,e} D=φ

3.下列语句中，不是命题的是____A_________ A.我说的这句话是真话； B.理发师说“我说的这句话是真话”； C.如果明天下雨，我就不去旅游； D.有些煤是白的，所以这些煤不会燃烧；

4.下面___D______命题公式是重言式。

A.PQR ； B.(PR)(PQ)；C.(PQ)(QR)；

D、(P(QR))((PQ)(PR))。

5.公式(p∧q)∨(p∧～q)的主析取范式是____B_______ A.m1∨m2 B.m2∨m3 C.m0∨m2 D.m1∨m3

6．设L(x)：x是演员，J(x)：x是老师，A(x , y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为___D______。

A、x(L(x)A(x,y))； B、x(L(x)y(J(y)A(x,y)))； C、xy(L(x)J(y)A(x,y))； D、xy(L(x)J(y)A(x,y))。7.关于谓词公式（x）(y)(P(x,y)∧Q(y,z))∧(x)p(x,y),下面的描述中错误的是__B_____ A．（x）的辖域是（y）（P（x,y）∧Q(y,z)）

B．z是该谓词公式的约束变元

C．（x）的辖域是P（x,y）D．x是该谓词公式的约束变元 8． 设SAB，下列各式中____B___________是正确的。

A、domSB ； B、domSA； C、ranSA； D、domS  ranS = S。9．设集合X，则空关系X不具备的性质是____A________。

A、自反性； B、反自反性； C、对称性； D、传递性。

10.集合A，R是A上的关系，如果R是等价关系，则R必须满足的条件是__D___ A.R是自反的、对称的 B.R是反自反的、对称的、传递的 C.R是自反的、对称的、不传递的 D.R是自反的，对称的、传递的 11.集合A={a,b,c,d},B={1,2,3},则下列关系中__ACD______是函数

A.R={(a,1),(b,2),(c,1),(d,2)} B.R={(a,1),(a,2),(c,1),(d,2)} C.R={(a,3),(b,2),(c,1)} D.R={(a,1),(b,1),(c,1),(d,1)} 已知集合 RA,且R={(1,2),(1,2),(2,1),(2,2),(2,3),(2,4),(3,4),(4,1)},则顶点2的入度和出度分别是___D_______ A.2,3 B.2,4 C.3,3 D.3,4 13.设完全图Kn有n个结点(n≥2)，m条边，当下面条件__C____满足时，Kn中存在欧拉回路．

A．m为奇数 B．n为偶数 C．n为奇数 D．m为偶数 14.下面叙述正确的是____B______ A.二部图K3,3是欧拉图 B.二部图是平面图

K3,3是哈密尔顿图

C.二部图 K3,32

D.二部图K3,3是既不是欧拉图也不哈密尔顿图

15.已知某平面图的顶点数是12，边数是14，则该平面图有__D___个面 A.3 B.2 C.5 D.4 16．设G是n个结点、m条边和r个面的连通平面图，则m等于___A____。

A、n+r-2 ； B、n-r+2 ； C、n-r-2 ； D、n+r+2。17.下面几种代数结构中，不是群的是___D____ A. B. C. D.(这里Z，Q，R，N分别表示整数集、有理数集、实数集、自然数集，+普通加法)

二、问答题

1.在程序设计过程中，有如下形式的判断语句： if(a>=0)if(b>1)if(c<0)cout<

请将这段程序化简，并说明化简的理由。解：简化的程序：

if(a>=0 && b>1 && c<0)cout<

设置命题变量： p: a>=0；q:b>1;r:c<0;s:cout<

A=P→(q→(r→s))经过等值演算可得，A与下面的公式是等值的 P∧q∧r→s

2.集合A={ 1, 2, 3, 4, 5, 6, 7, 8, 9 }，R={(x,y)| x|y}, ①证明R是偏序关系。

②写出偏序集（A，R）的极小元、极大元；最小元、最大元 ③写出A的子集B={1,2,3,6}的最小上界、最大下界

解：①根据整除性质可知，R满足自反性，反对称性，传递性。所以R是A上的偏序关系。

②偏序集（A，R）的极小元：1，极大元：5, 6，7，8，9 最小元：1； 最大元：无

③子集B={1,2,3,6}的最小上界：6 子集B={1,2,3,6}的最大下界：1

3.(1)m个男孩子，n个女孩排成一排，任何两个女孩不相邻，有多少种排法？

(n<=m)插空问题

(2)如果排成一个园环，又有多少种排法？

解：(1)考虑5个男孩，5个女孩的情况

男孩的安排方法： _B_B_B_B_B_ 排列总数P(5,5)女孩的安排方法：6个位置安排5个女孩，排列中数 P(6,5)所以：总的排列方法数是 m!*p(m+1,n)

(2)考虑男孩的圆排列情况，结果是(m-1)!*p(m,n)

4.某商家有三种品牌的足球，每种品牌的足球库存数量不少于10只，如果我想买5只足球，有多少种买法？如果每种品牌的足球最少买一只，有多少种买法？

解：①这是一个多重集的组合问题

类别数是k=3，选取的元素个数是 r=5 多重集组合数的计算公式是 N所以：N=C(3+5-1,5)=c(7,5)=21 ②可自由选取的球只有2个 k=3,r=2 N=C(3+2-1,2)=C(4,2)=6

(rk1)!C(kr1,r)

r!(k1)!

5．某软件公司将职工分为三种岗位。该公司65人，有些职工（例如项目管理人员、设计人员）可能从事不止一个岗位的工作。每个职工至少被分在一个岗位。现在软件设计岗位（岗位A）（包括需求分析、概要设计和详细设计等工作）的人数是15人，代码编写岗位（岗位B）的人数是32人，软件测试岗位（岗位C）的人数是28人，同时参加岗位A和岗位B的有12人, 同时参加岗位B和岗位C的有8人, 同时参加岗位A和岗位C组的有3人，问，三个岗位参加的有多少人？

解： 已知 |A|=15，|B|=32，|C|=28，|A∩B|=12，|B∩C|=8，|A∩C|=3 设S表示全班同学总人数，则 |S|=65 求：|A∩B∩C|=？

根据容斥原理：

|A∪B∪C|=|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C| 所以|A∩B∩C|=|A∪B∪C|-|A|-|B|-|C|+|A∩B|+|B∩C|+|A∩C| 因为每个同学至少参加一个小组，所以：|A∪B∪C|=|S| 因此：|A∩B∩C|=65-15-32-28+12+8+3=13 答：三个小组都参加的人数是13人

6.证明组合恒等式C(n,r)= C(n-1,r-1)+ C(n-1,r)

说明：也可以直接利用组合演算公式进行演算 7.求1228的个位数是多少? 解：1228的个位数就是1228 mod 10的余数1228mod10(12mod10)28mod1024*7mod10(27mod10)4mod108mod1064

8.已知图G有10条边, 4个3度顶点, 其余顶点的度数均小于2, 问G至少有多少个顶点?

解：由握手定理∑d(v)=2m=20，度数为3的顶点有3个占去12度，还有8度由其余顶点占有，而由题意，其余顶点的度数可为0，1，当均为1时所用顶点数最少，所以应有8个顶点占有此8度，即G中至少有8+4=12个顶点。

9刑侦人员审一件盗窃案时，已经掌握的线索如下：（1）甲或乙盗窃了电脑。

（2）若甲盗窃了电脑，则作案时间不能发生在午夜前。（3）若乙证词正确，则在午夜时屋里灯光未灭。（4）若乙证词不正确，则作案时间发生在午夜前。（5）午夜时屋里灯光灭了。

请通过命题逻辑推理，推论出谁是真正的盗窃犯？（写出详细的推理步骤）解 设p： 甲盗窃了电脑，q： 乙盗窃了电脑，r： 作案时间发生在午夜前，s： 乙证词正确，t：午夜时屋里灯光灭了。

前提： p∨q，p→~r，s→~t，~s→r，t(7)非p。。

10.插入排序算法的时间T与数据规模n的递推关系如下，求出T与n的显示关系表达式

T(n)T(n1)n1 T(1)0

解：

T(n)T(n1)n1 T(n2)n2n1T(n3)n3n2n1 T(nk)nkn2n1T(nk)kn-(12k)k(k1)T(nk)kn2令n-k=1，那么 k=n-1，所以：

n(n1)n(n1)n(n1) T(n)T(1)0222答：T与n的显示关系是：T(n)

11.解下列一阶同余方程组

n(n1)2x1(mod 3)x2(mod 4)x3(mod 5)解：已知a11,a22,a33;m13,m24,m35 方程组的齐次通解是：xkLcm(1,2,3)6k 60k 根据中国剩余定理，特解是：

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)M1m2m320,M2m1m315,M3m1m212 111M1mod m1是下列同余方程的解

3)，解得：x=2，即M12 M1x1(mod m1)即20x1(mod11同理可解得：M23，M33 11 7

x0a1M1(M1mod m1)a2M2(M2mod m2)a3M3(M3mod m3)mod m（120221533123）mod 60111所以：(4090108)mod 60238mod 6058

同余方程组的解是 xxx06k58 60k

12.假设需要加密的明文数据是a=8,选取两个素数p=7,q=19,使用RSA算法： ① 计算出密钥参数

② 利用加密算法计算出密文c ③ 利用解密算法根据密文c反求出明文a 解：① 取 p=7,q=19;计算 n=p*q=7*19=133 计算φ(n)=(p-1)*(q-1)=(7-1)*(19-1)=108 选取较小的数w,使w与108互质, 5是最小的,于是w=5 计算d,使d*w≡1(mod φ(n)),即d*5 mod 108=1,取d=65，d*5除以108余数为1, 于是算出d=65 至此加密、解密参数计算完成：

公钥w=5,n=133.私钥d=65,n=133.② 加密

cmwmodn85mod133((82mod133)*(83mod133))mod133

(64*113)mod13350③ 解密

acdmodn5065mod133

aA0A6 其中，A050, Ai(Ai1)2

根据上述递推公式可以计算出：A1502mod133106,A21062mod13364

A3642mod133106，„„, A61062mod13364 aA0A6(50*64)mod1338

解密后的明文与原来的明文是相等的，所以算法正确。

13.设A={1，2，3，4，6，9，12，24},R定义为R{(a,b)|ab(mod 3)}，（1）证明R是一个等价关系；（2）写出A的商集；

14.基于字典序的组合生成算法

问题说明：假设我们需要从5个元素中选取3个的所有组合，已知组合个数为 C（５，３）＝１０，按字典序，其具体组合为： 123,124,125,134,135,145,234,235,245,345 所谓按字典序生成组合，就是已知当前的组合（例如135），求下一个组合（例如，145）。下面给出算法的函数头：

//数组s[]:函数运行前，保存当前的组合，函数结束后，是新生成的下一个组合 //n,r:表示从n个元素中选取r个元素的组合 void next_comb(int s[],int n,int r)解：

void next_comb(into s[],int n,int r){

int j,m,max_val;

max_val=n;

m=r;

while(s[m]==max_val)

{

m=m-1;

max_val=max_val-1;

}

s[m]=s[m]+1;

for(j=m+1;j

s[j]=s[j-1]+1;}

大学离散数学总复习题 篇2

教师要想上好一节课, 必须拿出上课时间三倍的时间来备课。教师首先要吃透教材, 只有熟悉了教材才能顺利完成教学任务, 熟悉教材不仅包括掌握课本上的内容, 而且要深入到更深的层次上。

比如在讲欧拉图和哈密顿图的过程中, 教师可以在上课前通过上网查资料, 弄清楚欧拉图是欧拉通过哥尼斯堡七桥问题抽象出来的。尼斯堡是位于普累格河上的一座城市, 它包含两个岛屿和连接它们的七座桥, 该河流经城区的这两个岛, 岛与河岸之间架有六座桥, 另一座桥则连接着两个岛。星期天散步已成为当地居民的一种习惯, 但试图走过这样的七座桥, 而且每桥只走过一次却从来没有成功过, 但直至引起瑞士数学家欧拉注意之前, 没有人能够解决这个问题。通过这样一个有意思的小故事引出欧拉图, 学生就很容易记住欧拉图讲的是边不能重复的问题。在讲哈密顿图时, 教师可以介绍一下哈密顿周游世界问题, 从正十二面体的一个顶点出发, 沿着正十二面体的棱前进, 要把十二面体顶点无一遗漏地全部通过, 而每个顶点恰好只通过一次, 最后回到出发点。在这个问题刚提出来时, 生产商以为这是一个难题, 专为此设计了一个玩具, 以为可以吸引消费者, 谁知当这玩具推出市场时, 这个问题立刻被人解决了, 令生产商损失了一大笔钱。学生可以在笑声中很容易地记住哈密顿图是点不重复问题, 知道这两个图的区别。这些都要求教师在备课的过程中要充分准备各种资料。

教师在开始离散数学的教学之前应先简单介绍一下这门课程的重要意义及作用, 点明离散数学对其后续课程的基础作用, 让学生意识到这门课程在整个专业课程中的地位。学生只有提高了学习的积极性, 才会主动地去学习, 而不是被动地接受老师填鸭式的教学。教师应先把整个教材的内容分成几个小部分, 把每一部分的结构帮学生梳理清楚, 简单介绍一下每部分的主要内容。以耿素云的《离散数学》为例, 教师可以通过列表的方法把整个教材分成五个部分, 这样子可让学生在学习之前就大体了解离散数学的框架。

在上课的过程中, 教师要采用多种教学方法。离散数学定义特别多, 不太适用传统教学手段像黑板板书之类的, 这就要求教师采用现代化的教学方法多媒体, 而对数学来讲单纯多媒体教学效果不是特别好, 所以应该将这两种教学方法相结合。在课堂上教师应注意学生对这节课教学内容的反馈, 多问几个“听明白了吗”, “有没有问题”, 不能只注重教, 要注重教学效果, 要重视学生的情绪, 及时调整教学进度, 把学生的思路引进到教学活动中来, 使之兴趣盎然。比如在讲数理逻辑这一部分内容时, 教师可以多举几个实际问题的例子, 以便引起学生的兴趣。在讲关键路径时, 在定义描述中最早完成时间是沿最长路径到达目的地所需要的时间, 大部分学生对这个最长路径不理解。我给学生举了个简单的例子:在工程的盖楼过程中, 假设盖好一层楼需要两个必须步骤, 一是买水泥做钢筋混凝土, 二是打木桩, 在盖楼的过程中, 买水泥需要两周的时间, 做混凝土需要三周, 而打木桩需要四周, 那么现在盖起楼的最早完成时间是五周, 取决于时间最长的那个步骤。这样通过一个简单的例子, 学生就记住最早完成时间的概念。教学方法只是一种手段, 而不是教学目的, 甚至可以对某些内容设计几套方案, 以防止种种可能出现的结果, 做到有备无患。

在离散数学的教学过程中要讲求教学的针对性, 离散数学是计算机类专业普遍开设的一门专业基础课, 这就决定了其面向特定的学生, 这要求教师要注重学生的学科特点和内容的针对性。计算机学科的发展速度很快, 课本的内容可能有些已经跟不上时代的发展, 教师需要在教学过程中多去查资料, 运用互联网的资源, 把最先进最前沿的学科知识介绍给学生, 不断更新引例, 使授课内容更具时代特色和生活气息。比如在讲最短路径时, 教师可以找一个运用到最短路径的实际例子, 把这个问题的程序给学生运行一下, 让学生明白所学到的知识点和实际问题有什么联系。另外一个问题是在讲特殊的图时, 可以结合实际, 比如说教务处安排考试的问题, 要求教务处七天安排七门考试, 同一个老师担任的几门课程不能排在相邻的两天, 并且已知一个老师最多担任四门课程, 问题是教务处能否安排出可行的考试方案。我在讲课的过程中提到这个问题时, 本来已经介绍过几种特殊的图, 但学生感觉内容太多接受不了, 可是一听考试并且和自己密切相关, 顿时打起精神, 纷纷讨论怎么安排可行, 这就把课堂气氛搞活跃了。最初学生并不能联想到把这个转化成图的问题, 我就一步一步地引导, 告诉他们先把实际问题转化成图的问题画在纸上, 然后看看题目要求的这个图具有什么特性。最后学生才恍然大悟, 原来是哈密顿通路问题, 这样子这一节课的教学效果就会比较好。

检查学生掌握程度的手段是测试, 但是不能让测试成为学生的压力, 让他们对离散数学的学习产生抵触程序。考试是衡量学生学习水平的重要手段, 应该为教学而考试, 而不是为考试而教学, 学生掌握这门课程才是教师教的目的。

学习知识的目的是为了培养学生动手能力, 同时也加深他们对该课程在专业教学中地位的理解和认识。在离散数学的教学过程中, 教师应尝试在传统教学内容的基础上, 适当增加上机实验操作的教学模式。教师在探索的基础上, 应不断丰富实验内容, 在量的积累的基础上达到质的飞跃, 从而建立一套完备的离散数学的教学方法, 进一步提高离散数学在计算专业中的地位。

参考文献

[1]罗幼芝.提高离散数学实践性教学的探讨.湖北生态工程职业技术学院学报, 2009, Vol7, No.4:25-28.

[2]离散数学课程教学改革探索与实践.计算机教育, 2010.3.25, 6:100-103.

高三数学总复习策略 篇3

认真研究考纲,确定复习方向

笔者通过多年对高考试题的研究发现,真正的高考信息,来自对考纲、高考题、教材的学习和研究。教师要分析、体会高考题是如何体现考纲要求的。同时,高考题也是课本上例题、习题的类似题或变式题。如果考纲变化了,教师要明确其变在哪里,稳在何处,从而采取针对性措施。对考纲中容易题、中等题、难题、复习中知识点难度的控制,要通过具体的题目来体现。所以,题目的选取能否既符合考试的要求和趋势,又符合学生的实际就显得尤为重要,更是对教师教学经验与水平和对考纲把握程度的反映。

研究好考纲,就能把握好复习的尺度,掌握好题目的难度和类型,从而避免复习的盲目性,不做无用功;就能增强复习的针对性,提高复习的实效性。教师必需通过对教材、高考题的研究,紧贴考纲,驾驭教材、高考题,制定好三轮复习的指导思想和复习计划。

优化教学过程,提高复习效果

首先,备课要充分、有计划,上课要有效率。备课时,教师对每个章节内容的取舍、重点难点的把握、题型的选择、方法的选取、题量的控制、测试题难度都要反复斟酌,做到心中有数,并在教学过程中,根据反馈信息及时调整复习的进度。如解题训练是高考复习的一个重要环节,教师可在分析研究学生实际情况的基础上,确定教学方案:课堂例题应以中档综合题为重点,少选难题,重视讲解,充分暴露思维过程,注重方法规律的概括总结,同时还要兼顾学生训练的度和量。上课要变传统的“讲——练——讲”为“练——讲——练”,题目要由易到难,分层次设计,从而使每个学生都有收获。又如,教师在课堂上要重视题目评点,能强化学生的思维形成:

(1)评点题目解答的多样性,培养学生思维的灵活性。讲一题多解,要先讲最基本的方法,再讲方法的演变,要从不同侧面、不同角度分析问题和解决问题,比较各种方法的优缺点,教会学生如何选择最佳方法,但一题多解不能因为过多地追求解题技巧而冲淡学生对基本解法的掌握。

(2)评点题目解答的合理性,培养学生思维的深刻性。针对有的学生解题时,不注意审题或审题不清,缺乏周密的和深入的思考,教学时教师可通过对学生解答的合理性作点评,进而提高学生的解题能力,深化学生的思维。

(3)评点题目解答的科学性,培养学生思维的批判性。对于有些题,特别是应用性的题目,通过引导学生判断答案是否合理,形成学生的批判性思维。

(4)评点题目结论的应用性,培养学生思维的敏捷性。有的数学题的结论应用广泛,充分挖掘和发挥其应用功能,就能让学生敏锐地抓住某些数学题的本质,从多种方案中快速优选,大大提高解题速度。

(5)评点题目的多变性,培养学生思维的广阔性和创造性。在解题教学中,教师不应满足于就题论题、讲完了事,要通过典型题的一题多变、多题归一的点评,达到让学生学会举一反三、融会贯通的教学目的,培养学生多角度、多层面、全方位地考虑问题,培养其勇于创新的思维品质。

其次,注意三轮复习的侧重点和衔接。第一轮复习是基础,要兼顾全面、扎实、系统、灵活的原则。第二轮复习是对第一轮复习的巩固、强化、综合,又是学生数学能力和学习成绩大幅度提高的过程。第三轮复习则是查漏补缺,模拟训练,调节学生心理情绪,使之处于最佳竞技状态。当然,三轮复习不是独立的,第二轮复习中要适当带有章节练习,教师应对学生进行不同题型的解题策略的指导和方法的总结。第三轮复习中还要穿插章节或专题训练。

注重信息反馈,调整教学策略

信息反馈包括课上信息反馈、课后信息反馈、测试后信息反馈。教师在课堂要根据学生反应、课堂练习情况,及时调整教学。课后要根据下班辅导、学生作文、学生疑问、师生交流等情况调整以后的教学。每次测试后,可先让学生自己改错、自己分析试卷,每道题考查了哪些知识点,可用哪些方法解题,你的方法优点在哪里,不足之处是什么,分析错题原因,搞清是知识理解、计算错误,还是方法选择上的失误。然后教师再来讲评,帮助学生分析总结,从而积累考试经验,尽量解决“会而不对、对而不全、全而不美”的知识原因、策略原因、逻辑原因、心理原因,在此基础上,教师再调整自己的教学,效果更佳。

了解易犯错误,防止问题出现

教师要对每轮复习中经常出现的几类问题进行深入地剖析,进而提前预防和及时发现问题。

第一轮复习中常出现的问题有:(1)复习无计划、效率低。原因是重点把握不准,详略不当;教材把握不准,复习偏难或偏易。(2)复习不扎实,漏洞多。原因是起点过高,难题耗时过多,忽视基础;速度过快,学生掌握不牢,知识出现漏洞;要求过松,抓而不紧,基础不牢。(3)解题不少,能力不高。原因是以题论题,缺少总结、归纳、推广;题目无序、无梯度、没有归类、重复。

第二轮复习中常出现的问题有:(1)机械重复第一轮复习。(2)单纯就题做题、就题论题。(3)起点过高、难题过多。(4)学生成绩的提高出现停滞。在第一轮对试题的大量练习后,第二轮复习过程中,由于种种原因,常常会出现学生成绩停滞不前的现象,这是教师在第二轮复习中应引起足够重视的一个危险信号。解决的措施有:组织会诊,寻找病因;重新研究学生;重新备课、重新设计习题;组织高质量的讲评:解决学生的心理问题。

第三轮复习中常出现的问题有:过多地做练习,以练代讲:进行不坚守课堂、不备课、不研究的“放养式”复习;考前辅导简单,考试技巧辅导不够,考试心理辅导不重视;没有继续着力解决学生成绩停滞的问题。

(作者单位:江苏海门市三厂

《离散数学》期末复习 篇4

内容：第一章~第七章 题型：

一、选择题（20%，每题2分）二．填空题（20%，每题2分）

三、计算题（20%，每题5分）

四、证明题（20%，每题5分）

五、判断题（20%，每题2分）

第1章 数学语言与证明方法

1.1 常用的数学符号

1.计算常用的数学符号式子 1.2 集合及其表示法

1.用列举法和描述法表示集合

2.判断元素与集合的关系(属于和不属于)3.判断集合之间的包含与相等关系，空集(E)，全集()4.计算集合的幂集

5.求集合的运算：并、交、相对补、对称差、绝对补

6.用文氏图表示集合的运算 7.证明集合包含或相等

方法一： 根据定义, 通过逻辑等值演算证明

方法二： 利用已知集合等式或包含式, 通过集合演算证明

1.3 证明方法概述

1、用如下各式方法对命题进行证明。 直接证明法：AB为真

 间接证明法：“AB为真”  “ ¬B ¬A为真”  归谬法(反证法)： A¬B0为真

 穷举法： A1B, A2B,…, AkB 均为真

 构造证明法：在A为真的条件下, 构造出具有这种性质的客体B  空证明法：“A恒为假”  “AB为真” 平凡证明法：“B恒为真”  “AB为真”  数学归纳法： 第2章 命题逻辑

2.1 命题逻辑基本概念

1、判断句子是否为命题、将命题符号化、求命题的真值（0或1）。

命题的定义和联结词(¬, , , , )

2、判断命题公式的类型

赋值或解释.成真赋值,成假赋值；重言式(永真式)、矛盾式(永假式)、可满足式:。2.2 命题逻辑等值演算

1、用真值表判断两个命题公式是否等值

2、用等值演算证明两个命题公式是否等值

3、证明联结词集合是否为联结词完备集 2.3 范式

1、求命题公式的析取范式与合取范式

2、求命题公式的主析取范式与主合取范式（两种主范式的转换）

3、应用主析取范式分析和解决实际问题 2.4 命题逻辑推理理论

1、用直接法、附加前提、归谬法、归结证明法等推理规则证明推理有效 第3章 一阶逻辑

3.1 一阶逻辑基本概念

1、用谓词公式符号命题（正确使用量词）

2、求谓词公式的真值、判断谓词公式的类型 3.2 一阶逻辑等值演算

1、证明谓词公式的等值式

2、求谓词公式的前束范式 第4章 关系

4.1 关系的定义及其表示

1、计算有序对、笛卡儿积

2、计算给定关系的集合

3、用关系图和关系矩阵表示关系 4.2 关系的运算

1、计算关系的定义域、关系的值域

2、计算关系的逆关系、复合关系和幂关系

3、证明关系运算满足的式子 4.3 关系的性质

1、判断关系是否为自反、反自反、对称、反对称、传递的2、判断关系运算与性质的关系

3、计算关系自反闭包、对称闭包和传递闭包 4.4 等价关系与偏序关系

1、判断关系是否为等价关系

2、计算等价关系的等价类和商集

3、计算集合的划分

4、判断关系是否为偏序关系

5、画出偏序集的哈期图

6、求偏序集的最大元、最小元、极小元、极大元、上界、下界、上确界、下确界

7、求偏序集的拓扑排序 第5章 函数

1.判断关系是否为函数 2.求函数的像和完全原像

3.判断函数是否为满射、单射、双射 4.构建集合之间的双射函数 5.求复合函数

6.判断函数的满射、单射、双射的性质与函数复合运算之间的关系 7.判断函数的反函数是否存在，若存在求反函数 第6章 图

1.指出无向图的阶数、边数、各顶点的度数、最大度、最小度

2.指出有向图的阶数、边数、各顶点的出度和入度、最大出度、最大入度、最小出度最小入出度

3.根据握手定理顶点数、边数等

4.指出图的平行边、环、弧立点、悬挂顶点和悬挂边 5.判断给定的度数列能否构成无向图

6.判断图是否为简单图、完全图、正则图、圈图、轮图、方体图 7.求给定图的补图、生成子图、导出子图 8.判断两个图是否同构 6.2 图的连通性

1.求图中给定顶点通路、回路的距离

2.计算无向图的连通度、点割集、割点、边割集、割边 3.判断有向图的类型：强连通图、单向连通图、弱连通图 6.3 图的矩阵表示

1.计算无向图的关联矩阵 2.计算有向无环图的关联矩阵 3.计算有向图的邻接矩阵 4.计算有向图的可达矩阵

5.计算图的给定长度的通路数、回路数 6.4 几种特殊的图

1、判断无向图是否为二部图、欧拉图、哈密顿图 第7章 树及其应用 7.1 无向树

1.判断一个无向图是否为树

2.计算无向树的树叶、树枝、顶点数、顶点度数之间的关系 3.给定无向树的度数列，画出非同构的无向树 4.求生成树对应的基本回路系统和基本割集系统 5.求最小生成树 7.2 根树及其应用

1.判断一个有向图是否为根树

2.求根树的树根、树叶、内点、树高 3.求最优树

4.判断一个符号串集合是否为前缀码 5.求最佳前缀码

《离散数学》图论部分习题 篇5

1.已知无向图G有12条边，6个3度顶点，其余顶点的度数均小于3，问G至少有几个顶点？并画出满足条件的一个图形.（24-3*6）/2 +6=9 2.是否存在7阶无向简单图G，其度序列为1、3、3、4、6、6、7.给出相应证明.不存在；7阶无向简单图G中最大度≤6 3.设d1、d2、…、dn为n个互不相同的正整数.证明：不存在以d1、d2、…、dn为度序列的无向简单图.Max{d1，d2，…，dn}≥n，n阶无向简单图G中最大度≤n-1 4.求下图的补图.5.1)试画一个具有5个顶点的自补图

2)是否存在具有6个顶点的自补图，试说明理由。

对于n阶图，原图与其补图同构，边数应相等，均为(n*(n-1)/2)/2，即n*(n-1)/4且为整 数，n=4k或n=4k+1，不存在6阶自补图。

6.设图G为n(n>2且为奇数)阶无向简单图，证明：G与G的补图中奇度顶点个数相等.n(n>2且为奇数)，奇度点成对出现

7.无向图G中只有2个奇度顶点u和v，u与v是否一定连通.给出说明或证明。

只有2个奇度顶点u和v，如果不连通，在u和v在2个连通分支上，每个分支上仅有一个奇度顶点，与握手引理相矛盾。

8.图G如下图所示：

1)写出上图的一个生成子图.2)δ(G)，κ(G)，λ(G).δ(G)=2，κ(G)=1，λ(G)=2.说明：δ(G)=min{ d(v)| vV } ；κ(G)=min{ |V’| |V’是图G的点割集} ； λ(G)=min{ |E’| |E’是图G的边割集} 9.在什么条件下无向完全图Kn为欧拉图？

n为奇数时

10.证明：有桥的图不是欧拉图.假设是欧拉图：桥的端点是u和v，并且图各顶点度均为偶数； 桥为割边，删除桥，图不再连通，u和v应该在2各不同的连通分支上；且u和v度数变为奇数；由于其他顶点度数均为偶数，则u和v所在的连通分支上只有一个奇度顶点，与握手引理矛盾。

11.证明：有桥的图不是哈密尔顿图.若G是K2，显然不是哈密尔顿图；

否则n≥3，则桥的两个端点u和v至少有一个不是悬挂顶点（容易证明悬挂顶点不是割点）；设u不是悬挂点，则u是割点，存在割点显然不是哈密尔顿图。

12.树T有2个4度顶点，3个3度顶点，其余顶点全为树叶，问T有几片树叶？

X+2*4+3*3=2*（2+3+x-1）

x=9 13.证明：最大度Δ（T）≥k的树T至少有k片树叶。

设有n个顶点，其中x片树叶

2*（n-1）≥1*K+（n-x-1）*2+x*1

x≥k 14.已知具有3个连通分支的平面图G有4个面，9条边，求G的阶数.n-9+4=3+1

n=9

15.给出全部互不同构的4阶简单无向图的平面图形。

离散数学练习题B 篇6

一、简要回答下列问题：

1．什么是消去环？请举一例。

2．请给出公式R→P的真值表。

3．什么是恒真公式？举一例。

4.什么是子句？什么是短语？

5．请给出命题xG(x)的真值规定

6．什么是最优树？

7．什么是群？举一例。

8．给出环的定义。举一例。

9．什么是整区？举一例。

10．什么是半序格？请举一例。

二、对任意集合A，B，证明：

(1)AB当且仅当(A) (B)；

(2)(A)(B)(AB)；

(3)(A)(B)=(AB)；

举例说明：(A)∪(B)≠(A∪B)

三、证明：映射的乘法满足结合律，举例说明：映射的乘法不满足交换律。

四、判断下列公式是恒真？恒假？可满足？

a)(P(QR))(P(QR))；

b)P(P(QP))；

c)(QP)(PQ)；

d)(PQ)(PQ)。

初中数学总复习策略 篇7

一、制定有效的复习计划

数学复习计划, 对指导师生进行系统复习具有明显的导向作用.复习计划的制订应注意: (1) 认真钻研教材, 确定复习重点.确定复习重点要根据课标要求的四个层次——了解、知道、理解和掌握来制定.这是确定复习重点的依据和标准.对教材要求了解的, 让学生知其然即可;要求知道的, 要领会其实质, 在原有的基础上加深印象;要求理解的, 要加深巩固, 对所涉及的各种类型的习题, 能准确地解答;要求掌握的, 要灵活掌握解题的技能技巧.熟识每一个知识点在数学教材中的地位、作用; (2) 正确分析学生的知识状况, 对平时教学中掌握的情况进行定性分析; (3) 根据知识重点、学生的知识状况及复习时间制定详细可行的复习计划.

二、坚持“先练后教”的原则

复习是对教材知识点的再现过程.学生往往认为, 复习就是将所学过的知识内容再重复一遍, 认为复习的内容都是学过的, 自己已经懂了;学生甚至会认为, 这么简单, 没有新意的问题, 根本没必要再学, 于是产生抵触情绪, 不配合教师的复习教学工作.如果教师不分析学生的思想实际, 一味地将知识点进行灌输, 势必让学生感到枯燥乏味.不妨采用“先练后教”的教学方法, 其具体步骤是:根据每节课的教学内容精选一定量的、具有代表性、典型性的例题, 在课堂教学中, 规定时间让学生先练习.当学生感觉到自己所学的不足与缺陷时, 自然会向教师提出问题.教师抓住这个时机, 激发学生求知欲, 增强学生产生知难而进、勇于攻破难题的信心, 引导学生解决问题.在解题的过程中按照中考确定的重点、难点渗透教材的知识点, 激发学生重新认识教材知识点的兴趣, 学生就会全神贯注地投入到复习教学中.

三、归纳强化, 提高常规题型的正确率

对常规题型, 必须经过适量、适当训练才能达到熟练程度, 每练一题就应是一次学习和巩固, 一看到这类问题马上就能想到涉及这类问题的相关知识点及解决它的常用方法, 使之形成习惯.注重知识体系的形成, 不只是简单的重复, 加强记忆, 重要的是要深化认识.从本质上发现数学知识之间的联系, 从而加以分类、整理、综合, 逐渐形成一个条理化、秩序化、网络化的有机体, 真正实现由厚到薄的过程.仔细总结做题时失误的地方, “吃一堑, 长一智”, 解答较易题时, 严谨细致, 落实到位;解答中档题时, 调整心态, 坚持不懈;解答较难题时, 顽强拼搏, 不言放弃.解题之前思路分析很重要, 学习数学不仅要学怎么做怎么算, 更重要的要学怎么想, 把解题之前的思路分析作为重点, 从中逐渐学会分析、判断和决策, 提高解题能力.

四、例题的讲解要一题多变, 防止题海战术

在数学复习课教学中, 根据教学目的、教学重点和学生实际进行例题的选择, 要选择具有代表性的典型例题进行分析, 要突出复习内容的重点, 紧扣课标, 反映课标中的重点的基本内容.一题多变, 挖掘内容的内涵、外延, 在变化中巩固知识, 寻找解题规律, 从而实现由量变到质变的飞跃.如在复习二次函数时, 我举这样一个例子:二次函数图像经过点 (0, 0) 与 (-1, -1) , 开口向上, 且在x轴上截得的线段长为2, 求这个二次函数的解析式.由于二次函数的图像是轴对称图形, 由题意画图后知, (-1, -1) 是顶点坐标.可用二次函数的顶点坐标式y=a (x+m) 2+n的形式, 再求它的解析式.在教学中将题目中的条件在x轴上截得的线段长为2改为在x轴上截得的线段长为4, 求解析式.变化后由题意可知 (-1, -1) 点并不是顶点坐标了, 但是图像经过了 (-1, -1) 点, 所以可以用二次函数的x轴交点坐标式求解.若将原题目中的条件开口向上去掉, 这样题目就会有两个解.条件的不断变化, 解题的思路也在不断变化, 学生的思维也在不断变化.让学生在不断变化中巩固知识, 在知识的纵横联系中提高学生灵活运用知识解决问题的能力.

五、系统整理, 提高复习效率

总复习要特别体现教师的主导作用.对初中数学知识加以系统整理, 依据基础知识的相互联系及相互转化关系, 梳理归类, 分块整理, 重新组织, 变为系统的条理化的知识点.这种归纳总结对学习程度差别不大、素质较好的班级可在教师的指导下师生共同去完成, 即由学生“画龙”, 教师“点睛”.中等及其以下班级由教师归类, 对比讲解, 分块练习与综合练习交叉进行, 使学生真正掌握初中数学教材内容.

中考数学总复习备考策略 篇8

下面谈一谈笔者对总复习的见解，以期抛砖引玉.

一、系统整理知识，做好复习计划（2月20日前完成）

从近几年各地区的中考试题来看，大多以基础题为主，有些基础题是课本上的原题或改造题，后面的大题虽“高于课本”，但原型一般还是课本中的例题或习题，是课本中题目的引申、变形或组合.因此，总复习教学要立足于课本，从教科书中寻找考题的“影子”.

初中数学知识多而杂，其基础知识和基本技能又分散在三年的教科书中.在总复习工作开展前夕，教师要系统地对三年的知识加以整理，进行分类、分块，重新组织，变为系统的、有条理的知识点.例如代数部分可分为以下单元：实数和代数式；方程（组）与不等式（组）；函数；概率与统计，几何部分可分为以下单元：几何的基本概念、相交线与平行线；三角形；四边形；相似形；解直角三角形；圆.教师可以根据以上分类、分块对知识点进行梳理，并做好系统的复习计划.制订复习计划时，既要考虑学生的因素，也要考虑到新课程标准，以及相关部门发布的中考说明之类的信息，要避免“只低头拉车，不抬头看路”的做法.

二、立足课本，落实“双基”（2月下旬~4月中旬）

扎实的基础知识，娴熟的基本技能是形成数学能力的基础，是进行后续学习的前提.复习的第一阶段，教师要帮助学生过好课本关（要按知识归类、板块复习，不可按课本编排的顺序复习），使学生系统掌握课本的基础知识和基本技能，始终把“双基”放在首位.近几年中考命题的一大特点是“切入容易，基础性强”，选择题、填空题、解答题中的多数题目都是立足于考查“双基”.为此，教师可以设置复习纲要问题，由学生思考、讨论、作答，要求学生对基本概念、性质、公式、法则、定理等内容的叙述、理解准确无误，运用自如.例如在复习“有理数”一章时，可把内容分成三类，即“概念关”、“法则关”、“运算关”，在规定时间内通过讨论，找出每个“关口”的知识点及应注意的地方.如“概念关”里的正负数、相反数、绝对值、数轴的意义；“法则关”里的异号两数相加的符号确定方法；在“运算关”强调计算细心、书写规范等等.学生讨论完毕，教师进行总结.这样，不仅使旧知识得以巩固，而且能使学生处于“听得懂，做得来”的状态，从而激发学生的兴趣并树立信心.

要让学生掌握各知识点之间的联系，理清知识结构，形成整体认识.例如，一元二次方程的根与二次函数图象和x轴交点之间的关系，在复习时，应从整体上理解这部分内容，从结构上把握教材，达到熟练地将这两部分知识相互转化.

要注重指导学生掌握课本的重点章节，典型例题，习题的分析，特别是解题的思路是怎样形成的，思维方法及常用解法都可以解决哪些问题，重视题目的变式训练.

例：（1）解方程：x²+y²+6x-2y+10=0；

（2）已知：a²+2a+1+b²=0，求a²⁰⁰⁸+b²⁰⁰⁹的值；

（3）已知：|3x+6|+(2y-4)²=0，求x和y的值；

（4）若a、b、c为△ABC的三边，且a²+b²+c²-ab-bc-ca=0，求证：△ABC是等边三角形.

经过观察、分析、比较，不难发现上述四个问题的表达方式虽然不同，但都属于应用非负数的性质解题.通过这样的训练，学生便能聚集练习题的同类题并能分析异同，把知识从一个问题迁移到另一个问题，形成技能技巧，达到做一题，会一类、懂一法、长一智的目的.

复习完一个板块的基础知识之后，教师应精心编制一份渗透该板块主要知识点的测试题，让学生在规定时间内独立完成，然后按测试中出现的学生难以理解、遗忘率较高、易混易错的内容深入讲解，加强训练.总之，第一阶段复习的目标是让学生全面掌握初中数学基础知识，提高基本技能，做到全面、扎实、系统，形成知识网络.

三、综合运用知识，加强能力培养（4月中旬~5月下旬）

复习的第二阶段应从整体上把握三年的内容，提高学生综合运用知识的能力.可以说这是一个攻坚阶段，[HJ][HJ2.6mm]它的成败决定着学生在中考中能否拿高分.

1.狠抓重点内容，学生反复练习.这个阶段，通常以综合练习题为主，适当加大模拟题的分量.对教师来说，主要任务是精心选题，精心批改学生完成的习题，及时讲评.选择的题目要有目的性、典型性、规律性和综合性，题目的形式要多样，但不宜让学生陷于“题海”中，题目要有一定难度，但不是越难越好，要让学生可以接受.这样既能激发学生解难题、攀高峰的学习欲望，又可使学生从解决难题的过程中看到自己的力量，增强前进的信心，从而培养学生良好的学习情感，提高复习的效率和效果.

例：已知关于x的一元二次方程（a+c）x²+2bx+(a－c)=0的两根之和为-1，两根之差为1，其中a、b、c是△ABC的三边长.（1）求方程的两根；（2）判断△ABC的形状.

这是一道代数、几何综合题，涉及的知识较多，也有一定难度.通过解答本题，既可使学生巩固基础知识和掌握重点内容，又能培养学生分析问题、解决问题以及综合运用知识的能力.

2.加强解题指导.要着力在思路分析上指导，在总结规律上指导，在题目变化上指导.例如，遇到有关一元二次方程的问题时，通常涉及根的判别式和根与系数的关系；遇到解直角三角形的问题时，经常涉及到边角关系的转换；平面几何的证明题，往往可以从结论开始分析往前推，直至推到已知条件或某个公理、定理为止；有关两圆相交或相切的证明题，往往通过添加两圆的公共弦或过切点引两圆的公切线来寻求推证的途径；在等积式的证明中，一般化为与其等价的比例式，要证明比例式成立，往往要证与之相关的两个三角形相似，若不能构成三角形或能构成三角形但难以直接证明三角形相似，可用以下方法处理：（1）利用“中间积”作代换；（2）利用“中间比”作等比代换；（3）利用另一条线段作“等量代换”.学生多掌握解题的窍门，解题时就能得心应手，顺利完成.

3.重视数学思想和数学方法.常用的数学思想有函数与方程思想、转化与化归思想、数形结合思想、分类讨论思想、概率与统计思想等，常用的数学方法有代入法、消元法、换元法、待定系数法、配方法、判别式法、分解组合法、构造法等.中考题考查数学思想和方法的题目一般都比较新颖，综合性强，要在复习中注意发掘和运用.

4.贯彻新理念，培养综合能力.新课程标准下的教学目标，在传统教学目标的基础上又强化了三大能力，即阅读理解能力、探索创新能力和数学应用能力.这些能力要求将使中考数学试题对能力的考查进入一个新阶段.因此，要引导学生关注生活、社会现实、经济建设、方案探索等各个方面的问题，增强学生用数学的意识；要扩大实际问题抽象为数学问题的建模训练，培养学生用数学的能力；要加强阅读、理解和表达的训练（例如文字、图形、图表、图象、符号等多种语言的理解和转化）；要紧密联系生活，促进学生学用结合的能力.

例：一种节能灯的功率为10瓦，售价为60元；一种白炽灯的功率为60瓦，售价为3元.两种灯的照明效果一样，使用寿命也相同（3000小时以上）.如果电费价格为0.6元/千瓦时，消费者选用哪种灯可以节省费用？

通过此例，可引导学生分析、寻找变量之间的关系，并建立数学模型（一次函数），解决好数学问题，进而解决应用问题，最终探索出解决方案选择这类问题的一般方法，显现数学的应用价值，贯彻“人人学有价值的数学”的新理念.

四、战前练兵，模拟中考（5月下旬~6月中旬）

在完成第二阶段的复习后，要做一批模拟试题检查复习效果.模拟测试要求学生做题“快”且“准”，在题量大、时间紧的情况下，“准”尤为重要.因此，平时训练时既要做到“准”又要做到“快”，而不是只要做对即可.要引导学生正确对待，调整心态，振作精神，要求会做的题拿满分，不会做的题争取拿分.如何拿分？主要靠准确完整的数学语言表述，不能省去必要的步骤，会多少写多少.唯有如此，才能拿到分、拿高分.

学生模拟测试后，教师要认真分析学生的考卷，讲评时要侧重对学生出现的问题加以解决并强化这方面的练习，也要要求学生养成良好的反思习惯，及时总结解题思路和技巧，从而扩大并巩固复习成果.

切实提高复习实效是初三数学复习教学的最终目标.因此，任课教师要有强烈的质量意识，要因地制宜地拟订复习计划，要充分发挥集体的智慧，加强同事之间和校际之间的交流，要认真探索、研究和总结有效的复习方法，使每一个学生都能学到“有价值的数学”都能获得“必需的数学”，都能在数学上得到应有的发展，都能轻松地、信心百倍地迎战中考.

大学离散数学总复习题 篇9

1.合计100分

2.给出每小题得分(注意: 写出扣分理由).3.总得分在采分点1处正确设置.设R={|x,y∈N且x+3y=12}.【本题合计10分】(1)求R的集合表达式(列元素法);(2)求domR, ranR;(3)求R◦R;(4)求R↾{2,3,4,6};(5)求R[{3}];解

(1)R={<0,4>,<3,3>,<6,2>,<9,1>,<12,0>}【2分】(2)domR={0,3,6,9,12}, ranR={0,1,2,3,4}【2分】(3)R◦R={<3,3>, <0,4>}【2分】(4)R↾{2,3,4,6}={<3,3>, <6,2>}【2分】(5)R[{3}]={3}【2分】 设R,F,G为A上的二元关系.证明:(1)R◦(F∪G)=R◦F∪R◦G(2)R◦(F∩G)⊆R◦F∩R◦G(3)R◦(F◦G)=(R◦F)◦G.【本题合计18分：每小题6分，证明格式正确得3分，错一步扣1分】 证明

(1)∀, ∈R◦(F∪G)⇔ ∃t(xRt∧t(F∪G)y)复合定义 ⇔ ∃t(xRt∧(tFy∨tGy)∪定义

⇔ ∃t((xRt∧tFy)∨(xRt∧tGy))∧对∨分配律 ⇔ ∃t(xRt∧tFy)∨∃t(xRt∧tGy)∃对∨分配律 ⇔ x(R◦F)y∨x(R◦G)y 复合定义 ⇔ x(R◦F∪R◦G)y ∪定义 得证

(2)∀, x(R◦(F∩G))y ⇔ ∃t(xRt∧t(F∩G)y)复合定义 ⇔ ∃t(xRt∧(tFy∧tGy))∩定义

⇔ ∃t((xRt∧tFy)∧(xRt∧tGy))∧幂等律, ∧交换律, ∧结合律 ⇒ ∃t(xRt∧tFy)∧∃t(xRt∧tGy)补充的量词推理定律 ⇔ x(R◦F)y∧x(R◦G)y 复合定义 ⇔ x(R◦F∪R◦G)y ∪定义 得证

(3)∀, ∈R◦(F◦G)⇔ ∃s(∈R∧∈(F◦G))◦定义 ⇔ ∃s(∈R∧∃t(∈F∧∈G)))◦定义 ⇔ ∃s∃t(∈R∧∈F∧∈G)辖域扩张公式 ⇔ ∃t∃s((∈R∧∈F)∧∈G)存在量词交换 ⇔ ∃t(∃s(∈R∧∈F)∧∈G)辖域收缩公式 ⇔ ∃t(∈(R◦F)∧∈G)复合定义 ⇔ ∈(R◦F)◦G 复合定义 得证 设F={|x－y+2>0∧x－y－2<0}是实数集R上的二元关系, 问F具有什么性质并说明理由.【本题合计10分：每种性质2分----答对得1分，正确说明理由得1分】 解 F={|x－y+2>0∧x－y－2<0}={|－2∈F显然.对称性: ∀, ∈F⇔－2∈F.不具有反自反性: 反例 <2,2>∈F 不具有反对称性: 反例 <2,3>,<3,2>∈F, 显然2≠3 不具有传递性: 反例 <2,3.5>,<3.5,5>∈F, 但<2,5>不属于F.设A={a,b,c}, R={,},(1)给出R的关系矩阵;(2)说明R具有的性质(用关系矩阵的判定方法说明理由)【本题合计12分：第（1）小题2分；第（2）小题10分----答对性质得1分，说明理由得1分】 解

(1)R的关系矩阵M(R)为

0 1 1 0 0 0 0 0 0(2)不具有自反性: M(R)的主对角线不是全为1 是反自反的: M(R)的主对角线全为0 不具有对称性: M(R)不是对称的

是反对称的: M(R)对称的位置至多有一个1 是传递的: M(R2)如下

0 0 0 0 0 0 0 0 0 显然满足: 如果M(R2)任意位置为1, 则M(R)对应位置也为1 5 设A≠ø, R⊆A×A, 证明(1)r(R)=R∪IA(2)s(R)=R∪R-1

【本题合计12分，每小题6分----证明格式正确得2分，过程错误一步扣1分】 证明

(1)只要证明r(R)⊆R∪IA和R∪IA⊆r(R)即可 先证r(R)⊆R∪IA:

IA⊆R∪IA

⇒ R∪IA自反(自反性的充要条件)⇒ r(R)⊆R∪IA(自反闭包的最小性)再证R∪IA⊆r(R): R⊆r(R)∧IA⊆r(R)(自反闭包的性质及自反性的充要条件)⇒ R∪IA⊆r(R)得证

(2)只要证明s(R)⊆R∪R-1及R∪R-1⊆s(R)即可 先证s(R)⊆R∪R-1:(R∪R-1)-1=R∪R-1(理由如下: ∀, ∈(R∪R-1)-1

⇔ ∈R∪R-1(逆运算定义)⇔ ∈R∨∈R-1(∪定义)⇔ ∈R-1∨∈R(逆运算定义)⇔ ∈R∪R-1(∪定义, ∪交换律)所以(R∪R-1)-1=R∪R-1)⇔ R∪R-1是对称的(对称性的充要条件)⇒ s(R)⊆R∪R-1(对称闭包的最小性)再证R∪R-1⊆s(R): R⊆s(R)(闭包定义)∧ R-1⊆s(R)(后者理由如下: ∀, ∈R-1

⇔ ∈R(逆运算定义)

⇒ ∈s(R)

⇒ ∈s(R)(s(R)是对称的)

所以 R-1⊆s(R))⇒ R∪R-1⊆s(R)得证 设A={a,b,c,d}, R={,,,,,}, 用Warshall算法求t(R).【本题合计8分】

解 依次求出W0,W1,W2,W3,W4=t(R)【2分】 W0=M(R)=

【1分】 0 1 1 0 0 0 0 0 0 1 0 1 0 1 0 W1=

【1分】 W2=

【1分】 W3=

【1分】 0 1 1 0 0 1 1 0 0 1 1 1 0 0 0 0 0 0 0 0 0 0 0 0 0 1 0 1 0 1 0 1 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 W4= 1 0 1 1

0 1 1

0 1 1

0 1 1 【1分】

即t(R)={,,,,,,,,,,,}.【1分】 设R为A上的自反和传递的关系, 证明R∩R-1是A上的等价关系.【本题合计10分】 证明

自反性: ∀x∈A，xRx∧xR-1x⇒ x(R∩R-1)x【3分】 对称性: ∀x,y∈A，x(R∩R-1)y⇔ xRy∧xR-1y⇔ yR-1x∧yRx⇒ y(R∩R-1)x【3分】 传递性: ∀x,y,z∈A，x(R∩R-1)y∧y(R∩R-1)z⇔ xRy∧xR-1y∧yRz∧yR-1z ⇔(xRy∧yRz)∧(xR-1y∧yR-1z)⇒ xRz∧xR-1z⇔ x(R∩R-1)z【4分】 得证.设A={1,2,3,4}, 在A×A上定义二元关系R, ∀,∈A×A, R⇔u+y=v+x(1)证明R是A×A上的等价关系;(2)确定由R引起的对A×A的划分.【本题合计10分】 解

(1)自反性: ∀∈A×A, R显然成立.【2分】 对称性: ∀,∈A×A, R⇔x+v=y+u⇔u+y=v+x⇔R【2分】 传递性: ∀,,∈A×A, R∧R⇔x+v=y+u∧u+t=v+s⇒x+t=y+s⇔R【2分】 因此R是A×A上的等价关系.(2)根据R的定义, R⇔x+v=y+u⇔x－y=u－v, 因此 []R={|∈A×A∧u－v=x－y},【2分】 所以R引起的划分如下: { { <1,1>,<2,2>,<3,3>,<4,4>}, {<1,2>,<2,3>,<3,4>}, {<2,1>,<3,2>,<4,3>}, {<1,3>,<2,4>}, {<3,1>,<4,2>}, {<1, 4>}, {<4,1>} }【2分】 设R, S是A={1,2,3,4}上的等价关系, 其关系矩阵分别为 【本题合计5分】

11MR00110000100100MS001, 0011001100001.求包含R与S的最小的等价关系.分析: 设包含R与S的最小等价关系为T，则RT, ST, 所以RS T.而T是等价关系，根据等价关系的定义，T应该具有自反性、对称性和传递性。由于R与S是等价关系，具有上述三个性质，由第四节关系运算与关系性质的关系知，RS具有自反性、对称性，但不一定有传递性。为此，需要使RS有传递性。又题目要求T是包含RS的最小等价关系，所以，T应是包含RS且具有传递性的最小关系，从而由传递闭包的定义，T应是RS的传递闭包，即T=t(RS)。如此，只需求出MT=Mt(RS)即可。

11求解过程：MR00110000100100，MS001***100110011000，01所以MRS11MRMS00111000（指对应元素逻辑或），【2分】 0100。【3分】 01故由Warshall算法，MTMt(RS)设R是集合A上的等价关系, |A|=n, |R|=r, |A/R|=t, 证明: rt≥n2.【本题合计5分】 证 设A/R={B1,B2,…,Bt}, |B1|=x1, |B2|=x2,…, |Bt|=xt, 显然有1 xin, xi∈N, 1it.由于A/R是A的划分, 因此 x1+x2+…+xt = n,(1).【1分】

根据Bi是等价类, 对任意s,t∈Bi, 有∈R, 从而

x12+x22+…+xt2 = r,(2)【2分】 根据算术-均方根均值不等式有

x1x2xtt2x12x2xt2