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

《离散数学考试试题(A、B卷及答案)test》由会员分享，可在线阅读，更多相关《离散数学考试试题(A、B卷及答案)test（15页珍藏版）》请在装配图网上搜索。

1、离散数学考试试题（ A 卷及答案）一、（10 分）证明(AB)(PQ)，P，(BA)P A。证明：(1)(AB)(PQ) P(2)(PQ)(AB) T(1)，E(3)P P(4)AB T(2)(3)，I(5)(BA)P P(6)BA T(3)(5)，I(7)AB T(6)，E(8)(AB)(AB) T(4)(7)，I(9)A(BB) T(8) ，E(10)A T(9)，E二、（10 分）甲、乙、丙、丁 4 个人有且仅有 2 个人参加围棋优胜比赛。关于谁参加竞赛，下列 4 种判断都是正确的：(1)甲和乙只有一人参加；(2)丙参加，丁必参加；(3)乙或丁至多参加一人；(4)丁不参加，甲也不会参加。

2、请推出哪两个人参加了围棋比赛。解符号化命题，设 A：甲参加了比赛；B：乙参加了比赛；C：丙参加了比赛；D：丁参加了比赛。依题意有，(1)甲和乙只有一人参加，符号化为 A B(AB)(AB)；(2)丙参加，丁必参加，符号化为 CD；(3)乙或丁至多参加一人，符号化为(BD)；(4)丁不参加，甲也不会参加，符号化为DA。所以原命题为：(A B)(CD)(BD)(DA)(AB)(AB)(CD)(BD)(DA)(A B C) (A B C) (A B D) (A B D) (B D) (B A) (D A)(ABCD)(ABD)(ABCD)T但依据题意条件，有且仅有两人参加竞赛，故ABCD 为 F。所

3、以只有：(ABC D)(ABD)T，即甲、丁参加了围棋比赛。三、（10 分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。(1) x(P(x)Q(x) P1 21 21 2 1 2 1 2 (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(

4、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 分）设 Aa，b，c，试给出 A 上的一个二元关系 R，使其同时不满足自反性、反自反性、 对称性、反对称性和传递性。解 设 R，则因为 R，R 不自反；因为R，R 不反自反；因为R， R，R 不对称；因为R，R，R 不反对称；因为R，R，但 R，R 不传递。五、（15 分）设函数 g：AB，f：BC，(1)若 fog 是满射，则 f 是满射。(2)若 fog 是单射，则 g 是单射。证明 因为 g：AB，f：BC，由定

5、理 5.5 知，fog 为 A 到 C 的函数。(1)对任意的 zC，因 fog 是满射，则存在 xA 使 fog(x)z，即 f(g(x)z。由 g：AB 可知 g(x) B，于是有 yg(x)B，使得 f(y)z。因此，f 是满射。(2)对任意的 x 、x A，若 x x ，则由 fog 是单射得 fog(x )fog(x )，于是 f(g(x )f(g(x )，必有 g(x )g(x )。所以，g 是单射。六、（15 分）设 R 是集合 A 上的一个具有传递和自反性质的关系，T 是 A 上的关系，使得 T R 且 R，证明 T 是一个等价关系。证明 因 R 自反，任意 aA，有R，由 T

6、 的定义，有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、bH 有 a*b 1H。证明 必要性：对任意的 a、bH，由是的子群，必有 b 1H，从而 a*b1H。充分性：由 H 非空，必存在 aH。于是 ea*a 1H。 任取 aH，由 e、aH 得 a 1e*a 1H。对于任意的 a、bH，有 a *ba*(b 1)1H，即 a*bH。又

7、因为 H 是 G 非空子集，所以*在 H 上满足结合律。综上可知，是的子群。八、（15 分）(1)若无向图 G 中只有两个奇数度结点，则这两个结点一定是连通的。 (2)若有向图 G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？证明 (1)设无向图 G 中只有两个奇数度结点u和v。从u开始构造一条回路，即从u出发经关联结点 u 的边 e 到达结点 u ，若 d (u ) 1 1 1为偶数，则必可由 u 再经关联 u 的边 e 到达结点 u ，如此继续下去，每1 1 2 2条边只取一次，直到另一个奇数度结点为止，由于图 G 中只有两个奇数度结点，故该结点或是u或是v。如果是 v ，那

8、么从 u 到 v 的一条路就构造好了。如果仍是 u ，该回路上每个结点都关联偶数条边，而d (u ) 是奇数，所以至少还有一条边关联结点 u 的边不在该回路上。继续从 u 出发，沿着该边到达另一个结点 u ，1依次下去直到另一个奇数度结点停下。这样经过有限次后必可到达结点v，这就是一条从u到v的路。(2)若有向图 G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达不一定成立。下面有向 图中，只有两个奇数度结点 u 和 v ， u 和 v 之间都不可达。u w v离散数学考试试题（ B 卷及答案）一、（15 分）设计一盏电灯的开关电路，要求受3 个开关 A、B、C 的控制：当且仅当 A

9、和 C 同时关 闭或 B 和 C 同时关闭时灯亮。设 F 表示灯亮。(1)写出 F 在全功能联结词组 中的命题公式。(2)写出 F 的主析取范式与主合取范式。解(1)设 A：开关 A 关闭；B：开关 B 关闭；C：开关 C 关闭；F(AC)(BC)。在全功能联结词组 中：AAC(AA) AA( AC)( AC) (AC)(AC)AB(AB) ( AA)(BB) ( AA)(BB)所以F (AC)(AC)(BC)(BC)(AC)(AC)(AC)(AC)(BC)(BC)(BC)(BC)(2)F (AC)(BC)(A(BB)C)(AA)BC)(ABC)(A m m m3 5 7BC)(ABC)(AB

10、C)主析取范式M M M M M 0 1 2 46主合取范式二、（10 分）判断下列公式是否是永真式？(1)(2)(xA(x) xA(x)xB(x) xB(x)x(A(x)B(x)。 x(A(x)B(x)。解(1)( xA(x)xB(x)x(A(x)B(x)(xA(x) xA(x)xB(x) xB(x)x(A(x)B(x)A(x)B(x) x(xA(x) xA(x)xxB(x) A(x)A(x) xxB(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

11、；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 为集合，AP(X) X且 A ，若|X |n，问 (1)偏序集是否有最大元？A 1 21 21 2 1 2 1 2 (2)偏序集是否有最小元？(3)偏序集中极大元和极小元的一般形式是什么？并说明理由。解偏序集不存在最大元和最小元，因为 n2。考察 P(X)的哈斯图，最底层的顶点是空集，记作第 0 层，由底向上，第一层是单元集，第二层是二元集，由|

12、X|n，则第 n1 层是 X 的 n1 元子集，第 n 层是 X。偏序集与偏序集相比，恰好缺少第 0 层和第 n 层。因此的极小元就是 X 的所有单元集，即x，xX；而极大元恰好是比 X 少一个元素，即 Xx，xX。四、（10 分）设 A1，2，3，4，5，R 是 A 上的二元关系，且 R， ，求 r(R)、s(R)和 t(R)。解r(R)RI ，s(R)RR1， R2，R3，R4，R2t(R) U Ri，i =1。五、（10 分）设函数 g：AB，f：BC，(1)若 fog 是满射，则 f 是满射。(2)若 fog 是单射，则 g 是单射。证明 因为 g：AB，f：BC，由定理 5.5 知，

13、fog 为 A 到 C 的函数。(1)对任意的 zC，因 fog 是满射，则存在 xA 使 fog(x)z，即 f(g(x)z。由 g：AB 可知 g(x) B，于是有 yg(x)B，使得 f(y)z。因此，f 是满射。(2)对任意的 x 、x A，若 x x ，则由 fog 是单射得 fog(x )fog(x )，于是 f(g(x )f(g(x )，必有 g(x )g(x )。所以，g 是单射。六、（10 分）有幺元且满足消去律的有限半群一定是群。证明 设是一个有幺元且满足消去律的有限半群，要证是群，只需证明 G 的任一元 素 a 可逆。考虑 a，a2，ak，。因为G 只有有限个元素，所以存

14、在 kl，使得 akal。令 mkl，有 al*eal*am，其中 e 是幺元。由消去率得 ame。于是，当 m1 时，ae，而 e 是可逆的；当 m1 时，a*am-1am-1*ae。从而 a 是可逆的，其逆元是 am-1。总之，a 是可逆的。七、（20 分）有向图 G 如图所示，试求：1 4 2 3 0 1 14 0 1 1 4T T 2 1 3 2 3 44 + + + (1)求 G 的邻接矩阵 A。(2)求出 A2、A3和 A4，v 到 v 长度为 1、2、3 和 4 的路有多少？(3)求出 ATA 和 AAT，说明 ATA 和 AAT中的第(2，2)元素和第(2，3)元素的意义。(4

15、)求出可达矩阵 P。 (5)求出强分图。解(1)求 G 的邻接矩阵为：A =00001 0 1 0 1 1 1 0 11 0 0(2)由于A =00001 1 1 2 0 1 A =1 1 1 0 20 10 20 21 2 2 2 A =1 2 0 30 40 30 12 3 1 3 2 32 2所以 v 到 v 长度为 1、2、3 和 4 的路的个数分别为 1、1、2、3。 (3)由于A A =00000 0 0 3 1 2 AA =0 1 1 2 11 22 11 02 1 1 0 2 12 1再由定理 10.19 可知，所以 ATA 的第(2，2)元素为 3，表明那些边以 v 为终结点

16、且具有不同始结点的2数目为 3，其第(2，3)元素为 0，表明那些边既以v2为终结点又以v3为终结点，并且具有相同始结点的数目为 0。AAT中的第(2，2)元素为 2，表明那些边以 v 为始结点且具有不同终结点的数目为 2，其第(2，23)元素为 1，表明那些边既以v2为始结点又以v3为始结点，并且具有相同终结点的数目为 1。(4) 因为B = A +A +A +A =00001 0 1 0 0 1 1 0 1 0 1 0 1 0 0 01 1 1 0 2 2 0 1 0 1 1 1 1 0 2 0 1 1 0 21 2 0 3 2 2 0 41 2 0 3 0 1 0 12 3 1 3 2

17、32 2=00007 4 1 7 4 7 7 4 74 3 4，所以求可达矩阵为P =00001 1 11 1 11 1 11 1 1。(5)因为 P PT =00001 1 1 0 1 1 1 1 1 1 1 1 1 1 1 10 0 0 0 1 1 1 0 1 1 1 0 1 1 1 00 0 0 1 1 1 1 1 11 1 1，所以 v ， v ，v ，v 构成 G 的强分图。 1 2 3 4A A一、单项选择题(本大题共 15 小题，每小题 1 分，共 15 分)在每小题列出的四个选 项中只有一个选项是符合题目要求的，请将正确选项前的字母填在题后的括号内。1.一个连通的无向图 G，如

18、果它的所有结点的度数都是偶数，那么它具有一条( )2.设 G 是连通简单平面图，G 中有 11 个顶点 5 个面，则 G 中的边是( )3.在布尔代数 L 中，表达式(ab)(abc)(bc)的等价式是( )(ac)B.(ab)(ab)C.(ab)(abc)(bc)D.(bc)(ac)4.设 i 是虚数，是复数乘法运算，则 G=是群，下列是 G 的子群是( ) A. B. -1,C.i,D.-i,5.设 Z 为整数集，A 为集合，A 的幂集为 P(A),+、-、/为数的加、减、除运算，为集合的交 运算，下列系统中是代数系统的有( )A.Z，+，/ C.Z，-，/B.Z，/ D.P(A)，6.下

19、列各代数系统中不含有零元素的是( )A.Q，*Q 是全体有理数集，*是数的乘法运算B.Mn(R),*,Mn(R)是全体 n 阶实矩阵集合，*是矩阵乘法运算 C.Z， o ，Z 是整数集， o 定义为 x o xy=xy, x,yZD.Z，+，Z 是整数集，+是数的加法运算7.设 A=1,2,3，A 上二元关系 R 的关系图如下：R 具有的性质是8.设 A=a,b,c，A 上二元关系 R=a,a，b,b,a,c，则关系 R 的对称闭包 S(R)是( ) I I9.设 X=a,b,c,Ix 是 X 上恒等关系，要使 Ixa,b，b,c，c,a，b,aR 为 X 上的 等价关系，R 应取( )A.c

20、,a，a,c B.c,b，b,aC.c,a，b,a D.a,c，c,b10.下列式子正确的是( )A. B. C. D. 11.设解释 R 如下：论域 D 为实数集，a=0,f(x,y)=x-y,A(x,y):xy.下列公式在 R 下为真的是 ( )A.( x)(y)(z)(A(x,y)A(f(x,z),f(y,z)B.( x)A(f(a,x),a)C.( x)( y)（A(f(x,y),x)R 24341 21 2R R R R1 2n 1 2n 1 2 nA D.(x)(y)(A(x,y)A(f(x,a),a)12.设 B 是不含变元 x 的公式，谓词公式( x)(A(x)B)等价于( )

21、A.( $x)A(x)B B.( x)A(x)B C.A(x)B D.( x)A(x)( x)B13.谓词公式(x)(P(x,y)($z)Q(x,z)( y)R(x,y)中变元 x( )14.若 P：他聪明；Q：他用功；则“他虽聪明，但不用功”，可符号化为( )Q15.以下命题公式中，为永假式的是( )(pqr) B.(pp)pC.(qq)p D.(qp)(pp)二、填空题(每空 1 分，共 20 分)16.在一棵根树中，仅有一个结点的入度为_，称为树根，其余结点的入度均为_。 17.A=1,2,3,4 上二元关系 R= 2 ， 4 ，3 ， 3 ，4 ， 2 ， R 的关系矩阵 M 中m =

22、_,m =_。18.设s,*是群，则那么 s 中除_外，不可能有别的幂等元；若s,*有零元，则|s|=_。 19.设 A 为集合，P(A)为 A 的幂集，则P(A)，是格，若 x,yP(A),则 x,y 最大下界是_，最小上界是_。20.设函数 f:XY,如果对 X 中的任意两个不同的 x 和 x ，它们的象 y 和 y 也不同，我们说 f 是_函数，如果 ranf=Y，则称 f 是_函数。21.设 R 为非空集合 A 上的等价关系，其等价类记为xR。 x,yA，若x,yR，则 x 与y 的关系是_，而若x,y R，则x y =_。22. 使公式 ($x)($y)(A(x) B(y) ($x)

23、A(x) ($y)B(y) 成立的条件是 _ 不含有 y ，_不含有 x。23.设 M(x):x 是人，D(s):x 是要死的，则命题“所有的人都是要死的”可符号化为( x)_,其中量词( x)的辖域是_。H H 是_，则称 H1,H2,Hn 是相容的，若 H H H 是_，则称 H ,H ,H 是不相容的。25.判断一个语句是否为命题，首先要看它是否为 ，然后再看它是否具有唯一 的 。三、计算题 (共 30 分)26.(4 分)设有向图 G=(V,E)如下图所示，试用邻接矩阵方法求长度为 2 的路的总数和回路总数。27.(5)设 A=a,b,P(A)是 A 的幂集， 是对称差运算，可以验证是

24、群。设 n 是正整数，求(a-1ba)n a-nbnan 28.(6 分)设 A=1,2,3,4,5,A 上偏序关系R=1，2，3，2，4，1，4，2，4，3，3，5，4，5I ;1 2n R (1)作出偏序关系 R 的哈斯图(2)令 B=1,2,3,5，求 B 的最大，最小元，极大、极小元，上界，下确界，下界，下确界。 29.(6 分)求(PQ) (PQ)的主合取范式并给出所有使命题为真的赋值。30.(5 分)设带权无向图 G 如下，求 G 的最小生成树 T 及 T 的权总和，要求写出解的过程。31.(4 分)求公式(x)F(x,y)($y)G(x,y)($x)H(x)的前束范式。四、证明题

25、 (共 20 分)32.(6 分)设 T 是非平凡的无向树，T 中度数最大的顶点有 2 个，它们的度数为 k(k2),证明 T 中至少有 2k-2 片树叶。33.(8 分)设 A 是非空集合，F 是所有从 A 到 A 的双射函数的集合， o 是函数复合运算。证明：F, o是群。34.(6 分)在个体域 D=a ,a ,，a 中证明等价式：($x)(A(x)B(x) (x)A(x)($x)B(x)五、应用题(共 15 分)35.(9 分)如果他是计算机系本科生或者是计算机系研究生，那么他一定学过 DELPHI 语言而 且学过 C+语言。只要他学过 DELPHI 语言或者 C+语言，那么他就会编程

26、序。因此如果 他是计算机系本科生，那么他就会编程序。请用命题逻辑推理方法，证明该推理的有效结 论。36.(6 分)一次学术会议的理事会共有 20 个人参加，他们之间有的相互认识但有的 相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于 20。问能否把这 20 个人排在圆桌旁，使得任意一个人认识其旁边的两个人? 根据是什么?参考答案一、单项选择题(本大题共 15 小题，每小题 1 分，共 15 分)二、填空题16.0 117.1 018.单位元 1 y xy 20.入射 满射21.x =yR22.A(x) B(y)23.(M(x)D(x) M(x)D(x) 4 4ij2 ij24.可满

27、足式永假式(或矛盾式)25.陈述句 三、计算题真值26. M=11101 0 00 1 00 1 10 1 121 1 0M2=221 1 11 2 110 1 1 M 2 =18,i=1 j=14i =1M =6G 中长度为 2 的路总数为 18，长度为 2 的回路总数为 6。 27.当 n 是偶数时， xP(A),xn= 当 n 是奇数时， xP(A),xn=x于是：当 n 是偶数，(a-1ba)na-nbnan= (a-1)nbnan= = 当 n 是奇数时，(a-1ba)n a-nbnan=a-1ba (a-1)nbnan =a-1ba a-1ba= 28.(1)偏序关系 R 的哈斯图

28、为(2)B 的最大元：无，最小元：无；极大元：2，5，极小元：1，3下界：4， 下确界 4；上界：无，上确界：无 (PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(PQ)(P QPQ)(PQ)(PQ) (PQ)(PQ)(PQ)(PQ)P(QQ)P(QQ)(PQ)(PQ)命题为真的赋值是 P=1,Q=0 和 P=1,Q=11 1 32 4 63 2 54 3 65 2 36 1 27 1 48 4 39 3 510 5 6i i a a a a a =a =a =a a =a1 1 2 2 3 3 4 4 5 51 11 12 21 1 11 2 21 11 11 2 21 1 21 1

29、1 2 i i A A A A AA =(v ,v ), e =(v ,v )e =(v ,v ), e =(v ,v )e =(v ,v ), e =(v ,v )e =(v ,v ), e =(v ,v )e =(v ,v ), e =(v ,v )令 a 为 e 上的权，则1 2 3 4 5 6 7 8 9 10取 a 的 e T,a 的 e T,a 的 e T,a 的 e T,a 的 e T,即，T 的总权和=1+2+3+4+5=15 (x F(x ,y) $y G(x,y ) $x H(x ) (换名) $x$y (F(x ,y)G(x,y ) $x H(x ) xy (F(x ,y

30、 )G(x,y ) $x H(x ) x y $x (F(x ,y )G(x,y )H(x )四、证明题32.设 T 中有 x 片树叶，y 个分支点。于是 T 中有 x+y 个顶点，有 x+y-1 条边，由握手定理知 T 中所有顶点的度数之的x +yi=1d(v )=2(x+y-1)。又树叶的度为 1，任一分支点的度大于等于 2 且度最大的顶点必是分支点，于是x +yi=1d(v )x1+2(y-2)+k+k=x+2y+2K-4从而 2(x+y-1)x+2y+2k-4x2k-233.从定义出发证明：由于集合 A 是非空的，故显然从 A 到 A 的双射函数总是存在的，如 A 上恒等函数，因此 F

31、 非空(1)f,gF,因为 f 和 g 都是 A 到 A 的双射函数，故 fo g 也是 A 到 A 的双射函数，从而集合 F 关于运算 o 是封闭的。(2)f,g,hF,由函数复合运算的结合律有 fo (g o h)=(f o g) o h 故运算 o 是可结合的。(3)A 上的恒等函数 I 也是 A 到 A 的双射函数即 I F,且 fF 有 I o f=f o I =f,故 I 是F， o 中的幺元(4)fF,因为 f 是双射函数，故其逆函数是存在的，也是 A 到 A 的双射函数，且有 fo f-1=f-1o f=I ,因此 f-1是 f 的逆元由此上知F， o 是群34.证明($x)(

32、A(x)B(x) $x(A(x)B(x)1 1 1 2 2 n n 1 2 n 1 2 n 1 2 n 1 2 n 1 220i j i j i i i i ji j i1 i2 i20 i1 (A(a )B(a )(A(a )B(a )(A(a )B(a ) (A(a )A(a )A(a )(B(a )B(a )(B(a ) (A(a )A(a )A(a )(B(a )B(a )(B(a ) ( x)A(x)( $x)B(x) ( x)A(x)( $x)B(x)五、应用题35.令 p：他是计算机系本科生q：他是计算机系研究生r：他学过 DELPHI 语言s:他学过 C+语言t:他会编程序前提

33、：(pq)(rs),(rs)t结论：pt证p P(附加前提)pq TI(pq)(rs) P(前提引入)rs TIr TIrs TI(rs)t P(前提引入)t TI36.可以把这 20 个人排在圆桌旁，使得任一人认识其旁边的两个人。根据：构造无向简单图 G=,其中 V=v ,v ,，V 是以 20 个人为顶点的集合，E 中 的边是若任两个人 v 和 v 相互认识则在 v 与 v 之间连一条边。V V,d(v )是与 v 相互认识的人的数目，由题意知 v ,v V 有 d(v )+d(v ) 中存在汉密尔顿回路。20,于是 G设 C=V V V V 是 G 中一条汉密尔顿回路，按这条回路的顺序按

34、其排座 位即符合要求。A A 一、单项选择题（本大题共 15 小题，每小题 1 分，共 15 分）在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括 号内。错选、多选或未选均无分。1下列是两个命题变元 p，q 的小项是（ ）Appq BpqCpq Dppq2令 p：今天下雪了，q：路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（ ） Apq BpqCpq Dpq3下列语句中是命题的只有（ ）A1+1=10 Bx+y=10Csinx+siny0 Dx mod 3=24下列等值式不正确的是（ ）A( x)A ( $x)AB( x)(BA(x) B( x)A(x)C(

35、 $x)(A(x)B(x) ( $x)A(x)( $x)B(x)D( x)( y)(A(x)B(y) ( $x)A(x)( y)B(y)5谓词公式( $x)P(x,y)( x)(Q(x,z)( $x)( y)R(x,y,z)中量词 x 的辖域是（ ）A( x)Q(x,z)( $x)( y)R(x,y,z)BQ(x,z)( y)R(x,y,z)CQ(x,z)( $x)( y)R(x,y,z)DQ(x,z)6设 R 为实数集，函数 f：RR，f(x)=2x，则 f 是（ ）A满射函数 C双射函数B入射函数 D非入射非满射7设 A=a,b,c,d，A 上的等价关系 R=,I ，则对应于 R 的 A

36、的划 分是（ ）Aa,b,c,d Ba,b,c,dCa,b,c,d Da,b,c,d8设 A=，B=P(P(A)，以下正确的式子是（ ）A,B B,BC,B D,B9设 X，Y，Z 是集合，一是集合相对补运算，下列等式不正确的是（ ）A(X- Y)- Z=X- (YZ)B(X- Y)- Z=(X- Z)- YC(X- Y)- Z=(X- Z)- (Y- Z)D(X- Y)- Z=X- (YZ)10设*是集合 A 上的二元运算，称 Z 是 A 上关于运算*的零元，若（ ）A x A, 有 x*Z=Z*x=ZBZ A，且 x A 有 x*Z=Z*x=ZCZ A，且 x A 有 x*Z=Z*x=xD

37、Z A，且 $x A 有 x*Z=Z*x=Z11在自然数集 N 上，下列定义的运算中不可结合的只有（ ）Aa*b=min(a,b)1 1 2 2 n ni 1 21 2 Ba*b=a+bCa*b=GCD(a,b)(a,b 的最大公约数)Da*b=a(mod b)12设 R 为实数集，R+=x|xRx0，*是数的乘法运算，是一个群，则下列集合 关于数的乘法运算构成该群的子群的是（ ）AR+中的有理数 BR+中的无理数CR+中的自然数 D1，2，313设是环，则下列正确的是（ ）A是交换群C o 对*是可分配的14下列各图不是欧拉图的是（ ）B是加法群 D*对 o 是可分配的15设 G 是连通平面

38、图，G 中有 6 个顶点 8 条边，则 G 的面的数目是（ ）A2 个面 C4 个面B3 个面 D5 个面第二部分非选择题（共 85 分）二、填空题（本大题共 10 小题，每空 1 分，共 20 分）请在每小题的空格中填上正确答案。错填、不填均无分。16一公式为 之充分必要条件是其析取范式之每一析取项中均必同时包含一命题变元 及其否定；一公式为 之充分必要条件是其合取范式之每一合取项中均必同时包含 一命题变元及其否定。17前束范式具有形式(Q V )(Q V )(Q V )A，其中 Q (1in)为 ，A 为 的谓 词公式。18设论域是a,b,c，则( x)S(x)等价于命题公式 ；( $x

39、)S(x)等价于命题公式 。 19设 R 为 A 上的关系，则 R 的自反闭包 r(R)= ，对称闭包 s(R)= 。20某集合 A 上的二元关系 R 具有对称性，反对称性，自反性和传递性，此关系 R 是 ， 其关系矩阵是 。21设是一个偏序集，如果 S 中的任意两个元素都有 和 ，则称 S 关于 构成一个格。22设 Z 是整数集，在 Z 上定义二元运算*为 a*b=a+b+ab，其中+和是数的加法和乘法， 则代数系统的幺元是 ，零元是 。23如下平面图有 2 个面 R 和 R ，其中 deg(R )= ，deg(R )= 。2 524无向图 G 具有一条欧拉回路，当且仅当 G 是 ，并且所有

40、结点的度数都是 。 25在下图中，结点 v 的度数是 ，结点 v 的度数是 。三、计算题（本大题共 6 小题，第 2627 小题每小题 4 分，第 28、30 小题每小题 5 分，第 29、31 小题每小题 6 分，共 30 分）26（4 分）求出从 A=1,2到 B=x,y的所有函数，并指出哪些是双射函数，哪些是满射函 数。27（4 分）如果论域是集合a,b,c，试消去给定公式中的量词： ( $y)(x)(x +y =0) 。28（5 分）设 A=a,b,c ，P（A）是 A 的幂集， 是集合对称差运算。已知是群。 在群 中，找出其幺元。找出任一元素的逆元。求元素 x 使满足 a x=b。2

41、9（6 分）用等值演算法求公式(pq)(pq)的主合取范式30（5 分）画出 5 个具有 5 个结点 5 条边的非同构的无向连通简单图。31（6 分）在偏序集中，其中 Z=1,2,3,4,6,8,12,14，是 Z 中的整除关系，求集合 D=2,3,4,6的极大元，极小元，最大元，最小元，最小上界和最大下界。四、证明题（本大题共 3 小题，第 3233 小题每小题 6 分，第 34 小题 8 分，共 20 分） 32（6 分）用等值演算法证明(qs)r)(s(pr) (s(pq)r33（6 分）设 n 阶无向树 G=中有 m 条边，证明 m=n- 1。34（8 分）设 P=,1,1,2,1,2,3， 是集合 P 上的包含关系。（1）证明：是偏序集。（2）在（1）的基础上证明是全序集五、应用题(15 分）35（9 分）在谓词逻辑中构造下面推理的证明：每个在学校读书的人都获得知识。所以如果 没有人获得知识就没有人在学校读书。（个体域：所有人的集合）