華南理工大學(xué)網(wǎng)絡(luò)教育學(xué)院–第一學(xué)期離散數(shù)學(xué)作業(yè)

1、（ 密 封 線 內(nèi) 不 答 題 ） 教學(xué)中心： 專業(yè)層次： 姓名： 學(xué)號(hào)： 座號(hào)： 華南理工大學(xué)網(wǎng)絡(luò)教育學(xué)院 教學(xué)中心： 專業(yè)層次： 姓名： 學(xué)號(hào)： 座號(hào)： 20192020學(xué)年度第一學(xué)期 離散數(shù)學(xué) 作業(yè)1、 用推理規(guī)則證明 Q，Ø解 P ® R， P ® S，Ø S Q ÙR證 （1）ØQ ÚR P （2）Ø R P （3）Ø Q （1）（2）析取三段論 （4）Ø（PÙ ØQ） P （5）ØP Ú Q （4）等價(jià)轉(zhuǎn)換 （6）Ø P （3）（5）

2、析取三段論2、用推理規(guī)則證明 Ø（PÙ ØQ），ØQ ÚR，Ø RØP證 （1）ØQ ÚR P （2）Ø R P （3）Ø Q （1）（2）析取三段論 （4）Ø（PÙ ØQ） P （5）ØP Ú Q （4）等價(jià)轉(zhuǎn)換 （6）Ø P （3）（5）析取三段論3設(shè)命題公式為 Ø Q Ù（P ® Q）® Ø P。 （1）求此命題公式的真值表；解真值表如下PQØQP®Q

3、Ø Q Ù（P ® Q） Ø PØ Q Ù（P ® Q）® Ø P0011111010101110100011101001（2）求此命題公式的析取范式；Ø Q Ù（P ® Q）® Ø PØ（Ø Q Ù（ØPÚ Q）ÚØ P（ QÚ Ø（ØPÚ Q）ÚØ PØ（ØPÚ Q）Ú（ QÚ

4、; Ø P）1（析取范式）（ØPÙØQ）Ú（ØPÙQ）Ú（PÙØQ）Ú（PÙQ）（主析取范式）（3）判斷該命題公式的類型。答：該公式為重言式4在一階邏輯中構(gòu)造下面推理的證明 每個(gè)喜歡步行的人都不喜歡坐汽車。每個(gè)人或者喜歡坐汽車或者喜歡騎自行車。有的人不喜歡騎自行車。因而有的人不喜歡步行。令F(x)：x喜歡步行。G(x)：x喜歡坐汽車。H(x)：x喜歡騎自行車。答：解 前提："x（F（x）®Ø G（x），"x（G（x）ÚH（x）

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

6、（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) 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)6設(shè)R是集合A = 1, 2, 3, 4, 5, 6, 7, 8, 9上的整除關(guān)系。 （1） 給出關(guān)系R；（2）畫出關(guān)系R的哈斯圖；答：解 R=&l

7、t;1,2>,<1,3>,<1,4>,<1,5>,<1,6>，<1,7>,<1,8>,<1,9>,<2,4>,<2,6>，<2,8>，<3,6>，<3,9>，<4,8>IACOV A=<1,2>,<1,3>,<1,5>,<1,7>,<2,4>,<2,6>，<3,6>，<3,9>，<4,8>作哈斯圖如右：（2） 指出關(guān)系R的最大、

8、最小元，極大、極小元。答：極小元和最小元為1；極大元為5,6,7,8,9, 無最大元 7設(shè)R是集合A = 1, 2, 3, 4, 6, 12上的整除關(guān)系。(1) 給出關(guān)系R；答：解 R=<1,2>,<1,3>,<1,4>,<1,6>，<1,12>,<2,4>,<2,6>，<2,12>，<3,6>，<3,12>，<4,12>,<6,12>IA（2） 給出COV A答：COV A=<1,2>,<1,3>,<2,4>,&l

9、t;2,6>，<3,6>，<4,12>，<6,12>（3） 畫出關(guān)系R的哈斯圖；答：作哈斯圖如右：（4） 給出關(guān)系R的極大、極小元、最大、最小元。 答：極小元和最小元為1；極大元和最大元為128求帶權(quán)圖G的最小生成樹，并計(jì)算它的權(quán)值。 答：解 9給定權(quán)為1，9，4，7，3；構(gòu)造一顆最優(yōu)二叉樹。 答：解 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24 10給定權(quán)為2，6，3，9，4；構(gòu)造一顆最優(yōu)二叉樹。答：解 2 3 4 6 9 5 4 6 9 9 6 9 15 924或 2 3 4 6 9 5 4 6 9 9 15 2411、設(shè)字母在通訊中出現(xiàn)的頻率為：，。試給出傳輸這6個(gè)字