离散数学试题(2007)_C

班级：学号：姓名：装订线第1页共6页第2页共6页一、填空题（每小题3分，共15分）1.谓词公式(xF(x,y)yG(x,y))的前束范式为．2.设A={1，2，3，4，5}，P(A)，构成群，其中为集合的对称差．令B={1，4，5}，则由B生成的循环子群B=．3.模加群G=Z6,的所有生成元为．4.n阶无向简单图G的==n-1，则G为．5.设G，＊为群，aG且|a|=m，则|a-1|=．二、选择题（每小题3分，共15分）1.命题公式¬(p→q)qr的类型是【】A．重言式．B．非重言式的可满足式．C．简单合取式．D．矛盾式．2.5阶无向完全图的非同构的自补图有【】A．1个．B．2个．C．3个．D．4个．3.设A，是独异点，e是其单位元，若aA，有aa=e，则A，【】A．是群但不是Abel群．B．是Abel群．C．不是群．D．不是代数系统．4.树T中有3个3度顶点，2个2度顶点,其余顶点都是树叶，则T中树叶片数为【】A．1B．4C．5D．65.对完全二部图Kr，s，当【】时，Kr，s为哈密尔顿图．A．r=s．B．rs．C．rs．D．rs．三、计算与简答题（每小题10分，共40分）1.利用等值演算法求公式(rp)(q(pr))的主析取范式，并给出其成真赋值．哈尔滨工程大学试卷考试科目：离散数学C（051121，051131-32）题号一二三四五总分分数评卷人装订线第3页共6页第4页共6页2.设S45表示45的全体正因子（包括1和45）组成的集合，在S45上定义整除关系：mnm|n．（１）画出偏序集S45，的哈斯图．（２）求出S45，中最大元、最小元和所有可逆元的逆元．（３）S45，是否构成格？简要说明理由．3.求模15加群G=Z15，的所有生成元与所有子群．4.设集合Ａ={a，b，c，d}上的二元关系R={a，b，b，a，b，c，c，b}，求R的自反闭包r(R)和对称闭包s(R)．5.设有向图D如图，求D中长度为3的通路数，并指出其中的回路数．v3v2v4v1班级：学号：姓名：装订线第5页共6页第6页共6页四、证明题（每小题10分，共20分）1.在一阶逻辑中构造下面推理的证明：前提：x(H(x)D(x)S(x))，x(H(x)(S(x)F(x)))，x(H(x)F(x))结论：x(H(x)D(x))．2.设G，＊是一个群，令C={aG|xG，a＊x=x＊a}证明：C，＊是G，＊的子群．五、应用题（10分）今有20人参加一个小型会议．这20人中每人至少与其中10人（不包括自己）认识，能否将这20人安排在一个圆桌上，使得每个人都和他身边的人认识，为什么？请说明理由．