离散数学考试试题(A、B卷及答案)test7_离散数学b卷及答案

2020-02-28 其他范文下载本文

离散数学考试试题(A、B卷及答案)test7由刀豆文库小编整理，希望给你工作、学习、生活带来方便，猜你可能喜欢“离散数学b卷及答案”。

离散数学考试试题（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)P

P(4)A∨B

T(2)(3)，I(5)(BA)∨P

P(6)BA

T(3)(5)，I(7)A∨B

T(6)，E(8)(A∨B)∧(A∨B)

T(4)(7)，I(9)A∧(B∨B)

T(8)，E(10)A

T(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＝{，，}，则因为R，R不自反；因为∈R，R不反自反；

因为∈R，R，R不对称；因为∈R，∈R，R不反对称；

因为∈R，∈R，但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)对任意的x1、x2∈A，若x1≠x2，则由fg是单射得fg(x1)≠fg(x2)，于是f(g(x1))≠f(g(x2))，必有g(x1)≠g(x2)。所以，g是单射。

六、（15分）设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得TR且R，证明T是一个等价关系。

证明

因R自反，任意a∈A，有∈R，由T的定义，有∈T，故T自反。

若∈T，即∈R且∈R，也就是∈R且∈R，从而∈T，故T对称。若∈T，∈T，即∈R且∈R，∈R且∈R，因R传递，由∈R和∈R可得∈R，由∈R和∈R可得∈R，由∈R和∈R可得∈T，故T传递。

所以，T是A上的等价关系。

七、（15分）若是群，H是G的非空子集，则是的子群对任意的a、b∈H有a*b1∈H。－证明

必要性：对任意的a、b∈H，由是的子群，必有b1∈H，从而a*b1∈H。

－

－充分性：由H非空，必存在a∈H。于是e＝a*a1∈H。

－任取a∈H，由e、a∈H得a1＝e*a1∈H。

－

－对于任意的a、b∈H，有a*b＝a*(b1)1∈H，即a*b∈H。

－

－又因为H是G非空子集，所以*在H上满足结合律。综上可知，是的子群。

八、（15分）(1)若无向图G中只有两个奇数度结点，则这两个结点一定是连通的。(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？

证明

(1)设无向图G中只有两个奇数度结点u和v。从u开始构造一条回路，即从u出发经关联结点u的边e1到达结点u1，若d(u1)为偶数，则必可由u1再经关联u1的边e2到达结点u2，如此继续下去，每条边只取一次，直到另一个奇数度结点为止，由于图G中只有两个奇数度结点，故该结点或是u或是v。如果是v，那么从u到v的一条路就构造好了。如果仍是u，该回路上每个结点都关联偶数条边，而d(u)是奇数，所以至少还有一条边关联结点u的边不在该回路上。继续从u出发，沿着该边到达另一个结点u1，依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。

(2)若有向图G中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向图中，只有两个奇数度结点u和v，u和v之间都不可达。

uwv离散数学考试试题（B卷及答案）

一、（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。偏序集与偏序集相比，恰好缺少第0层和第n层。因此的极小元就是X的所有单元集，即{x}，x∈X；而极大元恰好是比X少一个元素，即X－{x}，x∈X。

四、（10分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{，，，}，求r(R)、s(R)和t(R)。

解

r(R)＝R∪IA＝{，，，，，} s(R)＝R∪R1＝{，，，，} －R2＝{，，，} R3＝{，，，} R4＝{，，，}＝R2

t(R)＝Ri＝{，，，，，i1}。

五、（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分）有幺元且满足消去律的有限半群一定是群。

证明

设是一个有幺元且满足消去律的有限半群，要证是群，只需证明G的任一元素a可逆。

考虑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0A302111020111203220A4120301012313 2322所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。(3)由于

00TAA000002131212TAA

21011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。

00(4)因为B4AA2A3A40000以求可达矩阵为P00111111。

11111110100110+

101010001110



2010

1110



01102120312204+

2120320101231323220

000741



747，所