离散数学 期末复习题.doc

四川大学锦城学院考试试题 ( 2010 2011学年 第 二 学期)课程号：020255 课序号： 课程名称：离散数学 任课教师： 成绩：适用专业年级：07 计算机科学和软件 学生人数： 印题份数： 学号： 姓名：考 试 须 知四川大学锦城学院学生参加由学校组织或由学校承办的各级各类考试，必须严格执行四川大学锦城学院考试工作管理办法和四川大学锦城学院考场规则。有考试违纪作弊行为的，一律按照四川大学锦城学院学生考试违纪作弊处罚条例进行处理。四川大学锦城学院各级各类考试的监考人员，必须严格执行四川大学锦城学院考试工作管理办法、四川大学锦城学院考场规则和四川大学锦城学院监考人员职责。有违反学校有关规定的，严格按照四川大学锦城学院教学事故认定及处理办法进行处理。一、单项选择题1. 下列句子是命题的是( )。A.上课了吗? B.11+1=100。 C.再过10年，我们就能够上火星了！ D.本语句是假的。2. 设A=1，2，B=a,b，下列二元关系R不是A到B的函数的是( )；A.R=, B.R=,C.R=, D.R=,3. 在自然数集合N上，下列定义的运算中是可结合的只有( )；A.a*b=a-b B.a*b=max(a,b)C.a*b=a+2b D.a*b=|a-b|4. 设是环，则下列正确的是（ ）；A是半群 B是可换群C对+是可分配的D+对是可分配的5 . 设群（G , * ）的阶为15，则其真子群的最高阶是( )；A.1 B.3C.5 D.156无向图G=（n, m）是完全图，则（ ）；A. n=m B. m=n(n-1)C. m=n(n-1)/2 D. m=n(n+1)/27. 图G= 是一个（n, m）图，则所有节点的次数之和等于( )；A.2m B. 2nC.m+n D. m-n8. 在公式中变元z是（ ）；A自由变元 B约束变元C既是自由变元，又是约束变元 D既不是自由变元，又不是约束变元9. 非空集合A上的二元关系R若是自反、对称的和传递的，则R是( )；A.偏序关系B.等价关系C.相容关系D.拟序关系本题 2 页，本页为第 1 页 教务部试题编号： 四川大学锦城学院考试试题 10.设全总个体域为整数集，下列谓词公式中真值为假的是( )。A. B. C. D. 二、填空题1. 集合X=a，b，c上二元关系R=，则R的自反闭包r(R)= _；2. 设集合A=a, b, c, 则A的幂集为：_；3设代数系统是环，则代数系统满足_；4. 设群（Z , * ）（Z是整数集）是一个循环群，其生成元是_和_；5. 整数环中加法的零元是_，乘法的单位元是_；6. 在一棵内向树中，有且只有一个结点的引出次数为_；7. 把下述命题符号化：“张三身体好，工作也好。” ； 8. 设个体域是0,1,2，则xS(x)等于命题公式 _。三、计算题1设X=a，b，c，d，R是X上的二元关系，R=,。（1）画出R的关系图；（2）写出R的关系矩阵。2设A1，2，3，4，6，12，R为A上整除关系，试画的哈斯图，并求A中的最大元，最小元，极大元，极小元。3求有向图G的邻接矩阵，其中Vv1,v2,v3，E(v1,v2), (v2,v3), (v3,v2), (v3,v1)。4. 构造命题公式(PQ)(PQ)的真值表，并写出其主析取范式。5. 求公式 xP(x) yQ(y) 的前束范式。四、应用题 判断下面推理是否正确，并证明你的结论。我夫人过生日，我送一束鲜花给她，除非我工作忙。今天我没有送鲜花给夫人，今天是夫人的生日，由此是否可以推得“今天我工作忙”。 本题 2 页，本页为第 2 页 教务部试题编号： 一、单项选择题1. 下列句子是命题的是( )。A. 下雪了吗? B. 1+1=10。 C. 天气真好！ D. 我正在说谎。2. 设A=1，2，B=a,b，下列二元关系R是A到B的函数的是( )；A. R=, B. R=,C. R=, D. R=,3. 是整数加群，其单位元是 ( )；A. 0 B. 1C. -1 D. 任意元4. 设是域，则下列正确的是（ ）；A是可换群 B是可换单元半群C对+是可分配的 D每个元均有逆元5 . 设有限群（G , * ）的阶为7，下列叙述不正确的是( )；A. 有1阶子群B. 有7阶子群C. 无真子群 D. 有真子群6有向图G=（n, m）是完全图，则（ ）；A. n=m B. m=n(n-1)C. m=n(n-1)/2 D. m=n(n+1)/27. 图G= 是一个（n, m）连通图，若要确定它的生成树，需删去的边的数目是( )；A. n-m B. m-n+1C .m-n-1 D. m-n8. 在公式中变元z是（ ）；A自由变元 B约束变元C既是自由变元，又是约束变元 D既不是自由变元，又不是约束变元9. 非空集合A上的二元关系R若是反自反、传递的，则R是( )；A.偏序关系 B.等价关系C.相容关系 D.拟序关系10.下列等式正确的是( )。A. B. C. D. 二、填空题1. 集合X=1，2，3上二元关系R=，则R的对称闭包s(R)= _；2. 设集合A=, 则A的幂集为：_；3设代数系统是环，则代数系统满足_；（什么定律）4. 模m的剩余类加群是一个循环群，其生成元是_；5. 把下述命题符号化：“说数理逻辑枯燥无味或毫无价值，那是不对的。” ； 三、计算题1设X=a，b，c，d，e，R是X上的二元关系，R=, , , , , ,。（1）画出R的关系图；（2）写出R的关系矩阵。2设A1，2，3，6，12, 18，R为A上整除关系，试画的哈斯图，并求B=2, 3, 6, 12中的最大元，最小元，极大元，极小元。3. 构造命题公式(PQ)(PQ)的真值表，（1）求出成真赋值，成假赋值；（2）判断公式的类型；（3）写出其主合取范式。4