离散数学期末考试题-09-10-2-A-信科-试题

北京交通大学2009-2010学年第2学期《离散数学》期末考试试卷（A）学院_理学院________专业___信科__________班级__0801-0805____学号_______________姓名_____________题号一二三四总分得分阅卷人一、填空题（共20分，每小题2分）1.令F(x)：x是实数，G(x)：x是有理数。命题“实数不全是有理数”的符号化形式为（）。2.若含(1)nn≥个命题变项的公式A是重言式，则A的主合取范式为（）。3.设，R是A的幂集是P(A)上的关系，且A{1,2,3}={},|Rababφ=∩≠。在自反、反自反、对称、反对称、传递五种性质中，R满足（）性质。4.设R是集合A上的二元关系，如果关系R同时具有（）性、对称性和传递性，则称R是等价关系。5.设代数系统6,VZ=⊗，其中⊗为模6乘法，那么V中的幂等元是（）。6.半群、群及独异点的关系是（）。7.设群Ga=是15阶循环群，则子群3Ha=的元素是（）。8.在布尔格,A≤中有3个原子123,,aaa，则1a=（）。9.若n阶无向简单图G的1nδΔ==−，则G为（）。10.设n阶图的点连通度()Tκ、边连通度()Tλ、最小度()Tδ、最大度()TΔ，则这四个值从小到大排列顺序为（）。二、选择题（共20分，每小题2分）1.命题公式(P→Q)∧(P→R)的主析取范式中包含极小项（）。（A）P∧Q∧R（B）P∧Q∧¬R（C）P∧¬Q∧R（D）P∧¬Q∧¬R2.下列命题中正确的是（）。（A）φ∪{φ}=φ；（B）{φ,{φ}}-{{φ}}={φ}；（C）{φ,{φ}}-{φ}={φ，{φ}}；（D）{φ,{φ}}-φ={{φ}}；3.设R1，R2是集合A={a，b，c，d}上的两个关系，其中R1={（a，a），（b，b），（b，c），（d，d）}R2={（a，a），（b，b），（b，c），（c，b），（d，d）}则R2是R1的（）闭包。（A）自反（B）对称（C）传递（D）以上都不是4.设偏序关系R是集合A={1，2，3，4，5，6}中数的“整除”关系，则A的极大元、极小元的个数分别是（）。（A）2，1（B）2，2（C）3，1（D）3，25.在自然数集N上，下列哪种运算是可结合的（）。（A）a*b=a-b（B）a*b=max(a,b)（C）a*b=a+2b（D）a*b=⏐a-b⏐6.S的幂集P（S）对于运算∩，零元为（）。（A）Ø（B）P（S）（C）S（D）以上均不是7.在以下命题中，不正确的命题是（）。（A）循环群是Abel群；（B）循环群有有限多个生成元；（C）无限循环群的子群都是无限循环群；（D）阶循环群有唯一的阶子群，其中是n的正因子。ndd8.已知在一棵无向树T中，4度，3度，2度的分支点各两个，其余顶点都是树叶，则T的树叶数为（）。（A）3（B）6（C）8（D）59.如图1所示，以下说法正确的是（）。（A）{e1,e2,e3}是边割集（B）{A,C,D}是点割集（C）{E,F}是点割集（D）{e5,e4}是边割集e1e2e5e3e6e4ACDB图1图210.如图2所示，在图中有（）个强分图。（A）0（B）1（C）2（D）3三、计算题（每小题6分，共30分）1.利用等值演算求下面公式的主取范式((()))PQPQR∨∧¬→∧2.求1到250之间能被2，3，5和7任何一个整除的整数的个数。3.设为一个偏序集，其中，A={1，2，3，4，6，9，24，54}是A上的整除关系。（1）画出的哈斯图；（2）求R关于A的极大元；（3）求B={4,6,9}的最小上界和最大下界。4.设集合{1,2}A=，B是A上的等价关系的集合。（1）列出B的元素；（2）给出代数系统,VB=∩的运算表；（3）求出V的单位元、零元以及所有可逆元素的逆元；（4）说明V是否为半群、独异点和群。5.无向图G有11条边，4格3度顶点，其余顶点均为5度顶点，求G的阶数n。四、证明题（每小题10分，共30分）1.设R是A上的自反关系，证明R是A上的等价关系的充分必要条件是：若且,R，则有,∈。,abR∈ac∈bcR2.证明，任何循环群必定是Abel群。3.G8国际会议有8位不同国家的领导人参加,已知每位参会领导人至少与其他7位参会领导人中的4位可以使用共同语言,问能否将他们安排在同一圆桌周围就座,使得每位领导人都能与他两边的领导人交谈？