山東交通學(xué)院《離散數(shù)學(xué)》試卷2016-2017學(xué)年第一學(xué)期期末試卷

1、設(shè)集合M={a，φ}，N=｛{a｝,φ}則MnN=。3、設(shè)集合H={1，2，3，4則H上的關(guān)系R=｛<x,y>x+y是偶數(shù)｝具有。A、自反性、反對(duì)稱性和傳遞性B、反自反性、反對(duì)稱性和傳遞性C、反自反性、對(duì)稱性和傳遞性D、自反性、對(duì)稱性和傳遞性4、設(shè)T是一棵完全二叉樹(shù)，則T的每個(gè)結(jié)點(diǎn)都。A、至少有兩個(gè)子結(jié)點(diǎn)B、至多有兩個(gè)子結(jié)點(diǎn)C、恰有兩個(gè)子結(jié)點(diǎn)D、可以有任意多個(gè)子結(jié)點(diǎn)政A、結(jié)合律B、交換律C、分配律D、冪等律A、簡(jiǎn)單通路B、初級(jí)通路C、簡(jiǎn)單回路D、初級(jí)回路A、10B、13C、11D、6二、填空題（本大題共8題，共10個(gè)空，每空2分，共20分）3、設(shè)集合M={1,2，3，5}，則M的冪集P（M）包含個(gè)元素。4、設(shè)T是一棵有n(n之2）個(gè)頂點(diǎn)的樹(shù)，則T有條邊.___________________7、設(shè)D是有向圖，若D的基圖是連通圖，則稱D是圖8、既不含也不含的無(wú)向圖稱為簡(jiǎn)單圖.3、設(shè)集合A={1，2，3，4，5}，關(guān)系R={<x，y>x，yA且x整除y｝,要R1、用命題公式將下列命題符號(hào)化:2和5是偶數(shù)，當(dāng)且僅當(dāng)5〉2。2、用謂詞公式將下列命題符號(hào)化：1、在命題邏輯系統(tǒng)中用歸結(jié)法證明下列推理是有效的:前提:sq，pq,s2、在謂詞邏輯系統(tǒng)中寫(xiě)出下列推理的（形式)證明：6。設(shè)命題公式G=（P→Q）∨（Q∧（P→R)求G的主析取范式.11。通過(guò)求主析取范式判斷下列命題公式是否等價(jià)：13.設(shè)R和S是集合A＝{a，b,c，d｝上的關(guān)系,其中R(a，a)a,cb，c)c，d)｝,證明題1。利用形式演繹法證明:{P→Q，R→S，P∨R}蘊(yùn)涵Q∨S.：｛4.n—15.零元6。半群7。弱連通8。平行邊環(huán)三.EQ\*jc3\*hps35\o\al(\s\up0(1),2)R|EQ\*jc3\*hps35\o\al(\s\up18(3),4)EQ\*jc3\*hps35\o\al(\s\up18(0),0)EQ\*jc3\*hps35\o\al(\s\up18(0),0)EQ\*jc3\*hps35\o\al(\s\up18(1),0)EQ\*jc3\*hps35\o\al(\s\up18(0),1)EQ\*jc3\*hps35\o\al(\s\up18(0),0)|四五11)s前提引入（5）M(x）2,4析取三段論（8）P（x）5,7假言推理=（P∨Q）∨(Q∧（P∨R))=（P∧Q）∨（Q∧（P∨R)）=(P∧Q∧R)∨(P∧Q∧R)∨（P∧Q∧R)∨（P∧Q∧R)∨(P∧Q∧R）∨（P∧Q∧R)=（P∧Q∧R）∨(P∧Q∧R）∨(P∧Q∧R)∨(P∧Q∧R）∨(P∧Q∧R）As(RR∪R－1(a，b）,(b，a),（b,c)，(c，b)（c，d）,(d,c）}，ababr(R)bd=(P∧Q∧R）∨(P∧Q∧R)∨（P∧Q∧R）=m∨m∨m=（3，6,7）H=（P∨（Q∧R)）∧（Q∨(P∧R）)=(P∧Q）∨(Q∧R）)∨(P∧Q∧R)=(P∧Q∧R)∨（P∧Q∧R）∨(P∧Q∧R)∨(P∧Q∧R)∨（P∧Q∧R）=(P∧Q∧R）∨（P∧Q∧R）∨(P∧Q∧R)=m∨m∨m=（3,6,7)G，H的主析取范式相同，所以G=H.EQ\*jc3\*hps36\o\al(\s\up11(1),0)EQ\*jc3\*hps36\o\al(\s\up11(0),0EQ\*jc3\*hps36\o\al(\s\up11(1),0)EQ\*jc3\*hps36\o\al(\s\up11(0),0)EQ\*jc3\*hps36\o\al(\s\up11(1),1)EQ\*jc3\*hps36\o\al(\s\up11(0),0)EQ\*jc3\*hps36\o\al(\s\up11(1),0)EQ\*jc3\*hps36\o\al(\s\up11(0),1)EQ\*jc3\*hps36\o\al(\s\up11(0),1)－1a,a),（c,a)c，b）,（d,c)}，PPQ(2)(3）Q（4）PQ（5)(6)Q(7)2。證明:（A—B）-C=（A∩~B）∩~C=A∩(~B∩~C）=A∩~(B∪C)=A-(B∪C）3.證明:{A∨B，C→B,C→D}蘊(yùn)涵A→D