离散数学作业题

华南理工大学网络教育学院 2014–2015学年度第一学期 《 离散数学 》作业

(解答必须手写体上传，否则酌情扣分)

1

．设命题公式为 ⌝ Q ∧（P → Q ）→ ⌝ P 。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。

解 （1） 真值表如下 P Q ⌝Q P →Q ⌝ Q ∧（P → Q ） ⌝ P ⌝ Q ∧（P → Q ）→ ⌝ P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2） ⌝ Q ∧（P → Q ）→ ⌝ P ⇔⌝（⌝ Q ∧（⌝P ∨ Q ））∨⌝ P

）∨⌝ P ⇔⌝（⌝P ∨ Q ）∨（ Q ∨ ⌝ P ）⇔1（析取范式） ⇔（ Q ∨ ⌝（⌝P ∨ Q ）

（主析取范式） ⇔（⌝P ∧⌝Q ）∨（⌝P ∧Q ）∨（P ∧⌝Q ）∨（P ∧Q ）（3）该公式为重言式

2．用直接证法5．给定权为2，6，3，9，4；构造一最优二叉树。 解 2 3 4 6 9

5 4 6 9 9 6 9 15 9

24

颗

W (T )=4⨯(2+3) +3⨯4+2⨯6+9=53 或 2 3 4 6 9 5 4 6 9 9 15 24

W (T )=3⨯(2+3) +2⨯4+2⨯(6+9) =53

6．给定权为1，9，4，7，3 解 1 3 4 7 9

4 4 7 9 8 7 9 15 9 24

W (T )=4⨯1+4⨯3+3⨯4+2⨯7+1⨯9=51

3．给定权为2，6，5，9，4，1

解 1 2 4 5 6 9 3 4 5 6 9 7 5 6 9 7 11 9 11 16 27

W (T )=4⨯1+4⨯2+3⨯4+2⨯9+2⨯5+2⨯6=64证明 前提：P ∨ Q ，P → R ，Q → S 结论：S ∨ R

证 (1)P ∨ Q P (2) ⌝P → Q T(1)E

(3) Q → S P (4) ⌝P → S T(2,3)I (5) ⌝ S → P T(4)E

(6) P →R P (7) ⌝ S →R T(5,6)I (8) S∨R T(7)E

3．在一阶逻辑中构造下面推理的证明

每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。

令F(x)：x 喜欢步行。G(x)：x 喜欢坐汽车。H(x)：x 喜欢骑自行车。 解 前提：∀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 ））。

证 (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） 给出COV A

（3） 画出关系R 的哈斯图；

（4） 给出关系R 的极大、极小元、最大、最小元。

解 R ={,,,，,,，，，，,}∪I A

COV A ={,,,，，，}

作哈斯图如右：

极小元和最小元为1；

极大元和最大元为12

6．求带权图G 的最小生成树，并计算它的权值。

解

C (T )=1+2+3+1=7

7．给定权为1，9，4，7，3；构造一颗最优二叉树。 解 1 3 4 7 9 4 4 7 9 8 7 9 15 9 24

W (T )=4⨯1+4⨯3+3⨯4+2⨯7+1⨯9=51

8．给定权为2，6，3，9，4；构造一颗最优二叉树。 解 2 3 4 6 9 5 4 6 9 9 6 9 15 9

24

W (T )=4⨯(2+3) +3⨯4+2⨯6+9=53 或 2 3 4 6 9 5 4 6 9 9 15 24

W (T )=3⨯(2+3) +2⨯4+2⨯(6+9) =53

9、给定权为2，6，5，9，4，1

解 1 2 4 5 6 9 3 4 5 6

9 7 5 6 9 7 11 9 11 16 27

W (T )=4⨯1+4⨯2+3⨯4+2⨯9+2⨯5+2⨯

6=64

10、设字母a , b , c , d , e , f 在通讯中出现的频率为：a :30%,b :25%,c :20%，

d :10%,e :10%,f :5%。试给出传输这6

个字母的最佳前缀码？问传输1000个字

符需要多少位二进制位？

a :30,b :25, c :20, d :10,e :10,f :5是依照解 先求传输100个字符所需要的位数。

出现频率得出的个数。构造最优二叉树如下：

5 10 10 20 25 30 15 10 20 25 30 25 20 25 30 25 45 30 45 55 100

00000001

需要二进制位数为10W (T )=10⨯{4⨯(5+10)+3⨯10+2⨯(20+25+30)}=2400