离散数学期末试卷和答案

离散数学课程期末考试试卷（第A卷）考试专业班级信息09101、09102班考试形式闭卷考试时间120分钟考试学期2010年下学期考试类型考试命题教师席金菊题号一二三四五六七八总分分值202040200000100一、选择题(总共20分,每小题2分)1.设G是n个结点、m条边和r个面的连通平面图，则m等于（）。A、n+r-2；B、n-r+2；C、n-r-2；D、n+r+2。2.设L(x)：x是演员，J(x)：x是老师，A(x,y)：x钦佩y，命题“所有演员都钦佩某些老师”符号化为（）。A、；B、；C、；D、3.设K={e,a,b,c}，是Klein四元群，则元素a的逆元为（）。A、e；B、a；C、b；D、c。4.设，下列各式中（）是正确的。domSB；B、domSA；C、ranSA；D、domSranS=S。5.下面是前缀编码的是（）A.00,10,110,011B.10,000,101,01C.111,000,110,11D.010,110,01,1016.设A，+，·是一代数系统，+、·为普通加法和乘法运算，当A为（）时，A，+，·是域。A、；B、；C、；D、。7.下列问题成立的有（）。A、若，则；B、若，则；C、若，则；D、若，则。8.设集合A，B是有穷集合，且，则从A到B有（）个不同的双射函数。A、；B、；C、；D、。9.设A,是一个格，由格诱导的代数系统为，则（）成立。A、；B、；C、；D、。10.下列表达式正确的有（）A、；B、；C、；D、。二、填空题(总共20分,每空2分)1.设p：我生病，q：我去上课，命题“我虽然生病但我还是去上课”符号化为：（）。2.设|A|=3，则A上有（）个二元关系。3.按德摩根定理，=()。4.设考虑下列子集，，，，则A的划分有（）。5.设P，Q的真值为0，R，S的真值为1，则的真值=（）。6.任一有向图中，度数为奇数的结点有()个。7.若是集合A的一个分划，则它应满足（）。8.令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。9.给定命题公式A、B，若（），则称A和B是逻辑相等的。10.设图D=V，E，V={v1，v2，v3，v4}，若D的邻接矩阵A=，则deg-（v1）=（）。三、简答题(总共40分,每小题8分)1.设集合A={a,b,c,d}上关系R={a,b,b,a,b,c,c,d}要求1）写出R的关系矩阵和关系图。（4分）2）用矩阵运算求出R的传递闭包。（4分）2.设A={1，2，3，4}，S={{1}，{2，3}，{4}}，为A的一个分划，求由S导出的等价关系。3.已知某树有2个2度结点、3个3度结点、4个4度结点，问有几个叶子点（无其它度数点）。4.设S=R-{-1}（R为实数集），。说明是否构成群；5.将公式划为只含有联结词的等价公式。四、证明题(总共20分,每小题10分)1.设，在上定义关系当且仅当，证明是上的等价关系，并求出2.试证明若是群，，且任意的，对每一个，有，则是的子群。