離散數(shù)學(xué)作業(yè)

1、（ 密 封 線 內(nèi) 不 答 題 ） 教學(xué)中心： 專(zhuān)業(yè)層次： 姓名： 學(xué)號(hào)： 座號(hào)： 華南理工大學(xué)網(wǎng)絡(luò)教育學(xué)院 教學(xué)中心： 專(zhuān)業(yè)層次： 姓名： 學(xué)號(hào)： 座號(hào)： 20142015學(xué)年度第一學(xué)期 離散數(shù)學(xué) 作業(yè)（解答必須手寫(xiě)體上傳，否則酌情扣分）1設(shè)命題公式為 Q （P Q） P。 （1）求此命題公式的真值表；答：解 （1） 真值表如下PQQPQ Q （P Q） P Q （P Q） P0011111010101110100011101001（2）求此命題公式的析取范式；答：（ Q （P Q） P Q（P Q） P QP Q P P Q Q P P 1 P P P 11（PQ）（PQ）（PQ）（PQ）

2、（主析取范式）（3）判斷該命題公式的類(lèi)型。答：該命題公式重言式2用直接證法證明 前提：P Q，P R，Q S結(jié)論：S R證 (1)P Q P (2) P Q T(1)E(3) Q S P (4) P S T(2,3)I (5) S P T(4)E(6) P R P (7) S R T(5,6)I (8) SR T(7)E3在一階邏輯中構(gòu)造下面推理的證明 每個(gè)喜歡步行的人都不喜歡坐汽車(chē)。每個(gè)人或者喜歡坐汽車(chē)或者喜歡騎自行車(chē)。有的人不喜歡騎自行車(chē)。因而有的人不喜歡步行。令F(x)：x喜歡步行。G(x)：x喜歡坐汽車(chē)。H(x)：x喜歡騎自行車(chē)。解 前提：x（F（x） G（x），x（G（x）H（x），

3、$ x H（x）。結(jié)論：$ x F（x）。證 (1)$ x H（x） P (2)H（c） ES (1)(3)x（G（x）H（x） P (4) G（c）H（c） US(3) (5) G（c） T(2，4)I(6)x（F（x） G（x） P (7) F（c） G（c） US(6) (8) F（c） T(5,7)I (9)（$x） F（x） EG(8)4用直接證法證明：前提：（x）（C（x） W（x）R（x），（$x）（C（x）Q（x）結(jié)論：（$x）（Q（x）R（x）。證 (1)（$x）（C（x）Q（x） P (2)C（c）Q（c） ES (1)(3)（x）（C（x） W（x）R（x） P (4)

4、C（c） W（c）R（c） US(3) (5) C（c） T(2)I(6)W（c）R（c） T(4,5)I (7)R（c） T(6)I (8)Q（c） T(2)I (9)Q（c）R（c） T(7,8)I (10) （$x）（Q（x）R（x） EG(9)5設(shè)R是集合A = 1, 2, 3, 4, 6, 12上的整除關(guān)系。(1) 給出關(guān)系R；（2） 給出COV A（3） 畫(huà)出關(guān)系R的哈斯圖；（4） 給出關(guān)系R的極大、極小元、最大、最小元。解 R=,，,，,IACOV A=,，作哈斯圖如右：極小元和最小元為1；極大元和最大元為12 6求帶權(quán)圖G的最小生成樹(shù)，并計(jì)算它的權(quán)值。 答：C（T）=1+2+3

5、+1=77給定權(quán)為1，9，4，7，3；構(gòu)造一顆最優(yōu)二叉樹(shù)。 答： 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24W（T）=41+43+34+27+19=518給定權(quán)為2，6，3，9，4；構(gòu)造一顆最優(yōu)二叉樹(shù)。解 2 3 4 6 9 5 4 6 9 9 6 9 15 924W(T)=4(23)+34+26+9=53或 2 3 4 6 9 5 4 6 9 9 15 24W(T)=3(2+3)+24+2(6+9)=539、給定權(quán)為2，6，5，9，4，1；構(gòu)造一顆最優(yōu)二叉樹(shù)。 解 1 2 4 5 6 9 3 4 5 6 9 7 5 6 9 7 11 9 11 16 27W(T)=41+42+34+29+25+26=6410、設(shè)字母在通訊中出現(xiàn)的頻率為：，。試給出傳輸這6個(gè)字母的最佳前綴碼？問(wèn)傳輸1000個(gè)字符需要多少位二進(jìn)制位？解 先求傳輸100個(gè)字符所需要的位數(shù)。A:30,b:25,c:20,d:10,e:10,f:5是依照出現(xiàn)頻率得出的個(gè)數(shù)。構(gòu)造最優(yōu)二叉樹(shù)如下：5 10 10 20 25 30 15 10