东南大学2012年6月离散数学A.docxVIP

东南大学考试卷（A 卷）课程名称 离散结构（1）考试学期11-12-3得分适用专业计算机科学与技术考试形式闭卷考试时间长度120分钟选择题（每题2分，共10分）1．下列语句中，（）是命题。（A）如果天黑了你就把灯打开；（B）这世界一切言论都是谎言；（C）2和3都是奇数；（D）x + 5 6；2、设I是如下一个解释：D={a , b}, P(a,a)=1, P(a,b)=0, P(b,a)=1, P(b,b)=0, 则在解释I下，取真值为1的公式为（）D（A）?x?yP(x,y)；（B）?x?y P(x,y)；（C）?x P(x,x)；（D）?x?yP(x,y)；3、设命题公式G=(P→Q)，H=P→(Q→P)，则G与H的关系是（）（A）G?H；（B）H?G；（C）G?H；（D）以上都不是；4、设集合为A={2，{a}，3，4}，B={{a}，3，4，1}，E为全集下列命题为真的是（）（A）{2}∈A；（B）{a}?A；（C）Φ?{{a}}?B?E；（D）{{a}，1，3，4}?B；5、设集合A={1，2，3}，A上的关系R={1,1,2,2,2,3,3,2,3,3}, 则R不具备（）（A）自反性；（B）传递性；（C）对称性；（D）反对称性；填空题（每空2分，共20分）1．A={a,b,c,d}，A上的二元运算*如下：*abcdaabcdbbcdaccdabddabc则代数系统A,*的幺元为，a、b、c、d的逆元分别为。2、命题公式(P→Q)∧R的主析取范式为。3、设一阶逻辑公式为?xP(x) →?xQ(x)的前束范式为。4、设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则R1°R2 = _______________________,R2°R1 =____________________________,R12 =________________________.5、设A={a,b,c}，R={a,b,b,a}∪IA是A上的等价关系，设自然映射g：A→A/R，那么g(a)=。6、设A={1，2，3}，则A上既不是对称又不是反对称的关系R=。A上既是对称又是反对称的关系R=。三、用主析取范式判断下列公式是否等价。（10分）（1）G=(P∧Q)?( P∧Q∧R)（2）H=(P?(Q∧R)) ∧(Q?(P∧R))四、设集合A＝{1, 2, 4, 6, 8, 12}，R为A上整除关系。1、画出偏序集(A,R)的哈斯图；（4分）2、写出A的最大元，最小元，极大元，极小元；（3分）3、写出A的子集B = {4, 6, 8, 12}的上界，下界，最小上界，最大下界.（3分）(共10分)五、给出以下命题：所有的诗人都很浪漫，老王是个工程师也是个诗人，因此有些工程师很浪漫。（1）对以上命题进行符号化；（3）（2）用逻辑推理证明：（7分）（共10分）六、设R是A上的一个二元关系，S={a,b | a,b∈A 并且对于任意的c都有a,c∈R且c,b∈R }。证明若R是A上一个等价关系，则S也是A上的一个等价关系。（15分）七、设N6, +6是一个代数系统，其中N6={0，1，2，3，4，5},+6为模6加。（1）证明N6, +6与N, +为满同态，其中N为包含0的自然数集合，+为加法；（5分）（2）求出所有的子群以及相应的陪集；（5分）（3）求出N6所有元素的阶；（5分）（共15分）八、某公司要从A、B、C、D、E五名员工中选择一些人去非洲出差，选择必须满足以下条件：（1）若A去则B也去；（2）D和E中必有一人去；（3）B和C中去且仅去一人；（4）C和D两人同去或同不去；（5）若E去，则A和B也同去；用等值演算法分析该公司的派遣方案。（10分）