下载文档原格式
离散数学作业及答案2011-2012学年第⼀学期离散数学作业及参考答案---信息安全10级5-1 1.利⽤素因⼦分解法求2545与360的最⼤公约数。
解：掌握两点：(1) 如何进⾏素因⼦分解从最⼩素数2的素数去除n。
(2) 求最⼤公约数的⽅法gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn)360=23325150902545=2030515091gcd(2545,360) =2030515090=52.求487与468的最⼩公倍数。
解：掌握两点：(1) 如何进⾏素因⼦分解从最⼩素数2的素数去除n。
(2) 求最⼩公倍数的⽅法lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn)ab=gcd(a, b)﹡lcm (a, b)487是质数，因此gcd(487,468)=1lcm(487,468)= (487*468)/1=487*468=2279163.设n是正整数，证明：6|n(n+1)(2n+1)证明：⽤数学归纳法：归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6归纳假设：假设当n=m时，6|m(m+1)(2m+1)归纳推导：当n=m+1时，n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1]=(m+1)(m+2)(2m+3)= m(m+1)(2m+3)+2(m+1)(2m+3)= m(m+1)(2m+1+2)+2(m+1)(2m+3)= m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3)= m(m+1)(2m+1)+ 2(m+1)(m+2m+3)= m(m+1)(2m+1)+ 2(m+1)(3m+3)= m(m+1)(2m+1)+ 6(m+1)2因为由假设6|m(m+1)(2m+1)成⽴。
⽽6|6(m+1)2所以6|m(m+1)(2m+1)+ 6(m+1)2故当n=m+1时，命题亦成⽴。
华理离散数学试题及答案一、单项选择题（每题2分，共10分）1. 在离散数学中，以下哪个概念是用来描述两个集合之间元素的对应关系的？A. 函数B. 映射C. 序列D. 集合答案：A2. 命题逻辑中，以下哪个符号表示逻辑“与”？A. ∧B. ∨C. →D. ¬答案：A3. 集合{1, 2, 3}和{3, 4, 5}的交集是什么？A. {1, 2}B. {3, 4}C. {3}D. {1, 2, 3, 4, 5}答案：C4. 以下哪个图是无向图？A. 有向图B. 无向图C. 完全图D. 部分图答案：B5. 在图论中，一个图的度是指什么？A. 顶点的数量B. 边的数量C. 顶点的度数D. 图的连通性答案：C二、填空题（每题2分，共10分）1. 在集合论中，空集用符号____表示。
答案：∅2. 如果A和B是两个集合，那么A和B的并集用符号____表示。
答案：A∪B3. 逻辑运算中的否定运算符用符号____表示。
答案：¬4. 在图论中，如果一个图的任意两个顶点都可以通过路径相连，则称这个图为____图。
答案：连通5. 一个有n个顶点的完全图，其边的数量为____。
答案：\(\frac{n(n-1)}{2}\)三、简答题（每题5分，共20分）1. 请解释什么是二元关系，并给出一个例子。
答案：二元关系是集合A和集合B之间的一种对应关系，它由有序对(a, b)组成，其中a属于A，b属于B。
例如，如果A是人名集合，B是年龄集合，那么“小于”就是一个二元关系。
2. 什么是归纳推理？请给出一个简单的例子。
答案：归纳推理是一种从特殊到一般的推理方法，它通过观察一系列具体实例来推断出一个普遍的结论。
例如，观察到太阳每天从东方升起，我们归纳出“太阳每天都会从东方升起”。
3. 什么是图的生成树？请简述其特点。
答案：图的生成树是包含图中所有顶点的子图，并且是一个树。
它的特点是没有环，并且任意两个顶点之间有且仅有一条路径。
离散数学作业答案文档编制序号：[KK8UY-LL9IO69-TTO6M3-MTOL89-FTT688]离散数学作业5离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。
本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。
要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。
并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。
一、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ．2．设给定图G (如右由图所示)，则图G 的点割集是 {f,c}．3．设G 是一个图，结点集合为V ，边集合为E ，则G 的结点 度数之和 等于边数的两倍．4．无向图G 存在欧拉回路，当且仅当G 连通且 所有结点的度数全为偶数 ．5．设G=<V ，E >是具有n 个结点的简单图，若在G 中每一对结点度数之和大于等于n-1 ，则在G 中存在一条汉密尔顿回路．6．若图G=<V , E>中具有一条汉密尔顿回路，则对于结点集V 的每个非空子集S ，在G 中删除S 中的所有结点得到的连通分支数为W ，则S 中结点数|S|与W 满足的关系式为 S W ．7．设完全图K n 有n 个结点(n 2)，m 条边，当n 为奇数时，K n 中存在欧拉回路．8．结点数v 与边数e 满足 e= v －1 关系的无向连通图就是树． 9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去4 条边后使之变成树．姓 名： 学 号： 得 分： 教师签名：10．设正则5叉树的树叶数为17，则分支数为i = 4 ． 二、判断说明题（判断下列各题，并说明理由．）1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路．．答：不正确，图G 是无向图，当且仅当G 是连通，且所有结点度数均为偶数，这里不能确定图G 是否是连通的。
离散数学作业（解答必须手写体上传，否则酌情扣分）1．设命题公式为⌝Q∧（P→Q）→⌝P。
（1）求此命题公式的真值表；答：解（1）真值表如下P Q ⌝Q P→Q ⌝Q∧（P→Q）⌝P⌝Q∧（P→Q）→⌝P0 0 1 1 1 1 10 1 0 1 0 1 11 0 1 0 0 0 11 1 0 1 0 0 1（2）求此命题公式的析取范式；答：⌝（⌝Q∧（⌝P∨Q））∨⌝P ⇔Q∨⌝（⌝P∨Q）∨⌝P ⇔ Q∨P∧⌝Q∨⌝P ⇔ P∨ Q∧⌝Q∨⌝P⇔P ∨1∨⌝P⇔P ∨⌝P ∨1⇔1⇔（⌝P∧⌝Q）∨（⌝P∧Q）∨（P∧⌝Q）∨（P∧Q）（主析取范式）（3）判断该命题公式的类型。
答：该命题公式重言式2．用直接证法证明前提：P∨Q，P→R，Q→S结论：S∨R证 (1)P∨Q P(2)⌝P→Q T(1)E(3) Q→S P(4)⌝P→S T(2,3)I(5)⌝ S → P T(4)E(6) P→R P(7)⌝ S →R T(5,6)I(8) S∨R T(7)E3．在一阶逻辑中构造下面推理的证明每个喜欢步行的人都不喜欢坐汽车。
每个人或者喜欢坐汽车或者喜欢骑自行车。
有的人不喜欢骑自行车。
因而有的人不喜欢步行。
令F(x)：x喜欢步行。
G(x)：x喜欢坐汽车。
H(x)：x喜欢骑自行车。
解前提：∀x（F（x）→⌝ G（x）），∀x（G（x）∨H（x）），∃ x⌝ H（x）。
结论：∃ x ⌝F（x）。
证 (1)∃ x ⌝H（x） P(2)⌝H（c） ES(1)(3)∀x（G（x）∨H（x）） P(4) G（c）∨H（c） US(3)(5) G（c） T(2，4)I(6)∀x（F（x）→⌝ G（x）） P(7)F（c）→⌝ G（c） US(6)(8)⌝ F（c） T(5,7)I(9)（∃x）⌝ F（x） EG(8)4．用直接证法证明：前提：（∀x）（C（x）→W（x）∧R（x）），（∃x）（C（x）∧Q（x））结论：（∃x）（Q（x）∧R（x））。
离散数学大作业题目赋权图的最小生成树算法学院班级学生姓名学号指导老师赋权图的最小生成树算法摘要一个有n个结点的连通图的生成树是原图的极小连通子图，且包含原图中的所有n个结点并且有保持图联通的最少的边问题就是最小生成树问题。
许多应用问题都是一个求无向连通图的最小生成树问题。
例如寻找在城市之间铺设光缆的最好方案问题等等。
解决权值最小生成树问题的方法有很多种，如Prim 算法、Kruskal算法等等都是很好的方法。
本文中使用了kruskal算法（避圈法）实现寻找赋权图的最小生成树问题。
概述离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。
它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。
通过离散数学的学习，不但可以掌握处理离散结构的描述工具和方法，为后续课程的学习创造条件，而且可以提高抽象思维和严格的逻辑推理能力，为将来参与创新性的研究和开发工作打下坚实的基础。
随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。
离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。
由于数字电子计算机是一个离散结构，它只能处理离散的或离散化了的数量关系，因此，无论计算机科学本身，还是与计算机科学及其应用密切相关的现代科学研究领域，都面临着如何对离散结构建立相应的数学模型；又如何将已用连续数量关系建立起来的数学模型离散化，从而可由计算机加以处理。
离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。
离散数学习题及解答作业题与解答第⼀章19 (2)、(4) 、(6)21 (1)、(2) 、(3)19、(2)解答: (p→┐p)→┐q 真值表如下:所以公式(p→┐q)→┐q 为可满⾜式19、(4)解答: (p→q)→(┐q→┐p) 真值表如下:所以公式(p→q)→(┐q→┐p)为永真式19、(6)解答: ((p→q)∧(q→r))→(p→r) 真值表如下:所以公式((p→q)∧(q→r))→(p→r)为永真式21、(1)解答: ┐(┐p∧q)∨┐r 真值表如下:所以成假赋值为:01121、(2)解答: (┐q∨r)∧(p→q)真值表如下:所以成假赋值为:010,100,101,11021、(3)解答: (p→q)∧(┐(p∧r)∨p)真值表如下:所以成假赋值为:100,101第⼆章5、(1) (2) (3) 6、(1) (2) (3) 7、(1) (2) 8、(1) (2) (3) 5、求下列公式的主析取范式,并求成真赋值(1) (┐p→q)→(┐q∨p)┐(┐p→q) ∨(┐q∨p)┐(┐(┐p) ∨q) ∨(┐q∨p)(┐p ∧┐q) ∨(┐q∨p)(┐p ∧┐q) ∨(p ∧┐q)∨(p ∧q)所以00，10，11 为成真赋值。
(2) (┐p→q)∧(q∧r)(┐┐p∨q)∧(q∧r)(p∨q)∧(q∧r)(p∧q∧r)∨(q∧r)(p∧q∧r)∨(p∧q∧r)∨(┐p∧q∧r)(p∧q∧r)∨(┐p∧q∧r)m3∨m 7，所以011，111 为成真赋值。
(3) (p∨(q∧r))→(p∨q∨r)┐(p∨(q∧r))∨(p∨q∨r)(┐p∧(┐q∨┐r))∨(p∨q∨r)(┐p∧┐q)∨(┐p∧┐r)∨(p∨q∨r)(┐p∧┐q)∨((┐p∧┐r)∨(p∨q∨r))(┐p∧┐q)∨((┐p∨p∨q∨r)∧(┐r∨p∨q∨r) )(┐p∧┐q)∨(1∧1)(┐p∧┐q)∨11m0∨m1∨m 2∨m3∨m4∨m5∨m 6 ∨m 7，所以000, 001, 010, 011, 100, 101, 110, 111 为成真赋值。
离散数学作业4离散数学图论部分形成性考核书面作业本课程形成性考核书面作业共3次，内容重要分别是集合论部分、图论部分、数理逻辑部分旳综合练习，基本上是按照考试旳题型（除单项选择题外）安排练习题目，目旳是通过综合性书面作业，使同学自己检查学习成果，找出掌握旳微弱知识点，重点复习，争取尽快掌握。
本次形考书面作业是第二次作业，大家要认真及时地完毕图论部分旳综合练习作业。
一、填空题1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 旳边数是 15 ．2．设给定图G (如右由图所示)，则图G 旳点割集是{f} ．3．设G 是一种图，结点集合为V ，边集合为E ，则G 旳结点 度数之和 等于边数旳两倍．姓 名：学 号：4．无向图G存在欧拉回路，当且仅当G连通且等于出度．5．设G=<V，E>是具有n个结点旳简朴图，若在G中每一对结点度数之和不小于等于n-1 ，则在G中存在一条汉密尔顿路．6．若图G=<V, E>中具有一条汉密尔顿回路，则对于结点集V旳每个非空子集S，在G中删除S中旳所有结点得到旳连通分支数为W，则S中结点数|S|与W满足旳关系式为W(G-V1) ≤∣V1∣．7．设完全图n个结点(n≥2)，m条边，当n为奇数时，存在欧拉回路．8．结点数v与边数e满足e=v-1 关系旳无向连通图就是树．9．设图G是有6个结点旳连通图，结点旳总度数为18，则可从G中删去4 条边后使之变成树．10．设正则5叉树旳树叶数为17，则分支数为i = 5 ．二、判断阐明题（判断下列各题，并阐明理由．）1．假如图G是无向图，且其结点度数均为偶数，则图G存在一条欧拉回路．．(1) 不对旳，缺了一种条件，图G应当是连通图，可以找出一种反例，例如图G是一种有孤立结点旳图。
2．如下图所示旳图G存在一条欧拉回路．(2) 不对旳，图中有奇数度结点，因此不存在是欧拉回路。
3．如下图所示旳图G不是欧拉图而是汉密尔顿图．G解：对旳由于图中结点a，b，d，f旳度数都为奇数，因此不是欧拉图。
考生答题情况作业名称：2017年秋季网上作业1 出卷人：SA 作业总分：100 通过分数：60 起止时间：2017/12/11 23:43:18 至2017/12/12 0:17:07 学员姓名：学员成绩：85 标准题总分：100 标准题得分：85 详细信息：题号:1 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列语句中是命题的为（）. A、上帝是万能的么？！B、X = 3. C、如果2+3＝23，那么雪是蓝色的. D、敬礼！标准答案:C 学员答案:C 本题得分:5题号:2 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列图形中是平面图的是（）. A、B、C、.D、（彼得森）图标准答案:B 学员答案:B 本题得分:5题号:3 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:若完全图是图的一个子图，则图的色数至少应为（）. A、2 B、3 C、4 D、5 标准答案:B 学员答案:B 本题得分:5题号:4 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:已知集合上偏序关系，其中属于的序偶有（）. A、B、和C、D、标准答案:B 学员答案:B 本题得分:5题号:5 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:集合上的二元关系、，下列选项中唯一正确的是（）. A、如果、都是对称的，那么也是对称的B、如果、都是反对称的，那么也是反对称的C、如果、都是传递的，那么也是传递的D、如果、都是自反的，那么也是自反的标准答案:D 学员答案:D 本题得分:5题号:6 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:对有限连通平面图，则其边数、点数、面数必满足的是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:7 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:一棵树中的任意两点之间相连的通路条数必为（）. A、2 B、3 C、1 D、5 标准答案:C 学员答案:C 本题得分:5题号:8 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:交换群是只须同时满足（）等特征的独异点. A、存在生成元B、存在零元C、存在幺元D、可交换性且中每个元素都有逆元标准答案:D 学员答案:D 本题得分:5题号:9 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:设：我去看电影;：我有时间，将命题“我去看电影，仅当我有时间.” 符号化为（）. A、B、C、D、标准答案:A 学员答案:A 本题得分:5题号:10 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:已知上偏序关系对应的，则的子集的极小元为（）. A、4 B、2 C、1 D、3 标准答案:C 学员答案:B 本题得分:0题号:11 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:与命题公式唯一不等价的选项是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:12 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列各式中，为永假式的是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:13 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:对代数系统，下列四个论述中正确的只有（）. A、若存在零元，则零元是唯一的B、若存在左幺元，则左幺元必是唯一的C、若同时存在左、右幺元，则左、右幺元必相等D、若一个元素存在左逆元，则它一定也存在右逆元标准答案:A 学员答案:D 本题得分:0题号:14 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:集合，为上的一个二元关系，则下列命题中（）为真. A、不是自反的B、不是反自反的C、不是传递的D、不是对称的标准答案:B 学员答案:B 本题得分:5题号:15 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:前提，，，下的结论是（）. A、B、C、D、标准答案:C 学员答案:C 本题得分:5题号:16 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:集合的幂集的幂集是（）. A、B、C、D、标准答案:D 学员答案:D 本题得分:5题号:17 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:平面图的点数与边数一定满足的关系式为（）. A、B、C、标准答案:C 学员答案:C 本题得分:5题号:18 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:设是非空集合上的二元关系，则的对称闭包（）. A、B、C、D、标准答案:D 学员答案:B 本题得分:0题号:19 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:前提，下的结论是（）. A、B、C、D、标准答案:A 学员答案:A 本题得分:5题号:20 题型:单选题（请在以下几个选项中选择唯一正确答案）本题分数:5 内容:下列图形中不是汉密尔顿图的是（）. A、B、C、D、（彼得森）图E、标准答案:D 学员答案:D 本题得分:5。
华工 2023秋离散数学平时作业作业一题目一请使用归纳法证明下列结论：在一副扑克牌中，无论怎样选择，其中总是存在不管选择多少张牌，至少有两张点数相同的牌。
解答使用归纳法证明：基础情况：当选择一张牌时，无论选择哪张牌，都不存在其他相同点数的牌，因为只有一张牌。
当选择一张牌时，无论选择哪张牌，都不存在其他相同点数的牌，因为只有一张牌。
归纳假设：假设选择任意n张牌时，其中至少存在两张点数相同的牌。
假设选择任意n张牌时，其中至少存在两张点数相同的牌。
归纳步骤：假设选择n+1张牌。
我们可以将这些牌分成两组：前n张牌和第n+1张牌。
根据归纳假设，前n张牌中至少存在两张点数相同的牌。
假设选择n+1张牌。
我们可以将这些牌分成两组：前n张牌和第n+1张牌。
根据归纳假设，前n张牌中至少存在两张点数相同的牌。
- 若第n+1张牌与前n张牌中的其中一张点数相同，则至少存在两张点数相同的牌。
- 若第n+1张牌为新的点数，则前n张牌中至少存在两张点数相同的牌。
根据抽屉原理，由于一副扑克牌中只有有限的不同点数，当选择的牌数超过不同点数的数量时，必然存在两张点数相同的牌。
综上所述，无论选择多少张牌，至少存在两张点数相同的牌。
题目二给定集合A={1，2，3}和集合B={x | x为自然数且1≤x≤6}，找出集合A和集合B的笛卡尔积，并用集合的形式表示。
解答集合A和集合B的笛卡尔积为：A × B = {(1,1), (1,2), (1,3), (1,4), (1,5), (1,6), (2,1), (2,2), (2,3), (2,4), (2,5), (2,6), (3,1), (3,2), (3,3), (3,4), (3,5), (3,6)}作业二（待补充）......（继续完成其他题目）。
欢迎共阅为
，
、完全二部图、完全图
、圈
上的关系中，不具有传递性的是（、
、
、
、
、
、
、
、
的点数
;：我有时间，将命题“我去看电影，仅当我有时间
、
、
、
、
，其中属于的序偶有（）.
D、
标准答案:B
学员答案:C
本题得分:0
对应的，则唯一不是
，则其边数、面数
中每个元素的逆元存在且唯
关于“”运算满足消去律
、群中除了么元外，还存在其他元素也满足
集合上的以下四个关系中，既是对称又是反对称的有（、
、
是由
、
、
、
的对偶图的对偶图同构于
是个集合，表示的幂集，则对代数系统
是实数集合，，则“”在上唯一满足的
集合上有两个自反关系
、
、
，则谓词表达式消去量词后等价于（、
与点数
、、、。
华东理工离散数学试卷(专升本)(A)姓名 学号 班级 成绩一．填空题（共46分） 1． （3分）给出下列语句：（1）7能被3整除. （2）5是素数当且仅当太阳从西边升起. （3）x+7<0. （4）9是2得倍数或者是4的倍数. （5）上海石化不在金山区.其中 是命题； 是复合命题. 2． （2分）给出以下命题：（1）1073532≠+→=+. （2）1073532≠+→≠+. （3）1073532=+↔≠+ （4）1073532=+→≠+.其中真值是F 的命题是 . 3．（3分）给出下列命题： （1）)()(p q q p ⌝→⌝→→ （2）p p q ∧→⌝)(（3）))((p q p →∧⌝ （4）)())()((r p r q q p →→→∧→ 其中 是重言式， 是矛盾式.4．（4分）将下列各式翻译成自然语言，并分别在整数集合 以及正整数集合 +的范围内 判断他们的真值：(1))(x xy y x =∀∃; (2).)(x xy y x ≥∀∀.(1) ;(2) . 5．（5分）判断下列命题的真假（其中A,B,C,S,T 均为集合, φ为空集）：（ ）（1）φφ∈ （ ）（2）φφ⊆ （ ）（3）T S T S =→=-)(φ （ ）（4）C A C B B A ∈→∈∧∈)()( （ ）（5）C B C A B A =→=)( 6．（2分）若{}{}φφ,=A ，则℘=)(A { }7．(4分)若{})1()(<∧∈=x R x x A ，{})1()(<∧∈=x Z x x B ，则=B A { } =B A { } =-B A { }=⊕B A { } 8．(4分)判断下列命题之真伪：（ ）（1）设Z Y X ,,为三个集合，φ≠X ，那么 Z Y Z X Y X =→⨯=⨯)(. （ ）（2）设D C B A ,,,为集合，则)()()()(D B C A D C B A ⨯⨯=⨯ .9．(2分)设{}c b a A ,,=，则 A A ⨯)(中有 个元素；元素{}c a ,,与 A A ⨯)(的关系是{c a b ,,A A ⨯)(（填∈或∉）.10．(2分)设集合{}c b a A ,,=，则A 上的二元关系共有 个；其中满足自反性的 关系有 个.11．(6分)给定集合{}3,2,1=A 上的3个关系如下：{}><><><><=1,1,1,2,3,2,2,21R ，{}><><><><><=1,1,3,3,2,3,3,2,2,22R ，{}><><><=1,3,3,3,3,23R ，则其中满足对称性的关系是 ；满足传递性的关系是 ； 满足反自反性的关系是 ；满足反对称性的关系是 ； 为等价关系的是 ；=⊕)(21R R dom { } . 12．(3分)设21,R R 是集合A 上的等价关系，做出下列几个关系：（1）1)(R A A -⨯ （2）12R R - （3）11R R （4）)(21R R r -， 其中关系 一般不再是A 上的等价关系.13．(4分)集合{}d c b a A ,,,=上包含序偶><d a ,和><b c ,的全序关系是=R { }. 14．(2分)在正整数集合+Z 上定义如下的乘法运算“ ”：b a ab b a ++=2 ，那么 ><+,Z 构成一个 .（代数系统，广群，半群，独异点，群，Abel 群， 循环群）二．选择题（每小题2分，共10分） 1．下列命题中正确的结论是：(A)集合上A 的关系如果不是自反的，就一定是反自反的；(B)集合上A 的关系如果不是对称的，就一定是反对称的；(C)集合上A 的关系如果满足自反性和反对称性，也可能是相容关系； (D)每一个全序集必为良序集.2．设S R ,是集合A 上的两个关系，则下列命题中正确的结论是： (A)若S R ,都是对称的，那么S R 必也为对称的； (B)若S R ,都是自反的，那么S R 必也为自反的； (C)若S R ,都是反自反的，那么S R 必也为反自反的； (D) 若S R ,都是传递的，那么S R 必也为传递的. 3以下命题中正确的结论是：(A)非空全序集的子集不一定有最小元； (B)非空全序集的子集一定有最大元；(C)非空偏序集的子集如有上界，则一定有最小上界； (D)非空偏序集的子集一定有最大元. 4．以下命题中不正确的结论是： (A)素数阶群必为循环群； (B)循环群必为Abel 群；(C)当3≥n 时，n 阶对称群n S 必为非Abel 群； (D)4阶群必为循环群.5．以下命题中正确的结论是：(A)n 个结点的完全图n K 的着色数4)(≤n K χ；(B)如果一个连通图的奇结点的个数大于2，那么它必不是一个Hamilton 图； (C)一棵树必是连通图，且其中没有回路； (D)图的邻接矩阵必为对称阵. 三．解答题(共44分) 1．（8分）证明下述蕴含式（方法不限）： )())()((R P R Q Q P →⇒→∧→ 2．（6分）证明：对任意集合C B A ,,有)()()(C A B A C B A ⊕=⊕ 3．（共14分）设}1,0{-=R X ，在X 上定义如下6个函数：x x f =)(0， x x f -=1)(1， xx f -=11)(2， x x f 1)(3=， 1)(4-=x x x f ， xx x f 1)(5-=.在集合{}543210,,,,,f f f f f f G =上定义二元运算“ ”是函数的复合运算. （1）（6分）将下列运算表中的空白处填上适当的元素：（2）（6分）证明>< ,G 是一个群.（3）（2分）它是一个Abel 群吗？说明你的理由. 4．（共16分）给出一个如下图的有向连通图G .（1）（4分）写出它的邻接矩阵A ； （2）（8分）图中长度为3的通路一共有多少条？ （3）（2分）其中长为4的通路中有几条回路？ （4）（2分）从3v 到4v 有几条长为4的通路？。
姓名：学号：得分：教师签名：离散数学作业7离散数学数理逻辑局部形成性查核书面作业本课程形成性查核书面作业共 3 次，内容主要别离是调集论局部、图论局部、数理逻辑局部的综合操练，底子上是按照测验的题型〔除单项选择题外〕安排练习标题问题，目的是通过综合性书面作业，使同学本身查验学习成果，找出掌握的薄弱常识点，重点复习，争取尽快掌握。
本次形考书面作业是第三次作业，大师要当真及时地完成数理逻辑局部的综合操练作业。
要求：将此作业用A4 纸打印出来，手工书写答题，笔迹工整，解答题要有解答过程，要求2021年12 月19日前完成并上交任课教师〔不收电子稿〕。
并在07 任务界面下方点击“保存〞和“交卷〞按钮，以便教师评分。
一、填空题1．命题公式P (Q P) 的真值是 1 ．2．设P：他生病了，Q：他出差了．R：我同意他不参加学习. 那么命题“如果他生病或出差了，我就同意他不参加学习〞符号化的成果为．(P Q) R3．含有三个命题变项P，Q，R 的命题公式P Q 的主析取范式是(P Q R) (P Q R) ．4．设P(x)：x 是人，Q(x)：x 去上课，那么命题“有人去上课．〞可符号化为( x)(P(x) →Q(x)) ．5．设个体域D＝{a, b},那么谓词公式xA( x) yB( y) 消去量词后的等值式为(A(a) A(b)) (B(a) B(b)) ．6．设个体域D＝{1, 2, 3} ，A(x) 为“x 大于3〞，那么谓词公式( x)A(x) 的真值为．7．谓词命题公式( x)((A(x) B(x)) C(y))中的自由变元为8．谓词命题公式( x)(P(x) Q(x) R(x，y))中的约束变元为．X ．三、公式翻译题1．请将语句“今天是天晴〞翻译成命题公式．1．解：设P：今天是天晴；那么P．2．请将语句“小王去旅游，小李也去旅游．〞翻译成命题公式．解：设P：小王去旅游，Q：小李去旅游，那么PQ．3．请将语句“如果明天天下雪，那么我就去滑雪〞翻译成命题公式．解：设P:明天天下雪。
基础部《离散数学》作业题目2011-2012学年第二学期课程名称：离散数学课程代码：GE1032计划学时：68 学分： 4课程性质：必修、考试面向专业：软件工程专业课程负责人：田检课程授课老师：田检、王涛文、商晓阳、邓炳茂广州大学华软软件学院South China Institute of Software Engineering, GuangZhou University1.作业题：第一周P33习题1.5(3)(5)(6)(7).第二周P34习题1.7(2); 1.8(2); 1.9(3)第三周P34习题1.12(2)第四周P35习题1.17(3); 1.18第五周P53习题2.1(1)(3); 2.3(3)(4)第六周P54习题2.6(2); 2.10(1); 2.12(1).第七周临时增加课外题目。
第八周P75习题3.13(2)(5); 3.14(2)第九周P75习题3.16(1)(3);临时增加课外题目。
第十周P113习题4.2;P116习题4.12第十一周P116习题4.14求自反闭包和对称闭包，传递闭包不用求。
第十二周P117习题4.16(2)第十三周P117习题4.17(1)(2); 4.25(1).第十四周P173习题7.1(2)(5); 7.5(1)(2).第十五周P174习题7.18; 7.22第十六周P203习题9.1.P204习题9.9; 9.13第十七周2.评分标准课后复习和课堂作业成绩分为ABCDE五等。
3.参考答案参考答案详见《离散数学题解(第三版)》屈婉玲等编著。
