离散数学2012年7月考试真题(02324)

今有a，b，c，d，e，f，g共7人，已知下列事实：a会讲汉语和英语;b会讲英语和韩语;c会讲英语和意大利语;d会讲法语、俄语和意大利语;e会讲俄语和韩语;f会讲汉语; g会讲法语和汉语。试问这7个人应如何排座位(圆桌)，才能使每个人和他身边的人交谈?

设G是有n个结点、n+1条边的简单连通图，且G中存在度数为5的结点。

证明：G中至少有一个度数为1的结点。

设A={l a，b为正整数}，在A上定义二元关系～如下：～当且仅当|a-b|=|c-d|。

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

构造下列推理的证明。

如果他有时间并且他有很多钱，他必去过桂林。如果他没有很多钱，他一定不会买小轿车。他有时间。他买了小轿车。所以他去过桂林。

设={1，3，5，9，15，45}，≦为整除关系。

(1)画出的哈斯图;

(2)求子集B={3，9，15}的极大元、极小元、最大元、最小元。

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

(1)画出R的关系图;

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

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

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

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

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

构造命题公式的真值表。

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

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

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

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

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

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

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

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

• A.0是幺元
• B.是幺元
• C.{0}是幺元
• D.没有幺元

下列必为欧拉图的是()

• A.有回路的连通图
• B.不可以一笔画的图
• C.有1个奇数度结点的连通图
• D.无奇数度结点的连通图

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

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

设R₁，R₂是A上的两个关系，s为对称闭包，t为传递闭包，则下列描述正确的是()

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

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

• A.6
• B.9
• C.12
• D.18

设，是函数，则下列陈述正确的是()

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

设A={a，{ b，c } }，则其幂集P(A)的元素总个数为()

• A.3
• B.4
• C.6
• D.8

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

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

设是群，则下列陈述不正确的是()

• A.(a^-1)^-1=a
• B.(ab)^-1=a^-1b^-1
• C.aⁿa^m=a^n+m
• D.(a^-1ba)ⁿ=a^-1bⁿa

设A∩B=B，则有()

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

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

设A(x)：x是鸟，B(x)：x会飞，“有的鸟不会飞”符号化为()

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

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

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

下列等价式正确的是()

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

设P：他看电影，Q：他学习，将命题“他在学习或在看电影”符号化正确的是()

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