2022年离散数学期末考试复习题

《2022年离散数学期末考试复习题》由会员分享，可在线阅读，更多相关《2022年离散数学期末考试复习题（40页珍藏版）》请在金锄头文库上搜索。

1、、判断题（共 5 道小题，共 50.0 分）1. 如果，则或A.正确B.错误知识点 : 集合学生答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 2. 设为集合上的等价关系 , 则A.正确B.错误知识点 : 关系学生答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 3. 设为集合上的等价关系 , 则也是集合上的等价关系A.正确B.错误知识点 : 关系学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 4. 设A.正确B.错误知识点 : 关系学生答案 : A; 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -

2、 -第 1 页，共 40 页得分 : 10 试题分值 : 10.0 提示 : 5.(错误 )设集合，则A.正确B.错误知识点 : 关系学生答案 : A; 得分 : 0 试题分值 : 10.0 提示 : 二、单项选择题（共5 道小题，共 50.0 分）1. 设 A，B，C是集合，则（）成立 . A.如果B.如果C.如果D.如果知识点 : 集合学生答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 2. 设，则下列各式中错误的是A.B.C.精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 2 页，共 40 页D.知识点 : 集合学生答案 :

3、 B; 得分 : 10 试题分值 : 10.0 提示 : 3.(错误 )下列各式中不正确的是A.B.C.D.知识点 : 集合学生答案 : B; 得分 : 0 试题分值 : 10.0 提示 : 4. 设为实数集合，下列集合中哪一个不是空集A.B.C.D.知识点 : 集合学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 3 页，共 40 页5. 设，则的恒等关系为A.B.C.D.知识点 : 关系学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 一、判断题（共5 道小

4、题，共 50.0 分）1. 设是代数系统的元素，如果是该代数系统的单位元），则A.正确B.错误知识点 : 代数系统的基本概念学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 2. 集合 A上的任一运算对A是封闭的A.正确B.错误知识点 : 代数系统的基本概念学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 4 页，共 40 页3. 设是群如果对于任意，有，则是阿贝尔群A.正确B.错误知识点 : 群、环和域学生答案 : A; 得分 : 10 试题分值 : 10.0

5、 提示 : 4. 设是布尔代数，则对任意，有A.正确B.错误知识点 : 格和布尔代数学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 5. 设集合，则是格A.正确B.错误知识点 : 格和布尔代数学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 二、单项选择题（共5 道小题，共 50.0 分）1. 下列哪个集关于减法运算是封闭的A.（自然数集）B.C.D.精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 5 页，共 40 页知识点 : 代数系统的基本概念学生答案 : B; 得分 : 10 试题分值 : 10.0

6、提示 : 2.下列定义的实数集R上的运算 * 中可结合的是A.B.C.D.知识点 : 代数系统的基本概念学生答案 : c 得分 : 0 试题分值 : 10.0 提示 : 3. 在整数集上，下列哪种运算是可结合的A.B.C.D.知识点 : 代数系统的基本概念学生答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 4.循环群的所有生成元为A.1，0 B.-1，2精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 6 页，共 40 页C.1，2 D.1，-1知识点 : 群、环和域学生答案 : D 得分 : 0 试题分值 : 10.0 提示 :

7、5.设代数系统A，?，则下面结论成立的是 . A.如果A，?是群，则A，?是阿贝尔群B.如果A，?是阿贝尔群，则A，?是循环群C.如果A，?是循环群，则A，?是阿贝尔群D.如果A，?是阿贝尔群，则A，?必不是循环群知识点 : 群、环和域学生答案 : C 得分 : 0 试题分值 : 10.0 提示 : 一、判断题（共5 道小题，共 50.0 分）1. 强连通有向图一定是单向连通的A.正确B.错误知识点 : 无向图和有向图学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 2. 有生成树的无向图是连通的A.正确精选学习资料 - - - - - - - - - 名师归纳总结 - -

8、 - - - - -第 7 页，共 40 页B.错误知识点 : 树学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 3. 设 P，Q都是命题公式，则A.正确B.错误知识点 : 命题逻辑学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 4. 设都是命题公式，则也是命题公式A.正确B.错误知识点 : 命题逻辑学生答案 : B; 得分 : 10 试题分值 : 10.0 提示 : 5. “如果 872，则三角形有四条边”是命题A.正确B.错误知识点 : 命题逻辑学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 6.二、单项选择题（共5 道小题

9、，共 50.0 分）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 8 页，共 40 页1.设 G1= V1, E1, G2= V2, E2都是无向图，则 #V1=#V2且#E1=#E2是 G1与 G2同构的A.充分必要条件B.充分而非必要条件C.必要而非充分条件D.既非充分又非必要条件知识点 : 无向图和有向图学生答案 : C 得分 : 0 试题分值 : 10.0 提示 : 2.有向图，其中，则有向图是A.强连通图B.单向连通图C.弱连通图D.不连通图知识点 : 无向图和有向图学生答案 : C 得分 : 0 试题分值 : 10.0 提示 : 3.

10、是无向图的关联矩阵，是中的孤立点，则A.对应的一行元素全为0B.对应的一行元素全为1C.对应的一列元素全为0精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 9 页，共 40 页D.对应的一列元素全为1知识点 : 图的矩阵表示学生答案 : A; 得分 : 10 试题分值 : 10.0 提示 : 4.由前提得到的有效结论为A.SB.QC.PD.知识点 : 命题逻辑学生答案 : C 得分 : 0 试题分值 : 10.0 提示 : 5. 设个体域，公式在上消去量词后应为A.B.C.D.知识点 : 一阶逻辑学生答案 : B; 得分 : 10 试题分值 : 1

11、0.0 提示 : 离散数学期末复习题第一章集合论精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 10 页，共 40 页一、判断题（1）空集是任何集合的真子集（错）（2）是空集（错）（3）aaa,（对）（4）设集合AA22,1,2, 1,2, 1则. ( 对）（5）如果BAa，则Aa或Ba（错）解BAa则BABAa，即Aa且Ba，所以Aa且Ba（6）如果 A.,BABB则（对）（7）设集合,321aaaA，,321bbbB，则,332211bababaBA（错）（8）设集合 1 ,0A，则1,0,0,0,1 ,0,是A2到A的关系（对）解A2,1,0

12、 ,A，AA21 ,0,1,1,0,1,1,0,0,0,1 ,0,AA（9）关系的复合运算满足交换律（错）（10）.条件具有传递性的充分必要上的关系是集合 A（错）（11）设.,上的传递关系也是则上的传递关系是集合AA( 对) （12）集合 A 上的对称关系必不是反对称的. （错）（13）设21,为集合A上的等价关系, 则21也是集合A上的等价关系( 对 ) （14）设是集合A上的等价关系, 则当ba,时，ba ( 对 ) （15）设21,为集合A上的等价关系 , 则 ( 错 ) 二、单项选择题（1）设R为实数集合，下列集合中哪一个不是空集（ A ）A. Rxxx且,01|2 BRxxx且,0

13、9|2C. Rxxxx且, 1| D. Rxxx且, 1|2（2）设BA,为集合，若BA，则一定有（ C ）A. B BB C. BA D. BA（3）下列各式中不正确的是（ C ）A. B C. D. ,精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 11 页，共 40 页（4）设 , aaA，则下列各式中错误的是（ B ）A. Aa2 BAa2 C. Aa2 D. Aa2（5）设2, 1A，cbaB,，dcC,，则)(CBA为（ B ）A. cc,2,1 , Bcc,2, 1C. 2, 1cc D. 2,1 ,cc（6）设bA,0，3, 1 b

14、B，则BA的恒等关系为（A ）A. 3 ,3,1 , 1,0,0bb B3 ,3,1 , 1,0,0C. 3 ,3,0 ,0bb D. 0 ,3,3, 1,1 , 0bb（7）设cbaA,上的二元关系如下，则具有传递性的为（ D ）A. abbaacca,1Bacca,2C. cbabccba,3D. aa,4（8）设为集合A上的等价关系，对任意Aa，其等价类a为（ B ）A. 空集； B非空集； C. 是否为空集不能确定； D. |Axx. （9）映射的复合运算满足（ B ）A. 交换律 B结合律 C. 幂等律 D. 分配律（10）设 A，B 是集合，则下列说法中（C ）是正确的 . AA

15、到 B 的关系都是A 到 B 的映射BA 到 B 的映射都是可逆的CA 到 B 的双射都是可逆的DBA时必不存在A 到 B 的双射（11）设 A 是集合，则（B ）成立 . AAA#22#BAXXA2CA2DAA2（12）设 A 是有限集（nA#） ，则 A 上既是又是的关系共有（ B ）.A0 个B1 个C2 个Dn个精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 12 页，共 40 页三、填空题1. 设2, 1 ,2, 1A，则A2_. 填,2, 1 ,2,2, 1 , 1,2, 1,2,1,2,1 ,2AA2. 设 ,A，则A2= . 填,

16、,2AA3. 设集合BA,中元素的个数分别为5#A，7#B，且9)(#BA，则集合BA中元素的个数)(#BA .3 4. 设集合4,1001|ZxxxxA的倍数，是，5,1001|ZxxxxB的倍数，是，则BA中元素的个数为 .40 5. 设,baA, 是A2上的包含于关系，, 则有= . , , ,AAAbbbAaaaAba6. 设21,为集合A上的二元关系, 则21 .127. 集合A上的二元关系为传递的充分必要条件是8. 设 集 合0,2,2,02,1,01上的关系A及 集 合A到 集 合4,2,0B的 关 系2ba,|ba,AbaBA,且21,则B_. 填2,2,0,2,2,0,0 ,

17、0四、解答题1. 设AdcbaA,上的关系,cddcabbaddccbbaa（1）写出的关系矩阵；（2）验证是A上的等价关系；（3）求出A的各元素的等价类。解 （1）的关系矩阵为1100110000110011M（2）从的关系矩阵可知：是自反的和对称的。又由于MMM110011000011001111001100001100111100110000110011或满足所以是传递的。因为是自反的、对称的和传递的，所以是A上的等价关系。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 13 页，共 40 页（3）,baba，,dcdc2. 设集合36,24

18、,12,8 ,6 ,3,2,1A，是A上的整除关系，（1）写出的关系矩阵M；（2）画出偏序集,A的哈斯图；（3）求出A的子集6,3 ,2B的最小上界和最大下界。解： （1）1000000001000000111000000101000011101000111011001111101011111111M（2）（3）lubB=6, glbB=1五、证明题1. 设21,为集合A上的等价关系, 试证21也是集合A上的等价关系。证明：由于21,是自反的，所以对任意Aa,21,aaaa, 因而21,aa，即21是自反的。若21,ba，则21,baba,由 于21,是对称的，所 以21,abab, 从而21

19、,ab，即21是对称的。若21,cbba，则21,cbbacbba, 由于21,是传递的，所以21,caca, 从而21,ca，即21是传递的。由于21是自反的、对称的和传递的，所以21是等价关系。第二章代数系统一、判断题（1）集合 A上的任一运算对A是封闭的（对）（2）代数系统的零元是可逆元. （错）（3）设 A是集合，AAA:，bba，则是可结合的（对）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 14 页，共 40 页（ 4 ） 设ba,是 代 数 系 统,A的 元 素 ， 如 果eeabba(是 该 代 数 系 统 的 单 位 元 ） ，

20、 则.1ba( 对) （5）设.)(,111babaGba则的元素是群（错）（ 6 ） 设,G是 群 如 果 对 于 任 意Gba,， 有222)(baba， 则,G是 阿 贝 尔群（对）（7）设.,满足幂等律则运算是格L（对）（8）设集合,baA，则, ,Aba是格（对）（9）设,B是布尔代数，则,B是格（对）二、单项选择题（1）在整数集Z上，下列哪种运算是可结合的（ B ）A. baba B,maxbabaC. baba2 D. |baba（2）下列定义的实数集R 上的运算* 中可结合的是. （C ）AbaabaBbaaba2CbbaDbaba其中， +， ，分别为实数的加法、乘法和取绝对

21、值运算. （3）设集合10,4,3,2, 1A，下面定义的哪种运算关于集合A不是封闭的（ D ）A. ,maxyxyxB,minyxyxC. ,GCDyxyx，即yx,的最大公约数D. ,LCMyxyx，即yx,的最小公倍数（4）下列哪个集关于减法运算是封闭的（ B ）A. N（自然数集） ； B)(|2整数集Zxx；C. |12Zxx； D. |是质数xx. （5）设Q是有理数集，在Q定义运算为abbaba，则,Q的单位元为（ D ）A. a； Bb； C. 1； D. 0 （6）设代数系统A， ，则下面结论成立的是. （C ）A如果A， 是群，则A， 是阿贝尔群精选学习资料 - - - -

22、 - - - - - 名师归纳总结 - - - - - - -第 15 页，共 40 页B如果A， 是阿贝尔群，则A， 是循环群C如果A， 是循环群，则A， 是阿贝尔群D如果A， 是阿贝尔群，则A， 必不是循环群（7）循环群,Z的所有生成元为（ D ）A. 1 ，0 B-1，2 C. 1，2 D. 1，-1 三、填空题1. 设A为非空有限集，代数系统,2A中，A2对运算的单位元为，零元为.填A,2. 代数系统,Z中（其中Z为整数集合，+为普通加法） ，对任意的Ix，其1x .填x3. 在整数集合Z上定义运算为baba2，则,Z的单位元为 . 解 设单位元为e，aeaea2，所以2e，又aaaa

23、aa2)2()2(,)2(2)2(，所以单位元为2e4. 在整数集合Z上定义运算为abbaba，则,Z的单位元为 . 解设单位元为e，aaeeaea，0)1 (ea，所以0e5. 设,G是群，对任意Gcba,，如果,caba，则.填cb6. 设,G是群，e为单位元，若G元素a满足aa2，则a .填e四、解答题1.设为实数集R上的二元运算，其定义为abbabaRR2,:2，对于任意Rba,求运算的单位元和零元。解：设单位元为e，则对任意Ra，有aaeeaea2，即0)21(ae，由a的任意性知0e，又对任意Ra，aaa000；aaa000所以单位元为0 设零元为，则对任意Ra，有aaa2，即0)

24、21 (a，由a的任意性知21又对任意Ra，2121)21(aaa，2121)21(aaa所以零元为212. 设为集合4,3 ,2, 1 ,05I上的二元运算，其定义为5mod)(,:525abbaII，对于任意5,Iba（1）写出运算的运算表；（2）说明运算是否满足交换律、结合律，是否有单位元和零元、如果有请指出；（3） 写出所有可逆元的逆元解：（ 1）运算表为精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 16 页，共 40 页（ 2）运 算满足交换律、结合律，有单位元，单位元为1，有 零元，零元为0；（ 3） 1 的逆 元为1， 2 的逆元为

25、3， 3 的逆元 为 2， 4 的逆元4， 0 没 有逆元五、证明题1. 设,G是一个群，试证G是交换群当且仅当对任意的Gba, , 有222)(baba . 证明：充分性若在群,G中，对任意的Gba, , 有222)(baba . 则)()()()(bababbaabababbaa)()(abba从而,G是一个交换群。必要性若,G是一个交换群，对任意的Gba, , 有abba，则bababbaa)()()()()()(bababbaa即222)(baba. 2. 证明代数系统,Z是群，其中二元运算定义如下：ZZ2，3yxyx（这里， +，分别是整数的加法与减法运算.）证明 （ 1）运算满足交

26、换律对任意zyx,Z，由,6)3()(zyxzyxzyx6)3()(zyxzyxzyx即得),()(zyxzyx满足结合律；（2）有单位元3 是单位元；（3）任意元素有逆元对任意xZ，,.61所以xxZ，是群 . 第三章图论一、判断题（1）n 阶完全图的任意两个不同结点的距离都为1. （对）0 1 2 3 4 0 0 0 0 0 0 1 0 1 2 3 4 2 0 2 4 1 3 3 0 3 1 4 2 4 0 4 3 2 1 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 17 页，共 40 页（2）图 G 的两个不同结点jivv ,连接时一定邻

27、接. （错）（3）图 G 中连接结点.,之间的短程的初级通路为jijivvvv（错）（4）在有向图中，结点iv到结点jv的有向短程即为jv到iv的有向短程（错）（5）强连通有向图一定是单向连通的（对）（6）不论无向图或有向图，初级回路一定是简单回路（对）（7）设图 G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的（对）（8）有生成树的无向图是连通的（对）（9）下图所示的图是欧拉图. （错）（10）下图所示的图有哈密尔顿回路. （对）二、单项选择题（1）仅由孤立点组成的图称为（ A ）A. 零图； B平凡图； C. 完全图； D. 多重图 . （2）仅由一个孤立点组成的图称为（ B ）

28、A. 零图； B平凡图； C.多重图； D. 子图 . （3）在任何图G中必有偶数个（ B ）A. 度数为偶数的结点； B度数为奇数的结点；C. 入度为奇数的结点； D. 出度为奇数的结点. （4）设G为有n个结点的无向完全图，则G的边数为（ C ）A. )1(nn B)1(nn C. 2)1(nn D. 2)1(n（5）在有n个结点的连通图G中，其边数（ B ）A. 最多1n条； B至少1n条；C. 最多n条； D. 至少n条. （6）任何无向图G中结点间的连通关系是（ B ）A. 偏序关系； B等价关系；C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系. （7）对于无向

29、图，下列说法中正确的是. （B ）A不含平行边及环的图称为完全图B任何两个不同结点都有边相连且无平行边及环的图称为完全图C具有经过每条边一次且仅一次回路的图称为哈密尔顿图精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 18 页，共 40 页D具有经过每个结点一次且仅一次回路的图称为欧拉图（8）设 D 是有向图，则D 强连通的充分必要条件为. ( C ) A略去 D 中各边方向后所得到的无向图是连通的BD 是单向连通图，且改变它的各边方向后所得到的有向图也是单向连通图CD 的任意两个不同的结点都可以相互到达DD 是完全图（9）对于无向图G，以下结论中

30、 不正确 的是 . （ A ）A如果 G 的两个不同结点是连接的，则这两个结点之间有初级回路B如果 G 的两个不同结点是连接的，则这两个结点之间至少有一条短程C如果 G 是树，则任何两个不同结点之间有且仅有一条初级通路D如果 G 是欧拉图，则G 有欧拉回路三、填空题1. 设树 T中有 7 片树叶， 3 个 3 度结点，其余都是4 度结点，则T 中有个 4 度结点 . 解 用握手定理和树的性质列出方程求解，设有x个 4度结点，) 137(2497xx，1x2. 设EVT,为树，T中有 4 度， 3 度， 2度分支点各1 个，问T中有片树叶。解 与上题解法相同，设有x片树叶，)13(2234xx，

31、5x3.n 阶完全图的任意两个不同结点的距离都为1 4. 图G为n阶无向完全图，则G共有条边。2/) 1(nn5. 设G为),(mn图，则图中结点度数的总和为。m26.图 G 为欧拉图的充分必要条件是_. G 为无奇度结点的连通图四、解答题1.对下图所示的图G，求（1）G 的邻接矩阵A；（2）G 的结点31,vv之间长度为3 的通路；（3）G 的连接矩阵C；（4）G 的关联矩阵M。解 （1）A=.00001110011101110101011105432154321vvvvvvvvvv（2） 因为精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 19

32、 页，共 40 页A2=,2112111221114221223121213A3=,7所以，结点31,vv之间长度为3 的通路共有7 条，它们是.,3431323135313141312135213131vvvvvvvvvvvvvvvvvvvvvvvvvvvv（3）由于图G 是连通的，所以54321vvvvvC=.111111111111111111111111154321vvvvv（4）7654321eeeeeeeM=.1100000001100001101101000011000110154321vvvvv2. 在下面的有向图D中，回答下列问题（1）写出图D的邻接矩阵A；（2）写出结点1v

33、到结点3v的长度为 3 的所有有向通路；（3）写出结点5v到自身的长度为3 的所有有向回路；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 20 页，共 40 页解： （1）0101010000011000010110000A（2）10101010101110011100010102A12110101011211012110101013A所以结点1v到结点3v的长度为3 的所有有向通路只有一条: 3251vvvv（3）结点5v到自身的长度为3 的所有有向回路只有一条：5125vvvv3. 在下面的无向图G中，回答下列问题aedbc（1）写出da,之

34、间的所有初级通路；（2）写出da,之间的所有短程，并求),(dad；（3）判断无向图G是否为欧拉图并说明理由。解（ 1）da,之间的所有初级通路共有7 条，分别为aed，aecd，aebcd，abed，abcd，abecd，abced（2）da,之间的长度最短的通路只有1 条，即aed，因而它是da,之间唯一的短程，2),(dad（3）由于无向图G中有两个奇度顶点3)deg(,3)deg(cb，所以无向图G没有欧拉回路，因而不是欧拉图。第四章数理逻辑一、判断题（1） “如果 872，则三角形有四条边”是命题（对）（2）设QP,都是命题公式，则QP也是命题公式（错）（3）命题公式QP,的真值分别

35、为0，1，则QP的真值为0 （以上是在对QP,所包含的命题变元的某个赋值下）（错）（ 4）设:,1963:qp年他生于他生于1964 年，则命题“他生于1963 年或1964 年”可以符号化为.qp（对）（5）设 P，Q 都是命题公式，则.1QPQP的充分必要条件为（对）（6）逻辑结论是正确结论（错）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 21 页，共 40 页（9）设CBA,都是命题公式，则)()(CACBA也是命题公式（ 对）（10）命题公式QP,的真值分别为0，1，则QP的真值为0 （以上是在对QP,所包含的命题变元的某个赋值下）（对

36、）二、单项选择题（1）下面哪个联结词不可交换（ B ）A. ； B； C.； D. . （2）命题公式qqpp)(是（ C ）A. 永假式； B非永真式的可满足式；C. 永真式； D. 等价式 . （3）记:p他懂法律，:q他犯法，则命题“他只有懂法律，才不会犯法”可符号化为（B ）. AqpBpqCpqDqp（4）下列命题中 假命题是（B ）. A如果雪不是白的，则太阳从西边出来B如果雪是白的，则太阳从西边出来C如果雪不是白的，则太阳从东边出来D只要雪不是白的，太阳就从西边出来（5）设 A，B 都是命题公式，则AB 为可满足式是BA的（B ）. A充分而非必要条件B必要而非充分条件C充分必要

37、条件D既非充分又非必要条件三、填空题1. 设:p天气很冷，:q老王还是来了， 则命题“虽然天气很冷, 但老王还是来了” 符号化为 .qp2. 设:p天 下 雨 ，:q我 骑 自 行 车 上 班 ， 则 命 题 “ 如 果 天 不 下 雨 , 我 就 骑 自 行 车 上 班 ” 符 号 化为 .qp3. 设qp,的真值为0，sr,的真值为1，则命题公式)()(sqrp的真值为 .0 4. 设qp,的真值为 0，r的真值为1，则命题公式)(rqp的真值为 .0 离散数学综合练习题一、判断下列命题是否正确如果正确，在题后括号内填“/ ” ；否则，填“”（1）空集是任何集合的真子集（）精选学习资料 -

38、 - - - - - - - - 名师归纳总结 - - - - - - -第 22 页，共 40 页（2）是空集（）（3）aaa,（）（4）如果BAa，则Aa或Ba（）（5）设集合,321aaaA，,321bbbB，则,332211bababaBA（）（6）设集合 1 ,0A，则1,0,0,0,1 ,0 ,是A2到A的关系（）（7）关系的复合运算满足交换律（）（8）设21,为集合A上的等价关系 , 则21也是集合A上的等价关系( ) （9）设是集合A上的等价关系, 则当ba,时，ba( ) （10）设21,为集合A上的等价关系, 则2121 ( ) （11）集合 A上的任一运算对A是封闭的（）

39、（12）设 A是集合，AAA:，bba，则是可结合的（）（13）设,G是群如果对于任意Gba,，有222)(baba则,G是阿贝尔群（）（14）设 a 是群,G的元素，记|yaayGyyH且则,H是,G的子群（）（15）是格（）（16）设 a，b 是格,L的任意两个元素，则ababba（）（17）设,B是布尔代数，则,B是格（）（18）设集合,baA，则, ,Aba是格（）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 23 页，共 40 页（19）设,B是布尔代数，则对任意Bba,，有baba（）（20）设,B是布尔代数，则对任意Ba，都有Bb，

40、使得0, 1baba（）（21）n 阶完全图的任意两个不同结点的距离都为1. （）（22）在有向图中，结点iv到结点jv的有向短程即为jv到iv的有向短程（）（23）强连通有向图一定是单向连通的（）（24）不论无向图或有向图，初级回路一定是简单回路（）（25）设图 G是连通的，则任意指定G的各边方向后所得的有向图是弱连通的（）（26）设 A是某个无向图的邻接矩阵，则TAA(TA是A的转置矩阵 )（）（27）设有向图D的可达矩阵为1000110011101111P则G是单向连通的（）（28）有生成树的无向图是连通的（）（29）由 r 棵树组成的森林的结点数n 与边数 m有下列关系：m=n-r.

41、（）（30）如果有向图D仅有一个结点的入度为0，其余结点的入度都为1，则 D是有向树（）（31） “如果 872，则三角形有四条边”是命题（）（32）设QP,都是命题公式，则QP也是命题公式（）（33）命题公式QP,的真值分别为0， 1，则QP的真值为 0 （以上是在对QP,所包含的命题变元的某个赋值下）（）（34）逻辑结论是正确结论（）（35）设BA,都是谓词公式，则BA也是谓词公式（）（36）设BA,都是谓词公式，BA，则BA是永真式（）（37）设CBA,都是命题公式，则)()(CACBA也是命题公式（）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - -

42、 -第 24 页，共 40 页（38）命题公式QP,的真值分别为0， 1，则QP的真值为 0 （以上是在对QP,所包含的命题变元的某个赋值下）（）（39）设c是个体域中某个元素，则)()()()(cQcPxxQxxP其中QP,都是谓词（）（40）),(),(yxxAyyxyAx（）答案： （ 1）错误；（2）错误；（3）正确；（4）错误；（5）错误；（6）正确；（7）错误；（8）正确；（9）正确；（10）错误；（11）正确；（12）正确；（13）正确；（14）正确；（15）正确；（16）正确；（17）正确；（18）正确；（19）正确；（20）正确；（21）正确；（22）错误；（23）正确；（2

43、4）正确；（25）正确；（26）正确；（27）正确；（28）正确；（29）正确；（30）错误；（31）正确；（32）错误；（33）错误；（34）错误；（35）错误；（36）正确；（37）正确；（38）正确；（39）错误；（40）错误 . 二、填空题（1）设A有n个元素，则集合A的幂集)(AP中有个元素。（2）设 ,A，则A2= . （3）设集合BA,中元素的个数分别为5#A，7#B，且9)(#BA，则集合BA中元素的个数)(#BA . （ 4）设集合4,1001|ZxxxxA的倍数，是，5,1001|ZxxxxB的倍数，是，则BA中元素的个数为 . (5) 设21,为集合A上的二元关系 , 则

44、21 . (6) 集合A上的二元关系为传递的充分必要条件是 (7) 设1：a称b为母亲，2：b称c为父亲，则21： , (8) 设N为自然数的集合，“” 为自然数的小于等于关系，N的子集9, 7, 5A， 则A的下确界为，下确界为 , (9)设 10 人集合E 赵茵，钱小滨，孙丽春，赵萍，钱浩，李靖华，李秀娟，钱钰，李惠芝，李莉上的同姓关系为，则等价类 赵= ， 钱= ， (10)设,baA, 是A2上的包含于关系，,则有= . (11)设S为非空有限集，代数系统),(SP中，)(SP对运算的单位元为，零元为 . (12)循环群33,I的生成元为 . (13)循环群66,I的所有子群为 . (

45、14)代数系统,Z中（其中Z为整数集合，+为普通加法） ，对任意的Ix，其1x . (15)在整数集合Z上定义运算为baba2，则,Z的单位元为 . (16)设10,4,3,2, 1T, 在代数系统max,T中，max,T的单位元为，可逆元为 . 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 25 页，共 40 页 (17)设,G是群，则对于任意的Gba,，方程和有唯一解。 (18)设,G是群，对任意Gcba,，如果,caba，则. (19)设,G是群，e为单位元，若G元素a满足aa2，则a . (20)在整数集合Z上定义运算为abbaba，则,

46、Z的单位元为 . (21)设EVT,为树，T中有 4 度， 3 度， 2度分支点各1 个，问T中有片树叶。 (22)为了从（ n，m ）连通无向图得到一棵生成树，必须删除G的条边 (23)设树 T 中有 7 片树叶， 3 个 3 度结点，其余都是4 度结点，问T 中有个 4 度结点。 (24)无环有向图的关联矩阵的所有元素之和为 (25)n阶完全图的任意两个不同结点的距离都为 (26)图G为n阶无向完全图，则G共有条边。 (27)设G为),(mn图，则图中结点度数的总和为。 (28)设图G有 6 结点，若各结点的度数分别为：1， 4，4，3，5，5，则G共有条边。 (29)无向图G是由)2(k

47、k棵树组成的森林，至少要添加条边才能使G成为一棵树。 (30)在任何图EVG,中，奇数结点必为个。 (31)设:p天 气 很 冷 ，:q老 王 还 是 来 了 ， 则 命 题 “ 虽 然 天 气 很 冷 , 但 老 王 还 是 来 了 ” 符 号 化为 . (32)设:p天 下 雨 ，:q我 骑 自 行 车 上 班 ， 则 命 题 “ 如 果 天 不 下 雨 , 我 就 骑 自 行 车 上 班 ” 符 号 化为 . (33)设:p经一事 , :q长一智，则命题“不经一事, 不长一智”符号化为 . (34)设qp,的真值为 0，r的真值为1，则命题公式)(rqp的真值为 . (35)设qp,的真

48、值为 0，sr,的真值为1，则命题公式)()(sqrp的真值为 . (36)由n个命题变项可以组成个不等值的命题公式。 (37)设个体域,21naaaA，公式)()(xFx在A上消去量词后应为 . (38)设xxN:)(是自然数，xxF:)(是奇数，xxG:)(是偶数，则命题“任何自然数不是奇数就是偶数”符号化为 . (39)设xxF:)(是素数，xxG:)(是偶数，2:a， 则命题“2 既是偶数又是素数” 符号化为 . (40)设xxG:)(是金子，xxF:)(是发光的，则命题“金子是发光的, 但发光的不一定是金子”符号化为 . 答案： （ 1）n2；（2） , ,；（3）3；（4）40；

49、(5)12(6) ； (7)a称c为外祖父； (8)5， 9；(9) 赵= 赵茵，赵萍 ， 钱= 钱小滨，钱浩，钱钰 ， 孙= 孙丽春 ， 李 = 李靖华，李秀娟，李惠芝，李莉. (10) , , ,AAAbbbAaaaAba(11) S,； (12) 1和 2；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 26 页，共 40 页(13)6,0，6,3 ,0，6,4,2,0，66,I；(14) x； (15) 2； (16) 1，1； (17) bxa，bay； (18) cb；(19) e； (20) 0； (21) 5； (22) m-n1；

50、 (23) 1； (24) 0； (25) 1；(26) 2)1(nn； (27) m2； (28) 11； (29) 1k； (30) 偶数；(31) qp； (32) qp； (33) qp； (34) 0； (35) 0；(36) n22； (37)()()(21naFaFaF； (38) )()()()(xGxFxNx；(39) )()(aGaF； (40) )()()()()()(xGxFxxFxGx. 三、选择题（每题后面有四个选项，四个选项中只有一个是正确的，请将正确的所对应的字母填在括号内）（1）设R为实数集合，下列集合中哪一个不是空集（）A. Rxxx且,01|2 BRxxx

51、且,09|2C. Rxxxx且, 1| D. Rxxx且, 1|2（2）设BA,为集合，若BA，则一定有（）A. B BB C. BA D. BA（3）下列各式中不正确的是（）A. B C. D. ,（4）设 , aaA，则下列各式中错误的是（）A. Aa2 BAa2 C. Aa2 D. Aa2（5）设2, 1A，cbaB,，dcC,，则)(CBA为（）A. cc,2,1 , Bcc,2, 1C. 2, 1cc D. 2,1 ,cc（6）设bA,0，3, 1 bB，则BA的恒等关系为（）A. 3 ,3,1 , 1,0,0bb B3 ,3,1 , 1,0,0C. 3 ,3,0 ,0bb D. 0

52、 ,3,3, 1,1 , 0bb（7）集合10,2, 1A上的二元关系,10|),(Ayxyxyx且，则的性质为（）A. 自反的； B对称的； C. 反对称的； D. 反自反的 . （8）设cbaA,上的二元关系如下，则具有传递性的为（）A. abbaacca,1精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 27 页，共 40 页Bacca,2C. cbabccba,3D. aa,4（9）设为集合A上的等价关系，对任意Aa，其等价类a为（）A. 空集； B非空集； C. 是否为空集不能确定； D. |Axx. （10）映射的复合运算满足（）A.

53、交换律 B结合律 C. 幂等律 D. 分配律（11）在整数集Z上，下列哪种运算是可结合的（）A. baba B,maxbabaC. baba2 D. |baba（12）设集合10,4, 3,2, 1A，下面定义的哪种运算关于集合A不是封闭的（）A. ,maxyxyxB,minyxyxC. ,GCDyxyx，即yx,的最大公约数D. ,LCMyxyx，即yx,的最小公倍数（13）下列哪个集关于减法运算是封闭的（）A. N（自然数集） ； B)(|2整数集Ixx；C. |12Ixx； D. |是质数xx. （14）设Q是有理数集，在Q定义运算为abbaba，则,Q的单位元为（）A. a； Bb；

54、C. 1； D. 0 （15）下列代数系统,G中，哪一个不构成群（）A. ,10,1G是模 11 乘法；B. ,2 ,1 ,0G是模 3加法；C. ),(有理数集QG普通加法；D. ,QG普通乘法 . （16）循环群33,I的生成元为1 和 2，它们的周期为（）精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 28 页，共 40 页A. 5 B6 C. 3 D. 9 （17）循环群55,I的所有子群为（）A. 55,I B5,0C. 55,I和5,0 D. （18）循环群,Z的所有生成元为（）A. 1 ，0 B-1，2 C. 1，2 D. 1，-1

55、（19）有限布尔代数的元素个数必定等于（）A. n2； B2n； C. n2； D. n4. （20）在下面偏序集的哈斯图中，哪一个是格（）A B C D （21）仅由孤立点组成的图称为（）A. 零图； B平凡图； C. 完全图； D. 多重图 . （22）仅由一个孤立点组成的图称为（）A. 零图； B平凡图； C.多重图； D. 子图 . （23）在任何图G中必有偶数个（）A. 度数为偶数的结点； B度数为奇数的结点；C. 入度为奇数的结点； D. 出度为奇数的结点. （24）设G为有n个结点的无向完全图，则G的边数为（）A. )1(nn B)1(nn C. 2)1(nn D. 2)1(n（

56、25）图G和G的结点和边分别存在一一对应关系是GG（同构）的（）A. 充分条件； B必要条件；C. 充分必要条件； D. 既不充分也不必要条件. （26）给定下列序列，哪一个可构成无向简单图的结点度数序列（）A. )3,2, 2, 1, 1( B)2,2,2, 1, 1(C. )3,3,3, 1,0( D. )5, 4,4,3, 1 (（27）在有n个结点的连通图G中，其边数（）A. 最多1n条； B至少1n条；C. 最多n条； D. 至少n条. （28）mnijmM是无向图EVG,的关联矩阵，Vvi是G中的孤立点，则（）A. iv对应的一行元素全为0； Biv对应的一行元素全为1；C. iv

57、对应的一列元素全为0； D. iv对应的一列元素全为1. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 29 页，共 40 页（29）任何无向图G中结点间的连通关系是（）A. 偏序关系； B等价关系；C. 既是偏序关系又是等价关系； D. 既不是偏序关系也不是等价关系. （30）有向图EVG,，其中,fedcbaV，,dacbbaE,efed，则有向图EVG,是（）A. 强连通图； B单向连通图；C. 弱连通图； D. 不连通图 . （31）下面哪个联结词不可交换（）A. ； B； C.； D. . （32）命题公式qqpp)(是（）A. 矛盾式

58、； B非永真式的可满足式；C. 重言式； D. 等价式 . （33）下列哪一组命题公式是等值的（）A. qp，qp； B)(pqp，)(qpp；C. )(qpq，)(qpq； D. )(qpp，q（34）下面哪一个命题是假命题（）A. 如果 2 是偶数，那么一个公式的析取范式唯一；B如果 2 是偶数，那么一个公式的析取范式不唯一；C. 如果 2 是奇数，那么一个公式的析取范式唯一；D. 如果 2 是奇数，那么一个公式的析取范式不唯一. （35）设论域为整数集，下列公式中哪个值为真（）A. )0)()(yxyx； B. )0)()(yxxy；C. )0)()(yxyx； D. )0)()(yxy

59、x. （ 36） 设 谓 词xxP:)(是 奇 数 ，xxQ:)(是 偶 数 ， 谓 词 公 式)()()(xQxPx在 哪 个 论 域 中 是 可 满 足 的（）A. 自然数； B整数； C. 实数； D. 以上均不成立. （37）命题“没有不犯错误的人”符号化为( 设xxA:)(是人 ,xxB:)(犯错误 ) （）A. )()()(xBxAx； B.)()()(xBxAx；C. )()()(xBxAx； D.)()()(xBxAx. （38）设个体域,baA，公式)()()()(xSxxPx在A上消去量词后应为（）A. )()(xSxP； B. )()()()(bSaSbPaP；C. )(

60、)(bPaP； D. )()()()(bSaSbPaP. （39）在谓词演算中，下列各式中，哪一个是正确的（）A.),()(),()(yxAxyyxAyx； B.),()(),()(yxAxyyxAyx；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 30 页，共 40 页C.),()(),()(yxAyxyxAyx； D.),()(),()(yxBxyyxAyx. （40） “学习有如逆水行舟，不进则退”。设:p学习如逆水行舟，:q学习进步，:r学习退步。则命题符号化为（）A. )(rqp； B)(rqp；C. )(rqp； D. )(rqp.

61、答案： （ 1） A；（2） C；（3） C；（4） B；（5） B；（6） A；（7） B；（8） D ；（9） B；（10）B；（11）B；（12）D；（13）B；（14）D；（15）D；（16）C；（17）C；（18）D；（19）C；（20）A；（21）A；（22）B；（23）B；（24）C；（25）B；（26）B；（27）B；（28）A；（29）B；（30）C；（31）B；（32）C；（33）B；（34）A；（35）A；（36）D；（37）D；（38）B；（39）B；（40）B. 四、解答题1. 设AdcbaA,上的关系,cddcabbaddccbbaa试 （1）写出的关系矩阵；（2）

62、验证是A上的等价关系；（3）求出A的各元素的等价类。解 （1）的关系矩阵为1100110000110011M（2）从的关系矩阵可知：是自反的和对称的。又由于MMM110011000011001111001100001100111100110000110011所以是传递的。因为是自反的、对称的和传递的，所以是A上的等价关系。（3）,baba，,dcdc2. 设24,12,8 ,6,4, 3,2A，A是上的整除关系，画出,A的哈斯图。解： 24 8 12 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 31 页，共 40 页4 6 2 3 3. 设集合

63、32,24,16,12,8 ,6 ,3 ,2A, 是A上的整除关系, 画出,A的哈斯图；解： 32 24 16 12 8 6 2 3 4. 设集合6 , 5, 4, 3,2, 1A, 是A上的整除关系，试求：（1）集合A的最大元，最小元（2）子集5,3 ,21A和6,3 ,22A的上界、下界、上确界和下确界。解：由于是A上的整除关系，所以是A上的偏序关系，,A的哈斯图为 4 6 2 3 5 1 （1）集合A的最大元：无，最小元：1 （2）子集上界下界上确界下确界 5, 3,21A无1 无1 6,3,22A6 1 6 1 5. 在下面的无向图G中，回答下列问题aedbc（1）写出da,之间的所有

64、初级通路；（2）写出da,之间的所有短程，并求),(dad；（3）判断无向图G是否为欧拉图并说明理由。解： （1）da,之间的所有初级通路共有7 条，分别为aed，aecd，aebcd，abed，abcd，abecd，abced精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 32 页，共 40 页（2）da,之间的长度最短的通路只有1 条，即aed，因而它是da,之间唯一的短程，2),(dad（3）由于无向图G中有两个奇度顶点3)deg(, 3)deg(cb，所以无向图G没有欧拉图回路，因而不是欧拉图。6. 下列各图是否为欧拉图，是否为哈密尔顿图？

65、为什么？ab1v2v3vcde4v5v6vfghi7v8v9v(1) (2) 解：图（ 1）中各顶点的度数为4)deg(a，4)deg(b，4)deg(c，4)deg(d，4)deg(e，2)deg( f，4)deg(g，4)deg(h，2)deg(i由于图（ 1）中各顶点的度数均为偶数，所以图（1）为欧拉图。回路abihecdgfa为经过图（ 1）中每个结点一次且仅一次的回路，所以回路abihecdgfa为哈密尔顿回路，因此图（ 1）是哈密尔顿图。图（ 2）中各顶点的度数为2)deg(1v，4)deg(2v，3)deg(3v，4)deg(4v，5)deg(5v，4)deg(6v，2)deg(

66、7v，4)deg(8v，2)deg(9v由于图（ 2）中有两个奇度顶点，所以图（2）存在欧拉图通路，但是没有欧拉图回路，因此图（2）不是欧拉图。回路2356987412vvvvvvvvvv为经过图 （2）中每个结点一次且仅一次的回路，所以回路2356987412vvvvvvvvvv为哈密尔顿回路，因此图（2）是哈密尔顿图。7. 下列图形中最少需添加几条边才能成为欧拉图 a a b e b d c d c （1）（2）解由于 (1) 只有两个奇度结点，b,e. 因此，要由 (1) 得到一个欧拉图，必须使它们的度数都为偶数。最少需添加一条边才能使(1) 为欧拉图。由于 (2) 有 4 个奇度结点，

67、因此，要由(2) 得到一个欧拉图，必须使它们的度数都为偶数。最少需添加两条边才能使 (2) 为欧拉图。例如，可在 (1) 中添加边 (b,e), 在(2) 中添加边 (a,b),(c,d) a a b e b d 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 33 页，共 40 页 c d c （1）（2）8. 有向图D如下图所示v1v2v3v4e1e2e3e4e5e6e7(1) 求D的邻接矩阵A；(2) 求D中长度为4 的通路数和回路数，并找出D中从1v到4v长度为 4 的所有通路。(3) D是哪类连通图？解： (1) 求D的邻接矩阵01001

68、00001000121A；(2) 10000100100013212A, 01001000010034213A, 10000100100046214AD中长度为4 的通路数为164141)4(ijija，其中对角元素之和为3，D中长度为4 的回路有3 条。由于4A中4)4(14a，所以D中1v到4v长度为 4 的通路有4 条。即6411eeee，6764eeee，6521eeee，6531eeee，其中6521eeee为简单通路。(3) 由于22002200220081484432AAAAB由B可知道D是单向连通图。9. 设有向图EVD,，,54321vvvvvV，其邻接矩阵为精选学习资料 -

69、 - - - - - - - - 名师归纳总结 - - - - - - -第 34 页，共 40 页0010110000010101000001010A(1) 画出有向图D；(2)D中长度为4 的通路有多少条？其中有多少条为回路？(3)D是那类连通图？解： (1) 有向图D为4v3v5v1v2v(2) 由于00404400000404040000040404AD中长度为4 的通路数为32。因对角元素之和为0，故D中无长度为4 的回路。(4) 从图可得D的可达矩阵为1111111111111111111111111P从P可知D是强连通的。10. 设连通图G如下图所示，求它的一棵生成树a b c

70、e f 解： a 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 35 页，共 40 页 b c e f 答案不唯一。五、构造下列推理的证明 1. 证明prrqqp,),(证明：r前提引入；rq前提引入；q析取三段论；)(qp前提引入；qp置换；p析取三段论。2. 证明qtrstsrpqp,证明t前提引入；ts前提引入；s拒取式；rs前提引入；r假言推理；rp前提引入；p拒取式；qp前提引入；q析取三段论。3. 证明rsqpsrqp,),(证明ps前提引入；s前提引入；p析取三段论；)(rqp前提引入；rq假言推理；q前提引入；r假言推理。4. 证

71、明)()()()()()(),()()()(xRxQxxQxCxxRxWxCx证明：)()()(xQxCx前提引入；精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 36 页，共 40 页)()(cQcCEI；)(cC化简；)()()()(xRxWxCx前提引入；)()()(cRcWcCUI；)()(cRcW 假言推理；)(cR化简；)(cQ化简；)()(cRcQ合取引入(10) )()()(xRxQxEG 5. 构造下列推理的证明：每个学术委员会的成员都是专家并且是大学生，有些成员是青年人，所以有些成员是青年专家。解：设xxF:)(是学术委员会的成

72、员，xxG:)(是专家，xxH:)(是大学生，xxR:)(是青年人。前提)()()(),()()()(xRxFxxHxGxFx结论)()()()(xRxGxFx证明：)()()(xRxFx前提引入；)()(cRcFEI；)()()()(xHxGxFx前提引入；)()()(cHcGcF UI；)(cF化简；)()(cHcG假言推理；)(cR化简；)(cG化简；)()()(cRcGcF合取引入(10) )()()()(xRxGxFxEG 6. “有些病人相信所有的医生，病人都不相信骗子，所以医生都不是骗子。”在一阶逻辑中证明以上推理是正确的。精选学习资料 - - - - - - - - - 名师归

73、纳总结 - - - - - - -第 37 页，共 40 页解：记xxF:)(是病人，xxG:)(是医生，xxH:)(是骗子，xyxL:),(相信y。则上述推理符号化为前提：),()()(yxLyGyxFx),()()(yxLyHyxFx结论：)()(xHxGx证明：),()()(yxLyGyxFx前提引入；),()()(yaLyGyaF存在量词消去规则；)(aF化简规则；),()()(yxLyHyxFx前提引入；),()()(yaLyHyaF全称量词消去规则；),()(yaLyHy假言推理规则；),()(yaLyH全称量词消去规则；)(),(yHyaL置换；),()(yaLyGy化简规则；（

74、 10）),()(yaLyG全称量词消去规则；（ 11）)()(yHyG（ 10）假言三段论规则；（ 12）)()(xHxGx（11）全称量词引入规则；六、证明题1. 设21,为集合A上的等价关系, 试证21也是集合A上的等价关系。证明：由于21,是自反的，所以对任意Aa,21,aaaa, 因而21,aa，即21是自反的。若21,ba，则21,baba,由 于21,是对称的，所 以21,abab, 从而21,ab，即21是对称的。若21,cbba，则21,cbbacbba, 由于21,是传递的，所以21,caca, 从而21,ca，即21是传递的。由于21是自反的、对称的和传递的，所以21是等

75、价关系。2. 设wu,为无向连通图G中任意两个顶点，证明：若2),(wud，则存在顶点v，使得),(),(),(wudwvdvud证明： 由于G的连通性，wu,之间必存在短程)2(,121lwvvuvPl，则lwud),(，取v为P上除wu,外的任意一点)11(livi，都有ivu,之间的短程为ivvuvP211，wvi,之间的短程为wvvvPlii112. 否则，若ivu,之间存在比ivvuvP211短的短程ivuuuP211，则wvvvuuuPlii1121比P短，这与P为wu,之间的短程矛盾。同理可证：wvvvPlii112为wvi,之间的短程。因而),(),(wvdvudii等于1P的

76、长度加上2P的长度，而1P的长度加上2P的长度为P的长度，即为l，所以),(),(),(wudlwvdvudii. 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 38 页，共 40 页3. 证明下面四个矩阵关于矩阵乘法运算构成群。1001，1001，1001，1001证明：令A为由上述四个矩阵组成的集合，是矩阵乘法运算，容易验证上述四个矩阵关于矩阵乘法运算是封闭的。1.由矩阵乘法运算知识知，是可结合的；2.任取矩阵Aba00，由于baba00100100，baba00001001所以矩阵1001是运算的单位元。3.由于100110011，1001

77、10011，100110011，100110011，所以A中每个元素都是可逆的。由上面的1，2，3 知，,A是群。4. 设,G是一个群，试证G是交换群当且仅当对任意的Gba, , 有222)(baba . 解：充分性若在群,G中，对任意的Gba, , 有222)(baba . 则)()()()(bababbaabababbaa)()(abba从而,G是一个交换群。必要性若,G是一个交换群，对任意的Gba, , 有abba，则bababbaa)()()()()()(bababbaa即222)(baba. 5. 设a是群,G的元素，记|yaayGyyH且，证明,H是,G的子群证明：由于对任意的Hy

78、x,，有ayyaaxxa,所以ayaaxayx111)()(ayaax)()(11aayxa1)()(ayaxa1)()(aayxa11)(1yxa即Hyx1，由子群的判定定理知,H是,G的子群。精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 39 页，共 40 页6. 设,G是一个群，取定Gu，定义buaba1*，Gba,证明,*G是一个群。证明显然， *是G上的二元运算。先证结合律成立。Gcba,，有cubuacba11)(*)*()(11cubua)*(1cbua)*(*cba即运算是可结合的. 由于Ga，有auuaua1*aauuau1*故u是运算 * 的单位元 . 最后证明Ga，uau1是a在,*G中的逆元。由于)()(*111uauuauauauauua11)(uaa)(1uauuauauau111)(*)(auuau)(11)(1aauu因此,*G是一个群 . 精选学习资料 - - - - - - - - - 名师归纳总结 - - - - - - -第 40 页，共 40 页