离散数学-2005`2006(2)-试卷a

《离散数学-2005`2006(2)-试卷a》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、一、基础知识（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,

2、yÎAÙ(x=yÚx+yÎA)}，请写出二元关系R的集合表达式，并判断R具有的性质。（6分）6．已知图G中有10条边，4个3度顶点，其余顶点的度数均小于等于2，则G中至少有多少个顶点？（4分）7．在下面各图中，哪些是欧拉图，哪些是哈密尔顿图？（4分）8．设代数系统，其中A={a,b,c}，A上的二元运算*定义如下表：请分析*运算的封闭性、交换性、等幂性。A中关于*是否有幺元和零元？如有幺元，每个元素是否有逆元？如有，求出逆元。（8分）二、理解运用（30分）9．证明逻辑等价式A«BÛ(A∧B)∨(┐A∧┐B)成立。（6分）10.求下列命题公式的主析取范式和所有成假赋值。（6分）11

3、.求谓词公式的前束范式。（6分）12.令A={1,2,3,4,5,6},画出偏序集＜A，整除＞的哈斯图，并求(1)集合A的最大元、最小元、极大元和极小元；(2)集合B＝{2，3，6}的上界、下界、最小上界、最大下界。（6分）13.求带权图1的最小生成树及权（6分）图1三、综合能力（30分）14.用推理理论证明下面结论是否有效？如果今天是星期三，那么我有一次离散数学或数字逻辑测验。如果离散数学课老师有事，那么没有离散数学测验。今天是星期三且离散数学老师有事。所以，我有一次数字逻辑测验。(10分)15.某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球

4、，还有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

5、)：x是偶数，E(x)：x是偶数，D(x)：x能被2整除。则原句可符号化为：(2分)②取论域为实数域，可设L(x,y)：x小于y，f(x)：x的平方。则可符号化为：(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分)f◦h(x)＝f(h(x))＝x/2＋3；(1分)f◦h◦g(x)＝f(h(g(x)))=

6、(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分)*运算可交换，因运算表关于主对角线对称

7、。(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)∨