离散数学期末试卷.pdf

学院姓名学号任课老师选课号„„„密„„„封„„„线„„„以„„„内„„„答„„„题„„„无„„„效„„电子科技大学二零零六至二零零七学年第二学期期末考试离散数学课程考试题B卷（120分钟）考试形式：闭卷考试日期200年月日课程成绩构成：平时分，期中分，实验分，期末分一二三四五六七八九十合计一、单选题（四选一）（10×1＝10分）1.如果命题公式G=P∧Q，则下列之一哪一个成立（2）。1).G=(P→Q)2).G=(P→Q)3).G=(P→Q)4).G=(P→Q)2.设Φ是一个空集，则下列之一哪一个不成立（1）。1).Φ∈Φ2).ΦΦ3).Φ∈{Φ}4).Φ{Φ}3.谓词逻辑的推理中，G(x)(x)G(x)使用的是规则（3）。1).ES2).US3).UG4).EG4.在集合｛0，1｝上可定义（2）个不同的二元运算。1).22).43).84).165.设集合A＝{a,b,c}，A上的二元关系R＝{<a,a>,<b,b>,<c,c>,<a,b>,<c,b>}，则R是A上的（2）关系。1).拟序2).偏序3).全序4).良序0116.设图G的邻接矩阵为000，则G中长度为2的回路总数为（）。1001).12).23).44).57.下列图中（）即非欧拉图又非哈密尔顿图。1).2).3).4).8.设G是一个7阶群，则该群一定有（）个不变子群。1).22).43).64).89.设G是连通的平面图，设n、m、r分别为G的顶点数，边数和面数，则有：n－m＋r＝(。)学院姓名学号任课老师选课号„„„密„„„封„„„线„„„以„„„内„„„答„„„题„„„无„„„效„„1).12).23).34).410.设G是一个24阶群，a是G中任意一个元素，则a的周期一定不是（）。1).22).83).164).24二、多项选择题（五选二至五）（5×1＝5分）1.设G=PQ是仅含原子P和Q的命题公式，则G是（3,4）。1).短语2).析取范式3).合取范式4).主析取范式5).主合取范式2.下列哈斯图中，是格的有（）。1).2).3).4).5).3.若<G,*>是一个13阶群，则运算“*”一定满足（）。交换律1).2).消去律幂等律3.结合律4).5).分配律4.下列谓词的蕴涵公式中，错误的有（1,4,5）。1).(x)G(x)(x)H(x)(x)(G(x)H(x))2).(x)(G(x)H(x))(x)G(x)(x)H(x)3).(x)(G(x)H(x))(x)G(x)(x)H(x)4).(x)G(x)(x)H(x)(x)(G(x)H(x))5).(x)(y)G(x,y)(y)(x)G(x,y)5.非空集合A上的恒等关系具有（135）。1).自反性反自反性2).3).对称性反对称性4).5).传递性三、简答题（4×2=8分）1、试述幂集的定义。2、设R是集合A上的二元关系，试述R是传递性的定义。学院姓名学号任课老师选课号„„„密„„„封„„„线„„„以„„„内„„„答„„„题„„„无„„„效„„3、试述树的定义。4、试述格同态的定义。四、判断分析改错题(如果正确，说明理由，如果不正确，举例说明)（4×5＝20分）1.“若R，S是集合A上的反自反的二元关系，则RS也是反自反的二元关系。”这句话对吗？为什么？2.等价公式“（x）(G(x)H(x))＝（x）G(x)（x）H(x)”成立吗？如果成立，说明理由，如果不成立，举例说明。3.“无向简单图中的每条边都必须在一个连通分支中。”这句话对吗？为什么？学院姓名学号任课老师选课号„„„密„„„封„„„线„„„以„„„内„„„答„„„题„„„无„„„效„„4.“设<G,>是满足消去律的二元代数系统，且幺元存在，则G中除幺元外无其它幂等元。”这句话对吗？为什么？五、计算题（4×8＝32分）1.设有合适公式(x)P(x)(x)Q(f(a)，x)，给定如下解释：个体域D＝{1，0}，＝a0，f(1)＝0，f(0)＝1，P(0)＝0，P(1)＝1，Q(1，1)＝1，Q(1，0)＝1，Q(0，1)＝0，Q(0，0)＝0，计算该合适公式在给定的解释下的真值。12.设A＝{1,2,3,4,5,6,7,8,9},R={<x,y>|x,y∈A且3|(x-y)}，则R是等价关系，计算商集A/R。3.下图为一个无有向图，用邻接矩阵计算该图中长度为3的所有通路和回路总数。学院姓名学号任课老师选课号„„„密„„„封„„„线„„„以„„„内„„„答„„„题„„„无„„„效„„4.设有代数系统<Z,*>，其中Z是整数集合，运算