离散数学2013年4月考试真题(02324)

已知a，b，c，d，e，f，g共7个人中，a会讲英语;b会讲英语和汉语;c会讲英语、意大利语和俄语;d会讲汉语和日语;e会讲意大利语和德语;f会讲俄语、日语和法语;g会讲德语和法语。若将他们的座位安排在圆桌旁，要使得每个人都能与他身边的人交谈，应如何安排座位，说明理由并画出座位安排图。

设G =< V，E >是连通图，且e∈E，证明：当且仅当e是G的割边时，e才在G的每棵生成树中。

设S={1，2，3，4}，并设A=SxS，在A上定义关系R为： R< c，d >当且仅当a+b=c+d，证明R是等价关系。

构造下面的推理证明：任何自然数都是整数，存在着自然数，所以存在着整数(设个体域为实数集合R)。

?有向图D=如图30图，请完成下列问题：

(1)给出D的邻接矩阵及4次以下的幂;

(2)判定D中长度为2的路径有几条?从v₁到v₄长度为3的路径有几条?

(3)求D的可达性矩阵P。

设< A，* >为群，任意a，b，c∈A，证明：若a*b=a*c，则b=c。

设A={1，2，3，4，5，8，12，24}，R为A上整除关系，试画出的哈斯图，并求出A中最大元，最小元，极大元，极小元。

设有向图D=的邻接矩阵A=，那么|E|=_______，|V|=_______。

给定集合A={0，1，2，3}，且A上有关系：

R={|i，j∈A，j=i+1或j=i/2}，

S={|i，j∈A，i=j+2 }，

试计算R。S

设为群，若在G中存在一个元素a，使得G中的任意元素都由a的幂组成，则称该群为_______，元素a称为G的_______。

设f：R→R，f(x)=x+3，g：R→R，g(x)=x/2，则复合函数(f。g)(x)=______，(g。f)(x)=_______。

设Z是整数集，在Z上定义二元运算 * 为a*b=a+b+a·b，其中+和·是数的加法和乘法，则代数系统的幺元是_______，零元是_______。

命题公式的成真指派是_______，成假指派是_______。

设N表示非负整数集，R：N→N，xRy定义为x+2y=10，则domR=_______，ranR=_______。

集合A={1，2，3}上不同的等价关系有()

• A.3个
• B.4个
• C.5个
• D.6个

设V={a，b，c，d}，则下列与V构成强连通图的边集的是()

• A.
• B.
• C.
• D.

一棵树有2个2度结点，1个3度结点，3个4度结点，则其1度结点数为()

• A.5
• B.7
• C.8
• D.9

设有A={a，b，c}上的关系R={,,,,}，则R不具有（）

• A.自反性
• B.对称性
• C.传递性
• D.反对称性

设是阶大于1的群，则下列命题中错误的是()

• A.G中每个元素都有逆元
• B.存在幺元
• C.存在零元
• D.运算 * 是可结合的

一个连通的无向图G，如果它的所有结点的度数都是偶数，那么它有一条()

• A.汉密尔顿回路
• B.欧拉回路
• C.汉密尔顿通路
• D.初级回路

下列代数系统中，不是群的是()

• A.
• B.
• C.
• D.

设A={1，2，3}，B={a，b}，下列二元关系中是从A到B的函数是()

• A.R={<1,a>,<2,a>,<3,a>}
• B.R={<1,a>,<1,b>,<2,a>,<3,a>}
• C.R={<1,a>,<2,b>}
• D.R={<1,b>,<2,a>,<3,b>,<1,1>}

的否定是()

• A.
• B.
• C.
• D.

设A={a，{a}}，ψ(A)为A的幂集，下列选项不正确的是()

• A.
• B.
• C.
• D.

对于任意集合A，B，C，下列结论正确的是()

• A.
• B.
• C.
• D.

下列谓词公式中为前束范式的是()

• A.
• B.
• C.
• D.

下列命题公式为重言式的是()

• A.
• B.
• C.
• D.

下列命题公式的联结词集合中，可作为最小联结词组的是()

• A.
• B.
• C.
• D.

设P：天下雨，Q：我骑自行车上班，对命题“除非天下雨，否则我就骑自行车上班”符号化正确的是()

• A.￢P∧Q
• B.￢P→Q
• C.￢P→￢Q
• D.P→￢Q