离散数学考试试题（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)PP(4)A∨BT(2)(3)，I(5)(BA)∨PP(6)BAT(3)(5)，I(7)A∨BT(6)，E(8)(A∨B)∧(A∨B)T(4)(7)，I(9)A∧(B∨B)T(8)，E(10)AT(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中只有两个奇数度结点，它们一个可达另一个...