《離散數(shù)學(xué)》期末考試試題

第第3頁(yè)（共3頁(yè)）第第2頁(yè)（共3頁(yè)）第第1頁(yè)(共3頁(yè))《離散數(shù)學(xué)》期末考試試題一、填空題(每空2分，合計(jì)20分).設(shè)個(gè)體域?yàn)镈={—2,3,6},F(x):x<3,G(x):x>0。則在此解釋下公式(Vx)(F(x)△G(x))的真值為。.設(shè)p：我是大學(xué)生，q：我喜歡數(shù)學(xué)。命題“我是喜歡數(shù)學(xué)的大學(xué)生"為可符合化為。.設(shè)A={1,2,3,4},B={2,4,6}，則A—B=,A十B=。.合式公式-<0—P)八P是永式。5。給定集合A={1,2,3,4,5}，在集合A上定義兩種關(guān)系：R={<1,3>,<3,4>,<2,2>}，S={<4,2>,<3,1>,<2,3>}，貝IR°S=，SoR=。6。設(shè)e是群G上的幺元，若aeG且a2=e，則a-1=—,a-2=。.公式」(PvQ)△(Pv-(Q△-S))的對(duì)偶公式為..設(shè)A={2,3,6,12},Y是A上的整除關(guān)系，則偏序集<A,Y>的最大元是 ,極小元是.9。一棵有6個(gè)葉結(jié)點(diǎn)的完全二叉樹(shù)，有個(gè)內(nèi)點(diǎn);而若一棵樹(shù)有2個(gè)結(jié)點(diǎn)度數(shù)為2,一個(gè)結(jié)點(diǎn)度數(shù)為3，3個(gè)結(jié)點(diǎn)度數(shù)為4，其余是葉結(jié)點(diǎn)，則該樹(shù)有 個(gè)葉結(jié)點(diǎn).10。設(shè)圖G10。設(shè)圖G=<丫,E>,V={V1,v2,V3,v4}，若G的鄰接矩陣A=0111101011100，000貝Udeg-(v1)=,deg+(v4)=二、選擇題(每題2分,合計(jì)20分).下列各式中哪個(gè)不成立().A、Vx(P(x)vQ(x))oVxP(x)vVxQ(x)；B、3x(P(x)vQ(x))o3xP(x)v3xQ(x)；C、Vx(P(x)△Q(x))oVxP(x)aVxQ(x)；D、Vx(P(x)aQ)oVxP(x)aQ..謂詞公式V武P(x)v3yR(y))-Q(x)中的x是()。人、自由變?cè)?B、約束變?cè)?；C、既是自由變?cè)质羌s束變?cè)?D、既不是自由變?cè)植皇羌s束變?cè)＃?集合的以下運(yùn)算律不成立的是( )。A.AQB^B^A b.AUB^B]JACA十B=B十A D.A-B=B-A.公式VxVy(P(x,y)vQ(y,工))a3xP(x,y)換名()。VxVu(P(x,u)vQ(u,z))a3xP(x,y)VxVy(P(x,u)vQ(u,z))a3xP(x,u)VxVy(P(x,y)vQ(y,z))a3xP(x,u)VuVy(P(u,y)vQ(y,z))a3uP(u,y).5。設(shè)集合A,B是有窮集合，且囿二m,|B|=n，則從A到B有()個(gè)不同的雙射函數(shù).A、n；B、m；C、n!; D、m!。.設(shè)A={a,b,c,d},A上的等價(jià)關(guān)系R={<a,b>,<b,a>,<c,d>,<d,c>},則對(duì)應(yīng)于R的A的劃分是()A.{{a},{b,c},61k8em9} B.{{a,b},{c},pzyxfd8}C.{{a},,{c},r96f0qh} D.{{a,b},{c,d}}.設(shè)A={1,2,3,4}，則A上的二元關(guān)系有()個(gè)。A.24 B。42 C.2公4D.42x2.下面集合()關(guān)于減法運(yùn)算是封閉的.A、N;B、{2x|xeI}；C、{2x+11xeI}； d、{x|x是質(zhì)數(shù)}。。設(shè)集合X={0,1,2,3},R是X上的二元關(guān)系，R={<0,0>,<0,2>,<1,2>,<1,3>,<2,0>,<2,1>,<3,3>},則R的關(guān)系矩陣Mr是R( )

A.Co10101010B.000110100101A.Co10101010B.0001101001011110Do1110001100011010.一個(gè)連通的無(wú)向圖G,如果它的所有結(jié)點(diǎn)的度數(shù)都是偶數(shù)，那么它具有一條（ ）A.漢密爾頓回路 Bo歐拉回路 C.漢密爾頓通路 D.初級(jí)回路三、計(jì)算題（每題8分合計(jì)40分）.寫出命題公式「5-幻的真值表..集合A={2,3,6,12,24,36}上的偏序關(guān)系I為整除關(guān)系。設(shè)5二{6,12},。二{2,3,6},試畫出〈A,|＞的哈斯圖，并求集合5和。中關(guān)于|的極大元、最大元、下界和下確界。3o求命題公式「（尸a。）?！梗ā甘?R）的主析取范式。4O求下圖所示的邊賦權(quán)圖的一棵最小生成樹(shù)。5。已知某有向圖的鄰接矩陣如下:V1V2v5。已知某有向圖的鄰接矩陣如下:V1V2v3V4001110、110111)試求：V3到V1的長(zhǎng)度為4的有向路徑的條數(shù)。四證明題（每題10分，合計(jì)20分）.設(shè)論域D為全總個(gè)體域，謂詞G（x）：x是研究生,T（x）:x是推薦免試者，K（x）：x是統(tǒng)考選拔者。在謂詞邏輯中符號(hào)化下列各命題,推證結(jié)論的有效性。“所有的研究生或者是推薦免試者或者是統(tǒng)考