离散数学考试试题(A、B卷及答案)test7.doc

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

离散数学考试试题（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)
Û∨∨ 主析取范式
Û∧∧∧∧ 主合取范式
二、（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)偏序集<A，Í>是否有最大元？
(2)偏序集<A，Í>是否有最小元？
(3)偏序集<A，Í>中极大元和极小元的一般形式是什么？并说明理由。
解 偏序集<A，Í>不存在最大元和最小元，因为n＞2。
考察P(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|＝n，则第n－1层是X的n－1元子集，第n层是X。偏序集<A，Í>与偏序集<P(X)，Í>相比，恰好缺少第0层和第n层。因此<A，Í>的极小元就是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∪IA＝{<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>}
R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}
R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>}
R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2
t(R)＝Ri＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
五、（10分）设函数g：A→B，f：B→C，
(1)若fog是满射，则f是满射。
(2)若fog是单射，则g是单射。
证明 因为g：A→B，f：B→C，由定理5.5知，fog为A到C的函数。
(1)对任意的z∈C，因fog是满射，则存在x∈A使fog(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，则由fog是单射得fog(x1)≠fog(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。
六、（10分）有幺元且满足消去律的有限半群一定是群。
证明 设<G，*>是一个有幺元且满足消去律的有限半群，要证<G，*>是群，只需证明G的任一元素a可逆。
考虑a，a2，…，ak，…。因为G只有有限个元素，所以存在k＞l，使得ak＝al。令m＝k－l，有al*e＝al*am，其中e是幺元。由消去率得am＝e。
于是，当m＝1时，a＝e，而e是可逆的；当m＞1时，a*am-1＝am-1*a＝e。从而a是可逆的，其逆元是am-1。总之，a是可逆的。
七、（20分）有向图G如图所示，试求：
(1)求G的邻接矩阵A。
(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？
(3)求出ATA和AAT，说明ATA和AAT中的第(2，2)元素和第(2，3)元素的意义。
(4)求出可达矩阵P。
(5)求出强分图。
解 (1)求G的邻接矩阵为：

(2)由于

所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。
(3)由于

再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以为终结点又以为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以为始结点又以为始结点，并且具有相同终结点的数目为1。
(4)因为+++，所以求可达矩阵为。
(5)因为∧＝，所以{}，{，，}构成G的强分图。
6