资料：离散数学试题 (1).pdf

离散数学考试题库（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)若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)x1x2Ax1x2fgfg(x1)fg(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∈