离散数学习题课
1．若集合A={a，{b，c}}的幂集为P(A)，集合B={ O/，{ O/}}的幂集为P(B)，求P(A)∩P(B)。
2．设函数g: Z×Z→Z定义为g (x , y)=x*y=x + y – xy
试证明二元运算“*”满足交换律和结合律。求幺元，并指出哪些元素有逆元，逆元是什么？
3．求图G＝的可达矩阵，其中V＝｛v1,v2,v3,v4｝
E＝｛(v1,v2), (v2,v3), (v2,v4), (v3,v2), (v3,v4), (v3,v1), (v4,v1)｝
4．求
()
P Q
⌝∧
的主析取范式和
()()
xF x xG x
∃∨⌝∀的前束范式
解：
┐(P∧Q)
⇔┐P∨┐Q
⇔ (┐P∨┐Q)∧(┐P∨P)
⇔┐P∨(┐Q∧P)
⇔ [┐P∨(┐Q∧P)]∧(┐Q∨Q)
⇔ [┐P∧(┐Q∨Q)] ∨[ (┐Q∧P) ∧(┐Q∨Q)] ⇔ (┐P∧┐Q)∨(┐P∧Q)∨(┐Q∧P)
∃x F(x)∨┐∀x G(x)
⇔∃x F(x)∨∃x ┐G(x)
⇔∃x(F(x) ∨┐G(x))
5．设A＝｛2，3，4，6，8，12，24｝，R为A上整除关系，试画的哈斯图，并求A 中的最大元，最小元，极大元，极小元。
6．设M是偶数集，＋和·是数的加、乘运算，证明是一个环。
7．设R是集合X上的二元关系，证明R是X上传递关系当且仅当R R⊆R。
8．求叶带权2，3，5，7，8的最优二元树，并由此编一组前缀码。
解：
计算过程如下：
2，3，5，7，8
5，5，7，8
10，7，8
10，15
25
所以，最优二元树如下：
该图的前缀编码为：｛000，001，01，10，11｝。
9．将下列命题符号化，并用演绎法证明其论证是否正确。
不存在白色的乌鸦；北京鸭是白色的。因此，北京鸭不是乌鸦。
10．有6个村庄V i，i=l，2，…，6欲修建道路使村村可通。现已有修建方案如下带权无向图所示，其中边表示道路，边上的数字表示修建该道路所需费用，问应选择修建哪些道路可使得任二个村庄之间是可通的且总的修建费用最低?画出符合要求的最低费用的道路网络图并计算其费用。
