：名 姓 线 ： 号 学 订 ： 业 专 装 ：院 学广东工业大学考试试卷 ( A ) 课程名称: 试卷满分 分 考试时间: 年 月 日 (第 周 星期 ) 题 号 一 二 三 四 五 六 七 八 九 十 总分 评卷得分 评卷签名 复核得分 复核签名 一、填空题（共8题，每题3分，共24分） 1、设A = 1, 2，求：A×P(A) = 2、下图中最小生成树的权为 3、设个体域D ={1,3}，命题xy(x + y = 3)的真值为__________。 4、设
是群，a, b G，则（a-1）-1 = a ，（ab）-1 = a 。 5、设p: 3 + 3 = 6，q: 雪是黑色的，命题“如果3 + 3 = 6，那么雪是黑色的”的命题符号化形式为 。 6、设A＝{1, 2, 3}, R1, R2, R3和R4都是A上的关系, 其中 R1 ＝ {<1, 1>, <2, 2>}，R2 ＝ {<1, 1>, <1, 2>, <2, 1>} R3 ＝ {<1, 2>, <1, 3>}，R4 ＝ {<1, 2>, <2, 1>, <1, 3>} 既是对称又是反对称的关系是 ，不对称也不反对称的关系是 7、定义1234553214,1234543125，那么 = 广东工业大学试卷用纸，共 3 页，第 1 页8、代数系统 （6为模6乘法运算）中所有的等幂元为 二、选择题（共10题，每题2分，共20分） 1、下列数列中，可简单图化的是( ) A、(2, 4, 6, 8, 10) B、(1, 3, 3, 3, 4) C、(2, 2, 3, 4, 5) D、(3, 3, 3, 4) 2、下列命题正确的是( )。 A、 B、AC = BD 则A=B,C=D C、{ a, b} { a, b, {{a,b}}} D、{ a, b} { a, b, {{a, b}}} 3、判断下列为双射函数的是( ) A、f: R→R, f(x) = x2+2x1 B、f: R→Z, f(x) = x C、f: R→R, f(x) = 2x+1 D、f: R+→R+, f(x) = (x2+1)/x 4、公式（p∧q）→┐p的成假赋值是（ ） A、00 B、01 C、10 D、11 5、无向图G如右图所示，下列对图G的判断，正确的是：( A ) A、G是哈密顿图 B、G是半欧拉图 C、{e1, e2}是G的边割集 D、{v5, v8}是G的点割集 6、运算*的运算表如图所示，则左幺元是（ ） * a b c d 7、下述*运算为实数集合上的运算，其中可交换且可结合的运算是( ) A、a*b = a+2b B、a*b = a+b-ab C、a*b = a D、a*b = |a+b| 广东工业大学试卷用纸，共 3 页，第 2 页a a a c a b b b c b c b c c a d b d c d A、a B、b C、c D、d 8、公式xy(F(x,y）→F(y,x))是（ ） A、永真式 B、永假式 C、非永真式的可满足式 D、不能确定 9、设A和B是有限集，设|A| = n，|B| = m，从A到B的不同的二元关系有（ ）个 A、2n*m B、 2n*n C、mn D、nm 10、 (7为加法取模7运算)的所有生成元是（ ） A、1 B、1, 3, 5, 7 C、2, 4, 6, 8 D、N7 – {0}中所有元素 三、(12分) 集合A是自然数集合的子集A = 1, 3, 5, 9, 15, 18, 27, 36, 45, 54，R是A上的整除关系。 (1) 画出关系R的哈斯图 (2) 求A的最大元，最小元，极大元，极小元 (3) 求集合{3, 9}的上界，下界，上确界，下确界 四、(12分) 在通信中，设7个字母出现的频率如下： a：35% b：20% c：15% d：10% e：10% f： 5% g：5% (1) 以100乘各个字母出现的频率为权，画出一棵最优树。并求出该最优树的权值。 (2) 请依据最优树，为此7个字母设计一种最优前缀码的编码方案。 五、(8分) 已知公式：（p→q)→r，求其主析取范式与主合取范式。 六、(8分) 代数系统中，若存在单位元e，则单位元e必唯一。 七、(10分) 在一阶谓词逻辑中构造下面推理的证明。 前提：x(F(x)∨G(x))，x(G(x)→┐H(x))， 结论：xH(x)→xF(x) 八、(6分) 设 G 为 n（n3）阶无向简单图， (G) 2，证明G中存在长度 (G)的路径.广东工业大学试卷用纸，共 3 页，第 3 页