2019年电大《离散数学》期末综合复习资料必考重点.doc

PAGE 5 电大《离散数学》期末综合复习资料小抄 一、判断题 （ ）命题联结词{?，?，?}是最小联结词组。 （ ）（P?Q）??P为矛盾式。 （ ）（（?P?Q）?（Q?R））?（P?R）为重言式。 （ ）A、B、C是任意命题公式，如果A?C?B?C，一定有A?B。 （ ）若集合A上的二元关系R是对称的，RC一定是对称的。 （ ）R是A上的二元关系，R是自反的，当且仅当r(R)=R。 （ ）集合A上的等价关系确定了A的一个划分。 （ ）有理数集是可数的。 （ ）若函数f，g为入射则其复合函数也为入射。 （ ）R是集合A上的关系，R有传递性的充要条件是RoR?R。 （ ）设A，*是一个代数系统，且集合A中元素的个数大于1。如果该代数系统中存在幺元e和零元?，则e??。 （ ）交换群必是循环群。 （ ）一个群可以有多个等幂元。 （ ）模格一定是分配格。 （ ）每个有向图中，结点入度数总和等于结点出度总和。 （ ）图G的邻接矩阵A，Al中的i行j列表示结点vi到vj长度为l路的数目。 （ ）任何图中必有偶数个度数为奇数的结点。 （ ）有向图中，它的每一个结点位于且只位于一个单侧分图中。 （ ）任意平面图最多是四色的。 （ ）不存在既有欧拉回路又有汉密尔顿回路的图。 二、填空题 设P：“天下雨”，Q：“他骑自行车上班”，R：“他乘公共汽车上班”。则命题“除非下雨，否则他就骑自行车上班”可符号化为 。“他或者骑自行车，或者乘公共汽车上班”可符号化为 设N(x)：x是自然数；J(x)：x是奇数；Q(x)：x是偶数，用谓词公式符号化命题“任何自然数不是偶数就是奇数”。 设P(x)：x是运动员，Q(x)：x是教练。则命题“不是所有运动员都是教练”可符号化为 。 设D={a,b}；P(a,a)=P(b,b)=T；P(a,b)=P(b,a)=F。则公式(?x)(?y)(P(x,y)?P(y,x))的真值是 。 集合A={?,{?}}的幂集P(A)为 集合A={1,2}，B={a,b,c,d}，C={c,d,e}，则A?(B-C)为 试用空集?构成集合A（A??）= 和B= ，使得A?B且A?B都成立。并且A?B= 。 设A={1,2,3}，R={1,2,2,1,1,3,1,1}，传递闭包t(R)为 。 设A={1,2,3}，B={x,y}，f：A?B，则不同的函数个数为 个。 Q为有理数集，Q上定义运算*为a*b=a+b-ab，则Q,*的幺元为 。 代数系统Sk,+，其中Sk={x|x?Z?x=K}，+为普通加法，则Sk,+是一个半群的必要条件是 。 设G为v个结点e条边的连通平面图，则面r等于 。 一棵树有n2个结点度数为2，n3个结点度数为3，……，nk个结点度数为k，则度数为1的结点的个数为 。 设T为根树，若每个结点的出度都小于等于m，则T称为 树，若除 外，每个结点的出度都等于m，则T称为完全m叉树。 设A，?是偏序集，如果A中任意两个元素都有 和 ，则称A，?为格。 三、解答题 将公式((P?Q) ? (Q?R))?(P?R)化成与之等价且仅含{?、?、?}的公式。 将下列命题符号化：（1）他虽聪明但不用功。（2）除非你努力否则你将失败。（3）我们不能既划船又跑步（4）仅当你走我才留下。 用谓词表达式符号化下列命题：（1）所有老的国家选手都是运动员。（2）某些教练是年老的，但是健壮的。（3）任何自然数不是偶数就是奇数。（4）不是所有运动员都是教练。 求命题公式?(P?Q)的主合取范式。 求命题公式P?(P?Q)的主析取范式。 设集合A＝{1, 2, 3}，A上的关系R＝{1, 1,1, 2,2, 2,3, 2,3, 3}, （1）画出R的关系图；（2）写出R的关系矩阵；（2）问R具有关系的哪几种性质(自反、反自反、对称、反对称、传递)。 构造一非空偏序集，它存在一子集有上界，但没有最小上界。它还有一子集，存在最大下界但没有最小元。 以下哪些是函数？哪些是入射？哪些是满射？对任意一个双射，写出它们的逆函数。 f: Z?N, f(x)=x2+1 f: N?Q, f(x) = 1/x f: {1,2,3}?{a,b,c}, f={1,b,2,c,3,a} f: N?N, f(x)=2x f: R?R?R?R, f(x,y)=y+1,x+1 设S={1,2,3,4,6,12}，D为S上的整除关系，（1）试写出该关系并画出哈斯图；（2）设子集B={2,3,6}，试求B的最大元、最小元、极大