密 封 線 內(nèi) 不 答 題 ） 教學(xué)中心： 專業(yè)層次： 姓名： 學(xué)號： 座號： 華南理工大學(xué)網(wǎng)絡(luò)教育學(xué)院 教學(xué)中心： 專業(yè)層次： 姓名： 學(xué)號： 座號： 2020–2021學(xué)年度第一學(xué)期《 離散數(shù)學(xué) 》作業(yè) 1、用推理規(guī)則證明 P ? Q，(?Q úR）ù? R，?（?PùS）? S證 （1）(?Q úR）ù? R 前提引入 （2）?Q ù? R （1）等價轉(zhuǎn)換 （3）? Q （2）化簡 （4）P ? Q P （5）?P （3）（4）拒取式 （6）?（?PùS） P （7）P ú? S （6）等價轉(zhuǎn)換 （8）?S （5）（7）析取三段論2、用推理規(guī)則證明 P ? Q，R ? S （Pù R）?（Q ù S）證 （1）Pù R 附加前提引入 （2）R （1）化簡 （3）P （1）化簡 （4）P ? Q P （5）Q （3）（4）假言推理 （6）R ? S P （7）S （2）（6）假言推理 （8）Q ùS （5）（7）合取3．求公式的主析取范式與主合取范式，并寫出相應(yīng)的成真賦值與成假賦值。

解 主析取范式，成真賦值10，11主合取范式成假賦值是00,014．在一階邏輯中構(gòu)造下面推理的證明 每個喜歡步行的人都不喜歡坐汽車每個人或者喜歡坐汽車或者喜歡騎自行車有的人不喜歡騎自行車因而有的人不喜歡步行令F(x)：x喜歡步行G(x)：x喜歡坐汽車H(x)：x喜歡騎自行車5．用推理規(guī)則證明 "x（P（x）ú Q（x）），"x ?P（x）"x Q（x）證 （1）"x ?B（x） 前提引入 （2）?B（c） （1） US （3）"x（?A（x）? B（x）） 前提引入 （4）?A（c）? B（c） （3） US （5）A（c） （2）（4）I （6）$x A（x） （5）EG6．設(shè)R是集合A = {1, 2, 3, 4, 6, 8, 12, 24}上的整除關(guān)系 （1） 給出關(guān)系R；（2） 畫出關(guān)系R的哈斯圖；（3）指出關(guān)系R的最大、最小元，極大、極小元 解：（1）R={<1,1>,<1,2>,<1,3>,<1,4>,<1,6>,<1,8>,<1,12>,<1,24>,<2,2>,<2,4>, <2,6>,<2,8>,<2,12>,<2,24>,<3,3>,<3,6>,<3,12>,<3,24>,<3,3>,<3,6>,<3,12>,<3,24>,<4,4>,<4,8>,<4,12>,<4,24>,<6,6>,<6,12>,<6,24>,<8,8>,<8,24>,<12,12>,<12,24>,<24,24>}(2)哈斯圖如下所示（3）最大元24 最小元1 極大元12 極小元17． 設(shè)R是集合A = {1, 6, 9,12,18,24,36}上的整除關(guān)系。

1) 給出關(guān)系R；（2）畫出關(guān)系R的哈斯圖；（3）給出關(guān)系R的極大、極小元、最大、最小元 解：(1) R={<2,2>,<2,4>,<2,6>,<2,8>,<2,12>,<2,16>,<3,3>,<3,6>,<3,9>,<3,12>,<4,4>,<4,8>,<4,12>,<4,16>,<6,6>,<6,12>,<8,8>,<8,16>,<9,9>,<12,12>,<16,16>}(2) COVA= {<2,4>,<2,6>,<3,6>,<3,9>,<4,8>,<4,12>,<6,12>,<8,16>}8．求帶權(quán)圖G的最小生成樹，并計算它的權(quán)值 解：最小生成樹如圖所示權(quán)值為 4+7+8+9=289．求帶權(quán)圖G的最小生成樹，并計算它的權(quán)值 　解：C(T)=2+2+3+5+6+100=11810、求帶權(quán)為1，2，3，4，5，6，7，8的最優(yōu)二元樹T，并給出T對應(yīng)的二元前綴碼集合解：（B={000,001,01000,01001,0101,011,10,11},W(T)=102）《 離散數(shù)學(xué)作業(yè) 》 第 2 頁 （共 2 頁）。