洪帆《离散数学基础》第三版课后习题答案.pdf

1 第第 1 章章 集合集合 1、列举下列集合的元素 (1) 小于 20 的素数的集合 (2) 小于 5 的非负整数的集合 (3) 2 |,10240515i iI iii是偶数且或 是奇数且 (6) |6n n是 的倍数 答：1,2,3,4,5,6,7,8,9,10,11A =，1,2,3,4,5,6,7,8B = 2,4,6,8,C =，3,6,9,12,D =，1,3,5,7,E = 2,4,6,8BC= 3,6,9=AD 10=()ABDE (4) |369n nnn=或或369,10,11,12, 3,6,9,10,11,12,()AD B = (5) 2,4,6,8,10,11,13,15,()()()AEEBADB= (6) |66,12,18,24,30n n=是 的倍数CD 12、 判断以下哪些论断是正确的，哪些论断是错误的，并说明理由。 (1) 若aA，则aAB 5 答：正确，根据集合并的定义 (2) 若aA，则aAB 答：显然不正确，因为根据集合交运算的定义，必须a同时属于A和B (3) 若aAB，则aB 答：正确 (4) 若AB，则ABB= 答：错误 (5) 若AB，则ABA= 答：正确 (6) 若aA，则aAB 答：错误 (7) 若aA，则aAB 答：正确 13、 设, ,A B C是任意的集合，下述论断哪些是正确的？哪些是错误的？说明理 由 (1) 若ABAC=，则BC= 答：不正确，反例，设A=，则不论,B C是什么集合，都有ABAC=， 但显然,B C不一定相等。 (2) 当且仅当ABB=，有AB； 答： 正确， 证明如下： 若ABB=， 则对aA ， 有aABB=， 则有aB， 因此有AB。反之，若AB，则ABB=显然成立。 (3) 当且仅当ABA=，有AB 答：正确，证明如下：若ABA=，则对aA ，因此aAB，则aB， 则有AB。 若AB， 则aA ， 有aB， 因此由aA， 可以得出aAB， 因此AAB，又ABA，有ABA=。 6 (4) 当且仅当AC，有()ABC= 答：不正确，因为()ABCAB C =，因此不一定需要满足AC，而若 AB=也可以满足。 例如： , , Aa b c=， , Bd e=， , Ca b=，()ABC= 成立，而AC不成立。 (5) 当且仅当BC，有()ABCA= 答：不正确，因为若BC，有()ABCA=成立，但是反之不成立，反例如 下:1,2,3,4,5A =，1,6B =，1,2C =，而2,3,4,5AB=， ()1,2,3,4,5ABC=，但是BC不成立。 14、 设, ,A B C D是集合，下述哪些论断是正确的？哪些是错误的？说明理由。 (1) 若,AB CD，则()ACBD 答： 正确， 证明： 对aAC ， 则aA或aC， 因为,AB CD， 因此aB 或aD，因此aBD，即()ACBD成立。 (2) 若,AB CD，则()ACBD 答：正确 (3)若AB，CD，则()ACBD 答：正确 (4) 若,AB CD，则()ACBD 答：不正确。例如若,AB CD，但是AC=，BD=，则 ()ACBD=。 15、 设,A B是两个集合，问： (1)如果ABB=，那么A和B有什么关系？ 答：因为ABB=，而ABABB=，即对aB 有,aA a B ，因此 7 AB=。 (2) 如果ABBA=，那么A和B有什么关系？ 答：充要条件是AB=。证明：因为ABBA=的()()ABABAA=，从 而有AAB=，即AB，同理可证明BA，因此AB=。 16、 设,A B是任意集合，下述论断哪些是正确的？哪些是错误的？说明理由。 (1) 222 ABAB = 答：不正确。例如 , Aa b=， , Bb c=，则 , , ABa b c= 2 , , , , , , , , , , , , AB abca ba cb ca b c = 2 , , , , A aba b=，2 , , , , B bcb c= 显然222 ABAB =不成立。 (2) 222 ABAB = 答：成立。证明：对22 AB C，则2AC且2BC，则,CA CB，则 CAB， 因此2A B C 。 反之， 若2A B C ， 则CAB， 则CA且CB， 因此2AC，且2BC，因此22 AB C，即222 ABAB =。 (3) 2(2 ) AA = 答：显然不成立，因为左边集合肯定含有，而右边不含有。 17、 在一个班级的 50 个学生中，有 26 人在离散数学的考试中取得了优秀的成 绩；21 人在程序设计的考试中取得了优秀的成绩。假如有 17 人在两次考试中都 没有取得优秀成绩，问有多少人在两次考试中都取得了优秀成绩? 答： 分别用,A B表示在离散和程序设计的考试中取得优秀成绩的学生集合，U表 示全体学生集合：则#( )26A =，#( )21B =，#()50 1733AB=，则两次考试 中都取得了优秀成绩的学生人数为 26+21-33=14 人。 18、 设, ,A B C是任意集合，运用成员表证明： (1) ()()()()ABACACAB= 证明： 8 A B C A AC AB AC AB 左边 右边 0 0 0 1 1 0 0 0 0 0 0 0 1 1 1 0 0 0 0 0 0 1 0 1 1 1 0 1 1 1 0 1 1 1 1 1 0 1 1 1 1 0 0 0 0 1 0 0 0 0 1 0 1 0 1 1 1 0 1 1 1 1 0 0 0 1 0 0 0 0 1 1 1 0 1 1 1 0 1 1 (3) ()()()ABCABAC= 证明： A B C AB AC ()()ABAC BC ()ABC 0 0 0 0 0 0 0 0 0 0 1 0 0 0 1 0 0 1 0 0 0 0 1 0 0 1 1 0 0 0 1 0 1 0 0 1 1 1 0 1 1 0 1 1 0 0 1 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 1 0 由上得证左右两边相等。 19、由S和T的成员表如何判断ST？应用成员表证明或否定 ()()ABBCAB 答：先分别给出集合()()ABB C 和A B 的成员表如下： A B C AB BC ()B C ()()ABB C B A B 0 0 0 0 0 1 0 1 0 0 0 1 0 1 0 0 1 0 0 1 0 1 1 0 0 0 0 0 1 1 1 1 0 0 0 0 1 0 0 1 0 1 1 1 1 1 0 1 1 1 0 0 1 1 1 1 0 1 1 0 0 0 0 1 1 1 1 1 0 0 0 0 观察上述表格，我们发现()()ABB C 所标记的列中，仅在第五列为 1，这 9 意味着当元素,uA uB且uC时，()()uABB C ，而在其他情形下， 元素()()uABB C 。而集合A B 所标记的列中，第五和第六行均为 1， 这意味着,uA uB且uC时，uA B ，当,uA uB，且uC时，也有 uA B 。所以当元素()()uABB C 时也有uA B ，反之不然，因 此()()ABBCAB成立。 20、 12 , r A AA为U的子集， 12 , r A AA至多能产生多少不同的子集？ 答： 构造由 12 , r A AA所产生的集合的成员表， 显然该成员表由2r个行所组成。 在该成员表中不同的列可由2r为的二进制数 000011111 分别表示， 而不同 的列所标记的集合 不相同的，因此由 12 , r A AA至多可以产生 2 2 r 个不同的集 合。 21、证明分配律、等幂律和吸收律 9 1 分配律 ()()()ABCABAC= 证明： 对()aABC ， 则有aA且aBC， 即有aA， 且aB或aC， 也即有aAB或aAC，即()()aABAC，因此左边右边。 对()()aABAC ，则aAB或aAC，即aA且aB， 或aA且aC，即有aA或aBC，因此()aABC，因此右边左 边。 2 吸收律()AABA= 证明：()AABA显然成立，对aA ，则显然有aAB，因此有 ()aAAB，因此有()AAAB成立。 22、设, ,A B C是任意集合，运用集合运算定律证明： (1) ()BABAU= 10 证明： () ()()() ()() BABA BABABAAAB BUABBABU = = = 左边 右边 (2) ()()()()()()ABBCCAABBCCA= 证明： ()() ()()() ()()()() ()()()() BACCA CABCAAC CBBAACAACC CBBAACAC = = = = 左边 右边 (3) ()()()()()()ABBCACABABCABC= 证明： ()() ()()() ()() ()()() ()() ()()() ()() ()()() BACAABC BAAACABC BACABC BABCABC BCABCB BCABBBC BCABC BCABAC = = = = = = = = 右边 由上题的证明可知左边=右边，得证。 23、用得摩根定律证明()()ABABC补集是 ()()()ABABAC。 证明： ()() () )() ()() ) ()() ()()() ABABC ABABC ABABC ABABC ABABAC = = = = 24、设 i A为某些实数的集合，定义为 0 |1 1 |1 (1,2,) i Aa a Aa ai i =， 因此 11 11 1 a k b = 解： 定义域6,5,4,3,2D=，5,4,3,2,1R= (5) ( , )|i jij=，则在A中必存在1k个元素 121 , k iii aaa，使得： baaaaa k iiii 1211 , 因为nk ，所以在baaaa k iii , 121 这1+k个元素中必有两个元素 tr ii aa= （ktr 1 ，用类似的方法又可找到 12 kk 时，有 21 nn； 答： 非自反的， 因为11不成立， 但N1。 对称的， 非可传递的， 因为101，210， 但是21不成立。 （3）当且仅当),( | 2121 Rrrrr时，有 21 rr。 答：自反的，非对称的，非可传递的，因为)8(5，18，但是15不成立。 23 + = 1 n i i = 1 n i i = 1 i i = 19 21、设 1 和 2 是集合A上的任意两个关系，判断下列命题是否正确，并说明理 由： （1）若 1 和 2 是自反的，则 21 也是自反的； 答： 正确。 因为 1 和 2 是自反的， 因此对任意Aa， 有aaaa 21 ,， 因此aa 21 ， 所以 21 也是自反的。 （2）若 1 和 2 是非自反的，则 21 也是非自反的； 答：错误；例如,cbaA =，),(),(),( 1 acbbaa=，),(),(),( 2 cabbaa=， 1 和 2 都是非自反的，但是),(),(),( 21 ccbbaa=是自反的。 （3）若 1 和 2 是对称的，则 21 也是对称的； 答：错误，设,cbaA =，),(),( 1 abba=，),(),( 2 acca=，显然 1 和 2 是对称的，但是),( 21 cb=是非对称的。 （4）若 1 和 2 是反对称的，则 21 也是反对称的； 答：错误，设,cbaA =，),(),( 1 ccba=，),(),( 2 accb=，显然 1 和 2 是 反对称的，但是),(),( 21 acca=不是对称的。 （5）若 1 和 2 是可传递的，则 21 也是可传递的； 答：错误，设,cbaA =，),(),(),( 1 cacbba=，),(),(),( 2 abaccb=，显 然 1 2 是可传递的，但是),(),(),( 21 abaaca=却是不可传递的。 22、证明若是对称的，则对任何整数1k， k 也是对称的。 证明：数学归纳法，当2=k时，若 2 ),(ba，则根据复合关系的定义，存在元 素c，使得),( ,),(bcca，因为是对称的，所以),( ,),(cbac，所以 2 ),(ab，因此 2 是对称的，假设当kn =时成立，则当1+= kn时，若 1 ),( + k ba， 则存在元素 1 c， 使得),( ,),( 11 bcca k ， 因为和 k 是对称的， 因此),( ,),( 11 cbac k ，所以 1 ),( + k ab ，因此： 1+= kn 时成立，即得证。 23、已知1,2,3,4A =和定义在A上的关系(1,2),(4,3),(2,2),(2,1),(3,1)=，试 证明不是可传递的。求出一个关系 1 ，使得 1 是可传递的，你能求出另 一个关系 2 也是可传递的嘛？ 答：证明：显然不是可传递的，因为(1,2)，(2,1)，但是(1,1)。 1 (1,2),(4,3),(2,2),(2,1),(3,1),(1,1),(4,1),(4,2)=，能找出另一个关系。 1 (1,2),(4,3),(2,2),(2,1),(3,1),(1,1),(4,1),(4,2),(3,3)=。 20 24、图 2-10 表示在1,2,3上的 12 个关系的关系图。试对每一个这样的图，确定 其表示的关系是自反的还是非自反的；是对称，非对称还是反对称；是可传递的 还是不可传递的？ 答： 自反的、非对称的、非反对称的，非可传递的 自反的、对称的，非反对称的、可传递的 非自反的、非对称的、反对称的、可传递的 21 自反的、非对称的、反对称的、可传递的 25、图 2-11 给出了1,2,3上的两个关系的关系图，这些关系是等价的吗？ 答： (a) (b) 答： 图(a)表示的关系(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)=具有自反性， 对称 性，但是不具有传递性，因为有(2,1),(1,3)，但是(2,3)，因此不是等价关 系。 图(b)表示的关系(1,1),(2,2),(3,3),(1,2),(2,1)=， 具有自反性， 对称性， 传递性， 因此是等价关系。 26、在N上的关系定义为当且仅当/ ij nn可以用形式2m表示时，有 ij nn，这 里m是任意整数： (1)证明是等价关系 证明：对nN ， 0 /12n n = =，因此n n，所以关系具有自反性。 对, i jN， 若ij， 即存在m， 使得/2mij =， 则有/2 m j i =， 因此有j i。 所以关系具有对称性。 对, ,i j kN， 若ij， 且j k， 即存在 12 ,m m， 使得 1 /2mij =， 2 /2mj k =， 则 12 /2m m i k + =，因此有i k，所以关系具有传递性。 综上可得关系是等价关系。 (2) 找出的所有等价类 答： 1 ,3 ,5 ,21 N k =+ 27、有人说，集合A上的关系，如果是对称的且可传递的，则它也是自反的， 11,2,4,8,16,2 ,0,1,2,3,4, 33,6,12,24,3 2 ,0,1,2,3,4, 55,10,20,40,5 2 ,0,1,2,3,4, k k k k k k = = = 22 其理由是，从 ij aa，由对称性得 ji aa，再由可传递性便得 ii aa。 答：这种说法是错误的。例如，1,2,3A =，(1,2),(2,1),(1,1)=，显然是对 称的，且是可传递的，但是它不是自反的。 28、 设有集合A和A上的关系， 对于所有的, ijk a a aA， 若由 ij aa和 jk aa可 推得 ki aa，则称关系是循环的，试证明当且仅当是等价关系时，是自反 且循环的。 证明：先证充分性 若是等价关系，则是自反的，对称的，可传递的。对于所有的, ijk a a aA， 若 ij aa且 jk aa，则 ik aa，由对称性则有 ki aa，因此关系是循环的。 再证必要性 若对于所有的, ijk a a aA，若有 ij aa，又由自反性，有 jj aa，则由是循环 的，可得 ji aa成立，即具有对称性。 若对于所有的, ijk a a aA，若由 ij aa和 jk aa，由是循环的有 ki aa，由对称 性可得 ik aa，因此具有可传递性。 又由是自反的，则是等价的。 29、设 1 和 2 是A上的等价关系，试证明：当且仅当 1 A 中的每一等价类都包含 于 2 A 的某一等价类中时，有 12 。 证明：先证充分性 设 1 A 中的每一个等价类都包含于 2 A 的某一个等价类中，对任一 1 ( ,) ij a a，有 1ij aa，因此 11 , iiji aaaa 。又由假设必有某元素bA存在，使得 12 i ab ，因此有 2 i ab ， 2 j ab ，所以 2 ( ,) ij a a，故有 12 。 再证必要性： 设 12 ，并设 1 i a 是 1 A 中任一等价类，对任一 1 i xa ，有 1i ax，即 1 ( , ) i a x，由假设 2 ( , ) i a x，即 2 i xa ，故有 12 ii aa 。 30、已知 1 和 2 是集合A上分别有秩 1 r和 2 r的等价关系，试证明 21 也是A 上的等价关系，它的秩最多为 21r r，再证明 21 不一定是A上的等价关系。 证明：由交集的定义 1212 ( , )|( , )( , )a ba ba b=且 对于aA ，因为 12 , 都是自反的，所以 1 ( , )a a，且 2 ( , )a a，因为 12 ( , )a a，所以 12 是自反的。 对于, a bA，若 12 ( , )a b，则 1 ( , )a b， 2 ( , )a b，由 1 和 2 的对称 性知 1 ( , )b a，且 2 ( , )b a，因而有 12 ( , )b a，故 12 是对称的。 23 对于, ,a b cA， 若 12 ( , )a b， 12 ( , )b c， 则有 1 ( , )a b， 1 ( , )b c， 2 ( , )a b， 2 ( , )b c， 由 12 , 的 传 递 性 知 1 ( , )a c， 2 ( , )a c， 因 而 12 ( , )a c，故 12 是可传递的。所以 21 也是A上的等价关系。 对于 12 ，由并集的定义知 1212 ( , )|( , )( , )a ba ba b=或者 对于aA ， 因为 1 是自反的， 所以 1 ( , )a a， 因而 12 ( , )a a， 所以 12 是自反的。对于, a bA，若 12 ( , )a b，则 1 ( , )a b或者 2 ( , )a b，由于 1 和 2 都是对称的，因此有 1 ( , )b a或者 2 ( , )b a，因而有 12 ( , )b a， 故 12 也是对称的。 对于任意的, ,a b cA，若 12 ( , )a b， 12 ( , )b c，则 1 ( , )a b或者 2 ( , )a b； 1 ( , )b c或者 2 ( , )b c，因为( , )a b和( , )b c不一定能同时属于 1 ， 也不一定能同时属于 2 ，所以无法推出 1 ( , )a c或者 2 ( , )a c，因而也就无法 推出 12 ( , )a c，这说明 12 的可传递性不一定能成立，因此推不出 12 是A上的等价关系。 反 例 ： 设1,2,3A =，A上 的 关 系 1 (1,1),(2,2),(3,3),(1,3),(3,1)=， 2 (1,1),(2,2),(3,3),(1,2),(2,1)=， 显 然 1 和 2 均 是 等 价 关 系 。 12 (1,1),(2,2),(3,3),(1,3),(3,1),(1,2),(2,1)=， 这里 12 是自反的， 对称的， 但是不可传递的。 31、设 1 是集合A上的一个关系， 211 ( , )|,( , )( , )a bca cc b=存在 使且。 试证明：若 1 是一个等价关系，则 2 也是一个等价关系。 证明：因为 1 是自反的，因此对aA ，有 1 ( , )a a，由 1 ( , )a a，因此 有 2 ( , )a a，故 2 是自反的。 对于任意的, a bA，若 2 ( , )a b，则必有元素cA，使得 1 ( , )a c且 1 ( , )c b，由 1 的对称性又有 1 ( , )b c且 1 ( , )c a，因而有 2 ( , )b a，故 2 是 对称的。 对任意的, ,a b cA，若 2 ( , )a b， 2 ( , )b c，则必有元素,d eA，使得： 11 ( , ),( , )a dd b 11 ( , ),( , )b ee c 由 1 的可传递性，又有 1 ( , )a b， 2 ( , )b c，于是又有 2 ( , )a c，故 2 是 可传递的。 由上得证 2 是一个等价关系。 32、设A是由 4 个元素组成的集合，试问在A上可以定义多少个不同的等价关 系？ 24 答：根据等价关系与分划一一对应，将A分划为一块：有一种方法，将A分划为 两块：2+2 方式有 1/2 2 4 C种，1+3 方式有 1 4 C种 将A分划为三块：只能是 1+1+2 方式，有 2 4 C种 将A分划为四块：有一种方法 因此集合A上不同等价关系的个数为 15 种。 33、设 1 和 2 是集合A上的等价关系，下列各式哪些是A上的等价关系？为什 么？ (1) 1 ()AA 答：不是等价关系，因为不具有自反性 (2) 12 答：不是等价关系，因为不具有自反性 (3) 2 1 答：是等价关系，证明如下： 1 是自反的， 2 1 显然也是自反的。若 2 1 ( , )a b， 则有复合关系的定义，存在cA，使得 1 ( , )a c， 1 ( , )c b，由 1 的对称性有 1 ( , )c a， 1 ( , )b c，由复合关系的定义有 2 1 ( , )b a，因此 2 1 是对称的。若 2 1 ( , ),( , )a bb c，由复合关系的定义， 由对称性， ， 所以 2 1 ( , )c a， 由 2 1 的对称性， 2 1 ( , )a c， 因此 2 1 具有传递性。 因此 2 1 是A上 的等价关系。 (4) 12 ()r 答： 不一定是A上的等价关系。 例如1,2,3A =， 2 (1,1),(2,2),(3,3),(2,3),(3,2)=， 1 为A上的普遍关系，则 12 ()(1,1),(2,2),(3,3),(1,2),(2,1),(1,3),(3,1)r=不具 有传递性，因为 12 (2,1),(1,3)()r，但是 12 (2,3)()r。 34、对于下列集合中的整除关系，画出次序图： (1) 1,2,3,4,6,8,12,24 答： 11 11 ,( , ),( , ) ,( , ),( , ) dA a dd b eA b ee c 111 111 ( , ),( , )( , ) ( , ),( , )( , ) d ab db a e bc ec b 25 (2) 1,2,3,4,5,6,7,8,9,10,11,12 答： 35、对于下列集合，画出偏序关系整除的次序图，并指出哪些是全序 (1)2,6,24 答： 是全序 (2)3,5,15 答： 非全序 (3)1,2,3,6,12 答： 非全序 (4)2,4,8,16 答： 26 是全序 (5) 3,9,27,54 答： 是全序 36、如果是集合A中的偏序关系，且BA，试证明：()BB是B上的偏 序关系。 证明：对任意的aB，必有( , )a aBB，又因为aA及的自反性，所以 ( , )a a，因此( , )()a aBB，故()BB是自反的。 对任意的, a bB，若( , )()a bBB，且( , )()b aBB，则有( , )a b， 且( , )b a，由的反对称性，有ab=，因此()BB是反对称的。 对任意的, ,a b cB，若( , )()a bBB，( , )()b cBB，则( , )a b，且 ( , )b c，由的可传递性必有( , )a c，由BB的定义，( , )a cBB，于是 ( , )()a cBB，因此()BB是可传递的，由上得证()BB是B上的 偏序关系。 37、 给出一个集合A的例子，使得包含关系是幂集2A上的一个全序。 答：1,2,3A =，2 ,1,2,3,1,2,2,3,1,3,1,2,3 A = 2A上的关系 ,1,1,2,1,2,3=。 38、给出一个关系，使它既是某一集合上的偏序关系又是等价关系 答：1,2,3A =，(1,1),(2,2),(3,3)=， 显然具有自反性， 对称性， 可传递性， 还具有反对称性，因此既是A上的；偏序关系，也是等价关系。 39、图 2-12 表示1,2,3,4上的四个偏序关系图。画出每一个的次序图，并指出 其中哪些是全序，哪些是良序 答： 27 (a) (1,1),(2,2),(3,3),(4,4),(1,2),(3,2),(3,1),(3,4),(1,4)= 不是全序，也不是良序 (b) 不是全序也不是良序 (c) (1,1),(2,2),(3,3),(4,4),(3,1),(1,2),(3,2),(1,4),(3,4),(4,2)= 是全序也是良序 (1,1),(2,2),(3,3),(4,4),(1,3),(2,3),(1,4),(2,4)= 28 (d) (1,1),(2,2),(3,3),(4,4),(3,1),(4,3),(4,1),(4,2)=非全序，也不是良序。 40、 一个集合上的自反和对称关的关系称为相容关系 (1) 设A是人的集合，是集合A上的关系，定义为当且仅当a是b的朋友时， 有a b，试证明是A上的相容关系。 证明：对aA ，因为任何的人都是自己的朋友，也就是有a a，因此具有 自反性，若a b，也就是a是b的朋友，那么一定有b是a的朋友，则有b a， 因此是对称的，因此是A上的相容关系。 (2) 是正整数集N上的关系，当且仅当两个正整数 1 n 和 2 n中有相同的数字时， 12 nn ，试证明是一个相容关系； 证明：显然，对nN ，有n n，因此具有自反性；若 12 nn，则表示 1 n和 2 n 中有相同的数字， 因此 2 n和 1 n 也有相同的数字， 因此 21 nn。 所以具有对称性， 所以是N上的一个相容关系。 (3) 再举出一个相容关系的例子 答：等价关系都是相容关系，反之则不成立。 (4) 设 1 和 2 是A上的两个相容关系， 12 是相容关系吗？ 12 是相容关 系吗？ 答： 12 和 12 都是相容关系，前题 30 中证明了若 1 和 2 是A上的等价 关系，则 12 也是等价关系，而 12 具有自反性和对称性。 29 第第 3 章章 函数函数 1. 以下关系中哪一个构成函数？ (1) 121212 ( ,)|,10n nn nN nn+是格，试证明对于所有的, ,a b cL，则有： ()()()ababcbac 证明：根据格的分配律，我们有 ()()()abcabac 因为ab，所以abb=，所以()()abcbac。 7、 设, ,L是一个格，如果对于所有的, ,a b cL，有 ()()()ababcbac= 则称, ,L是模式格，下图所给出的格是模式格吗？证明你的结论。 解： 不是模式格， 因为对于, ,b d c这三个元素，bd， 但是()bdcbab=， 而()dbcded=，并不满足模式格的要求，因此不是模式格。 8、证明具有两个或更多个元素的格中，不会有元素是它自身的补。 证明：因在格中求补元，此格必为有界格，设,L为有界格，若#( )2L =，则 0,1L =。因为000,000,1 11,1 11,010,011= = = = =，因此 0 和 38 1 互为补元， 即具有两个元素的格中不存在以自身为补元的元素。 若#( )2L ， 设存在lL，0l 且1l ，若l以自身为补元，则由补元的定义： 01lllll = = =，可得01l =，与假设矛盾。因此不存在以自身为补元 的元素。 9、设; ,L是一个格，#( )1L ，试证明如果; ,L有元素 1 和元素 0， 则这两个元素必定是不相同的。 证明：反证，假设这两个元素是相同的，并记01l =，则根据最大元素和最小 元素的定义，我们有对 1 lL ， 1 01lll= = ，则 1 ll=，因此#( )1L =，这 与条件矛盾。 10、举例说明并非每一有补格都是分配格；并非每个分配格都是有补格。 解：由下图(a)表示的格由于元素z无补元，因此不是有补格；但是对任意三个元 素都满足分配等式，因此是分配格。 (a) 下图(b)表示的格中，0 和 1 互为补元， , x y两两互补，因此是有补格。又 因为()1xyzxx= =，()()000xyxz=，即 ()()()xyzxyxz 所以不是分配格。 (b) 11、 设,L是一个格，, a bL，且ab也是一个格。 证明： 因为,L是格， 所以对任意 12 ,l lL， 有 1212 glb( , )lll l=，1 212 lub( , )lll l=。 由B的定义知BL，aB，所以B。对任意, x yB， 由于,L 是格，所以xy和xy在L中存在且唯一。 下证,xyB xyB。 由B的定义知axb，ayb。所以ax且ay，根据格的保号性及 等幂性有aaaxy=， 所以axy。 类似地，,xb yb得xyb， 所以 axyb，即xyB。类似地可证明axyb，即xyB。 12、设;L是一个格，试证明对于任意的元素, ,a b cL，有下列命题成立： (1) 若abab=，则ab= (2) 若abcabc=，则abc= (3) ()()()()aabacabac= 证明： (1) 因为aababa=， 所以aab=， 同理有bab=， 因此ab=。 (2) 因为 aabcabca babcabcb cabcabcc ，所以abcabcabc=。 (3) 由格的分配律 ()()()()()()aabacaabaacabac= 又因为()()aabac为()()abac和a的上确界，因此 ()()()()aabacabac 因此得证。 13、设a和b是格;L中的两个元素，试证明当且仅当, a b不可比时， ,aba abb成为一个格？ 解：记( ) i P A=，其中 i 为A的一种分划，定义( )P A上的偏序关系为，若分 40 划 i 是 j 的一个细分，则 ij 。显然有，对任意( ) i P A， ii 因此具 有自反性； 若, ijji ， 则 ij =因此具有反对称性； 若, ijjk ， 则 ik (根据细分的定义很容易得出)，所以具有可传递性，因此是偏序关 系。 , , Aa b c=中 3 个元素，共 5 种： 12 34 5 , , , , , , , , , , , , abca bc ab ca cb a b c = = = 则对定义二元运算 iji =(若 i j )， 1ij =(若 i 和 j 不可比) ijj =(若 i j )， 5ij =(若 i 和 j 不可比) 可以画出该偏序关系的次序图如下： 显然定义的偏序关系是格。 15、试证明在格中对任意元素, ,a b c，有 ()()()()()()abbccaabbcca 证明:因为aba，bcb，caa，所以()()abbcab， ()()()()abbccaabaab=，所以可得： ()()()abbccaab，同理有： ()()()abbccabc，和()()()abbccaac 所以()()()()()()abbccaabbcac成立。 16、试证明在格中对于任意元素, ,a b cL，有： ()()()()()()abbccaabbcca= 时，格,L是分配格。 证明：必要性：设,L是分配格，则对于任意, ,a b cL有： ()()()()()()() ()() ()()()() ()()() abbccaabbccabbca abcbca acbcbaca abbcca = = = = 充分性：对于任意, ,a b cL，令()()aabac = ，bbc = ，ca = ，则 41 ,a b cL 满足等式： ()()()()()()abbccaabbcca= (1) 于是式(1)的左边 左边 ()()()() ()()() ()()() () abacbcbcaa abbccaa abbccaa bca = = = = 因为aab，aac，故()()aabac 所以()()()()aabacabac=。 将,a b c 带入(1)的右边得 右边 ()()()()()() ()()()()()() ()()() ()()() ()() abacbcbcaaabac abacbcabacbca abacacb abacacb abac = = = = = 所以有()()()abcabac=。因此是分配格。 42 第第 8 8 章章 图论图论 1、图 1 所示之图是否同构于图 2 图 1 图 2 答 ： 根 据 点 和 边 的 关 联 关 系 ， 构 造 12 :, ( ),1,2,3,4 ii h VV h vu i=， 5665 (), ()h vu h vu=，显然h是双射且满足同构的定义。 2、图 3 中所给出的两个 8 结点图是否同构？证明你的回答 图 3(a) 图 3(b) 答：上述两个图不同构。 证明： 因为图 3(b)中 4 个度数为 3 的结点中每一个均与另外两个度数为 3 的结点 相邻，而图 3(a)中的每个度数为 3 的结点只与另外一个度数为 3 的结点相邻，所 以不同构。 3、证明在任何图中奇次度结点的个数是偶数。 证明：反证，假设图 G 中存在奇数个奇次度结点，则图中不论偶次度结点的个 数是奇数还是偶数，该图的结点总度数为偶数，但是任何图的所有结点度的总 和又为边数的两倍，因此必为偶数，矛盾！ 4、设 G 是具有 4 个结点的完全图，试问： (1)G 有多少个子图？ (2)G 有多少个生成子图？ 43 (3)如果没有任何两个子图是同构的，则 G 的子图个数是多少？请将这些子图构 造出来？ 答：(1)含有一个结点的子图有 1 4 C个，含有两个结点的子图有 2 4 2C 个，含有三 个结点的子图有 3 4 8C 个，含有 4 个结点的子图有 4 4 64C 个，所以共有 112 个 子图。 (2) G 的生成子图包含 G 的所有结点，因为 G 有 6 条边，构成子图时，每条边有 被选和不被选择两种情况，因此 G 生成的子图为 6 2=64 种。 (3)G 的所有不同构的子图如下：共 18 个。 5、在图 4 中找出其所有的真路和环，该图是否包含有割边？ 图 4 解：真路： 1253 6 v v v cv v等。环： 1 2 5 4 1 v v v v v等。其中 34 ,v v是割边，因为该条边不 在 G 的任何环中出现。 6、图 G 的邻接矩阵为： 44 001100 000011 100000 100000 010001 010010 A = 给出，G 是否是连通的？ 解：直接由邻接矩阵给出图 G 的一个图解，如下图所示，显然 G 是不连通的。 7、求下图中图(a)和图(b)的全部断集： (a) (b) 解： 对于图(a) 1 , Sa f d=， 2 , , Sa e b=， 3 , , Sb c f=， 4 , Sc f d=， 5 Sg=， 6 , , Sa e f c=， 7 , , , Sb d e f=都是边割集。 对于图(b) 1 , Sa b=， 2 , Sf g=， 3 , , Sc d e=， 4 , , , Sa c d f=都是边割集。 8、证明图G的任一生成树和任一边割集至少有一条公共边。 证明：设图G中若有一个边割S与G的一棵生成树T没有公共边，那么删去S后 所得子图GS必包含T，这意味着GS仍连通，与S是边割集矛盾，所以一定 45 有S与T至少有一条公共边， 9、试作出一个连通图G，使之满足等式( )( )( )K GGG=。 解： 上图中由定义可得( )( )( )2K GGG= 10、设图G中各结点的度都是 3，且结点数n与边数m间有如下关系 23nm= 问(1) G中结点数与边数各为多少？ (2) 在同构的意义下G是唯一的吗？ 解： (1) 由题知该图的总度数为3n， 由握手定理知边数与度数的关系为23mn=， 又由23nm=，可以解出边数9m =，结点数6n =。 (2) 在同构的意义下图G不唯一，见第一节的例 8 中图(b)和图(c)。 11、若图G的补图同构于G，则称G为自补图。试证明下图所示的图是自补图。 你能否找到其他 5 结点的自补图。 证明：上图的补图为 图G与其补图的结点集合之间可以建立一一对应关系，因此两个图是同构的。 46 12、已知关于人员, , , , ,a b c d e f g的下述事实： a说英语；b说英语和西班牙语；c说英语、意大利语和俄语；d说日语和西班 牙语；e说德语和意大利语；f说法语、日语和俄语；g说法语和德语，试问上 述 7 人中是否任意两个人都能交谈？如有必要， 可由其余 5 人中所组成的译员链 帮忙？ 解：设 7 个人为 7 个结点，将两个懂同一种语言的人之间连成一条边，即表示他 们能直接交谈。这样就得到一个简单图 G，问题就转化为 G 是否连通，G 如下 图所示，因为 G 中任意两个结点是连接的，所以 G 是连通图。因此