華南理工網(wǎng)絡教育2018年離散數(shù)學大作業(yè)參考答案

1、華南理工大學網(wǎng)絡教育學院20182019 學年度第一學期離散數(shù)學作業(yè)、用推理規(guī)則證明（PQ），Q R，RP1QR證（1）P（2）RP（3）QQ）（ 1）（2）析取三段論（ ）（PP4Q（ ）P（ ）等價轉(zhuǎn)換54（6）P（3）（5）析取三段論2、用推理規(guī)則證明Q，PR， PS ，SQ R證（1）PSP（2）SP（3）P（ ）（ ）拒取式PR12（4）RP（5）（ ）（ ）假言推理34（6）QRP（7）Q（ ）（ ）合取56設命題公式為Q（ PQ）P。3（1）求此命題公式的真值表；（2）求此命題公式的析取范式；（3）判斷該命題公式的類型。解 （1）真值表如下PQQ P QQ （ PQ）PQ （PQ

2、）P0011111010101110100011101001（ ）Q （PQ）P（Q （P Q）P2（ Q（PQ）P（ PQ）（ QP）1（析取范式）（ PQ）（P Q）（ PQ）（ PQ）（主析取范式）（ 3）該公式為重言式4在一階邏輯中構造下面推理的證明每個喜歡步行的人都不喜歡坐汽車。每個人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車。因而有的人不喜歡步行。令 F(x) ：x 喜歡步行。 G(x) ： x 喜歡坐汽車。 H(x) ：x 喜歡騎自行車。解前提：x（F（x）G（x），x（G（x）H（x），x H （x）。結論：xF（x）。證 (1)xH（x）P(2)H（c）ES(1)(

3、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)（$5用直接證法證明：前提：（ x）（C（x） W（x） R（ x），（$x）（ C（ x） Q（x）結論：（$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)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）

4、T(6)I(8)QT(2)I（ c）(9)Q （ c） R（ c）T(7,8)I(10) （$x）（Q（x） R（ x）EG(9)6設 R 是集合 A = 1, 2, 3, 4, 5, 6, 7, 8, 9上的整除關系。（1） 給出關系 R；（ 2）畫出關系 R 的哈斯圖；（3）指出關系 R的最大、最小元，極大、極小元。解 R=, ，, ， ， ， ， I ACOVA=,， ， ，作哈斯圖如右：極小元和最小元為1；極大元為 5,6,7,8,9,無最大元8694235717設 R 是集合 A = 1, 2, 3, 4, 6, 12上的整除關系。(1) 給出關系 R；（2） 給出 COVA（3）

5、畫出關系 R的哈斯圖；（4） 給出關系 R的極大、極小元、最大、最小元。解R，,，=, ， , I A，ACOV =,12作哈斯圖如右：極小元和最小元為 1；46極大元和最大元為 12238求帶權圖 G的最小生成樹，并計算它的權值。1231解C T1231719給定權為 1， 9， 4， 7， 3；構造一顆最優(yōu)二叉樹。解 1 3 4792444 7 915879915982474413W T 4 1 4 3 3 4 2 7 1 9 5110給定權為 2，6，3，9，4；構造一顆最優(yōu)二叉樹。解 2 3 4 6 92454 6 91596999159546243W T 4 (2 3) 3 4 2

6、6 9 532或 2 3 4 6 92454 6 91599155 6492423W T3(2 3) 242 (6 9) 5311、設字母 a,b,c, d , e, f在通訊中出現(xiàn)的頻率為： a :30%, b : 25%, c : 20% ，d :10%, e:10%, f :5%。試給出傳輸這 6 個字母的最佳前綴碼？問傳輸1000 個字符需要多少位二進制位？解先求傳輸 100 個字符所需要的位數(shù)。 a :30, b : 25, c : 20, d :10, e :10, f :5 是依照出現(xiàn)頻率得出的個數(shù)。構造最優(yōu)二叉樹如下：51010 202530100151020 253045252