资源描述：
《东南大学2012年6月离散数学A答案.doc》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、学号姓名密封线东南大学考试卷（A卷）课程名称离散结构（1）考试学期11-12-3得分适用专业计算机科学与技术考试形式闭卷考试时间长度120分钟一、选择题（每题2分，共10分）1．下列语句中，（C）是命题。（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∀yP(x,y)；（C）∀xP(x,x)；（D）∀x∃yP(x,y)；3、设命题公式G=Ø(P→
2、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）反对称性；一、填空题（每空2分，共30分）1．A={a,b,c,d}，A上的二元运算*如下：*abcdaab
3、cdbbcdaccdabddabc则代数系统的幺元为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)→
4、∀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={}∪IA是A上的等价关系，设自然映射g：A→A/R，那么g(a)={a,b}。6、设A={1，2，3}，则A上既不是对称又不是反对称的关系R={<1,2>,<1,3>,<2,1>}。A上既是对称又是反
5、对称的关系R={<1,1>,<2,2>,<3,3>}。7、拉格朗日定理说明若是群的子群，则可建立G中的等价关系：R={
6、a∈G,b∈G,a-1*b∈H}。若
7、G
8、=n,
9、H
10、=m，则m和n的关系为m/n。三、用主析取范式判断下列公式是否等价。（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∧
11、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分)1246812(2)无最大元，最小元1，极大元8,12;极小元是1.(3)B无上界，无最小上界。下界1,2;最大下界2.五、给出以下命题：所有的诗人都很浪漫，老王是个工程师也是个诗人，因此有些工程师很浪漫。（1）对
12、以上命题进行符号化；（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))存在
