离散数学第三章总结

离散数学第三章总结

离散数学第三章总结 篇1

14.在自然推理系统P中构造下面推理的证明：(2)前提：pq,(qr),r 结论：p(4)前提：qp,qs,st,tr 结论：pq

证明：（2）

①(qr)前提引入 ②qr ①置换 ③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦￢p ⑤⑥拒取式

证明（4）：

①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入

⑤qt ③④等价三段论 ⑥（qt）(tq)⑤ 置换 ⑦（qt）⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理(11)pq ⑧⑩合取

15在自然推理系统P中用附加前提法证明下面各推理：(1)前提：p(qr),sp,q 结论：sr 证明

①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr)前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理

16在自然推理系统P中用归谬法证明下面各推理：

(1)前提：pq,rq,rs 结论：p 证明：

①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢r ④化简律 ⑥r￢s 前提引入 ⑦r ⑥化简律 ⑧r﹁r ⑤⑦ 合取

离散数学第三章总结 篇2

（2011年3月18日）

实验室名称： 离散数学及其应用教育部重点实验室 主管部门： 福建省教育厅 依托单位： 福州大学

实验室概况: 在迅速发展的计算机科学技术及信息技术等领域，离散数学是重要的基础学科和支撑学科，它的发展和应用是影响一个国家科学技术发展水平的重要因素。以福州大学“离散数学与理论计算机科学研究中心”为依托的离散数学及其应用教育部重点实验室于2007年7月获教育部批准立项建设。目前，实验室共有固定研究人员27人，其中教授16人，副教授4人。实验室由马志明院士担任学术委员会主任，范更华教授担任实验室主任。实验室位于福州大学铜盘校区。2007年11月完成了实验室装修一期工程；2009年3月完成了二期装修工程，达到 “环境优美、设备一流”。按国际研究所标准建设基础设施，为每位研究人员及来访学者提供40平米宽敞办公室及一流科研设备。为每位研究生提供一个工作位及台式电脑。已建成无线网覆盖实验室3000平米的科研、办公场所。重视网络建设，保证网络高速畅通。订购相关专业的国外数据库及原版图书，已基本建成一流的专业图书资料室。

一、实验室现有三个研究方向：图论与组合数学、大规模集成电路设计中的数学方法、优化理论与算法。

二、在本，实验室主任范更华教授获全国优秀科技工作者。实验室在研科研项目国家973计划课题1项，国家自然科学基金7项，其中重点项目1项，面上项目6项，新增国家973计划课题1项，为

1.大规模集成电路物理设计中关键应用数学理论和方法（2011CB808003），范更华 新增国家自然科学基金3项，其中面上项目2项，青年项目1项，分别是：

1.超大规模集成电路多目标划分的算法研究（61070020），朱文兴，国家基金面上项目。

2.近景摄影测量中的自动图像分割技术（11071270），王美清，国家基金面上项目。

3.几类图染色问题的研究（11001055），侯建锋，国家基金青年项目。

实验室在2010年8月顺利完成了国家重点基础研究发展计划（973计划）课题“大规模集成电路设计中的图论与代数方法（2006CB805904）”。课题实施期间，课题组共发表研究论文133篇，其中被SCI收录104篇；由于出色完成了该课题，我们将继续承担新一轮的973课题：大规模集成电路物理设计中关键应用数学理论和方法（2011年1月至2015年12月）。

三、实验室不仅是高水平科学研究中心，也是高层次人才培养基地。实验室以应用数学、计算机应用技术省级重点学科，国家集成电路人才培养基地，离散数学“211工程”建设重点学科，应用数学博士点以及两个一级学科硕士点（数学、计算机科学与技术）为支撑，形成具有一定规模的离散数学高层次人才培养体系。实验室将充分利用自身的条件，围绕主攻方向，提升开放层次，促进学术交流与合作，使实验室整体研究水平达到国内领先水平，某些研究方向达到国际先进水平，为国家及福建地方建设做出突出贡献。本培养博士研究生2名，硕士研究生21名。

四、科研成果

实验室在各个研究问题方面开展了深入地研究工作，在课题研究中取得了一些很好的研究结果。本课题组研究成员在国内外重要专业刊物上发表SCI收录论文27篇，EI收录论文6篇，具体研究成果如下：

（1）图论与组合研究工作 关于连通图支撑树的计数问题，给出了连通图支撑树个数的紧的上界，并且考虑的连通度为k的图的支撑树的个数，同时给出了连通图支撑树的个数和图色数之间的关系，其结果发表在《Applied Mathematics Letters》上。

一个图的Laplacian谱半径是指该图Laplacian矩阵的最大特征值，对于图n个顶点，最大度为△，直径为D的非正则图，Shi给出了该图的Laplacian谱半径的上界，我们改进了该上界，并且证明了该上界给出了在某些情况是紧的，同时，给出了不含三角形图的Laplacian谱半径的上界。对于连通二部图，给出了Laplacian谱半径紧的上界和下界，从而改进了Shi的结果。

在图染色领域，考虑了图的列表染色问题，给出了考虑图列表染色的新的思路，并且用该思路证明了某些形式的完全k部图是(2, 2)-total weight choosable，并证明了除了一条边外的所有完全二部图都是(1, 2)-total weight choosable。研究了稀疏图和平面图的列表全染色问题，证明了如果平面图的最大度不超过8，则其列表全色数不超过11；如果平面图最大度至少是8，且不含5-圈，则其列表全色数等于最大度加一；如果图的最大度是4，并且最大平均度不超过3，则其列表全色数是5，该项成果发表在《Information Processing Letters》上。考虑了有向图博弈染色，给出了有向图博弈色数以及弱的博弈色数的定义，证明每个定向平面图的博弈色数不超过9，每个定向外平面图的博弈色数不超过4，同时研究了有向图强博弈染色，证明了每个定向平面图的强博弈色数不超过16。考虑的外平面图的无圈边染色问题，完全确定了外平面图无圈边色数的上界，其结果发表在《Journal of Graph Theory》上。在化学图论方面，一个图的能量是指该图所有特征值绝对值的和，一个图的能量小于图的顶点数，称该图是hypoenergetic，我们研究了图的能量，构造了顶点数为4n+2的树T，使得T是hypoenergetic，从而验证了Gutman等人在2008年提出的猜想，该文发表在《Applied Mathematics Letters》上。同时考虑的图的能量和Estrada指标之间的关系，给出了图Estrada指标紧的上界。（2）VLSI中的图论与优化算法研究工作

为了开展大规模集成电路设计领域的研究工作，实验室于2010年建立了一个150m2的大规模集成电路设计EDA实验室，拥有16个研究工作位，装备国产熊猫EDA系统软件16台套，对所有实验室研究成员和研究生开放使用。

布局是大规模集成电路电路设计重要环节，决定了超大规模集成电路芯片的性能，尺寸，产量和可靠性，我们给出了基于粒子群优化算法新的智能决策，利用该决策可以超大规模集成电路较快的获得一个可行的电路物理布局。同时在遗传算法的变异和交叉的原则中引入了粒子群优化算法，可以使得该算法脱离局部最优和实现更好的多样性。实验通过采用MCNC和GSRC基准测试表明，该算法是有效的。同时该算法可以避免局部最小，并有很好的收敛性。实验结果表明所提出的方法可以大大帮助集成电路设计中的布局决策，其结果发表在《Soft Comput.》上。

从计算的角度来看，超大规模集成电路布局规划是一个NP-困难问题。我们给出了非分层和模块VLSI布图规划问题的一个混合演化算法（HGA），该算法使用一个有效的遗传搜索方法来探索搜索空间和一种有效的局部搜索方法，利用信息在搜索区域。MCNC基准的实验结果表明该算法是有效的。同时，借助于进化算法和模拟退火算法的概念，给出了另外一种混合演化算法，实验表明该算法也是有效的。

（3）优化理论与算法

我们提出了一个高效求解三维装箱问题（Three Dimensional Container Loading Problem 3D-CLP）的混合模拟退火算法；研究了极大可满足性问题的局部搜索算法，提出了用单纯形法产生“初始概率”(每个变量取1的概率)，用“初始概率”对局部搜索算法中变量的初始随机指派进行适当的约束；研究了箱约束非线性整数规划问题，提出了该问题的离散动态凸化算法，同时还证明了算法的收敛性；对非线性约束连续全局优化问题，我们构造一个结合罚函数的辅助函数，构造了解非线性约束连续全局优化的一个动态凸化算法，该算法避免了传统罚函数法中罚参数选取困难的问题。

五、学术交流

为推动福建省数学教育和研究活动开展，在范更华教授的大力倡导下，协同福建省数学会，于2010年10月16日至17日召开福建省首届数学大会，1100多名来自全省各地高校和中学的数学教师参会。为了使基层农村学校数学教师有机会参加会议，在省政府、省教育厅等部门的大力支持下，会议为300名工作在乡镇学校的教师提供了交通、住宿等经费支持。会议期间，“院士与中学教师互动座谈会”和“专家讲座”等专项活动交流和讨论热烈，这种面对面的交流让来自中小学的数学教师受益匪浅、耳目一新，为广大基层学校特别是农村学校教师提供了良好的学习机会，有效地调动了全省中学教师参与数学研究的积极性，对提升福建省数学教育水平起到了积极的推动作用。

2010年5月，实验室协同中国运筹学会，召开中国运筹学会第八届三次常务理事会。

离散数学第三章总结 篇3

鲜花盛开，果实飘香的金秋时节，我们迎来了朝阳小学第三届数学周活动。这既是顺应当前课改要求的教学尝试，同时也是我校“建设和谐校园”的一项重大创新和实践。我们所开展的数学周活动是以“促进学生全面、持续、和谐地发展”为根本宗旨。它的举办将进一步创建良好的数学人文环境，让每一位学生都接受数学文化的熏陶，增强学好数学的信心，在数学魅力的感染下，自觉掀起爱数学、学数学、用数学的热潮，从而全面提高学生的数学文化素养。

在活动内容的设置上老师们既考虑到要适合学生心理、知识水平上的实际情况。还注意尽量与当前学生的数学课内的教学内容有一定联系。时间安排有保障。从星期一至星期五，利用大课间时间进行活动。此次活动在活动内容的设置形式多样。如：

品德教育类型：讲数学家的故事；我国科技成就等。数学家的故事、趣事经过老师、同学娓娓到来,在孩子们幼小的心灵里播下了一颗热爱数学的种子。

计算类型：口算、笔算、简便计算、数字侦探等。计算类型活动版块提高了学生的计算能力。

有关数认识类型：一年级听指令做动作、说说生活中的数等。

空间几何类型：

二、三年级测量物体、七巧板拼图等。七巧板拼图。这项活动学生很感兴趣，很多孩子积极在赛前练习。决赛中以小组合作的形式用七巧板拼出“2008”的字样来迎接明年在北京举办的奥运会，使得七巧板比赛更富有意义。通过拼搭七巧板，使学生发挥出无限创意，体会七巧板的“巧”、“活”、“妙”，感受创造的无穷乐趣。概念类型：二年级抢答乘法口决比赛等。这活动使得学生能在愉悦的氛围中记忆乘法口决。

数学广角类：三年级“我是快乐的小画家”(搭配的学问)、巧算24点等。四年级24点比赛是一项传统的比赛，也是学生最喜欢玩的游戏之一。它教会了学生在闲暇时间如何开展有益的活动，孩子在游戏中练习数学运算，对于那些对数学不感兴趣的孩子来说，不失为一个好方法；对于那些对数学感兴趣的孩子而言，可以更加有效地提高他的运算速度。由于采取的小组合作的方式，使得活动的气氛非常活跃，学生不但能在活动的过程中学会与他人交流合作，还有利于增加集体荣誉感。培养学生做事不轻易放弃的 1

精神。三年级“我是快乐的小画家”考查学生搭配的能力，活动中学生用彩色笔设计出一张张精美的图案，展示出自己聪明才智。

趣味型：高年级数学谜语、中年级古今算谣等。

学科整合型：

五、六年级制作数学手抄报、数学日记、跳蚤市场等。学生的一篇篇日记中体现着探索数学学习的精神；一篇篇数学小论文中渗透着认真和严谨的态度，一次次活动中凝结着智慧和合作的汗水。六年级开展的“周跳蚤市场”活动成了第三届数学周活动最亮丽的一道风景。这次活动打破了时间和空间的限制，把课堂移到了超市让学生感受数学生活化，同时也培养了学生的合作能力。在这一系列活动中，孩子们感受了“数学皇冠”的灿烂，经历了数学探索的过程，体验了数学学习的成功，感受到数学世界的精彩，领略到数学的独特魅力。

评比办法：有个人奖和集体奖；单项奖和综合奖。班级数学之星每班两名，全校共评出34名。年级数学之星，每班一名，全校共评出17名。

活动成效显著。通过活动学生享受学习快乐、感受学科价值、提高实践能力、培养创新精神。

下面将我们第三届数学周活动精彩片断摘记如下：

11月26日，朝阳小学校园内彩旗飘扬，多媒体教室里、教学楼走廊上、各班教室里、学校操场上充满了欢声笑语，贴满了各种数学标语和数学周活动展示材料——“欣赏数学.热爱数学”、“人人学习有价值的数学 人人获得必须的数学”、“我是计算小能手”、“数字侦探”、“跳蚤市场”、“数学谜语竞猜”„„等等。校园内外沉浸在一片欢腾之中。

一年级的小朋友刚入学三个月，很多家长、老师可能还为他们是否适应学习生活发愁。你看有些孩子平时的作业动作慢，对课堂纪律可能还不适应呢，他们会怎么表现呢？别着急，瞧，跑道旁边那不正是一年级小朋友的身影吗？他们正排成马蹄形队列，屏息凝神地注视着老师说口令，心里紧张地数着老师击掌的次数呢！“8可以分成几和几？”老师击了3下掌，第一组马上有一只小手高高地举了起来——“8可以分成3和5！”这时，老师在记分牌上重重地划了一横，“嘢!”第一组的小朋友顿时欢呼起来。你看他们眼睛看得直直的，笑脸涨得红红的，原来数学离他们并不遥远，数学就在游戏中。

哎？哪里来的一帮孩子正拿着尺子和表格，成群结队地到处走，量量这儿，测测那儿？原来是二年级的孩子在进行测量物体这项活动。测量这个工作看起来容易，操作性

强，其实也不简单啊。它求的是速度和精确。你看他们小组合作填表，培养的就是孩子们的团结协作能力和认真严谨的求学精神。这同时还关系着小组的荣誉，就是个别平时对数学不感兴趣的孩子，也积极行动起来了。

而另外一边，三年级正在举行的“数学迎奥运“七巧板拼图赛”，同学们的加油声直冲云霄。老师将两个班分为竞赛队，哪个队能最快地用数个形状不一的七巧板拼出“2008”4个数字，即为取胜。比赛似乎一边倒，其中的一个班很快遥遥领先，他们的亲友团呐喊助威声直冲云霄；而另一个班的同学们小脸甭得紧紧的，小手紧张地选择七巧板的摆放位置，他们的助威团也不敢造次，生怕影响了小选手的思路。

“嘢！我们赢了！”获胜的欢呼声后继而是不服气的声音：“看谁笑到最后，还有两个回合呢！”多媒体教室传来阵阵喧哗声。原来是四年级两个班的孩子在搞数学比赛活动。你玩过巧算24点吗？听说它还是30年前咱们中国人发明的。它的游戏方法很简单：一副扑克牌去掉“大王”、“小王”和超过10以上的牌，任意抽出四张牌，用加、减、乘、除和小括号来计算出24点，每张牌不能不用，但只能用一次。正因为24点玩法既有趣又简单，所以听说曾在美国风靡一时呢。

今天，我们四年级的孩子玩的正是这个游戏。轮到四（1）班的同学了。陈老师用课件出示一组扑克牌，分别是8、6、5、2，刚才的吵闹声顿时消失了，同学们全神贯注地思考着。突然，陈老师说道：“开始”！话筒立刻开始在四（1）班同学当中传递。只听一个同学说：“ 8×(6-5+1)=24”第一个答案出来了，第二个答案紧跟着：（8－2）×5－6也等于24。最后，同学们居然想出了五种方法!计算24点既能锻炼人的计算能力，又很有趣，适合不同程度的孩子参与。看得出，这样的数学活动很受孩子们欢迎。

五年级展出的数学日记，记录了同学们学习数学的有趣过程和收获。五（2）班的郭蕾同学写道，有一天妈妈花20元买了两样水果回来，却忘了苹果的价格。妈妈只记得苹果的重量是2千克，另外，她还买了4千克的梨，每千克2.5元。郭蕾正好学了数学方程，于是她列了一道公式：2X+4×2.5﹦20。好了，按这公式一算——妈妈买的苹果是每千克5元。啊，这就是生活中的数学，原来数学就在看似平常的日常生活当中。

各位去逛商店，估计没见过这么“啰嗦”的招牌：“惊爆价啦„„悠悠球原价80元，降了40%，再加8元！”“小精品，原价4元，现价是原价的3/4”„„哪个商场如此“幽默”？原来是六年级学生举办的跳蚤市场，要求所有的购物者都要先做一道数

学题，才能获得打折优惠。妙趣横生、充满“数学味”的跳蚤市场顿时吸引了同学们，柜台附近围满了老师、家长和同学们，到处是孩子们的欢呼声和尖叫声。

六（2）班一位同学这样卖东西：把价钱告诉顾客后还要这样问：“这个东西打了8折后是15元，请问原价是多少元？答对了才得买。”这样的交易让人忍俊不禁；那边，六（3）班的同学缠上了一位家长，要她买一个1.5元的钥匙扣。家长佯装讨价到1元，同学一听，一算，不卖了：“我们花12元才买进这15个钥匙扣，1元钱一个的话，一个才赚2角钱。那不行！我们还要用这钱给学校爱心基金会捐款呢！” 是啊，谁说学数学没有价值？在那煞有介事的讨价还价中，数学不再枯燥无味，而是妙趣横生了。

既然是“数学周”活动，当然不是一天就能展示完的。在动人心魄的数学周的每一天里，老师和同学们都在丰富多彩的活动中经历数学，感受数学。每天30分钟的口算、笔算竞赛、数学口诀擂台赛，每节课前10分钟的数学谜语竞猜、古今算谣展示、数学故事交流„„等活动都在如火如荼地开展着。以往，许多老师让学生讲数学家故事，学生能收集到的都是“高斯的故事”、“祖冲之的故事”„„几个耳熟能详的老故事。而这次数学周活动，学生在老师轻轻点拨下扩大了资料搜索的范围，不再拘泥于数学家学习数学、发现数学的故事，而是所有关于数学的故事，也包括数学家的生活趣事。你瞧，四年级曾辉同学介绍的就是一个抗日战争时期，游击队员老王数算车轮摩擦铁轨声音，判断火车行进路程的故事。王择奂同学介绍的则是数学家苏步青的爱国故事。在丰富多彩的数学故事中，大家得到的是更多的人文熏陶和互动交流，而不单单是老师传授式的单向的知识传播。

老师和学生都深切地体验到，数学的学习方式可以是丰富多彩的，数学不是束之高阁的文物，更不是只有少数数学专家才能享受到的奢侈品，而是人人可以体验的游戏，人人可以享受的文化，人人都在使用的工具。数学的教学更是与生活息息相关、紧密相连的一湾活水。

一周来，同学们兴致勃勃地穿梭于校园的各个角落，在那里，许多复杂、抽象的数学原理被应用到实际中，非常形象地展示出来。同学们惊叹：原来我们生活中看似平常的事情却蕴含着如此深奥的数学道理，原来这些抽象乏味的原理可以发挥如此巨大的作用为我们人类作贡献。这大大激发了同学们的学习兴趣，纷纷动手参与试验，并尝试着与课本中学到的知识作对比，解释生活中的各种现象，同学们在亲身实践中又快又好的掌握了许多原来所不知道的数学道理。参与、交流、互动、心动„„每一个环节都让同学们震撼，让同学们感到：勤奋、求真、谦虚、严谨是永不变的做人法则。

本次数学周活动得到兴宁区教育局李局长、兴宁区教育局党委马书记、南宁市教科所杨副所长、南宁市教科所教研员黄中南以及兄弟学校的领导和老师的莅临指导，所有来宾对我们的数学周活动给予一致的好评，《南国早报》、《小博士报》还对我们的活动进行报道。第三届数学周成功举办与学校领导和全校老师的大力支持是分不开的。特别是全体数学老师的辛勤付出和出色的组织能力才有学生们的精彩表现，老师们都感慨道：“苦并快乐着，累并充实着”。数学周活动，让孩子们感受到数学是美丽的、有趣的，也是有用的。孩子们在神秘而美丽的数学王国里，扬起智慧的风帆尽情地畅游，个性得到了发展，思维得到了锻炼，才干得到增长。在整个活动过程中,老师人人都是参与者，个个都是策划者，他们用智慧的头脑，创新的思维，先进的理念，执着的追求,无私的奉献，编织出这么绚丽多彩的花朵。孩子，因为他们而幸福快乐；学校，因为他们而美丽动人。

南宁市朝阳小学

离散数学一单元 篇4

一单元测试题

1.将下列命题翻译成符号逻辑形式

（1）银行利率一降低，股价随之上扬。

（2）尽管银行利率降低，股价却没有上升。

（3）占据空间的、有质量而且不断变化的对象称为物质

（4）如果一个整数能背6整出，那么它就能被2或3整除。如果一个整数能被3整

除，那么它的各位数字之和也能被3整除。

2.判断下面各语句是否是命题，如果是命题，说出它的真值。

（1）可导的实函数都是连续函数。

（2）凡是都有例外。

（3）白天比夜晚时间长

（4）两个三角形全等当且仅当它们的对应角相等。

3.简述命题的定义。

4.简述原子命题的定义。

5.下列公式中，（）不是永真式。（单选，写清楚每个属于什么公式）

A.(P∧Q)→QB.P→(P∨Q)

C．（P→Q）↔（~Q→~P）D.(~P∨Q)∧(~(~P∨~Q))

5.下列语句，是命题的有（）（多选）

1）美国的首都是纽约。2）你喜欢日本吗？3）我们一定要解放台湾！

4）所有实数都是整数。3）如果3>2，那么有人不死。

6.构造公式的真值表，判断哪些是永真式，矛盾式，和可满足式

（1）(P→(Q→R))↔((P∧Q)→R)

（2）(P∧(P∧Q))↔~P

（3）~（P∨Q）→R

7.如果P∨QQ∨R，能否判断PR？如果P∧QR∧Q,能否判断PR？如果~P~R能否判断PR。

8．判断下面等式是否是等价式：P→（Q∨R）（P→Q）∨（P→R）

9．求下列两式的对偶式

（1）（P∧~Q）∨（R∧T）∨F

（2）~（P∨~（Q∨R））∧（R∧~Q）

10．分别利用真值表法和等价变换法求下列公式的主合取范式及主析取范式。

（1）P→（R∧（Q→P））

（2）（P→（Q∧R））∧（~P→（~Q∧~R））

11．证明（P→Q）∧（Q→R）P→R

12．证明R→S是{P→（Q→S），~R∨P，Q}的逻辑结果（使用直接法，CP规则法，和反证法）

13．求公式（P→（R∨P））∧（Q ↔P）的主合取范式和主析取范式。

中大复试离散数学 篇5

1)R是A上的一个对称和传递的关系,对于任意a属于A,都存在一个b属于A,使得属

于R,证明R是一个等价关系。

2)是一个半群,对于任意a, b属于G,a!=b,则a*b!=b*a。试证:对任一元素a属于

G,有a*a=a。

3)证明一个图G,它顶点的最小顶点度不小于2,证明它存在圈。4)求(PVQ)<->P主析取范式。

04 年

8．证明对于集合A、B、C，如果有A∩B=B∩C，并且A∩B=A*∩C，其中A*为A的补集，则一定有B=C。（10分）。9．证明：一个连通且每个顶点的度数都为偶数的图一定没有割边。（10分）

10．设代数系统（G，*）为一个半群，且有左单位元e，对于任意一个x均有x’,使得x’*x=e。证明：对于任意a、b、c，如果b*a=b*c，则一定有a=c。（15分）11．根据已知前提，证明如下结论（10分）前提：P ┑RVP, Q 结论：R

11年

离散总共五道题，第一道关于一阶逻辑求主析取范式、主合取范式、真值表(只要看了书，计算细心点，这道题一般能拿满分）

第二道对循环关系有如下定义：对于A上的关系R，若对任意属于R且属于R，则属于R.证明：R是自反和循环关系当且仅当R是等价关系。（我当时不知道什么是循环关系，悲剧了）

第三道考得是集合的求解，思想与课本上的200能被3、5、7整除解法类似，（文氏图法或都公式法）

第四道考得Dijkstra算法，初试数据结构是重点章节，问题不大

08离散数学试题 篇6

一、填空（共36分）

1、命题公式PQ的真值为假，当且仅当。

2、设F(x)：x是整数，G(x):x是自然数，则命题“并不是每个整数都是自然数”符号化为。

3、设10阶平面图G有5个面，则G中有条边。

4．设A={1，2，3，4，5，6，7}，R是A上的模4同余关系，则关系R＝。

5．六阶循环群的所有生成元为，所有子群为。

6．设集合Sa,b,c，S上所有互不相同的等价关系的数目为。

7．R是非空集合上的偏序关系，当且仅当R具有

8．仅用联结词来表示PQ为。

二、解答题（共24分）。

1． 求等价于下面公式的前束合取范式与前束析取范式。（10分）xPxyzQx,y(z)R(y,x)

2． 整数集合Z上的二元运算*定义为x*y判断Z,*是不xy2，是群？如果是，求出它的单位元以及每个元素的逆元。（8分）

3． 设A,B,C是三个集合，函数f:AB，函数g:BC。若函数

gf:AC是双射，则f和g一定都是双射函数吗？若是，请给出证明；若否，请举例说明。（6分）

三、证明题（共40分）

1．（10分）构造下面推理的证明（个体域取学生的集合）：

每个一年级学生至少有一个高年级学生作他的辅导员。凡理科学生的辅导员皆是理科学生。小王是理科一年级学生。因此，至少有一个理科高年级学生。

2．（8分）证明在至少含有3个节点的简单连通平面图中，至少有一个节点的度数小于等于5。

3．4． 证明命题的等价关系：证明在无向完全图Kn

顿图。（6分）

5． 设G为群，PQPQPQ（8分）n3中任意删去3条边后，所得到的图是哈密f:GG，xG有fxx1。证明当且仅当G是

离散数学学习心得 篇7

姓名：周燕

班级：12计本（2）班

学号：1204012032

当老师说这门课快要结束的时候，我才发现这门课的学习以经接近尾声了。通过这一学期的学习，我觉得离散数学是一们很有意思的课程，不同于以往学习数学类知识的大量的运算，离散数学更多的是培养逻辑推理方面的，掌握基本的方法并加以运用就能很好地掌握。下面我来整理一下我这个学期的学习思路。

第一章学习的是命题逻辑的基本概念，介绍了命题的定义，连接词以及命题公式的赋值。然后学习了命题逻辑的等值演算，等值式即两个命题公式为重言式。判断等值式的方法通常有列真值表，等值演算等。本章还给出了命题公式的两种规范的表示方法。析取范式和合取范式，本章还介绍了连结词的完备集。第三章介绍的是命题逻辑的推理理论，在自然推理系统中，命题的推理证明。第四章是对前面推理证明的补充与完备，前三章中，命题逻辑具有一定的局限性，有时候无法判断一些常见的简单推理，于是我们引进了一阶逻辑命题。第五章便是一阶逻辑等值演算的推理。第二部分学习集合论，介绍了集合论的基本概念，集合的运算集合恒等式，第七章关于二元关系，关系的性质，着重介绍了自反性，对称性，传递性。第三部分学习图论，图的基本概念，通路与回路，以及图的连通性，然后学习了树，树的性质树的生成。最后是代数系统。

以上就是本学期离散数学学习的所有内容，很开心能有华老师带我们学习离散数学。华老师可以说是我上大学以来遇到的最负责任的老师了，教书很认真，每次上课声音都很洪亮，可以照顾到后座的同学。最喜欢老师的幽默了，大学的学生并不再是高中时候埋头苦干的书呆子了，很需要在课堂上调动学生的学习兴趣。所以我很支持老师能够将刻板的知识讲解的精彩生动，偶尔的幽默是很好的方法。

离散数学历年考试证明题 篇8

证明：

设S=A∩(B∪C)，T=(A∩B)∪(A∩C)，若x∈S，则x∈A且x∈B∪C，即 x∈A且x∈B 或 x∈A且x∈C，也即x∈A∩B 或 x∈A∩C，即 x∈T，所以ST．

反之，若x∈T，则x∈A∩B 或 x∈A∩C，即x∈A且x∈B 或 x∈A且x∈C，也即x∈A且x∈B∪C，即x∈S，所以TS． 因此T=S．

2、试证明集合等式A(BC)=(AB)(AC)．

证明：设S= A(BC)，T=(AB)(AC)，若x∈S，则x∈A或x∈BC，即 x∈A或x∈B 且 x∈A或x∈C．

也即x∈AB 且 x∈AC，即 x∈T，所以ST．

反之，若x∈T，则x∈AB 且 x∈AC，即x∈A或x∈B 且 x∈A或x∈C，也即x∈A或x∈BC，即x∈S，所以TS．

因此T=S．

3、试证明（x）（P（x）∧R（x））（x）P（x）∧（x）R（x）．

证明：

（1）（x）（P（x）∧R（x））P（2）P（a）∧R（a）ES(1)

（3）P（a）T(2)I（4）（x）P（x）EG(3)

（5）R（a）T(2)I（6）（x）R（x）EG(5)

（7）（x）P（x）∧（x）R（x）T(5)(6)I4、设A，B是任意集合，试证明：若AA=BB，则A=B．

证明：设xA，则AA，因为AA=BB，故BB，则有xB，所以AB． 设xB，则BB，因为AA=BB，故AA，则有xA，所以BA． 故得A=B．

5、设G是一个n阶无向简单图，n是大于等于2的奇数．证明G与G中的奇数度顶点个数相等(G是G的补图)．

证明：因为n是奇数，所以n阶完全图每个顶点度数为偶数，因此，若G中顶点v的度数为奇数，则在G中v的度数一定也是奇数，所以G与G中的奇数度顶点个数相等．

6．设连通图G有k个奇数度的结点，证明在图G中至少要添加

欧拉图．

证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．

又根据定理4.1.1的推论，图G是欧拉图的充分必要条件是图G不含奇数度结点．因此只要在每对奇数度结点之间各加一条边，使图G的所有结点的度数变为偶数，成为欧拉图． 故最少要加k条边才能使其成为2k条边到图G才能使其成为欧拉图． 2

7．设R是集合A上的对称关系和传递关系，试证明：若对任意aA，存在bA，使得R，则R是等价关系．

证明：已知R是对称关系和传递关系，只需证明R是自反关系．

aA，bA，使得R，因为R是对称的，故R；

又R是传递的，即当R，R R；

由元素a的任意性，知R是自反的．

所以，R是等价关系．

8．若非空集合A上的二元关系R和S是偏序关系，试证明：RS也是A上的偏序关系．

证明：.① xA,x,xR,x,xSx,xRS，所以RS有自反性；②x,yA,因为R，S是反对称的，x,yRSy,xRS(x,yRx,yS)(y,xRy,xS)(x,yRy,xR)(x,ySy,xS)xyyxxy 所以，RS有反对称性．

③x,y,zA，因为R，S是传递的，x,yRSy,zRS

x,yRx,ySy,zRy,zS

x,yRy,zRx,ySy,zS

x,zRx,zSx,zRS

所以，RS有传递性．

总之，R是偏序关系．

9．试证明命题公式(P(QR))PQ与（PQ）等价．

证明：(P(QR))PQ

(P(QR))PQ(PQR)PQ

(PPQ)(QPQ)(RPQ)

(PQ)(PQ)(PQR)PQ（吸收律）

(PQ)（摩根律）

10．试证明（x）（P（x）∧R（x））（x）P（x）∧（x）R（x）．

证明：（1）（x）（P（x）∧R（x））P

（2）P（a）∧R（a）ES(1)（3）P（a）T(2)I

（4）（x）P（x）EG(3)（5）R（a）T(2)I

（6）（x）R（x）EG(5)（7）（x）P（x）∧（x）R（x）T(5)(6)I

11．若无向图G中只有两个奇数度结点，则这两个结点一定是连通的．

证明：用反证法．设G中的两个奇数度结点分别为u和v．假设u和v不连通，即它们之间无任何通路，则G至少有两个连通分支G1，G2，且u和v分别属于G1和G2，于是G1和G2各含有一个奇数度结点．这与定理3.1.2的推论矛盾．因而u和v一定是连通的．

12．设G是一个n阶无向简单图，n是大于等于2的奇数．证明图G与它的补图G中的奇数度顶点个数相等．

证明：设GV,E，V,E．则E是由n阶无向完全图Kn的边删去E所得到的．所以对于任意结点uV，u在G和G中的度数之和等于u在Kn中的度数．由于n是大于等于2的奇数，从而Kn的每个结点都是偶数度的（n1(2)度），于是若uV在G中是奇数度结点，则它在G中也是奇数度结点．故图G与它的补图G中的奇数度结点个数相等．

13．设连通图G有k个奇数度的结点，证明在图G中至少要添加

欧拉图． k条边才能使其成为2

证明：由定理3.1.2，任何图中度数为奇数的结点必是偶数，可知k是偶数．

离散数学第三章总结 篇9

《离散数学》复习大纲

考试时：允许带计算器，不允许带手机。

题型：单选题（10个*2分=20分），填空题（5个*3分=15分），大题（8个，每个分值不等，共计65分）

绪论

1、判断一句话是否是命题（P2）

2、绘制真值表（P2,P3,P4,P5）

第1章：集合1.掌握以下概念：元素、集合、子集，元素与集合的关系（属于或不属于），集合之间的关系（包含于或不包含于）。

2.求幂集，计算幂集的基数。（P28—34，P28—35，P28—36，P28—37，P28—38）

3.利用文氏图求集合的基数（P29—60，P28—48）

第2章：关系与函数

1.判断某个映射是否是函数（P43），判断某个函数是否有反函数（P52—33）

2.判断某个关系是否具有自反性、对称性、反对称性、传递性（P50—13）

3.等价关系与划分之间的转换（P50—13）

第3章：布尔代数

1.求出某个布尔代数中某个定理的对偶定理（P74）

2.十进制、二进制、八进制之间的转换（P78，P82—14，P82—15，P82—19）

3.根据电路图，写出布尔表达式，对布尔表达式进行化简，画出简化之后的电路图。（P84—53，P85—54）

第4章：自然数与归纳法：

1、使用数学归纳法进行等式、不等式、整除式的证明（P122—2，P122—3，P122—6，P122—8，P122—11，P124—39，P123—22，P124—40）

第5章：数论

1.使用欧几里德算法进行反推（P152—例子）

2.求解模数方程（P166—9，P166—10）

3.位移加密、摩尔加密的加密解密过程（P167—26，P167—27，P167—28，P167—30）

4.5.6.7.利用快速求幂算法计算余数（P167—25）求解欧拉函数Φ函数（P166—16）利用欧拉函数Φ函数进行因式分解（P166—15）RSA加密的加密解密过程（P167—31，P167—32）

第6章：递归：

1、使用折半查找法在某个指定数组中查找某个元素时，得出查找成功或者不成功的结果时经历的查找过程。（P207—例子）

第7章：递归式求解：

1、递归式求解（P234—5，P234—6，P234—11）

第8章：计数：

1、当从一幅标准扑克（52张）中选出一手牌（5张）时，计算出这手牌呈现某种特点（例如：一对、两对、一滚、一连、一滚加一对、同花、顺子、同花顺等等）的概率。（该题可能需要使用计算器）（P252）

第9章：矩阵

1.矩阵加法（P276—方框）

2.矩阵乘法（P277—最后的例子）

3.给出与方程组对应的矩阵方程（P280—方框）

4.矩阵对应的行列式的值（P282—第一个矩阵，P282—方框）

5.利用克莱姆法则求解方程组（P283—例子，P283—方框）

6.利用矩阵加密解密，其中要用到高斯消去法（P287，P288，P289）

第10章：图论

1.欧拉路径和欧拉回路的判断（P329—图）

2.判断图形是否能“一笔画出”（P329—图）

3.利用Prim算法求出最小生成树（P330—图，P332—4，P332—13）

4.利用Kruskal算法求出最小生成树（P330—图，P332—4，P332—13）

离散数学证明方法有哪些 篇10

康托尔在1874年和1891年分别用两种不同的方法，证明了实数集是不可数集。其中1891年所用的方法更加为人所熟知，又被称为对角线法。证明发表之后，这种方法在数理逻辑中获得广泛应用。

对角线法证明实数集不可数的大致思路如下：显然实数集不是有限集。反设实数集和自然数集之间存在一个双射，设自然数0对应的实数是a0，1对应实数a1，2对应a2，……i对应ai。注意任意实数可以地表示为不以无限多个9结尾的十进制小数，可设aij为ai小数点后的第j+1位。