1、离散数学考试试题(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
2、 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:乙参
3、加了比赛;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)
4、∨(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
5、 (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)
6、 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)
7、 T(5),EG
四、(10分)设A={a,b,c},试给出A上的一个二元关系R,使其同时不满足自反性、反自反性、对称性、反对称性和传递性。
解 设R={,,,},则
因为ÏR,R不自反;
因为∈R,R不反自反;
因为∈R,
8、 因为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上的关系,使得ÎTÛÎR且ÎR,证明T是一个等价关系。 证明
9、 因R自反,任意a∈A,有∈R,由T的定义,有∈T,故T自反。
若∈T,即∈R且∈R,也就是∈R且∈R,从而∈T,故T对称。
若∈T,∈T,即∈R且∈R,∈R且
10、Û对任意的a、b∈H有a*b-1∈H。
证明 必要性:对任意的a、b∈H,由
11、1)设无向图G中只有两个奇数度结点和。从开始构造一条回路,即从出发经关联结点的边到达结点,若为偶数,则必可由再经关联的边到达结点,如此继续下去,每条边只取一次,直到另一个奇数度结点为止,由于图G中只有两个奇数度结点,故该结点或是或是。如果是,那么从到的一条路就构造好了。如果仍是,该回路上每个结点都关联偶数条边,而是奇数,所以至少还有一条边关联结点的边不在该回路上。继续从出发,沿着该边到达另一个结点,依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点,这就是一条从到的路。 (2)若有向图G中只有两个奇数度结点,它们一个可达另一个结点或互相可达不一定成立。下面有向图中,只有两个奇数
12、度结点和,和之间都不可达。 离散数学考试试题(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)ÛAA A∧CÛØØ( A∧C)ÛØ( AC)Û(AC)(AC) A∨BÛØ(ØA∧ØB)ÛØ(( A
13、A)∧(BB))Û( AA)(BB) 所以 FÛ((AC)(AC))∨((BC)(BC)) Û(((AC)(AC))((AC)(AC)))(((BC)(BC))((BC)(BC))) (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) Û∨∨ 主析取范式 Û∧∧∧∧ 主合取范式 二、(10分)判断下列公式是否是永真式? (1)($xA(x)®$x
14、B(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))®$
15、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)偏序集中极大元和极小元的一般形式是什么?并说明理由。
16、解 偏序集不存在最大元和最小元,因为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={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>},求r(R)、s(R)和t(R)。
解 r(R) 17、=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∪R-1={<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
t(R)=Ri={< 18、2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>,<2,2>,<5,1>,<5,4>,<5,5>}。
五、(10分)设函数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(x 19、2),于是f(g(x1))≠f(g(x2)),必有g(x1)≠g(x2)。所以,g是单射。
六、(10分)有幺元且满足消去律的有限半群一定是群。
证明 设 20、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的邻接矩阵为:
(2)由于
所以v1到v4长度为1、2、3和4的路的个数分别为1、1、2、3。
(3)由于
再由定理10.19可知,所以ATA的第(2,2)元素为3,表明那些边以为终结点且具有不同始结点的数目为3,其第(2,3)元素为0,表明那些边既以为终结点又以为终结点,并且具有相同始结点的数目为0。AAT中的第(2,2)元素为2,表明那些边以为始结点且具有不同终结点的数目为2,其第(2,3)元素为1,表明那些边既以为始结点又以为始结点,并且具有相同终结点的数目为1。
(4)因为+++,所以求可达矩阵为。
(5)因为∧=,所以{},{,,}构成G的强分图。
6
©2010-2025 宁波自信网络信息技术有限公司 版权所有
客服电话:4009-655-100 投诉/维权电话:18658249818