4331243214334
7．设7个字母在通信中出现的频率如下：
a：35% b：20% c：15% d：10% e：10% f：5% g：5%。
用最优二元树构造一个表示它们的最佳前缀码，使得用较短的符号串表示频率较大的字母。
解：将所有频率都乘以100作为权值，得Wa = 35，Wb = 20，Wc= 15，Wd= 10，We= 10，Wf= 5，Wg= 5，而这7个权所对应的最优二元树如下所示：
1000400200100001101120010350151001101011601251105001050011
对照各个权可知各字母的最佳前缀码是：
a ：11 b：01 c：100 d：101 e：000 f：0010 g：0011
8．求一棵带权为1，1，1，2，2，3，4，5的最优二元树T，并计算它的权W(T)。 解：带权为1，1，1，2，2，3，4，5的最优二元树T如下所示：
19842211132411635
W(T)＝（1+1+1+2）×4+（2+3）×3+（4+5）×2＝53 四、证明题
1．构造下列推理的证明：
前提：(P∨Q) →( R∧S), (S∨M) → U，结论：P →U 证明：
6
① P 附加前提引入 ② P∨Q ①附加规则 ③ (P∨Q) →( R∧S) 前提引入 ④ R∧S ②③ 假言推理 ⑤ S ④化简规则 ⑥ S∨M ⑤附加规则 ⑦ (S∨M) → U 前提引入 ⑧ U
2．构造下列推理的证明：
前提：?x (A(x)→B(x))，证明：
① ? x (A(x)∧H(x)) ② A(c)∧H(c) ③ ?x (A(x)→B(x)) ④ A(c)→B(c) ⑤ A(c) ⑥ H(c) ⑦ B(c) ⑧ B(c)∧H(c) ⑨ ? x (B(x)∧H(x))
⑥ ⑦假言推理
? x (A(x)∧H(x))，结论：?x(B(x)∧H(x)) 前提引入 ① EI规则 前提引入 ③ UI 规则 ②化简规则 ②化简规则 ④ ⑤假言推理 ⑥⑦ 合取
⑧EU规则 7
本科《离散数学》(计算机数学软件)复习题
