眼睛起针眼-网通宽带电话

离散数学试题（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)对任意的x
1
、x
2
∈A，若x
1
≠x
2
，则由fg是单射得 fg(x
1
)≠fg(x
2
)，于是f(g(x
1
)) ≠f(g(x
2
))，必有
g(x
1
)≠g(x
2
)。所以，g是单射。
六、（15分）设R是集合A上的一个具有传递和自反性质的关系，T是A上的 关系，使得Tb>R且R，证明T是一个等价关系。
证明 因R自反，任意a∈A，有∈R，由T的定义，有∈T，故T自反。 < br>若∈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*b
－
1
∈H。
证明 必要性：对任意的a、b∈H，由是的子群，必有b∈H，从而a*b∈H。
充分性：由H非空，必存在a∈H。于是e＝a*a
－
1
∈H。
任 取a∈H，由e、a∈H得a
－
1
＝e*a
－
1
∈H。 < br>对于任意的a、b∈H，有a*b＝a*(b
－
1
)
－
1∈H，即a*b∈H。
又因为H是G非空子集，所以*在H上满足结合律。
综上可知，是的子群。
八、（15分）(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。
(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？
证明 (1)设无向图G中只有两个奇数度结点
u
和
v
。从
u
开始 构造一条回路，即从
u
出发经关联结
点
u
的边
e
1
到达结点
u
1
，若
d(u
1
)
为偶数，则 必可由
u
1
再经关联
u
1
的边
e
2
到达结点
u
2
，如此继续下去，每
条边只取一次，直到另一个奇数度结点为 止，由于图G中只有两个奇数度结点，故该结点或是
u
或是
v
。
如果 是
v
，那么从
u
到
v
的一条路就构造好了。如果仍是
u
，该回路上每个结点都关联偶数条边，而
d(u)
是奇数，所以至少还有一条边关 联结点
u
的边不在该回路上。继续从
u
出发，沿着该边到达另一个结点
u

，
1
－
1
－
1
依次下去直到另一个 奇数度结点停下。这样经过有限次后必可到达结点
v
，这就是一条从
u
到v
的路。
(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达 不一定成立。下面有向
图中，只有两个奇数度结点
u
和
v
，
u
和
v
之间都不可达。



uw
v









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)

m
3
∨
m
5
∨
m
7
主析取范式

M
0
∧
M
1
∧
M
2
∧
M
4
∧
M
6
主合取范式
二、（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

(2)偏序集是否有最小元？
(3)偏序集中极大元和极小元的一般形式是什么？并说明理由。
解 偏序集不存在最大元和最小元，因为n＞2。
考察P(X)的哈斯图，最底层的顶点是空集 ，记作第0层，由底向上，第一层是单元集，第二层是二
元集，…，由|X|＝n，则第n－1层是X的 n－1元子集，第n层是X。偏序集与偏序集>相比，恰好缺少第0层和第n 层。因此的极小元就是X的所有单元集，即{x}，x∈X；而极大
元恰好是比X少一个元素 ，即X－{x}，x∈X。
四、（10分）设A＝{1，2，3，4，5}，R是A上的二元关系，且 R＝{<2，1>，<2，5>，<2，4>，
<3，4>，<4，4>，<5，2>}，求r(R)、 s(R)和t(R)。
解 r(R)＝R∪I
A
＝{<2，1>，<2，5>，< 2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，
3>，<4，4> ，<5，5>}
s(R)＝R∪R
－
1
＝{<2，1>，<2，5>，<2 ，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>}
R
2
＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}
R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}
R＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝ R
t(R)＝

R
＝{<2，1>，<2，5>，<2，4>，<3，4> ，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，
i1

342
i
<5，5>}。
五、（10分）设函数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)对任意的x
1
、x
2
∈A，若x
1
≠x
2
，则由fg是单射得 fg(x
1
)≠fg(x
2
)，于是f(g(x
1
)) ≠f(g(x
2
))，必有
g(x
1
)≠g(x
2
)。所以，g是单射。
六、（10分）有幺元且满足消去律的有限半群一定是群。
证明 设是一个有幺元且满足消去律的有限半群，要证是群，只需证明G的任一元
素a可 逆。
考虑a，a
2
，…，a
k
，…。因为G只有有限个元素，所以 存在k＞l，使得a
k
＝a
l
。令m＝k－l，有a
l
*e
＝a
l
*a
m
，其中e是幺元。由消去率得a
m
＝ e。
于是，当m＝1时，a＝e，而e是可逆的；当m＞1时，a*a
元是a
m-1
m-1
＝a
m-1
*a＝e。从而a是可逆的，其逆
。总之，a是可 逆的。
七、（20分）有向图G如图所示，试求：
(1)求G的邻接矩阵A。
5

(2)求出A
2
、A
3
和A
4
，v
1
到v
4
长度为1、2、3和4的路有多少？
(3)求出AA和AA，说明AA和AA中的第(2，2)元素和第(2，3)元素的意义。
(4)求出可达矩阵P。
(5)求出强分图。
解 (1)求G的邻接矩阵为：

0


0
A

0


0

1
0
1
1
0
1
0
0
1


1


1

0


TTTT

(2)由于

0

< br>0


0


0

1
2< br>1
0
1
0
1
1
1


1< br>

1

1



0
< br>
0
3
A

0


0

2
1
2
2
1
2
1
0
2


2


2

1



0


0


0


0

3
4
3
1
2
1
2
2
3


3


3

2


A
2

A
4

所以v
1
到v
4
长度为1、2、3和4的路的个数分别为1、1、2、3。
(3)由于

0


0
T
AA

0


0

0
3
0
2
0
1
1
1
0


2



1

3



2


1


2


1

1
2
1
0
2
1
2
2
1


0



1

1



AA
T
再由定理10.19可知，所以A
T
A的第(2，2)元素为3，表明那些 边以
v
2
为终结点且具有不同始结点的
数目为3，其第(2，3)元素为0， 表明那些边既以
v
2
为终结点又以
v
3
为终结点，并且具有 相同始结点的数
目为0。AA
T
中的第(2，2)元素为2，表明那些边以
v
2
为始结点且具有不同终结点的数目为2，其第(2，
3)元素为1，表明那些边既以
v
2
为始结点又以
v
3
为始结点，并且具有相同终结点的数 目为1。

0


0


0


0

1
0
1
1
0
1
0
0
1


1


1

0



0


0
+

0


0

1
2
1
0
1
0
1
1
1


1


1

1



0


0

0


0

2
1
2
2
1
2
1
0
2


2


2

1



0


0
+

0


0

3
4
3
1
2
1
2
2
3

0

3
0


30


02

7
7
7
4
4
4
4
3
1

7


7

4


(4) 因为
B
4
AAAA
234
+，所
以求可达矩阵为< br>
0


0
P

0


0


0


0


0


0

111


111
< br>
。
111

111


1
1< br>1
1
1
1
1
1
1

0
 
1


1
∧

11


1
1



0
1
1
10
1
1
1
0


1

1

1



0


0＝

0


0

0
1
11
0
1
1
1
0


1

1

1


(5)因为
PP
T< br>，所以{
v
1
}，{
v
2
，
v
3< br>，
v
4
}构成G的强分图。
6