资源描述：
《电大《离散数学》本科期末复习题资料考试小抄》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、电大离散数学（本）期末复习资料小抄一、单项选择题1．设P：a是偶数，Q：b是偶数。R：a+b是偶数，则命题“若a是偶数，b是偶数，则a+b也是偶数”符号化为（D．PQ→R）。2．表达式x（P（x，y）Q（z））y（Q（x，y）→zQ（z））中x的辖域是（P（x，y）Q（z））。3．设则命题为假的是（）。4．设G是有n个结点的无向完全图，则G的边数（1/2n（n-1））。5．设G是连通平面图，有v个结点，e条边，r个面，则r=（e-v+2）。6．若集合A={1，{2}，{1，2}}，则下列表述正确的是({1}ÌA)．7．已知一棵无向树T中有8个顶点，4度
2、、3度、2度的分支点各一个，T的树叶数为(5)．8．设无向图G的邻接矩阵为则G的边数为(7)．9．设集合A={a}，则A的幂集为({Æ，{a}})．10．下列公式中(ØAÙØB«Ø(AÚB))为永真式．11．若G是一个汉密尔顿图，则G一定是(连通图)．12．集合A={1,2,3,4}上的关系R={
3、x=y且x,yA}，则R的性质为（传递的）．13．设集合A={1，2，3，4，5}，偏序关系£是A上的整除关系，则偏序集上的元素5是集合A的（极大元）．14．图G如图一所示，以下说法正确的是({(a,d),(b,d)}是边割集)．图一15
4、．设A（x）：x是人，B（x）：x是工人，则命题“有人是工人”可符号化为（(x)(A(x)∧B(x))）．16．若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是(AÌB，且AÎB)．17．设有向图（a）、（b）、（c）与（d）如图一所示，则下列结论成立的是(（d）是强连通的)．18．设图G的邻接矩阵为则G的边数为(5)．19．无向简单图G是棵树，当且仅当(G连通且边数比结点数少1)．20．下列公式((P®(ØQ®P))«(ØP®(P®Q)))为重言式．21．若集合A＝{a，{a}，{1，2}}，则下列表述正确的是({a}ÍA)．22
5、．设图G＝，vÎV，则下列结论成立的是()．23．命题公式（P∨Q）→R的析取范式是(（ØP∧ØQ）∨R)24．下列等价公式成立的为(P®(ØQ®P)ÛØP®(P®Q))．25．设A={a,b}，B={1,2}，R1，R2，R3是A到B的二元关系，且R1={,}，R2={,,}，R3={,}，则（R2）不是从A到B的函数．26．设A={1,2,3,4,5,6,7,8}，R是A上的整除关系，B={2,4,6}，则集合B的最大元、最小元、上界、下界依次为(无、2、无、2)．11
6、/1127．若集合A的元素个数为10，则其幂集的元素个数为（1024）．28．如图一所示，以下说法正确的是(e是割点)．图一29．设完全图K有n个结点(n≥2)，m条边，当（n为奇数）时，K中存在欧拉回路．30．已知图G的邻接矩阵为，则G有（5点，7边）．二、填空题（每小题3分，共15分）1．设A，B为任意命题公式，C为重言式，若ACBC，那么AB是重言式（重言式、矛盾式或可满足式）。2．命题公式（P→Q）P的主合取范式为。3．设集合A={，{a}}，则P（A）=。4．设图G=〈V，E〉，G′=〈V′，E′〉，若V′=V,E′E,则G′是G的生成子图。
7、5．在平面G=〈V，E〉中，则=2
8、E
9、，其中（i=1，2，…，r）是G的面。6．命题公式的真值是假（或F，或0） ．7．若无向树T有5个结点，则T的边数为4．8．设正则m叉树的树叶数为t，分支数为i，则(m-1)i=t-1．9．设集合A={1，2}上的关系R＝{<1,1>,<1,2>}，则在R中仅需加一个元素<2,1>，就可使新得到的关系为对称的．10．("x)(A(x)→B(x，z)∨C(y))中的自由变元有z，y．11．若集合A={1，3，5，7}，B={2，4，6，8}，则A∩B= 空集（或Æ）．12．设集合A={1，2，3}上的函数分别为：f
10、={<1,2>,<2,1>,<3,3>,}，g={<1,3>,<2,2>,<3,2>,}，则复合函数g°f={<1,2>,<2,3>,<3,2>,}．13．设G是一个图，结点集合为V，边集合为E，则G的结点度数之和为2
11、E
12、（或“边数的两倍”）．14．无向连通图G的结点数为v，边数为e，则G当v与e满足e=v-1关系时是树．15．设个体域D＝{1,2,3}，P(x)为“x小于2”，则谓词公式("x)P(x)的真值为假（或F，或0）．16．命题公式的真值是 T（或1） ．17．若图G=中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G
13、中删除S中的所有结点得到的连通分支数为W，则S中结点数
14、S
15、与W满足的关系式为W£
16、S
17、．18
