发布时间 : 2024/5/20 10:01:00 星期一 文章离散数学试题更新完毕开始阅读e8f31e6baf1ffc4ffe47acce

离散数学考试试题（A卷及答案）

一、（10分）证明?(A∨B)??(P∨Q)，P，(B?A)∨?PA。 证明：(1)?(A∨B)??(P∨Q) P (2)(P∨Q)?(A∨B) T(1)，E (3)P P (4)A∨B T(2)(3)，I (5)(B?A)∨?P P

(6)B?A T(3)(5)，I (7)A∨?B T(6)，E (8)(A∨B)∧(A∨?B) T(4)(7)，I (9)A∧(B∨?B) T(8)，E (10)A T(9)，E

二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的：

(1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。

解 符号化命题，设A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。 依题意有，

(1)甲和乙只有一人参加，符号化为A?B?(?A∧B)∨(A∧?B)； (2)丙参加，丁必参加，符号化为C?D； (3)乙或丁至多参加一人，符号化为?(B∧D)； (4)丁不参加，甲也不会参加，符号化为?D??A。 所以原命题为：(A?B)∧(C?D)∧(?(B∧D))∧(?D??A)

?((?A∧B)∨(A∧?B))∧(?C∨D)∧(?B∨?D)∧(D∨?A)

?((?A∧B∧?C)∨(A∧?B∧?C)∨(?A∧B∧D)∨(A∧?B∧D))∧((?B∧D)∨(?B∧?A)∨(?D∧?A))

?(A∧?B∧?C∧D)∨(A∧?B∧D)∨(?A∧B∧?C∧?D)?T

但依据题意条件，有且仅有两人参加竞赛，故?A∧B∧?C∧?D为F。所以只有：(A∧?B∧?C∧D)∨(A∧?B∧D)?T，即甲、丁参加了围棋比赛。

三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。 (1)?x(P(x)?Q(x)) P

1

(2)P(y)?Q(y) T(1)，US (3)?xP(x) P (4)P(y) T(3)，ES (5)Q(y) T(2)(4)，I (6)?xQ(x) T(5)，EG

解 (4)中ES错，因为对存在量词限制的变元x引用ES规则，只能将x换成某个个体常元c，而不能将其改为自由变元。所以应将(4)中P(y)改为P(c)，c为个体常元。

正确的推理过程为：

(1)?xP(x) P (2)P(c) T(1)，ES (3)?x(P(x)?Q(x)) P (4)P(c)?Q(c) T(3)，US (5)Q(c) T(2)(4)，I (6)?xQ(x) T(5)，EG

四、（10分）设A＝{a，b，c}，试给出A上的一个二元关系R，使其同时不满足自反性、反自反性、对称性、反对称性和传递性。

解 设R＝{，，，}，则 因为?R，R不自反； 因为∈R，R不反自反；

因为∈R，?R，R不对称； 因为∈R，∈R，R不反对称；

因为∈R，∈R，但?R，R不传递。 五、（15分）设函数g：A→B，f：B→C， (1)若f?g是满射，则f是满射。 (2)若f?g是单射，则g是单射。

证明 因为g：A→B，f：B→C，由定理5.5知，f?g为A到C的函数。

(1)对任意的z∈C，因f?g是满射，则存在x∈A使f?g(x)＝z，即f(g(x))＝z。由g：A→B可知g(x)∈B，于是有y＝g(x)∈B，使得f(y)＝z。因此，f是满射。

(2)对任意的x1、x2∈A，若x1≠x2，则由f?g是单射得f?g(x1)≠f?g(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。

六、（15分）设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得?T??R且?R，证明T是一个等价关系。

证明 因R自反，任意a∈A，有∈R，由T的定义，有∈T，故T自反。

若∈T，即∈R且∈R，也就是∈R且∈R，从而∈T，故T对称。

2

若∈T，∈T，即∈R且∈R，∈R且∈R，因R传递，由∈R和∈R可得∈R，由∈R和∈R可得∈R，由∈R和∈R可得∈T，故T传递。

所以，T是A上的等价关系。

七、（15分）若是群，H是G的非空子集，则是的子群?对任意的a、b∈H有a*b1∈H。

－

证明 必要性：对任意的a、b∈H，由是的子群，必有b1∈H，从而a*b1∈H。

－

－

充分性：由H非空，必存在a∈H。于是e＝a*a1∈H。

－

任取a∈H，由e、a∈H得a1＝e*a1∈H。

－

－

对于任意的a、b∈H，有a*b＝a*(b1)1∈H，即a*b∈H。

－

－

又因为H是G非空子集，所以*在H上满足结合律。 综上可知，是的子群。

八、（15分）(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？

证明 (1)设无向图G中只有两个奇数度结点u和v。从u开始构造一条回路，即从u出发经关联结点u的边e1到达结点u1，若d(u1)为偶数，则必可由u1再经关联u1的边e2到达结点u2，如此继续下去，每条边只取一次，直到另一个奇数度结点为止，由于图G中只有两个奇数度结点，故该结点或是u或是v。如果是v，那么从u到v的一条路就构造好了。如果仍是u，该回路上每个结点都关联偶数条边，而d(u)是奇数，所以至少还有一条边关联结点u的边不在该回路上。继续从u出发，沿着该边到达另一个结点u1?，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。

(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两个奇数度结点u和v，u和v之间都不可达。

uwv

3

离散数学考试试题（B卷及答案）

一、（15分）设计一盏电灯的开关电路，要求受3个开关A、B、C的控制：当且仅当A和C同时关闭或B和C同时关闭时灯亮。设F表示灯亮。

(1)写出F在全功能联结词组{?}中的命题公式。 (2)写出F的主析取范式与主合取范式。

解 (1)设A：开关A关闭；B：开关B关闭；C：开关C关闭；F＝(A∧C)∨(B∧C)。 在全功能联结词组{?}中：

?A??(A∧A)?A?A

A∧C???( A∧C)??( A?C)?(A?C)?(A?C)

A∨B??(?A∧?B)??(( A?A)∧(B?B))?( A?A)?(B?B)

所以

F?((A?C)?(A?C))∨((B?C)?(B?C))

?(((A?C)?(A?C))?((A?C)?(A?C)))?(((B?C)?(B?C))?((B?C)?(B?C)))

(2)F?(A∧C)∨(B∧C)

?(A∧(B∨?B)∧C)∨((A∨?A)∧B∧C)

?(A∧B∧C)∨(A∧?B∧C)∨(A∧B∧C)∨(?A∧B∧C) ?m3∨m5∨m7 主析取范式 ?M0∧M1∧M2∧M4∧M6 主合取范式 二、（10分）判断下列公式是否是永真式？ (1)(?xA(x)??xB(x))??x(A(x)?B(x))。 (2)(?xA(x)??xB(x))??x(A(x)?B(x)))。 解 (1)(?xA(x)??xB(x))??x(A(x)?B(x))

?(??xA(x)∨?xB(x))??x(A(x)?B(x)) ??(??xA(x)∨?xB(x))∨?x(?A(x)∨B(x)) ?(?xA(x)∧??xB(x))∨?x?A(x)∨?xB(x)

?(?xA(x)∨?x?A(x)∨?xB(x))∧(??xB(x)∨?x?A(x)∨?xB(x)) ??x(A(x)∨?A(x))∨?xB(x) ?T

所以，(?xA(x)??xB(x))??x(A(x)?B(x))为永真式。

(2)设论域为{1，2}，令A(1)＝T；A(2)＝F；B(1)＝F；B(2)＝T。

则?xA(x)为假，?xB(x)也为假，从而?xA(x)??xB(x)为真；而由于A(1)?B(1)为假，所以?x(A(x)?B(x))也为假，因此公式(?xA(x)??xB(x))??x(A(x)?B(x))为假。该公式不是永真式。

三、（15分）设X为集合，A＝P(X)－{?}－{X}且A≠?，若|X|＝n，问 (1)偏序集是否有最大元？

4