【正文】 式為： P Q． 3．將 語句“他是學(xué)生 ． ”翻譯成命題公式 ． 設(shè) P：他是學(xué)生， 則命題公式為： P． 4． 將 語句“如果明天不下雨，我們就去郊游 ． ”翻譯成命題公式 ． 設(shè) P：明天下雨， Q：我們就去郊游， 則命題公式為： ? P? Q． 5．將 語句“他不去學(xué)校 ． ”翻譯成命題公式 ． 設(shè) P：他去學(xué)校， ? P． 6． 將 語句“他去旅游，僅當(dāng)他有時間 ． ”翻譯成命題公式 ． 設(shè) P：他去旅游， Q：他有時間， P ?Q． 7． 將 語句“所有的人都學(xué)習(xí)努力 ． ”翻譯成命題公式 ． 設(shè) P(x)： x 是人， Q(x)： x 學(xué)習(xí)努力， （ ?x） (P(x)?Q(x))． 8．將 語句“如果你去了，那么他就不去 ． ”翻譯成命題公式 ． 設(shè) P：你去， Q：他去， P??Q． 9． 將 語句“小 王去旅游，小李也去旅游 ． ”翻譯成命題公式 ． 設(shè) P：小王去旅游， Q：小李去旅游， P?Q． 10． 將 語句“所有人都去工作 ． ”翻譯成謂詞公式 ． 設(shè) P(x)： x 是人， Q(x)： x 去工作， (?x)(P(x)?Q(x))． 11． 將 語句“如果所有人今天都去參加活動，則明天的會議取消 ． ”翻譯成命題公式 ． 設(shè) P：所有人今天都去參加活動， Q：明天的會議取消， P? Q． 12． 將 語句“今天沒有人來 ． ” 翻譯成命題公式 ． 設(shè) P：今天有人來， ? P． 13． 將 語句“有人去上課 ． ” 翻譯成謂 詞公式 ． 設(shè) P(x)： x 是人， Q(x)： x 去上課， (?x)(P(x) ?Q(x))． 1 1. 將語句 如果小李學(xué)習(xí)努力，那么他就會取得好成績 . 翻譯成命題公式 . 設(shè) P：小李學(xué)習(xí)努力， Q:小李會取得好成績， P→ Q 12. 將語句 小張學(xué)習(xí)努力 ,小王取得好成績 . 翻譯成命題公式 . 設(shè) P：小張學(xué)習(xí)努力， Q:小王取得好成績， P∧ Q 四、判斷說明題 1．設(shè)集合 A={1， 2}， B={3， 4}，從 A 到 B 的關(guān)系為 f={1, 3}，則 f 是 A 到 B 的函數(shù)． 錯誤． 因?yàn)?A 中元素 2 沒有 B 中元素與之對應(yīng)，故 f 不是 A 到 B 的函數(shù)． 2．設(shè) G 是一個有 4 個結(jié)點(diǎn) 10 條邊的連通圖，則 G 為平面圖． 錯誤． 不滿足“設(shè) G 是一個有 v 個結(jié)點(diǎn) e 條邊的連通簡單平面圖，若 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） ． 錯誤． （ 2）應(yīng)為 F（ y）→ G（ x） ，換名時，約束變元與自由變元不能混淆． 5．如圖二所示的圖 G 存在一條歐拉回路． 圖二 錯誤． 因?yàn)閳D G 為中包含度數(shù)為奇數(shù)的結(jié)點(diǎn)． 6．設(shè) G 是一個有 6 個結(jié)點(diǎn) 14 條邊的連通圖，則 G 為平面圖． 錯誤． 不滿足“設(shè) G 是一個有 v 個結(jié)點(diǎn) e 條邊的連通簡單平面圖，若 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 為連通的，且其中每個頂點(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)為真，則整個公式為真． 可以看到，不論 P 的值為真或?yàn)榧伲?P∧（ P→┐ Q）與 P 總有一個為真， 所以┐ P∧（ P→┐ Q）∨ P 是永真式． 或用等價演算┐ P∧（ P→┐ Q）∨ P?T 10．若偏序集 A， R的哈斯圖如圖一所示，則集合 A 的最大元為 a，最小元不存在． 圖一 v1 v2 v3 v5 v4 d b a c e f g h n 圖 二 5 / 11 正確． 對于集合 A 的任意元素 x，均有 x, a?R（或 xRa），所以 a 是集合 A 中的最大元．按照最小元的定義，在集合 A 中不存在最小元． 11. 如果 R1 和 R2是 A 上的自反關(guān)系， 則 R1∩ R2 是自反的。 正確， R1和 R2，是自反 的， ?x∈ A,x,x∈ R1,x,x∈ R2,則 x,x ∈ R1∩ R2，所以 R1∩ R2是自反的 . 12. 如圖二所示的圖中存在一條歐拉回路 . 圖二 正確，因?yàn)閳D G 為連通的，且其中每個頂點(diǎn)的度數(shù)為偶數(shù)。 五．計算題（每小題 12 分，本題共 36 分） 1．試求出（ P∨ Q）→（ R∨ Q）的析取范式． （ P∨ Q）→（ R∨ Q） ? ┐ (P∨ Q)∨（ R∨ Q） ? (┐ P∧┐ Q)∨（ R∨ Q） ? (┐ P∧┐ Q)∨ R∨ Q（析取范式） 2．設(shè) A={{1}, 1, 2}， B={ 1, {2}}，試計算（ 1）（ A∩ B） （ 2）（ A∪ B） （ 3） A ?（ A∩ B）． （ 1）（ A∩ B） ={1} （ 2）（ A∪ B） ={1, 2, {1}, {2}} （ 3） A?（ A∩ B） ={{1}, 1, 2} 3．圖 G=V, E，其中 V={ a, b, c, d }， E={ (a, b), (a, c) , (a, d), (b, c), (b, d), (c, d)}，對應(yīng)邊的權(quán)值依次為 4 及 5，試 （ 1）畫出 G 的圖形； （ 2）寫出 G 的鄰接矩陣； （ 3）求出 G 權(quán)最小的生成樹及其權(quán)值． （ 1） G 的圖形表示如圖一所示： （ 2）鄰接矩陣：????????????0111101111011110 （ 3）最小的生成樹如圖二中的粗線所示： 權(quán)為： 1+1+3=5 4． 畫一棵帶權(quán)為 1, 2, 2, 3, 4 的 最優(yōu)二叉樹 ,計算它們的權(quán) ． 最優(yōu)二叉樹 如圖三所示 圖三 圖二 ? ? ? ? a b c d 1 1 2 4 5 3 圖一 ? ? ? ? a b c d 1 1 2 4 5 3 ? ? ? ? ? ? ? ? ? 1 2 2 3 3 4 7 5 12 6 / 11 權(quán)為 1?3+2?3+2?2+3?2+4?2=27 5． 求（ P∨ Q）→ R 的析取范式與合取范式． （ P∨ Q）→ R ? ?（ P∨ Q）∨ R ? (?P∧ ?Q)∨ R （析取范式） ? (?P∨ R)∧ (?Q∨ R) （合取范式） 6．設(shè) A={0， 1， 2， 3}， R={x， y|x?A， y?A 且 x+y0}， S={x， y|x?A， y?A 且 x+y?2}，試求 R， S， R?S， S 1， r(R)． R=?, S={0,0,0,1,0,2,1,0,1,1,2,0} R?S=?， S 1= S， r(R)=IA={0,0,1,1,2,2,3,3}． 7．試求出（ P∨ Q）→ R 的析取范式，合取范式，主合取范式． （ P∨ Q）→ R?┐ (P∨ Q)∨ R? (┐ P∧┐ Q)∨ R（析取范式） ? (┐ P∨ R)∧ (┐ Q∨ R)（合取范式） ? ((┐ P∨ R)∨ (Q∧┐ Q))∧ ((┐ Q∨ R)∨ (P∧┐ P)) ? (┐ P∨ R∨ Q)∧ (