离散数学-2005`2006-试卷A

一、基础知识（40分）1．判断下列句子是否是命题，若是命题将其符号化。（4分）①.李平虽然聪明，但不用功。②.除非你陪伴我或代我雇辆车子，否则我不去。2．在一阶逻辑中将下列命题符号化。（4分）①.任何自然数不是奇数就是偶数，偶数均能被2整除，奇数均不能被2整除。②.任意实数的平方都不小于0。3．求下列集合的幂集。（4分）①.A={φ，{φ}}②.B={{φ,a},{a}}4．设f,g,h∈RR，且有f(x)＝x＋3，g(x)＝2x＋1，h(x)＝x/2。求g◦g，h◦f，g◦h，f◦h，f◦h◦g.（6分）5．设集合A={0,1,2,3,4}，定义A上的二元关系R为：R＝{x,yx,yA(x=yx+yA)}，请写出二元关系R的集合表达式，并判断R具有的性质。（6分）6．已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，则G中至少有多少个顶点？（4分）7．在下面各图中，哪些是欧拉图，哪些是哈密尔顿图？（4分）8．设代数系统A,*，其中A={a,b,c}，A上的二元运算*定义如下表：请分析*运算的封闭性、交换性、等幂性。A中关于*是否有幺元和零元？如有幺元，每个元素是否有逆元？如有，求出逆元。（8分）二、理解运用（30分）9．证明逻辑等价式AB(A∧B)∨(┐A∧┐B)成立。（6分）10.求下列命题公式的主析取范式和所有成假赋值。)())((rqprqp（6分）11.求谓词公式的前束范式。（6分）12.令A={1,2,3,4,5,6},画出偏序集＜A，整除＞的哈斯图，并求(1)集合A的最大元、最小元、极大元和极小元；(2)集合B＝{2，3，6}的上界、下界、最小上界、最大下界。（6分）13.求带权图1的最小生成树及权（6分）三、综合能力（30分）14.用推理理论证明下面结论是否有效？如果今天是星期三，那么我有一次离散数学或数字逻辑测验。如果离散数学课老师有事，那么没有离散数学测验。今天是星期三且离散数学老师有事。所以，我有一次数字逻辑测验。(10分)15.某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打三种球。而6个会打网球的人都会打另外一种球（指篮球或排球），求不会打这三种球的人数。（10分）16.设7个英语字母在通信中出现的频率如下：a:35%，b:20%，c:15，d:10%，e:10%，f:5%，g:5%设计一个最佳2元前缀码。使通信中出现的二进制数字尽可能少，并计算传输104个按上述比例出现的字母需要多少个二进制数字。（10分）答案及评分参考（A卷）1.①是命题。(1分)用p表示“李平聪明”，q表示“李平用功”，则符号化为p∧﹁q。(1分)②是命题。(1分)可表示为(p∨q)r(1分)，其中p：你陪伴我，q：你代我雇车，r：我去2.①设O(x)：x是奇数，N(x)：x是偶数，E(x)：x是偶数，D(x)：x能被2整除。则原句可符号化为：(2分)))()(())()(())()()((xDxOxxDxExxExOxNx②取论域为实数域，可设L(x,y)：x小于y，f(x)：x的平方。则可符号化为：)0),((xfLx(2分)3.①ρ(A)={φ，{φ}，{{φ}}，{φ,{φ}}}(2分)②ρ(B)={φ，{{φ,a}},{{φ}},{{φ,a},{a}}}(2分)4.g◦g(x)=g(g(x))＝2(2x＋1)＋1=4x＋3；(1分)h◦f(x)＝h(f(x))＝1/2(x+3)；(1分)g◦h(x)＝g(h(x))＝2·x/2＋1＝x＋1；(1分)图1f◦h(x)＝f(h(x))＝x/2＋3；(1分)f◦h◦g(x)＝f(h(g(x)))=(2x+1)/2＋3＝x＋7/2；(2分)5.R＝IA{0,1,1,0,0,2,2,0,0,3,3,0,0,4,4,0,1,2,2,1,1,3,3,1}(2分)易知，R具有自反性(2分)和对称性(2分)。6.图G中边数m=10，由握手定理可知，G中各顶点度数之和为20，4个3度顶点占去12度，还剩8度，若其余全是2度顶点，还需要4个顶点来占用这8度，所以G至少有8个顶点。(4分)7.(3)为欧拉图(1分)；(2)，(3)，(4)是哈密尔顿图。(3分)8.*运算是封闭的，因为表中每个元素都属于A。(1分)*运算可交换，因运算表关于主对角线对称。(1分)*运算不等幂，因运算表主对角线有的元素与所在行列表头元素不同。(1分)*运算有零元c，因为c所在行列中的元素都是与它相同。(1分)*运算有幺元a，因为a所在行列中的元素依次与表头行列一致。(2分)a和b均以自身为逆元，因为a、b所在行和列交汇处的元素为幺元。(2分)9.AB(A→B)∧(B→A)(┐A∨B)∧(┐B∨A)(2分)(┐A∧┐B)∨(┐A∧A)∨(B∧┐B)∨(B∧A)(2分)(A∧B)∨(┐A∧┐B)(2分)(注：此题证法不唯一，用其他方法也可)10．解把原命题公式记为A，则(2分)。(2分)A的所有成假赋值为011，100，101，110。(2分)11.),()(),())((),()(yxyGxFxyxyGxxFyxyGxxF(3分))),()((),()(yzGxFyxyzyGxFx(3分)12.哈斯图如下：(2分)(1)集合A无最大元，最小元是1，极大元是4、5、6，极小元是1。(2分)(2)集合B的上界是6，下界是1，最小上界是6，最大下界是1。(2分)13.所求最小生成树如下图所示(4分)W(T)=18(2分)14.证明：设p：今天是星期三。q：我有一次离散数学测验。r：我有一次数字逻辑测验。s：离散数学课老师有事。该推理就是要证明：p→(q∨r)，s→q，p∧sr(2分)⑴p∧sP(1分)⑵pT⑴化简律(1分)⑶sT⑴化简律(1分)⑷s→qP(1分)⑸qT⑶⑷假言推理(1分)⑹p→(q∨r)P(1分)⑺q∨rT⑵⑹假言推理(1分)⑻rT⑸⑺析取三段论(1分)15．设会打排球、网球、篮球的学生集合分别为A，B和C，则|A|＝12，|B|＝6，|C|＝14，|S|＝25，|A∩C|=6，|B∩C|＝5，|A∩B∩C|=2。｜A∩B｜＝3(5分)(5分)16.解：将所有的频率都乘100，所得结果按从小到大顺序排列：(2分)，，，，，，。图2以以上各数为权，用Huffman算法求一棵最优树，见下图所示。(2分)对照各个权可知各字母的前缀码如下：(4分)a：10，b：01，c：111，d：110，e：001，f：0001，g：0000，于是，a，b的码长为2，c，d，e的码长为3，f，g的码长为4。(各分支点的权之和)，是传输100个按给定频率出现的字母所用的二进制数，因而传输个按上述频率出现的字母要用个二进制数字。(2分)