四川大学离散数学往年考试试题二.doc

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