资源描述
.中央电大离散数学（本科）考试试题一、单项选择题（每小题 3 分，本题共 15 分）1若集合 A=1， 2，B=1，2，1 ，2，则下列表述正确的是( a )AAB，且 AB BB A，且 ABCAB，且 AB DAB ，且 AB2设有向图（a）、（b）、（c ）与（d）如图一所示，则下列结论成立的是 ( d )图一A（a）是强连通的 B（b）是强连通的C（c ）是强连通的 D（d）是强连通的3设图 G 的邻接矩阵为 01则 G 的边数为( b )A6 B5 C4 D34无向简单图 G 是棵树，当且仅当( a )AG 连通且边数比结点数少 1 BG 连通且结点数比边数少 1CG 的边数比结点数少 1 DG 中没有回路5下列公式 ( c )为重言式AP QPQ B(Q (PQ) (Q(PQ)C(P (QP)(P(PQ) D( P(PQ) Q1若集合 A=a，b，B= a，b， a，b ，则（ a ） AAB ，且 AB BAB，但 ABCAB，但 AB DAB，且 AB2集合 A=1, 2, 3, 4, 5, 6, 7, 8上的关系 R=|x+y=10 且 x, y A，则 R 的性质为（ b ） A自反的 B对称的C传递且对称的 D反自反且传递的3如果 R1 和 R2 是 A 上的自反关系，则 R1R 2，R 1R 2，R 1-R2 中自反关系有（ b ）个A0 B2 C1 D34如图一所示，以下说法正确的是 ( d ) A(a, e)是割边 B(a, e)是边割集C(a, e) ,( b, c)是边割集 D(d, e)是边割集图一5设 A（x）：x 是人，B（ x）：x 是学生，则命题“不是所有人都是学生”可符号化为（ c ） A( x)(A(x)B(x) B( x)(A(x)B(x) C(x)(A(x) B(x) D( x)(A(x)B(x)1设 A=a, b，B=1, 2，R 1，R 2，R 3 是 A 到 B 的二元关系，且 R1=, ，R 2=, , ，R3=, ，则（ b ）不是从 A 到 B 的函数AR 1 和 R2 BR 2 CR 3 DR 1 和 R32设 A=1, 2, 3, 4, 5, 6, 7, 8，R 是 A 上的整除关系，B =2, 4, 6，则集合 B 的最大元、最小元、上界、下界依次为 ( b )A8、2、8、2 B无、2、无、2C6、2、6、2 D8、1、6、13若集合 A 的元素个数为 10，则其幂集的元素个数为（ a ） A1024 B10 C100 D14设完全图 K 有 n 个结点(n2)，m 条边，当（ c ）时，K 中存在欧拉回路nAm 为奇数 Bn 为偶数 Cn 为奇数 D m 为偶数5已知图 G 的邻接矩阵为 .，则 G 有（ d ） A5 点，8 边 B6 点，7 边 C6 点，8 边 D5 点，7 边1若集合 A a，a ，1，2，则下列表述正确的是( c )Aa，aA B2ACa A D A2设图 G ，vV，则下列结论成立的是 ( c ) Adeg(v)=2 E B deg(v)=E C DVv)deg(vVdeg3命题公式（PQ）R 的析取范式是 ( d )A（PQ ）R B （PQ）R C （PQ）R D （PQ）R4如图一所示，以下说法正确的是 ( a )Ae 是割点 Ba, e 是点割集Cb, e是点割集 Dd是点割集5下列等价公式成立的为( b )AP QPQ BP (QP) P(PQ)CQ(P Q) Q(PQ) DP (PQ) Q1若 G 是一个汉密尔顿图，则 G 一定是( d )A平面图 B对偶图C欧拉图 D连通图2集合 A=1, 2, 3, 4上的关系 R=|x=y 且 x, y A，则 R 的性质为（ c ） A不是自反的 B不是对称的C传递的 D反自反3设集合 A=1，2，3，4，5，偏序关系 是 A 上的整除关系，则偏序集上的元素 5 是集合 A 的（ b ） A最大元 B极大元 C最小元 D极小元4图 G 如图一所示，以下说法正确的是 ( c ) A(a, d)是割边 B(a, d)是边割集C(a, d) ,(b, d)是边割集 D(b, d)是边割集图一5设 A（x）：x 是人，B（x）： x 是工人，则命题“有人是工人”可符号化为（ a ） A( x)(A(x)B(x) B( x)(A(x)B(x)C(x)(A(x) B(x) D( x)(A(x)B(x)1若集合 A a，a ，则下列表述正确的是( a )AaA BaACa ，a A DA2命题公式（P Q）的合取范式是 ( c )A （PQ） B （PQ）（PQ） C （PQ） D（PQ）3无向树 T 有 8 个结点，则 T 的边数为( b )A6 B7 C8 D9 4图 G 如图一所示，以下说法正确的是 ( b )Aa 是割点 Bb, c 是点割集Cb, d 是点割集 Dc 是点割集图一5下列公式成立的为( d )AP Q PQ BP Q PQCQP P DP(PQ) Q1 “小于 5 的非负整数集合”采用描述法表示为_a_Axx N, x,B,C, , , , D1,2,a,b, 4设 A=1, 2, 3, 4, 5, 6, 7, 8，R 是 A 上的整除关系，B=2, 4, 6，则集合 B 的最大元、最小元、上界、下界依次为_d_A8、1、6、1 B 8、2、8、2C6、2、6、2 D无、2、无、25有 5 个结点的无向完全图 K5 的边数为_a_A10 B20 C5 D256设完全图 K 有 n 个结点(n2)，m 条边，当_b_时，K 中存在欧拉回路nAn 为偶数 Bn 为奇数 Cm 为偶数 Dm 为奇数7一棵无向树 T 有 5 片树叶，3 个 2 度分支点，其余的分支点都是 3 度顶点，则 T 有_c_个顶点A3 B8C11 D138命题公式（PQ）R 的析取范式是_b_A （PQ）R B （PQ）RC （PQ） R D （PQ）R9下列等价公式成立的是_b_APQP Q B P(QP) P(PQ)CP (PQ) Q DQ(PQ) Q(PQ)10谓词公式 的类型是_c_)()xxxA蕴涵式 B永假式 C永真式 D非永真的可满足式二、填空题（每小题 3 分，本题共 15 分）6命题公式 的真值是 T （或 1） )(7若图 G=中具有一条汉密尔顿回路，则对于结点集 V 的每个非空子集 S，在 G 中删除 S 中的所有结点得到的连通分支数为 W，则 S 中结点数|S|与 W 满足的关系式为 W|S| 8给定一个序列集合000，001，01，10，0 ，若去掉其中的元素 0 ，则该序列集合构成前缀码9已知一棵无向树 T 中有 8 个结点，4 度，3 度，2 度的分支点各一个，T 的树叶数为 5 .10(x)(P( x)Q(x )R(x ，y)中的自由变元为 R(x，y ) 中的 y6若集合 A 的元素个数为 10，则其幂集的元素个数为 1024 7设 A=a，b，c，B=1，2，作 f：AB，则不同的函数个数为 8 8若 A=1,2，R=|xA, yA, x+y=10，则 R 的自反闭包为, 9结点数 v 与边数 e 满足 e=v-1 关系的无向连通图就是树6设集合 Aa，b，那么集合 A 的幂集是 ,a,b,a,b 7如果 R1 和 R2 是 A 上的自反关系，则 R1R 2，R 1R 2，R 1-R2 中自反关系有 2 个 8设图 G 是有 6 个结点的连通图，结点的总度数为 18，则可从 G 中删去 4 条边后使之变成树9设连通平面图 G 的结点数为 5，边数为 6，则面数为 3 10设个体域 Da, b，则谓词公式(x )A(x)（x ）B（x）消去量词后的等值式为 (A (a)A (b)( B（a）B（b）) 6设集合 A=0, 1, 2, 3，B=2, 3, 4, 5 ，R 是 A 到 B 的二元关系， ,yy且且则 R 的有序对集合为， ，7设 G 是连通平面图，v, e , r 分别表示 G 的结点数，边数和面数，则 v，e 和 r 满足的关系式 v-e+r=2 8设 G是有 6 个结点， 8 条边的连通图，则从 G 中删去 3 条边，可以确定图 G 的一棵生成树9无向图 G 存在欧拉回路，当且仅当 G 连通且所有结点的度数全为偶数10设个体域 D1,2，则谓词公式 消去量词后的等值式为 A(1)A(2)(x6命题公式 的真值是 T （或 1） )(PQ7若图 G=中具有一条汉密尔顿回路，则对于结点集 V 的每个非空子集 S，在 G 中删除 S 中的所有结点得到的连通分支数为 W，则 S 中结点数|S|与 W 满足的关系式为 W|S| 8给定一个序列集合000，001，01，10，0 ，若去掉其中的元素 0 ，则该序列集合构成前缀码9已知一棵无向树 T 中有 8 个结点，4 度，3 度，2 度的分支点各一个，T 的树叶数为 5 10(x)(P( x)Q(x )R(x ，y)中的自由变元为 R(x，y ) 中的 y6若集合 A 的元素个数为 10，则其幂集的元素个数为 1024 7设 A=a，b，c，B=1，2，作 f：AB，则不同的函数个数为 8 8若 A=1,2，R=|xA, yA, x+y=10，则 R 的自反闭包为, 9结点数 v 与边数 e 满足 e=v-1 关系的无向连通图就是树10设个体域 Da, b, c，则谓词公式 (x)A(x)消去量词后的等值式为 A (a) A (b) A （c）6若集合 A=1，3，5，7，B=2，4，6，8 ，则 AB= 空集（或） 7设集合 A=1，2，3上的函数分别为： f=,，g=,，则复合函数 gf =, , ,8设 G 是一个图，结点集合为 V，边集合为 E，则 G 的结点度数之和为 2|E|（或“边数的两倍” ） 9无向连通图 G 的结点数为 v，边数为 e，则 G 当 v 与 e 满足 e=v-1 关系时是树 10设个体域 D1, 2, 3， P(x)为“x 小于 2”，则谓词公式( x)P(x) 的真值为假（或 F，或 0） 6设集合 A=2, 3, 4，B=1, 2, 3, 4 ，R 是 A 到 B 的二元关系，,yyyR且且则 R 的有序对集合为， ， ，7如果 R 是非空集合 A 上的等价关系，a A，bA，则可推知 R 中至少包含， 等元素8设 G是有 4 个结点， 8 条边的无向连通图，则从 G 中删去 5 条边，可以确定图 G 的一棵生成树9设 G 是具有 n 个结点 m 条边 k 个面的连通平面图，则 m 等于 n+k210设个体域 D1, 2，A(x )为“x 大于 1”，则谓词公式 的真值为真（或 T，或 1）()x11设集合 A=1,2,3，用列举法写出 A 上的恒等关系 IA，全关系 EA：IA = _ IA =,；EA =,12设集合 Aa，b，那么集合 A 的幂集是 ,a,b,a,b13设集合 A=1,2,3，B =a,b，从 A 到 B 的两个二元关系 R=,， S=,，则 R-S=_ R-S=14设 G 是连通平面图，v, e, r 分别表示 G 的结点数，边数和面数，则 v，e 和 r 满足的关系式 v-e+r=215无向连通图 G 是欧拉图的充分必要条件是结点度数均为偶数16设 G是有 6 个结点， 8 条边的连通图，则从 G 中删去 3 条边，可以确定图 G 的一棵生成树17设 G 是完全二叉树，G 有 15 个结点，其中有 8 个是树叶，则 G 有_14_条边，G 的总度数是_28_，G 的分支点数是_7_18设 P，Q 的真值为 1，R，S 的真值为 0，则命题公式 的真值为_0_QSP)(19命题公式 的合取范式为 析取范式为)(Q)()(RP20设个体域为整数集，公式 真值为_1_)(yx11设集合 A=1,2,3,4，B= 3,4,5,6， 则 ：_3,4_， _1,2,3,4,5,6_A12设集合 A 有 n 个元素，那么 A 的幂集合 P(A)的元素个数为 13设集合 A=a,b,c,d，B= x,y,z，R =,则关系矩阵 MR 0114设集合 A=a,b,c,d,e， A 上的二元关系 R=,， S=,， 则 RS=,.15无向图 G 存在欧拉回路，当且仅当 G 连通且_所有结点的度数全为偶数16设连通平面图 G 的结点数为 5，边数为 6，则面数为 3 17设正则二叉树有 n 个分支点，且内部通路长度总和为 I，外部通路长度总和为 E，则有 E=_ I+2n18设 P，Q 的真值为 0，R，S 的真值为 1，则命题公式 的真值为_1_)()(SQRP19已知命题公式为 G(PQ) R，则命题公式 G 的析取范式是(P Q)R20谓词命题公式(x )(P(x) Q(x)R(x，y )中的约束变元为_x_三、逻辑公式翻译（每小题 4 分，本题共 12 分）11将语句“如果所有人今天都去参加活动，则明天的会议取消 ”翻译成命题公式设 P：所有人今天都去参加活动，Q：明天的会议取消， （1 分）P Q （4 分）12将语句“今天没有人来 ” 翻译成命题公式设 P：今天有人来， （1 分） P （ 4 分）13将语句“有人去上课 ” 翻译成谓词公式设 P(x)：x 是人，Q(x)：x 去上课， （1 分）(x)(P(x) Q(x) （4 分）11将语句“如果你去了，那么他就不去 ”翻译成命题公式设 P：你去， Q：他去， （1 分）PQ （4 分）12将语句“小王去旅游，小李也去旅游 ”翻译成命题公式设 P：小王去旅游，Q：小李去旅游， （1 分）PQ （4 分）13将语句“所有人都去工作 ”翻译成谓词公式设 P(x)：x 是人，Q(x)：x 去工作， （ 1 分）(x)(P(x)Q(x) （4 分）11将语句“他不去学校 ”翻译成命题公式设 P：他去学校， （1 分） P （ 4 分）12将语句“他去旅游，仅当他有时间 ”翻译成命题公式设 P：他去旅游，Q：他有时间， （1 分）P Q （4 分）13将语句“所有的人都学习努力 ”翻译成命题公式设 P(x)：x 是人，Q(x)：x 学习努力， （1 分）（x）(P(x) Q(x) （3 分）11将语句“尽管他接受了这个任务，但他没有完成好 ”翻译成命题公式设 P：他接受了这个任务，Q：他完成好了这个任务， （2 分）P Q （6 分）12将语句“今天没有下雨 ”翻译成命题公式设 P：今天下雨， （2 分） P （6 分）11将语句“他是学生 ”翻译成命题公式设 P：他是学生， （2 分）则命题公式为： P （6 分）12将语句“如果明天不下雨，我们就去郊游 ”翻译成命题公式设 P：明天下雨，Q：我们就去郊游， （2 分）则命题公式为： P Q （6 分）11将语句“今天考试，明天放假 ”翻译成命题公式设 P：今天考试，Q：明天放假 （2 分）则命题公式为：PQ （6 分）12将语句“我去旅游，仅当我有时间 ”翻译成命题公式设 P：我去旅游， Q：我有时间， （2 分）则命题公式为：P Q （6 分） 将语句“如果明天不下雨，我们就去春游 ”翻译成命题公式 将语句“有人去上课 ” 翻译成谓词公式设命题 P 表示“ 明天下雨” ，命题 Q 表示“我们就去春游”.则原语句可以表示成命题公式 PQ. （5 分）设 P(x)：x 是人，Q(x)：x 去上课 则原语句可以表示成谓词公式 (x)(P(x) Q(x) 四、判断说明题（每小题 7 分，本题共 14 分）14P（P Q）P 为永真式正确 （3 分）P （ PQ） P 是由P（ PQ）与 P 组成的析取式，如果 P 的值为真，则P （PQ）P 为真， （5 分）如果 P 的值为假，则P 与 PQ 为真，即P（P Q）为真，也即P（P Q）P 为真，所以P（P Q）P 是永真式 （7 分）.15若偏序集的哈斯图如图一所示，则集合 A 的最大元为 a，最小元不存在正确 （3 分）对于集合 A 的任意元素 x，均有R（或 xRa） ，所以 a 是集合 A 中的最大元 （5 分）14如果 R1 和 R2 是 A 上的自反关系，则 R1R2 是自反的正确 （3 分）R1 和 R2 是自反的，x A， R1 ， R2 ， 则 R1R2， 所以 R1R2 是自反的 （7 分）15如图二所示的图 G 存在一条欧拉回路正确 （3 分）因为图 G 为连通的，且其中每个顶点的度数为偶数 （7 分）14设 N、R 分别为自然数集与实数集， f：NR，f (x)=x+6，则 f 是单射正确 （3 分）设 x1，x2 为自然数且 x1x2，则有 f(x1)= x1+6 x2+6= f(x2)，故 f 为单射 （7 分）15设 G 是一个有 6 个结点 14 条边的连通图，则 G 为平面图错误 （3 分）不满足“设 G 是一个有 v 个结点 e 条边的连通简单平面图，若 v3，则 e3v-6 ” 13下面的推理是否正确，试予以说明(1) （ x）F（x）G（ x） 前提引入(2) F（y）G（y） US（1） 错误 （3 分）（2）应为 F（y） G（x） ，换名时，约束变元与自由变元不能混淆 （7 分）14若偏序集的哈斯图如图二所示，则集合 A 的最大元为 a，最小元不存在错误 （3 分）集合 A 的最大元不存在，a 是极大元 （7 分）13下面的推理是否正确，试予以说明(1) （ x）F（x）G（ x） 前提引入(2) F（y）G（y） US（1） 错误 （3 分）（2）应为 F（y） G（x） ，换名时，约束变元与自由变元不能混淆 （7 分）14如图二所示的图 G 存在一条欧拉回路错误 （3 分）因为图 G 为中包含度数为奇数的结点 （7 分）13如果图 G 是无向图，且其结点度数均为偶数，则图 G 是欧拉图错误 （3 分）当图 G 不连通时图 G 不为欧拉图 （7 分）14若偏序集的哈斯图如图二所示，则集合 A 的最大元为 a，最小元是 f图二错误 （3 分）v1v2 v3v5 v4dbacefgh n图二.集合 A 的最大元与最小元不存在，a 是极大元，f 是极小元， 五计算题（每小题 12 分，本题共 36 分）16设集合 A=1，2，3，4，R=|x, yA；|x y|=1 或 xy=0，试（1）写出 R 的有序对表示；（2）画出 R 的关系图；（3）说明 R 满足自反性，不满足传递性（1）R=, （3 分）（2）关系图为（6 分）（3）因为, 均属于 R，即 A 的每个元素构成的有序对均在 R 中，故 R 在 A 上是自反的。 （9 分）因有与属于 R，但不属于 R，所以 R 在 A 上不是传递的。 17求 PQR 的析取范式，合取范式、主析取范式，主合取范式P（ RQ）P(RQ) PQR （析取、合取、主合取范式） （9 分）(P QR)(PQR) (PQR) (P QR) (PQR) (PQR) (PQR) （主析取范式） （12 分）18设图 G=，V= v1，v2，v3，v4，v5 ，E= (v1, v2)，(v1, v3)，(v2, v3) ，(v2, v4)，(v3, v4)，(v3, v5)，(v4, v5) ，试画出 G 的图形表示；写出其邻接矩阵；(3) 求出每个结点的度数；(4) 画出图 G 的补图的图形（1）关系图 （3 分）（2）邻接矩阵（6 分）010（3）deg( v1)=2deg(v2)=3deg(v3)=4deg(v4)=3deg(v5)=2 （9 分）（4）补图16设谓词公式 ，试)(),(),(),( yFzyRzxQyxP（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元（1）x 量词的辖域为 ， （2 分）,z 量词的辖域为 , （4 分）)(zy 量词的辖域为 （6 分）yR（2）自由变元为 与 中的 y，以及 中的 z),(zxyx(),(12 34v1v2v3 v4v5 v1v2v3 v4v5 .约束变元为 x 与 中的 z，以及 中的 y （12 分）),(yQ),(zR17设 A=1,2,1,2，B=1,2,1,2，试计算（1）（AB）； （2）（AB）； （3）AB（1）AB =1,2 （4 分）（2）AB =1,2 （8 分）（3）AB=，, 18设 G=，V= v1，v2，v3，v4，v5 ，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) ，(v3,v5)，(v4,v5) ，试（1）给出 G 的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形1）G 的图形表示为：（3 分）（2）邻接矩阵：（6 分）010（3）v1，v2，v3，v4，v5 结点的度数依次为 1，2，4，3，2 （9 分）（4）补图如下：16试求出（P Q）R 的析取范式，合取范式，主合取范式（P Q） R(PQ)R (PQ)R（析取范式） （3 分） (PR) (QR)（合取范式） （6 分） (PR)(QQ) (QR)(PP) (PRQ) (PR Q) (QRP)(QRP) (PQR)(PQR) (PQR) （主合取范式） （12 分）17设 A=a, b, 1, 2，B= a, b, 1, 1，试计算（1） （AB ） （2） （AB） （3） （AB ）（AB） （1） （AB ）=a, b, 2 （4 分）（2） （AB）=a, b, 1, 2, a, b, 1 （8 分）（3） （AB） （AB）=a, b, 2, a, b, 1 （12 分）18图 G=，其中 V= a, b, c, d, e，E= (a, b), (a, c), (a, e), (b, d), (b, e), (c, e), (c, d), (d, e) ，对应边的权值依次为2、1、2、3、6、1、4 及 5，试（1）画出 G 的图形； （2）写出 G 的邻接矩阵；（3）求出 G 权最小的生成树及其权值（1）G 的图形表示为： （3 分）（2）邻接矩阵：0110.（3）粗线表示最小的生成树， （10 分）权为 7： （12 分）15求（PQ） （R Q）的合取范式（P Q） （R Q）（P Q）（RQ） （4 分）(P Q)（RQ）(P RQ) (QRQ)(P RQ) R 合取范式 （12 分）16设 A=0，1， 2，3，4，R=|xA，yA 且 x+y|x A，yA 且 x+y3，试求 R，S，R S，R-1，S-1，r(R) R=, （2 分）S=, （4 分）RS=， （6 分）R-1=， （8 分）S-1= S， （10 分）r(R)=IA （12 分）17画一棵带权为 1, 2, 2, 3, 4 的最优二叉树,计算它们的权（10 分）权为 13+23+22+32+42=27 （12 分）15求（PQ） R 的析取范式与合取范式（P Q） R （PQ）R （4 分） (PQ)R （析取范式） （8 分） (PR) (QR) （合取范式） （12 分）16设 A=0，1， 2，3，R=|xA，yA 且 x+y|x A，yA 且 x+y2，试求 R，S，R S，S -1，r(R)R=, S=, （3 分）RS=， （6 分）S -1= S， （9 分）r(R)=IA=, （12 分）17画一棵带权为 1, 2, 2, 3, 4 的最优二叉树,计算它们的权最优二叉树如图三所示（10 分）图三权为 13+23+22+32+42=27 （12 分）15设谓词公式 ，试),(),()zxyByxA（1）写出量词的辖域； （2）指出该公式的自由变元和约束变元（1）x 量词的辖域为 ， （3 分）,z 量词的辖域为 , （6 分）)(zxyB（2）自由变元为 中的 y， （9 分）),(zxBA约束变元为 x 与 z （12 分）16设集合 A=1,1,2，B=1,1,2，试计算（1） （AB ） ； （2） （AB） ； （3）AB （1）AB =1,2 （4 分）（2）AB =1 （8 分）（3）AB=， （12 分）17设 G=，V= v1，v2，v3，v4 ，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) ，试（1）给出 G 的图形表示； （2）写出其邻接矩阵；（3）求出每个结点的度数； （4）画出其补图的图形 （10分）权为13+23+22+32+42=27 （12分） 1 22 3347 512 1 22 3347 512.（1）G 的图形表示为(如图三)：（3 分） （2）邻接矩阵：（6 分）01（3）v1，v2，v3，v4 结点的度数依次为 1，2，3，2 （9 分）（4）补图如图四所示：21化简下列集合表示式：)()()()( CBACBA= A= = 设 E 为全集E= )()(= = = A22设 ， ，求 ， ，并画出其图像,21|Rxx,0|RyBBA =B,|y= | x的图像如下图 1 所示的阴影部分图 1 图 2 =AB,1|,0|RxxRy= ,02| yx的图像如上图 2 所示的阴影部分23设 G=，V= v1，v2，v3，v4，v5 ，E= (v1,v3)，(v2,v3)，(v2,v4)，(v3,v4) ，(v3,v5)，(v4,v5) ，试： 给出 G 的图形表示； 画出其补图的图形 G 的图形表示见图 3； G 的补图的图形，见图 4.图 3 图 424构 造 权 为 2， 3， 4， 4， 5， 5， 7 的 最 优 树 。最优树如下图 5 所示21设 A，B 和 C 是全集 E 的子集，化简下列集合表示式：)()()( CBA= )(CBA= = )()(= (= 22设 A 1,2,3，用列举法给出 A 上的恒等关系 IA，全关系 EA，A 上的小于关系yxyxL及其逆关系和关系矩阵.（2 分）,AI3,1,3,2,1, E（2 分）（2 分）321,2LA 的逆关系 （2 分）,A. （2 分）0AM011ALM23图 G=，其图形如右图 1 所示。 写出 G 的邻接矩阵； 画出 G 的权最小的生成树以及计算出其权值 G 的邻接矩阵为： （4 分）0101 G 的权最小的生成树如右上图 1 所示 （4 分）最小的生成树的权为：1+1+5+2+3=12 （2 分）六、证明题（本题共 8 分）19试证明（x） （P（x）R（x） ） （ x）P（x）（ x）R（x） 证明： （1） （x） （P（x）R（x ） ） P（2）P（a）R（a） ES(1) （2 分）（3）P（a） T(2)I 图 1.（4） （x）P（x） EG(3) （4 分）（5）R（a） T(2)I（6） （x）R（x） EG(5) （6 分）（7） （x）P（x）（ x）R（ x） T(5)(6)I （2 分）19试证明集合等式 A (BC)=(AB) (AC) 证明：设 S= A (BC)，T=(AB) (A C)，若 xS，则 xA 或 xB C，即 xA 或 xB 且 xA 或 xC也即 xA B 且 xAC ，即 xT，所以 ST （4 分）反之，若 xT，则 xAB 且 xAC，即 xA 或 xB 且 xA 或 xC ，也即 xA 或 xBC，即 xS ，所以 TS因此 T=S 19试证明集合等式 A (BC)=(AB) (AC)证明：设 S= A (BC)，T=(AB) (A C)，若 xS，则 xA 或 xB C，即 xA 或 xB 且 xA 或 xC也即 xA B 且 xAC ，即 xT，所以 ST （4 分）反之，若 xT，则 xAB 且 xAC，即 xA 或 xB 且 xA 或 xC ，也即 xA 或 xBC，即 xS，所以 TS18设 G 是一个 n 阶无向简单图，n 是大于等于 2 的奇数证明 G 与 中的奇数度顶点个数相等( 是 G 的补图) 证明：因为 n 是奇数，所以 n 阶完全图每个顶点度数为偶数， （3 分）因此，若 G 中顶点 v 的度数为奇数，则在 中 v 的度数一定也是奇数， （6 分）所以 G 与 中的奇数度顶点个数相等 （8 分）18试证明集合等式 A (BC)=(AB) (AC) 证明：设 S= A (BC)，T=(AB) (A C)，若 xS，则 xA 或 xB C，即 xA 或 xB 且 xA 或 xC也即 xA B 且 xAC ，即 xT，所以 ST （4 分）反之，若 xT，则 xAB 且 xAC， 即 xA 或 xB 且 xA 或 xC，也即 xA 或 xBC，即 xS ，所以 TS因此 T=S 18设 A，B 是任意集合，试证明：若 AA=BB，则 A=B证明：设 xA，则 AA， （1 分）因为 AA=BB，故 BB，则有 xB， （3 分）所以 AB （5 分）设 xB，则BB，
展开阅读全文