1、注：试题字迹务必清晰，书写工整。 本题 6 页，本页为第 1 页教务处试题编号：一、单项选择题（本大题共 15 小题，每题 1 分，共 15 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分1 2 3 4 5 6 7 8 9 10 11 12 13 14 151设 12xxA是 整 数 且，下面哪个命题为假（ ） 。A、 4,20； B、 A1,23；C、 ； D、 xx4是 整 数 且 。2设 ,，则 BA 是（ ） 。A、 ； B、 ； C、 ,； D、 。3右图描述的偏序集中，子集 feb的上界为 （ ） 。A、 cb,； B、
2、 a,； C、 ； D、 c。4设 f和 g都是 X 上的双射函数，则 1)(gf为（ ） 。A、 1； B、 1)(f； C、 f； D、 1fg。5下面集合（ ）关于减法运算是封闭的。A、N ； B、 2Ix； C、 2Ix； D、 是 质 数x。6具有如下定义的代数系统 ,G， （ ）不构成群。A、 10,G，*是模 11 乘 ； B、 9,543,1，*是模 11 乘 ；C、 Q（有理数集） ，*是普通加法 ； D、 Q（有理数集） ，*是普通乘法。7设 ,32Inm，*为普通乘法。则代数系统 ,G的幺元为（ ） 。A、不存在 ； B、 02e； C、 32e； D、 132e。8下面
3、集合（ ）关于整除关系构成格。A、2 ，3，6，12，24，36 ； B、1，2，3，4，6，8，12 ；C、1，2，3，5，6，15，30 ； D、3，6，9，12。9设 ,fedcbaV， , efdaE，则有向图G,是（ ） 。A、强连通的 ； B、单向连通的 ； C、弱连通的 ； D、不连通的。评阅教师 得分课程名称： 任课教师： 学号： 姓名： 本题 7 页，本页为第 2 页10下面那一个图是欧拉图（ ） 。11在任何图中必定有偶数个（ ） 。A、度数为偶数的结点 ； B、入度为奇数的结点 ；C、度数为奇数的结点 ； D、出度为奇数的结点 。12含有 3 个命题变元的具有不同真值的命
4、题公式的个数为（ ） 。A、 2； B、 2； C、 32； D、 23。13下列集合中哪个是最小联结词集（ ） 。A、 ,； B、 ,； C、 ,； D、 ,。14下面哪个命题公式是重言式（ ） 。A、 )()(RQP； B、 PQ)(；C、 ； D、 。15在谓词演算中，下列各式哪个是正确的（ ） 。A、 ),(),(yxAyx； B、 ),(),(yxAyxA；C、 ； D、 a。二、多项选择题（本大题共 5 小题，每题 2 分，共 10 分 ）在每小题列出的五个备选项中有二个至五个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选、少选或未选均无分。1 2 3 4 51、设 A
5、1,2,3，则右图所示 A 上的关系具有（ ） 。1).自反性 2).反自反性 3).对称性4).反对称性 5).传递性2、下列语句是命题的有（ ） 。1). 明年中秋节的晚上是晴天； 2). 0yx；3). 0xy当且仅当 x 和 y 都大于 0； 4).我正在说谎。3、A，B 为二合式公式，且 BA，则（ ） 。312评阅教师 得分课程名称： 任课教师： 学号： 姓名： 本题 7 页，本页为第 3 页1). BA为重言式； 2). *BA；3). ； 4). ； 5). BA为重言式。4、右图所示的图一定不是（ ） 。1).平面图 2).二部图 3).欧拉图4).哈密而顿图 5).树5、设
6、 R 和 S 是集合 A 上的任意关系，下列命题不成立（ ） 。1).若 R 和 S 是自反的，则 R0S 也是自反的。2).若 R 和 S 是反自反的，则 R0S 也是反自反的。3).若 R 和 S 是对称的，则 R0S 也是对称的。4).若 R 和 S 是传递的，则 R0S 也是传递的。三、填空题（本大题共 5 小题，每题 2 分，共 10 分）1 2 3 4 51、P：你努力，Q：你失败。 “除非你努力，否则你将失败”的翻译为；“虽然你努力了，但还是失败了”的翻译为。2、设 A=2，3，4，5，6上的二元关系 |,是 质 数xyxR，则R= （枚举法） 。R 的关系矩阵 MR=。3、设
7、A=1，2，3，则 A 上既不是对称的又不是反对称的关系 R= ；A 上既是对称的又是反对称的关系 R= 。评阅教师 得分课程名称： 任课教师： 学号： 姓名： 本题 7 页，本页为第 4 页4、设代数系统 ，其中 A=a，b，c,则幺元是 ；是否有幂等性 。5、n 个结点的无向完全图 Kn 的边数为 ，欧拉图的充要条件是。四、演算题（本大题共 4 小题，每题 10 分，共 40 分 ）1 2 3 41、设 )()()(),( 31321321 xxxE是布尔代数 ,1,0上的一个布尔表达式，试写出其主析取范式和主合取范式。* a b cabca b cb b cc c b评阅教师 得分课程名
8、称： 任课教师： 学号： 姓名： 本题 7 页，本页为第 5 页2、如下图所示的赋权图表示某七个城市 721,v 及预先算出它们之间的一些直接通信线路造价（单位：万元） ，试给出一个设计方案，使得各城市之间既能够通信又使总造价最小。3、已知有如图的偏序关系，求出其子集 A=b,c,d,e的极大元、极小元、最大元、最小元、最小上界和最大下界。4、设 ,cbaA，A 上的关系 , bcba ，求出)(,)(tsr和 。fgecdba课程名称： 任课教师： 学号： 姓名： 本题 7 页，本页为第 6 页五、证明题（本大题共 2 小题，共 25 分 ）1 21、 （12 分）证明：(P(QS)( RP)QRS评阅教师 得分课程名称： 任课教师： 学号： 姓名： 本题 7 页，本页为第 7 页2、(13 分) 如果集合 A 上的关系 R 和 S 是反自反的、对称的和传递的，证明： SR是 A 上的等价关系。
