离散数学试卷与答案

离散数学试卷与答案（通用9篇）

离散数学试卷与答案 篇1

《离散数学》试题及答案

一、选择题：本题共5小题，每小题3分，共15分，在每小题给出的四个选项中，只有一项是符合题目要求的。

1.命题公式(PQ)Q为()

(A)矛盾式(B)可满足式(C)重言式(D)合取范式

2．设P表示“天下大雨”，Q表示“他在室内运动”，则命题“除非天下大雨，否则他不在室内运动”符号化为（）。

(A)． PQ；(B)．PQ；(C)．PQ；(D)．PQ．

3.设集合A={{1,2,3}, {4,5}, {6,7,8}}，则下式为真的是()

(A)1A(B){1,2, 3}A

(C){{4,5}}A(D)A

4.设A＝{1,2},B={a,b,c},C={c,d}, 则A×(BC)=()

(A){<1,c>,<2,c>}(B){,<2,c>}(C){,}(D){<1,c>,}

5.设G如右图：那么G不是().(A)哈密顿图；(B)完全图；

(C)欧拉图；(D)平面图.二、填空题：本大题共5小题，每小题4分，共20

6.设集合A={,{a}}，则A的幂集P(A7.设集合A={1,2,3,4 }, B={6,8,12}, A到B的关系R＝{x,yy2x,xA,yB},那么R1＝－

8.在“同学，老乡，亲戚，朋友”四个关系中_______是等价关系.9.写出一个不含“”的逻辑联结词的完备集.10.设X＝{a,b,c}，R是X上的二元关系，其关系矩阵为

101，那么R的关系图为 MR＝100100

三、证明题（共30分）

11.（10分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)

12.（10分）构造证明：(P(QS))∧(R∨P)∧QRS

（0,1）13.（10分）证明与[0,1)，[0,1)与[0,1]等势。

四、解答题(共35分)

14.（7分）构造三阶幻方（以1为首项的9个连续自然数正好布满一个33方阵，且方阵中的每一行, 每一列及主、副对角线上的各数之和都相等.）

15.（8分）求命题公式(PQ)(PQ)的真值表.16.（10分）设R1是A1＝{1,2}到A2＝(a,b,c)的二元关系，R2是A2到A3＝{,}的二元关系，R1= {<1,a>,<1,b>,<2,c>}, R2={,}

毕节学院《离散数学 》课程试卷

求R1R2的集合表达式.17.（10分）某项工作需要派A、B、C和D 4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？

三个条件：(1)若A去，则C和D中要去1个人；(2)B和C不能都去；

(3)若C去，则D留下。

一、单项选择题(每小题3分，共15分)

1.B2.C3.C4.A5.B

二、填空题(每小题4分，共20分)

6.{,{},{{a}},{,{a}}}

7.{<6,3>,<8,4> }8.老乡

9.{,}或{,} 或 {}或 {}

10.见

f(0)0111························································································ 10分 ,n1,A ·f()n1nn

f(x)x,x[0,1)A

14.85 1 2 7 6

填对每个格得1分。

15.表中最后一列的数中，每对1个数得2分.11016.MR1,(2分)001

MR201(4分)0100

010101(6分)0000110 MR1R2001

R1R2{1,}(10分)

17.解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。······························································································ 2分 因此(ACD)∧(B∧C)∧(CD)

(A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D)

(A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D))

(A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D)

∨(C∧ D∧B∧C)∨(C∧ D∧B∧D)∨(C∧ D∧C)∨(C∧ D∧C∧D)

∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D∧C∧D)

F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F

(A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D)

(A∧C)∨(B∧C∧ D)∨(C∧D)

T ··································································································································· 8分

毕节学院《离散数学 》课程试卷

故有三种派法：B∧D，A∧C，A∧D。······································································· 10分

毕节学院《离散数学 》课程试卷

离散数学试卷与答案 篇2

一、知识点归纳与总结

根据本课程特点, 在授课时要前后呼应, 使学生形成一种离而不散的知识结构。例如:讲授代数结构时候, 在集合、关系、函数等概念的基础上, 研究更为复杂的对象———代数结构。在授课时要讲透重点和难点, 应该注重知识点的归纳与总结, 使所学知识融会贯通, 这不但是了解知识体系的手段, 也是促使学生养成深入钻研的习惯和培养开拓创新能力的必要步骤。

二、选择典型例题

离散数学中有些抽象的概念、结论和证明, 学生反映较慢。如何选取适合学生的典型例题很关键, 通过教学实践总结如下:例题选择应该适合教学, 即简单清晰有启发性, 并且密切结合定义和定理应用, 结合计算机科学与技术应用背景, 尽量与计算机专业课内容相关。

三、知识背景

对离散数学中某些理论的提出来源、解决的实际问题和最新发展方向进行适当介绍, 提高学生学习兴趣并且使学生对相关理论有感性认识。如:数理逻辑内容应用到形式语义学和人工智能。讲集合的时候跟学生介绍康托尔, 讲关系的时候介绍笛卡尔。集合论中的二元关系是研究关系数据库的一种重要方法, 在研究实体集中的域和域之间的可能关系、关系操作、关系分解的无损连接性分析、连接依赖等问题都用到其中的理论。

四、教学方法

虽然计算机网教平台提供了良好的辅助教学空间, 但根据离散数学自身的特点 (理论性强, 逻辑性强) , 如果把公式推导及定理证明过程也以幻灯片的形式显示出来, 教师只是看着屏幕讲, 学生就只是在看证明, 而不会追踪教师的思维过程, 这种教学虽然方便了教师授课, 但是不利于学生数学能力的培养。所以离散数学的教学, 笔者建议应以板书讲解为主、课件演示为辅。

五、引入实验

在离散数学教学中, 绝大多数院校只重视理论教学, 很少开设或根本不开设上机实验课, 导致学生不知道学这门课的原因和目的。根据计算机专业的教学安排, 一般要求学生掌握离散数学中的数理逻辑、集合论、代数结构和图论四大部分, 针对每一部分的主要内容选择一个有代表性的实验。如, 第一部分引入真值表的求解方法及其在解决命题逻辑中的应用方面的实验。第二部分引入理解集合的运算规则、关系、函数性质的判定和等价关系构造等方面实验。第三部分引入代数系统在纠错码方面的应用。第四部分熟悉图在计算机上的表示和运算方法, 且能够解决图论实际应用问题方面的实验。

六、结束语

总之, 要把“离散数学”这门课教好, 因素很多, 但作者认为最主要的有以下两点: (1) 教师要有较深厚的专业理论知识基础, 这样讲课时才能融会贯通, 才能引入相关实际案例, 才能使学生明确相关知识在后续课中的应用, 才能使离散数学理论与计算机科学发展方向相辅相成, 紧密结合。 (2) 引入相关实验, 使学生把抽象理论与程序设计联系起来, 加深对理论的理解与应用。从而培养学生主动学习的兴趣、追踪新科技的能力, 以适应计算机科学发展的需要。

参考文献

[1]耿素云, 屈婉玲.离散数学[M].北京:高等教育出版社, 2008.

[2]左孝凌, 李为, 刘永才.离散数学[M].上海:上海科学技术出版社, 1982.

[3]李盘林, 李丽双等.离散数学[M].北京:高等教育出版社, 2008.

[4] (美) Kenneth H Rosen.Discrete Mathematics and itsapp lica-tions[M].北京:机械工业出版社, 2003.

[5]吕国英, 梁吉业.“离散数学”教学模式探讨[J].高等理科教育出版社, 2008.

离散数学创新教学设计与实践 篇3

关键词：离散数学；教学设计；创新思维；任务驱动

G642.4

一、引言

离散数学（Discrete mathematics）是研究离散结构和离散数量相互关系的数学学科，是现代数学的一个重要分支。它是计算机专业基础理论的核心课程，同时也是很多专业课程的先修课，比如高级语言程序设计、数据结构、操作系统、编译原理、数据库、算法设计与分析等。在计算机科学中离散数学中的基本概念、基本思想和方法被普遍采用。例如，集合论的概念和方法，代数的概念和方法等。所有这些都使得离散数学在计算机科学中的地位和作用越来越重要，成了必不可少的工具，因此有人把离散数学称为“计算机数学”。在计算机科学中，离散数学有两个主要用途：一是描述计算机科学理论、方法和技术的主要工具，为理论计算机科学提供坚实的基础；二是为形式描述技术奠定数学基础，而形式描述技術则是描述和验证计算机系统的数学表示方法[1]。因此，学好离散数学对计算机后续专业课程的学习发挥着重的作用。

二、传统教学设计

（一）传统授课过程

①撰写教案：确定教学目标、教学参考、教学重难点；

②教学过程的实施：传统授课，板书及多媒体教学辅助；

③课后作业；

④教学反思。

（二）传统教学实施过程的不足

1.教材内容抽象，数学味浓。教学内容是纯数学理论，在习题上的设置也大多是计算或证明，这对学生来讲，理论性太强，不太好调动学生的学习兴趣。

2.教学形单一枯燥。采用传统的授课方式，老师的传统理论讲解，利用板书向同学传授数学原理，最多加之幻灯片辅助。定义、定理、计算、证明等教学内容充实了整个课堂，课后布置一定量的作业，这样单一的传统教学过程无法激发学生的兴趣，教学效果也就无法显现。

3.课程考核传统。离散数学课程考核学大多采用传统的闭卷考试方式，不能很好的体现学习过程的考核，这样无法体现学生的学以致用能力和实践动手能力，无法真正体现计算机专业基础课的特点，为后续专业课程的服务也就无法突显。

三、基于任务驱动的创新教学设计

基于任务驱动教学模式强调以学生为中心，强调学生的学习过程必须与学习任务相结合，通过完成任务来激发学生的兴趣和动机。根据任务驱动式教学过程的 3 个要素——教师、学生、任务，利用驱动的理论基础提出 教师经过1：课前准备 2：任务设计 3：任务分配 4：实施任务 5：监督指导 学生经过1：课前预习 2：接受任务 3：明确任务 4：执行任务 5：完成任务 6：共享交流 最后老师学生相互进行反思评价。基于这样的任务驱动式教学模式，加强学生计算思维的培养。

该模式在任务驱动的主线下把教师的教学活动和学生的学习活动以任务为主线贯穿起来，通过任务来驱动教学活动，并在整个教学活动中贯穿计算思维的一系列方法：递归、抽象、分解、在不确定性情况下的规划和利用启发式的推理来寻求解答等，通过教学内容的选择、教学过程设计和教学评价体系的构建实现对计算思维能力的培养[2]。

四、创新教学设计的实施过程

（一）准备工作

教师课前准备，要对教学内容进行任务设计，确定教学目标、教学任务、教学预期效果，对任务进行总体策划，收集整理相关资料。学生要根据教师的上次课要求进行课前预习，阅读相关参考资料，了解命题公式及分类的基本教学内容。教师结合授课内容，组织授课只是层次模块，方便激发学生的学习兴趣和计算思维[3]。

（二）教学设计的实施过程（以命题逻辑为例）

1.学生分组：根据班级规模将班级分成4个学习小组，每组选出一位小组长。

2.问题设计：教师结合问题的应用领域设计相关问题并创设问题情境，呈现问题。教师针对命题逻辑部分内容的教学给出一个理论练习和一个生活中的问题：a）构造真值表判定公式类型；b）“楼梯的灯由上下2个开关控制， 要求按动任何一个都能打开或关闭灯，试设计一个这样的线路。”（此处需同学查找资料，门电路符号，与门、或门和非门）。设p，q为开关的状态，F：灯的状态，打开为1， 关闭为0。不妨设当2个开关都为0时灯是打开的，根答案可得： F=m0∧m3= （x∧y）∨（x∧y）。（解题过程对学生屏蔽）

3.接受任务：小组长代表小组接受教师安排的任务，明确任务，查阅教材及相关的资料。

4.任务执行：小组分工协作，逐项完成任务。小组学习记录任务完成的全过程，真值表和应用题解题过程。

5.小组长集中，教师分别检查各组任务的执行情况，分享过程和心得，小组对各组的任务给出量化评分，这样会激励各组在后期的任务学习过程中投入更多的精力去准备，当然，在这个过程中就掌握了知识和技能，这种不是教师灌输式的教学，效率高，效果好。

6.最后10分钟进行课堂小结和教学反思，布置下次课教学任务。

五、结束语

作为一门计算机的专业基础课《离散数学》在计算机学科领域中发挥了重要的作用。如何培养学生学习兴趣和学习效果，是每位教师需要多加思考的问题，结合多年工作经验，对本课程的创新教学设计和实践取得了明显的效果，然而学生的计算思维能力需要长期不断地培养积累和沉淀，但我们要坚定培养目标，在探索中提高、在提高中不断总结，争取更好地效果。

参考文献：

[1]屈婉玲，耿素云，张立昂.离散数学[M].北京：高等教育出版社，2008年3月：1-10.

[2]牟琴，谭良，周雄俊.基于计算思维的任务驱动式教学模式的研究[J].现代教育技术， 2011年第21卷第6期：45-49.

[3]路美秀，王玉山，巫小蓉.“离散数学”教学中计算思维能力的培养[J].计算机教育，2013年3月10日，第5期：47-58.

离散数学习题三 含答案 篇4

11、填充下面推理证明中没有写出的推理规则。前提：pq,qr,rs,p 结论：s 证明：①

p

前提引入 ②pq

前提引入

③

q

（①②析取三段论）④qr

前提引入

⑤

r

（③④析取三段论）⑥rs

前提引入

⑦

s

（⑤⑥假言推理）

12、填充下面推理证明中没有写出的推理规则。前提：p(qr),q(rs)结论：(pq)s

证明：①(pq)

（附加前提）②

p

（①化简规则）③

q

（①化简规则）④p(qr)

前提引入 ⑤qr

（②④假言推理）⑥

r

（③⑤假言推理）⑦q(rs)

前提引入 ⑧(rs)

（③⑦假言推理）⑨

s

（⑥⑧假言推理）

13、前提：(pq)q,pq,rs

结论1：r 结论2：s 结论3：rs

（1）证明从此前提出发，推出结论1，结论2，结论3的推理都是正确的。（2）证明从此前提出发，推任何结论的推理都是正确的。证明：（1）①(((pq)q)(pq)(rs))r

((pq)q)(pq)(rs))r1 ②(((pq)q)(pq)(rs))s

((pq)q)(pq)(rs))s1

③(((pq)q)(pq)(rs))(rs)

((pq)q)(pq)(rs))rs1

即结论1，结论2，结论3的推理都是正确的。

（2）((pq)q)(pq)(rs)

((pq)q)(pq)(rs)(pqq)(pq)(rs)0(pq)(rs)0

即推任何结论的推理都是正确的。

14、在自然推理系统P中构造下面推理的证明：（1）前提：p(qr)，p,q 结论：rs

证明：①p(qr)

前提引入 ②

p

前提引入 ③

(qr)

① ②假言推理

④

q

前提引入 ⑤

r

③ ④假言推理 ⑥

rs

⑤ 附加律

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

结论：sr 证明：

①

s

附加前提引入 ②

sp

前提引入 ③

p

① ②假言推理 ④

p(qr)

前提引入 ⑤

qr

③ ④假言推理 ⑥

q

前提引入

⑦

r

⑤

⑥假言推理 即根据附加前提证明法，推理正确。

16、在自然推理系统P中用归谬法证明下面的推理： 前提：pq，qr,qs 结论：rs 证明：

①

(rs)

结论否定引入 ②

pq

前提引入 ③

qr

前提引入 ④

qs

前提引入

⑤

rs

② ③ ④构造性二难 ⑥

(rs)(rs)

① ⑤

合取

因为⑥为矛盾式即推理正确

17、在自然推理系统P中构造下面推理的证明：

只要A曾到过受害者房间并且11点以前没离开，A就是谋杀嫌犯。A曾到过受害者房间，如果A在11点以前离开，看门人会看见他。看门人没有看见他。所以，A是谋杀嫌犯。

答：令p: A到过受害者房间

q: A在11点以前离开

r: A是谋杀嫌犯

s: 看门人看见过A 前提：(pq)r,p,qs,s 结论：r 证明：① qs

前提引入 ②

s

前提引入 ③

q

① ②拒取式 ④

p

前提引入 ⑤

pq

③ ④合取 ⑥(pq)r

前提引入 ⑦

r

⑤

⑥假言推理

1114490009

离散数学三、四章检测题及答案 篇5

一、填空题（每空2分，共40分）

1．若集合A的基数为n，则AP(A)。n2n

２．设A=｛｛，｛｝｝｝，则A×P(P())=。其中P(A)表示集合A的幂集．{{,{}},,{,{}},{}}

3．设A{{a,{b,c}}}，则P(A)=。其中

P(A)表示集合A的幂集．{,{{a,{b,c}}}}

4．设A={1，2，3}，A上的二元关系R={1,1,1,2,1,3,3,3}，则关系R具有性。反对称，传递。



5．设R是集合A上的二元关系，则S(R)=，t(R)=。RR1；

i1R i

6．设R是集合A上的具有自反性、对称性、反对称性和传递性的二元关系，则



10（IA，R=，R的关系矩阵是。001000或单位矩阵）1

7． 在偏序集A,中，其中A={1,2,3,4,6,8,12,14}，≤是A中的整除关系，则集合B={2,3,4,6}的极大元是 4,6，极小元是2,3，最大元是无，最小元是无，上确界是12，下确界是1。

8．设A{{},},}1{0,B, 所有从A到B的双射函数是f

1{,0,{},1,f2{,1,{},0。

9．设f是A到B的函数，如果对x1,x2A,x1x2，都有f(x1)f(x2)，则称f为，如果ran(f)B，则称f为 f，则称f为双射。当f为双射时，f

f11是B到A的函数，且ff1f=。（单射，满射；既是单射又是满射； IB； IA）

二、单项选择题（每小题2分，共20分）

1．设R1和R2是集合A上的任意两个关系，则下列命题为真的是（）．(1)

(1)．若R1和R2是自反的，则R1R2也是自反的；(2)．若R1和R2是非自反的，则R1R2也是非自反的；(3)．若R1和R2是对称的，则R1R2也是对称的；(4)．若R1和R2是传递的，则R1R2也是传递的．

２．集合A上的关系R为一个偏序关系，当且仅当R具有（）。(2)(1)．自反性、对称性和传递性；(2)．自反性、反对称性和传递性；(3)．反自反性、对称性和传递性；(4)．反自反性、反对称性和传递 ３．集合A上的关系R为一个等价关系，当且仅当R具有（）。(1)(1)．自反性、对称性和传递性；(2)．自反性、反对称性和传递性；

(3)．反自反性、对称性和传递性；(4)．反自反性、反对称性和传递性

４．集合A上的等价关系R，其等价类的集合｛aRaA｝称为（）．(3)

(1)．A与R的并集，记为A∪R；(2)．A与R的交集，记为A∩R；(3)．A与R的商集，记为A／R；(4)．A与R的差集，记为A－R．

５．设集合A{0,1,2,3}，R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3,>}是A上的二元关系，则R的关系矩阵MR是()。（2）

11（1）．00

0100

1001

0100（2）.11

10

0010

1100

00

11（3）.00

11

0011

0101

11

00（4）.01

01

1000

1101

0

110

６．设A{1,2,3,4,5,6},B{a,b,c,d,e}，以下哪一个关系是从A到B的满射(2)。

(1)．R{a,2,b,3,c,4,d,5,e；(2)．R{e,2,d

3,c,4,b,5,a,6,e；

(3)．R{a,2,b,3,c,4,a,5,b,6,c ；(4)．R{a,2,b,3,c,4,d,5,e,b ．

7．设A{a,b,c}，集合A上的等价关系R所确定的A的划分的是{{a},{ b, c }}，则

R=(1)

（1）． {< a, a>,,,,}（2）．{< a ,b>,,,}

（3）．{< a ,b>,,}（4）．{< a, a>,< a ,b>,,,,} 8．设Z为整数集，f：ZZ，f(i)i(mod3)，则f是（）．（3）

(1)．是入射不是满射；(2)．是满射不是入射；(3)．既非入射也非满射；(4)．是双射． 9．设f,g,h是集合A上的任意函数，下列哪个命题是真命题（）．（3）

(1)． fggf ；(2)．fff；(3)．f(gh)(fg)h；(4)．fgh．10．设A{1,2,3},B{a,b}，下列二元关系R为A到B的函数的是(1)

(1)．R{a,2,a,3,a ；(2)．R{a,2,b；

(3)．R{a,b,2,a,3,a ；(4)．R{a,1,b,2,a,3,b ．

三、简答题（共30分）

1．（6分）设A={1,2,3,5,6,10,15,30}，“／” 为集合A上的整除关系。〈A，／〉是否为偏序集?若是，画出其哈斯图；

解：〈A，／〉是偏序集。其哈斯图为：

2．（12分）对下图所给的偏序集A,，求下表所列集合的上（下）界，上（下）确界，并将结果填入表中。

3．（6分）设 A

={1,2,3,4,5,6}，集合A上的关系

R={〈1,3〉,〈1,5〉,〈2,5〉,〈4,4〉,〈4,5〉,〈5,4〉,〈6,3〉,〈6,6〉}。（1）画出R的关系图，并求它的关系矩阵；（2）求r(R),S(R)及 解：（1）R的关系图为

t(R)。

R的关系矩阵为

M

R

0

00000

000000

10000

1000110

110100

0

00

0（2分）01

（2）r(R)R{1,1,2,2,3,3,5,5，（1分）

S(R)R3,51, ,（31,分）6 }t(R)R1,4 5}2分）,5（4．设Z是整数集，R是Z上的模3同余关系，即R{x,yx,yZ,xy(mod3)}，试根据等价关系R决定Z的一个划分。答案：由R决定的Z的划分为：{

0R,1R,2R}，其中：

0R{,9,6,3,0,3,6,9,}1R{,8,5,2,1,4,7,}

2R{,7,4,1,2,5,8,}

四．证明题（共10分）

１．设a,bR,ab, 定义f:[a,b][0,1]为 f(x)

其逆映射。

证：1）先证明f是入射（2分）

xaba，证明：f是双射，并求出

对任意的x1,x2a,b,若f(x1)f(x2),则有

x1aba



x2aba，从而有

x1x2，故

f是入射。

2)再证明f是满射（2分）

对任意的y0,1,都存在x(ba)yaa,b,使得f(x)y,从而f是满射。

综合（1）、（2）知f是双射。f

1

:[0,1][a,b]为 f

1

(x)(ba)xa，对任意

离散数学试卷与答案 篇6

3.在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值:(1)对于任意x,均有错误！未找到引用源。2=(x+错误！未找到引用源。)(x错误！未找到引用源。).(2)存在x,使得x+5=9.其中(a)个体域为自然数集合.(b)个体域为实数集合.解：

F(x): 错误！未找到引用源。2=(x+错误！未找到引用源。)(x错误！未找到引用源。).G(x): x+5=9.(1)在两个个体域中都解释为xF(x)，在（a）中为假命题，在(b)中为真命题。

(2)在两个个体域中都解释为xG(x)，在（a）(b)中均为真命题。

4.在一阶逻辑中将下列命题符号化:(1)没有不能表示成分数的有理数.(2)在北京卖菜的人不全是外地人.解:(1)F(x): x能表示成分数 H(x): x是有理数

命题符号化为: x(F(x)(2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: x(F(x)H(x))H(x))

5.在一阶逻辑将下列命题符号化:(1)火车都比轮船快.(3)不存在比所有火车都快的汽车.解:(1)F(x): x是火车;G(x): x是轮船;H(x,y): x比y快 屈婉玲版离散数学课后习题答案 命题符号化为: xy((F(x)G(y))H(x,y))

(2)(1)F(x): x是火车;G(x): x是汽车;H(x,y): x比y快 命题符号化为: y(G(y)x(F(x)9.给定解释I如下:(a)个体域D为实数集合R.(b)D中特定元素错误！未找到引用源。=0.(c)特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y未找到引用源。.(d)特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x

错误！.说明下列公式在I下的含义,并指出各公式的真值:(1)xy(G(x,y)(2)F(x,y))

xy(F(f(x,y),a)G(x,y))答:(1)对于任意两个实数x,y,如果x

（a）个体域D=N(N为自然数集合).（b）D中特定元素错误！未找到引用源。=2.（c）D上函数错误！未找到引用源。=x+y,错误！未找到引用源。(x,y)=xy.（d）D上谓词错误！未找到引用源。(x,y):x=y.说明下列各式在I下的含义，并讨论其真值.(1)错误！未找到引用源。xF(g(x,a),x)(2)错误！未找到引用源。x错误！未找到引用源。y(F(f(x,a),y)→F(f(y,a),x)答:(1)对于任意自然数x, 都有2x=x, 真值0.(2)对于任意两个自然数x,y,使得如果x+2=y, 那么y+2=x.真值0.11.判断下列各式的类型:(1)错误！未找到引用源。

(3)错误！未找到引用源。yF(x,y).解:(1)因为 p(qp)p(qp)1 为永真式；

所以 错误！未找到引用源。为永真式； 屈婉玲版离散数学课后习题答案(3)取解释I个体域为全体实数 F(x,y)：x+y=5 所以,前件为任意实数x存在实数y使x+y=5，前件真； 后件为存在实数x对任意实数y都有x+y=5，后件假，] 此时为假命题

再取解释I个体域为自然数N，F(x,y)：:x+y=5 所以,前件为任意自然数x存在自然数y使x+y=5，前件假。此时为假命题。

此公式为非永真式的可满足式。13.给定下列各公式一个成真的解释，一个成假的解释。

(1)错误！未找到引用源。(F(x)错误！未找到引用源。

(2)错误！未找到引用源。x(F(x)错误！未找到引用源。G(x)错误！未找到引用源。H(x))解:(1)个体域:本班同学

F(x)：x会吃饭, G(x)：x会睡觉.成真解释

F(x)：x是泰安人,G(x)：x是济南人.（2）成假解释(2)个体域:泰山学院的学生

F(x)：x出生在山东,G(x):x出生在北京,H(x):x出生在江苏,成假解释.F(x)：x会吃饭,G(x)：x会睡觉,H(x)：x会呼吸.成真解释.第五章部分课后习题参考答案

5.给定解释Ｉ如下:(a)个体域D={3,4};(b)f(x)错误！未找到引用源。为f(3)4,f(4)3错误！未找到引用源。

(c)F(x,y)为F(3,3)F(4,4)0,F(3,4)F(4,3)1错误！未找到引用源。.试求下列公式在Ｉ下的真值.(1)xyF(x,y)

F(f(x),f(y)))(3)xy(F(x,y)解:(1)xyF(x,y)x(F(x,3)F(x,4))屈婉玲版离散数学课后习题答案 (F(3,3)F(3,4))(F(4,3)F(4,4))

(01)(10)1

(2)xy(F(x,y)F(f(x),f(y)))

x((F(x,3)F(f(x),f(3)))(F(x,4)F(f(x),f(4))))

x((F(x,3)F(f(x),4))(F(x,4)F(f(x),3)))((F(3,3)F(f(3),4))(F(3,4)F(f(3),3)))

((F(4,3)F(f(4),4))(F(4,4)F(f(4),3)))((0F(4,4))(F(3,4)F(4,3)))((1F(3,4))(0F(3,3)))(00)(11)(11)(00)1

12.求下列各式的前束范式。

(1)xF(x)yG(x,y)

(5)x1F(x1,x2)解:(1)xF(H(x1)x2G(x1,x2))(本题课本上有错误)(x)yG(x,y)xF(x)yG(t,y)xy(F(x)G(t,y))

(5)x1F(x1,x2)(H(x1)x2G(x1,x2))

x1F(x1,x2)(H(x3)x2G(x3,x2))x1F(x1,x4)x2(H(x3)G(x3,x2))x1x2(F(x1,x4)(H(x3)G(x3,x2)))15.在自然数推理系统F中,构造下面推理的证明:(1)前提: xF(x)y((F(y)G(y))R(y)),xF(x)

结论: xR(x)(2)前提: x(F(x)→(G(a)∧R(x))), 错误！未找到引用源。xF(x)结论:错误！未找到引用源。x(F(x)∧R(x))证明(1)①xF(x)前提引入

②F(c)①EI ③xF(x)y((F(y)G(y))R(y))G(y))R(y))前提引入

④y((F(y) ①③假言推理

⑤(F(c)∨G(c))→R(c))④UI 屈婉玲版离散数学课后习题答案 ⑥F(c)∨G(c)②附加

⑦R(c)⑤⑥假言推理

⑧xR(x)⑦EG(2)①xF(x)前提引入 ②F(c)①EI ③x(F(x)→(G(a)∧R(x)))④F(c)→(G(a)∧R(c))⑤G(a)∧R(c)⑥R(c)⑦F(c)∧R(c)⑧x(F(x)∧R(x))

离散数学试卷与答案 篇7

关键词：悖论,离散数学,教学

离散数学作为计算机专业的核心专业基础课, 是学习许多计算机专业课程的先决条件。如何更好地开展离散数学教学意义重大, 是每个该门课程授课教师应认真思考的问题。作者在针对计算机科学与技术、信息与计算科学等专业的离散数学教学实践中, 探索出一条基于悖论的离散数学教学思路, 取得了较好的效果。

悖论, 即在逻辑上可以推导出互相矛盾之结论, 但表面上又能自圆其说的命题或理论体系。悖论的出现往往是因为人类对某些概念的理解认识不够深刻所致。悖论的成因极为复杂且深刻, 对它们的深入研究有助于数学、逻辑学、语义学等等理论学科的发展, 因此具有重要意义。难怪对于悖论曾有这样的评论:“当悖论提出时, 问题已经解决一半了。”

在离散数学的教学内容中, 牵涉到一系列的悖论, 这些悖论在当时引起争议, 在争议中推动了理论的进步与发展。对于学生来说, 接触到悖论时, 都会在思想上产生惊讶, 引起强烈的学习兴趣, 这是因为悖论与学生受到的形式逻辑的教育形成鲜明的反差, 因此在离散数学的教学中追本溯源引入悖论具有积极、重要的教学意义。

一、秃头悖论

秃头悖论描述:设n为某人头发的根数 (n≥0) , 基于数学归纳法:

1. n=0时, 此人为秃子

2. 假设n=k时, 此人为秃子

3. n=k+1时, 由于相比情况2仅仅多出一根头发, 因此, 此人仍是秃子, 即世界上所有的人都是秃子。

显然这一论断是不成立的, 分析其原因, 在于推导中使用了“秃子”这一模糊概念, 即人到底有多少根头发算作秃子没有精确的标准和定义。

要解决秃头悖论, 关键在于类似“秃子”这样模糊概念的表示, 从而引出模糊集合的特征函数定义以及隶属度的概念。

二、无穷饭店

无穷饭店描述:

“无穷饭店”是银河系中心的一家巨大的旅馆。它拥有无穷多个房间, 这些房间通过黑洞伸展到更高级的时空领域。房间号从1开始, 无限制地排下去。

情况1:一天, 这个旅店的客房全住进了客人, 这时来了一位飞碟驾驶员要住宿。尽管已经没有空房间了, 但旅店老板仍然给驾驶员找到了一个房间:把原来住在各个房间里的房客都一一移到高一号的房间。从而空出第1号房间使用。

情况2:第二天又来了五对夫妇渡蜜月。老板只需把每个客人都一一移到高5号的房间中去, 空出的1到5号房就给这5对夫妇即可。

情况3:周末, 又有无穷多个推销员来这家旅馆开会。此时老板只需把每个房间里的客人移到原来号码两倍的房间中去就可以。

无穷饭店乍一看似乎是不可能的, 因为它似乎违背了我们常常遵循的局部小于整体这一原则, 但当学习集合的基数以及等势的概念后, 无穷饭店这一悖论也就能够理解了。基于一一映射 (双射) 的方法, 不论是有限集还是无限集, 两个集合间可建立等势的概念。

无穷饭店的所有房间号可视为自然数集合N={1, 2, 3, 4, ……}, 对于情况1, 老板将原来客人的房间号均加1, 使得原房客的房间号集合对应到A={2, 3, 4, 5, ……}, N与A存在双射f (x) =x+1;因此, 所以老板可在保持原来房客住宿容量的情况下腾出一个房间。情况2与情况1类似。对于情况3, 原有房客的房间号集合被调整为C={2, 4, 6, 8, ……}, N与C之间存在一个双射f (x) =2x;因此, 所以老板可在保持原有住宿容量的情况下为推销员们腾出无穷多个房间[1]。

通过无穷饭店这一悖论, 在思考中加深了对集合基数以及两集合等势的概念理解。

三、理发师悖论 (罗素悖论)

理发师悖论描述:一位乡村理发师, 宣称他不给村子里任何自己刮脸的人刮脸, 但给所有不自己刮脸的人刮脸。此时有人问:“那您自己给不给自己刮脸?”理发师无言以对。事实上, 理发师悖论是罗素悖论的通俗描述。下面介绍罗素悖论:

对于大部分集合是不满足它与自身的属于关系的, 例如, 26个英文字母的集合A={a, b, c, ……, y, z}, 显然对于集合。但是有的集合, 例如“集合B是由2个以上元素的集合为元素组成的集合”, 则{1, 2, 3}、{1, 2, 3, 4}、{1, 2, 3, 5}等这些集合中的元素个数都是大于2, 因此都是集合B中的元素, 从而集合B中的元素数亦大于2, 因此有。

由此, 由康托尔最初所提出的“朴素集合论”, 会出现集合不是自己的元素、或者集合是自己元素的情况。

基于以上, 罗素构造集合, 提出问题“吗?”经过思考后会发现这个问题无法解答。首先, 若, 则按照P的定义有;其次, 若, 则按照P的定义有;即无论做何种解答都会出现矛盾的结论, 称之为罗素悖论[2]。

罗素悖论引发第三次数学危机, 自此之后一大群数学精英为了推进集合论的发展, 先后为剔除“罗素悖论”前赴后继。其中的理论改革中, 以法国数学家策墨罗提出的方案最为彻底, 即他与弗伦克尔合作提出的ZF公理。

理发师悖论以及罗素悖论的引入, 不仅让学生生动了解集合理论的发展历程, 同时进一步加深了对集合概念的理解。

四、结论

悖论由于与平常的教学知识的灌输与众不同, 使得往往在悖论的引入中, 学生全神贯注, 积极思考悖论的产生原因, 在潜移默化中达到了知识的灌输与强化作用, 学生反响不错, 因此, 有必要在今后的教学中挖掘更多更好的悖论, 以悖论促教学, 提高教学质量, 实现素质教育。

参考文献

[1]左孝凌, 李为, 刘永才.离散数学[M].上海:上海科学技术文献出版社, 1982.

[2]屈婉玲, 耿素云, 张立昂.离散数学[M].北京:高等教育出版社, 2008.

离散数学试卷与答案 篇8

关键词：离散数学；工科；教学体会；教学方法

中图分类号：G642.0 文献标识码：A 文章编号：1671-0568（2013）35-0006-02

作者简介：刘庆山，男，博士，副教授，硕士生导师，研究方向为网络科学理论及应用。

现代社会是信息社会，随着计算机科学与信息科学的不断发展，离散数学作为相关学科领域的一门基础课程，也凸显出越来越重要的作用。离散数学是数学的几个分支的总称，包括数理逻辑、集合论、数论和图论等。其教学的主要目的是为学生培养逻辑思维能力、抽象思维能力以及归纳推理能力，并为相应的后续课程如程序语言、数据结构、编译技术、电路设计等提供必要的数学基础。

离散数学研究基于离散空间的数学结构，不同于基于连续空间的数学结构。其研究对象是各种各样的离散量的结构及关系，这就形成了离散数学这门课的特点，即定义定理多、概念抽象、逻辑性强，使得学生在学习的过程中容易产生畏难情绪和枯燥感。在多年的教学过程中，笔者结合国内外关于离散数学的教材特点及课程特性，对离散数学在工科教学中的特点与方法进行了一些研究。

一、工科离散数学的特点

作为工科教学的专业基础课之一，离散数学在工科学生的本科学习，以及后续的专业学习、科学研究和工程应用中具有重要的基础作用。离散数学课程内容丰富多彩，逻辑性强，各部分内容相互独立又相互关联。通过离散数学的学习，有利于培养学生的逻辑推理能力，有利于提高他们的概括抽象能力。与其它工科类基础课程相比，离线数学具有以下特点：

首先，内容丰富繁多。离散数学的教学内容相对于其它工科类的基础课，可谓内容丰富多彩而又纷繁杂乱。通常的学习内容包括数理逻辑、集合论、数论和图论，这四部分的每一部分都可作为一门独立的课程来学习，可见离散数学的教学内容具有很大的弹性。在工科学生中讲解离散数学，主要应注重基本概念和基本方法的讲解。

其次，概念抽象难懂。离散数学中的定义定理很多，而且抽象难懂。这样的内容对于工科学生更是难以理解和掌握。因此在具体内容的讲解时，需要采取灵活多样的方式，以利于学生对基本知识点的理解和基本方法的掌握。

最后，内容实用性强。工科学生在课程学习中更强调动手能力和实用性。离散数学的课程内容不仅理论性强，而且理论与实际结合的非常紧密。如数理逻辑在电路设计中的应用，图论在现代网络科学研究中的应用，等等。

二、课程内容的引入

离散数学作为多个数学分支的合并，概念多、定理多是必然的，在具体的教学活动中，教师如何能够巧妙地调动学生对于这样一门内容繁多的课程的兴趣呢？通过参考大量国内外教材，以及借鉴工科课程教学中的实用方法，在教学中，通过引入一些有趣的实例来吸引学生的注意，调动他们的学习积极性。例如在数理逻辑教学的开始，引入一个有趣的逻辑故事：“古希腊有个国王，对处死囚徒的方法作了两种规定：砍头和绞刑，并且他做出了一个规定，囚徒可以任意说出一句话，而且这句话马上就可以验证真假。如果囚徒说的是真话那么就处以绞刑；如果是假话那么就砍头。结果很多囚徒或者因为说了真话被绞死，或者因为说了假话被砍头。有一位极其聪明的囚徒，当轮到他来选择处死方式时，他说出了一句巧妙的话，结果使得国王无论按照哪种方式处死他都有违自己的规定，最后不得不放了这个囚徒。那么这个囚徒说了一句什么话呢？”学生在听到故事后，不由自主地就会去思考到底这个囚徒说了什么。其实，这个故事在数理逻辑中实际上表现了一种悖论，于是结合故事就自然地引出了数理逻辑的学习。用这样的方法去调动学生的学习积极性，既活跃了课堂气氛，也使学生对课程内容产生了兴趣，成为一种十分有效的教学手段。同样在图论的教学中，也可以结合现代物流配送和路由器设计等讲解最短路径问题。用这种贴近生活的教学方式，使学生在学习的过程中产生这样一种理念：数学其实并不是枯燥乏味的，生活中处处可见数学知识。

三、授课方式的灵活多变与讲授内容的不断更新

传统的数学教学方式一直就是粉笔加黑板的模式，这种教学方式的优点是可以细致地表现定理的推导演绎过程。但是，对于离散数学这门课程来说，其教学内容丰富多样，单纯地依靠板书的形式来进行授课，会由于内容的过于抽象而使得学生产生枯燥感。所以，在教学中实行板书与多媒体相结合的方式，利用多媒体课件的直观性、生动性抓住学生，再用板书的形式加以对定理推导过程的演绎，二者结合，可使学生在图文并茂的教学环境中逐步地理解和接受严谨的数学推理过程。

同时，鉴于离散数学这门课程的自身特点，笔者发现，在授课的过程中，适当地利用学生参与教学的方式，可以达到事半功倍的效果。例如在进行命题逻辑的教学过程中，让学生自己分组进行辩论，互相出题，从而加深他们对命题真假性判断的能力。在图论中，请学生帮助快递员安排送货路线，使得他们可以利用最短的时间配送最多的快件。这样的教学方式，贴近学生生活，大大激发了他们的主观能动性，在实际问题的解决过程中达到了教学目的。

离散数学作为众多学科的基础课程，适当地让学生了解与之相关的现代科学前沿问题，有助于他们对课本知识点的掌握，培养学习的兴趣，激发探索新的科学方法和技术的动力。在进行数理逻辑部分的讲解中，适当地讲述一些机器推理方面的知识。在图论部分的讲解中，介绍一些现代网络科学发展的动态，如学生比较熟悉的微信网络，其中微信广告的发展，如何在最短的时间内散布广告信息，以及如何在最短的时间内阻止垃圾广告的传播，这些都涉及到经典图论的研究内容。通过这些实际应用方面的介绍，能够让学生知道离散数学在后续的课程学习、科学研究和工程应用中都会发挥重要的作用。

四、课程考核形式多样

数学的考核形式一般都是以期末闭卷考试成绩为主，这种考核方式单一呆板，并不能全面地考核学生的综合能力。因此，在离散数学的考核方式上可采取灵活多样的考核方式，除了期末的笔试以外，增加平时成绩和实践环节，在日常学习中穿插一些小的实践题目，让学生练习，并尝试用计算机程序实现，从而丰富期末综合考核的内容，也更能体现学生对所学知识的综合掌握情况。

综上所述，离散数学在工科课程的教学活动中，不仅要注重理论知识的讲解，更要注重将理论知识应用与实践相结合。在进一步的教学实践和教学改革中，应加大实践环节的教学，注重学生能力的培养。

参考文献：

[1]屈婉玲等.离散数学[M].北京：高等教育出版社，2008.

[2]Kenneth H.Rosen.离散数学及其应用（英文版）[M].北京：机械工业出版社，2008.

[3]匡能晖，胡国辉.离散数学教学中采取的三点技巧[J].当代教育理论与实践，2011，（9）.

[4]孙岚等.离散数学教学方法探讨[J].计算机教育，2012，（1）.

离散数学试卷与答案 篇9

说明：适用于计算机科学与技术本科国开平台网上形考。

形考任务一

试题及答案

题目为随机，用查找功能(Ctrl＋F)搜索题目

[题目]若集合A＝{

a，{a}，{1，2}}，则下列表述正确的是（）．

[答案]{a}A

[题目]若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是（）．

[答案]AB，且AB

[题目]若集合A＝{2，a，{

a

}，4}，则下列表述正确的是（）．

[答案]{

a

}A

[题目]设集合A={1,2,3}，B={3,4,5}，C={5,6,7}，则A∪B–C

=（）．

[答案]{1,2,3,4}

[题目]设集合A={a}，则A的幂集为（）．

[答案]{，{a}}

[题目]设集合A

=

{1,a

}，则P(A)

=

（）．

[答案]{,{1},{a},{1,a

}}

[题目]若集合A的元素个数为10，则其幂集的元素个数为（）．

[答案]1024

[题目]设A、B是两个任意集合，则A-B

=

（）．

[答案]AB

[题目]设集合A={2,4,6,8}，B={1,3,5,7｝，A到B的关系R={|

y

=

x

+1｝，则R=

（）．

[答案]{<2,3>,<4,5>,<6,7>}

[题目]集合A={1,2,3,4,5,6,7,8}上的关系R={|x+y=10且x,yA}，则R的性质为（）．

[答案]对称的[题目]集合A={1,2,3,4}上的关系R={|x=y且x,yA}，则R的性质为（）．

[答案]传递的[题目]如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有（）个．

[答案]2

[题目]设集合A={1,2,3,4}上的二元关系R={<1,1>，<2,2>，<2,3>，<4,4>}，S={<1,1>，<2,2>，<2,3>，<3,2>，<4,4>}，则S是R的（）闭包．

[答案]对称

[题目]设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为

（）．

[答案]无、2、无、2

[题目]设集合A={1，2，3，4，5}，偏序关系是A上的整除关系，则偏序集上的元素5是集合A的（）．

[答案]极大元

[题目]设集合A

=

{1,2,3,4,5}上的偏序关系的哈斯图如图所示，若A的子集B

=

{3,4,5}，则元素3为B的（）．

[答案]最小上界

[题目]设A={a，b，c}，B={1，2}，作f：A→B，则不同的函数个数为（）．

[答案]8

[题目]设A={a，b}，B={1，2}，C={4，5}，从A到B的函数f={,}，从B到C的函数g={<1，5>,<2，4>}，则下列表述正确的是（）．

[答案]g°

f

={,}

[题目]设集合A

={1,2,3}上的函数分别为：f

=

{<1,2>，<2,1>，<3,3>}，g

=

{<1,3>，<2,2>，<3,2>}，h

=

{<1,3>，<2,1>，<3,1>}，则h

=（）．

[答案]f◦g

[题目]设函数f：N→N，f(n)=n+1，下列表述正确的是（）．

[答案]f是单射函数

判断题

[题目]设集合A={1,2,3}，B={2,3,4}，C={3,4,5}，则A∩(C-B)=

{1,2,3,5}．（）

[答案]错

[题目]设集合A={1,2,3}，B={1,2}，则P(A)-P(B)=

{{3},{1,3},{2,3},{1,2,3}}．（）

[答案]对

[题目]空集的幂集是空集．（）

[答案]错

[题目]设集合A={1,2,3}，B={1,2}，则A×B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>}．（）

[答案]对

[题目]设A={1，2}，B={

a,b,c

}，则A×B的元素个数为8．（）

[答案]错

[题目]设集合A={0,1,2,3}，B={2,3,4,5}，R是A到B的二元关系，则R的有序对集合为{<2,2>，<2,3>，<3,2>，<3,3>}．（）

[答案]对

[题目]设集合A={1,2,3,4

}，B={6,8,12}，A到B的二元关系R＝

那么R－1＝{<6,3>，<8,4>}．（）

[答案]对

[题目]设集合A=｛a,b,c,d｝，A上的二元关系R={,,,}，则R具有反自反性质．（）

[答案]对

[题目]设集合A=｛a,b,c,d｝，A上的二元关系R={

>,,,}，若在R中再增加两个元素，，则新得到的关系就具有反自反性质．（）

[答案]错

[题目]若集合A

=

{1，2，3}上的二元关系R={<1,1>，<1,2>，<3,3>}，则R是对称的关系．（）

[答案]错

[题目]若集合A

=

{1，2，3}上的二元关系R={<1,1>，<2,2>，<1,2>}，则R是自反的关系．（）

[答案]错

[题目]设A={1,2}上的二元关系为R={|xA，yA,x+y

=10}，则R的自反闭包为{<1,1>,<2,2>}．（）

[答案]对

[题目]设R是集合A上的等价关系，且1,2,3是A中的元素，则R中至少包含<1,1>，<2,2>，<3,3>

等元素．（）

[答案]对

[题目]设A={1，2，3

}，R={<1，1

>,<1，2

>，<2，1

>,<3，3

>}，则R是等价关系．（）

[答案]错

[题目]如果R1和R2是A上的自反关系，则、R1∪R2、R1∩R2是自反的．（）

[答案]对

[题目]若偏序集的哈斯图如图二所示，则集合A的最大元为a，极小元不存在．（）

[答案]错

[题目]设集合A={1,2,3,4}，B={2,4,6,8}，下列关系f

=

{<1,4>,<2,2,>,<4,6>,<1,8>}可以构成函数f：．（）

[答案]错

[题目]设集合A={1,2,3,4}，B={2,4,6,8}，下列关系f

=

{<1,8>,<2,6>,<3,4>,<4,2,>}可以构成函数f：．（）

[答案]对

[题目]设A={a,b}，B={1,2}，C={a,b}，从A到B的函数f={,}，从B到C的函数g={<1,b>,<2,a

>}，则g°

f

={<1，2

>,<2，1

>}．（）

[答案]错

[题目]设A={2,3}，B={1,2}，C={3,4}，从A到B的函数f={<2,2>,<3,1>}，从B到C的函数g={<1，3>,<2，4>}，则Dom(g°

f)

={2，3}．（）

[答案]对

形考任务二

试题及答案

题目为随机，用查找功能(Ctrl＋F)搜索题目

单选题

[题目]设图G＝，v∈V，则下列结论成立的是

（）

．

[答案]

[题目]设无向图G的邻接矩阵为，则G的边数为（）．

[答案]5

[题目]设无向图G的邻接矩阵为，则G的边数为（）．

[答案]7

[题目]已知无向图G的邻接矩阵为，则G有（）．

[答案]5点，7边

[题目]如图一所示，以下说法正确的是

（）

．

[答案]{(d,e)}是边割集

[题目]如图二所示，以下说法正确的是

（）．

[答案]e是割点

[题目]图G如图三所示，以下说法正确的是

（）．

[答案]{b,c}是点割集

[题目]图G如图四所示，以下说法正确的是

（）

．

[答案]{(a,d),(b,d)}是边割集

[题目]设有向图（a）、（b）、（c）与（d）如图五所示，则下列结论成立的是（）．

[答案]（a）是强连通的[题目]设有向图（a）、（b）、（c）与（d）如图六所示，则下列结论成立的是（）．

[答案]（d）只是弱连通的[题目]无向图G存在欧拉回路，当且仅当（）．

[答案]G连通且所有结点的度数全为偶数

[题目]无向完全图K4是（）．

[答案]汉密尔顿图

[题目]若G是一个汉密尔顿图，则G一定是（）．

[答案]连通图

[题目]若G是一个欧拉图，则G一定是（）．

[答案]连通图

[题目]G是连通平面图，有v个结点，e条边，r个面，则r=

（）．

[答案]e－v＋2

[题目]无向树T有8个结点，则T的边数为（）．

[答案]7

[题目]无向简单图G是棵树，当且仅当（）．

[答案]G连通且边数比结点数少1

[题目]已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树叶数为（）．

[答案]5

[题目]设G是有n个结点，m条边的连通图，必须删去G的（）条边，才能确定G的一棵生成树．

[答案]m-n+1

[题目]以下结论正确的是（）．

[答案]树的每条边都是割边

判断题

[题目]已知图G中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G的边数是15．（）

[答案]对

[题目]设G是一个图，结点集合为V，边集合为E，则

．（）

[答案]对

[题目]设图G如图七所示，则图G的点割集是{f}．（）

[答案]错

[题目]若图G=，其中V={

a,b,c,d

}，E={

(a,b),(a,d),(b,c),(b,d)}，则该图中的割边为(b,c)．（）

[答案]对

[题目]无向图G存在欧拉回路，当且仅当G连通且结点度数都是偶数．（）

[答案]对

[题目]如果图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．（）

[答案]错

[题目]如图八所示的图G存在一条欧拉回路．（）

[答案]错

[题目]设完全图K有n个结点(n2)，m条边，当n为奇数时，Kn中存在欧拉回路．（）

[答案]对

[题目]汉密尔顿图一定是欧拉图．（）

[答案]错

[题目]设G=是具有n个结点的简单图，若在G中每一对结点度数之和小于n-1，则在G中存在一条汉密尔顿路．（）

[答案]错

[题目]若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为W|S|．（）

[答案]对

[题目]如图九所示的图G不是欧拉图而是汉密尔顿图．（）

[答案]对

[题目]设G是一个有7个结点16条边的连通图，则G为平面图．（）

[答案]错

[题目]设G是一个连通平面图，且有6个结点11条边，则G有7个面．（）

[答案]对

[题目]设连通平面图G的结点数为5，边数为6，则面数为4．（）

[答案]错

[题目]结点数v与边数e满足e=v的无向连通图就是树．（）

[答案]错

[题目]设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去4条边后使之变成树．（）

[答案]对

[题目]无向图G的结点数比边数多1，则G是树．（）

[答案]错

[题目]设图G是有5个结点的连通图，结点度数总和为10，则可从G中删去6条边后使之变成树．（）

[答案]错

[题目]两个图同构的必要条件是结点数相等；边数相等；度数相同的结点数相等．（）

[答案]对

形考任务三

试题及答案

题目为随机，用查找功能(Ctrl＋F)搜索题目

选择题

[题目]设P：我将去打球，Q：我有时间．命题“我将去打球，仅当我有时间时”符号化为（）．

[答案]P→Q

[题目]设命题公式G：G:

┐p→(Q∧R)，则使公式G取真值为1的P，Q，R赋值分别是

（）．

[答案]1,0,0

[题目]命题公式

(P∨Q)→R的析取范式是

（）．

[答案](┐P∧┐Q)∨R

[题目]命题公式

(P∨Q)的合取范式是

（）

．

[答案](P∨Q)

[题目]命题公式┐(p→Q)的主析取范式是（）．

[答案]P∧┐Q

[题目]命题公式P→Q的主合取范式是（）．

[答案]┐P∨Q

[题目]下列等价公式成立的为（）．

[答案]P→(┐Q→P)

＜＝＞┐P→(P→Q)

[题目]下列等价公式成立的为（）．

[答案]┐P∧P＜＝＞┐Q∧Q

[题目]下列公式成立的为（）．

[答案]┐P∧(P∨Q)

＝＞Q

[题目]下列公式中

（）为永真式．

[答案]┐A∧┐B

↔

┐(A∨B)

[题目]下列公式

（）为重言式．

[答案]Q→(P∨(P∧Q))↔Q

→P

[题目]命题公式(P∨Q)

→Q为（）

[答案]可满足式

[题目]设A（x）：x是书，B（x）：x是数学书，则命题“不是所有书都是数学书”可符号化为（）．

[答案]

[题目]设A（x）：x是人，B（x）：x是教师，则命题“有人是教师”可符号化为（）．

[答案]

[题目]设个体域为整数集，则公式的解释可为（）．

[答案]对任一整数x存在整数y满足x+y=0

[题目]表达式中的辖域是（）．

[答案]

[题目]谓词公式(∀x)(A(x)→B(x)∨C(x，y))中的（）。

[答案]x是约束变元，y都是自由变元

[题目]设个体域D={a,b,c}，那么谓词公式消去量词后的等值式为（）．

[答案]

[题目]设个体域D是整数集合，则命题的真值是（）．

[答案]T

[题目]前提条件P→┐Q2P的有效结论是（）．

[答案]┐Q

判断题

[题目]设P：小王来学校，Q：他会参加比赛．那么命题“如果小王来学校，则他会参加比赛”符号化的结果为P→Q．（）

[答案]对

[题目]设P：昨天下雨，Q：今天下雨．那么命题“昨天下雨，今天仍然下雨”符号化的结果为P∧Q．（）

[答案]对

[题目]设P：我们下午2点去礼堂看电影，Q：我们下午2点去教室看书．那么命题“我们下午2点或者去礼堂看电影或者去教室看书”

符号化的结果为P∨Q．（）

[答案]错

[题目]设P：他生病了，Q：他出差了，R：我同意他不参加学习．那么命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P∨Q)→┐R．（）

[答案]错

[题目]命题公式P→(Q∨P)的真值是T．（）

[答案]对

[题目]命题公式┐P∧P的真值是T．（）

[答案]错

[题目]命题公式┐P∧(P∨Q)=>Q成立．

（）

[答案]对

[题目]命题公式┐P∧(P→┐Q)∨P为永真式．（）

[答案]对

[题目]命题公式┐(P→Q)的主析取范式是P∨┐Q．（）

[答案]错

[题目]含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式(P∧Q∧R)∨(P∧Q∧┐R)．（）

[答案]对

[题目]设P(x)：x是人，Q(x)：x去上课，那么命题“有人去上课．”为(∃x)(P(x)→Q(x))．（）

[答案]错

[题目]设P(x)：x是人，Q(x)：x学习努力，那么命题“所有的人都学习努力．”为(∀x)(P(x)∧Q(x))．（）

[答案]错

[题目]设个体域D＝{1,2,3}，A(x)为“x小于3”，则谓词公式(∃x)A(x)的真值为T．（）

[答案]对

[题目]设个体域D＝{1,2,3,4}，A(x)为“x大于5”，则谓词公式(∀x)A(x)的真值为T．（）

[答案]错

[题目]谓词公式┐(∀x)P(x)(∃x)┐P(x)成立．（）

[答案]对

[题目]谓词命题公式(∀x)((A(x)∧B(x))∨C(y))中的自由变元为x．（）

[答案]错

[题目]谓词命题公式(∀x)(P(x)→Q(x)∨R(x，y))中的约束变元为x．（）

[答案]对

[题目]设个体域D＝{a,b},那么谓词公式(∃x)A(x)∨(∀y)B(y)消去量词后的等值式为A(a)∨B(b)．（）

[答案]错

[题目]设个体域D＝{a,b}，则谓词公式(∀x)(A(x)∧B(x))消去量词后的等值式为(A(a)∧B(a))∧(A(b)∧B(b))．（）

[答案]对

[题目]下面的推理是否正确．（）

(1)

(∀x)A(x)→B(x)

前提引入

(2)

A(y)→B(y)

US

(1)