离散数学2011年4月考试真题（02324）

今有a，b，c，d，e，f，g共7人，已知下列事实：a会讲德语和汉语;b会讲英语和汉语;c会讲俄语和英语;d会讲日语和汉语;e会讲德语;f会讲法语、日语和俄语;g会讲法语和德语。

试问这7个人应如何排座位(圆桌)，才能使每个人和他身边的人交谈?

设G是有n个结点、2n条边，且存在度数为3的结点。

证明：G中至少有一个结点度数≥5。

构造下列推理的证明。如果天气很好并且他没去公司，他必去钓鱼。如果他去公司，他会乘1路公交车。今天天气很好。他没有乘1路公交车。所以他去钓鱼。

设={1，2，3，6，9，18}，≦为整除关系。(1)画出的哈斯图;(2)求子集B={3，6，9}的极大元、极小元、最大元、最小元。

设是一个群， a，b∈G。

证明：必存在惟一的x∈G，使得x*a=b。

设A={1，b为正整数}，在A上定义二元关系～如下：～当且仅当ab=cd。

证明：～是一个等价关系。

求公式的主合取范式和主析取范式。

设R={<1，1>，<1，3>，<2，1>，<2，2>，<3，3>，<4，3>，<4，4>}是A={1，2，3，4}上的二元关系。

(1)画出R的关系图;

(2)写出R的关系矩阵;

(3)说明R是否具有自反、反自反、对称、反对称性质。

构造命题公式的真值表。

K_n是n个结点的完全图，则K₁₀有_______条边，每个结点的度数为_______。

如题24图所示的格中，b的补元是________，c的补元是________。

设A={<2，2>，<3，5>，<3，4>}，B={<1，3>，<2，5>，<3，4>}，则dom(A ∩ B)=_________，ran(A U B)= ________。

设f(x)=2-x2，g(x)=2x+1，那么复合函数(f。g)(x)= ________，(g。f)(x)=________。

整数集Z中的运算 * 定义如下：a*b=a+b-3ab，则*运算的单位元为________;设a有逆元，则其逆元a^-1为________。

是一个群，其中，1的阶为________，9的阶为________。

公式的约束变元为________，自由变元为________。

设A={2，a}，B={1，2，3}，则A⊕B=________，A⊕?=________。

设R={<1,2>,<3,5>,<5,5>}和S={<4,2>,<5,1>,<2,3>}是集合A={1，2，3，4，5}上的两个关系，则R。S=________，S。R=________。

命题公式P→(P ∧ Q)的成真指派为________，成假指派为________。

设R₁，R₂是A上的两个关系，则下列描述错误的是()

• A.s(R₁∪ R₂)=s(R₁)∪ s(R₂)
• B.s(R₁∩ R₂)=s(R₁)∩ s(R₂)
• C.t(R₁∪ R₂))=t(R₁)∪ t(R₂)
• D.

下列必为欧拉图的是()

• A.结点度数都是偶数的连通图
• B.奇数度结点最多2个的连通图
• C.存在欧拉路的图
• D.无回路的连通图

设x={a}，下列关于代数系统的陈述正确的是()

• A.a是幺元
• B.X是幺元
• C.是幺元
• D.没有幺元

设简单图G所有结点的度数之和为18，则G的边数为()

• A.2
• B.3
• C.6
• D.9

下列无向图一定是树的是()

• A.连通图
• B.无回路但添加一条边则有回路的图
• C.每对结点之间都有通路的图
• D.有n个结点，n-1条边的图

在整数集Z上，下列定义的运算满足结合律的是()

• A.a * b=|a-b|
• B.a * b=3a+b
• C.a * b=ab-1
• D.a * b=2ab

设 f:X→Y，g:Y→Z是函数，则下列陈述正确的是()

• A.若g^。f是入射的，则f是入射的
• B.若g^。f是满射的，则f是满射的
• C.若g是满射的，则g^。f是满射的
• D.若f是满射的，则g^。f是满射的

在整数集Z上，下列定义的运算能构成一个群的是()

• A.a*b=max{a，b}
• B.a*b=a-b
• C.a*b=a+b+1
• D.a*b=ab

设A∪B=A，则有()

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

设，则其幂集P(A)的元素总个数为()

• A.0
• B.1
• C.2
• D.4

下列等价式错误的是()

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

设A(x)：x是实数，B(x)：x是有理数，命题“有的实数是有理数”符号化为()

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

设X={a，{a}，{a，{a}}}，则下列陈述错误的是()

• A.{a}∈X
• B.
• C.
• D.{{a}}∈X

设P：他用功，Q：他成绩好，命题“只有他用功，他成绩才好”符号化正确的是()

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

下列命题公式是永真式的是()

• A.P ∨ ￢Q
• B.(P→￢Q)∨ P
• C.P ∨(￢P ∧ Q)
• D.(P ∨ Q)∨ Q