电大计算机本科离散数学考试题,中央电大离散数学(本科)考试试题(可编辑)

太过爱你忘了你带给我的痛 2022-10-19 05:48 242阅读 0赞

《中央电大离散数学(本科)考试试题(可编辑)》由会员分享，可在线阅读，更多相关《中央电大离散数学(本科)考试试题(可编辑)(33页珍藏版)》请在人人文库网上搜索。

1、中央电大离散数学(本科)考试试题一、单项选择题(每小题3分，本题共15分)1若集合A 1，2 ，B 1，2， 1，2 ，则下列表述正确的是 a AAA B BA BCAA B DAA B2设有向图(a)、(b)、(c)与(d)如图一所示，则下列结论成立的是 d 图一A(a)是强连通的 B(b)是强连通的C(c)是强连通的 D(d)是强连通的G的邻接矩阵为则G的边数为 b ABCD c 为重言式A P Q P Q B Q P Q Q P Q C Q P P P Q D P P Q Q1若集合A a，b ，B a，b， a，b ，则( a )AA B，且A B BA B，但A BCA B，但A B。

2、 DA B，且A B2集合A 1, 2, 3, 4, 5, 6, 7, 8 上的关系R x，y |x+y 10且x, yA ，则R的性质为( b )A自反的 B对称的C传递且对称的 D反自反且传递的3如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-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 。

3、A x B x D x A x B x 1设A a, b ，B 1, 2 ，R1，R2，R3是A到B的二元关系，且R1 a，2 , b，2 ，R2 a，1 , a，2 , b，1 ，R3 a，1 , b，2 ，则( b )不是从A到B的函数AR1和R2 BR2 CR3 DR1和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。

4、有n个结点 n2 ，m条边，当( c )时，K中存在欧拉回路Am为奇数 Bn为偶数 Cn为奇数 Dm为偶数5已知图G的邻接矩阵为 ，则G有( d ) A5点，8边 B6点，7边 C6点，8边 D5点，7边1若集合A a， a ， ，则下列表述正确的是 c A aa A B AC a A D A V，则下列结论成立的是 c Adeg v 2 E B deg v E C D3命题公式(PQ)R的析取范式是 d A (PQ)R B(PQ)R C(PQ)R D( P Q)R4如图一所示，以下说法正确的是 a Ae是割点 B a, e 是点割集C b, e 是点割集 D d 是点割集5下列等价公式成立的。

5、为 b A P Q P Q BP Q P P P Q C P Q Q P Q D P Q Q1若G是一个汉密尔顿图，则G一定是 d ABC D, 2, 3, 4 上的关系R x，y |x y且x, yA ，则R的性质为( c )A不是自反的 B不是对称的C传递的 D反自反3设集合A 1，2，3，4，5 ，偏序关系 是A上的整除关系，则偏序集 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。

6、是工人，则命题“有人是工人”可符号化为( 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 A a AB a AC aa A D APQ)的合取范式是 c A(PQ) B(PQ)(PQ) C(PQ) D ( P Q)3无向树T有8个结点，则T的边数为 b A图一5下列公式成立的为 d A P Q PQ BP Q P QC P P D PQ1“小于5的非负整数集合”采用描述法表示为\_\_\_a\_\_\_A x xN, x 5 B x xR, x 5 C x xZ, x 5 D x xQ, x 5 2设R1。

7、，R2是集合A a,b,c,d 上的两个关系，其中R1 a,a , b,b , b,c , d,d ，R2 a,a , b,b , b,c , c,b , d,d ，则R2是R1的\_\_b\_\_\_\_闭包A自反 B对称 C传递 D以上答案都不对3设函数f：RR，f a 2a+1；g：RR，g a a2，则\_\_\_c\_\_\_有反函数Afg Bgf Cf Dg 4已知图G的邻接矩阵为，则图G有\_\_\_d\_\_\_A5点，8边 B6点，7边 C6点，8边 D5点7边5无向完全图K4是\_\_\_a\_\_\_A汉密尔顿图 B欧拉图 C非平面图 D树6在5个结点的完全二叉树中，若有4条边，则有\_\_\_b\_\_\_片树叶A2 B3 C4。

8、 D57无向树T有7片树叶，3个3度结点，其余的都是4度结点，则T有\_\_c\_\_\_个4度结点A3 B2 C1 D08与命题公式P (Q R)等值的公式是 P Q R B P Q R C P Q R DP Q R 9谓词公式中量词 x的辖域是 B CP x D10谓词公式的类型是蕴涵式永假式 永真式 非永真的可满足式 B C D2若集合A的元素个数为10，则其幂集的元素个数为\_\_\_b\_\_\_A1000 B1024C1 D103设集合A 1,2 ，B a,b ，C ，则\_\_c\_\_\_\_A 1,a, , 1,b, , 2,a, , 2,b, B 1, a, , 1, b, , 2, a, , 2, b, 。

9、C 1,a , , 1,b , , 2,a , , 2,b , D 1,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中存在欧拉回路An为偶数 Bn为奇数 Cm为偶数 Dm为奇数7一棵无向树T有5片树叶，3个2度分支点，其余的分支点都是3度顶点，则T有\_\_c\_\_。

10、\_个顶点A3 B8C11 D138命题公式(PQ)R的析取范式是\_\_\_b\_\_\_A( P Q)R B (PQ)RC(PQ)R D(PQ)R9下列等价公式成立的是\_\_\_b\_\_\_A P Q P Q B P Q P P P Q C P P Q Q DQ P Q Q P Q 10谓词公式的类型是蕴涵式永假式 永真式 非永真的可满足式6命题公式的真值是 T (或1) 7若图G V, E 中具有一条汉密尔顿回路，则对于结点集V的每个非空子集S，在G中删除S中的所有结点得到的连通分支数为W，则S中结点数|S|与W满足的关系式为 W |S| 8给定一个序列集合 000，001，01，10，0 ，若去掉其中的元素。

11、 0 ，则该序列集合构成前缀码9已知一棵无向树T中有8个结点，4度，3度，2度的分支点各一个，T的树叶数为 5 10 x P x Q x R x，y中的变元R x，yA的元素个数为10，则其幂集的元素个数为 1024 7设A a，b，c ，B 1，2 ，作f：AB，则不同的函数个数为 8 8若A 1,2 ，R x, y |x A, y A, x+y 10 ，则R的自反闭包为 1,1 , 2,2 9结点数v与边数e满足 e v-1 关系的无向连通图就是树6设集合A a，b ，A的幂集是 , a,b , a , b 7如果R1和R2是A上的自反关系，则R1R2，R1R2，R1-R2中自反关系有 2。

12、 个 8设图G是有6个结点的连通图，结点的总度数为18，则可从G中删去 4 条边后使之变成树9设连通平面图G的结点数为5，边数为6，则面数为 3 10设个体域D a, 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的二元关系，则R的有序对集合为 2, 2 ， 2, 3 ， 3, 2 ， 3, 3 7设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r 2 8设G V, E 是有6个结点，8条边的连通图，则从G中删去 3 。

13、条边，可以确定图G的一棵生成树9无向图G存在欧拉回路，当且仅当G连通且所有结点的度数全为偶数10设个体域D 1,2 ，则谓词公式消去量词后的等值式为A 1 A 2 6命题公式的真值是 T (或1) 7若图G V, E 中具有一条汉密尔顿回路，则对于结点集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 。

14、x，yA的元素个数为10，则其幂集的元素个数为 1024 7设A a，b，c ，B 1，2 ，作f：AB，则不同的函数个数为 8 8若A 1,2 ，R x, y |x A, y A, x+y 10 ，则R的自反闭包为 1,1 , 2,2 9结点数v与边数e满足 e v-1 关系的无向连通图就是树10设个体域D a, b, c ，则谓词公式 x A x 消去量词后的等值式为A a A b A(c)6若集合A 1，3，5，7 ，B 2，4，6，8 ，则AB 空集(或 ) 7设集合上的函数分别为：f 10设个体域D 1, 2, 3 ， P x 为“x小于2”，则谓词公式 x P x 的真值为假(或F。

15、，或0)则R的有序对集合为 2, 2 ， 2, 3 ， 2, 4 ， 3, 3 ， 3, 4 ， 4, 4 7如果R是非空集合A上的等价关系，a A，b A，则可推知R中至少包含 a, a ， b, b 等元素8设G V, E 是有4个结点，8条边的无向连通图，则从G中删去 5 条边，可以确定图G的一棵生成树9设G是具有n个结点m条边k个面的连通平面图，则m等于n+k 210设个体域D 1, 2 ，A x 为“x大于1”，则谓词公式的真值为真(或T，或1)11设A 1,2,3 ，用列举法出A上的恒等关系IA，全关系EAIA \_\_ IA 1,1 , 2,2 , 3,3 ；EA 1,1 , 1,2。

16、 , 1,3 , 2,1 , 2,2 , 2,3 , 3,1 , 3,2 , 3,3 12设集合A a，b ，A的幂集是 , a , b , a,b 13设集合A 1,2,3 ，B a,b ，从A到B的两个二元关系R 1,a , 2,b ,3,a ，S 1,a , 2,a , 3,a ，则R-S \_ R-S 2,b 14设G是连通平面图，v, e, r分别表示G的结点数，边数和面数，则v，e和r满足的关系式v-e+r 215无向连通图G是欧拉图的充分必要条件是结点度数均为偶数16设G V, E 是有6个结点，8条边的连通图，则从G中删去 3 条边，可以确定图G的一棵生成树17设G是完全二叉树，。

17、G有15个结点，其中有8个是树叶，则G有\_\_\_\_14\_\_\_条边，G的总度数是\_\_\_28\_\_\_\_\_，G的分支点数是\_\_\_\_7\_\_\_\_18设P，Q的真值为1，R，S的真值为0，则命题公式的真值为\_\_\_0\_\_\_\_\_19命题公式的合取范式为析取范式为20设个体域为整数集，公式真值为设A 1,2,3,4 ，B 3,4,5,6 ，则：\_\_\_ 3,4 \_\_\_\_\_，\_\_\_\_\_ 1,2,3,4,5,6 \_\_\_\_\_12设集合A有n个元素，那么A的幂集合P A 的元素个数为 13设集合A ,b,c,d ，B x,y,z ，R a,x , a,z , b,y , c,z , d,y 则关系矩阵MR设集合A ,b,c,。

18、d,e ，A上的二元关系R a,b , c,d , b,b ，S d,b ,b,e , c,a ，则R?SG的结点数为5，边数为6，则面数为 3 17设正则二叉树有n个分支点，且内部通路长度总和为I，外部通路长度总和为E，则有E \_\_\_ I+2n18设P，Q的真值为0，R，S的真值为1，则命题公式的真值为\_\_\_\_\_1\_\_\_19已知命题公式为G P Q R则命题公式G的析取范式是 P Q R x P x Q x R x，y中的约束变元1111将语句“他不去学校”翻译成命题公式设P：他去学校， (1分)P (4分)12将语句“他去旅游，仅当他有时间”翻译成命题公式设 P：他去旅游，Q：他有时间， 。

19、(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将。

20、语句“今天考试，明天放假”翻译成命题公式设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(PQ)P为永真式正确 (3分)P(PQ)P是由。

21、P(PQ)与P组成的析取式，如果P的值为真，则P(PQ)P为真， (5分)如果P的值为假，则P与PQ为真，即P(PQ)为真，也即P(PQ)P为真，所以P(PQ)P是永真式 (7分)15若偏序集 A，R 的哈斯图如图一所示，则集合A的最大元为a，最小元不存在正确 (3分)对于集合A的任意元素x，均有 x, a R(或xRa)，所以a是集合A中的最大元(5分)14如果R1和R2是A上的自反关系，则R1R2是自反的正确 (3分)R1和R2是自反的， x A， x, x R1， x, x R2， 则 x, x R1 R2， 所以R1R2是自反的 (7分)15如图二所示的图G存在一条欧拉回路正确 (3分。

22、)因为图G为连通的，且其中每个顶点的度数为偶数 (7分)14设N、R分别为自然数集与实数集，f：NR，f x x+6，则f是单射正确 (3分)设x1，x2为自然数且x1 x2，则有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，R 的。

23、哈斯图如图二所示，则集合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，R 的哈斯图如图二所示，则集合A的最大元为a，最小元是f图二错误 (3分)集合A的。

24、最大元与最小元不存在，a是极大元，f是极小元， 五计算题(每小题12分，本题共36分)16设集合A 1，2，3，4 ，R x, y |x, y A；|x y| 1或x y 0 ，试(1)写出R的有序对表示；(2)画出R的关系图；(3)说明R满足自反性，不满足传递性(1)R 1,1 , 2,2 , 3,3 , 4,4 , 1,2 , 2,1 , 2,3 , 3,2 , 3,4 , 4,3 (3分)(2)关系图为(6分)(3)因为 1,1 , 2,2 , 3,3 , 4,4 均属于R，即A的每个元素构成的有序对均在R中，故R在A上是自反的。 (9分)因有 2,3 与 3,4 属于R，但 2,4 不。

25、属于R，所以R在A上不是传递的。 17求P Q R的析取范式，合取范式、主析取范式，主合取范式P(RQ)P RQ PQR (析取、合取、主合取范式) (9分)PQR PQR PQR PQR PQR PQR PQR (主析取范式) (12分)18设图G V，E ，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分)(3)deg v1 2deg v2 3deg 。

26、v3 4deg v4 3deg v5 2 (9分)(4)补图16设谓词公式，试(1)写出量词的辖域； (2)指出该公式的自由变元和约束变元(1) x量词的辖域为， (2分)z量词的辖域为, (4分)y量词的辖域为 (6分)(2)自由变元为与中的y，以及中的z约束变元为x与中的z，以及中的y (12分)17设A 1 , 2 ,1,2 ，B 1,2, 1,2 ，试计算(1)(A B)； (2)(AB)； (3)AB(1)A B 1 , 2 (4分)(2)AB 1,2 (8分)(3)AB 1 ,1 ， 1 ,2 ， 1 , 1,2 ， 2 ,1 ， 2 ,2 ，2 , 1,2 ， 1,1 ， 1,2。

27、 ， 1, 1,2 ， 2,1 ， 2,2 ,2, 1,2 18设G V，E ，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分)(3)v1，v2，v3，v4，v5结点的度数依次为1，2，4，3，2 (9分)(4)补图如下：16试求出(PQ)R的析取范式，合取范式，主合取范式(PQ)R PQ R PQ R(析取范式) (3分)PR QR (合取范式) (6分)P。

28、R QQ QR PP PRQ PRQ QRP QRP PQR PQR PQR (主合取范式) (12分)17设A a, b , 1, 2 ，B a, b, 1 , 1 ，试计算(1)(A B) (2)(AB) (3)(AB) (AB)(1)(A B) 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, E ，其中V a, b, c, d, e ，E a, b , a, c , a, e , b, d , b, e , c, e , c, d , d, e ，对应边的权。

29、值依次为2、1、2、3、6、1、4及5，试(1)画出G的图形； (2)写出G的邻接矩阵；(3)求出G权最小的生成树及其权值(1)G的图形表示为： (3分)(2)邻接矩阵：(3)粗线表示最小的生成树， (10分)权为7： (12分)15求(PQ)(RQ)的合取范式(PQ)(RQ)(PQ)(RQ) (4分)P Q (RQ)PRQ QRQ PRQ R 合取范式 (12分)16设A 0，1，2，3，4 ，R x，y |x A，y A且x+y 0 ，S x，y |x A，y A且x+y 3 ，试求R，S，R S，R，S，r R R , (2分)S 0,0 , 0,1 , 0,2 , 0,3 , 1,0 。

30、, 1,1 , 1,2 , 2,0 , 2,1 , 3,0 (4分)R S ， (6分)R-1 ， (8分)S-1 S， (10分)r R IA (12分)17画一棵带权为1, 2, 2, 3, 4的15求(PQ)R的析取范式与合取范式(PQ)R (PQ)R (4分)P Q R (析取范式) (8分)PR QR (合取范式) (12分)16设A 0，1，2，3 ，R x，y |x A，y A且x+y 0 ，S x，y |x A，y A且x+y ，试求R，S，R S，S，r R R , S 0,0 , 0,1 , 0,2 , 1,0 , 1,1 , 2,0 (3分)R S ， (6分)S -1 。

31、S， (9分)r R IA 0,0 , 1,1 , 2,2 , 3,3 (12分)17画一棵带权为1, 2, 2, 3, 4的15设谓词公式，试(1)写出量词的辖域； (2)指出该公式的自由变元和约束变元(1) x量词的辖域为， (3分)z量词的辖域为, (6分)(2)自由变元为中的y， (9分)约束变元为x与z (12分)16设集合A 1 ,1,2 ，B 1, 1,2 ，试计算(1)(A B)； (2)(AB)； (3)AB(1)A B 1 ,2 (4分)(2)AB 1 (8分)(3)AB 1 ,1 ， 1 , 1,2 ， 1,1 ， 1, 1,2 ， 2,1 ， 2, 1,2 (12分)1。

32、7设G V，E ，V v1，v2，v3，v4 ，E v1,v3 ， v2,v3 ， v2,v4 ， v3,v4 ，试(1)给出G的图形表示； (2)写出其邻接矩阵；(3)求出每个结点的度数； (4)画出其补图的图形(1)G的图形表示为 如图三 ：(3分) (2)邻接矩阵：(6分)(3)v1，v2，v3，v4结点的度数依次为1，2，3，2 (9分)(4)补图如图四所示：21化简下列集合表示式：设E为全集A22设，求，并画出其图像 的图像如下图1所示的阴影部分图1 图2 的图像如上图2所示的阴影部分23设G V，E ，V v1，v2，v3，v4，v5 ，E v1,v3 ， v2,v3 ， v2,v。

33、4 ， v3,v4 ， v3,v5 ， v4,v5 ，试： 给出G的图形表示； 画出其补图的图形 G的图形表示 G的补图的图形图 图24构造权为2，3，4，4，5，5，7的最优树。最优树如下图5所示21设A，B和C是全集E的子集，化简下列集合表示式：22设A 1,2,3 用列举法给出A上的恒等关系IA，全关系EA，A上的小于关系及其逆关系和关系矩阵. (2分)(2分)(2分)LA的逆关系 . (2分)23图G V, E ，其图形如右图1所示。 写出G的邻接矩阵； 画出G的权最小的生成树以及计算出其权值 G的邻接矩阵为： (4分) G的权最小的生成树如右上图1所示 (4分)最小的生成树的权为：1。

34、+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 (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 B C A B A C 证明：设S A B C ，T A B A C ，若xS，则xA或xB C，即 xA或xB 且 xA或xC也即xA B 且 xA C ，即 x。

35、T，所以S T (4分)反之，若xT，则xA B 且 xA C，即xA或xB 且 xA或xC，也即xA或xB C，即xS，所以T S因此T S 19试证明集合等式A B C A B A C 证明：设S A B C ，T A B A C ，若xS，则xA或xB C，即 xA或xB 且 xA或xC也即xA B 且 xA C ，即 xT，所以S T (4分)反之，若xT，则xA B 且 xA C，即xA或xB 且 xA或xC，也即xA或xB C，即xS，所以T S18设G是一个n阶无向简单图，n是大于等于2的奇数证明G与中的奇数度顶点个数相等 是G的补图 证明：因为n是奇数，所以n阶完全图每个顶点度。

36、数为偶数， (3分)因此，若G中顶点v的度数为奇数，则在中v的度数一定也是奇数， (6分)所以G与中的奇数度顶点个数相等 (8分)18试证明集合等式A B C A B A C 证明：设S A B C ，T A B A C ，若xS，则xA或xB C，即 xA或xB 且 xA或xC也即xA B 且 xA C ，即 xT，所以S T (4分)反之，若xT，则xA B 且 xA C， 即xA或xB 且 xA或xC，也即xA或xB C，即xS，所以T S因此T S 18设A，B是任意集合，试证明：若A A B B，则A B证明：设x A，则 x，x A A， (1分)因为A A B B，故 x，x B。

37、 B，则有x B， (3分)所以A B (5分)设x B，则 x，x B B， (6分)因为A A B B，故 x，x A A，则有x A，所以B A (7分)故得A B (8分)试证明( x)(P(x)R(x) ( x)P(x)( x)R(x)证明： ( x)(P(x)R(x) P P(a)R(a) ES 1 P(a) T 2 I ( x)P(x) EG 3 R(a) T 2 I( x)R(x) EG 5 ( x)P(x)( x)R(x) T 5 6 I26试证明 成立。证明：设公式中的个体变元为a1，a2，an，即个体域E a1，a2，an ，则有：25设T是正则二叉树，有t片树叶，证明T的阶数n 2t-1证明：根据正则二叉树的概念和握手定理得 n t+i ，i为分支点数 n m+1 ，m为T的边数 m 2i (正则二叉树的定义)由和可解得i 代入，解出 n 2t-1.成立。