资源描述：
《离散数学作业.doc》由会员上传分享，免费在线阅读，更多相关内容在应用文档-天天文库。
1、（密封线内不答题）教学中心：专业层次：姓名：学号：座号：华南理工大学网络教育学院教学中心：专业层次：姓名：学号：座号：2014–2015学年度第一学期《离散数学》作业（解答必须手写体上传，否则酌情扣分）1．设命题公式为ØQÙ（P®Q）®ØP。 （1）求此命题公式的真值表；答：解（1）真值表如下PQØQP®QØQÙ（P®Q）ØPØQÙ（P®Q）®ØP0011111010101110100011101001（2）求此命题公式的析取范式；答：Ø（ØQÙ（ØPÚQ））ÚØPQÚØ（ØPÚQ）ÚØPQÚPÙØQÚØPPÚQÙØQÚØPPÚ1ÚØPPÚØPÚ11（ØPÙØQ）Ú
2、（ØPÙQ）Ú（PÙØQ）Ú（PÙQ）（主析取范式）（3）判断该命题公式的类型。答：该命题公式重言式2．用直接证法证明前提：PÚQ，P®R，Q®S结论：SÚR证(1)PÚQP(2)ØP®QT(1)E(3)Q®SP(4)ØP®ST(2,3)I《离散数学作业》第5页（共5页）(5)ØS®PT(4)E(6)P®RP(7)ØS®RT(5,6)I(8)SÚRT(7)E3．在一阶逻辑中构造下面推理的证明每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢
3、骑自行车。解前提："x（F（x）®ØG（x）），"x（G（x）ÚH（x）），$xØH（x）。结论：$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））结论：（$x）（Q（x）∧R（x））。《离散数学作业》第5页（共5页）证(
4、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)5．设R是集合A={1,2,3,4,6,12}上的整除关系。(1)给出关系R；（2）给出COVA（3）画出关系R的哈斯图；（4）给出关系R的极大、极小元、最大、最小元。解R={<1,2>,<1,3>,<1,4>,<
5、1,6>，<1,12>,<2,4>,<2,6>，<2,12>，<3,6>，<3,12>，<4,12>,<6,12>}∪IACOVA={<1,2>,<1,3>,<2,4>,<2,6>，<3,6>，<4,12>，<6,12>}作哈斯图如右：极小元和最小元为1；极大元和最大元为126．求带权图G的最小生成树，并计算它的权值。《离散数学作业》第5页（共5页）答：C（T）=1+2+3+1=77．给定权为1，9，4，7，3；构造一颗最优二叉树。答：13479447987915924W（T）=4×1+4×3+3×4+2×7+1×9=518．给定权为2，6，3，9，4；构造一颗最优
6、二叉树。 解23469546996915924W(T)=4×(2×3)+3×4+2×6+9=53或23469546991524《离散数学作业》第5页（共5页）W(T)=3×(2+3)+2×4+2×(6+9)=539、给定权为2，6，5，9，4，1；构造一颗最优二叉树。解1245693456975697119111627W(T)=4×1+4×2+3×4+2×9+2×5+2×6=6410、设字母在通讯中出现的频率为：，。试给出传输这6个字母的最佳前缀码？问传输1000个字符需要多少位二进制位？解先求传输100个字符所需要的位数。A:30,b:25,c:20,d:10,e
7、:10,f:5是依照出现频率得出的个数。构造最优二叉树如下：510102025301510202530252025302545304555100需要二进制位数为10W(T)=10×{4×(5+10)+3×10+2×(20+25+30)}=2400《离散数学作业》第5页（共5页）
