(1)?R 附加前提 (2)P?R P (3)?P T(1)(2)，I (4)P∨Q P (5)Q T(3)(4)，I (6)Q?S P (7)S T(5)(6)，I (8)?R?S CP (9)S∨R T(8)，E
二、（15分）根据推理理论证明：每个考生或者勤奋或者聪明，所有勤奋的人都将有所作为，但并非所有考生都将有所作为，所以，一定有些考生是聪明的。
设P(e)：e是考生，Q(e)：e将有所作为，A(e)：e是勤奋的，B(e)：e是聪明的，个体域：人的集合，则命题可符号化为：?x(P(x)?(A(x)∨B(x)))，?x(A(x)?Q(x))，??x(P(x)?Q(x))?x(P(x)∧B(x))。
(1)??x(P(x)?Q(x)) P (2)??x(?P(x)∨Q(x)) T(1)，E (3)?x(P(x)∧?Q(x)) T(2)，E (4)P(a)∧?Q(a) T(3)，ES (5)P(a) T(4)，I (6)?Q(a) T(4)，I (7)?x(P(x)?(A(x)∨B(x)) P (8)P(a)?(A(a)∨B(a)) T(7)，US (9)A(a)∨B(a) T(8)(5)，I (10)?x(A(x)?Q(x)) P
(11)A(a)?Q(a) T(10)，US (12)?A(a) T(11)(6)，I (13)B(a) T(12)(9)，I (14)P(a)∧B(a) T(5)(13)，I (15)?x(P(x)∧B(x)) T(14)，EG
三、（10分）某班有25名学生，其中14人会打篮球，12人会打排球，6人会打篮球
和排球，5人会打篮球和网球，还有2人会打这三种球。而6个会打网球的人都会打另外一种球，求不会打这三种球的人数。
解 设A、B、C分别表示会打排球、网球和篮球的学生集合。则：
|A|＝12，|B|＝6，|C|＝14，|A∩C|＝6，|B∩C|＝5，|A∩B∩C|＝2，|(A∪C)∩B|＝6。 因为|(A∪C)∩B|＝(A∩B)∪(B∩C)|＝|(A∩B)|＋|(B∩C)|－|A∩B∩C|＝|(A∩B)|＋5－2＝6，所以|(A∩B)|＝3。于是|A∪B∪C|＝12＋6＋14－6－5－3＋2＝20，|A?B?C|＝25－20＝5。故，不会打这三种球的共5人。
四、（10分）设A1、A2和A3是全集U的子集，则形如?Ai?(Ai?为Ai或Ai)的集合称
i?13为由A1、A2和A3产生的小项。试证由A1、A2和A3所产生的所有非空小项的集合构成全集U的一个划分。
证明 小项共8个，设有r个非空小项s1、s2、…、sr(r≤8)。
对任意的a∈U，则a∈Ai或a∈Ai，两者必有一个成立，取Ai?为包含元素a的Ai
或Ai，则a∈?Ai?，即有a∈?si，于是U??si。又显然有?si?U，所以U＝?si。
i?1i?1i?1i?1i?13rrrr任取两个非空小项sp和sq，若sp≠sq，则必存在某个Ai和Ai分别出现在sp和sq中，于是sp∩sq＝?。
综上可知，{s1，s2，…，sr}是U的一个划分。
五、（15分）设R是A上的二元关系，则：R是传递的?R*R?R。
证明 (5)若R是传递的，则
反之，若R*R?R，则对任意的x、y、z∈A，如果xRz且zRy，则
六、（15分）若G为连通平面图，则n－m＋r＝2，其中，n、m、r分别为G的结点数、边数和面数。
证明 对G的边数m作归纳法。
当m＝0时，由于G是连通图，所以G为平凡图，此时n＝1，r＝1，结论自然成立。 假设对边数小于m的连通平面图结论成立。下面考虑连通平面图G的边数为m的情况。
设e是G的一条边，从G中删去e后得到的图记为G?，并设其结点数、边数和面数
分别为n?、m?和r?。对e分为下列情况来讨论：
若e为割边，则G?有两个连通分支G1和G2。Gi的结点数、边数和面数分别为ni、mi和ri。显然n1＋n2＝n?＝n，m1＋m2＝m?＝m－1，r1＋r2＝r?＋1＝r＋1。由归纳假设有n1－m1＋r1＝2，n2－m2＋r2＝2，从而(n1＋n2)－(m1＋m2)＋(r1＋r2)＝4，n－(m－1)＋(r＋1)＝4，即n－m＋r＝2。
若e不为割边，则n?＝n，m?＝m－1，r?＝r－1，由归纳假设有n?－m?＋r?＝2，从而n－(m－1)＋r－1＝2，即n－m＋r＝2。
由数学归纳法知，结论成立。
七、（10分）设函数g：A→B，f：B→C，则： (1)f?g是A到C的函数；
(2)对任意的x∈A，有f?g(x)＝f(g(x))。
证明 (1)对任意的x∈A，因为g：A→B是函数，则存在y∈B使
对任意的x∈A，若存在y1、y2∈C，使得
综上可知，f?g是A到C的函数。
(2)对任意的x∈A，由g：A→B是函数，有
八、（15分）设
－
则R是G中的一个等价关系，且[a]R＝aH。
证明 对于任意a∈G，必有a1∈G使得a1*a＝e∈H，所以∈R。
－
－
若∈R，则a1*b∈H。因为H是G的子群，故(a1*b)1＝b1*a∈H。所以 － － － － a>∈R。 若∈R， － － － 1 *b)*(b1*c)＝a1*c∈H，故∈R。 － － 综上可得，R是G中的一个等价关系。 对于任意的b∈[a]R，有∈R，a1*b∈H，则存在h∈H使得a1*b＝h，b＝a*h， － － 于是b∈aH，[a]R?aH。对任意的b∈aH，存在h∈H使得b＝a*h，a1*b＝h∈H， － b>∈R，故aH?[a]R。所以，[a]R＝aH。 离散数学试题（B卷答案9） 一、（10分）证明(P∧Q∧A?C)∧(A?P∨Q∨C)?(A∧(P?Q))?C。 证明：(P∧Q∧A?C)∧(A?P∨Q∨C)?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?(?P∨?Q∨?A∨C)∧(?A∨P∨Q∨C) ?((?P∨?Q∨?A)∧(?A∨P∨Q))∨C ??((P∧Q∧A)∨(A∧?P∧?Q))∨C ??( A∧((P∧Q)∨(?P∧?Q)))∨C ??( A∧(P?Q))∨C ?(A∧(P?Q))?C。 二、（10分）举例说明下面推理不正确：?x?y(P(x)?Q(y))，?y?z(R(y)?Q(z))?x?z(P(x)?R(z))。 解：设论域为{1，2}，令P(1)＝P(2)＝T；Q(1)＝Q(2)＝T；R(1)＝R(2)＝F。则： ?x?y(P(x)?Q(y))??x((P(x)?Q(1))∨(P(x)?Q(2))) ?((P(1)?Q(1))∨(P(1)?Q(2)))∧((P(2)?Q(1))∨(P(2)?Q(2))) ?((T?T)∨(T?T))∧((T?T)∨(T?T)) ?T ?y?z(R(y)?Q(z))??y((R(y)?Q(1))∨(R(y)?Q(2))) ?((R(1)?Q(1))∨(R(1)?Q(2)))∧((R(2)?Q(1))∨(R(2)?Q(2))) ?((F?T)∨(F?T))∧((F?T)∨(F?T)) ?T 但 ?x?z(P(x)?R(z))??x((P(x)?R(1))∧(P(x)?R(2))) ?((P(1)?R(1))∧(P(1)?R(2)))∨((P(2)?R(1))∧(P(2)?R(2))) ?((T?F)∧(T?F))∨((T?F)∧(T?F)) ?F 所以，?x?y(P(x)?Q(y))，?y?z(R(y)?Q(z))?x?z(P(x)?R(z))不正确。 三、（15分）在谓词逻辑中构造下面推理的证明：所有牛都有角，有些动物是牛，所以，有些动物有角。 解：令P(x)：x是牛；Q(x)：x有角；R(x)：x是动物；则推理化形式为： ?x(P(x)?Q(x))，?x(P(x)∧R(x))?x(Q(x)∧R(x)) 下面给出证明： (1)?x(P(x)∧R(x)) P (2)P(a)∧R(a) T(1)，ES (3)?x(P(x)?Q(x)) P (4)P(a)?Q(a) T(3)，US (5)P(a) T(2)，I (6)Q(a) T(4)(5)，I (7)R(a) T(2)，I (8)Q(a)∧R(a) T(6)(7)，I (9)?x(Q(x)∧R(x)) T(8)，EG 四、（10分）证明(A∩B)×(C∩D)＝(A×C)∩(B×D)。 证明：因为 五、（15分）设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