离散数学考试c

《离散数学考试c》由会员上传分享，免费在线阅读，更多相关内容在行业资料-天天文库。

1、班级：学号：姓名：装订线哈尔滨工程大学试卷考试科目：离散数学C（041121，041131-32）题号一二三四五总分分数评卷人一、填空题（每小题3分，共15分）1.谓词公式"xF(x)®Ø$yG(x，y)的前束范式为．2.设R是集合A={1，2，3，4，5，6，7，8，9，10}上的模3同余关系，则A关于R的商集为．3.有理数集上定义二元运算*为a*b=a+b-ab，则运算*的单位元为，零元为．4.无向树T中有2个4度顶点，3个3度顶点，其余顶点都是树叶，则T中有片树叶．5.设G是n阶无向简单完

2、全图，则n与边数m的关系为．二、选择题（每小题3分，共15分）1.令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)))．2.4阶无向完全图的非同构的生成子图有【】A．1个．B．2个．C．3

3、个．D．4个．3.设代数系统áA，*ñ是独异点，e是其单位元，若"aÎA，有a*a=e，则áA，*ñ【】A．是群但不是Abel群．B．是Abel群．C．不是群．D．不是代数系统．4.下列图中是哈密尔顿图的有【】A．K3，4．B．K4．C．K2．D．K1,1．5.下列图中是欧拉图的有【】A．K2，3．B．K4．C．K7．D．K3，3．三、计算与简答题（每小题10分，共40分）1.利用等值演算法求公式(pÚq)®(q«p)的主析取范式，并给出其成真赋值．第5页共6页第6页共6页班级：学号：姓名：装订

4、线1.设A={1，2，3，4，6，9，12，18，36}，B={2，4，6，12，18}，D为整除关系．（１）画出偏序集áA，Dñ的哈斯图．（２）求B的极大元、极小元、最大元、最小元、最小上界，最大下界．（３）áA，Dñ是否构成格？简要说明理由．2.求模10加群G=áZ10，Å10ñ的所有生成元与子群．3.设集合Ａ={a，b，c，d}上的二元关系R={áa，bñ，áb，añ，áb，cñ，ác，bñ}，用关系矩阵来求R的传递闭包t(R)．聞創沟燴鐺險爱氇谴净。一、证明题（共20分）1.在一阶逻辑中

5、构造下面推理的证明：前提："x(F(x)®G(x))，$x(F(x)ÙH(x))．结论：$x(G(x)ÙH(x))．第5页共6页第6页共6页班级：学号：姓名：装订线1.设áB，Ù，Ú，'，1，0ñ为一布尔代数，证明："a，bÎB，有(aÚb)'=a'Ùb'．2.证明：设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

6、，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个城市、且造价最低的铁路线路网．第5页共6页第6页共6页