离散数学试题C.doc

装 订 线 班级： 学号： 姓名： 装 订 线 第 =page 2*2-1 3页 共 = NUMPAGES 3*26页 第 = PAGE 2*2 4页 共  = NUMPAGES 3*26页 第 =page 3*2-1 5页 共 = NUMPAGES 3*26页 第 = PAGE 3*2 6页 共  = NUMPAGES 3*26页 哈尔滨工程大学试卷 考试科目：离散数学C（041121，041131-32） 题号一二三四五总分分数评卷人 填空题（每小题3分，共15分） 谓词公式?xF(x)???yG(x，y)的前束范式为 ． 设R是集合A={1，2，3，4，5，6，7，8，9，10}上的模3同余关系，则A关于R的商集为 ． 有理数集上定义二元运算*为a*b=a+b-ab，则运算*的单位元为 　　 ，零元为 　　 ． 无向树T中有2个4度顶点，3个3度顶点，其余顶点都是树叶，则T中有 　 片树叶． 设G是n阶无向简单完全图，则n与边数m的关系为 　． 选择题（每小题3分，共15分） 令F(x)：x是火车，G(y)：y是汽车，H(x，y)：x比y跑得快．在一阶逻辑中将“所有的火车都比某些汽车跑得快”符号化为【 】 A．?x(F(x)??y(G(y)?H(x，y)))． B．?x?y((F(x)?G(y))?H(x，y))． C．?x?y(F(x)?(G(y)?H(x，y)))． D．?x(F(x)??y(G(y)?H(x，y)))． 4阶无向完全图的非同构的生成子图有 【 】 A．1个． B．2个． C．3个． D．4个． 设代数系统?A，??是独异点，e是其单位元，若?a?A，有a?a=e，则?A，?? 　　　　　　　 【 】 A．是群但不是Abel群． B．是Abel群． C．不是群． D．不是代数系统． 下列图中是哈密尔顿图的有 【 】 A．K3，4． B．K4． C．K2． D．K1,1． 下列图中是欧拉图的有 【 】 A．K2，3． B．K4． C．K7． D．K3，3． 计算与简答题（每小题10分，共40分） 利用等值演算法求公式(p?q)?(q?p)的主析取范式，并给出其成真赋值． 设A={1，2，3，4，6，9，12，18，36}，B={2，4，6，12，18}，D为整除关系． 画出偏序集?A，D?的哈斯图． 求B的极大元、极小元、最大元、最小元、最小上界，最大下界． ?A，D?是否构成格？简要说明理由． 求模10加群G=áZ10，?10?的所有生成元与子群． 设集合Ａ={a，b，c，d}上的二元关系R={áa，b?，áb，a?，áb，c?，ác，b?}，用关系矩阵来求R的传递闭包t(R)． 证明题（共20分） 在一阶逻辑中构造下面推理的证明： 前提：?x(F(x)?G(x))，?x(F(x)?H(x))． 结论：?x(G(x)?H(x))． 设?B，?，?，，1，0?为一布尔代数，证明：?a，b?B，有 (aúb) = aùb． 证明：设e为无向连通图G的桥，则e在G的每棵生成树中． 应用题（10分） 设有5个城市C1，C2，C3，C4，C5，任意两城市之间铁路造价如下：（以百万元为单位） W(C1，C2)=4，W(C1，C3)=7，W(C1，C4)=16，W(C1，C5)=10； W(C2，C3)=13，W(C2，C4)=8，W(C2，C5)=17； W(C3，C4)=3， W(C3，C5)=10； W(C4，C5)=12． 试求出连接5个城市、且造价最低的铁路线路网．