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

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

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

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

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

构造下列推理的证明。如果他是侦探，他必精通逻辑推理。如果他不是清洁工，他必是侦探。他逻辑推理能力差。所以他是清洁工。

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

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

当且仅当a+b=c+d。

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

在代数系统中，若存在a∈A，有a*a=a，则称a为A的幂等元。

证明：在群中，除幺元e外不可能有任何别的幂等元。

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

(1)画出R的关系图;

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

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

设={1，6，9，12，18，36}，≦为整除关系。

(1)画出的哈斯图;

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

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

构造命题公式的真值表。

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

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

如题21图所示的格中，a的补元是________，d的补元是________。

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

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

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

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

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

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

下列必为欧拉图的是()

• A.奇数度结点最多2个的连通图
• B.可以一笔画的图
• C.存在欧拉路的图
• D.存在欧拉回路的图

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

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

• A.无回路的连通图
• B.无环的连通图
• C.每对结点之间都有通路的图
• D.结点数比边数多1的图

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

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

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

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

• A.6
• B.8
• C.12
• D.24

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

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

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

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

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

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

设，则有()

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

• 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→(P∨Q)

设P：他聪明，Q：他成绩好，命题“他虽然聪明但成绩不好”符号化正确的是()

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