2016华东师范大学离散数学作业

P591（1）. 用谓词公式表达语句“所有的运动员都钦佩某些教练”，个体域为全总个体域。

解：P(x):x是运动员，G(y):y是教练，R(x,y):x钦佩y。

原题量词表达为：∀x (P(x)→∃y(R(x,y)∧G(y)))此题错误较多：1. ∀x∃ yR(P(x),G(y)) 2. ∀x∃y(P(x)∧G(y)→R(x,y)) 3. R(x):x钦佩某些教练3. 将∀x(C(x)∨∃y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同班同学，个体域是学校全体学生的集合。

解：学校的全体学生要么自己有电脑，要么其同班同学有电脑。

80%能正确解释。

5. 给定解释I如下：个体域D：{-2,3,6}；个体常元a：6；谓词P：2>1，Q(x)：x≤3，R(x)：x>5。

求出谓词公式∀x(P→Q(x))∨R(a)在解释I下的真值。

解：R(a)总为1,故∀x(P→Q(x))∨R(a)为∀x(P→Q(x))∨1＝1都能做对最后答案。

有的学生将D的每个元素代入求得，有的学生做法如上。

9（2）. 指出谓词公式∀x∀y(P(x,y)∨Q(y,z))∧∃xR(x,y)的指导变元、量词的辖域、约束变元和自由变元。

解：第一个x是指导变元，相应的辖域是∀y (P(x,y)∨Q(y,z))；第二、四个x是约束变元；第三个x 是指导变元，相应的辖域是R(x,y)；第一个y是指导变元，相应的辖域是：(P(x,y)∨Q(y,z))；第二，三个y是约束变元；第四个y 是自由变元；第一个z 是自由变元。

即：指导变元：第一个x，第三个x，第一个y辖域：∀y (P(x,y)∨Q(y,z))，R(x,y)，(P(x,y)∨Q(y,z))约束变元：第二个x，第四个x，第二个y，第三个y自由变元：第四个y，第一个z约一半学生错在第一个X为指导变元时的辖域，错写为(P(x,y)∨Q(y,z))，其余的正确。

离散数学形成性考核作业9参考答案离散数学作业9姓名：学号：得分：教师签名：离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。

要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成并上交任课教师（不收电子稿）。

并在09任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、单项选择题1．设P：我将去市里，Q：我有时间．命题“我将去市里，仅当我有时间时”符号化为( B )．A．Q?P B．P?Q C．P?Q D．?P??Q2．设命题公式G：?P?(Q?R)，则使公式G取真值为1的P，Q，R赋值分别是 (D )．A．0, 0, 0 B．0, 0, 1 C．0, 1, 0 D．1, 0, 03．下列命题公式成立的为( C )．A．?P??Q?P?Q B．?B?A ? A?B C．P ? Q ?Q D．?A? (A?B) ?B4．下列公式 ( C )为重言式．A．P?Q ??P?Q B．(B?(A?B)) ?(?A?(A?B))C．?(P?Q)??P??Q D．A??B?A?B 5．命题公式?(P?Q)的析取范式是( A )．A．P??Q B?P?Q C．?P?Q D．P??Q 6．设C(x)：x是国家级运动员，G(x)：x是健壮的，则命题“没有一个国家级运动员不是健壮的”可符号化为(D )．A．??x(C(x)??G(x)) B．??x(C(x)??G(x))C．??x(C(x)??G(x)) D．??x(C(x)??G(x))7．表达式?x(P(x,y)?Q(z))??y(R(x,y)??zQ(z))中?x的辖域是( B )． A．P(x, y) B．P(x, y)?Q(z) C．R(x, y) D．P(x, y)?R(x, y)8．谓词公式?xP(x)?(?x?Q(x)???xQ(x))的类型是( A )．1 / 6A．永真式 B．永假式 C．非永真的可满足式 D．蕴含式二、填空题1．命题公式P?(Q?P)的真值是 1 ．2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P∨Q)→R ．3．设A，B为任意命题公式，C为重言式，若A?C?B?C，那么A?B是言重式式(重言式、矛盾式或可满足式) ．4．含有三个命题变项P，Q，R的命题公式P?Q的主析取范式是（P∧ Q∧R）∧（P∧ Q ∧?R）．5．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”为(?χ)(PCχ)→Q(χ)) ．6．设个体域D＝{a, b},那么谓词公式?xA(x)??yB(y)消去量词后的等值式为(A(a)∨A(b))∨(B(a)∧B(b)) ．7．设个体域D＝{1, 2, 3, 4}，A(x)为“x小于3”，则谓词公式(?x)A(x) 的真值为．8．谓词命题公式(?x)(P(x)→Q(x)∨R(x，y))中的约束变元为χ．三、公式翻译题1．请将语句“今天是天晴”翻译成命题公式．解: 设P: 今天晴天则命题公式为P2．请将语句“如果明天天下雪，我就去市里”翻译成命题公式．解: 设P:天下雨. Q我明天去市里.则命题公式为P→Q3．请将语句“除非你去，否则我不去”翻译成命题公式．解: 设P:你去.Q我去.则命题公式为��P→��Q或Q→P2 / 64．请将语句“我去书店，仅当天不下雨”翻译成命题公式．解: 设P:我去书店. Q天不下雨则命题公式为P→Q5．请将语句“有人不去工作”翻译成谓词公式．解: 设P(χ): χ是人. Q(χ): χ去工作 .则谓词公式为(?χ)(P (χ)∧?Q(χ))6．请将语句“所有人都努力工作．”翻译成谓词公式．解: 设P(χ): χ是人. Q(χ): χ努力工作 . 则谓词公式为(?χ)(P (χ)→Q(χ))四、判断说明题（判断下列各题，并说明理由．）1．命题公式┐P∧P的真值是1．2．命题公式┐P∧（P→┐Q）∨P为永真式．答：正确┐P∧（P→┐Q）∨P是由┐P∧（P→┐Q）与P组成的析取式如果P的值为真，则┐P∧（P→┐Q）∨P为真如果P的值为假，则┐P与P→┐Q为真，即┐P∧（P→┐Q）为真也即┐P∧（P→┐Q）∨P为真。

离散数学作业答案01一、单项选择题（共8 道试题，共80 分。

）1. 本课程的教学内容分为三个单元，其中第三单元的名称是（）．A.数理逻辑B. 集合论C. 图论D. 谓词逻辑满分：10 分2. 本课程的教学内容按知识点将各种学习资源和学习环节进行了有机组合，其中第2章关系与函数中的第3个知识点的名称是（）．A. 函数B. 关系的概念及其运算C. 关系的性质与闭包运算D. 几个重要关系满分：10 分3. 本课程所有教学内容的电视视频讲解集中在VOD点播版块中，VOD点播版块中共有（）讲．A. 18B. 20C. 19D. 17满分：10 分4. 本课程安排了7次形成性考核作业，第3次形成性考核作业的名称是（）．A. 集合恒等式与等价关系的判定B. 图论部分书面作业C. 集合论部分书面作业D. 网上学习问答满分：10 分5. 课程学习平台左侧第1个版块名称是：（）．A. 课程导学B. 课程公告C. 课程信息D. 使用帮助满分：10 分6. 课程学习平台右侧第5个版块名称是：（）．A.典型例题B. 视频课堂C. VOD点播D. 常见问题满分：10 分7. “教学活动资料”版块是课程学习平台右侧的第（）个版块．A. 6B. 7C. 8D. 9满分：10 分8. 课程学习平台中“课程复习”版块下，放有本课程历年考试试卷的栏目名称是：（）．A. 复习指导B. 视频C. 课件D. 自测满分：10 分二、作品题（共 1 道试题，共20 分。

）1. 请您按照课程导学与章节导学中安排学习进度、学习目标和学习方法设计自己的学习计划，学习计划应该包括：课程性质和目标（参考教学大纲）、学习内容、考核方式，以及自己的学习安排，字数要求在100—500字．完成后在下列文本框中提交．提示：答题框内不能输入超过2000个字符。

如果超过2000字符，请使用附件上传功能。

学习离散数学有两项最基本的任务：其一是通过学习离散数学，使学生了解和掌握在后续课程中要直接用到的一些数学概念和基本原理，掌握计算机中常用的科学论证方法，为后续课程的学习奠定一个良好的数学基础；其二是在离散数学的学习过程中，培训自学能力、抽象思维能力和逻辑推理能力，以提高专业理论水平。

离散数学作业2离散数学集合论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。

．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。

．要求：将此作业用A4纸打印出来，并在03任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，要求2009年4月5日前完成并后上交任课教师（不收电子稿）。

．并在03任务界面下方点击“保存”和“交卷”按钮，以便教师评分。

一、单项选择题1．若集合A ＝{2，a ，{ a }，4}，则下列表述正确的是( B )．A ．{a ，{a }}∈AB ．{ a }⊆AC ．{2}∈AD ．∅∈A2．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ B ）．A ．{2}∈B B ．{2, {2}, 3, 4}⊂BC ．{2}⊂BD ．{2, {2}}⊂B3．若集合A ={a ，b ，{ 1，2 }}，B ={ 1，2}，则（ D ）．A ．B ⊂ A B ．A ⊂ BC ．B ∉ AD ．B ∈ A4．设集合A = {1, a }，则P (A ) = ( C )．A ．{{1}, {a }}B ．{∅,{1}, {a }}C ．{∅,{1}, {a }, {1, a }}D ．{{1}, {a }, {1, a }}5．设集合A = {1，2，3}，R 是A 上的二元关系，R ={<a , b >⎢a ∈A ，b ∈ A 且1=-b a }则R 具有的性质为（ B ）．A ．自反的B ．对称的C ．传递的D ．反对称的6．设集合A = {1，2，3，4，5，6 }上的二元关系R ={<a , b >⎢a , b ∈A ，且a =b }，则R 具有的性质为（ D ）．A ．不是自反的B ．不是对称的C ．反自反的D ．传递的7．设集合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 的（ C ）闭包．A ．自反B ．传递C ．对称D ．以上都不对8．设集合A ={a , b }，则A 上的二元关系R={<a , a >，<b , b >}是A 上的( D )关系．A ．是等价关系但不是偏序关系B ．是偏序关系但不是等价关系C ．既是等价关系又是偏序关系D ．不是等价关系也不是偏序关系9．设集合A = {1 , 2 , 3 , 4 , 5}上的偏序关系 的哈斯图如右图所示,若A 的子集B = {3 , 4 , 5}，则元素3为B 的（ C ）．A ．下界B ．最大下界C ．最小上界D ．以上答案都不对10．设集合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 =（ A ）．（A ）f ◦g （B ）g ◦f （C ）f ◦f （D ）g ◦g二一、填空题1．设集合{1,2,3},{1,2}A B ==，则A B = A ，A B = B ．21．设集合{1,2,3},{1,2}A B ==，则P (A )-P (B )= {{3},{1,3},{2,3},{1,2,3}} ，A ⨯B = {<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ．32．设集合A 有10个元素，那么A 的幂集合P (A )的元素个数为210 ．43．设集合A ={0, 1, 2, 3}，B ={2, 3, 4, 5}，R 是A 到B 的二元关系，},,{B A y x B y A x y x R ⋂∈∈∈><=且且则R 的有序对集合为:{<2,2>,<2,3>,<3,2>,<3,3>}设集合A = {1，2，3，4，5 }，B = {1，2，3}，R 从A 到B 的二元关系，R ={<a , b >⎢a ∈A ，b ∈B 且2≤a + b则R 的有序对集合为:A ⨯B 。

第1次作业一、单项选择题(本大题共40分，共20小题，每小题2分)1.表达式FA (PV (QA-i S))的对偶式为 ___________ oA.FV(PA(QV-i S))B.T-(PV(QVn S))C.TV(PA(QV-| S))D.TV(PA(QAS))2.公式VxF(x) —3xG(x),下面给出的前束范式等价式中，哪一个是对的()OA.3x(F(x) V^G(x))B.VxF (x) VG(x)C.3x(-F(x) VG(x))Vx (「F(x) VG(X))3.设两个群＜乙+＞和V,•＞，,其中Z为整数集，Z x= {•••,10-3/10~2,10_1,10°,101,102,103,'-}, + 为普通加法，为普通乘法。

设(p： Z-»Z\屮(n)-io”。

则V乙+＞和＜Z-,•＞ ()A.是同构B.是单一同态C.是满同态D.不是同态4.不是命题的是()。

A.5大于3B.11是质数C.他是优秀学牛k是太阳5.对任意的公式P、Q、R,若P=>Q、Q=>R,则有A.R=>PB.P=>RC.Q=>PD.RnQ6.下列代数系统中， _________ 是群。

A.S={0, 1,3, 5}, *是模7 加法B.S=Q （有理数集），*是普通乘法C.S=Z （整数集合），*是普通减法D.S={1,3, 4, 5, 9}, *是模11 乘法7.P：今天下雨。

Q：明天下雨。

上述命题的合取为____________ o （符号表示）A.-1 PA-i QB.-I PVQC.n PV-i QD.PAQ&A.B.C.6D.39.他虽聪明单不用功。

设P：他聪明。

Q：他用功。

则命题符号化为_______ oA.PA-i QB.-I PVQC.n PVQD.QAP10.设G为至少有三个结点的连通平面图，则G中必有一个结点u,使得deg(u)<5B.deg(u)=5C.deg(u)>5D.deg(u) W511.下列关系中哪些能构成函数？()A.{ <x, y) |x, ye N, x+y<10}B.{ <x, y) |x, ye N, x+y二10}C.{ <x, y) |x, ye R, |x|=y}D.{ <x,y) |x,yG R, x=|y|}12.联结词一可以转化为由「和V表示，P-Qon PAn QB.-i PVQC.-1 PV-i QD.PAQ13.连通图G有6个顶点9条边，从G中删去___________ 条边才可能得到G的一•棵生成树T。

离散数学大作业题目赋权图的最小生成树算法学院班级学生姓名学号指导老师赋权图的最小生成树算法摘要一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点并且有保持图联通的最少的边问题就是最小生成树问题。

许多应用问题都是一个求无向连通图的最小生成树问题。

例如寻找在城市之间铺设光缆的最好方案问题等等。

解决权值最小生成树问题的方法有很多种，如Prim 算法、Kruskal算法等等都是很好的方法。

本文中使用了kruskal算法（避圈法）实现寻找赋权图的最小生成树问题。

概述离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。

它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。

通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。

随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。

离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。

由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。

离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。

离散数学2016.1.3期末试卷出现过的题目，有以下几道题：1、答案：错误2、5阶完全图有10条边。

答案：正确3、答案：正确4、答案：正确5、答案：错误证明题有，第三道和第十一道，类似第十二道的有一题判断题：1答案：错误；2 答案：错误；3答案：正确4答案：正确5答案：正确6答案：正确7答案：错误7答案：正确8欧拉图含有初级回路。

答案：错误9、可逆映射是双射。

答案：正确10永真式是可满足式。

答案：正确11、完全有向图是有向哈米尔顿图。

答案：正确12零元是不可逆的。

答案：正确；13、逻辑结论是正确结论。

答案：错误；14空集是任何集合的真子集。

答案：错误15空集是任何集合的子集。

答案：正确16单位元是可逆的。

答案：正确17一棵树的树叶树至少为2。

答案：错误18有生成树的无向图是连通的。

答案：正确18、5阶完全图有10条边。

答案：正确19强连通有向图一定是单向连通的。

答案：正确5、n阶完全图的任意2个结点的距离都是1。

答案：正确6、2个具有相同结点数和边数的图是同构的答案：错误11答案：正确12答案：正确13答案：正确13答案：正确14 答案：正确15答案：错误15答案：错误16 答案：正确16答案：错误17答案：错误18答案：错误19答案：正确20答案：错误22答案：错误25答案：错误27答案正确28答案：正确28答案：正确29答案：正确30答案：错误31答案：错误31答案：错误32答案正确证明题第一题：第二题答案：第三题第四题答案：第五题答案：第六题第七题第八题第九题第十题第十一题某班共有60人参加比赛，其中参加足球比赛的有28人，有29人参加篮球比赛，26人参加排球比赛，7人既踢足球又打篮球，9人既打篮球又打排球，11人既打排球又踢足球，求同时参加三种比赛的人数。

方案一：解 设参加足球、篮球、排球比赛的学生集合分别为A、B、C设x y z分别表示只参加足球、篮球、排球的人数设同时参加足球、篮球和排球的人数为Q？X+11+7-Q=28，Y+9+7-Q=29，Z+11+9-Q=26，X+Y+Z+11+9+7-2Q=60解得x=28+Q-11-7，y=29+Q-9-7，z=26+Q-11-9，则Q=28+29+26+Q-11-9-7=60，从而Q=4，所以同时参加足球、篮球、排球比赛的人数为4人方案二：解：设参加足球比赛的人为集合A；设参加篮球的比赛的人为集合B；设参加排球的比赛的人为集合C；则有:(用减代表交，用加代表并）。

离散数学集合论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业．要求：学生提交作业有以下三种方式可供选择：1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅．2. 在线提交word文档3. 自备答题纸张，将答题过程手工书写，并拍照上传．一、填空题1．设集合{1,2,3},{1,2}==，则P(A)-P(B )=A B{{1,2},{2,3},{1,3},{1,2,3}} ，A B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ．2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ．3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系，则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>}．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系R＝}x∈∈yy<>=,,2x{ByxA,那么R－1＝ {<6,3>,<8,4>} ．5．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, b>, <b, a>, <b, c>, <c, d>}，则R具有的性质是反自反性．6．设集合A=｛a, b, c, d｝，A上的二元关系R={<a, a>, <b, b>, <b, c>, <c, d>}，若在R中再增加两个元素<c,b>,<d,c>，则新得到的关系就具有对称性．7．如果R1和R2是A上的自反关系，则R1∪R2，R1∩R2，R1-R2中自反关系有 2 个．8．设A ={1, 2}上的二元关系为R ={<x , y >|xA ，yA , x +y =10}，则R 的自反闭包为 {<1,1>,<2,2>} ．9．设R 是集合A 上的等价关系，且1 , 2 , 3是A 中的元素，则R 中至少包含 <1,1>,<2,2>,<3,3> 等元素．10．设A ={1，2}，B ={a ，b }，C ={3，4，5}，从A 到B 的函数f ={<1, a >, <2, b >}，从B 到C 的函数g ={< a ，4>, < b ，3>}，则Ran(g f )= {<1,a>,<2,b>}或{<1,b>,<2,a>} ．二、判断说明题（判断下列各题，并说明理由．）1．若集合A = {1，2，3}上的二元关系R ={<1, 1>，<2, 2>，<1, 2>}，则(1) R 是自反的关系； (2) R 是对称的关系．解：(1)结论不成立．因为关系R 要成为自反的，其中缺少元素<3,3>．(2)结论不成立． 因为关系R 中缺少元素<2,1>2．设A ={1，2，3}，R ={<1，1>, <2，2>, <1，2> ，<2，1>}，则R 是等价关系．解：(1)结论不成立．因为关系R 要成为自反的，其中缺少元素<3,3>．(2)结论不成立． 因为关系R 中缺少元素<2,1>3．若偏序集<A ，R >的哈斯图如图一所示， 则集合A 的最大元为a ，最小元不存在．答： 错误，按照定义，图中不存在最大元和最小元。