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分）若函数f：A→B是双射，则对任意x∈A，有f1(f(x))＝x。
－
证明 对任意的x∈A，因为f：A→B是函数，则 － 由f －1 是B到A的函数，于是可写为f1(f(x))＝x。 － 七、（10分）若G为有限群，则|G|＝|H|·[G:H]。 证明 设[G:H]＝k，a1、a2、…、ak分别为H的k个左陪集的代表元，由定理8.38得 G??[ai]R??aiH i?1i?1kk又因为对H中任意不同的元素x、y∈H及a∈G，必有a*x≠a*y，所以|a1H|＝…＝|akH|＝|H|。因此 |G|?|?aiH|?i?1k?|aH|?k|H|＝|H|·[G:H]。 ii?1k八、（20分）（1）画出3阶2条边的所有非同构有向简单图。 解：由握手定理可知，所画的有向简单图各结点度数之和为4，且最大出度和最大入度均小于或等于2。度数列与入度列、出度列为： 1、2、1：入度列为0、1、1或0、2、0或1、0、1；出度列为1、1、0或1、0、1或0、2、0 2、2、0：入度列为1、1、0；出度列为1、1、0 四个所求有向简单图如图所示。 （2）设G是n(n≥4)阶极大平面图，则G的最小度?≥3。 证明 设v是极大平面图G的任一结点，则v在平面图G－{v}的某个面f内。由于G－{v}是一个平面简单图且其结点数大于等于3，所以d(f)≥3。由G的极大平面性，v 与f上的结点之间都有边，因此d(v)≥3。由v的任意性可得，G的最小度?≥3。 离散数学试题（B卷答案10） 一、（10分）使用将命题公式化为主范式的方法，证明(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。 证明：因为(P?Q)?(P∧Q)??(?P∨Q)∨(P∧Q) ?(P∧?Q)∨(P∧Q) (Q?P)∧(P∨Q)?(?Q∨P)∧(P∨Q) ?(P∧?Q)∨(?Q∧Q)∨(P∧P) ∨(P∧Q) ?(P∧?Q)∨P ?(P∧?Q)∨(P∧(Q∨?Q)) ?(P∧?Q)∨(P∧Q)∨(P∧?Q) ?(P∧?Q)∨(P∧Q) 所以，(P?Q)?(P∧Q)?(Q?P)∧(P∨Q)。 二、（10分）证明下述推理： 如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。 解 设A：A努力工作；B、C、D分别表示B、C、D愉快；则推理化形式为： A?B∨C，B??A，D??CA??D (1)A 附加前提 (2)A?B∨C P (3)B∨C T(1)(2)，I (4)B??A P (5)A??B T(4)，E (6)?B T(1)(5)，I (7)C T(3)(6)，I (8)D??C P (9)?D T(7)(8)，I (10)A??D CP 三、（10分）证明?x?y(P(x)?Q(y))?(?xP(x)??yQ(y))。 ?x?y(P(x)?Q(y))??x?y(?P(x)∨Q(y)) ??x(?P(x)∨?yQ(y)) ??x?P(x)∨?yQ(y) ???xP(x)∨?yQ(y) ?(?xP(x)??yQ(y)) 四、（10分）设A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)?B。 解 P(A)＝{?，{?}，{1}，{{1}}，{?，1}，{?，{1}}，{1，{1}}，{?，1，{1}}} P(B)－{0}＝{?，{0}，{{0}}，{0，{0}}－{0}＝{?，{0}，{{0}}，{0，{0}} P(B)?B＝{?，{0}，{{0}}，{0，{0}}?{0，{0}}＝{?，0，{{0}}，{0，{0}} 五、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>} (1)画出R的关系图。 (2)写出R的关系矩阵。 (3)说明R是否是自反、反自反、对称、传递的。 解 (1)R的关系图如图所示： (2) R的关系矩阵为： ?1??0M(R)??1??1?101110110??0? ?0?0??(3)对于R的关系矩阵，由于对角线上不全为1，R不是自反的；由于对角线上存在非0元，R不是反自反的；由于矩阵不对称，R不是对称的； 经过计算可得 ?1??02M(R)??1??1?101110110??0??M(R)，所以R是传递的。 ?0?0??六、（15分）设函数f：R×R?R×R，f定义为：f( (3)求逆函数f。(4)求复合函数f?f和f?f。 证明 (1)对任意的x，y，x1，y1∈R，若f( (2)对任意的 －1－1 u?wu?wu?wu?w ，y＝，则f( u?wu?w －>＝ (3)f( －1 u?wu?w－1－1－1 ，>。(4)f?f( x－y>)＝< x?y?x?yx?y?(x?y)，>＝ 22f?f( 七、（15分）给定群 证明 对G中任意元a和b。 因为a*b＝(a*b)，所以a*a*b*b＝a*(a*b)*b，即得a*b＝(b*a)。同 3 3 3 3 3 3 2 2 2 5 5 5 3 3 3 4 4 4 ?13 ?1?1?1理，由a*b＝(a*b)可得，a*b＝(b*a)。由a*b＝(a*b)可得，a*b＝(b*a)。 于是(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。同理可得，(a*b)*(b*a)＝(b*a)＝a*b，即b*a＝a*b。 由于(a*b)*b＝a*b＝b*a＝b*(b*a)＝b*(a*b)＝(b*a)*b，故a*b＝b*a。 八、（15分）（1）证明在n个结点的连通图G中，至少有n－1条边。 证明 不妨设G是无向连通图（若G为有向图，可略去边的方向讨论对应的无向图）。 设G中结点为v1、v2、?、vn。由连通性，必存在与v1相邻的结点，不妨设它为v2（否则可重新编号），连接v1和v2，得边e1，还是由连通性，在v3、v4、?、vn中必存在与v1或v2相邻的结点，不妨设为v3，将其连接得边e2，续行此法，vn必与v1、v2、?、vn?1中的某个结点相邻，得新边en?1，由此可见G中至少有n－1条边。 （2）试给出|V|＝n，|E|＝(n－1)(n－2)的简单无向图G＝ 123 4 4 3 3 3 3 3 3 3 3 3 4 4 4 4 4 2 2 3 44433555444