【正文】 R（析取范式） ? (┐ P∨ R)∧ (┐ Q∨ R)（合取范式） ? ((┐ P∨ R)∨ (Q∧┐ Q))∧ ((┐ Q∨ R)∨ (P∧┐ P)) ? (┐ P∨ R∨ Q)∧ (┐ P∨ R∨┐ Q)∧ (┐ Q∨ R∨ P) ∧ (┐ Q∨ R∨┐ P) ? (┐ P∨ Q∨ R)∧ (┐ P∨┐ Q∨ R)∧ (P∨┐ Q∨ R) 8．設(shè) A={{a, b}, 1, 2}， B={ a, b, {1}, 1}，試計(jì)算 （ 1）（ A?B） （ 2）（ A∪ B） （ 3） （ A∪ B） ?（ A∩ B） ． （ 1）（ A?B） ={{a, b}, 2} （ 2）（ A∪ B） ={{a, b}, 1, 2, a, b, {1}} （ 3）（ A∪ B） ?（ A∩ B） ={{a, b}, 2, a, b, {1}} 9．圖 G=V, E，其中 V={ a, b, c, d, e}， E={ (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) }，對(duì)應(yīng)邊的權(quán)值依次為 4 及 5，試 （ 1）畫出 G 的圖形； （ 2）寫出 G 的鄰接矩陣； （ 3）求出 G 權(quán)最小的生成樹及其權(quán)值． （ 1） G 的圖形表示為： （ 2）鄰接矩陣： ????????????????0111110110110011100110110 （ 3）粗線表示最小的生成樹， 7 / 11 權(quán)為 7： 10．設(shè)謂詞公式 )(),()),(),(( yFzyyRzxyzQyxPx ?????? ，試（ 1）寫出量詞的轄域； （ 2）指出該公式的自由變?cè)图s束變?cè)? （ 1） ?x 量詞的轄域?yàn)?)),(),(( zxyzQyxP ?? ， ?z 量詞的轄域?yàn)?),( zxyQ , ?y 量詞的轄域?yàn)?),( zyR ． （ 2）自由變?cè)獮?)),(),(( zxyzQyxP ?? 與 )yF 中的 y，以及 ),( zyR 中的 z 約束變?cè)獮?x 與 ),( zxyQ 中的 z，以及 ),( zyR 中的 y． 11．設(shè) A={{1},{2},1,2}， B={1,2,{1,2}}，試計(jì)算 （ 1）（ A?B）； （ 2）（ A∩ B）； （ 3） A B． （ 1） A?B ={{1},{2}} （ 2） A∩ B ={1,2} （ 3） AB={{1},1， {1},2， {1},{1,2}， {2},1， {2},2， {2},{1,2}， 1,1， 1,2， 1, {1,2}， 2,1， 2,2, 2, {1,2}} 12．設(shè) G=V， E， V={ v1， v2， v3， v4， v5}， E={ (v1,v3)， (v2,v3)， (v2,v4)， (v3,v4)， (v3,v5)， (v4,v5) }，試 （ 1）給出 G 的圖形表示； （ 2）寫出其鄰接矩陣； （ 3）求出每個(gè)結(jié)點(diǎn)的度數(shù)； （ 4）畫出其補(bǔ)圖 的圖形． （ 1） G 的圖形表示為： （ 2）鄰接矩陣： ????????????????0110010110110110110000100 （ 3） v1， v2， v3， v4， v5 結(jié)點(diǎn)的度數(shù)依次為 1， 2， 4， 3， 2 （ 4）補(bǔ)圖如下： 8 / 11 13．設(shè)集合 A={1， 2， 3， 4}， R={x, y|x, y?A； |x?y|=1 或 x?y=0}，試 （ 1）寫出 R 的有序?qū)Ρ硎荆? （ 2）畫出 R 的關(guān)系圖； （ 3）說明 R 滿足自反性，不滿足傳遞性． （ 1） R={1,1,2,2,3,3,4,4,1,2,2,1,2,3,3,2,3,4,4,3} （ 2）關(guān)系圖為 3）因?yàn)?1,1,2,2,3,3,4,4均屬于 R，即 A 的每個(gè)元素構(gòu)成的有序?qū)?R 中，故 R 在 A 上是自反的。 解 從 R 的表達(dá)式知， ,),(, RxxAx ??? 即 R具有自反性； 三、邏輯公式翻譯 1．將語(yǔ)句 “今天上課． ”翻譯成命題公式． 設(shè) P：今天上課， 則命題公式為： P． 2．將語(yǔ)句 “他去操場(chǎng)鍛煉，僅當(dāng)他有時(shí)間． ”翻譯成命題公式． 設(shè) P：他去操場(chǎng)鍛煉， Q：他有時(shí)間， 則命題公式為： P Q． 3．將 語(yǔ)句“他是學(xué)生 ． ”翻譯成命題公式 ． 設(shè) P：他是學(xué)生， 則命題公式為： P． 4． 將 語(yǔ)句“如果明天不下雨，我們就去郊游 ． ”翻譯成命題公式 ． 設(shè) P：明天下雨， Q：我們就去郊游， 則命題公式為： ? P? Q． 5．將 語(yǔ)句“他不去學(xué)校 ． ”翻譯成命題公式 ． 設(shè) P：他去學(xué)校， ? P． 6． 將 語(yǔ)句“他去旅游，僅當(dāng)他有時(shí)間 ． ”翻譯成命題公式 ． 設(shè) P：他去旅游， Q：他有時(shí)間， P ?Q． 7． 將 語(yǔ)句“所有的人都學(xué)習(xí)努力 ． ”翻譯成命題公式 ． 設(shè) P(x)： x 是人， Q(x)： x 學(xué)習(xí)努力， （ ?x） (P(x)?Q(x))． 8．將 語(yǔ)句“如果你去了，那么他就不去 ． ”翻譯成命題公式 ． 設(shè) P：你去， Q：他去， P??Q． 9． 將 語(yǔ)句“小 王去旅游，小李也去旅游 ． ”翻譯成命題公式 ． 設(shè) P：小王去旅游， Q：小李去旅游， P?Q． 10． 將 語(yǔ)句“所有人都去工作 ． ”翻譯成謂詞公式 ． 設(shè) P(x)： x 是人， Q(x)： x 去工作， (?x)(P(x)?Q(x))． 11． 將 語(yǔ)句“如果所有人今天都去參加活動(dòng)，則明天的會(huì)議取消 ． ”翻譯成命題公式 ． 設(shè) P：所有人今天都去參加活動(dòng)， Q：明天的會(huì)議取消， P? Q． 12． 將 語(yǔ)句“今天沒有人來 ． ” 翻譯成命題公式 ． 設(shè) P：今天有人來， ? P． 13． 將 語(yǔ)句“有人去上課 ． ” 翻譯成謂 詞公式 ． 設(shè) P(x)： x 是人， Q(x)： x 去上課， (?x)(P(x) ?Q(x))． 1 1. 將語(yǔ)句 如果小李學(xué)習(xí)努力，那么他就會(huì)取得好成績(jī) . 翻譯成命題公式 . 設(shè) P：小李學(xué)習(xí)努力， Q:小李會(huì)取得好成績(jī)， P→ Q 12. 將語(yǔ)句 小張學(xué)習(xí)努力 ,小王取得好成績(jī) . 翻譯成命題公式 . 設(shè) P：小張學(xué)習(xí)努力， Q:小王取得好成績(jī)， P∧ Q 四、判斷說明題 1．設(shè)集合 A={1， 2}， B={3， 4}，從 A 到 B 的關(guān)系為 f={1, 3}，則 f 是 A 到 B 的函數(shù)． 錯(cuò)誤． 因?yàn)?A 中元素 2 沒有 B 中元素與之對(duì)應(yīng)，故 f 不是 A 到 B 的函數(shù)． 2．設(shè) G 是一個(gè)有 4 個(gè)結(jié)點(diǎn) 10 條邊的連通圖，則 G 為平面圖． 錯(cuò)誤． 不滿足“設(shè) G 是一個(gè)有 v 個(gè)結(jié)點(diǎn) e 條邊的連通簡(jiǎn)單平面圖，若 v≥ 3，則 e≤ 3v6．” 4 / 11 3．設(shè) N、 R 分別為自然數(shù)集與實(shí)數(shù)集， f： N→ R， f (x)=x+6，則 f 是單射． 正確． 設(shè) x1， x2 為自然數(shù)且 x1?x2，則有 f(x1)= x1+6? x2+6= f(x2)，故 f 為單射． 4． 下面的推理是否正確，試予以說明 ． (1) （ ?x） F（ x）→ G（ x） 前提引入 (2) F（ y） → G（ y） US（ 1） ． 錯(cuò)誤． （ 2）應(yīng)為 F（ y）→ G（ x） ，換名時(shí)，約束變?cè)c自由變?cè)荒芑煜? 5．如圖二所示的圖 G 存在一條歐拉回路． 圖二 錯(cuò)誤． 因?yàn)閳D G 為中包含度數(shù)為奇數(shù)的結(jié)點(diǎn)． 6．設(shè) G 是一個(gè)有 6 個(gè)結(jié)點(diǎn) 14 條邊的連通圖，則 G 為平面圖． 錯(cuò)誤． 不滿足“設(shè) G 是一個(gè)有 v 個(gè)結(jié)點(diǎn) e 條邊的連通簡(jiǎn)單平面圖，若 v≥ 3，則 e≤ 3v6．” 7．如果 R1 和 R2是 A 上的自反關(guān)系，則 R1∪ R2是自反的． 正確． R1 和 R2 是自反的， ?x ?A， x, x ? R1， x, x ?R2，則 x, x ? R1?R2，所以 R1∪ R2 是自反的． 8．如圖二所示的圖 G 存在一條歐拉回路． 正確． 因?yàn)閳D G 為連通的，且其中每個(gè)頂點(diǎn)的度數(shù)為偶數(shù)． 9．┐ P∧（ P→┐ Q）∨ P 為永真式． 正確． ┐ P∧（ P→┐ Q）∨ P 是由┐ P∧（ P→┐ Q）與 P 組成的析取式， 如果 P 的值為真，則┐ P∧（ P→┐ Q）∨ P 為真， 如果 P 的值為假，則┐ P 與 P→┐ Q 為真，即┐ P∧（ P→┐ Q）為真， 也即┐ P∧（ P→┐ Q）∨ P 為真， 所以┐ P∧（ P→┐ Q）∨ P 是永真式． 另種說明： ┐ P∧（ P→┐ Q）∨ P 是由┐ P∧（ P→┐ Q）與 P 組成的析取式， 只要其中一項(xiàng)為真，則整個(gè)公式為真． 可以看到，不論 P 的值為真或?yàn)榧?，?P∧（ P→┐ Q）與 P 總有一個(gè)為真， 所以┐ P∧（ P→┐