离散数学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={1,2,3}，B={3,4,5}，则AA=___________，AB=___________。

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

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

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

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

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

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

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

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

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

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

谓词公式中变元x是(　　　)

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

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

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