离散数学2
离散数学作业5
离散数学图论部分形成性考核书面作业
本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业．
要求：将此作业用A4纸打印出来，并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，完成后上交任课教师（不收电子稿）．
一、填空题
1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 ．
2．设给定图G (如右由图所示)，则图G 的点割集是 ．
3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 等于边数的两倍．
4．无向图G 存在欧拉回路，当且仅当G 连通且 ． 5．设G=
6．若图G=
7．设完全图K n 有n 个结点(n 2)，m 条边，当 时，K n 中存在欧拉回路．
8．结点数v 与边数e 满足 关系的无向连通图就是树． 9．设图G 是有6个结点的连通图，结点的总度数为18，则可从G 中删去 条边后使之变成树．
10．设正则5叉树的树叶数为17，则分支数为i = ．
二、判断说明题（判断下列各题，并说明理由．）
1．如果图G 是无向图，且其结点度数均为偶数，则图G 存在一条欧拉回路．
2．如下图所示的图G存在一条欧拉回路．
3．如下图所示的图G不是欧拉图而是汉密尔顿图．
G
4．设G是一个有7个结点16条边的连通图，则G为平面图．
5．设G是一个连通平面图，且有6个结点11条边，则G有7个面．
三、计算题
1．设G=
(1) 给出G的图形表示；(2) 写出其邻接矩阵；
(3) 求出每个结点的度数；(4) 画出其补图的图形．
2．图G=
（3）求出G权最小的生成树及其权值．
3．已知带权图G如右图所示．
(1) 求图G的最小生成树；(2)计算该生成树的权值．
4．设有一组权为2, 3, 5, 7, 17, 31，试画出相应的最优二叉树，计算该最优二叉树的权．
四、证明题
1．设G 是一个n 阶无向简单图，n 是大于等于3的奇数．证明图G 与它的补图G 中的奇数度顶点个数相等．
2．设连通图G 有k 个奇数度的结点，证明在图G 中至少要添加2
k
条边才能使其成为欧拉图．
离散数学第二次在线作业
第二次在线作业 1.（ 2.5分）代数系统是指由集合及其上的一元或二元运算符组成的系统 ?正确 ?错误 我的答案：正确此题得分：2.5分 2.（2.5分）设< L*1*2> 是代数系统，其中是*1*2二元运算符，如果*1*2都满足交换律、结合律，并且*1和*2满足吸收律，则称< L*1*2> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 3.（2.5分）对实数的普通加法和乘法，0是加法的幂等元，1是乘法的幂等元 ?正确 ?错误 我的答案：正确此题得分：2.5分 4.（2.5分）零元是不可逆的 ?正确 ?错误 我的答案：正确此题得分：2.5分 5.（2.5分）群中每个元素的逆元都是惟一的 ?正确 ?错误 我的答案：正确此题得分：2.5分
6.（2.5分）设abc是阿贝尔群< G+> 的元素，则-(a+b+c)=(-a)+( -b)+( -c) ?正确 ?错误 我的答案：正确此题得分：2.5分 7.（2.5分） < {01234}MAXMIN> 是格 ?正确 ?错误 我的答案：正确此题得分：2.5分 8.（2.5分）一个图的哈密尔顿路是一条通过图中所有结点一次且恰好一次的路 ?正确 ?错误 我的答案：正确此题得分：2.5分 9.（2.5分）在有向图中，结点v的出度deg+(v)表示以v为起点的边的条数，入度deg-(v)表示以v为终点的边的条数 ?正确 ?错误 我的答案：正确此题得分：2.5分 10.（2.5分）一个图的欧拉回路是一条通过图中所有边一次且恰好一次的回路 ?正确 ?错误 我的答案：正确此题得分：2.5分
11.（2.5分）不含回路的连通图是树 ?正确 ?错误 我的答案：正确此题得分：2.5分 12.（2.5分）简单图邻接矩阵主对角线上的元素全为0 ?正确 ?错误 我的答案：正确此题得分：2.5分 13.（2.5分）树一定是连通图 ?正确 ?错误 我的答案：正确此题得分：2.5分 14.（2.5分）无向图的邻接矩阵是对称阵 ?正确 ?错误 我的答案：正确此题得分：2.5分 15.（2.5分）不与任何结点相邻接的结点称为孤立结点 ?正确 ?错误 我的答案：正确此题得分：2.5分
离散数学答案屈婉玲版第二版高等教育出版社课后答案
离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 （1）p∨(q∧r)?0∨(0∧1) ?0 （2）（p?r）∧(﹁q∨s) ?（0?1）∧(1∨1) ?0∧1?0. （3）（?p∧?q∧r）?(p∧q∧﹁r) ?（1∧1∧1）? (0∧0∧0)?0 (4)（?r∧s）→(p∧?q) ?（0∧1）→(1∧0) ?0→0?1 17．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 答：p: π是无理数1 q: 3是无理数0 r: 2是无理数 1 s: 6能被2整除1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型： （4）(p→q) →(?q→?p) （5）(p∧r) ?(?p∧?q) （6）((p→q) ∧(q→r)) →(p→r) 答：（4） p q p→q ?q ?p ?q→?p (p→q)→(?q→?p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式
（5）公式类型为可满足式（方法如上例） （6）公式类型为永真式（方法如上例） 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 答：(2)（p→(p∨q)）∨(p→r)?(?p∨(p∨q))∨(?p∨r)??p∨p∨q∨r?1所以公式类型为永真式 (3)P q r p∨q p∧r （p∨q）→(p∧r) 0 0 0 0 0 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 1 所以公式类型为可满足式 4.用等值演算法证明下面等值式： (2)(p→q)∧(p→r)?(p→(q∧r)) (4)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) 证明（2）(p→q)∧(p→r) ?(?p∨q)∧(?p∨r) ??p∨(q∧r)) ?p→(q∧r) （4）(p∧?q)∨(?p∧q)?(p∨(?p∧q)) ∧(?q∨(?p∧q)
离散数学试卷及答案(2)
一、填空 20% （每小题2分） 1、 P ：你努力，Q ：你失败。“除非你努力，否则你将失败”的翻译为 ；“虽然你努力了，但还是失败了”的翻译为 。 2、论域D={1，2}，指定谓词P 则公式),(x y yP x ??真值为 。 2、 设S={a 1 ，a 2 ，…，a 8}，B i 是S 的子集，则由B 31所表达的子集是 。 3、 设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则R= （列举法）。 R 的关系矩阵M R = 。 5、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系R= ； A 上既是对称的又是反对称的关系R= 。 6、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 7、4阶群必是 群或 群。 8、下面偏序格是分配格的是 。
9、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 10、公式R Q P Q P P ?∧∨?∧∧?∨)(())(( 的根树表示为 。 二、选择 20% （每小题2分） 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→ 。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、 设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为
屈婉玲版离散数学课后习题答案【2】
第四章部分课后习题参考答案 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)在两个个体域中都解释为)(x xF ?，在（a ）中为假命题，在(b)中为真命题。 (2)在两个个体域中都解释为)(x xG ?，在（a ）(b)中均为真命题。 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x 能表示成分数 H(x): x 是有理数 命题符号化为: ))()((x H x F x ∧??? (2)F(x): x 是北京卖菜的人 H(x): x 是外地人 命题符号化为: ))()((x H x F x →?? 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x 是火车; G(x): x 是轮船; H(x,y): x 比y 快
命题符号化为: )) F x G x→ ∧ ? ? y y ( )) ( ) , x ((y ( H (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快 命题符号化为: ))) x x F y y→ ?? ∧ ? G (y H ( , ( ) ( ( x ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素错误！未找到引用源。=0. (c) 特定函数错误！未找到引用源。(x,y)=x错误！未找到引用源。y,x,y D ∈错误！未找到引用源。. (d) 特定谓词错误！未找到引用源。(x,y):x=y,错误！未找到引用源。(x,y):x 一、填空题 1. 设A = {1, 2}, B = {2, 3}, 则A - A =________, A – B =________, B – A =________. 2. 设N 是自然数集合, f 和g 是N 到N 的函数, 且f (n ) = 2n +1，g (n ) = n 2, 那么复合函数(f f ) (n )=________ , (f g ) (n )=________ , (g f ) (n ) =________. 3. 设|X | = n , P (X )为集合X 的幂集, 则| P (X )| = ________. 在代数结构(P (X ), ∪)中，则P (X ) 对∪运算的单位元是________, 零元是________ . 4. 在下图中， _______________________________是其Euler 路 . 5. 设有向图G = (V , E )，V = {v 1，v 2，v 3，v 4}，若G 的邻接矩阵A =???? ??????1001001111011010, 则v 1的出度deg +(v 1) =________, v 1的入度deg -(v 1) =________, 从v 2到v 4长度为2的路有________条. 二、单选题 1. 设A = {{1, 2, 3}, {4, 5}, {6, 7, 8}}, 下列选项正确的是( ) (A) 1∈A (B) {1, 2, 3}?A (C) {{4, 5}}?A (D) ?∈A . 2．集合A = {1, 2, …, 10}上的关系R ={(x , y )|x + y = 10, x , y ∈A }, 则R 的性质是 ( ) (A) 自反的 (B) 对称的 (C) 传递的、对称的 (D) 反自反的、传递的. 3．若R 和S 是集合A 上的两个关系，则下述结论正确的是( ) (A) 若R 和S 是自反的, 则R ∩S 是自反的 (B) 若R 和S 是对称的, 则R S 是对称的 (C) 若R 和S 是反对称的, 则R S 是反对称的 (D) 若R 和S 是传递的, 则R ∪S 是传递的. 4．集合A = {1, 2, 3, 4}上的关系 R = {(1, 4), (2, 3), (3, 1), (4, 3)}, 则下列不是．．t (R )中元素的是( ) (A) (1, 1) (B) (1, 2) (C) (1, 3) (D) (1, 4). 5．设p ：我们划船，q ：我们跑步, 则有命题“我们不能既划船又跑步”符号化为( ) (A) ? p ∧? q (B) ? p ∨? q 离散数学图论部分综合练习 一、单项选择题 1．设无向图G 的邻接矩阵为 ??????? ? ??? ?? ???010 1010010000 011100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝ A．{(a, e)}是割边B．{(a, e)}是边割集 C．{(a, e) ,(b, c)}是边割集D．{(d, e)}是边割集 图三 7．设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )． 图四 A．（a）是强连通的B．（b）是强连通的 C．（c）是强连通的D．（d）是强连通的 应该填写：D 8．设完全图K n 有n个结点(n≥2)，m条边，当（）时，K n 中存在欧拉 回路． A．m为奇数B．n为偶数C．n为奇数D．m为偶数9．设G是连通平面图，有v个结点，e条边，r个面，则r= ( )． A．e－v＋2 B．v＋e－2 C．e－v－2 D．e＋v＋2 10．无向图G存在欧拉通路，当且仅当( )． A．G中所有结点的度数全为偶数 B．G中至多有两个奇数度结点 C．G连通且所有结点的度数全为偶数 D．G连通且至多有两个奇数度结点 11．设G是有n个结点，m条边的连通图，必须删去G的( )条边，才能确定G的一棵生成树． A．1 m n-+B．m n-C．1 m n++D．1 n m -+ 12．无向简单图G是棵树，当且仅当( )． A．G连通且边数比结点数少1 B．G连通且结点数比边数少1 离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111 2013年4月考试离散数学第二次作业 一、单项选择题（本大题共50分，共 25 小题，每小题 2 分） 1. 下列语句中为命题的是（） A. 暮春三月，江南草长. B. 这是多么可爱的风景啊！ C. 大家想做什么，就做什么，行吗？ D. 请勿践踏草地！ 2. 2.设G是n个顶点的无向简单图，则下列说法不正确的是（） A. 若G是树，则其边数等于n-1 B. 若G是欧拉图，则G中必有割边 C. 若G中有欧拉路，则G是连通图，且有零个或两个奇度数顶点 D. 若G中任意一对顶点的度数之和大于等于n-1，则G中有汉密尔顿路 3. 集合|A|=3，|B|=2，则A B上不同的函数个数为（）。 A. 3+2个 B. 32个 C. 2*3个 D. 23个 4. 设A-B=φ，则以下正确的是（）。 A. A＝B B. A?B C. B?A D. 以上都不对 5. 设R为实数集，函数f：R→R，f(x)=2x，则f是（） A. 满射函数 B. 入射函数 C. 双射函数 D. 非入射非满射 6. 设B={a,b,c},C={1,2,3,4}，以下哪个关系是从B到C的单射函数？（） A. f={<1,8>,<3,9>,<4,10>,<2,6>,<5,7>} B. f={<1,7>,<2,6>,<4,8>,<1,9>,<5,10>} C. f={<1,7>,<2,7>,<4,9>,<3,8>} D. f={<1,10>,<5,9>,<3,6>,<4,6>,<2,8>} E. f={<1,7>,<5,10>,<2,6>,<4,8>,<3,9>} 7. 下述*运算为实数集上的运算，其中可交换且可结合的运算是（）。 A. a*b=a+2b B. a*b=a+b-ab C. a*b=a D. a*b=|a+b| 8. 在下列命题中，为真的命题是（） A. 汉密顿图一定是欧拉图 B. 无向完全图都是欧拉图 C. 度数为奇数的结点个数为0个或2个的连通无向图G可以一笔画出 D. 有割点的连通图是汉密顿图 9. 设p:小李努力学习，q:小李取得好成绩，命题“只有小李努力学习，他才能取得好成绩”的符号化形式为（）。 A. B. C. 离散数学(第2版)_在线作业_2 交卷时间：2017-01-12 10:56:42 一、单选题 1. (5分) 设R是实数集合，R上的运算*定义为，则为( )。 纠错 得分： 5 知识点：离散数学(第2版) 收起解析 答案 B 解析 2. (5分) ? 得分： 5 知识点：离散数学(第2版) 收起解析 答案 B 解析 3. (5分) 纠错 得分： 5 知识点：离散数学(第2版) 收起解析 答案 C 解析 4. (5分) 谓词公式中变元( )。 得分： 5 知识点：离散数学(第2版) 收起解析 答案 C 解析 5. (5分) 设上的关系，则R的定义域等于( )。 ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点：离散数学(第2版) 收起解析 答案 D 解析 6. (5分) 集合的交运算不满足( )。 得分： 5 知识点：离散数学(第2版) 收起解析 答案 B 解析 7. (5分) 纠错 得分： 5 知识点：离散数学(第2版) 收起解析 答案 A 解析 8. (5分) ? B. ? C. ? D. 集合的并运算不满足( )。 设，下面命题为假的是( )。 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 9. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 10. (5分) ? A. ? B. ? C. ? D. 纠错 前提，，的逻辑结论不会是( )。 。 得分： 5 知识点：离散数学(第2版) 收起解析 答案 A 解析 11. (5分) 纠错 得分： 5 知识点：离散数学(第2版) 收起解析 答案 B 解析 12. (5分) 。 ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点：离散数学(第2版) 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = _________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是_________________________ _____________, 其中双射的是_____ 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________，_____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。 16. 设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。 x x P :)(是素数，)(x P 可表示为)1)(()1(x u u x u v v u x =∨=?=???∧=?。 离散数学(第2版)_在线作业_1 交卷时间：2017-01-12 10:34:32 一、单选题 1. (5分) ? A. P∨┐Q ? B. P∧┐Q ? C. ┐P ∧Q ? D. ┐P∨Q 纠错 得分：5 知识点：离散数学(第2版) 收起解析 答案A 解析 2. (5分) ? A. ? B. ? C. 命题变元P和Q的极大项M1表示( )。 设，下面集合等于A的是( )。 ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 B 解析 3. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 4. 下面既是哈密顿图又是欧拉图的是( )。 ? A. 水开了吗？ ? B. ? C. 请不要抽烟! ? D. 再过5000年，地球上就没有水了 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 5. (5分) ? A. 2n-1 ? B. n ? C. n+1 ? D. n-1 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 6. 下列语句中为命题的是( )。 n 个结点、m 条边的无向连通图是树当且仅当m=( )。 ? A. P ∨┐Q ? B. ┐P ∨Q ? C. ┐P ∧Q ? D. P ∧┐Q 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 7. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 B 解析 命题变元P 和Q 的极小项m 1表示( )。 公式的前束范式为( )。 离散数学（2）复习题 一、判断题 1、两个集合相等的充分必要条件是这两个集合互为补集。（ × ） 2、两个集合相等的充分必要条件是这两个集合互为子集。（ √ ） 3、两个集合相等的充分必要条件是这两个集合互为幂集。（ × ） 4、对于任意一个集合A ，A f í。（ √ ） 5、对于任意一个集合A ，A f ?。（ × ） 6、如果有限集合有n 个元素，则其幂集有2n 个元素。（ √ ） 7、设R 、S 是集合A 上的关系，且R S ê，则()()s R s S ê。（ √ ） 8、设R 、S 是集合A 上的关系，且R S ê，则()()t R t S ê。（ √ ） 9、设R 、S 是集合A 上的关系，且R S ê，则()()r R r S ê。（ √ ） 10、一个关系可以：既不满足自反性，也不满足非自反性。（ √ ） 11、一个关系可以：既不满足对称性，也不满足反对称性。（ √ ） 12、一个关系可以：既满足对称性，同时也满足反对称性。（ √ ） 13、若图G 是不连通的，则图G 的补图G - 是连通的。（ √ ） 二、单项选择题 1、由集合运算定义，下列各式正确的有（ A ）。 A.X ?X ?Y B.X ?X ?Y C.X ?X ?Y D.Y ?X ?Y 2、设A B -=?，则有（ C ）。 A.B =? B.B ≠? C.A B ? D.A B ? 3、对任意的集合A 、全集U ，下列命题为假的是（ D ）。 A.A ?? ＝A ， B.A ?U = U C.A ?? = ?， D.A ?U = U 4、集合A={1，2，…，10}上的关系R={ 离散数学课后习题答案(左孝凌版) 1-1，1-2解： a)是命题，真值为T。 b)不是命题。 c)是命题，真值要根据具体情况确定。 d)不是命题。 e)是命题，真值为T。 f)是命题，真值为T。 g)是命题，真值为F。 h)不是命题。 i)不是命题。 （2）解： 原子命题：我爱北京天安门。 复合命题：如果不是练健美操，我就出外旅游拉。 （3）解： a)(┓P ∧R)→Q b)Q→R c)┓P d)P→┓Q （4）解： a)设Q:我将去参加舞会。R:我有时间。P:天下雨。 Q (R∧┓P):我将去参加舞会当且仅当我有时间和天不下雨。 b)设R:我在看电视。Q:我在吃苹果。 R∧Q:我在看电视边吃苹果。 c) 设Q:一个数是奇数。R:一个数不能被2除。 （Q→R）∧(R→Q):一个数是奇数，则它不能被2整除并且一个数不能被2整除，则它是奇数。 (5) 解： a)设P：王强身体很好。Q：王强成绩很好。P∧Q b)设P：小李看书。Q：小李听音乐。P∧Q c)设P：气候很好。Q：气候很热。P∨Q d)设P： a和b是偶数。Q：a+b是偶数。P→Q e)设P：四边形ABCD是平行四边形。Q ：四边形ABCD的对边平行。P Q f)设P：语法错误。Q：程序错误。R：停机。（P∨ Q）→ R (6) 解： a)P:天气炎热。Q:正在下雨。 P∧Q b)P:天气炎热。R:湿度较低。 P∧R c)R:天正在下雨。S:湿度很高。 R∨S d)A:刘英上山。B:李进上山。 A∧B e)M:老王是革新者。N:小李是革新者。 M∨N f)L:你看电影。M:我看电影。┓L→┓M g)P:我不看电视。Q:我不外出。 R:我在睡觉。 P∧Q∧R h)P:控制台打字机作输入设备。Q:控制台打字机作输出设备。P∧Q 1-3 （1）解： 第二章 谓词逻辑 习题与解答 1. 将下列命题符号化： (1) 所有的火车都比某些汽车快。 (2) 任何金属都可以溶解在某种液体中。 (3) 至少有一种金属可以溶解在所有液体中。 (4) 每个人都有自己喜欢的职业。 (5) 有些职业是所有的人都喜欢的。 解 (1) 取论域为所有交通工具的集合。令 x x T :)(是火车， x x C :)(是汽车， x y x F :),(比y 跑得快。 “所有的火车都比某些汽车快”可以符号化为))),()(()((y x F y C y x T x ∧?→?。 (2) 取论域为所有物质的集合。令 x x M :)(是金属， x x L :)(是液体， x y x D :),(可以溶解在y 中。 “任何金属都可以溶解在某种液体中” 可以符号化为))),()(()((y x D y L y x M x ∧?→?。 (3) 论域和谓词与(2)同。“至少有一种金属可以溶解在所有液体中” 可以符号化为))),()(()((y x D y L y x M x →?∧?。 (4) 取论域为所有事物的集合。令 x x M :)(是人， x x J :)(是职业， x y x L :),(喜欢y 。 “每个人都有自己喜欢的职业” 可以符号化为))),()(()((y x L y J y x M x ∧?→? (5)论域和谓词与(4)同。“有些职业是所有的人都喜欢的”可以符号化为))),()(()((x y L y M y x J x →?∧?。 2. 取论域为正整数集，用函数+（加法），?（乘法）和谓词<，=将下列命题符号化： (1) 没有既是奇数，又是偶数的正整数。 (2) 任何两个正整数都有最小公倍数。 (3) 没有最大的素数。 (4) 并非所有的素数都不是偶数。 解 先引进一些谓词如下： x y x D :),(能被y 整除，),(y x D 可表示为)(x y v v =??。 x x J :)(是奇数，)(x J 可表示为)2(x v v =???。 x x E :)(是偶数，)(x E 可表示为)2(x v v =??。 离散数学 一、判断下列句子哪些是命题（在答题纸写上题目标号，并将正确答案写在答题纸相应位置处。答案错或未答者，该题不得分。每空1分，共10分。） 1、除非小王穿羽绒服，否则天不冷。 2、如果天不冷，则小王不穿羽绒服。 3、小王穿羽绒服仅当天冷的时候。 4、2 + 2 ＝ 4 当且仅当 3 + 3 ＝ 6。 5、2 + 2 ＝ 4 当且仅当 3 是偶数。 6、2 + 2 ＝ 4 当且仅当太阳从东方升起。 7、2 + 2 ＝ 4 当且仅当美国位于非洲。 8、函数f (x) 在x0可导的充要条件是它在x0连续。 9、如果我上街，我就去书店，除非我很累。 10、若不是他生病或出差了，我是不会同意他不参加学习的。 二、命题符号化题（在答题纸写上题目标号，并将正确答案写在答题纸相应位置处。答案错或未答者，该题不得分。每空3分，共15分。） 1、若不是他生病或出差了，我是不会同意他不参加学习的。 2、如果张三和李四都不去，他就去。 3、我们不能既划船又跑步。 4、一个人起初说“占据空间的,有质量的而且不断变化叫做物质”；后来他说：”占据空间的有质量的叫做物质，而物质是不断变化的”。请将他第前主张符号化 5、一个人起初说“占据空间的,有质量的而且不断变化叫做物质”；后来他说：”占据空间的有质量的叫做物质，而物质是不断变化的”。请将他的后主张符号化 三、判断题（在答题纸写上题目标号，并将正确答案写在答题纸相应位置处。答案错或未答者，该题不得分。每题5分，共10分。） 1、P ?Q 与(P ∧Q )∨(?P ∧?Q ) 是否等价？ 2、判断函数f：R+→R+, f(x)=(x2+1)/x, 其中R+为正实数集是否为单射, 满射, 双射的, 为什么? 四、证明题（在答题纸写上题目标号，并将正确答案写在答题纸相应位置处。答案错或未答者，该题不得分。每题5分，共20分。） 1、试证明 p→(q→r) ? (p∧q)→r 2、构造下面推理的证明： 前提：? (p∧q) ∨r, r→s, ?s, p，结论：?q 3、对于集合A、B和C ，证明A?C ?B?C ∧A-C ?B-C ?A?B 4、设F, G, H是任意的关系, 则 (F°G)°H=F°(G°H) 五、求范式（在答题纸写上题目标号，并将正确答案写在答题纸相应位置处。答案错或未答者，该题不得分。每题5分，共10分。） 1、求(P→Q)<->R的主析取范式 2、求?x(F(x,y)→?y(G(x,y)∧H(x,z)))的前束范式 六、应用题（在答题纸写上题目标号，并将正确答案写在答题纸相应位置处。答案错或未答者，该题不得分。每题10分，共20分。） 1、在某次球赛中，3位球迷甲、乙、丙对某球队的比赛结果进行猜测 甲说：该球队不会得第一名，是第二名； 乙说：该球队不会得第二名，是第一名； 丙说：该球队不会得第二名，也不会是第三名。 比赛结束后，比赛结果证实甲、乙、丙3人中有1人猜的全对，有1人猜对了一半，有1人猜的全错。试分析该队究竟是第几名？ 2、 某班有25个学生，其中 篮球：14；排球：12； 篮球和排球：6；篮球和网球：5； 第1次作业 一、单项选择题（本大题共30分，共 15 小题，每小题 2 分） 1. 图G所示平面图deg(R3)为 A. 4 B. 5 C. 6 D. 3 2. 在完全m叉树中，若树叶数为t，分枝点数为i，则有（）。 A. (m-1)i C. (m-1)i=t-1 D. (m-1)i≤t-1 3. 命题a）：如果天下雨，我不去。写出命题a）的逆换式。 A. 如果我不去，天下雨。 B. 如果我去，天下雨。 C. 如果天下雨，我去。 D. 如果天不下雨，我去。 4. 设无向图中有6条边，3度与5度顶点各1个，其余顶点都是2度点，问该图有多少个顶点（） A. 5 B. 4 C. 2 D. 6 5. 假设A={a,b,c,d},考虑子集S={{a,b},{b,c},{d}}，则下列选项正确的是（）。 A. S是A的覆盖 B. S是A的划分 C. S既不是划分也不是覆盖 D. 以上选项都不正确 6. 没有不犯错误的人。M(x)：x为人。F（x）：x犯错误。则命题可表示为（）。 A. (?x)(M(x)→F(x) B. (?x)(M(x)?F(x) C. （?x）(M(x)?F(x)) D. (?x)(M(x)→F(x) 7. 命题逻辑演绎的CP规则为（） A. 在推演过程中可随便使用前提 B. 在推演过程中可随便使用前面演绎出的某些公式的逻辑结果 C. 如果要演绎出的公式为B→C形式，那么将B作为前提，演绎出C D. 设?(A)是含公式A的命题公式，B<=>A，则可以用B替换?(A)中的A 8. 设G是有6个结点的完全图，从G中删去（）条边，则得到树。 A. 6 B. 9 C. 10 D. 离散数学(第2版)_在线作业_3 交卷时间： 2017-01-12 13:46:31 一、单选题 1. (5分 ) ? A. 简单图 ? B. 多重图 ? C. 树 ? D. 完全图 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 B 解析 2. (5分) 设为无环的无向图，，，则G 是( )。 ? A. 哈密顿图 ? B. 完全图 ? C. 平面图 ? D. 欧拉图 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 3. (5分) ? A. 有么元、可结合 ? B. 有零元、可交换 ? C. 满足结合律、交换律 ? D. 有么元、可交换 纠错 得分： 5 知识点： 离散数学(第2版) 设G 如右图，则G 不是( )。 . 若是群，则运算( )。 答案 A 解析 4. (5分) ? A. G 只有一个顶点的入度为1 ? B. G 只有一个顶点的出度为0 ? C. G 一定是弱连通的 ? D. G 一定是强连通的 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 5. (5分) ? A. ? B. ? C. ? D. G 是一棵根树，则( )。 设：，：雪是黑色的，：，：太阳从东方升起，则下列 为真的命题是( )。 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 6. (5分 ) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 A 解析 7. (5分) ? A. 16 ? B. 14 ? C. 12 下列集合为前缀码的是( )。 设G 是连通的平面图，G 中有11个顶点，5个面，则G 中的边数为( )。 21st Century University Planned Textbooks of Computer Science (第2版) Discrete Mathematics (2nd Edition) 李盘林赵铭伟徐喜荣李丽双编著 □概念严谨精炼 □叙述简明清晰 □推理详尽严格 人民邮电出版社 POSTS & TELECOM PRESS 第2版前言 离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础。因此，它是计算机科学与技术专业的核心、骨干课程。一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理和人工智能等，提供必要的数学基础；另一方面，通过学习离散数学，培养和提高了学生的抽象思维和逻辑推理能力，为其今后继续学习和工作，进行科学研究，攀登科技高峰，打下扎实的数学基础。 本书第1版于2002年2月出版以来，六年来，先后多次印刷发行，已得到了普遍认可，被全国部分普通高校选作教材，本版除了勘误了第1版中的不妥之处外，还增加了一些新的章节，并相应补充了例题和习题，以适应高等学校教学改革的需要。 本书共12章，内容包括命题逻辑、谓词逻辑、集合、关系、函数、代数结构的概念及性质、半群与群、环和域、格与布尔代数、图的概念与表示、几类重要的图以及数论。 本书是笔者结合多年教学实践与科学研究，参考国内外教材，在力求通俗易懂、简明扼要的指导思想下编写而成的。在编写过程中有如下3点考虑。 1. 力求做到“少而精”，注意突出重点，论证详细明了，便于自学，在定理证明中多次运用归纳法，希望读者熟练掌握这一方法。 2. 在加强基本理论教学的同时，注意了分析问题、解决问题的技能培养和训练。书中各知识点均配有典型例子，并加以说明。此外，各章都配有适量的习题，希望通过做习题这个环节，来培养、提高学生解决问题的能力。 3. 一方面每章各有独立性，教师根据需要可以单独选讲几章；另一方面，尽可能注意各章之间的联系，规范并统一了符号和术语。 本书在编写过程中，得到了有关领导、老师和同学的热情关心、支持和帮助，在此一并表示感谢。 限于作者水平，书中难免有不当和疏漏之处，恳请读者批评指正。 编者 于大连理工大学 2008年9月《离散数学》第2次作业
上海大学-离散数学2-图部分试题
离散数学作业 (2)
2013年4月考试离散数学第二次作业
离散数学(第2版)-在线作业-2
《离散数学》试题及答案 (2)
离散数学答案第二章习题解答
离散数学(第2版)_在线作业_1
离散数学2
离散数学课后习题答案(左孝凌版)
离散数学答案(尹宝林版)第二章习题解答
离散数学2
离散数学(第1次)
离散数学(第2版)_在线作业_3
离散数学(第2版)电子教案
- 离散数学(第二版)最全课后习题答案详解
- 清华离散数学(第2版)
- 离散数学答案解析屈婉玲版第二版高等教育出版社课后答案解析
- 离散数学(第2版)_在线作业_3
- 离散数学(第2版)电子教案
- 离散数学(第二版)最全课后习题答案详解
- 离散数学(第2版)-在线作业-3
- 离散数学(第2版)_在线作业_1
- 离散数学 第二版 课后习题答案详解
- 离散数学答案屈婉玲版第二版高等教育出版社课后答案
- 离散数学答案屈婉玲版第二版高等教育出版社课后答案
- 离散数学答案屈婉玲版第二版 高等教育出版社课后答案
- 离散数学第二版邓辉文编著第一章第二节习题答案
- 离散数学(第2版)_在线作业_3
- 离散数学答案屈婉玲版第二版高等教育出版社课后答案
- 离散数学(第二版)课后习题答案详解(完整版)
- 离散数学答案解析屈婉玲版第二版高等教育出版社课后答案解析
- 离散数学答案 屈婉玲版 第二版 高等教育出版社课后答案
- 离散数学(第2版)_在线作业_4
- 离散数学第二版 屈婉玲 1-5章(答案)