計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)（1）07秋綜合練習(xí)（三）_計(jì)算機(jī)_期末大練兵__電大在線

1、計(jì)算機(jī)數(shù)學(xué)基礎(chǔ)（1）07秋綜合練習(xí)（三） 三、化簡(jiǎn)計(jì)算題 1作命題公式的真值表，并判斷該公式的類型解：命題公式的真值表PQP®Q001000011000100011111111 原式為可滿足式. 2判斷命題公式的類型(重言式、矛盾式或可滿足式)解： 所以是矛盾式(永假式) 3設(shè)謂詞公式，試寫出量詞的轄域，并指出該公式的自由變?cè)图s束變?cè)猓?x的轄域是：P(x,y)®"zQ(y,x,z)；"z的轄域是：Q(y,x,z)； "y的轄域是：R(y,x) 公式的自由變?cè)牵簓,z；約束變?cè)牵簒,y,z 4 化簡(jiǎn)集合表達(dá)式：(AÈB

2、0;C)Ç(AÈB)(BÈ(BC)A) 解： (AÈBÈC)Ç(AÈB)(BÈ(BC)A)(AÈB)(BA) (3分) =(AÈB)Ç(BÈA) (5分) =AÈ(BÇB)=AÈÆ=A 5設(shè)集合Aa,b,c,d，在A上定義二元關(guān)系R<a,a>,<a,d>,<b,b>,<b,c>,<c,b>,<c,c>,<d,a>,<d,d>R是否為等價(jià)關(guān)系，

3、說明理由. 解： R含有<a,a>,<b,b>,<c,c>,<d,d>, 是自反的； R含有<a,a>,<b,b>,<c,c>,<d,d>,<a,d>,<d,a>,<b,c>,<c,b>, 是對(duì)稱的；可以驗(yàn)證，對(duì)，是傳遞的. 故R是A上的等價(jià)關(guān)系. ab c f d e<A,R>的哈斯圖 6：偏序集<A, R>的哈斯圖如下圖所示： 試寫出A和R的集合表達(dá)式并求A的極大元和最大元解：A=a,b,c,d,e,f(2分) R=<

4、b,a>,<d,b>,<d,a>,<d,c>,<c,a>, <e,c>,<e,a>ÈIA (5分) A的極大元：a,f；最大元：無v5 d v4v1v2 v3圖Ge f n ca h g b7圖G(如下圖)能否一筆畫出？說明理由. 若能畫出，請(qǐng)寫出一條通路或回路. 解：因?yàn)閳D中 (v1)=2, (v2)=(v3)=(v4)=(v5)=4,無奇數(shù)度結(jié)點(diǎn)，圖G是歐拉圖，故能一筆畫出. 一條歐拉回路為：v5e v1a v2hv4c v3g v5f v2b v3n v4d v5 (不惟一) 8指出有向圖D中各圖是強(qiáng)

5、連通，單側(cè)連通還是弱連通？(1)(2)(3)(4)(5)圖D解：強(qiáng)連通圖為：圖(1),(4),(5)；單側(cè)連通圖為：圖(2),(4),(5)，或圖(2)；弱連通圖為：圖(3),(2),(4),(5)，或圖(3) 9給定三個(gè)圖如下圖所示，試判斷它們是否為歐拉圖、哈密頓圖、或平面圖？并說明理由 a b c d e f g 圖G1 圖G2 圖G3 解： 圖G1是歐拉圖，因?yàn)槊總€(gè)結(jié)點(diǎn)度數(shù)均為偶數(shù) 圖G2是哈密頓圖，存在哈密頓回路，如cdgfebac(不惟一) 圖G3是平面圖可以改畫成可平面圖，如下圖 平面圖 10(1)在1棵有2個(gè)2度結(jié)點(diǎn)，4個(gè)3度結(jié)點(diǎn)，其余為樹葉的無向圖中，應(yīng)該有幾片樹葉？(2) 畫

6、出兩棵不同構(gòu)的滿足條件(1)的結(jié)點(diǎn)度數(shù)的無向樹T1，T2解：(1)設(shè)有k片樹葉，則該樹有k+2+4個(gè)結(jié)點(diǎn)，根據(jù)樹的等價(jià)定義，有k+5條邊由握手定理，2×(k+5)=k+2×2+4×3k+16,故k=6即有6片樹葉 (2) 非同構(gòu)的樹如下圖 T1 T2 兩個(gè)非同構(gòu)樹圖 11設(shè)代數(shù)系統(tǒng)(Z，+，×)，已知(Z，×)是半群，驗(yàn)證(Z，+，×)是環(huán)解：只需驗(yàn)證(Z，+)是交換群易驗(yàn)證整數(shù)具有結(jié)合律，交換律0是加法的單位元"kÎZ，$(k)ÎZ，有k+(k)=(k)+k=0Z中每個(gè)元素有逆元故(Z,+)是交換群所以

7、(Z,+,×)是環(huán) 12化簡(jiǎn)布爾表達(dá)式. 解： 13求命題公式的主合取范式. 解： 14求命題公式的真值表. 解：作真值表P Q PÙQØPØQØPÚØQ(PÙQ)Ù(ØPÚØQ)00 0 1 1 1 001 0 1 0 1 010 0 0 1 1 011 1 0 0 0 0 15求謂詞公式的真值其中P：4>3，Q（x）：x>1，R（x）：x£2f（-3）=1，f（1）=5，f（5）= -3a：5個(gè)體域D=（-3，1，5）解：= = 16求謂詞公式的前束

8、范式解： (2分) (4分) (6分) (8分) (或) 17設(shè)，求：(AÇB)ÈC，P(A)P(B)，AÅB解：(AÇB)ÈC=1È AÅB =(AÈB)（AÇB）= 18設(shè)集合Xa,b,c,d,X上的二元關(guān)系R的關(guān)系圖如下圖所示ah hdbh hcR的關(guān)系圖試寫出R的表達(dá)式和關(guān)系矩陣 解：R<a,a>,<a,c>,<b,c>,<d,d> 19設(shè)偏序集<A,R>的哈斯圖如下：4 62 35 1 <A,R>哈斯圖求偏序關(guān)系R的集合表達(dá)

9、式和A的子集合B=2,3,6的極大元、極小元、最大元和最小元解：R=IAÈ<1,2>,<2,4>,<1,4>,<2,6>,<1,6>,<1,3>,<3,6>B的極大元和最大元：為6；極小元為2,3；最小元：無v4 h h v3v1 h h v2 圖D 20已知有向圖D(如下圖)的鄰接矩陣為 A(D)=求從v2到v4長(zhǎng)度為2和從v3到v3長(zhǎng)度為2的通路條數(shù)，并將它們具體寫出.解答：. A2(D)= 從矩陣A2(D)中a24=2,a33=2可知， 從v2到v4長(zhǎng)度為2的通路有2條. 它們是：v2v3v4,

10、和v2v1v4, 從v3到v3長(zhǎng)度為2的通路有2條. 它們是：v3v4v3,和v3v2v3, 21設(shè)簡(jiǎn)單連通無向圖G有12條邊，G中有2個(gè)1度結(jié)點(diǎn)，2個(gè)2度結(jié)點(diǎn)，3個(gè)4度結(jié)點(diǎn)，其余結(jié)點(diǎn)度數(shù)為3求G中有多少個(gè)結(jié)點(diǎn)試作一個(gè)滿足該條件的簡(jiǎn)單無向圖解：設(shè)圖G有x個(gè)結(jié)點(diǎn)，有握手定理 2´1+2´2+3´4+3´（x-2-2-3）12´2 x9圖G有9個(gè)結(jié)點(diǎn) 簡(jiǎn)單無向圖作圖如下圖 22設(shè)無向圖G如下圖，說明圖G是哈密頓圖，并求一條哈密頓回路 e f無向圖Gc dab解：這是6階圖，每個(gè)結(jié)點(diǎn)的度數(shù)為3，任意不相鄰結(jié)點(diǎn)度數(shù)之和大于或等6，故圖G是哈密頓圖一條哈密頓回路為：acebfda 23已知帶權(quán)圖G，如下圖所示試求圖G的最小生成樹，并計(jì)算該生成樹的權(quán) · 1 9 2· 8 · 7 · 4 · 3 · 圖G5 610解：做法如下：選邊1； 選邊2；選邊3； 選邊5； 選邊7 · 1 9 2· 8 ·