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

构造下列推理的证明。如果他是计算机专业学生，他必修离散数学。如果他不是工商管理专业的学生，他必是计算机专业的学生。他没修离散数学。所以他是工商管理专业的学生。

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

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

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

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

设是一个群，H是G的子群，a∈G。

证明：aHa^-1是G的子群。

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

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

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

设={1，2，3，4，6，12}，≦为整除关系。

(1)画出的哈斯图;

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

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

(1)画出R的关系图;

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

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

构造命题公式的真值表。

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

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

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

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

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

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

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

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

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

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

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

下列必为欧拉图的是()

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

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

• A.无回路的图
• B.边数比结点数少1的图
• C.连通但任意删去一条边都不连通的图
• D.每对结点之间都有通路的图

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

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

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

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

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

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

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

• A.2
• B.4
• C.8
• D.16

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

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

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

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

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

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

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

设A∪B=B，则有()

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

下列等价式正确的是()

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

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

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

设P：天下雨，Q：我去爬山，命题“只要天不下雨，我就去爬山”符号化正确的是()

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