自學(xué)考試專(zhuān)題：離散數(shù)學(xué)(二)練習(xí)題含答案

1、06094離散數(shù)學(xué)(二)單項(xiàng)選擇題1下面給出的句子中， A 不構(gòu)成命題。A不要作弊B3+2=9C7是質(zhì)數(shù)D我是男生 2能使命題PQ為真的條件是 C AP真BQ假CQ真DP真Q假 3用P表示“選張三任班長(zhǎng)”，Q表示“選李四任班長(zhǎng)”。則命題“選張三或李四中的一人任班長(zhǎng)”可符號(hào)為 D APQBPQCPQD4P(3,x,y,z)是 C 元謂詞。A1B4C3D0 5在公式中，稱(chēng)P為量詞的 B A論域B轄域C值域D0 定義域6設(shè)謂詞F(x)表示x是實(shí)數(shù)；Q(x)表示x能被2整除。則命題“存在能被2整除的實(shí)數(shù)”可符號(hào)化為 D ABCD 7由存在指定規(guī)則， A 可得到P(c)。ABCD 8下面描述中 C 是錯(cuò)

2、誤的。AP是合式公式，則P是合式公式 B中x是約束出現(xiàn)的變?cè)狢 是合式公式 D 9只有兩個(gè)元素的集合其冪集共有 C 元素。A2B7C8D16 10設(shè)集合M=1,2，P=2,3。則有 BAMP=2BMP=1，3CM-P=3DMP=1,2,3 11下面給出的集合中， A 不是a,b到1,2,3的二元關(guān)系。Aa,2B(a,2)C<a,2>D空集 12設(shè)A=1,2,B=3,4,M=(1,3),(2,4)是A到B的一個(gè)二元關(guān)系，則M的關(guān)系矩陣第二行第二列的值為 D A0B3C2D1 13A=1,2,3上的關(guān)系R=(1,2),(2,3)的傳遞閉包必含 C 序偶。A(1,1)B(3,2)C(1,

3、3)D(3,1) 14設(shè)(1,2),(2,3)R是A=1,2,3上的偏序，則R必有元 D 。A(3,2)B(2,1)C(3,1)D (1,3) 15實(shí)數(shù)集R及其加法運(yùn)算組成的代數(shù)系統(tǒng)<R,+>不滿(mǎn)足 CA封閉性B結(jié)合律C冪等律D交換律 16非空集合M上二元運(yùn)算*滿(mǎn)足封閉性是指M中的任意元 BA a,b均滿(mǎn)足a*b=b*aBa,b均滿(mǎn)足a*bM C a均滿(mǎn)足a*a=aDa,b,c均滿(mǎn)足(a*b)*c=a*(b*c) 17設(shè)<G,*>是一個(gè)環(huán)，且<G,>是阿貝爾群，則 CA*有幺元B*有零元C<G ,*>是半群D對(duì)于*可分配18在含有100個(gè)頂點(diǎn)的完

4、全圖中，其每個(gè)頂點(diǎn)的度均為 CA100B101C99D50 19連通平面圖G有16個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度都為4。則G共有 A 個(gè)區(qū)域。 A18B17C16D14 20針對(duì)下面給出的各圖，以下說(shuō)法中錯(cuò)誤的是 A(a) (b) (c) (d) Aa與c同構(gòu)Bb是a的子圖Cc是a的生成子圖Dd與c同胚 21 D 是命題。A春天真美B你好嗎？C5-1=9D公共場(chǎng)所別吸煙 22P=0，Q=1，則 A =1。APQBQPCQDPQ23P表示“天下雨”，Q表示“我走路上班”。則“只要天下雨，我就不走路上班”可符號(hào)為 C APQBPQCPQDPQ 24命題函數(shù)就是 A A謂詞變項(xiàng)B個(gè)體變項(xiàng)C個(gè)體常項(xiàng)D 謂詞常項(xiàng)

5、 25下面表達(dá)式中 A 是謂詞公式。ABCD 26設(shè)個(gè)體域?yàn)閷?shí)數(shù)集，P(x)表示x是有理數(shù)；Q(x)表示x可寫(xiě)成分?jǐn)?shù)，則命題“有理數(shù)均可寫(xiě)成分?jǐn)?shù)”可符號(hào)化為： B AP(x)Q(x)BCP(x)Q(x)D27設(shè)個(gè)體域?yàn)?,2,4，P(x,y)表示xy。則下面給出的謂詞公式中 B 為假。 ABCD 28由可得到P(c)。這是應(yīng)用了 D 規(guī)則。A存在推廣B全稱(chēng)推廣C存在指定D全稱(chēng)指定 29集合1,2,3的冪集不含元素 D A空集B1C1,2,3D430設(shè)集合M=a,b,c，P=c,d。則MP= B Aa,bBa,b,dCdDa,b,c,d 311,2×a,b,c不含 B 元素。A(a,2

6、)B(2,a)C(2,c)D(1,b) 32A=1,2,3上的關(guān)系R=(1,2),(2,3)的對(duì)稱(chēng)閉包必含 C 序偶。A(1,3)B(2,2)C(3,2)D(3,1) 33設(shè)集合A=a,b,c,B=x,y,C=4,5,6,R是集合A到集合B的關(guān)系，S是集合B到的集合C關(guān)系，且R=(a,x),(b,x),(b,y),(c,y)，S=(x,4),(y,5),(y,6)。則R與S的復(fù)合關(guān)系中沒(méi)有 A 序偶。A(a,5)B(c,6)C(b,4)D(b,5) 34已知f:RR，f(x)= A 時(shí)f是雙射。A3x5+1B2|x|-1C5x2Dcosx 35非空集合M上二元運(yùn)算*滿(mǎn)足冪等律是指M中的任意元

7、BA a,b均滿(mǎn)足a*b=b*aB a均滿(mǎn)足a*a=aC a,b均滿(mǎn)足a*bMD a,b,c均滿(mǎn)足(a*b)*c=a*(b*c) 36設(shè)*是集合A上的二元運(yùn)算，且在A中有關(guān)于*的左零元a和右零元b，則 BAa>bBa=bCa<bDab37代數(shù)系統(tǒng)<G,*>是群，則以下結(jié)論中， A 是錯(cuò)誤的。AA*滿(mǎn)足交換律B存在幺元C*滿(mǎn)足結(jié)合律D每個(gè)元有逆元 38K5圖的頂點(diǎn)數(shù)和邊數(shù)分別為 A A5、10B5、5C6、6D6、1239圖G有n個(gè)頂點(diǎn)m條邊，圖Q有a個(gè)頂點(diǎn)b條邊。如果Q是G的生成子圖，則 DAn=a,m=bBn>a,m>bCn<a,m<bDn=a

8、,mb40設(shè)M是4個(gè)結(jié)點(diǎn)的簡(jiǎn)單圖的鄰接矩陣。如果M2的第三行的數(shù)據(jù)依次為1、2、3、4， 則第二個(gè)結(jié)點(diǎn)與第三個(gè)結(jié)點(diǎn)之間長(zhǎng)度為2的路徑有 A 條。A2B3C4D1 41合取聯(lián)結(jié)詞的表示符號(hào)為 A ABCD 42在解釋“P真Q假”下，命題 B 是假命題。AQBPQCPQDPQ 43P表示“你來(lái)”，Q表示“我來(lái)”。則“你來(lái)我就不來(lái)”可符號(hào)為 C APQBPQCPQDPQ 44在謂詞邏輯中，論域是指 B 的取值范圍。A量詞B個(gè)體變項(xiàng)C命題函數(shù)D謂詞變項(xiàng) 45已知個(gè)體域?yàn)?,1。消除中的量詞可得 C A(P(0)P(1)(Q(0)Q(1) B(P(0) P(1) (Q(0)Q(1)C(P(0)P(1)Q

9、(0)Q(1) D(P(0)P(1)Q(0)Q(1)46中 B 是存在量詞的轄域。AGBFCxDy 47由P(x)可得到。這是應(yīng)用了 D 規(guī)則。A全稱(chēng)指定B存在推廣C存在指定D全稱(chēng)推廣48 D 是錯(cuò)誤的。AB若P是合式公式，則P是合式公式CP(2,x,y)是二元謂詞D合式公式中不能使用自由變?cè)胍?guī)則 49空集是 D 的真子集。（題中給定的x均為實(shí)數(shù)內(nèi)求解）Ax|x2<0Bx|x2+2x+10=0C4,51,2,3D1，3 50設(shè)集合M=a,b,c,d，P=a,c,e。則M-P= BAa,cBb,dCeDb,d,e 51集合M有2個(gè)元，P有3個(gè)元，則M與P的笛卡爾積的冪集有 C 個(gè)元。A

10、32B128C64D6 52下面有關(guān)二元關(guān)系性質(zhì)的敘述中， B 是錯(cuò)誤的。A存在關(guān)系R既不是對(duì)稱(chēng)的，也不是反對(duì)稱(chēng)的 B如果關(guān)系R的關(guān)系矩陣的主對(duì)角線上的元素不全為1，則R是反自反的C存在關(guān)系R既不是自反的，也不是反自反的 D如果關(guān)系R的關(guān)系矩陣的主對(duì)角線上的元素全為1，則R是自反的53偏序關(guān)系不滿(mǎn)足 C 性。A自反B反對(duì)稱(chēng)C對(duì)稱(chēng)D傳遞54設(shè)f:RR,f(x)=sinx，則f不是 A A滿(mǎn)射B入射C函數(shù)D二元關(guān)系55<S,*>作為代數(shù)系統(tǒng)必須滿(mǎn)足 A AS非空B*是二元運(yùn)算C*有幺元D*有零元56代數(shù)系統(tǒng)<S,*>中，*存在左幺元a和右幺元b，則 A Aa=bBa>

11、bCa<bDab57設(shè)G=0,1,2,3,是G上的二元運(yùn)算：ab=a*b除以4的余數(shù)（*是數(shù)的乘法）。則G不滿(mǎn)足 D A結(jié)合律B交換律C封閉性D冪等律 58K3,3圖共有 C 個(gè)頂點(diǎn)。A3B9C6D27 59通過(guò)圖G里的 C 一次的通路稱(chēng)為歐拉通路。A每條路徑B每個(gè)點(diǎn)C每條邊D每條邊和每個(gè)點(diǎn)60假定某人用手機(jī)向多人發(fā)了同一條短信，而收到這條短信的人可能不再向任何人發(fā)送這條短信，也可能向其他若干人發(fā)了這條短信。試驗(yàn)結(jié)束后發(fā)現(xiàn)共有36人參與了這次游戲，且沒(méi)有人重復(fù)收到同樣的短信。那么共有 B 人收到了這條短信。A18B35C30D22 61符號(hào)“”表示 A 聯(lián)結(jié)詞。A合取B否定C析取D條件6

12、2如果P為真，Q為假，則 B 為真。APQBPQCPDPQ63設(shè)P表示“雪是黑的”，Q表示“我相信你”。則“如果雪是黑的，我就不相信你”可符號(hào)為 C APQBPQCPQDPQ 64在謂詞邏輯中，個(gè)體變項(xiàng)的取值范圍稱(chēng)為 B A作用域B論域C定義域D值域 65一個(gè)公式，如果量詞均在全式的開(kāi)頭，它們的作用域延伸到整個(gè)公式的末尾，則該公式叫做 B A主范式B前束范式C等價(jià)式D蘊(yùn)含式 66下面表達(dá)式中 A 不是謂詞公式。ABCD 67轄域中除去約束出現(xiàn)的其他變項(xiàng)的出現(xiàn)稱(chēng)為 A A自由出現(xiàn)B約束出現(xiàn)C個(gè)體變項(xiàng)D謂詞變項(xiàng) 68由P(c)可得到。這是應(yīng)用了 D 規(guī)則。A全稱(chēng)指定B全稱(chēng)推廣C存在指定D存在推廣6

13、9 1是 B 的真子集。A1B1，2C2，3D3，470設(shè)集合M=1,2，當(dāng)P= B 時(shí)有MP=1,3。A 1B2,3C2D1,2,3 71集合M=a,b與N=c,d,e的笛卡爾積共有 D 個(gè)元素。A3B5C4D6 72設(shè)I、R分別為1,2,3上的恒等關(guān)系、相容關(guān)系，則IR是R的 D 閉包。A對(duì)稱(chēng)閉包B傳遞閉包C等價(jià)關(guān)系D自反閉包 73設(shè)A=1,2,3,R=(1,2),(2,3)是A上的二元關(guān)系，則R2= D A(1,3)B(3,1)C<1,3>D(1,3) 74等價(jià)關(guān)系不是 C A自反的B對(duì)稱(chēng)的C反對(duì)稱(chēng)的D傳遞的75代數(shù)系統(tǒng)由非空集合及其 A 組成。A運(yùn)算B子集C冪集D關(guān)系 76

14、<S,*>是半群，則不需具備的條件是 B A*是二元運(yùn)算B*是可交換的C*是封閉的D*是可結(jié)合的 77設(shè)*是集合M=a,b上的二元運(yùn)算，如下表所示，則 B *abaabbbaAb是*的幺元Ba是*的幺元Ca是*的零元Db是*的零元78假定某人用手機(jī)向多人發(fā)了同一條短信，而收到這條短信的人可能不再向任何人發(fā)送這條短信，也可能向其他若干人發(fā)了這條短信。試驗(yàn)結(jié)束后發(fā)現(xiàn)共有50人參與了這次游戲，且沒(méi)有人重復(fù)收到同樣的短信。那么共有 B 人收到了這條短信。A25B49C36D50 79在含有40個(gè)頂點(diǎn)的完全圖中，其每個(gè)頂點(diǎn)的度均為 CA40B41C39D20 80連通平面圖G有17個(gè)頂點(diǎn)，每

15、個(gè)頂點(diǎn)的度都為4。則G共有 A 個(gè)區(qū)域。A19B17C18D13 填空題81在各種指派下取值均為 假 的命題公式稱(chēng)為永假式。82寫(xiě)出兩個(gè)命題變?cè)狿、Q的所有小項(xiàng)： PQ,PQ,PQ,PQ 。83根據(jù)自由變?cè)?代入 規(guī)則，可得。（代入，換名）84的前束范式為： 。85設(shè)集合A=1,2,3,B=4,5,C=a,b,c,R是集合A到集合B的關(guān)系，S是集合B到的集合C關(guān)系，且R=(1,4),(2,5),(3,4),(3,5)，S=(4,a),(5,b),(5,c)。如果(x,b)是R與S的復(fù)合關(guān)系中的序偶，則x的值為 2或3 。86設(shè)f:RR，f(x)=cosx，則f 不是 入射。（是，不是）87設(shè)*

16、是集合A上的二元運(yùn)算，且在A中有關(guān)于*的左零元a和右零元b，則a與b的等量關(guān)系是： a=b 。（a>b，a=b，a<b）88設(shè)*是集合S上的二元關(guān)系，若*是封閉的、 可結(jié)合的 ，則<S,*>是半群。（可交換的，可結(jié)合的，對(duì)稱(chēng)的）89無(wú)向連通圖存在歐拉回路的充要條件是： 所有結(jié)點(diǎn)的度均是偶數(shù) 。90假定某人用手機(jī)向多人發(fā)了同一條短信，而收到這條短信的人可能不再向任何人發(fā)送這條短信，也可能向其他若干人發(fā)了這條短信。試驗(yàn)結(jié)束后發(fā)現(xiàn)共有20人參與了這次游戲，且沒(méi)有人重復(fù)收到同樣的短信。那么共有 19 人收到了這條短信。91在各種指派下取值均為 假 的命題公式稱(chēng)為矛盾式。92寫(xiě)出

17、兩個(gè)命題變?cè)狿、Q的所有大項(xiàng)： PQ,PQ,PQ,PQ 。93中Q(x,y)中的x是 約束 出現(xiàn)。（約束，自由）94設(shè)個(gè)體域?yàn)?,2，消除中的量詞得： (P(1)P(2)Q(1)Q(2) 。95相容關(guān)系滿(mǎn)足自反性和 對(duì)稱(chēng) 性。（對(duì)稱(chēng)，反對(duì)稱(chēng)，傳遞）96設(shè)(1,2),(2,3)R是A=1,2,3上的偏序，則(1,3) 是 R的元。（不是，是）97<G ,*>是半群，且G的每個(gè)元都有逆元，則當(dāng)存在幺 元時(shí)該半群是群。(幺，零)98環(huán)是含 2 個(gè)二元運(yùn)算的代數(shù)系統(tǒng)。99通過(guò)圖G里的 每個(gè)點(diǎn) 一次的通路稱(chēng)為哈密頓通路。101在各種指派下取值均為 真 的命題公式稱(chēng)為永真式。（真，假）102命

18、題變?cè)狿與Q的任意兩個(gè)不同小項(xiàng)的合取式的真值為 假 。（真，假）103F(x)：x是大于2的偶數(shù)；Q(x)：x能寫(xiě)為兩個(gè)質(zhì)數(shù)的和。則命題“大于2的偶數(shù)能寫(xiě)為兩個(gè)質(zhì)數(shù)的和”可符號(hào)化為： 。104一個(gè)公式，如果量詞均在全式的開(kāi)頭，它們的作用域延伸到整個(gè)公式的末尾，則該公式叫做 前束范式 。（主合取式，前束范式，主析取范式）105滿(mǎn)足傳遞性 的相容關(guān)系是等價(jià)關(guān)系。（傳遞性，對(duì)稱(chēng)性，反對(duì)稱(chēng)性）106設(shè)R為非空集合A上的二元關(guān)系，則RR-1是R的 傳遞 閉包。（自反，傳遞，對(duì)稱(chēng)）107群 一定 是半群。（一定，不一定）108設(shè)<G ,*>是環(huán)，且<G,*>是半群，則 <G,

19、> 是阿貝爾群。109在含有30個(gè)頂點(diǎn)的完全圖中，其每個(gè)頂點(diǎn)的度均為 29 。110連通平面圖G有15個(gè)頂點(diǎn)，每個(gè)頂點(diǎn)的度都為4。則G共有 17 個(gè)區(qū)域。111在各種指派下取值均為 真 的命題公式稱(chēng)為重言式。（真，假）112兩個(gè)命題變?cè)狿與Q的任意兩個(gè)不同大項(xiàng)的析取式的真值為 真 。（真，假）113設(shè)個(gè)體域?yàn)閷?shí)數(shù)集，謂詞F(x)表示x可寫(xiě)成分?jǐn)?shù)；Q(x)表示x是有理數(shù)，則命題“有理數(shù)均可寫(xiě)成分?jǐn)?shù)”可符號(hào)化為： 。114 F(x) 。（F(x)，F(xiàn)(x)）115偏序關(guān)系滿(mǎn)足自反性、 反對(duì)稱(chēng)性 和傳遞性。（反對(duì)稱(chēng)性，對(duì)稱(chēng)性）116設(shè)f:RR，f(x)=2x-1，則f 是 雙射。（不是，是）1

20、17代數(shù)系統(tǒng)<S,*>中，*存在左幺元a和右幺元b，則a與b的大小關(guān)系是 a=b 。118如果<G,*>是環(huán)，則*對(duì)是 可分配的。（不可，可）119通過(guò)圖G里的 每條邊 一次的通路稱(chēng)為歐拉通路。計(jì)算題1利用真值表求公式PQ的主析取范式。P QPPQ0 0100 1111 0011 101解：因?yàn)樗?，PQ的主析取范式的主析取范式為：(PQ)(PQ)(PQ)2設(shè)個(gè)體域?yàn)閍,b。試求消除量詞后的等價(jià)式。解：消除量詞得：P(a)P(b)消除量詞得：Q(a)Q(b) 故消除量詞得：(P(a)P(b)(Q(a)Q(b)3設(shè)R(a,b),(b,c)是集合M=a,b,c上的等價(jià)關(guān)系。

21、求最小關(guān)系R。解：（1）等價(jià)關(guān)系必須滿(mǎn)足自反性，故(a,a),(b,b),(c,c)R；2）等價(jià)關(guān)系必須滿(mǎn)足對(duì)稱(chēng)性，故(b,a),(c,b)R；（3）等價(jià)關(guān)系必須滿(mǎn)足傳遞性，故(a,c)R由于R是最小關(guān)系，故，R=(a,a),(b,b),(c,c),(b,a),(c,b), (a,c) abcdefhgijk4求右圖所示樹(shù)的前序行遍、中序行遍和后序行遍。解：前序行遍：即訪問(wèn)次序?yàn)椋焊?、左子?shù)、右子樹(shù)，故為：ghaibcjdkef；中序行扁次序?yàn)椋鹤笞訕?shù)、根、右子樹(shù)，故有：ahbicgdjekf后序行扁次序?yàn)椋鹤笞訕?shù)、右子樹(shù)、根，故有：abcihdefkjg5求的不含蘊(yùn)含聯(lián)結(jié)詞的前束范式。解：

22、6設(shè)R=(1,2),(2,3)是A=1,2,3上的關(guān)系，求R的逆關(guān)系和傳遞閉包。解：將R中每一序偶的元素順序互換，即得R的逆關(guān)系為(2,1),(3,2) ；R的傳遞閉包是包含R且滿(mǎn)足傳遞性的最小關(guān)系；故R的傳遞閉包為(1,2),(2,3),(1,3) 7假定某人用手機(jī)向多人發(fā)了同一條短信，而收到這條短信的人可能不再向任何人發(fā)送這條短信，也可能向其他若干人發(fā)了這條短信。試驗(yàn)結(jié)束后發(fā)現(xiàn)共有28人參與了這次游戲，且沒(méi)有人重復(fù)收到同樣的短信。那么共有多少人收到了這條短信？解：以人為頂點(diǎn)，某人向另外一人發(fā)送短信就畫(huà)一條有向邊，則以上游戲可得到一棵樹(shù) 樹(shù)的邊數(shù)=頂點(diǎn)數(shù)-1，而該樹(shù)的頂點(diǎn)數(shù)即人數(shù)，為28該樹(shù)

23、的邊數(shù)（也就是收到短信的人數(shù)）為28-1=27。8求公式PQ的主合取范式。解：PQ=PQ PQ是大項(xiàng) PQ就是公式PQ的主合取范式。9求中的自由出現(xiàn)變?cè)图s束出現(xiàn)變?cè)＝猓鹤杂沙霈F(xiàn)的變?cè)校篎(x,y)中的x；G(x,y)中的y。約束出現(xiàn)的變?cè)校篎(x,y)中的y；G(x,y)中的x。10設(shè)R=(a,a),(a,b),(b,c)是A=a,b,c上的關(guān)系，在R中添加最少的序偶，使R成為偏充關(guān)系。解：偏序關(guān)系滿(mǎn)足自反性、反對(duì)稱(chēng)性和傳遞性，故：（1）要滿(mǎn)足自反性，必須添加序偶：(b,b),(c,c) （2）要滿(mǎn)足傳遞性，必須添加序偶：(a,c) （3）R已滿(mǎn)足反對(duì)稱(chēng)性，不必添加或刪除任何序偶。綜上

24、所述，R必須添加的序偶為：(b,b),(c,c),(a,c) 11求公式PQ的主合取范式。解：PQ=PQ PQ是大項(xiàng) PQ就是公式PQ的主合取范式。12設(shè)個(gè)體域?yàn)?,2。求消除量詞后的等價(jià)式。解：原式消除量詞得：(F(1,1)F(1,2)(F(2,1)F(2,2) 13設(shè)R=(1,a),(2,b),(a,2)是A=1,2,a,b上的關(guān)系，求R的對(duì)稱(chēng)閉包和R2。解：R的逆關(guān)系R-1= (a,1),(b,2),(2,a) ，故R的對(duì)稱(chēng)閉包為RR-1=(1,a),(2,b),(a,2), (a,1),(b,2),(2,a) ，R2即R與R的復(fù)合關(guān)系為(1,2),(a,b)，求解過(guò)程如下圖所示。12a

25、b12ab12ab14某公司擬在A、B、C、D、E五個(gè)宿舍區(qū)之間鋪設(shè)光纜。初步方案及預(yù)算如下：A與B：10萬(wàn)元（即A與B之間要鋪設(shè)光纜的預(yù)算為10萬(wàn)元）；A與C：15萬(wàn)元；A與D：13萬(wàn)元；B與C：12萬(wàn)元；B與E：14萬(wàn)元；C與D：15萬(wàn)元；C與E：16萬(wàn)元；D與E：17萬(wàn)元。在確保五個(gè)宿舍區(qū)相互連通的情況下，如何確定方案使總開(kāi)銷(xiāo)最?。緼BCDE1015131215161417解：根據(jù)題意，得初步方案的無(wú)向圖如下：求解本問(wèn)題即求最小生成樹(shù)。方法如下：ABCDE10131214(1)將權(quán)最小的邊加入樹(shù)T中：選擇邊AB；(2)從余下的邊中，將權(quán)最小的邊加入樹(shù)T中，T不能有回路：選擇邊BC；(3)

26、從余下的邊中，將權(quán)最小的邊加入樹(shù)T中，T不能有回路：選擇邊AD；(4)從余下的邊中，將權(quán)最小的邊加入樹(shù)T中，T不能有回路：選擇邊BE；得到最小生成樹(shù)如下：因此，為使總開(kāi)銷(xiāo)最小，必須按如上圖所示的最小生成樹(shù)鋪設(shè)光纜。15集合上的關(guān)系，寫(xiě)出關(guān)系矩陣，畫(huà)出關(guān)系圖并討論R的性質(zhì)。解： R的關(guān)系圖為 R是自反、對(duì)稱(chēng)的。 16求主合取范式解: 17設(shè)A=1，2，3，4，5，A上的偏序關(guān)系為：求A的子集3，4，5和1，2，3，的上界，下界，上確界和下確界。解：3，4，5 ：上界：1，3；上確界：3； 下界：無(wú)；下確界：無(wú)； 1，2，3：上界：1；上確界：1； 下界：4；下確界：4。 18給定解釋I：D=2，

27、3，L（x,y）為L(zhǎng)( 2 , 2 ) = L ( 3 , 3 ) = 1 , L ( 2 , 3 ) = L (3 , 2 )=0 ,求謂詞合式公式的真值。解：19集合S=1，2，3，4，5，找出S上的等價(jià)關(guān)系，此關(guān)系能產(chǎn)生劃分1，2，3，4，5。 解：R1=1,2×1,2=<1,1>,<1,2>,<2,1>,<2,2> R2=3×3=<3,3> R3=4,5×4,5=<4,4>,<4,5>,<5,4>,<5,5> R=R1R2R3=<1,1>

28、,<1,2>,<2,1>,<2,2>,<3,3>,<4,4>,<4,5>,<5,4>,<5,5> 20試構(gòu)造命題公式的真值表。TTFFTFFFFTTTFFTF21用等值演算方法求的主合取范式。解: 22設(shè)，給定上的二元關(guān)系，試求關(guān)系R的自反閉包、對(duì)稱(chēng)閉包和傳遞閉包。解:自反閉包: .2分對(duì)稱(chēng)閉包:.2分 傳遞閉包: 23設(shè)圖,的鄰接矩陣為:,則(1)的入度是多少?(2)的出度是多少?(3)從到長(zhǎng)度為2的路有幾條?解:(1)的入度是 (2) 的出度是 (3)從到長(zhǎng)度為2的路有條。 24設(shè)解釋如下:,試

29、求出下列公式在下的真值.(1)；(2)。解：(1) (2) 25.將公式化為前束范式。 (2)從表中可以看出，公式的真值為F所對(duì)應(yīng)大項(xiàng)編碼為。(3)故與該公式等價(jià)的主合取范式為：26設(shè)函數(shù)，試求出復(fù)合函數(shù)和 解：27試給出右圖的鄰接矩陣，約定圖中結(jié)點(diǎn)標(biāo)記序列為順序。解：證明題1利用推理規(guī)則證明：PQ，QR，R P證明：（1）PQ P （2）QR P （3）PR T(1)(2)I （4）R P （5）P T(3)(4)I2簡(jiǎn)單連通圖G有10個(gè)結(jié)點(diǎn)、25條邊。證明圖G不是平面圖，并求任意兩點(diǎn)間最短路徑的最大長(zhǎng)度。證明：設(shè)簡(jiǎn)單連通圖G有v個(gè)結(jié)點(diǎn)、e條邊。如果G是平面圖，則有：e3v-6 而v=10,

30、e=25。顯然e3v-6不成立。故G不是平面圖。 由定理：任意兩點(diǎn)間必存在長(zhǎng)度不超過(guò)v-1的路徑。故最大長(zhǎng)度為10-1=9。fabcde3如下圖G是一個(gè)無(wú)向簡(jiǎn)單圖，證明該圖存在歐拉路但不存在歐拉回路。并寫(xiě)出一條歐拉路。4證明：無(wú)向圖G具有歐拉路，當(dāng)且僅當(dāng)G連通且有零個(gè)或兩個(gè)奇數(shù)度結(jié)點(diǎn)。而上圖中，G恰有兩個(gè)奇數(shù)度結(jié)點(diǎn)b、d（度均為3），其余結(jié)點(diǎn)的度均為4，且圖G顯然是連通的。所以，圖G存在歐拉路。如：b-c-d-e-f-a-b-e-a-c-f-d就是一條歐拉路。無(wú)向連通圖具有歐拉回路當(dāng)且僅當(dāng)所有結(jié)點(diǎn)的度都是偶數(shù)。而圖G有兩個(gè)奇數(shù)度結(jié)點(diǎn)，所以，G無(wú)歐拉回路。5證明：下面給出的有權(quán)無(wú)向圖的最小生成樹(shù)不唯一。ABCDE15325644證明：根據(jù)題意，可先求其最小生成樹(shù)：(1)將權(quán)最小的邊加入樹(shù)T中：選擇邊AB(2)從余下的邊中，將權(quán)最小的邊加入樹(shù)T中，T不能有回路：選擇邊BC(3)從余下的邊中，將權(quán)最小的邊加入樹(shù)T中，T不能有回路：選擇邊ADABCDE1324ABCDE1324(4)從余下的邊中，