652離散數(shù)學(xué)試題15

PAGEPAGE4頁（4頁）河南科技大學(xué)2015年碩士研究生入學(xué)考試試題考試科目代碼：652 考試科目名稱：離散數(shù)學(xué)（如無特殊注明，所有答案必須寫在答題紙上，否則以“0”分計(jì)算）一、單項(xiàng)選擇題(本大題共15小題，每小題2分，共30分)1．下列語句（ ）是命題。A．X+Y=13； B7+8＞184條邊；C．我從不講真話； D．給我一杯水吧2．命題公(pq)(pq)可化簡(jiǎn)為（ 。A．p； B．q； C．1； 3．下列公式中（ ）是矛盾式。。A．(PQ)；B．(PQ)Q；C．(PQ)P；D．(QP)P。令Z(x):x是整數(shù)，Q(x):x是有理數(shù)。則命題“并非每個(gè)有理數(shù)都是整數(shù)”的符號(hào)化表示為（ 。A．x(Q(x)Z(x))； B．x(Z(x)Q(x))；Cx(Q(x)Z(x))； Dx(Z(x)Q(x))。5．設(shè)P={x|(x+1)2

4且xR},Q={x|5x2+7且xR},則下列命題正確的是（ 。QP； Q；C．QP； DP=Q。6．集合A={1，2，3，4}上的偏序關(guān)系圖為下圖，則它的哈斯圖為（ 。7．集合A={1,2,…,9}上的關(guān)系R={<x,y>|x+y=12,x,yA}，則R的性質(zhì)為（ A．自反性、對(duì)稱性、傳遞性； B．自反性、反對(duì)稱性；C．反自反性、反對(duì)稱性、傳遞性； D．對(duì)稱性下圖是格L的哈斯圖，則L是（ 。A．分配格；B.有補(bǔ)格；C.布爾格；D. 有界格。9．10階有限群的任何子群一定不是（ 。A.2階； B.5階； C.7階； D.1階10．在自然數(shù)集N上，下列（ ）是可結(jié)合的。A. a*bab； B. a*ba2b；C. a*bmin{a； D.a*b=|a-b|。1．<A,>是偏序集“”定義為：a,b,aba|b，則當(dāng)A（ ）時(shí)<A,>是格A．{1,2,3,4,6,9,12,14}；B．{1,2,3,4,6,12}；C．{1,2,3,…，12}；D．{1,2,3,5,7}下圖中從v到v長(zhǎng)度為2的通路有（ ）條。1 2A．0； B．1； C．2； D．3。設(shè)無向圖G有18條邊且每個(gè)頂點(diǎn)的度數(shù)都是3，則圖G有( )個(gè)頂點(diǎn)A．10； B．4； C．7； D．12。下圖中既不是歐拉圖，也不是Hamilton圖的圖是（ ）下面給出的集合中，哪一個(gè)不是前綴( )。A.{01，001，000，1}； B.{a，ab，110，a1b11}；C.{1，2，00，01，0210}； D.。二、填空題(本大題共10小題，每小題2分，共20分)小王努力學(xué)習(xí)小王取得成功語“小王只有努力學(xué)習(xí)，他才能取得成功符號(hào)化。有一集合A{2,{2}}，則A的冪集；AA= 。若P，Q，為二命題，PQ真值為0當(dāng)且僅當(dāng) 。謂詞公式xF(x)(xG(x))的前束范式。設(shè)A={1，3，5，6}上的二元關(guān)系R{x,yxy是偶}，則（列舉法。公x((P(x)Q(y，x))zR(y，z))S(x)中，自由變?cè)s束變?cè)?。若解釋I的論域D僅包含一個(gè)元素，則xP(x)xP(x) 在I下真值。設(shè)A={a，b，c，d}，A上二元運(yùn)算如下：*abcdaabcdbbcdaccdabddabc那么代數(shù)系<A，*>的幺元是 ，有逆元的元素。若連通平面圖GV,E共有r個(gè)面，其中Vv,Ee，則e= 。設(shè)G是n階無向完全圖，則G的邊數(shù)m= ，它的補(bǔ)圖。三、計(jì)算題(本大題共5小題，每小題8分，共40分)1．求公式(P∨(Q∧R))(P∧Q∧R)的主析取范式和主合取范式，并判斷類型。(注：重言式、矛盾式或可滿足式)2．以1，4，9，16，25，36，49，64，81，100為權(quán)數(shù)構(gòu)造一棵最優(yōu)二叉樹。設(shè)G

,是模6的整數(shù)加群，求G的生成元和所有子群。6G如右圖所示。（1）求G的鄰接矩陣A；（2）G中v1到v44（3）G中v13（4）G是哪類連通圖？5．設(shè)S={1,2,3,4,6,8,12,24”為S上整除關(guān)系，問：<S,的Hass圖如何？<S,?B={2,3,4},B的上界、下界、最小上界、最大下界是什么？四、證明題(本大題共3小題，每小題10分，共30分)1．用邏輯推理證明：所有的舞蹈者都很有風(fēng)度，王華是個(gè)學(xué)生且是個(gè)舞蹈者。因此有些學(xué)生很有風(fēng)度。2．集合X={1,2,3,…,9}，R={<<x1,y1>,<x2,y2>>|x1+y2=x2+y1x1,x2,y1,y2X}。證明R是X上的等價(jià)關(guān)系。3.設(shè)G,*xGaba*x*babG。證明G,也是一群。五、綜合題(本大題共2小題，每小題15分，共30分)R 1．A={1,2,3,R={<1,2>,<3,>,<2,3>,<3,5>}RMG，Rr(R)s(R)t(R)R 2．有7個(gè)城市需要修高鐵，如果用圖