离散数学作业标准答案

离散数学作业一、选择题 1、下列语句中哪个是真命题（C）。A我正在说谎。B如果1+2=3，那么雪是黑色的。C如果1+2=5，那么雪是白色的。D严禁吸烟！2、设命题公式，则G是（ C ）。A. 恒假的 B. 恒真的 C. 可满足的 D. 析取范式3、谓词公式中的变元（ C ）。 A是自由变元但不是约束变元 B既不是自由变元又不是约束变元 C既是自由变元又是约束变元 D是约束变元但不是自由变元4、设A=1，2，3，则下列关系R不是等价关系的是（C ）AR=， BR=，CR=，DR=，5、设R为实数集，映射s=RR，s（x）= -x2+2x-1，则s是（ D ）。A单射而非满射 B满射而非单射 C双射 D既不是单射，也不是满射6、下列二元运算在所给的集合上不封闭的是（ D ）A. S=2x-1|xZ+，S关于普通的乘法运算B. S=0，1，S关于普通的乘法运算C. 整数集合Z和普通的减法运算D. S=x | x=2n，nZ+，S关于普通的加法运算7、*运算如下表所示，哪个能使（a,b，*）成为含幺元半群（ D ） A B C D8、下列图中是欧拉图的是（ A ）。 A B C D9、下列各组数中,能构成无向图的度数列是（ D ）A1,1,1,2,4 B1,2,3,4,5C0,1,0,2,4 D1,2,3,3,510、一棵树有2个4度顶点，3个3度顶点，其余都是树叶，则该树中树叶的个数是（ B ）A .8 B.9 C. 10 D. 1111、“所有的人都是要死的。苏格拉底是人，所以苏格拉底是要死的。”则该句话（ B ）A不是命题 B是真命题 C是假命题 D是悖论12、一个公式在等价意义下，下面哪个写法是唯一的（ C ）。A析取范式 B合取范式 C主析取范式 D以上答案都不对13、设论域E=a, b，且P(a,a)=1 P(a,b)=0 P(b,a)=1 P(b,b)=0 则在下列公式中真值为1的是（ D ） A.$xyP(x,y) B.xyP(x,y) C.xP(x,x) D. x$yP(x,y) 14、设集合A=1, 2, 3 ，A上的关系R=, ，则R不具有（ A ）性质。 A.自反性 B.对称性 C.传递性 D. 反对称性15、设集合A=a,b,c,d,B=1,2,3,4,则从A到B的函数f=,是（ D ）。 A. 双射函数 B. 单射函数 C. 满射函数 D. 即不是满射又是不是单射函数16、下面给出的一阶逻辑等值式中，（ B ）是错的。A. B.C.D.17、下列各代数系统中，不含零元素的是 （ C ）A， 是全体n阶实矩阵集合，是矩阵乘法运算。B，是集合S的幂集合，是集合的并运算。C，是有理数集，是数的加法运算。D，是整数集，是数的乘法运算。18、 设图G是有6个顶点的连通图，总度数为20，则从G中删去（ B ）边后使之变成树。A .10 B. 5 C. 3 D. 219、在具有n个结点的无向连通图中，（B ）。A. 恰好有n条边 B. 恰好有n-1条边C. 最多有n条边 D. 至少有n条边20、下列图是欧拉图的是（ C ）21. 半群、群及独异点的关系是（ D ）（A）群独异点半群 （B）独异点半群群 （C）独异点群半群 （D）半群独异点群22. 设集合A=1, 2, 3 ，A上的关系R=,，则R不具有下列性质中的 （D）(A) 自反性 (B) 对称性 (C) 传递性 (D) 反自反性 23. 以下图中哪个是欧拉图 （D）24*运算如下表所示，哪个能使成为含幺元半群（D） (A) (B) (C) (D)25. 设P：张三可以做这件事，Q：李四可以做这件事。命题“张三或李四可以做这件事”符号化为（A） (A) (B) (C) (D) 26. 27. G是连通的平面图，有5个顶点，6个面，则G的边数为（C ） (A) 6 (B) 5 (C) 9 (D) 11 28. 下列句子中是命题的有 （D）(A) 上课时请不要说话! (B) 我在说谎.（C）你吃饭了吗？（D）上海是中国的首都.29. 以下命题公式中，为永假式的是( C )(A) p(pqr) (B) (pp)p（C）(qq)p （D）(qp)(pp)30. 图 的生成子图为（ C ）(A) (B) (C) (D) 31.如下图所示的有界格中，元素b的补元是( D )（A）a（B）0（C）c（D）d32. 设A=a,b,c，则下列是集合A的划分的是( D )（A） b,c,c （B）a,b,a,c （C）a,b,c （D）a,b,c33. 整数集合Z上“”关系的自反闭包是关系 （ D ）(A) = (B) (C) (D) 34. 下列式子正确的是 ( B )(A) (B) (C) (D)35. 设i是虚数，是复数乘法运算，则G=是群，下列是G的子群是( A )（A） （B）-1, （C）i, （D）-i,36.集合A=1，2的幂集P(A)的基数是（ D ） （A） 0 （B） 1 （C） 2 （D） 437. 下列哪个联结词运算不可交换？（A） (A) (B) (C) (D) 38. 设集合A=1，2，3，10,下列定义的哪种运算关于集合A是不封闭的 (D ) (A) x*y=maxx,y (B) x*y=(x,y) 即x,y的最大公约数 (C) x*y=minx,y (D) x*y=x,y 即x,y的最小公倍数 39.设R为实数集，函数f：RR，f(x)=2x，则f是（ B ）A满射函数B单射函数 C双射函数 D非单射非满射40. 若是一个代数系统,且满足结合律,则必为（A ）(A) 半群 (B) 独异点 (C) 群 (D) 交换群 41. 设R是A上的等价关系,即R是（D）（A）反自反的,对称的，传递的 （B）自反的,反对称的, 传递的 （C）反自反的,反对称的,传递的 （D） 自反的,对称的,传递的42下列哪一组命题公式是等价的（B ） (A) ， (B) ， (C) ， (D) ，43.设S=0,1,则S（A ）（A）在普通乘法下封闭，在普通加法下不封闭; （B）在普通加法和乘法下都封闭；（C）在普通加法下封闭，在普通乘法下不封闭； （D）在普通加法和乘法下都不封闭；44. 下面谓词公式是前束范式的是 （ A ）A. B. C. D. 45. 整数集合Z上“”关系的自反闭包是关系（D）(A)= (B) (C) (D)(A)(D)(C)(B)11.下列图既是欧拉图,又是哈密顿图的是（C ）46. 设A=a,b,c，A上二元关系R=a,a，b,b,a,c，则关系R的对称闭包S(R)是( C )(A) RIA (B) R (C) Rc,a (D) RIA47. 下列式子正确的是( B )(A) (B) (C) (D) 48. 下列句子是命题的是( C )(A) 水开了吗? (B) 这朵花多好看呀！ (C) 2是常数。 (D)我正在说谎49. 函数可逆的充要条件是 （ D ）(A) A=B (B)A与B有相同的基数 (C)f 为满射 (D)f为双射二、填空题1、 公式(PQ)(RS)真值表中共有 16 种真值指派。2、 设A(x):x是运动员,B(x):x是强壮的.命题“没有一个运动员不是强壮的”可符号化为 。3、 是公式的前束范式。4、设集合A=1,2,3上两个二元关系为R1=1,3，2,1，3,2 和R2=1,2，2,3，3,1，则R1 R2= , 。5、集合Zm=0,1,2，m-1，在Zm上定义运算+m为：对任意的i，jZm有：i+mj=（i+j）（modm），则的幺元是 0 ，iZm的逆元是 m-i 。6、无向图G如图1所示，则G的点连通度为 1 。 图1 图27、有向图D如图2所示，则有向图D的邻接矩阵A= ， D中长度为2的回路有 2 条。8、设p：1+1=5，q：明天是阴天。则命题“只要1+1=5，那么明天是阴天”可符号化为_ _，其真值为_ 1 _。9、设是兔子，是乌龟，比跑得快，则“并不是所有的兔子都比乌龟跑得快。”可符号化为 10、 设有向图D的邻接矩阵A(D)=,则长度为2的通路有 10 条. 11、设，则的生成元是 1 或 3 。12、具有16个结点的完全无向图其边数一定为 120 条。13、设集合，R为A上的整除关系，集合A中的极大元是 24 ；极小元2，3；14、整数加群的幺元是_ 0_。15若A=1,2,3 ,则*的运算表为 16.设A=a,a, A的幂集P(A)是 。17.设G是n阶无向完全图,则该图的边数为 。18.在一棵根树中，仅有一个结点的入度为 0_，称为树根，其余结点的入度均为 1 。19.设A、B是两个集合，其中A= a,b,c，B= 1，2，则AB= .20. 设个体域A=a,b,公式在A中消去量词后应是 21. 设M(x):x是人，D(x):x是要死的，则命题“所有的人都是要死的”可符号化为_ _,其中量词的辖域是_ _22. 画出完全图 23. 设A=a,b,c,则AA中的元素有 9 个。24. 设集合A=1,2,3 ,4,R为A上的一个二元关系，R=, ,则R的关系矩阵为 . 25. 设G是m阶有向完全图,则该图的边数为 m(m-1) 26. 设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则命题“小李非常聪明和能干”的为谓词表达式为_。27. 设A，B是两个集合，A=1, 2, 3, 4，B=2, 3, 5，则AB=1.4.5.28. 公式A(x)B(x)的前束范式为_。29. 一个简单连通无向图有n个节点，它的边数至少有 n-1 条。30. 画出完全图 三、计算题1、求公式的主析取范式和主合取范式。解：方法一（等值演算法） 方法二（真值表法）公式真值表如下：pqr00010100011111010101001111111000111101010011010101111111根据真值表可以得到主析取范式为：2、列出命题公式（的真值表。解：pq001010110110011111113、设集合A=，为A上的二元关系，R=1,23,1,2,3 ，求R2，的集合表达式。解：因为R=,所以R2=,r(R)=,s(R)=,t(R)=EA4、在偏序集中，其中A=1,2,3,4,6,8,12,14，是A中的整除关系，求集合D=2,3,4,6的极大元，极小元，最大元，最小元，上界，下界,最小上界和最大下界。解：极大元：4，6；极小元：2，3；最大元：无；最小元：无；上界：12；下界1：最小上界：12;最大下界:15、求带权为1, 3, 6, 7,8,11的最优二叉树,编一个最佳2元前缀码，并求其权数. 解：最优二叉树如下图所示：编码： 1：0000 ；3：0001 ；6：001； 7：10； 8：11； 11：01 最小生成树的权数为其权W(T)=(1+3)*4+6*3+(11+7+8)*12=86 13641011217836157 6、用Kruskal算法求下列权图的最小生成树,并求最小生成树的权数,要求写出解的过程. 3724C97E5214ADEB解: 取数的由小到大的排列为123457932142BDEFAC最小生成树如图所示： 最小生成树的权数为其权W(T)=127、设A=a,b,c,d,R=,。试用关系图表示R及R的传递闭包。8、设G=a是10阶循环群，求出G的所有子群。解：因为10的正因子是1,2,5，10 所以 G的子群有4个， 分别是=e=e, a5 =e, a2, a4, a6，a8 =G9、（1）在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？（2）画出两棵非同构的满足（1）中顶点度数的无向树T1和T2。解：（1）设树有n个顶点，则有n-6片树叶根据握手定理可知于是n=12因此有6片树叶。(2)两棵非同构的树为T1 T210、A、B、C、D四个人中要派两个人出差，需满足如下条件：（1）若A去，则C和D中要去一人；（2）B和C不能都去；（3）C去则D要留下。问有几种派法？如何派？解：用A、B、C、D分别表示A去，B去，C去，D去出差，则命题符号化如下：（1）A（CD）（表示异或，可用其它符号）（2）（BC）（BC）（3）CD出差的派法要同时满足上述三个条件，故G= （A（CD）（BC）（BC）（CD）列该公式的真值表如下：（可以去掉所有不满足条件的，只剩6种情况如下：）ABCD（1）（2）（3）G001111000101111101101010100101101010111111000110由真值表知有两种派法A，C去或B，D去。11、设A=1,2,3,6,12,对于整除关系构成偏序集R(1)作出偏序关系R的哈斯图(2)令B=2,3,6，求B的最大，最小元，极大、极小元，上界，最小上界，下界，最大下界。12、一棵树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子数。解：设树的叶子数为x,于是T中有x+2+3个顶点,有(x+2+3)-1条边，由握手定理知T中所有顶点的度数之和 =2(x+2+3)-1 2*4+3*3+x*1=2*(2+3+x)-1 X=9 13、求带权为2, 3, 5, 7,8,9的最优二叉树,并编一个最佳2元前缀码. 解：最优二叉树如下图所示： 编码： 2：0000； 3：0001 5：001 7：10 8：11 9：01 235510919783415714、带权无向图G如下，求G的最小生成树T及T的权总和，要求写出解的过程。abcfedg200230360150381628917741解：取数的由小到大的排列为1348915161720232836abcfedg23038941最小生成树如图所示： 最小生成树的权数为其权W(T)=48 15、 求(PQ) (PQ)的主合取范式并给出所有使命题为真的赋值。解：原式(PQ)(PQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ)(PQPQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ) P(QQ) P(QQ) (PQ)(PQ) 命题为真的赋值是P=1,Q=0和P=1,Q=116、某班有学生60人，其中有38人选修Visual C+课程，有l6人选修Visual Basic课程。有21人选修Java课程；有3人这三门课程都选修，有2人这三门课程都不选修，问仅选修两门课程的学生人数是多少？解 设选修Visual C+课程的学生为集合A；选修Visual Basic课程的学生为集合B；选修Java课程的学生为集合C。 由题意可知： |A|38 |B|16 |C|21 |ABC|3 60-|ABC|2因为|ABC|A|+|B|+|C|-|AB|-|AC|-|BC|+|ABC|所以有：|AB|+|AC|+|BC|=20。 所以仅选修两门课程的学生数是|AB|+|AC|+|BC|-3|ABC|=11。 17、设A,R为一个偏序集，其中A=1，2，3，4，6，9，24，54 ，R是A上的整除关系。（1）画出A,R的哈斯图；（2）求R关于A的极大元；（3）求B=4,6,9的最小上界和最大下界。18、设G=a是12阶循环群，求出G的所有子群。解：因为12的正因子是1,2,5，10 所以 G的子群有4个， 分别是=e=e, a5 =e, a2, a4, a6，a8 =G四、证明题1、设R1，R2为A上的关系，证明：。证明：对任意的，有 故2、设R1，R2为A上的关系，证明：。证明：对任意的，有 故3、在自然推理系统P中，构造下面推理的证明：只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他，所以A犯了谋杀罪。证明： 命题符号化：p：A曾到过受害者房间q：A11点以前离开r ：A犯了谋杀罪s：看门人会看见他 前提：（pq）r，p，qs，s 结论：r 证明： s qs q p （pq） （pq）r r 4、设C*=a+bi | a,b为实数，且a0。其中i 是虚数单位。在C*上定义：R=| a+biC*c+diC*ac0（1）证明：R是C*上的等价关系；（2）给出R产生的等价类。证明：（1）对任意的a+biC*，a0aa0（a+bi）R（a+bi） 所以R是自反的。（2）对任意的a+bi，c+diC*，（a+bi）R（c+di）ac0 ca0 （c+di）R（a+bi） 所以R是对称的。（3）对任意的a+bi，c+di， e+fiC*，（a+bi）R（c+di），（c+di）R（e+fi） ac0，ce0ae0（a+bi）R（e+fi）所以R是传递的。综上R是一个等价关系。R有两个不同的等价类。设为K1，K2K1=（a+bi）a0，K2=（a+bi）a05、证明：6阶群中必含3阶元。证明：设G是6阶群，由L定理的推论1知G中元素的阶只可能是1，2，3，6。 若G中含有6阶元，设该元素为a，则a2为3阶元。若G中不含有6阶元，下面证明G中必含有3阶元。若不然G中只含有1阶和2阶元，即对任意aG，有a2=e，则G是Abel群，取G中两个不同的2 阶元a,b，令H=e,a,b,ab，则H是G的子群，但|H|=4，|G|=6，4不整除6，矛盾。故G中必含有3阶元。6、构造下面推理的证明:前提: 结论: 证明: (1) 前提引入(2) (1)置换 (3) (2)置换(4) (3)UI(5) 前提引入(6) (5)UI(7) (6)(4)假言三段论 (8) (7)UG 7、构造下列推理的证明.前提:结论:证明： (1) 前提引入 (2) 前提引入 (3) (1)(2)拒取式 (4) 前提引入 (5) (3)(4)假言推理 (6) 前提引入(7) (5)(6)拒取式 (8) 前提引入(9) (7)(8)析取三段论 8、设Z为整数集合,在Z上定义二元运算*, 有证明: (Z, *)是群. 证明: (1) 封闭性： (2) 可结合性：(3)幺元为1 ：(4)x的逆元为 9、试证：任一棵非平凡树G至少有两