廣工離散數(shù)學試卷及答案一、單項選擇題（每題2分，共20分）1.在集合{1,2,3}上，以下哪個關(guān)系是等價關(guān)系？A.R={(1,1),(2,2),(3,3),(1,2)}B.R={(1,1),(2,2),(3,3),(2,3)}C.R={(1,1),(2,2),(3,3),(1,3)}D.R={(1,1),(2,2),(3,3),(1,2),(2,1)}2.以下哪個命題是真命題？A.所有的偶數(shù)都是整數(shù)。B.所有的整數(shù)都是偶數(shù)。C.所有的實數(shù)都是復(fù)數(shù)。D.所有的復(fù)數(shù)都是實數(shù)。3.如果一個圖是連通的，那么它至少有多少個頂點？A.1B.2C.3D.44.以下哪個邏輯表達式等價于P∧(Q∨R)？A.(P∧Q)∨(P∧R)B.(P∨Q)∧(P∨R)C.(P∧Q)∨RD.P∧(P∨Q)∧(P∨R)5.以下哪個命題是永真命題？A.P→(Q→P)B.P∧?PC.P∨?PD.P??P6.在一個有向圖中，如果存在從頂點A到頂點B的路徑，那么稱A可達B，以下哪個圖是強連通的？A.只有一個頂點的圖B.所有頂點都相互可達的圖C.存在至少一個頂點不可達其他頂點的圖D.存在至少兩個頂點，其中一個頂點不可達另一個頂點的圖7.以下哪個是圖的生成樹？A.包含圖中所有頂點的子圖B.包含圖中所有邊的子圖C.包含圖中所有頂點且無環(huán)的子圖D.包含圖中所有頂點和邊的子圖8.以下哪個邏輯表達式等價于(P→Q)∧(Q→R)？A.P→RB.?P∨RC.?Q∨RD.P∨R9.以下哪個是二元關(guān)系？A.一個集合與其自身的笛卡爾積B.兩個不同集合的笛卡爾積C.一個集合與其子集的笛卡爾積D.兩個不同集合的并集10.以下哪個命題是永假命題？A.P→(Q→P)B.P∧?PC.P∨?PD.P??P二、填空題（每題3分，共30分）1.如果集合A={1,2,3}，集合B={3,4,5}，則A∩B=______。2.命題“若x>0，則x2>0”的逆否命題是______。3.在一個有n個頂點的完全圖中，邊的數(shù)量是______。4.邏輯表達式(P∨Q)∧?P的等價表達式是______。5.如果一個圖的頂點集是V，邊集是E，則該圖的鄰接矩陣是一個______矩陣。6.命題“若x>0，則x2>0”的逆命題是______。7.在一個無向圖中，如果存在環(huán)，則該圖是______。8.邏輯表達式(P→Q)∧(Q→R)的等價表達式是______。9.如果集合A={1,2,3}，集合B={2,3,4}，則A∪B=______。10.在一個有向圖中，如果存在從頂點A到頂點B的有向路徑，則稱A可達B，以下哪個圖是強連通的？______。三、解答題（每題10分，共50分）1.給定集合A={1,2,3}，B={3,4,5}，請找出A和B的所有子集，并計算A∪B，A∩B，A-B，B-A。2.證明命題“若x>0，則x2>0”是真命題。3.給定一個有5個頂點的無向圖，頂點集為V={v1,v2,v3,v4,v5}，邊集為E={(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)}，請找出該圖的生成樹，并說明理由。4.給定邏輯表達式P∧(Q∨R)，請使用邏輯等價變換將其轉(zhuǎn)換為(P∧Q)∨(P∧R)的形式。5.給定一個有向圖，頂點集為V={A,B,C,D}，邊集為E={(A,B),(B,C),(C,D),(D,A)}，請判斷該圖是否是強連通的，并說明理由。四、附加題（每題10分，共10分）1.給定一個無向圖，頂點集為V={A,B,C,D,E}，邊集為E={(A,B),(B,C),(C,D),(D,E),(E,A),(A,C),(B,D)}，請找出該圖的所有生成樹，并計算生成樹的數(shù)量。答案：一、單項選擇題1.D2.A3.B4.A5.C6.B7.C8.A9.A10.B二、填空題1.{3}2.若x2≤0，則x≤03.n(n-1)/24.Q5.n×n6.若x2>0，則x>07.連通8.P→R9.{1,2,3,4}10.所有頂點都相互可達的圖三、解答題1.A的子集：?,{1},{2},{3},{1,2},{1,3},{2,3},{1,2,3}B的子集：?,{3},{4},{5},{3,4},{3,5},{4,5},{3,4,5}A∪B={1,2,3,4,5}A∩B={3}A-B={1,2}B-A={4,5}2.證明：假設(shè)x>0，根據(jù)實數(shù)的性質(zhì)，x2≥0。又因為x>0，所以x2>0。因此，若x>0，則x2>0是真命題。3.生成樹：{(v1,v2),(v2,v3),(v3,v4),(v4,v5)}。理由：該子圖包含所有頂點且無環(huán)，滿足生成樹的定義。4.證明：P∧(Q∨R)≡(P∧Q)∨(P∧R)。根據(jù)邏輯等價變換，我們可以將P∧(Q∨R)轉(zhuǎn)換為(P∧Q)∨(P∧R)的形式。5.該圖是強連通的。理由：在該有向圖中，每個頂點都可達其他頂點，滿足強連通圖的定義。四、附加題1.生成樹：{(A,B),(B,C),(C,D),(D,E),(E,