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

今要将6人分成3组(每组2个人)去完成3项任务。已知每个人至少与其余5个人中的3个人能相互合作。

(1)能否使得每组的2个人都能相互合作?

(2)你能给出几种不同的分组方案?

构造下面推理的证明。

每个喜欢步行的人都不喜欢坐汽车，每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车，因而有的人不喜欢步行。

设R是A上的自反和传递关系，如下定义A上的关系T，使得

证明：T是A上的等价关系。

设有G=，V的结点数|V|=n，称该图为n阶图，若从结点v_i到v_j存在路，证明：从vi到v_j必存在长度小于等于n-1的一条路。

给定图G如图所示，

(1)G中长度为4的路有几条?其中有几条回路?

(2)写出G的可达矩阵。

设(L，≤)是格，试证明：, 有a∧(b∨c)≥(a∧b)∨(a∧c);　a∨(b∧c)≤(a∨b)∧(a∨c)。

设A={a, b, c, d, e}，R为A上的关系，R={，，, , 　　e>,, }∪IA，试画的哈斯图，并求A中的最大元，最小元，极大元，　　极小元。

构造命题公式的真值表。

求下列公式的主析取范式和主合取范式：

设A={a，b，c，d}，A上的等价关系∪IA，画出R的关系图，并求出A中各元素的等价类。

给定集合A={1,2,3,4,5}，在集合A上定义两种关系：R={<1,2>,<3,4>,<2,2>}，S={<4,2>,<2,5>,<3,1>,<1,3>}，则

无向图G=如图所示，则G的最大度 Δ(G)=_____________，G的最小度δ(G)=_____________。

设图G，V={v₁,v₂,v₃,v₄}，若G的邻接矩阵，则deg-(v₁)=　　_________，deg+(v₄)=____________。

格L是分配格，当且仅当L既不含有与_____同构的子格，也不含有与_____同格的子格。

设f：R→R，f(x)=x+3;g：R→R，g(x)=2x+1，则复合函数

3个结点可构成________个不同构的简单无向图，可构成_______个不同构的简单有向图。

对于公式，其中P(x)：x=1，Q(x)∶x=2，当论域为{1，2}时，　　其真值为_____________ ，当论域为{0，1，2}时，其真值为_____________。

设A={1,2,3,4,5}，，R={<1,2>，<3,4>，<2,2>}，则R的自反闭包　　r(R)=__________。对称闭包t(R)=__________。

设P、Q为两个命题，德摩根律可表示为_____________，吸收律可表示为____________。

设D的结点数大于1，D=是强连通图，当且仅当(　　　)

• A.D中至少有一条通路
• B.D中至少有一条回路
• C.D中有通过每个结点至少一次的通路
• D.D中有通过每个结点至少一次的回路

设A={1,2,3}，B={3,4,5}，则AA=___________，AB=___________。

含有5个结点，3条边的不同构的简单图有(　　　)

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

设集合A={a，b，c}上的关系如下，具有传递性的是(　　　)

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

下列函数中为双射的是(　　　)

• A.f：Z→Z，f(j)=j(mod)
• B.f：N→N，
• C.f：Z→N，f(j)=|2j|+1
• D.f：R→R，f(r)=2r-15

下列集合对所给的二元运算封闭的是(　　　)

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

设集合A={1，2，3}，下列关系R中不是等价关系的是(　　　)

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

下列表达式中不成立的是(　　　)

• A.A∪(B⊕C)=(A∪B)⊕(A∪C)
• B.A ∩(B⊕C)=(A ∩ B)⊕(A ∩ C)
• C.(A⊕B)×C=(A×C)⊕(B×C)
• D.(A-B)×C=(A×C)-(B×C)

半群、群及独异点的关系是(　　　)

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

若个体域为整数域，下列公式中值为真的是(　　　)

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

下列命题中不正确的是(　　　)

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

设P={x|(x+1)2≤4}，Q={x|x2+16≥5x}，则下列选项正确的是(　　　)

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

谓词公式中变元x是(　　　)

• A.自由变元
• B.约束变元
• C.既不是自由变元也不是约束变元
• D.既是自由变元也是约束变元

下列命题为假命题的是(　　　)

• A.如果2是偶数，那么一个公式的析取范式惟一
• B.如果2是偶数，那么一个公式的析取范式不惟一
• C.如果2是奇数，那么一个公式的析取范式惟一
• D.如果2是奇数，那么一个公式的析取范式不惟一

下列命题联结词集合中，是最小联结词组的是(　　　)

• A.{ ￢，}
• B.{ ￢，∨，∧}
• C.{ ￢，∧}
• D.{∧，→}

设P：天下大雨，Q：他在室内运动，命题“除非天下大雨，否则他不在室内运动”可符号化为(　　　)

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