华中科技大学计算机学院离散数学(二)样板题

附录2 习题答案习题一答案1.1下列各语句中哪些是命题?1) 不是；2) 是；3) 不是；4) 不是；5) 不是；6) 是；7) 是；8) 不是9) 不是；10)是；11)不是；12)是。

1.2 将下列命题符号化。

1) p∧⌝q, p:太阳明亮,q:湿度高；2) q→⌝p, p:明天你看到我，q:我要去深圳。

3) p→q, p:我出校，q:我去图书城；4) q→p , p:你去,q:我去；5) 5.1) p∧q； 5.2) p∧⌝q; 5.3) p∧q； 5.4) p∧⌝q；6) 6.1) p∨q 6.2) ⌝(p ↔q) 6.3) p∧¬q6.4) ¬ (p∧r) 6.5) (p∧q) →r 6.6)¬ (r→ (p∧q))7) p:蓝色和黄色可以调配成绿色；8) ⌝(p↔q), p:李兰现在在宿舍, q:李兰在图书馆里；9) ¬p→¬ q, p:一个人经一事，q:一个人长一智；10) (p∧¬q) →⌝(r↔ s), p:晚上小王做完了做业, q: 晚上小王没有其他事情，r: 晚上小王看电视, s: 晚上小王看电影。

11) ⌝(r↔ s), r:小飞在睡觉, s:小飞在游泳；12) ¬p∧¬q∧r, p:这个星期天我看电视，q: 这个星期天我外出，r:这个星期天我在睡觉。

13) p→q , p:卫星上天了，q:国家强大了；14) p→q, p:今天没有课，q:我呆在图书馆里；15) p→q,p:我去图书城，q:我有时间；16) ¬p→¬q , p:人们辛劳，p: 人们收获1.3 1) 小李家住北大西门外, 他现在坐在公共汽车里看书，没有考虑问题；2) 小李在思考问题, 他没有乘坐公共汽车，也没有看书；3) 小李只要乘坐公共汽车，他就看书或考虑问题；4) 小李乘坐公共汽车，要么看书不考虑问题，要么考虑问题不看书，5) 同4);6) 如果小李家住北大西门外,则他现在没有乘坐公共汽车，没有看书，也没有考虑问题。

一. 单项选择（每小题3分，共15分）( ) 1. 5种不同的球中取出8个，共有多少种取法(A) C(8, 5) (B) C(12, 5) (C) C(12, 8) (D) C(13, 5)( ) 2. 递推式x n = 4x n-1 - 4x n-2的通解是(A)C 1+C 22n (B)C 1n +C 22n (C) C 1n +C 2n 2n (D) (C 1+C 2n )2n( ) 3. 5个结点的完全图去掉一条边后，一定不是(A) 连通图 (B) 欧拉图 (C) 哈密顿图 (D) 平面图( ) 4. 5个结点的简单平面图的边数最多是(A) 7 (B) 8 (C) 9 (D) 10( ) 5. 完全正则二元树（满二叉树）的叶结点数是t ， 则该树的结点数一定是(A) t +t /2+1(B) 2t -1 (C) 2t (D) 2t +1二. 填空（每小题3分，共15分）1. 6个人平均分到3个不同部门的分法有___90___种；2. 5个不同的球分成3堆的分法有___25___种；3. 图G 分支数是3，节点数是10，则其边数至少是___7___；4. n 个结点的多重图（无单边弧）的邻接矩阵的主对角线以上部分所有项的和等于图的_____边数______；5. 利用欧拉定理，可得11890 ≡___1___ (mod 15)三. 解答题（共40分）1. 排列26个字母，使得a与b之间恰有7个字母，求方法数。

（6分）2×C(24,7)A(7，7)A(18，18) = 36×24!这道题的解答并不难，可以有以下的几种解法。

解法1：从24个字母（a,b除外）中任选7个字母，放置于ab之间，然后将这选出来7个字母与ab构成一个整体当成一个对象，再于剩下的17个字母（已经选了7个，再除掉ab），共18个对象全排列。

结论是C(24,7)A(7，7)A(18，18) = 36×24! 但还需要考虑到a在前b在后和b在前a在后两种不同的情况，所以答案是：2×C(24,7)A(7，7)A(18，18) = 36×24!这种做法中，不少同学没有考虑到上面ab两个字母顺序的问题，没有乘以2; 也有不少同学只考虑了剩下17个字母的全排列，没有考虑的a*******b这个整体在整个排列中的位置不同的问题。

离散数学第2版课后习题答案离散数学是计算机科学和数学领域中一门重要的学科，它研究离散对象及其关系、结构和运算方法。

离散数学的应用非常广泛，包括计算机科学、信息科学、密码学、人工智能等领域。

而离散数学第2版是一本经典的教材，它系统地介绍了离散数学的基本概念、原理和方法。

本文将为读者提供离散数学第2版课后习题的答案，帮助读者更好地理解和掌握离散数学的知识。

第一章：基本概念和原理1.1 命题逻辑习题1：命题逻辑的基本符号有哪些？它们的含义是什么？答：命题逻辑的基本符号包括命题变量、命题联结词和括号。

命题变量用字母表示，代表一个命题。

命题联结词包括否定、合取、析取、条件和双条件等，分别表示“非”、“与”、“或”、“如果...则...”和“当且仅当”。

括号用于改变命题联结词的优先级。

习题2：列举命题逻辑的基本定律。

答：命题逻辑的基本定律包括德摩根定律、分配律、结合律、交换律、吸收律和否定律等。

1.2 集合论习题1：什么是集合？集合的基本运算有哪些？答：集合是由一些确定的对象组成的整体，这些对象称为集合的元素。

集合的基本运算包括并、交、差和补等。

习题2：列举集合的基本定律。

答：集合的基本定律包括幂等律、交换律、结合律、分配律、吸收律和德摩根定律等。

第二章：数理逻辑2.1 命题逻辑的推理习题1：什么是命题逻辑的推理规则？列举几个常用的推理规则。

答：命题逻辑的推理规则是用来推导命题的逻辑规则。

常用的推理规则包括假言推理、拒取推理、假言三段论和析取三段论等。

习题2：使用推理规则证明以下命题：如果A成立，则B成立；B不成立，则A不成立。

答：假言推理规则可以用来证明该命题。

根据假言推理规则，如果A成立，则B成立。

又根据假言推理规则，如果B不成立，则A不成立。

2.2 谓词逻辑习题1：什么是谓词逻辑？它与命题逻辑有何区别？答：谓词逻辑是一种扩展了命题逻辑的逻辑系统，它引入了谓词和量词。

与命题逻辑不同，谓词逻辑可以对个体进行量化和描述。

第2次作业一、单项选择题(本大题共40分，共20小题，每小题2分)1.假设A={a, b, c, d},考虑子集S= {{a, b}, {b, c}, {d}},则下列选项正确的是()oA.S是A的覆盖B.S是A的划分C.s既不是划分也不是覆盖D.以上选项都不正确2.设h是群G上的一个同态，|G|二12,山(G)|二3,则|K| (K是h的核)二_________________ ()A.1B.2C.D.3.L23 ), 设G是连通(n,m)的平面图，有r个面，且每个面的次数至少为L( 则A.m>3n-6B.Hl <c.m+n-r=2D.m+r-n二24.如果小王和小张都不去，则小李去。

设P：小王去。

Q：小张去。

R：小李去。

则命题符号化为_________ oA.-I QA-i PVRB.(Q->P)ARC.(n PAn QLRD.(PAQ)-R5.没有不犯错误的人。

M(x)： x为人。

F (x) : x犯错误。

则命题可表示为()OA.(Vx) (M(x) F (x)B.(3x) (M(x) AF(x)C.(Vx) (M(x)AF(x))D.(3x) (M(x)-F(x)6.(1)燕子北冋，春天来了。

设P:燕了北回。

Q：春天來了。

则(1)可以表示为___________ oP->QQ-PC.UQD.P VQ7.命题公式(P->QA-i P)的类型是___________ 。

A.重言式B.矛盾式C.可满足式D.永真式6.一阶逻辑公式Vx(F(x, y)AG(y, z) )—VzF(z, y)是()前束范式封闭公式C.永真式D.永假式7.谓词公式(3x)P(x, y) A (Vx) (Q(x, z)-> Gx) (Vy)R(x, y, z)中的量词Vx 的辖域是()。

A.(Vx)(Q(x,z)->(3 x)( Vy)R(x,y ,z)B.Q(x, z)-> (Vy)R(x, y, z)C.Q (x, z) —(3x) (Vy) R (x, y, z)D.Q(x, z)8.关于半群的性质，下面说法不正确的是()A.若〈S,*>S且*在8上是封闭的，那么匸是一个半群，B<B, *>也是一个半群。

计算机学院、系2005 /2006 学年（1 ）学期期末考试试卷《离散数学II 》试卷（A 卷）专业年级班级姓名学号一、单选题(在每小题的四个备选答案中，选出一个最正确的答案，并将答案的序号填在题干的括号内。

每小题2分，共24分)1、由r棵树组成的森林的顶点数n与边数m有下列关系（ B ）。

A．n=m-r B．n=m+r C．n=m-1 D．m+n+r=02、若无向图G中不含孤立点，且存在一条经过所有边的闭路径，则（ B ）。

A．G必为哈密顿图B．G必为欧拉图C．G必为不连通图D．G必为简单图3、下图是（ C ）。

A．强连通B．单侧连通C．弱连通D．不连通4、以下是简单图的度序列的是（ C ）。

A．(5,4,3,2,2,2,1) B．(7,6,5,4,4,3,1) C．(6,43,3,3,2,1) D．(6,6,4,3,2,2,1)5、下列无向图中，不．是哈密顿图的是（ B ）。

6、满足下列条件（ A ）的无向图不一定是树。

A．边数=顶点数-1 B．任意一对结点间有且仅有一条通路C．连通且无回路D．无回路，但添加任何一条边后必产生唯一回路7、设<S,*>为一代数系统，S={e,a,b}。

*运算定义如下。

则（ D ）为其子代数。

A．<{e,a,b},⊙> B．<{a,b},*> C．<{e,a},*> D．<{e,b},*>8、以下代数系统中，群是（ D ）。

A BC D9、设<S,*>为一代数系统，a∈S，则（ A ）。

A．若a存在逆元，则其逆元未必唯一B．若<S,*>中存在幺元，则幺元未必唯一C．若<S,*>中既有幺元又有零元，则幺元、零元必不相等D．若a既有左逆元，又有右逆元，则左、右逆元必相等10、<S,○><S1,*>为两个代数系统，且存在S到S1的同态映射h，则（ B ）。

离散数学考试题(后附详细答案)一、命题符号化（共6小题，每小题3分，共计18分）1.用命题逻辑把下列命题符号化a)假如上午不下雨，我去看电影，否则就在家里读书或看报。

b)我今天进城，除非下雨。

c)仅当你走，我将留下。

2.用谓词逻辑把下列命题符号化a)有些实数不是有理数b)对于所有非零实数x，总存在y使得xy=1。

c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b.二、简答题（共6道题，共32分）1.求命题公式(P→(Q→R)) (R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋值。

（5分）2.设个体域为{1,2,3}，求下列命题的真值（4分）a)x y(x+y=4)b)y x (x+y=4)3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。

（4分）4.判断下面命题的真假，并说明原因。

（每小题2分，共4分）a)（A B）－C=(A-B) (A-C)b)若f是从集合A到集合B的入射函数，则|A|≤|B|5.设A是有穷集，|A|=5，问（每小题2分，共4分）a)A上有多少种不同的等价关系？b)从A到A的不同双射函数有多少个？6.设有偏序集<A,≤>，其哈斯图如图1，求子集B={b,d,e}的最小元，最大元、极大元、极小元、上界集合、下界集合、上确界、下确界，(5分)f g图17.已知有限集S={a1,a2,…,a n},N为自然数集合，R为实数集合，求下列集合的基数S;P(S);N,N n;P(N);R,R×R,{o,1}N（写出即可）(6分)三、证明题（共3小题，共计40分）1.使用构造性证明，证明下面推理的有效性。

（每小题5分，共10分）a)A→(B∧C),(E→ F)→ C, B→(A∧ S) B→Eb)x(P(x)→ Q(x)), x(Q(x)∨R(x))，x R(x) x P(x)2.设R1是A上的等价关系，R2是B上的等价关系，A≠ 且B≠ ，关系R满足：<<x1,y1>,<x2,y2>>∈R，当且仅当< x1, x2>∈R1且<y1,y2>∈R2。

一. 单项选择（每小题3分，总共15分）( A ) 1、在如下的有向图中，从V 1到V 4长度为3 的道路有（ A ）条。

A ． 1；B ．2；C ．3；D ．4 。

( B ) 2、假设S 、T 是两个有限集合。

那么下面正确的是：A. |S ∪T| = |S| + |T|B. |S ∪T| = |S| + |T| - |S ∩T|C. |S ×T|= |S| × |T| - |S ∩T|D. |S-T|= |S| - |T|( B )3、假定递归算法把一个规模为n 的问题分解为a 个子问题，每个子问题规模为n /b . 再假定把子问题的解组合成原来问题的解的算法处理中，需要总量为g (n )的运算数. 用f (n )表示求解规模为n 的问题所需的运算数，则得出运算数f (n )的递推关系为：A ．f (n ) = b f (n /a) + g (n )；B ．f (n ) = af (n /b ) + g (n )；C ．f (n ) = f (n /b ) +a g (n )；D ．f (n ) = ag (n /b ) + f(n )；( D ) 4、如果两个图H 与G 同构，且结点数大于1，则下面不正确的是：A ．如果H 有一个子图是非平面图，则G 是非平面图B ．如果H 是连通图，则G 没有孤立点。

C ．H 是偶图则G 也是偶图，反之也成立D ．f 是H 的结点集到G 的结点集的双射，则H 的任一结点h 的度数等于G 中结点f(h)的度数。

( D ) 5、下面说法不正确的是：A ：不同算法求出的两个不同结点的最短通路的长度是一样的。

B: 不同算法求得的两个不同结点的最短通路可能不一样。

C: 连通有权图的任两个不同结点的最短通路一定是存在的。

D ：最短通路未必就是简单路。

二. 填空（每小题3分，总共15分）1、连通无向图有欧拉开路（非回路）的充要条件是2、 83个不同的盒子中,5、三. 解答题（总共40分，每小题5分）1、一个(n,m)简单无向图是2-色图(m>0)，那么它上面的所有回路是否都是偶数长？为什么？解答：简单无向图是2-色图(m>0) 就必然是偶图。

大学离散数学试卷二及答案一、单项选择题 （2分×10=20分）1、下列语句是命题的有[ B ]。

A. 122>+y x ；B. 2010年的国庆节是晴天；C. 青年学生多么朝气蓬勃呀！D. 学生不准吸烟!2、在命题逻辑中，任何命题公式的主合取范式都 [ C ]。

A. 不一定存在;B. 不存在；C. 存在且唯一;D. 存在但不唯一.3、设S={1,2,3,4}，R={<1,1>,<3,3>,<4,4>}，则R 满足的性质是 [ C ]A. 自反、对称、传递的 ;B. 自反、对称、反对称的;C. 对称、反对称、传递的;D. 只有对称性.4. 与命题p ∧(p ∨q)等值的公式是 [ A ]。

A. p ；B. q ；C. p ∨q ；D. p ∧q.5. 设M={a,b,c}，M 上的等价关系R={<a,a>,<b,b>,<c,c>,<b,c>,<c,b>}确定的集合M 的划分是[ D ]。

A.{{a},{b},{c}}B.{{a,c},{b,c}}C.{{a,c},{b}}D.{{a},{b,c }}6. 设D ：全总个体域，F （x ）：x 是花，M(x) ：x 是人，H(x,y)：x 喜欢y ，则命题“每个人都喜欢某种花”的逻辑符号化为[ C ]。

A. )),()(()((y x H y F y x M x →∃∧∀；B. )),()(()((y x H y F y x M x →∃→∀；C. )),()(()((y x H y F y x M x ∧∃→∀；D. )),()(()((y x H y F y x M x ∧∀→∃.7. 下列图中，不是哈密顿图的为[ A ]。

A B C D8. 下列四组数据中，能作为某个4阶无向简单图的度序列的为[ D ]。

A. 1,2,3,4 ；B. 2,2,2,3；C. 1,1,2,3；D. 1,1,1,3.9. 一棵无向树T 有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T 中有[ C ]片树叶。

离散数学考试题目及答案一、单项选择题（每题2分，共20分）1. 集合A={1,2,3}，集合B={3,4,5}，则A∩B的元素个数为：A. 0B. 1C. 2D. 3答案：B2. 函数f: X→Y是一个双射，当且仅当：A. f是单射且满射B. f是单射C. f是满射D. f是双射答案：A3. 命题p: "x是偶数"，命题q: "x是3的倍数"，下列逻辑运算中，表示"x是6的倍数"的是：A. p∧qB. p∨qC. ¬p∧¬qD. ¬p∨¬q答案：A4. 有向图G中，若存在从顶点u到顶点v的有向路径，则称顶点u可达顶点v。

若G中任意两个顶点都相互可达，则称G为：A. 强连通图B. 弱连通图C. 无向图D. 有向无环图答案：A5. 在二进制数系统中，下列哪个数的值最大？A. 1010B. 1100C. 1110D. 1101答案：C6. 布尔代数中，逻辑或运算符表示为：A. ∧B. ∨C. ¬D. →答案：B7. 有限自动机中，状态q0是初始状态，状态q1是接受状态。

若存在从q0到q1的ε-转移，则该自动机：A. 仅在输入为空时接受B. 仅在输入非空时接受C. 无论输入为何都接受D. 无法确定是否接受答案：C8. 命题逻辑中，若命题p和q都为真，则p∧q的真值是：A. 真B. 假C. 可能为真，也可能为假D. 无法确定答案：A9. 集合{1,2,3}的子集个数为：A. 4B. 6C. 7D. 8答案：D10. 若关系R在集合A上是自反的，则对于A中的任意元素a，有：A. (a,a)∈RB. (a,a)∉RC. (a,a)是R的自反对D. (a,a)不是R的自反对答案：A二、填空题（每题3分，共15分）1. 集合A={1,2,3}的幂集包含__个元素。

答案：82. 若函数f: X→Y是满射，则对于Y中的任意元素y，至少存在X中的一个元素x，使得f(x)=__。