资源描述
第1章 集合1、列举下列集合的元素(1) 小于20的素数的集合(2) 小于5的非负整数的集合(3) 答：(1) (2) (3) 2、用描述法表示下列集合(1) 答：(2) 答：(3) 答：3、下面哪些式子是错误的？(1) 答：正确(2) 答：错误(3) 答：正确(4) 答：正确4、已给和，指出下面哪些论断是正确的？哪些是错误的？(1) 错误(2) 正确(3) 正确(4) 正确(5) 错误(6) 正确(7) 错误(8) 正确(9) 正确(10) 错误(11) 错误(12) 正确5、 列举出集合的例子，使其满足，且答：，显然，显然，但是。6、 给出下列集合的幂集(1) 答：幂集(2) 答：幂集7、设，给出和的幂集答： 8、 设由和所表示的的子集各是什么？应如何表示子集和答：，9、 设，确定集合：(1) (2) (3) (4)(5) (6) (7) (8) (9) (10)答：(1) ，(2) ，(3) ，(4) ，(5) (6) ，(7) ，(8) ，(9) ，(10) 10、 给定自然数集的下列子集：，求下列集合：(1) 答：， ， (2) (3) 解：，(4) 解：，11、 给定自然数集的下列子集，将下列集合表示为由产生的集合：(1) (2) (3) (4)(5) (6) 答：，=(4) (5) (6) 12、 判断以下哪些论断是正确的，哪些论断是错误的，并说明理由。(1) 若，则答：正确，根据集合并的定义(2) 若，则答：显然不正确，因为根据集合交运算的定义，必须同时属于和(3) 若，则答：正确(4) 若，则答：错误(5) 若，则答：正确(6) 若，则答：错误(7) 若，则答：正确13、 设是任意的集合，下述论断哪些是正确的？哪些是错误的？说明理由(1) 若，则答：不正确，反例，设，则不论是什么集合，都有，但显然不一定相等。(2) 当且仅当，有；答：正确，证明如下：若，则对，有，则有，因此有。反之，若，则显然成立。(3) 当且仅当，有答：正确，证明如下：若，则对，因此，则，则有。若，则，有，因此由，可以得出，因此，又，有。(4) 当且仅当，有答：不正确，因为，因此不一定需要满足，而若也可以满足。例如：，成立，而不成立。(5) 当且仅当，有答：不正确，因为若，有成立，但是反之不成立，反例如下:，而，但是不成立。14、 设是集合，下述哪些论断是正确的？哪些是错误的？说明理由。(1) 若，则答：正确，证明：对，则或，因为，因此或，因此，即成立。(2) 若，则答：正确(3)若，则答：正确(4) 若，则答：不正确。例如若，但是，则。15、 设是两个集合，问：(1)如果，那么和有什么关系？答：因为，而，即对有，因此。(2) 如果，那么和有什么关系？答：充要条件是。证明：因为的，从而有，即，同理可证明，因此。16、 设是任意集合，下述论断哪些是正确的？哪些是错误的？说明理由。(1) 答：不正确。例如，则，显然不成立。(2) 答：成立。证明：对，则且，则，则，因此。反之，若，则，则且，因此，且，因此，即。(3) 答：显然不成立，因为左边集合肯定含有，而右边不含有。17、 在一个班级的50个学生中，有26人在离散数学的考试中取得了优秀的成绩；21人在程序设计的考试中取得了优秀的成绩。假如有17人在两次考试中都没有取得优秀成绩，问有多少人在两次考试中都取得了优秀成绩?答：分别用表示在离散和程序设计的考试中取得优秀成绩的学生集合，表示全体学生集合：则，则两次考试中都取得了优秀成绩的学生人数为26+21-33=14人。18、 设是任意集合，运用成员表证明：(1) 证明：左边右边00011000000011100000010111011101111101111000010000101011101111000100001110111011 (3) 证明：0000000000100010010000100110001010011101101100101100101011100010由上得证左右两边相等。19、由和的成员表如何判断？应用成员表证明或否定 答：先分别给出集合和的成员表如下：000001010001010010010110000011110000100101111101110011110110000111110000观察上述表格，我们发现所标记的列中，仅在第五列为1，这意味着当元素且时，而在其他情形下，元素。而集合所标记的列中，第五和第六行均为1，这意味着且时，当，且时，也有。所以当元素时也有，反之不然，因此成立。20、为的子集，至多能产生多少不同的子集？答：构造由所产生的集合的成员表，显然该成员表由个行所组成。在该成员表中不同的列可由为的二进制数000011111分别表示，而不同的列所标记的集合 不相同的，因此由至多可以产生个不同的集合。21、证明分配律、等幂律和吸收律1分配律 证明：对，则有且，即有，且或，也即有或，即，因此左边右边。 对，则或，即且，或且，即有或，因此，因此右边左边。2 吸收律证明：显然成立，对，则显然有，因此有，因此有成立。22、设是任意集合，运用集合运算定律证明：(1) 证明：(2) 证明：(3) 证明： 由上题的证明可知左边=右边，得证。23、用得摩根定律证明补集是。证明：24、设为某些实数的集合，定义为试证明：证明：设，则比存在整数，使得，因此有，于是,因此。另一方面，设，则有，若，则有，因此。若，则令，令，其中表示的整数部分，则有，因此，即，于是，因此得证。25、设是集合的一个分划，试证明中所有非空集合构成的一个分划。证明：因为是集合的一个分划，因此由分划的定义，可得，且，而，且，因此中所有非空集合构成的一个分划。26、个元素的集合，有多少中不同的方法可以分划成两块？答：当奇数时有种不同的方法，当为偶数时有种不同的方法。 第2章 关系1、若,，确定集合：(1) (2) (3) 解： 2、在通常的具有X轴和Y轴的笛卡尔坐标系中，若有 试给出笛卡尔积的几何解释解：表示横坐标的范围在，纵坐标的范围在的二维点集所构成的集合。3、设A，B，C和D是任意的集合，证明(1) (2) (3) 证明：(3) 首先，因为，所以 类似地，所以有： 反之，若，则， 则，且，即， 所以， 所以 所以4、对下列每种情形，列出由A到B的关系的元素，确定的定义域和值域，构造的关系矩阵：(1) 解：，关系矩阵(2) 解：关系矩阵=5、设，对下列每一种情形，构造A上的关系图，并确定的定义域和值域(1) 解：图略定义域，(2) 解： 定义域，(3) 解：定义域，(4) 解：定义域，(5) 解：定义域，(6) 解：定义域，(7) 解：定义域，(8) 解：定义域，6、设和，试求出， ， ， 和 ， 并证明：= 解：，证明：= 设，则必存在，使得，所以或者，因此，或者，即，所以； 反之，设，则或者，所以存在，使得，或者存在，使得，由并集的定义知，或者，总之有，故。证明： 设，则必存在，使得，因此且，由交集的定义，故。7、和是分别具有基数和的有限集，试问有多少个到的不同关系？答：的所有子集都是到的一个关系，所以共有个不同的关系。8、找出集合上普遍关系和恒等关系的关系矩阵和关系图的特征。答：上的普遍关系的关系矩阵是全1矩阵，而恒等关系的关系矩阵是单位矩阵。9、下列是集合上的关系：，试确定如下的复合关系：（1） （2） （3） （4）解：（1），（2）（3）（4） 10、 设是集合上的关系，试证明：如果，则有：（1） （2） （3）证明：（1）对，由复合关系的定义，使得，因为，所以，所以，所以（2）对，由复合关系的定义，使得，因为，所以，所以，所以。（3）对，有，因为，所以，所以，也即。11、给定，求一个基数最小的关系，使满足的条件。一般地说，若给定和，能被唯一的确定吗？基数最小的能被唯一确定吗？答：。一般地说，若给定和，不能被唯一的确定。基数最小的也不能被唯一确定。12、给定集合，设是由得关系，和是由得关系，试证明：（1）=证明：根据并集和复合关系的定义，和都是上的关系，下只需要证明它们由完全相同的序偶组成。设，必存在，使得，所以有或者，所以有或者，也即，也即；反之，若，也即或者，若，则存在，使得，则，则，若同理可得，因此有。则=。（2）证明：设，则存在，使得，则，且，所以，且，即，所以。13、给定是什么？答：，则14、对第9题中的关系，构造关系矩阵（1） （2） 解： (3) 解： 15、设是有个元素的有限集，是上的关系，试证明必存在两个正整数，使得。证明：因为是上的关系，所以对于任意正整数，也是上的关系，另一方面，因为，所以，也即上只有个不同的关系，因此在关系中必有两个是相同的，也即存在两个正整数，使得，其中。16、设是由到的关系，是由到的关系，试证明。证明：由题设知道和都是由到的关系，因此只要证明它们由完全相同的序偶组成。设，则，因此必存在元素，使得，所以，所以。反之，设，则必存在元素，使得，所以，所以，所以，所以。17、（1）设和是由到的关系，问成立吗？答：成立（2）设是集合上的关系，如果是自反的，则一定是自反的吗？答：是的。证明：若是自反的，则对所有的，有，则一定有，则也是自反的。（3）若是对称的，则也是对称的吗？ 答：是的。（4）若是可传递的，则也是可传递的吗？答：是的证明：若是可传递的，由定义可知，若，则一定有，由逆关系的定义，也即，若，一定有，则也是可传递的。18、图2-9给出了集合上的关系的关系图，试画出关系和的图，并利用关系图求出关系的传递闭包。解：图2-9关系因为，所以，传递闭包。 19、试证明：若是基数为的集合上的一个关系，则的传递闭包为证明：由定义，要证明，因为，所以只要证明即可。设，则必存在正整数，使得，若，则，若，则在中必存在个元素，使得： 因为，所以在这个元素中必有两个元素（，记为，记为），因此下述关系成立，这表明，。若，用类似的方法又可找到，使，最后必可找到一正整，使且，因此 ，故 。20、下列关系中哪一个是自反的、对称的、反对称的或者可传递的？（1）当且仅当时，有；答：是自反的，对称的，非可传递的，例如，但不成立。（2）当且仅当时，有；答：非自反的，因为不成立，但。对称的，非可传递的，因为，但是不成立。（3）当且仅当时，有。答：自反的，非对称的，非可传递的，因为，但是不成立。21、设和是集合上的任意两个关系，判断下列命题是否正确，并说明理由：（1）若和是自反的，则也是自反的；答：正确。因为和是自反的，因此对任意，有，因此，所以也是自反的。（2）若和是非自反的，则也是非自反的；答：错误；例如，和都是非自反的，但是是自反的。（3）若和是对称的，则也是对称的；答：错误，设，显然和是对称的，但是是非对称的。（4）若和是反对称的，则也是反对称的；答：错误，设，显然和是反对称的，但是不是对称的。（5）若和是可传递的，则也是可传递的；答：错误，设，显然是可传递的，但是却是不可传递的。22、证明若是对称的，则对任何整数，也是对称的。证明：数学归纳法，当时，若，则根据复合关系的定义，存在元素，使得，因为是对称的，所以，所以，因此是对称的，假设当时成立，则当时，若，则存在元素，使得，因为和是对称的，因此，所以，因此： 时成立，即得证。23、已知和定义在上的关系，试证明不是可传递的。求出一个关系，使得是可传递的，你能求出另一个关系也是可传递的嘛？答：证明：显然不是可传递的，因为，但是。，能找出另一个关系。24、图2-10表示在上的12个关系的关系图。试对每一个这样的图，确定其表示的关系是自反的还是非自反的；是对称，非对称还是反对称；是可传递的还是不可传递的？答：自反的、非对称的、非反对称的，非可传递的 自反的、对称的，非反对称的、可传递的非自反的、非对称的、反对称的、可传递的自反的、非对称的、反对称的、可传递的25、图2-11给出了上的两个关系的关系图，这些关系是等价的吗？答： (a) (b)答：图(a)表示的关系具有自反性，对称性，但是不具有传递性，因为有，但是，因此不是等价关系。图(b)表示的关系，具有自反性，对称性，传递性，因此是等价关系。26、在上的关系定义为当且仅当可以用形式表示时，有，这里是任意整数：(1)证明是等价关系证明：对，因此，所以关系具有自反性。 对，若，即存在，使得，则有，因此有。所以关系具有对称性。 对，若，且，即存在，使得，则，因此有，所以关系具有传递性。 综上可得关系是等价关系。(2) 找出的所有等价类答： 27、有人说，集合上的关系，如果是对称的且可传递的，则它也是自反的，其理由是，从，由对称性得，再由可传递性便得。答：这种说法是错误的。例如，显然是对称的，且是可传递的，但是它不是自反的。28、设有集合和上的关系，对于所有的，若由和可推得，则称关系是循环的，试证明当且仅当是等价关系时，是自反且循环的。证明：先证充分性若是等价关系，则是自反的，对称的，可传递的。对于所有的，若且，则，由对称性则有，因此关系是循环的。再证必要性若对于所有的，若有，又由自反性，有，则由是循环的，可得成立，即具有对称性。若对于所有的，若由和，由是循环的有，由对称性可得，因此具有可传递性。又由是自反的，则是等价的。29、设和是上的等价关系，试证明：当且仅当中的每一等价类都包含于的某一等价类中时，有。证明：先证充分性设中的每一个等价类都包含于的某一个等价类中，对任一，有，因此。又由假设必有某元素存在，使得，因此有，所以，故有。再证必要性：设，并设是中任一等价类，对任一，有，即，由假设，即，故有。30、已知和是集合上分别有秩和的等价关系，试证明也是上的等价关系，它的秩最多为，再证明不一定是上的等价关系。证明：由交集的定义 对于，因为都是自反的，所以，且，因为，所以是自反的。对于，若，则，由和的对称性知，且，因而有，故是对称的。对于，若，则有，由的传递性知，因而，故是可传递的。所以也是上的等价关系。对于，由并集的定义知对于，因为是自反的，所以，因而，所以是自反的。对于，若，则或者，由于和都是对称的，因此有或者，因而有，故也是对称的。对于任意的，若，则或者；或者，因为和不一定能同时属于，也不一定能同时属于，所以无法推出或者，因而也就无法推出，这说明的可传递性不一定能成立，因此推不出是上的等价关系。反例：设，上的关系，显然和均是等价关系。，这里是自反的，对称的，但是不可传递的。31、设是集合上的一个关系，。试证明：若是一个等价关系，则也是一个等价关系。证明：因为是自反的，因此对，有，由，因此有，故是自反的。对于任意的，若，则必有元素，使得且，由的对称性又有且，因而有，故是对称的。对任意的，若，则必有元素，使得：由的可传递性，又有，于是又有，故是可传递的。由上得证是一个等价关系。32、设是由4个元素组成的集合，试问在上可以定义多少个不同的等价关系？答：根据等价关系与分划一一对应，将分划为一块：有一种方法，将分划为两块：2+2方式有1/2种，1+3方式有种将分划为三块：只能是1+1+2方式，有种将分划为四块：有一种方法因此集合上不同等价关系的个数为15种。33、设和是集合上的等价关系，下列各式哪些是上的等价关系？为什么？(1)答：不是等价关系，因为不具有自反性(2) 答：不是等价关系，因为不具有自反性(3) 答：是等价关系，证明如下：是自反的，显然也是自反的。若，则有复合关系的定义，存在，使得，由的对称性有，由复合关系的定义有，因此是对称的。若，由复合关系的定义，由对称性， ，所以，由的对称性，因此具有传递性。因此是上的等价关系。(4)答：不一定是上的等价关系。例如，为上的普遍关系，则不具有传递性，因为，但是。34、对于下列集合中的整除关系，画出次序图：(1) 答： (2) 答：35、对于下列集合，画出偏序关系整除的次序图，并指出哪些是全序(1)答：是全序(2)答：非全序(3)答：非全序(4)答：是全序(5) 答：是全序36、如果是集合中的偏序关系，且，试证明：是上的偏序关系。证明：对任意的，必有，又因为及的自反性，所以，因此，故是自反的。对任意的，若，且，则有，且，由的反对称性，有，因此是反对称的。对任意的，若，则，且，由的可传递性必有，由的定义，于是，因此是可传递的，由上得证是上的偏序关系。37、 给出一个集合的例子，使得包含关系是幂集上的一个全序。答：，上的关系。38、给出一个关系，使它既是某一集合上的偏序关系又是等价关系答：，显然具有自反性，对称性，可传递性，还具有反对称性，因此既是上的；偏序关系，也是等价关系。39、图2-12表示上的四个偏序关系图。画出每一个的次序图，并指出其中哪些是全序，哪些是良序答： (a)不是全序，也不是良序 (b)不是全序也不是良序 (c) 是全序也是良序 (d)非全序，也不是良序。40、 一个集合上的自反和对称关的关系称为相容关系(1) 设是人的集合，是集合上的关系，定义为当且仅当是的朋友时，有，试证明是上的相容关系。证明：对，因为任何的人都是自己的朋友，也就是有，因此具有自反性，若，也就是是的朋友，那么一定有是的朋友，则有，因此是对称的，因此是上的相容关系。(2) 是正整数集上的关系，当且仅当两个正整数和中有相同的数字时， ，试证明是一个相容关系；证明：显然，对，有，因此具有自反性；若，则表示和中有相同的数字，因此和也有相同的数字，因此。所以具有对称性，所以是上的一个相容关系。(3) 再举出一个相容关系的例子答：等价关系都是相容关系，反之则不成立。(4) 设和是上的两个相容关系，是相容关系吗？是相容关系吗？答：和都是相容关系，前题30中证明了若和是上的等价关系，则也是等价关系，而具有自反性和对称性。 第3章 函数1. 以下关系中哪一个构成函数？(1) 答：不构成函数。象的唯一性不能满足，因为都属于这个集合。而等这样的数在中无像，所以象的存在性也不能满足。(2) 答：是函数，象的唯一性和存在性都能满足。2. 设，给定由到的关系： 是函数吗？若是的话，的值域吗？为什么？答：是函数。的值域。因为对，则，则对，因此象的像源为。3. 下列集合能够定义函数吗？如果能，试指出它们的定义域和值域？(1) 答：能定义函数。，(2) 答：能定义函数。，(3) 答：不能定义函数。因为有一对多的情况。(4) 答：能定义函数。，4. 设函数，等式成立吗？为什么？答：不成立。因为成立，但是不成立。下面证明。设，则且，所以必存在使。由于，所以，于是，因此，故。不成立，反例如下：设，则，函数的定义为：。显然，。由上可知不成立。5 设有函数，试证明等式，等式成立吗？为什么？证明：设，则或者。若，则存在使得，因此有，所以。若，类似地，有，故。反之，若，则存在，使得。由并集的定义或者，因此或者，于是，故。由上得证。不成立，因为，反之不成立。证明：设，则存在使得。因为且，所以且，因此，故。反例如下：设，其中，函数定义为，于是：，这里元素，但是。6. 设有函数和，使得是一个内射，且是满射。证明是一个内射。举出一个例子说明，若不是满射，则不一定是内射。证明：任取，并设。因为是满射，所以必有，使得，根据函数象的唯一性的条件，由可得。又因为是由到的函数，所以有，使得，。于是根据复合函数的定义，得： ，因为是内射，所以由，可知。此即，故是内射。例子：图3-1 图3-1中的例子可说明当不是满射时，不一定是内射。7. 在下列函数中，确定哪些是内射，哪些是满射，哪些是双射。(1) 小于的；答：，因此不是内射，是满射，因此不是双射。(2) ;答：是内射，是满射，因此是双射(3) 答：因为，所以不是内射，。显然对于任意的，。因此不是满射，因此不是双射。(4) 答：因为，所以不是内射。对于任意的，有。即对于任意的，有像源，所以是满射，但是不是双射。(5) 答：因为，所以，因此，因此不是满射。是内射(函数的单调性)。因此不是双射。(6) 等于或大于的最小整数；答：因为，因此不是内射是满射。因此不是双射。(是非负整数集合)(7)，答：对任意，但是，因此不是内射。又，但是找不到，使得，。因此不是满射，因此也不是双射。8. 设都是有限集，问存在着多少个不同的内射？存在多少个不同的双射？答：若要使得函数成为内射，必须满足，即，否则由到不可能存在内射。当时，由到可定义个不同的内射。此即为从的个元素中取出个元素的排列数。要使函数成为双射，必须满足，即。否则，由不可能存在双射。当时，由到可定义个不同的双射。9. 下列函数中，确定哪些是内射，哪些是满射，哪些是双射。(1) ，答：因为，因此不是内射。是满射，因此不是双射。(2) 答：表示被7除后的非负余数，于是按照函数的定义，得：显然又是内射，又是满射，因此是双射。(3) 答：，。因此不是内射不是满射，因此也不是双射。10. 设，试证明任何从到的函数，如果它是内射，则它必是满射，反之亦真。答：反证法。已知是内射，假设不是满射，则在中至少有一个元素没有像源，即集合中的元素至多只有个像。但是，因此中至少有两个元素对应同一个像，这与是内射相矛盾。反之，已知是满射，假设不是内射，则中至少有两个元素对应同一个像，即在中至多有个像，这与是满射矛盾，所以是内射。11. 设有函数，定义函数，使得： 试证明如果是满射，则是内射；其逆成立吗？答：设，因为是满射，存在，使得，因此，因此，因此是内射。其逆不成立。因为当是内射时，可能有一个元素，使，这意味着元素在中没有像源，因此不是满射。举例如下：，函数和的定义如下，此时是内射，但是不是满射。图3-212. 设函数，。这里，。试证明和是满射，但是都不是内射。答：，但是，因此不是内射。但是对，有，因此是满射。同理，但是，因此不是内射，但是对，因此是满射。13. 设有函数和，这里和。求出和。并说明这些函数是否是内射，满射或双射。答： 因为，因此不是内射，又因为，因此也不是满射。因此不是双射。也不是内射，也不是满射，也不是双射。但是是内射是满射，因此也是双射。不是内射，不是满射，因此也不是双射。14. 设有函数，给定为，。试求出，。答： ，15设，定义一个函数，使得，而且是双射，求，以及。能否找到一个双射，使得，但是？答：定义函数，使得，显然是双射且。函数；函数，类似地，。可定义函数，使得，。显然，但。16. 设，试求。答： 第7章 格和布尔代数1、下列各集合对于整除关系都构成偏序集。在每个集合中对存在有最大下界和最小上界的元素对，找出它们的最大下界和最小上界；指出各集合中是否有最小元素和最大元素。(1) (2)(3) 解：(1)偏序集的次序图如下：4和6的最大下界为1，最小上界为12； 2和3的最大下界为1，最小上界为6； 3和6的最大下界为3，最小上界为6； 该集合的最大元素为12，最小元素为1。(2)偏序集的次序图如下：该集合最小元素为1，最大元素为24。任何两个元素的最小上界为它们的最小公倍数，最大下界为它们的最大公约数。(3)偏序集的次序图如下：该集合没有最大元，有最小元素为1。2、 试证明在格中若，则有 证明：(1)因为，所以，又因为，所以，所以有成立。 (2)因为，所以，；又因为，所以，所以，所以有：成立。3、试证明在格中对于任意元素有证明：因为，所以由格的保号性 因为，所以由格的保号性 因此，是和的下界，所以： 4、在第一题中，哪一个偏序集构成格？答：第1和第2个偏序集构成了格，因为该集合中任何两个元素都存在最大下界和最小上界。但是第3个集合中的元素则不满足这个条件。5、下图给出了三个偏序集的次序图，其中哪些构成格？不是格，因为最下层两个元素没有下确界。 (a) (b) 是格，因为任何两个元素都有下确界和上确界。不是格，因为最上层两个元素没有上确界。6、设是格，试证明对于所有的，则有：证明：根据格的分配律，我们有 因为，所以，所以。7、 设是一个格，如果对于所有的，有 则称是模式格，下图所给出的格是模式格吗？证明你的结论。解：不是模式格，因为对于这三个元素，但是，而，并不满足模式格的要求，因此不是模式格。8、证明具有两个或更多个元素的格中，不会有元素是它自身的补。证明：因在格中求补元，此格必为有界格，设为有界格，若，则。因为，因此0和1互为补元，即具有两个元素的格中不存在以自身为补元的元素。若，设存在，且，若以自身为补元，则由补元的定义：，可得，与假设矛盾。因此不存在以自身为补元的元素。9、设是一个格，试证明如果有元素1和元素0，则这两个元素必定是不相同的。证明：反证，假设这两个元素是相同的，并记，则根据最大元素和最小元素的定义，我们有对，则，因此，这与条件矛盾。10、举例说明并非每一有补格都是分配格；并非每个分配格都是有补格。解：由下图(a)表示的格由于元素无补元，因此不是有补格；但是对任意三个元素都满足分配等式，因此是分配格。 (a)下图(b)表示的格中，0和1互为补元， 两两互补，因此是有补格。又因为，即所以不是分配格。 (b)11、 设是一个格，且(即，但是)，令集合 证明也是一个格。证明：因为是格，所以对任意，有，。由的定义知，所以。对任意， 由于是格，所以和在中存在且唯一。 下证。 由的定义知，。所以且，根据格的保号性及等幂性有，所以。类似地，得，所以 ，即。类似地可证明，即。12、设是一个格，试证明对于任意的元素，有下列命题成立： (1) 若，则 (2) 若，则 (3) 证明：(1) 因为，所以，同理有，因此。 (2) 因为，所以。 (3) 由格的分配律又因为为和的上确界，因此 因此得证。13、设和是格中的两个元素，试证明当且仅当不可比时，。证明：必要性：(反证)已知 不可比，因为一定有，所以若，则，因此可比，因此矛盾。 充分性：(反证)假设可比，则由格的性质，且，矛盾。14、设集合，集合上所有分划所构成的集合为，你能否适当定义上一个偏序关系,使得成为一个格？解：记，其中为的一种分划，定义上的偏序关系为，若分划是的一个细分，则。显然有，对任意，因此具有自反性；若，则因此具有反对称性；若，则(根据细分的定义很容易得出)，所以具有可传递性，因此是偏序关系。中3个元素，共5种： 则对定义二元运算(若)，(若和不可比) (若)，(若和不可比) 可以画出该偏序关系的次序图如下：显然定义的偏序关系是格。 15、试证明在格中对任意元素，有证明:因为，所以， ，所以可得： ，同理有： ，和所以成立。 16、试证明在格中对于任意元素，有：时，格是分配格。证明：必要性：设是分配格，则对于任意有： 充分性：对于任意，令，则满足等式： (1)于是式(1)的左边左边因为，故所以。将带入(1)的右边得右边所以有。因此是分配格。 第8章 图论1、图1所示之图是否同构于图2 图1 图2答：根据点和边的关联关系，构造，显然是双射且满足同构的定义。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 有多少个生成子图？(3)如果没有任何两个子图是同构的，则G的子图个数是多少？请将这些子图构造出来？答：(1)含有一个结点的子图有个，含有两个结点的子图有个，含有三个结点的子图有个，含有4个结点的子图有个，所以共有112个子图。(2) G的生成子图包含G的所有结点，因为G有6条边，构成子图时，每条边有被选和不被选择两种情况，因此G生成的子图为=64种。(3)G的所有不同构的子图如下：共18个。 5、在图4中找出其所有的真路和环，该图是否包含有割边？ 图4解：真路：等。环：等。其中是割边，因为该条边不在G的任何环中出现。6、图G的邻接矩阵为： 给出，G是否是连通的？解：直接由邻接矩阵给出图G的一个图解，如下图所示，显然G是不连通的。 7、求下图中图(a)和图(b)的全部断集： (a) (b)解：对于图(a)，都是边割集。对于图(b)，都是边割集。8、证明图的任一生成树和任一边割集至少有一条公共边。证明：设图中若有一个边割与的一棵生成树没有公共边，那么删去后所得子图必包含，这意味着仍连通，与是边割集矛盾，所以一定有与至少有一条公共边，9、试作出一个连通图，使之满足等式。解：上图中由定义可得10、设图中各结点的度都是3，且结点数与边数间有如下关系 问(1) 中结点数与边数各为多少？ (2) 在同构的意义下是唯一的吗？解：(1) 由题知该图的总度数为，由握手定理知边数与度数的关系为，又由，可以解出边数，结点数。(2) 在同构的意义下图不唯一，见第一节的例8中图(b)和图(c)。11、若图的补图同构于，则称为自补图。试证明下图所示的图是自补图。你能否找到其他5结点的自补图。 证明：上图的补图为图与其补图的结点集合之间可以建立一一对应关系，因此两个图是同构的。12、已知关于人员的下述事实： 说英语；说英语和西班牙语；说英语、意大利语和俄语；说日语和西班牙语；说德语和意大利语；说法语、日语和俄语；说法语和德语，试问上述7人中是否任意两个人都能交谈？如有必要，可由其余5人中所组成的译员链帮忙？解：设7个人为7个结点，将两个懂同一种语言的人之间连成一条边，即表示他们能直接交谈。这样就得到一个简单图G，问题就转化为G是否连通，G如下图所示，因为G中任意两个结点是连接的，所以G是连通图。因此，上述7个人中任意两个能交谈。13、试从下图中找出一条欧拉回路： 解：14、试在下图中找出一条欧拉路：解：。15、判断下面4个图哪个是欧拉图，哪个是哈密顿图，在各适当情况下指出欧拉回路和哈密顿环。 (a)解：图(a)是欧拉图，存在一条欧拉回路为；图(a)是哈密顿图，存在一个哈密顿环。 (b)解：图(b)是欧拉图，具有一条欧拉回路，不是哈密顿图。 (c)解：图(c)不是欧拉图，是哈密顿图，存在一个哈密顿环。(d)解：图(d)不是欧拉图，也不是哈密顿图。16、 构造下图中图G的闭包，并判断G是否为哈密顿图？如果不用观察的方法，你能说出你判别的根据嘛？解：先求图G的闭包n=6。因为；，所以连接与，与得图G1：在图G1中，因为因此，连接与，与，与，与的图G2：在图G2 中，因为，因此连接与得图G3：且G3是G的闭包，因此G是哈密顿图。17、某流动售货员居住在城，打算走销城后返回城。若该四城间的距离如下图所示，试找出完成该旅行的最短路线。 解：本题要求售货员将4个城市走且仅走一次，形成一个哈密顿环，并使得所走的路线最短。因此满足条件的走法应该是。18、构造互不同构的所有6结点的树。解：先画出6个顶点，然后分别考虑顶点的度数最大为2,3,4,5的情况，不同构的树有5个，如下图所示：19、试证明当且仅当图中得每一条边均为割边时，图是树林。证明：设连通图的每条边都是割边，则去掉任一条边后得到的子图不连通，这说明中没有回路，根据树的定义知，是一棵树。反之，若是一棵树，根据树的性质，去掉任一条边后就不连通了，所以的每条边都是割边。20、证明或反驳下一结论：连通图的任一边为的某一生成树的弦。解：若连通图含有割边，则为任何生成树的弦；若不含割边，那么对的任一边，一定在某个环路上，用破圈法构成生成树时，可在中删去，相对生成树，一定是弦。因此该结论当不含割边时才成立。21、试证明具有条边的连通图最多具有个结点。证明：数学归纳法 当时，显然一条边且连通，则只能有两个点，即；假设当时，点数，则当时，增加的一条边由于连通所以一定去某点相邻接的，因此最多增加一个点，所以点数，所以由数学归纳法结论成立。22、个结点的完全图的环秩是多少？解：个结点的完全图的边数为 ，因此其环秩为。 23、一棵树有5个度为2的结点，3个度为3的结点，4个度为4的结点，2个度为5的结点，其余均为度为1的结点，问它有几个度为1的结点？解：设有个度为1的结点，则总的度数为+10+9+16+10=+45根据树的定义，一棵树的边数等于点数减去1，而总度数又等于边数的两倍，因此有 (+45)/2=5+3+4+2+-1=13+ 解得： =19第9章 命题逻辑1、判断下列语句哪些才是命题，若是命题，则指出其真值(1) 只有小孩才爱哭(2) (3) 请勿随地吐痰(4) 你明天有空吗？(5) 3是素数(6) 银是白色的(7) 起来吧，我的朋友答：(1)是假命题，(5)是真命题，(6)是真命题，其它都不是命题2、将下列命题符号化(1) 昨天下雨并且打雷答：令昨天下雨，令昨天打雷命题可表示为：(2) 我看见的既不是小张也不是老李答：令我看见的是小张，令我看见的是老李命题可表示为：(3) 当他心情好的时候，他一定会唱歌，当他在唱歌的时候，就说明他心情一定很好答：令他心情好，令他在唱歌命题可表示为：(4)人不犯我，我不犯人；人若犯我，我必犯人答：令人犯我，令我犯人命题可表示为：(5)如果晚上做完了作业并且没有其它的事情，他就会看电视或者听音乐答：令晚上做完作业，晚上有其它事情，看电视，听音乐命题可表示为：3、设表示命题小王乘坐公交车，表示小王在看书，表示小王在唱歌。试用日常生活语言重复下列命题的内容(1) 答：小王一边乘公交车一边看书但是没有唱歌(2) 答：小王在乘公交车或者看书，但是他肯定没有唱歌(3) 答：如果小王在乘公交，那么他不是看书就是唱歌(4) 答：小王没有乘公交也没有看书，他只是在唱歌4、构造下列命题公式的真值表(1) 00011010011001010100101110011000100101010011000001110000 (2) 00010 00001 1 0 1 1 010 0 0 0 0011 0 0 0 0100 1 1 0 1101 1 1 1 1110 0 0 0 0111 0 0 0 0(4) 00 1 0 101 1 1 010 0 0 111 1 1 15、下列命题公式中哪些是重言式？哪些是矛盾式？(1) 答：先给出命题公式的真值表如下0011111011011110011001100010因此上式是可满足式(2) 答：真值表如下00101011111000111111因此上式是永真式或者重言式(3) 答：真值表如下001101011011100110111011因此上式是可满足式6、对于给定的代换产生下列公式的代换实例(1) ；用代换，用代换答：(2) ，用代换，用代换答：7、证明下列命题公式的等值关系(1) 证明：左边得证(2) 证明：左边(3) 证明：显然由(2)已经证明(4) 证明：右边(5) 证明： 得证。8、证明下列命题公式的蕴含关系(1)证明：左边 右边因此有左边右边，得证。(2) 证明：假设后件为假，即为假，又因为若为假，则一定为真，因此为真，而为假，由此看前件，因为恒为真，因此为真，为假，因此前件为假，所以当后件为假的时候，前件一定为假，因此得证。(3) 证明：假设后件为假，则一定有为真，而为假。因为恒为假，有为假，为真，因此前件为假，因此得证。9、求下列公式的析、合取范式(1) 证明：上式是合取范式。(2) 证明：上式是合取范式上式是析取范式(3) 证明：原式析取范式上式是合取范式10、求下列命题公式的主合取范式和主析取范式，并判断公式是否为重言式或矛盾式(1) 方法一：真值表方法0011100011011110011111100001主析取范式为：
展开阅读全文