东北师范大学2013年《离散数学》练习题和答案.doc 58页

'《离散数学》练习题一一、单项选择题1．设集合，则下面集合与相等的是。A．B．C．D．2．设，是集合上的整除关系，下列叙述中错误的是。A．4，5，6全是的极大元B．没有最大元C．6是的上界D．1是的最大下界3.设，，则下列关系中为从到的映射是。A．B．C．D．4.设是4阶群，则其子群的阶不能是下面的。A.1B.2C.3D.45．设，则下列集合中等于的是。　A．　　B．　C．　　D．6．下面有关集合之间的包含和属于关系的说法，正确的是。Ⅰ．Ⅱ．Ⅲ．Ⅳ．A．Ⅰ和ⅡB．Ⅰ和ⅢC．Ⅰ和ⅣD．Ⅱ、Ⅲ和Ⅳ7.设为个元素的集合，则上有个二元关系。A．B．C．2D．8.数的加法在下列集合中上是封闭的。　A．　　B．　C．　　D．9.下列图形中为欧拉图的是。10．设是格，，且，则。16 A.=B.C.D.没关系11．设，则有。A．B．C．D．12.。A．B．C．D．13.对于一个只有4个不同元素的集合来说，上的不同的二元关系的总数为。A．4B．16C．D．14.下列代数系统中，不构成群。A．，*是模11乘法B．，*是模11乘法C．为有理数集，*是普通加法D．为有理数集，*是普通乘法15.设为有个顶点的简单图，则有。A．B．C．D．16．设，则下列集合中等于的是（）。　A．　　　　B．　C．　　　　　　　D．17．设，下列选项正确的是（）。A．B．C．D．18．设为个元素的集合，则上有（）个二元关系。A．B．C．2D．19．数的加法在下列集合中（）上是封闭的。　A．　　B．　C．　　D．20．下列图形中为欧拉图的是（）。16 21．设，则下列集合中等于的是（）。　A．　　　　B．　C．　　　　　　　D．22．设，下列选项正确的是（）。A．B．C．D．23．设为个元素的集合，则上有（）个二元关系。A．B．C．2D．24．数的加法在下列集合中（）上是封闭的。　A．　　B．　C．　　D．25．下列图形中为欧拉图的是（）。26．下列命题中，是错误的。A.B.C.若，则且D.若，则27．幂集是。A．B．16 C．D．28.下列命题公式中为重言式。Ⅰ．Ⅱ．Ⅲ．Ⅳ．A.ⅢB.Ⅰ和ⅢC.Ⅰ和ⅡD.Ⅰ、Ⅱ、Ⅲ和Ⅳ29．任意一个具有多个等幂元的半群(若元素满足，则称为等幂元)，该半群。A．不能构成群B．不一定能构成群C．必能构成群D．能构成交换群30．设是整数集合，下列集合中关于数的加法和乘法构成整环。A．B．C．D．31．设集合，，，，又规定偏序关系“|”是集合上的“整除”关系，则下列偏序集中能构成格。A．B．C．D．二、填空题1．设为非空集合，且，则上不同的二元关系的个数为，上不同的映射的个数为。2．设、为两个命题，当且仅当时，的真值为1。3.在运算表中的空白处填入适当符号，使成为群。*4.当为数时，必为欧拉图。5.16 某校有足球队员38人，篮球队员15人，排球队员20人，三队队员总数为58人，且其中只有3人同时参加3种球队，那么仅仅参加两种球队的队员人数是。6.命题公式的主析取范式为。7.一棵无向树有两个2度顶点，一个3度顶点，三个4度顶点，则它的树叶数为。8．设：我生病，：我去学校，命题“如果我生病，那么我不去学校”符号化为。9．,为两个命题，当且仅当时，的值为0。10.设是四个非空集合，则的充分必要条件是。11.在有理数集合上定义二元运算*：，则的幺元是。12.设是分配格，若对任意的，都有，则。13.某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是。14.将布尔表达式化简得。15.设：我有钱，：我去看电影，命题“当且仅当我有钱时，我才去看电影”符号化为。16.设是群，且，则。17．命题公式是永（）式。18．的主析取范式中，含有（）个极小项。19.设集合，上有一个划分，那么所对应的等价关系应有（）个序偶。20.在有理数集合上定义二元运算*：，则的幺元是（）。21.一个（）称为布尔代数。22．命题公式是永（）式。23．的主析取范式中，含有（）个极小项。24.设集合，上有一个划分，那么所对应的等价关系应有（）个序偶。25.在有理数集合上定义二元运算*：，则的幺元是（）。26.一个（）称为布尔代数。27．的主析取范式是。(写出一般表示形式即可)16 28．设集合，是上的二元关系，且，则的传递闭包。29．设集合，是上的整除关系，则的关系矩阵，哈斯图为。30.一个连通平面图有9个顶点，它们的度数分别为：2，2，2，3，3，3，4，4，5，则该图共有个面。31.集合上可以定义的二元运算的个数是。三、解答题1.求带权值为1,3,5,5,8,12,14,19的最优二叉树。(只要最终结果，不要求中间过程)(8分)2．求的最小生成树。(只要最终结果，不要求中间过程。)(8分)3.设是平面图，有个顶点，条边，个面，个连通分支，证明：(10分)4.化简下列布尔表达式。(1)(2)(8分)16 5.证明在格中，是格中的偏序关系，，若，则有。(8分)6.设，是的幂集，是集合的对称差运算，已知是群，在群中，求：(1)关于运算的幺元；(2)中每个元素的逆元；(3)求元素，使得。(9分)7.设是半群，其运算表如下(8分)证明：是循环群。*16 8.设是集合上的二元关系，若是自反的和传递的，则。(8分)9.设是格，其中是75的的所有正因数的集合，是上的整除关系，求中每个元素的余元素。(8分)10.证明等价式：。(6分)11.用推理规则证明：。12．设是非空集合上的二元关系，令，证明：具有自反性，对称性。13.设是独异点，并且对于中的每一个元素，都有，其中是幺元，证明：是一个阿贝尔群。16 14.证明：循环群是交换群。15.设是一个格，，且，令其中是格中的偏序关系，证明：是的子格。16.证明在格中，是格中的偏序关系，，若，，则有。17.给定树叶的权为1，4，9，16，25，36，49，64，81，100，试构造一棵最优二叉杩。18.证明：若无向图是不连通的，则其补图是连通的。16 19．(10分)求带权1、2、3、4、5、6、7、8、9、10的最优二叉树。20.(10分)设集合，是上的二元关系，，试求：(1)；(2)的关系图与关系矩阵；(3)、、。21．证明等价式：。22.证明：树是一个偶图。23.设是群，对任意的，令，证明：是的子群。16 24.设为实数集，，对任意的，定义：证明：是双射。25.设是含幺环,且*满足等幂律,在上定义运算+,·,ˉ如下:,,证明:是一个布尔代数，其中0和1分别是关于运算和*的幺元。26．用推理规则证明：(10分)27．设是非空集合上自反的二元关系，证明：也是自反的。(10分)28．设是整数加群，在上定义：，证明：是交换群。(20分)16 29．设是一个格，，且，令其中是格中的偏序关系，证明：是的子格。(15分)30．给定树叶的权为1，4，9，16，25，36，49，64，81，100，试构造一棵最优二叉杩。(10分)31．假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂，但是根据EPA(美国环保署)的规定，这些化学产品不能全部都装在同一节车厢里运输，因为如果它们混和起来，就会产生剧烈反应，从而引发事故，为了使费用最低，厂长希望使用尽可能少的车厢，问最少使用多少车厢？其中共有六种化学产品，不能与、或在同节车厢里运输，不能与或一起运输，不能与一起运输，不能与一起运输。(15分)16 32．用推理规则证明：(10分)33．设是非空集合上自反的二元关系，证明：也是自反的。(10分)34．设是整数加群，在上定义：，证明：是交换群。(20分)35．设是一个格，，且，令其中是格中的偏序关系，证明：是的子格。(15分)36．给定树叶的权为1，4，9，16，25，36，49，64，81，100，试构造一棵最优二叉杩。(10分)37．假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂，但是根据EPA(美国环保署)16 的规定，这些化学产品不能全部都装在同一节车厢里运输，因为如果它们混和起来，就会产生剧烈反应，从而引发事故，为了使费用最低，厂长希望使用尽可能少的车厢，问最少使用多少车厢？其中共有六种化学产品，不能与、或在同节车厢里运输，不能与或一起运输，不能与一起运输，不能与一起运输。(15分)38．(10分)设是从群到群的同态映射，，分别是群与的幺元，令证明：是群的子群。39.(14分)设是群，是的子群，在上定义二元关系如下：对任意的，当且仅当证明：(1)是上的等价关系；(2)对任意的，。40．(10分)用推理规则证明：。41.(10分)设是阶简单无向图，是大于2的奇数，如果中有个奇数度的顶点，那么的补图中奇数度的顶点也是个。42.(12分)设是从格到格的满同态映射，证明：若是有界格，则格也是有界格。43．设在一次国际会议上有7个人，各懂的语言如下：a：英语b：英语和西班牙语c：英语、汉语和俄语d：日语和西班牙语e：德语和汉语f：法语、日语和俄语g：法语和德语16 (1)用无向简单图描述以上事实；(2)他们中间是否任何两个人可对话(必要时通过别人作翻译)。44．设是格，其中是30的所有正因数的集合，是上的整除关系，则(1)求每个元素的余元素；(2)是否为有余格，是否为分配格？并说明理由。《离散数学》练习题二一、填空题1．幂集是。2．集合上可以定义的二元运算的个数是。3．集合上的关系的传递闭包。4．一个连通平面图有8个顶点，它们的度数分别为：2，2，3，3，3，4，4，5，则该图共有个面。5．设集合，是上的整除关系，则的关系矩阵，16 哈斯图为。6．设：我们勤奋，：我们好学，：我们取得好成绩。命题“只要勤奋好学，我们就能取得好成绩”符号化为。7．某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是。8.设集合，是上的二元关系，且，则的对称闭包=。9.设、是集合，若，，则到的单射函数有个。10.整数加法群的幺元是。11.设是分配格，若对任意的，都有，则。12.任何简单图中顶点的度数之和等于边数的倍。13.当为数时，必为欧拉图。14．设：我有钱，：我去看电影，命题“如果我有钱，那么我就去看电影”符号化为。15．某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没有得优，那么两次考试都得优的学生人数是。16 16.设集合，是上的二元关系，且，则的传递闭包=。17.设、是集合，若，，则到的单射函数有个。18.整数加法群的幺元是。19.设是分配格，若对任意的，都有，则。20.无向图中具有一条欧拉回路，当且仅当是连通的，并且所有顶点的度数都是。21.若连通简单平面图有4个顶点，3个面，则有条边。22．设、是集合，其中，，则。23．集合上的关系的传递闭包。17第页（共58页） 24.设是非空集合，则中的幺元是，零元是。25.若连通简单平面图有6个顶点，3个面，则有条边。26.设是格，其中，是整除关系，则3的补元是，6的补元是。27.设、是集合，若，，则到的单射函数有个。28．设集合，则。29．设集合，是上的二元关系，且，则的传递闭包=。30.若连通平面简单图有4个顶点，3个面，则有条边。31.设是非空集合，则中的幺元是，零元是。32.设是格，其中，是整除关系，则8的补元是，4的补元是。33.已知集合和，且，，则从到有个二元关系，从到有个映射。二、单项选择题1．下列集合运算中是正确的。A.B.C.D.2．下面是重言式。A.B.58 C.D.3.的主析取范式是A。A.　　　　　B.C.　　　　D.4.若是一个群，则运算“*”一定满足。A.交换律B.消去律C.幂等律D.分配律5．设是整数集合，下列集合中关于数的加法和乘法构成整环。A．B．C．D．6．如下的哈斯图所示偏序集为格的是。　　Ａ　　　　　Ｂ　　　　　　Ｃ　　　　　　Ｄ7．设，则下列集合中等于的是。A．　　　B．C．　　　　D．8．下列公式中，是析取范式。A.B.C.D.9.下列语句中为命题的是。　A.今天是阴天；　B.你身体好吗？C.我真快乐；　D.请不要走。10.设是连通简单平面图，中有6个顶点8条边，则G的面的数目是。A．2个面    B．3个面C．4个面    D．5个面11.设，是集合上的二元关系，称关系为的关系。58 A.交B.并C.补D.逆12.下面集合中,关于数的减法是封闭的。A．B．C．D．13.设A是有界格，若它也是有余格，只要。　A.每一个元素有一个余元　B.每一个元素至少有两个余元C.每一个元素无余元　　　　D.每一个元素仅有一个余元14．设集合，则下面集合与相等的是。A．B．C．D．15．下列公式中，是关于两个命题变元，的极小项。A．  B．C．     D．16.下列语句中不是命题的是。A.3是奇数　　B.请勿吸烟C.我是中学生　D.4+3>517.数的加法在下列集合上是封闭的。　A．　　B．　C．　D．18.给定下列序列，可构成无向简单图的顶点度数序列的是。A.B.C.D.19.若是一个群，则运算“*”一定满足。A.交换律B.消去律C.幂等律D.分配律20.设是非空集合上的关系，则的对称闭包=。A.B.C.D.21．下列集合运算中是正确的。58 A.B.C.D.22．下面的二元关系中，具有传递性。A.父子关系B.朋友关系C.集合的包含关系D.实数的不相等关系23.设是整数集，且设，对每一个，有，元素0的原象的集合为。A．B．C．D．24.数的加法在下列集合中上是封闭的。　A．　　　　　　B．C．　　D．25.设无向树由3个3度顶点，2个2度顶点。其余顶点都是树叶，则有片树叶。A.3B.4C.5D.626.设命题，的真值是0，命题，的真值是1，则下列公式中真值为1的是。A.　　　B.　　　C.　　D.27．设，，则方程的解集是。A．B．C．D．28．设是非空集合上的关系，则的对称闭包=。A.B.C.D.58 29.数的加法在下列集合中上是封闭的。　A．　　　　B．　C．　D．30.给定下列序列，可构成无向简单图的顶点度数序列的是。A.B.C.D.31.设是整数集，且设，对每一个，有，元素0的原象的集合为。A．B．C．D．32.命题公式为。A.重言式B.可满足式C.矛盾式D.等价式三、判断题1．若，则必有。()2．一个不是自反的关系，一定是反自反的。()3.凡陈述句都是命题。()4．有限半群必存在等幂元。()5.任何非平凡无向图中的奇数度顶点的个数是偶数。()6．设，，，均为非空的集合，已知且，则一定有。()7．一个不是自反的关系，一定是反自反的。()8.“王兰和王英是姐妹”是复合命题。()9.设是代数格，它所诱导的偏序格为，则对任意的，当且仅当。()10．任何非平凡树都至少有两片树叶。()58 11．设是偏序集，是的非空子集，若有上界，则必有最小上界。()12.在有界分配格中，一个元素若有补元，则补元一定是唯一的。()13.“王兰和王英是姐妹”是复合命题。()14．若半群存在左幺元，则左幺元是唯一的。()15.具有两个或多个元素的格中不存在以自身为补元的元素。()16.两个无向图同构的充分必要条件是它们的顶点个数与边的个数分别相等。()四、解答题1．(10分)设，上的二元运算为矩阵的乘法运算，求(1)的运算表；(2)的所有子群；2.(14分)设是一个群，定义集合上的一个关系如下：证明：是集合上的一个等价关系。3.(12分)设是从格到格的满同态映射，证明：若是有界格，则格也是有界格。4.(10分)试用推理规则证明：5.(10分)设是连通简单图，其中每个顶点的度数都是偶数，则对于任一顶点，图的连通分支数小于等于的度数的一半。6．设是格，其中是45的所有正因数的集合，是上的整除关系，则58 (1)求每个元素的余元素；(2)是否为有余格，是否为分配格？并说明理由。7．洛杉矶地区有7家汽车旅游公司，在一天中每家公司最多参观下列景点中的三个不同景点，这些景点是好莱坞、贝弗利山、迪斯尼乐园和通用电影制片厂，同一天中，参观一个景点的旅游公司不能超过一个，第一家旅游公司只参观好莱坞，第二家公司只参观好莱坞和迪斯尼乐园，第三家公司只参观通用电影制片厂，第四家只参观迪斯尼乐园和通用电影制片厂，第五家只参观好莱坞和贝弗利山，第六家只参观贝弗利山和通用电影制片厂，第七家只参观迪斯尼乐园和贝弗利山。请问这些游览可以只安排在星期一、星期三和星期五吗？8．设、是命题公式，试用两种方法分别证明等价式：。9．设是非空集合上的二元关系，若是自反的，证明：是自反的。10.设为实数集，：，对任意的，令，证明：是满射，并说明不是单射。11.证明：任一序集都是格。12.求带权1，2，3，4，5，6，7，8，9，10的最优二叉树。13.设和都是群的子群，令，证明是的子群的充要条件是。14.设为实数集，：，对任意的，令，证明58 是满射，并说明不是单射。15．设、是命题公式，试用两种方法分别证明等价式：。16.证明：三个元素以上的链不是有余格。17.求带权1，2，3，4，5，6，7，8，9，10的最优二叉树。18．设是非空集合上的二元关系，若是自反的，证明：是自反的。19.设，其中是整数集合，证明：是整环，其中运算“+”和“·”是关于数的普通加法和乘法。20．(10分)用推理规则证明：，。21.(20分)设是含幺环,且*满足等幂律,在上定义运算+,·,ˉ如下:,,证明:是一个布尔代数，其中0和1分别是关于运算和*的幺元。22.(15分)证明：在中任意删去条边后所得到的图是哈密尔顿图。12345671-4-62-32-52-313-7-2258 4-41-5-1-6-27-23．(5分)Gladbrook饲料公司有7个谷物箱，要通过谷物管道将它们连接起来，以使谷物能从任意一个箱子转移到其它箱子，为了使建造费用最少，希望建造尽可能少的管道，在两个箱子之间建造管道的费用(以10万美元计)由下表给出，其中“-”表示不能建造管道，应该怎样建造管道才能使费用最少。24．(15分)给定群，其中，是上的模6加法运算，试求：(1)的所有生成元；(2)的所有子群；(3)每个子群的所有右陪集。25.(5分)设集合，是上的二元关系，，试求的关系图与关系矩阵。26.(5分)设集合，是上的二元关系，，试求的关系图与关系矩阵。27.(15分)给定群，其中，是上的模15加法运算，试求：(1)的所有生成元；(2)的所有子群；(3)每个子群的所有右陪集。28．(5分)试用克鲁斯卡尔算法求下列表格所确定的权图的最小支撑树。/47914632007695283479/966156766630158 1463966/837998126720071567837/121317246956669981213/41228330112671724412/29．(15分)证明：如果是一个具有奇数个顶点的偶图，则不是哈密尔顿图。30．(10分)用推理规则证明：，31．(20分)设是一个布尔代数，在上定义运算*，×如下：，证明:是含幺交换环。《离散数学》练习题一答案一、单项选择题（每小题2分，共8分）1—5.DCBCC6—10．ABDCA11—15CBCDA16—20CCBDC21—25CCBDC26—30.DCBAD31.C二、填空题（每空1分，共11分）1．2．、的真值同时为13.*58 4.奇5.126.7.98．9．,的真值都为010.11.012.13.1414.15.或16.17.假18.219.1720.021.有余(补)分配格22.假23.224.1725.026.有余(补)分配格27.28.29.30.731.三、解答题（共81分）3.(10分)设是平面图，有个顶点，条边，个面，个连通分支，证明：。证明：对于图的每个连通分支都是连通平面图，因此由欧拉公式，有……其中分别是第个连通分支中的顶点数、边数和面数，则58 将上述个等式相加，有，即4.(8分)化简下列布尔表达式。(1)(2)解：(1)(2)5.(8分)证明在格中，若，则有。证明：因为，所以，，，，因此，故6.(9分)设，是的幂集，是集合的对称差运算，已知是群，在群中，求：(1)关于运算的幺元；(2)中每个元素的逆元；(3)求元素，使得。解：(1)，对于任意的，有，所以关于运算的幺元是。(2)对于任意的，有，所以的逆元是其自身。(3)，使得。7.(8分)设是半群，其运算表如下*证明：是循环群。证明：从运算表可知，是幺元，与互为逆元，以自身为逆元，所以是群。因为，，，所以是生成元，则是循环群。8.(8分)设是集合上的二元关系，若是自反的和传递的，则。证明：由于是传递的，必有。58 对任意的，因为是自反的，有，从而，所以。综上知，。9.(8分)设是格，其中是75的的所有正因数的集合，是上的整除关系，求中每个元素的余元素。解：由格的哈斯图可知：1与75互为余元素，3与25互为余元素，而5和15没有余元素。10.(6分)证明等价式：。证明：11．用推理规则证明：。证明：(1)(2)(3)(1)(2)(4)(5)(3)(4)(6)(7)(5)(6)12．设是非空集合上的二元关系，令，证明：具有自反性，对称性。证明：显然，所以是自反性的。又所以是对称的。13.设是独异点，并且对于中的每一个元素，都有，其中是幺元，证明：是一个阿贝尔群。证明：由可知，中的每一个元素都以自身为逆元，所以是群。对任意的，有58 所以运算*是可交换的，因此，是一个阿贝尔群。14.证明：循环群是交换群。证明：对任意的，不妨令，其中，则因此循环群是交换群。15.设是一个格，，且，令其中是格中的偏序关系，证明：是的子格。证明：对任意的，则有，从而有即因此，故运算在上是封闭的，所以是的子格。16.证明在格中，是格中的偏序关系，，若，，则有。证明：因为，，，所以，，因此右边，故。18.证明：若无向图是不连通的，则其补图是连通的。证明：因为是不连通的，则至少有两个连通分支，对于其中任意两个顶点，(1)，在同一个连通分支中，则在另一个连通分支中任取一点，与以及与在中皆是不相邻的，因而与以及与在中都是相邻的，那么在中找到一条从到的路。(2)，不在同一个连通分支中，与在中是不相邻的，因而与在中是相邻的，从而在中找到一条从到的路。综上，图中任意两点之间都存在路，所以是连通的。58 20.(10分)设集合，是上的二元关系，，试求：(1)；(2)的关系图与关系矩阵；(3)、、。解：(1)(2)工aaaaaaaaaaa关系图为：(3)21．(10分)证明等价式：证明：58 22.(10分)证明：树是一个偶图。证明：设是一棵树，对任意的，令(1)因为是连通的，所以对任意的，必有或，因此，(2)因为是树，与之间的基本通路有且只有一条，所以，(3)因为是树，中无回路，所以或中的任意的两个顶点不可能是相邻的。综上，是一个偶图。23.(10分)设是群，对任意的，令，证明：是的子群。证明：对任意的，有所以经整理，得所以58 因此，由子群判定定理，是的子群。24.(10分)设为实数集，，对任意的，定义：证明：是双射。证明：(1)对任意的，存在，使得所以是满射。(2)对任意的，若，即所以，有解得：即因此是单射。综上，是双射。25.(10分)设是含幺环,且*满足等幂律,在上定义运算+,·,ˉ如下:,,证明:是一个布尔代数，其中0和1分别是关于运算和*的幺元。证明：(1)由题设条件可知，运算+和·在上是封闭的。(2)对任意的，由书上习题结论，有58 从而有即，运算+和·在上是可交换的。(3)对任意的，有即所以运算·对+是可分配的。另外即所以运算+对·是可分配的。(4)对任意的，有(5)对任意的，有综上，由亨廷顿公理，是布尔代数。58 26．(10分)用推理规则证明：证明：(1)(2)(3)(1)(2)(4)(5)(3)(4)27．(10分)设是非空集合上自反的二元关系，证明：也是自反的。证明：因为是自反的，所以，则，故也是自反的。28.(20分)设是整数加群，在上定义：，证明：是交换群。证明：由题设，运算*在上是封闭的。对任意的，有则，即运算*是可结合的。对任意的，有所以运算*是可交换的。，对任意的，有所以2是关于运算*的幺元。对任意的，，有所以关于运算*，元素的逆元是。综上，是交换群。58 29.(15分)设是一个格，，且，令其中是格中的偏序关系，证明：是的子格。证明：对任意的，则有，从而有即因此，故运算在上是封闭的，所以是的子格。30.证明在格中，是格中的偏序关系，，若，则有。证明：因为，所以，，，因此，故31.(15分)假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂，但是根据EPA(美国环保署)的规定，这些化学产品不能全部都装在同一节车厢里运输，因为如果它们混和起来，就会产生剧烈反应，从而引发事故，为了使费用最低，厂长希望使用尽可能少的车厢，问最少使用多少车厢？其中共有六种化学产品，不能与、或在同节车厢里运输，不能与或一起运输，不能与一起运输，不能与一起运输。兰6兰6666666兰66666666666红5兰2红1白3兰4解58 ：在平面上画六个顶点分别表示六种化学产品，如果两种化学产品不能在一节车厢中运输，则在这两种产品所对应的顶点之间连一条边，从而得到一个无向图，现对该图的顶点着色，如图所示，用了三种颜色，所以最少用三节车厢，第一节车厢装、和，第二节车厢装，第三节车厢装和。32．(10分)用推理规则证明：证明：(1)(2)(3)(1)(2)(4)(5)(3)(4)33．(10分)设是非空集合上自反的二元关系，证明：也是自反的。证明：因为是自反的，所以，则，故也是自反的。34.(20分)设是整数加群，在上定义：，证明：是交换群。证明：由题设，运算*在上是封闭的。对任意的，有则，即运算*是可结合的。对任意的，有所以运算*是可交换的。，对任意的，有所以2是关于运算*的幺元。对任意的，，有58 所以关于运算*，元素的逆元是。综上，是交换群。35.(15分)设是一个格，，且，令其中是格中的偏序关系，证明：是的子格。证明：对任意的，则有，从而有即因此，故运算在上是封闭的，所以是的子格。36.证明在格中，是格中的偏序关系，，若，则有。证明：因为，所以，，，因此，故37.(15分)假设一家化工厂要将多种化学产品利用铁路从精炼厂运到炼油厂，但是根据EPA(美国环保署)的规定，这些化学产品不能全部都装在同一节车厢里运输，因为如果它们混和起来，就会产生剧烈反应，从而引发事故，为了使费用最低，厂长希望使用尽可能少的车厢，问最少使用多少车厢？其中共有六种化学产品，不能与、或在同节车厢里运输，不能与或一起运输，不能与一起运输，不能与一起运输。兰6兰6666666兰66666666666红5兰2红1白3兰4解58 ：在平面上画六个顶点分别表示六种化学产品，如果两种化学产品不能在一节车厢中运输，则在这两种产品所对应的顶点之间连一条边，从而得到一个无向图，现对该图的顶点着色，如图所示，用了三种颜色，所以最少用三节车厢，第一节车厢装、和，第二节车厢装，第三节车厢装和。38．(10分)设是从群到群的同态映射，，分别是群与的幺元，令证明：是群的子群。证明：显然，由于，所以，因此。对任意的，，则有，故所以，由子群判定定理，是群的子群。39.(14分)设是群，是的子群，在上定义二元关系如下：对任意的，当且仅当证明：(1)是上的等价关系；(2)对任意的，。证明：(1)对任意的，因为是的子群，所以，有，所以是自反的。对任意的，则有，因为是的子群，所以有，所以是对称的。对任意的，，则有，，因为是的子群，所以，有，所以是传递的。综上，是等价关系。(2)对任意的，有58 ，对任意的，则，故，令，则所以。对任意的，令，其中，则，所以，故，因此，。综上，。40．(10分)用推理规则证明：。证明：(1)P(2)P(附加前提)(3)P(4)T(1)(3)I(5)T(2)(4)I(6)T(5)I(7)CP41.(10分)设是阶简单无向图，是大于2的奇数，如果中有个奇数度的顶点，那么的补图中奇数度的顶点也是个。证明：对任意的，则，因为是奇数，所以若在中是奇数度顶点，则在中也是奇数度顶点；若在中是偶数度顶点，则在中也是偶数度顶点，因此，如果中有个奇数度的顶点，那么的补图中奇数度的顶点也是个。42.(12分)设是从格到格的满同态映射，证明：若是有界格，则格也是有界格。证明：设的最大元和最小元分别为1与0，往证和是的最大元和最小元。58 对任意的，其中，则，因为是同态映射，所以是保序映射，故有，所以和是的最大元和最小元，因此是有界格。43．设在一次国际会议上有7个人，各懂的语言如下：a：英语b：英语和西班牙语c：英语、汉语和俄语d：日语和西班牙语e：德语和汉语f：法语、日语和俄语g：法语和德语(1)用无向简单图描述以上事实；(2)他们中间是否任何两个人可对话(必要时通过别人作翻译)。解：在平面上做7个点分别表示这7个人，如果两个人会同一门语言，则在对应的两个点之间连一条边，则得到一个连通图，因此任何两个人可对话。44．设是格，其中是30的所有正因数的集合，是上的整除关系，则(1)求每个元素的余元素；(2)是否为有余格，是否为分配格？并说明理由。解：(1)，1与30、2与15、3与15、6与5互为余元素。(2)因为每个元素都存在余元素，所以是有余格。因为中不存在与五元素格同构的子格，所以是分配格。58 《离散数学》练习题二答案一、填空题（每空2分，共12分）1.2.3.4.75.6.7.148.9.610.011.12.213.奇14.15.1416.17.618.019.20.偶数21.522.23.24.、25.726.8、不存在27.628.29.30.531.、32.3、不存在33.、58 二、单项选择题（每小题2分，共12分）1.B2.D3.A4.B5.D6.D7.C8.D9.A10.C11.D12.B13.A14.D15.C16.B17.C18.B19.B20.A21.B22.C23.A24.C25.C26.D27.B28.D29.C30.B31.A32.C三、判断题1．T2．F3.F4．T5.T6．T7．F8.F9．T10.T11．F12．T13.F14．F15．T16.F三、解答题1．(10分)设，上的二元运算为矩阵的乘法运算，求(1)的运算表；(2)的所有子群；解：为方便起见，令，，，，则(1)*(2)、，，，58 2.(14分)设是一个群，定义集合上的一个关系如下：证明：是集合上的一个等价关系。证明：对任意的，，使得，则，所以是自反的。对任意的，则，使得，有则，所以是对称的。对任意的，则，使得及，有则，所以是传递的。综上，是等价关系。3.(12分)设是从格到格的满同态映射，证明：若是有界格，则格也是有界格。证明：设的最大元和最小元分别为1与0，往证和是的最大元和最小元。对任意的，其中，则，因为是同态映射，所以是保序映射，故有，所以和是的最大元和最小元，因此是有界格。4.(10分)试用推理规则证明：①②①③④③58 ⑤②④⑥⑦⑥⑧③⑦⑩⑤⑧⒒⑩5.(10分)设是连通简单图，其中每个顶点的度数都是偶数，则对于任一顶点，图的连通分支数小于等于的度数的一半。证明：由于中每个顶点的度数都是偶数，所以中奇顶点的数目等于的度数，并且在中与相邻，其余的顶点的度数仍为偶数。由于是连通的，所以的每个连通分支中都有原来在中与相邻的顶点。然而，的每个连通分支都可以看作是一个完整的图，所以每个分支中原来与相邻的顶点至少有两个，并且不同的连通分支中没有公共的奇顶点，所以的连通分支数小于等于奇顶点数目的一半，也就是的度数的一半。6．设是格，其中是45的所有正因数的集合，是上的整除关系，则(1)求每个元素的余元素；(2)是否为有余格，是否为分配格？并说明理由。解：(1)，1与45、5与9互为余元素；3与15不存在余元素。(2)因为3与15不存在余元素，所以不是有余格。因为中不存在与五元素格同构的子格，所以是分配格。兰2红3白4白5兰6红7红17．58 洛杉矶地区有7家汽车旅游公司，在一天中每家公司最多参观下列景点中的三个不同景点，这些景点是好莱坞、贝弗利山、迪斯尼乐园和通用电影制片厂，同一天中，参观一个景点的旅游公司不能超过一个，第一家旅游公司只参观好莱坞，第二家公司只参观好莱坞和迪斯尼乐园，第三家公司只参观通用电影制片厂，第四家只参观迪斯尼乐园和通用电影制片厂，第五家只参观好莱坞和贝弗利山，第六家只参观贝弗利山和通用电影制片厂，第七家只参观迪斯尼乐园和贝弗利山。请问这些游览可以只安排在星期一、星期三和星期五吗？解：在平面上画七个点分别表示七家旅游公司，如果两家公司参观同一个景点，则在这两家公司所对应的顶点之间连一条边，从而得到一个无向图，现对该图的顶点着色，如图所示，用了三种颜色，所以这些游览可以只安排在三天里，星期一安排第二家和第六家；星期三安排第一家、第三家和第七家；星期五安排第四家和第五家。8．设、是命题公式，试用两种方法分别证明等价式：。证明：等价演算法：真值表法：1101001010110101000011009．设是非空集合上的二元关系，若是自反的，证明：是自反的。证明：因为是自反的，所以，又，则，所以是自反的。10.设为实数集，：，对任意的，令，证明：是满射，并说明不是单射。证明：对任意的，存在，使得，所以是满射。由于，而，所以不是单射。58 11.证明：任一序集都是格。证明：设是序集，对任意的，则或，于是(1)若，因为，，所以是与的下界，是与的上界。设是与的任一下界，则，所以是与的最大下界。设是与的任一上界，则，所以是与的最小上界。(2)若，同理可证，是与的最大下界，是与的最小上界。所以是格。12.求带权1，2，3，4，5，6，7，8，9，10的最优二叉树。解：2113.设和都是群的子群，令，证明是的子群的充要条件是。证明：必要性。对任意的，因为是的子群，所以，不妨令，从而有58 所以。对任意的，有因为，和都是的子群，所以，，，所以，综上有。充分性。对任意的，，则有而，因为，故，不妨令，则有由子群判定定理，是的子群。14.设为实数集，：，对任意的，令，证明：是满射，并说明不是单射。证明：对任意的，存在，使得，所以是满射。由于，而，所以不是单射。15．设、是命题公式，试用两种方法分别证明等价式：。证明：等价演算法：真值表法：11010010101101010000110058 16.证明：三个元素以上的链不是有余格。证明：设是链，则是格。假设是有余格，则中每个元素都存在余元素，因为0与1互为余元素，而中至少有三个元素，设，且，，的余元素为，由于是链，则或，于是(1)若，则有，又的余余元素为，有，与矛盾。(2)若，则有，又的余余元素为，有，与矛盾。所以不是有余格。17.求带权1，2，3，4，5，6，7，8，9，10的最优二叉树。解：2118．设是非空集合上的二元关系，若是自反的，证明：是自反的。证明：因为是自反的，则，而，所以，故是自反的。19.设，其中是整数集合，证明：是整环，其中运算“+”和“·”是关于数的普通加法和乘法。证明：(1)对任意的，(其中)，有58 所以运算“+”和“·”在上是封闭的。(2)显然运算“+”和“·”在上满足交换性、结合性；运算“·”对“+”满足分配性；运算“·”满足消去律。(3)关于运算“+”的幺元。(4)关于运算“·”的幺元。(5)对任意的(其中)，关于运算“+”的逆元为。20．(10分)用推理规则证明：，。证明：(1)(附加前提)(2)(1)(3)(4)(2)(3)(5)(4)(6)(5)(7)(8)(6)(7)(9)21.(20分)设是含幺环,且*满足等幂律,在上定义运算+,·,ˉ如下:,,证明:是一个布尔代数，其中0和1分别是关于运算和*的幺元。证明：(1)由题设条件可知，运算+和·在上是封闭的。(2)对任意的，由书上习题结论，有从而有即，运算+和·在上是可交换的。(3)对任意的，有58 即所以运算·对+是可分配的。另外即所以运算+对·是可分配的。(4)对任意的，有(5)对任意的，有综上，由亨廷顿公理，是布尔代数。22.(15分)证明：在中任意删去条边后所得到的图是哈密尔顿图。证明：设是在中任意删去条边后所得到的图，是中任意两个不相邻的顶点，则在中都关联着条边，现由于删去条边，设其中有条所关联的边，条所关联的边，于是58 ，则因为总共删去条边，所以，则因此是哈密尔顿图。23．(5分)Gladbrook饲料公司有7个谷物箱，要通过谷物管道将它们连接起来，以使谷物能从任意一个箱子转移到其它箱子，为了使建造费用最少，希望建造尽可能少的管道，在两个箱子之间建造管道的费用(以10万美元计)由下表给出，其中“-”表示不能建造管道，应该怎样建造管道才能使费用最少。12345671-4-62-32-52-313-7-224-41-5-1-6-27-5172463或者64271558 324．(15分)给定群，其中，是上的模6加法运算，试求：(1)的所有生成元；(2)的所有子群；(3)每个子群的所有右陪集。解：(1)，所以的所有生成元为，即1，5。(2)，，(3)，，，，，，，，25.(5分)设集合，是上的二元关系，，试求的关系图与关系矩阵。解：关系矩阵为关系图为：工aaaaaaaaaaa58 26.(5分)设集合，是上的二元关系，，试求的关系图与关系矩阵。工aaaaaaaaaaa解：关系矩阵为关系图为：27.(15分)给定群，其中，是上的模15加法运算，试求：(1)的所有生成元；(2)的所有子群；(3)每个子群的所有右陪集。解：(1)，所以的所有生成元为即(2)，，(3)，，，…，，，，58 28．(5分)试用克鲁斯卡尔算法求下列表格所确定的权图的最小支撑树。/47914632007695283479/96615676663011463966/837998126720071567837/121317246956669981213/41228330112671724412/29．(15分)证明：如果是一个具有奇数个顶点的偶图，则不是哈密尔顿图。证明：因为是偶图，不妨设，，且中任意两个相邻的顶点，必是一个取自于，另一个取自于，由于是奇数，而所以，不妨设，现在中删除中所有的顶点，所得的子图恰好是中所有的顶点，且都是孤立的顶点，所以，因此不是哈密尔顿图。30．(10分)用推理规则证明：，证明：(1)(附加前提)(2)(3)(2)(4)(1)(3)(5)58 (6)(5)(7)(4)(6)(8)31．(20分)设是一个布尔代数，在上定义运算*，×如下：，证明:是含幺交换环。证明：因为是布尔代数，所以运算具有交换性、结合性以及分配性，1是最大元，0是最小元，则(1)由运算*，×的定义，显然运算*，×在上是封闭的。(2)由运算×的定义，显然运算×具有交换性和结合性。(3)因为1是最大元，则对任意的，有，所以1是关于运算×的幺元。(4)对任意的，有所以运算*具有交换性。(5)对任意的，有同理可证，所以，因此运算*具有结合性。(6)因为0是最小元，则对任意的，有所以0是关于运算*的幺元。58 (7)对任意的，存在，有所以对于每个元素，关于运算*存在逆元。(8)对任意的，有所以，即运算×对*满足分配律。综上，是含幺交换环。58'