2012《离散数学》A卷

共8页第1页2012级离散数学课程试题（A卷）合分人：复查人：一、选择题：（每题1分，共15分）分数评卷人1．设谓词是实数，,则语句“没有最小的实数”可符号化为()。A.B.C.D.2.下列语句是真命题的是（）。A.雪是黑色的，当且仅当50B.自然数中存在最大素数C.今天天气真好呀D.只有50，雪才是白色的3．设，则下列陈述正确的是（）。A.B.C.D.4.设，则（）。A.B.C.D.5.设，则其幂集的元素总个数为（）。A.2B.3C.4D.86.设，A上的等价关系，则对应于R的A的划分是（）。A．}}{},,{},{{dcbaB．}}{},{},,{{dcbaC．}}{},{},{},{{dcbaD．}},{},,{{dcba题号一二三四五六七总分分数共8页第2页7．是一个偏序集，其中A是正整数12的正因子的集合，为整除关系，则能盖住元素3的元素是（）。A.1B.3C.6D.128．在整数集Z上，下列定义的运算满足结合律的是（）。A.B.C.D.9.设是群，则下列陈述不正确的是（）。A.nnnabab（）B.-11nnabaaba（）C.nmnmaa（）D.nmnmaaa10.设}0{X，下列关于代数系统),(XP的陈述正确的是（）。A.0是幺元B.是幺元C.｛0｝是幺元D.没有幺元11.设Z是整数集，+，分别是普通加法和乘法，则（Z，+，）是（）。A．域B．整环和域C．整环D．含零因子环12．设简单图G所有顶点的度数之和为36，则G的边数为（）。A.12B.18C.36D.7213.下列无向图不一定是树的是（）。A.有n个结点，n-1条边的图B.无回路的连通图C.连通但删去一条边则不连通的图D.无回路但添加一条边则有一个回路的连通图14．下列必为欧拉图的是（）A.有回路的连通图B.不可以一笔画的图C.有1个奇数度顶点的连通图D.无奇数度顶点的连通图15．在简单无向图EVG,中，如果V中的每个顶点都与其余的所有顶点邻接，则该图称为（）。A.正则图B.完全图C.连通图D.强连通图共8页第3页二、填空题：（每空2分，共28分）分数评卷人1．公式)())()((rprqqp的主析取范式中的极小项有_________________，其成真赋值为_______________________________,成假赋值为________________________。2．公式的约束变元为_____________,自由变元为________________。3．设R=｛＜1，2＞，＜2，3＞，＜4，5＞｝和S=｛＜3，2＞，＜4，3＞，＜5，1＞｝是集合A=｛1，2，3，4，5｝上的两个关系，则RS_____________,SR=________________。4．若集合A中有三个元素，则A上的关系有___________个，其中__________个是等价关系，___________个是偏序关系。5．设Q为有理数集，笛卡尔集S=Q×Q，*是S上的二元运算，Syxba,,,,byaxyxba,,*,,则*运算的幺元是________________。Sba,,若a≠0，则ba,的逆元是________________。6．一个连通平面图共有7个顶点，3个面，则G的边数为_______________。7.设简单无向图G有15条边，有3个4度顶点，4个3度顶点，其余顶点的度数均为2，则G中的顶点个数为________________。三、计算题：（每题分数见题后，共27分）分数评卷人1．（4分）设解释I如下：共8页第4页D={2，3}，a=3，F(2,2)=F(3,3)=0，F(2,3)=F(3,2)=1，f(2,2)=f(2,3)=2，f(3,2)=f(3,3)=3。求谓词公式在I下的真值。2.（7分）设=1,4,2,1,2,3,3,1,4,2,4,3R｛｝是=A｛1,2,3,4｝上的二元关系，（1）画出R的关系图；（2）写出R的关系矩阵；（3）说明在A上R是否具有自反、反自反、对称、反对称性质。共8页第5页2.（8分）在域中解方程组，其中+为模5加法，*为模5乘法。4．（8分）某城市拟在六个城区之间架设有线电视网，其网点间的距离如下列的无向有权图矩阵给出，给出架设线路的最优方案，请画出图，并计算出最优方案下的线路的长度。共8页第6页四、证明题：（每题分数见题后，共30分）分数评卷人1.（10分）分别是集合S、T上的关系，定义上的关系当且仅当。证明：若为等价关系，则为等价关系。共8页第7页2.（12分）是群，其中为模n加法。定义代数系统（）：对任意，。证明：若m、n互质，（）是循环群，生成元是1,1。共8页第8页3.（8分）有下列命题：(1)参加展览的人中，每个N大学的男生都背K牌书包。(2)参观展览的人中，每个背K牌书包的都是来自N大学的男生。(3)每个背K牌书包的N大学男生都参观了该展览。写出相关的逻辑表达式，并证明（1）（2）不能推出（3），方法任选。