离散数学期末考试题答案.pdf

《离散数学期末考试题答案.pdf》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案北京交通大学2007-2008学年第二学期《离散数学基础（信科专业）》期末考试卷（A）学院：_____________专业：___________________班级____________姓名：学号：□选修□必修题号总分得分阅卷人一、填空题（共10分，每空1分）1.在推理理论中，推导过程中如果一个或多个公式重言蕴涵某个公式，则这个公式就可以引入推导过程中，这一推理规则叫做（T规则）。2.设A={a，{b}}，则A的幂集是P(A)={Φ,a，{b},{a，{b}}；3.设R是集

2、合A上的二元关系，如果关系R同时具有自反性、反对称性和传递性，则称R是A上的一个偏序关系。4.既是满射，又是单射的映射称为1-1映射（双射）。5.设S为非空有限集,代数系统的单位元和零元分别为S和φ。6.具有n个顶点的无向完全图共有n(n-1)/2条边。7.简单图是指无环、无重边的图。8.k-正则图是指所有顶点的度数均为k的的图。9.Hamilton通路是指通过图中所有顶点一次且仅一次的通路。10.设G=（E，V）是图，如果G是连通的，则P（G）=1。11.命题公式(PQ)(PR)的主析取范式中包含极小项（A）A．PQR；B．PQR；

3、第1页共7页北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案C．PQR；D．PQR12.下列谓词公式中（A）不正确。A．(x)(A(x)B)(x)A(x)B；B．(x)(BA(x))B(x)A(x)；C．(x)(BA(x))B(x)A(x)；D．(x)(A(x)B)(x)A(x)B；13.设S={2，a，{3}，4}，R={{a}，3，4，1}，指出下面的写法中正确的是（D）（A）R=S；（B）{a,3}S；（C）{a}R；（D）R；14.下列命题公式不是重言式的

4、是C。A.Q→(P∨Q)；B.(P∧Q)→P；C.（P∧Q）；D.（P∧0）。15.下列谓词公式中（）不正确。(A)(x)(A(x)B)(x)A(x)B；(B)(x)(BA(x))B(x)A(x)；(C)(x)(BA(x))B(x)A(x)；(D)(x)(A(x)B)(x)A(x)B；16.下列命题中正确的是（B）。(A)∪{}=；(B){,{}}-{{}}={}；(C){,{}}-{}={，{}}；(D){,{}}-={{}}；17.设A,B,C为任意三个集合，下列各命题中正确的是（A

5、）。(A)若AB且BC，则AC；(B)若AB且BC，则AC；(C)若AB且BC，则AC；(D)若AB且BC，则AC。2x,x318.设f:RR,f(x),g:RR,g(x)x2,则(fg)(x)A。2,x32(x2)x1(x2)x3（A）;（B）;2x12x322(x2)x1(x2)x3（C）;（D）.2x10x319.设R1，R2是集合A={a，b，c，d}上的两个关系，其中R1={（a，a），（b，b），（b，c），（d，d）}，R2={（a，a），（b，b）

6、，（b，c），（c，b），（d，d）}，则R2是R1的（B）闭包。(A)自反(B)对称(C)传递(D)以上都不是第2页共7页北京交通大学2007-2008学年第2学期离散数学基础（06级信科专业）期末试题&参考答案20.设偏序关系R是集合A={1，2，3，4，5，6}中数的“整除”关系，则A的极大元、极小元的个数分别是（C）。(A)2，1(B)2，2(C)3，1(D)3，2二、计算题（共40分，每小题10分）1.求命题公式（PQ）（PR）的主合取范式。2.在一个班级的50个学生中，有26人在第一次考试中得到A，21人在第二次考试中得到A。假如有17人两次考试

7、都没有得到A，问有多少学生两次考试中都得到了A？3.设为一个偏序集，其中，A={1，2，3，4，6，9，24，54}是A上的整除关系。（1）画出的哈斯图；（2）求R关于A的极大元；（3）求B={4,6,9}的最小上界和最大下界。4.用逻辑推理方法证明：{PQ，RS，PR}蕴涵QS。5.将公式P((PQ)(QP))化为主析取范式和主合取范式：解：P((PQ)(QP))P((PQ)QP)P(QP)(P(QQ))(QP)(PQ)(PQ)(QP)（主析取范式）P((PQ)(