(5)若R和S是自反的，则R∩S是自反的。 (6)若R和S是传递的，则R∪S是传递的。
解 (1)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R*S，故R*S也是自反的。
(2)不成立。例如，令A＝{1，2}，R＝{<1，2>}，S＝{<2，1>}，则R和S是反自反的，但R*S＝{<1，1>}不是反自反的。
(3)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，1>，<3，3>}，S＝{<2，3>，<3，2>}，则R和S是对称的，但R*S＝{<1，3>，<3，2>}不是对称的。
(4)不成立。例如，令A＝{1，2，3}，R＝{<1，2>，<2，3>，<1，3>}，S＝{<2，3>，<3，1>，<2，1>}，则R和S是传递的，但R*S＝{<1，3>，<1，1>，<2，1>}不是传递的。
(5)成立。对任意的a∈A，因为R和S是自反的，则∈R，∈S，于是∈R∩S，所以R∩S是自反的。
五、（15分）令X＝{x1，x2，?，xm}，Y＝{y1，y2，?，yn}。问 (1)有多少个不同的由X到Y的函数？
(2)当n、m满足什么条件时，存在单射，且有多少个不同的单射？ (3)当n、m满足什么条件时，存在双射，且有多少个不同的双射？
解 (1)由于对X中每个元素可以取Y中任一元素与其对应，每个元素有n种取法，所以不同的函数共nm个。
(2)显然当|m|≤|n|时，存在单射。由于在Y中任选m个元素的任一全排列都形成X到
mY的不同的单射，故不同的单射有Cnm!＝n(n－1)(n―m―1)个。
(3)显然当|m|＝|n|时，才存在双射。此时Y中元素的任一不同的全排列都形成X到Y的不同的双射，故不同的双射有m!个。
六、（5分）集合X上有m个元素，集合Y上有n个元素，问X到Y的二元关系总共有多少个？
解 X到Y的不同的二元关系对应X×Y的不同的子集，而X×Y的不同的子集共有个2mn，所以X到Y的二元关系总共有2mn个。
七、（10分）若
证明 设e是群
－
－
－
所以，x＝a1*b是a*x＝b的解。
－
若x?∈G也是a*x＝b的解，则x?＝e*x?＝(a1*a)*x?＝a1*(a*x?)＝a1*b＝x。所以，x
－
－
－
＝a1*b是a*x＝b的惟一解。
－
八、（10分）给定连通简单平面图G＝
证明 由偶拉公式得|V|－|E|＋|F|＝2，所以|F|＝2－|V|＋|E|＝8，于是?d(f)＝2|E|＝
f?F24。若存在f∈F，使得d(f)＞3，则3|F|＜2|E|＝24，于是|F|＜8，与|F|＝8矛盾。故对任意f∈F，d(f)＝3。
离散数学试题（B卷答案7）
一、（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)偏序集是否有最大元？ (2)偏序集是否有最小元？
(3)偏序集中极大元和极小元的一般形式是什么？并说明理由。 解 偏序集不存在最大元和最小元，因为n＞2。
考察P(X)的哈斯图，最底层的顶点是空集，记作第0层，由底向上，第一层是单元集，第二层是二元集，…，由|X|＝n，则第n－1层是X的n－1元子集，第n层是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∪R1＝{<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，
i?1?1>，<5，4>，<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)对任意的x1、x2∈A，若x1≠x2，则由f?g是单射得f?g(x1)≠f?g(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。
六、（10分）有幺元且满足消去律的有限半群一定是群。
证明 设
考虑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的邻接矩阵为：
?0??0A??0??0?101??011?
101??100??
(2)由于
?0??0A2??0??0?111??02??201?3?01A??
02111????02011???12??03??22??044A? ?0312????0101???23??13? 23??22??所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。 (3)由于
?0??0ATA??0??0?000??21??312??12 AAT???01121???10213???21??10? 21??21??再由定理10.19可知，所以ATA的第(2，2)元素为3，表明那些边以v2为终结点且具有不同始结点的数目为3，其第(2，3)元素为0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为0。AAT中的第(2，2)元素为2，表明那些边以v2为始结点且具有不同终结点的数目为2，其第(2，3)元素为1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为1。
(4)
?0??0B4?A?A2?A3?A4??0??0?101??0??011??0+
101??0???100???0因
111??0??201??0+
111??0???011???0212??03??122??04+
212??03???201???0123??13??23??22???0??0?0??0?为
741??747?，
747??434???0??0所以求可达矩阵为P??0??0??0??0(5)因为P?PT??0??0?111??111?。
111??111??111??0??111??1∧??1111???1111???000??0??111??0＝??1110???0111???000??111?，所以{v1}，{v2，v3，v4}
111??111??构成G的强分图。
离散数学试题（B卷答案8）
一、（10分）证明(P∨Q)∧(P?R)∧(Q?S)S∨R
证明 因为S∨R??R?S，所以，即要证(P∨Q)∧(P?R)∧(Q?S)?R?S。