df离散重修试卷.docVIP

PAGE 1 《离散数学》试卷　　第  PAGE 6 页 共  NUMPAGES 6 页 装 订 线 班级： 姓名： 学号： 江苏技术师范东方学院2008—2009学年第2学期 《离散数学》重修试卷 注意事项： 1．本试卷适用于计算机及其相关专业学生使用。 2．本试卷共 6 页，满分100分，答题时间120分钟。 题号一二三四五总分得分 得分评卷人一、单项选择题（本大题共5道小题，每小题2分，共10分） 集合A上的等价关系的三个性质是（ ）。A.自反性、反对称性和传递性 B.反自反性、反对称性和传递性C. 自反性、对称性和传递性 D.反自反性、对称性和传递性 Q是有理数集合，代数系统Q，+的零元是（ ）。A. 0 B. 1C. –1 D. 不存在 在1（ ）{}之间写上正确的符号。A. = B. C. D. 若集合A的基数|A|=6，则A的幂集的基数|P(A)|=（ ）。A. 32 B.64C. 16 D.8 当且仅当为下面条件中的哪一个时，无向图G是欧拉图？（ ） G的所有结点的次数为偶数 B. G的所有结点的次数为奇数 C. G连通且所有结点的次数为偶数 D. G连通且所有结点的次数为奇数 得分评卷人二、填空题（本大题共10空，每空2分，共20分）设A＝{{1}，1},则P(A)= 。 令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为： 。 设G是n阶无向带权连通图，各边的权均为a(a0),设T是G的一棵最小生成树，则T的权w(T)= 。 集合A上的等价关系的三个性质是自反性、对称性和 。 一条通过图中所有结点一次且恰好一次的路是 路。 集合A={1,2,…,10}上的关系R={x,y|x+y=10,x,yA}，则R的性质为 。 谓词公式?x(P(x)? ?yQ(y))R(x)中量词?x的辖域是 。 群(Z5,+5)的所有子群为： 。 一个图G有36条边，若每个结点的度均为3，则G有 个结点。 m个结点的无向完全图的边数为 。 得分评卷人三、判断题（本大题共10小题，每小题1分，共10分）正确的打“√”，错误的打“×” （ ）代数系统 Z+,+（Z+是正整数集合，+是普通加法）是独异点。 （ ）命题逻辑中任何命题公式的析取范式都存在且唯一。 （ ）集合A上的恒等关系IA是A上的偏序关系。 （ ）每对顶点间都有通路的图不一定是树。 （ ）集合R上的关系满足自反性，则一定满足反自反性。 （ ）半群中不一定有单位元。 （ ）Mn(R),+是群,其中Mn(R)是n阶实矩阵，＋是普通加法 （ ）“美国是面积最大的国家吗？”是命题。 （ ）命题公式是重言式。 （ ）设A,B为无限集，则A-B是空集。 得分评卷人四、证明题（本大题共3小题，第1、2小题各8分，第3小题10分，共26分）设A、B、C是三个集合，证明：AB=A(B-A) 在命题逻辑中符号化下述命题，并构造推理的证明。 若明天是星期一或星期三，我就有课。 若有课，今天必须备课。我今天没备课。所以，明天不是星期一和星期三。 在一阶逻辑中符号化下述命题，并推证之。 凡人必有一死，苏格拉底是人，所以苏格拉底会死的。 得分评卷人五、计算、应用题（本大题共5小题，第1、2、3、4小题各6分，第5小题10分，共34分） 设有一颗树，它有两个结点次数为2，三个结点次数为3，四个结点次数为4，问它有几个结点次数为1？ 有十个人参加聚会，每个人都认识其中的6个，问能否安排坐在一个圆桌上，使每个人认识与坐在他两边的人是认识的？为什么？ 求以1,3,4,5,6权为的最优2元树, 要求写出步骤并计算它的权。 求Q(Q→R)的主析取范式及主合取范式。 有向图G如下图所示： （1）写出此图的邻接矩阵表示。（4分） （2）v1到v3长为3的通路有多少条？v1到自身长为3的回路有多少条？（6分）