Question

离散数学求解答过程（求证后加分）

1. 用等值演算法证明：((p∨q)→r)→p <=> (p∨q∨p)∧( ┐r∨p) 2. 证明: a上的关系R1与R2都具有对称性,证明R1∪R2也具有对称性 3. 在自然推理系统P中，构造下面推理的证明: 或者逻辑学难学，或者有许多学生喜欢它，如果数学容易学，那么逻辑学并不难学。因此如果许多学生不喜欢逻辑，那么数学并不容易学。 4. 要传输十进制数据，已知十进制数(0~9)出现频率分别为27%,26%,16%,2%,2%,7%,6%,4%,5%,5%

Answer 1

1 ((p∨q)→r)→p <=> ┐((p∨q)→r)vp<=> ┐(┐(p∨q)vr)vp<=> ((p∨q) ∧ ┐r)vp<=> (p∨q vp) ∧ (┐rvp)

 

2 证明：对于任意的<x,y>属于R1∪R2，<x,y>属于R1或<x,y>属于R2,。因为R1和R2具有对称性，所以<y,x>属于R1或< y,x >属于R2,得< y,x >属于R1∪R2。R1∪R2满足对称性得证。

3

设  P:逻辑学难学 ,Q:许多学生喜欢逻辑学,  R:数学容易学

前提：PvQ, R→┐P

结论：┐Q→┐R

证明：

(1) ┐Q           P(附加前提)

(2)PvQ           P

(3) ┐Q→P     T(2)E

(4)P               T(1)(3)I

(5)R→┐P       P

(6) P→┐R      T(5)E

(7) ┐R           T(4)(6)I

(8) ┐Q→┐R   CP

 

4

用哈夫曼树编码

把出现频率化为权重形式，得

【0】0.27,【1】0.26,【2】0.16,【3】0.02,【4】0.02,

【5】0.07,【6】0.06，【7】0.04,【8】0.05, 【9】0.05

 

左子树标记0，右子树标记1，得到哈弗曼编码

0:100   1:10    2:111 3:00000     4:00001

5:1101   6:1100   7:0001  8:0010  9:0011