下载
加入VIP
  • 专属下载特权
  • 现金文档折扣购买
  • VIP免费专区
  • 千万文档免费下载

上传资料

关闭

关闭

关闭

封号提示

内容

首页 河南科技学院新科学院离散数学试卷2

河南科技学院新科学院离散数学试卷2.doc

河南科技学院新科学院离散数学试卷2

lv大飞
2019-02-21 0人阅读 举报 0 0 暂无简介

简介:本文档为《河南科技学院新科学院离散数学试卷2doc》,可适用于高等教育领域

离散数学试题()一、单项选择题(本大题共小题每小题分共分)在每小题列出的四个选项中只有一个选项是符合题目要求的请将正确选项前的字母填在题后的括号内。一个连通的无向图G如果它的所有结点的度数都是偶数那么它具有一条(   )A汉密尔顿回路          B欧拉回路C汉密尔顿通路          D初级回路设G是连通简单平面图G中有个顶点个面则G中的边是(   )A      B       C      D在布尔代数L中表达式(a∧b)∨(a∧b∧c)∨(b∧c)的等价式是(   )Ab∧(a∨c)B(a∧b)∨(a’∧b)C(a∨b)∧(a∨b∨c)∧(b∨c)D(b∨c)∧(a∨c)设i是虚数·是复数乘法运算则G=<{,,i,i},·>是群下列是G的子群是(   )A<{},·>            B〈{},·〉  C〈{i},·〉           D〈{i},·〉设Z为整数集A为集合A的幂集为P(A),、、为数的加、减、除运算∩为集合的交运算下列系统中是代数系统的有(   )A〈Z〉           B〈Z〉C〈Z〉           D〈P(A)∩〉下列各代数系统中不含有零元素的是(   )A〈Q*〉Q是全体有理数集*是数的乘法运算B〈Mn(R),*〉,Mn(R)是全体n阶实矩阵集合*是矩阵乘法运算C〈Z〉Z是整数集定义为xxy=xy,x,y∈ZD〈Z〉Z是整数集是数的加法运算设A={,,}A上二元关系R的关系图如下:R具有的性质是A自反性B对称性C传递性D反自反性设A={a,b,c}A上二元关系R={〈a,a〉〈b,b〉,〈a,c〉}则关系R的对称闭包S(R)是(   )AR∪IA      BR      CR∪{〈c,a〉}    DR∩IA设X={a,b,c},Ix是X上恒等关系要使Ix∪{〈a,b〉〈b,c〉〈c,a〉〈b,a〉}∪R为X上的等价关系R应取(   )A{〈c,a〉〈a,c〉}       B{〈c,b〉〈b,a〉}C{〈c,a〉〈b,a〉}        D{〈a,c〉〈c,b〉}下列式子正确的是(   )A∈      B  C{}    D{}∈设解释R如下:论域D为实数集a=,f(x,y)=xy,A(x,y):x<y下列公式在R下为真的是(   )A(x)(y)(z)(A(x,y))→A(f(x,z),f(y,z))B(x)A(f(a,x),a)C(x)(y)(A(f(x,y),x))D(x)(y)(A(x,y)→A(f(x,a),a))设B是不含变元x的公式谓词公式(x)(A(x)→B)等价于(   )A(x)A(x)→B           B(x)A(x)→BCA(x)→B             D(x)A(x)→(x)B谓词公式(x)(P(x,y))→(z)Q(x,z)∧(y)R(x,y)中变元x(   )A是自由变元但不是约束变元B既不是自由变元又不是约束变元C既是自由变元又是约束变元D是约束变元但不是自由变元若P:他聪明Q:他用功则“他虽聪明但不用功”可符号化为(   )AP∨Q     BP∧┐Q     CP→┐Q      DP∨┐Q以下命题公式中为永假式的是(   )Ap→(p∨q∨r)          B(p→┐p)→┐pC┐(q→q)∧p           D┐(q∨┐p)→(p∧┐p)二、填空题(每空分共分)在一棵根树中仅有一个结点的入度为称为树根其余结点的入度均为。A={,,,}上二元关系R={〈〉〈〉〈〉}R的关系矩阵MR中m=,m=。设〈s,*〉是群则那么s中除外不可能有别的幂等元若〈s,*〉有零元则|s|=。设A为集合P(A)为A的幂集则〈P(A)〉是格若x,y∈P(A),则x,y最大下界是最小上界是。设函数f:X→Y,如果对X中的任意两个不同的x和x它们的象y和y也不同我们说f是函数如果ranf=Y则称f是函数。设R为非空集合A上的等价关系其等价类记为〔x〕R。x,y∈A若〈x,y〉∈R则〔x〕R与〔y〕R的关系是而若〈x,y〉R则〔x〕R∩〔y〕R=。使公式(x)(y)(A(x)∧B(y))(x)A(x)∧(y)B(y)成立的条件是不含有y不含有x。设M(x):x是人D(s):x是要死的则命题“所有的人都是要死的”可符号化为(x),其中量词(x)的辖域是。若H∧H∧…∧Hn是则称H,H,…Hn是相容的若H∧H∧…∧Hn是则称H,H,…Hn是不相容的。判断一个语句是否为命题首先要看它是否为     然后再看它是否具有唯一的   。三、计算题(共分)(分)设有向图G=(V,E)如下图所示试用邻接矩阵方法求长度为的路的总数和回路总数。()设A={a,b},P(A)是A的幂集是对称差运算可以验证<P(A)>是群。设n是正整数求({a}{b}{a})n{a}n{b}n{a}n(分)设A={,,,,},A上偏序关系R={〈〉〈〉〈〉〈〉〈〉〈〉〈〉}∪IA()作出偏序关系R的哈斯图()令B={,,,}求B的最大最小元极大、极小元上界下确界下界下确界。(分)求┐(P→Q)(P→┐Q)的主合取范式并给出所有使命题为真的赋值。(分)设带权无向图G如下求G的最小生成树T及T的权总和要求写出解的过程。(分)求公式┐((x)F(x,y)→(y)G(x,y))∨(x)H(x)的前束范式。四、证明题(共分)(分)设T是非平凡的无向树T中度数最大的顶点有个它们的度数为k(k≥),证明T中至少有k片树叶。(分)设A是非空集合F是所有从A到A的双射函数的集合是函数复合运算。证明:〈F,〉是群。(分)在个体域D={a,a,…an}中证明等价式:(x)(A(x)→B(x))(x)A(x)→(x)B(x)五、应用题(共分)(分)如果他是计算机系本科生或者是计算机系研究生那么他一定学过DELPHI语言而且学过C语言。只要他学过DELPHI语言或者C语言那么他就会编程序。因此如果他是计算机系本科生那么他就会编程序。请用命题逻辑推理方法证明该推理的有效结论。(分)一次学术会议的理事会共有个人参加他们之间有的相互认识但有的相互不认识。但对任意两个人他们各自认识的人的数目之和不小于。问能否把这个人排在圆桌旁使得任意一个人认识其旁边的两个人根据是什么参考答案一、单项选择题(本大题共小题每小题分共分)B     D     A     A     DD     D     C     D     BA    A    C    B    C二、填空题      单位元   x∩y      x∪y入射  满射[x]R=[y]R      A(x)     B(y)(M(x)→D(x))     M(x)→D(x)可满足式    永假式(或矛盾式)陈述句  真值三、计算题M=   M=G中长度为的路总数为长度为的回路总数为。当n是偶数时x∈P(A),xn=当n是奇数时x∈P(A),xn=x于是:当n是偶数({a}{b}{a})n{a}n{b}n{a}n=({a})n{b}n{a}n=当n是奇数时({a}{b}{a})n{a}n{b}n{a}n={a}{b}{a}({a})n{b}n{a}n={a}{b}{a}{a}{b}{a}=()偏序关系R的哈斯图为()B的最大元:无最小元:无极大元:极小元:下界:下确界上界:无上确界:无原式(┐(P→Q)→(P→┐Q))∧((P→┐Q)→┐(P→Q))((P→Q)∨(P→┐Q))∧(┐(P→┐Q)∨┐(P→Q))(┐P∨Q∨┐P∨┐Q)∧(┐(┐P∨┐Q)∨(P∧┐Q))(┐(P∧┐Q)∨(P∧┐Q))(P∧Q)∨(P∧┐Q)P∧(Q∨┐Q)P∨(Q∧┐Q)(P∨Q)∧(P∨┐Q)命题为真的赋值是P=,Q=和P=,Q=令e=(v,v),  e=(v,v)e=(v,v),  e=(v,v)e=(v,v),  e=(v,v)e=(v,v),  e=(v,v)e=(v,v),  e=(v,v)令ai为ei上的权则a<a<a<a<a=a=a=a<a=a取a的e∈T,a的e∈T,a的e∈T,a的e∈T,a的e∈T,即T的总权和==原式┐(xF(x,y)→yG(x,y))∨xH(x) (换名)┐xy(F(x,y)→G(x,y))∨xH(x) xy┐(F(x,y)→G(x,y))∨xH(x) xyx(┐(F(x,y)→G(x,y))∨H(x) 四、证明题设T中有x片树叶y个分支点。于是T中有xy个顶点有xy条边由握手定理知T中所有顶点的度数之的=(xy)。又树叶的度为任一分支点的度大于等于且度最大的顶点必是分支点于是≥x·(y)kk=xyK从而(xy)≥xykx≥k从定义出发证明:由于集合A是非空的故显然从A到A的双射函数总是存在的如A上恒等函数因此F非空()f,g∈F,因为f和g都是A到A的双射函数故fg也是A到A的双射函数从而集合F关于运算是封闭的。()f,g,h∈F,由函数复合运算的结合律有f(gh)=(fg)h故运算是可结合的。()A上的恒等函数IA也是A到A的双射函数即IA∈F,且f∈F有IAf=fIA=f,故IA是〈F〉中的幺元()f∈F,因为f是双射函数故其逆函数是存在的也是A到A的双射函数且有ff=ff=IA,因此f是f的逆元由此上知〈F〉是群证明(x)(A(x)→B(x))x(┐A(x)∨B(x))(┐A(a)∨B(a))∨(┐A(a)∨B(a))∨…∨(┐A(an)∨B(an)))(┐A(a)∨A(a)∨…∨┐A(an)∨(B(a)∨B(a)∨…∨(B(an))┐(A(a)∧A(a)∧…∧A(an))∨(┐B(a)∨B(a)∨…∨(B(an))┐(x)A(x)∨(x)B(x)(x)A(x)→(x)B(x)五、应用题令p:他是计算机系本科生q:他是计算机系研究生r:他学过DELPHI语言s:他学过C语言t:他会编程序前提:(p∨q)→(r∧s),(r∨s)→t结论:p→t证①p        P(附加前提)②p∨q      T①I③(p∨q)→(r∧s) P(前提引入)④r∧s      T②③I⑤r        T④I⑥r∨s      T⑤I⑦(r∨s)→t    P(前提引入)⑧t        T⑤⑥I可以把这个人排在圆桌旁使得任一人认识其旁边的两个人。根据:构造无向简单图G=<V,E>,其中V={v,v,…V}是以个人为顶点的集合E中的边是若任两个人vi和vj相互认识则在vi与vj之间连一条边。Vi∈V,d(vi)是与vi相互认识的人的数目由题意知vi,vj∈V有d(vi)d(vj),于是G中存在汉密尔顿回路。设C=ViVi…ViVi是G中一条汉密尔顿回路按这条回路的顺序按其排座位即符合要求。

用户评价(0)

关闭

新课改视野下建构高中语文教学实验成果报告(32KB)

抱歉,积分不足下载失败,请稍后再试!

提示

试读已结束,如需要继续阅读或者下载,敬请购买!

文档小程序码

使用微信“扫一扫”扫码寻找文档

1

打开微信

2

扫描小程序码

3

发布寻找信息

4

等待寻找结果

我知道了
评分:

/18

河南科技学院新科学院离散数学试卷2

VIP

在线
客服

免费
邮箱

爱问共享资料服务号

扫描关注领取更多福利