东南大学2012年6月离散数学A答案

共7页第1页东南大学考试卷（A卷）课程名称离散结构（1）考试学期11-12-3得分适用专业计算机科学与技术考试形式闭卷考试时间长度120分钟一、选择题（每题2分，共10分）1．下列语句中，（C）是命题。（A）如果天黑了你就把灯打开；（B）这世界一切言论都是谎言；（C）2和3都是奇数；（D）x+56；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∀yP(x,y)；（C）∀xP(x,x)；（D）∀x∃yP(x,y)；3、设命题公式G=(P→Q)，H=P→(Q→P)，则G与H的关系是（A）（A）G⇒H；（B）H⇒G；（C）G⇔H；（D）以上都不是；4、设集合为A={2，{a}，3，4}，B={{a}，3，4，1}，E为全集下列命题为真的是（C）（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不具备（D）（A）自反性；（B）传递性；（C）对称性；（D）反对称性；学号姓名密封线共7页第2页二、填空题（每空2分，共30分）1．A={a,b,c,d}，A上的二元运算*如下：*abcdaabcdbbcdaccdabddabc则代数系统A,*的幺元为a，a、b、c、d的逆元分别为a,d,c,b。2、命题公式(P→Q)∧R的主析取范式为P∧Q∧R。3、一阶逻辑公式为∀xP(x)→∃xQ(x)的前束范式为∃x(P(x)⋁Q(x))。4、设个体域为全总域，F(x)：x是人类，G(x)：x是野兽，H(x,y)：x力量比y大，则，“有的野兽力量比人力气都大”可符号化为∃x∃y(G(x)⋀F(y)∧H(x,y))；“不存在力量比所有野兽都大的人类”可符号化为⌝∃x(F(x)⋀∀y(G(y)→H(x,y)))；“说凡是人类就比野兽力量小是不对的”可符号化为⌝∀x(F(x)→∀y(G(y)→H(x,y)))。4、设集合A＝{1,2,3,4},A上的关系R1={(1,4),(2,3),(3,2)},R1={(2,1),(3,2),(4,3)},则R1∘R2=__{(1,3),(2,2),(3,1)}__,R2∘R1=__{(2,4),(3,3),(4,2)}R12=____{(2,2),(3,3)}___.5、设A={a,b,c}，R={a,b,b,a}∪IA是A上的等价关系，设自然映射g：A→A/R，那么g(a)={a,b}。6、设A={1，2，3}，则A上既不是对称又不是反对称的关系R={1,2,1,3,2,1}。A上既是对称又是反对称的关系R={1,1,2,2,3,3}。7、拉格朗日定理说明若H，*是群G，*的子群，则可建立G中的等价关系：R={a,b|a∈G,b∈G,a-1*b∈H}。若|G|=n,|H|=m，则m和n的关系为m/n。共7页第3页三、用主析取范式判断下列公式是否等价。（7分）（1）G=(P∧Q)⋁(P∧Q∧R)（2）H=(P⋁(Q∧R))∧(Q⋁(P∧R))G＝(P∧Q)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m7∨m3H=(P∨(Q∧R))∧(Q∨(P∧R))＝(P∧Q)∨(Q∧R))∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝(P∧Q∧R)∨(P∧Q∧R)∨(P∧Q∧R)＝m6∨m3∨m7四、设集合A＝{1,2,4,6,8,12}，R为A上整除关系。1、画出偏序集(A,R)的哈斯图；（3分）2、写出A的最大元，最小元，极大元，极小元；（3分）3、写出A的子集B={4,6,8,12}的上界，下界，最小上界，最大下界.（2分）(共8分)(2)无最大元，最小元1，极大元8,12;极小元是1.(3)B无上界，无最小上界。下界1,2;最大下界2.1246812共7页第4页五、给出以下命题：所有的诗人都很浪漫，老王是个工程师也是个诗人，因此有些工程师很浪漫。（1）对以上命题进行符号化；（2分）（2）用逻辑推理证明：（5分）（共7分）P(x)：x是个诗人；Q(x)：x很浪漫；S(x)：x是个工程师；a：老王；前提：∀x(P(x)→Q(x))；S(a)∧P(a)；结论：∃x(S(x)∧Q(x))1、S(a)∧P(a)前提引入2、∀x(P(x)→Q(x))前提引入3、P(a)→Q(a)全称量词消去4、P(a)1代换实例5、Q(a)3、4代换实例6、S(a)1代换实例7、S(a)∧Q(a)5、6代换实例8、∃x(S(x)∧Q(x))存在量词引入六、设R是A上的一个二元关系，S={a,b|a,b∈A并且对于任意的c都有a,c∈R且c,b∈R}。证明若R是A上一个等价关系，则S也是A上的一个等价关系。（12分）（1）S自反的Aa，由R自反，),(),(RaaRaa，Saa,共7页第5页（2）S对称的传递对称定义RSabRRbcRcaSRbcRcaSbaAba,),(),(),(),(,,（3）S传递的定义传递SScaRRcbRbaRceRebRbdRdaScbSbaAcba,),(),(),(),(),(),(,,,,由（1）、（2）、（3）得；S是等价关系。七、设N6,+6是一个群，其中N6={0，1，2，3，4，5},+6为模6加。（1）证明N6,+6与N,+为满同态，其中N为包含0的自然数集合，+为加法；（3分）（2）求出所有的子群以及相应的陪集；（4分）（3）求出N6所有元素的阶；（3分）（共10分）1）证明：构造g：N→N6如下g(a)=amod6；显然g为满射；对于任意的a,b∈Ng(a+b)=(a+b)mod6=amod6+4bmod6=g(a)+4g(b)2）子群有{0},+6；{0,3},+6；[0,2,4},+6；Z6,+6{0}的左陪集：{0}，{1}；{2}，{3}；{4}，{5}{0，3}的左陪集：{0，3}；{1，4}；{2，5}{0，2，4}的左陪集：{0，2，4}；{1，3，5}N6的左陪集：N6。共7页第6页3）|0|=1；|1|=6；|2|=3；|3|=2；|4|=3；|5|=6；八、某公司要从A、B、C、D、E五名员工中选择一些人去非洲出差，选择必须满足以下条件：（1）若A去则B也去；（2）D和E中必有一人去；（3）B和C中去且仅去一人；（4）C和D两人同去或同不去；（5）若E去，则A和B也同去；用等值演算法分析该公司的派遣方案。（8分）参见课本P40第30题共7页第7页