湘潭大学 刘任任版 离散数学课后习题答案 习题2.doc

习 题 二1.确定下列二元关系：（1）（2） 分析：本题主要运用知识为集合的交、关系以及笛卡尔积的定义。解：(1) (2) 2. 请分别给出满足下列要求的二元关系的例子：（1）既是自反的，又是反自反的；（2）既不是自反的，又不是反自反的；（3）既是对称的，又是反对称的；（4）既不是对称的，又不是反对称的. 分析 本题主要考察关系的5个性质（自反性、反自反性、对称性、反对称性、传递性）。解：设是定义在集合上的二元关系。(1) 令，则，于是既是自反又是反自反的；(2) 令，于是既不是自反又不是反自反的；(3) 令，于是既是对称又是反对称的；(4) 令，于是既不是对称又不是反对称的。3. 设集合有个元素，试问：（1）共有多少种定义在上的不同的二元关系？（2）共有多少种定义在上的不同的自反关系？（3）共有多少种定义在上的不同的反自反关系？（4）共有多少种定义在上的不同的对称关系？（5）共有多少种定义在上的不同的反对称关系？分析：本题主要考察知识为二元关系的自反性、反自反性、对称性、反对称性所对应的关系矩阵之性质，本题可以在做完第四题（根据满足某个性质的关系之关系矩阵）之后再来考虑。解：设，于是(1) 共有种定义在上的不同的二元关系；(2) 共有种定义在上的不同的自反关系；(3) 共有种定义在上的不同的反自反关系；(4) 共有 种定义在上的不同的对称关系；(5) 共有种定义在上的不同的反对称关系，其中，。4. 请分别描述自反关系，反自反关系，对称关系和反对称关系的关系矩阵以及关系图的特征.分析： 本题主要是根据自反关系、反对称关系、对称关系和反对称关系之定义来确定关系矩阵以及关系图。解：(1) 自反关系矩阵的主对角线上元素全为1；而关系图中每个结点上都有圈。(2) 反自反关系矩阵的主对角线上元素全为0; 而关系图中每个结点上均无圈。(3) 对称关系矩阵为对称矩阵; 而关系图中任何两个结点之间的有向弧是成对出现的, 方向相反。(4) 反对称关系矩阵的元素满足：当时，。5设，试求及.分析 主要考察关系的复合运算之定义。解： 。6. 试举出使成立的二元关系的实例. 分析 本题主要说明关系的复合与关系的交运算不满足分配率。解：设,于是, 有, 因此, 从而, 。又，因此，从而, 。7. 设和是集合上的二元关系. 下面的说法正确吗?请说出理由. （1）若和是自反的，则也是自反的；（2）若和是反自反的，则也是反自反的；（3）若和是对称的，则也是对称的；（4）若和是反对称的，则也是反对称的；（5）若和是传递的，则也是传递的分析 本题主要是考察两个满足同一种性质的关系之复合运算是否保该性质，是的可以根据定义给出证明，不正确请给出反例，一般如果正确相对容易证明，不正确给出反例相对较难。解：(1) 正确。因为对任意，有，所以。故是自反的。(2) 错误。例如，设，且，于是。故不是自反的。(3) 错误。例如，设对称关系。于是，但。故不是对称的。(4) 错误。例如，设反对称关系。于是，。故不是反对称的。(5) 错误。例如，设传递关系。于是， ，但因为，所以，。8设和是集合上的二元关系，试证明：（1）；（2）；（3）并举出使时使的实例. 分析：（1）本小题根据自反闭包的定义，它一个关系的自反闭包应该包含，然后根据即可证得。（2）本小题根据对称闭包的定义，它一个关系的对称闭包应该包含，然后根据即可证得。（3）由于传递闭包的特殊性，它不满足类似与（1）（2）的情形，所以要进行相对麻烦的证明，主要运用集合的包含关系的证明方法。 解：(1) (2) (3) 由定义， 于是，。 下证对任意，有。任取，不妨设。于是，存在 使得从而， 。举例说明“”成立。设，于是，。9设和是集合上的二元关系，试证明：（1）；（2）；（3）并请给出时使和的实例. 分析：（1）本题主要是根据自反关系的定义得到一个特殊的等式进行变换，只要想到这个等式，下面的工作就比较容易做。（2）本题主要是根据对称关系的定义及定理2.2.6得到如下三个公式：, ,，有这三个公式以及集合之间包含关系的证明方法就可得到结论。（3）本小题根据传递闭包的定义及定理2.2.6得 有了上面三个等式以及集合之间包含关系证明方法可得结论。解：设是集合上的二元关系。注意到，于是，(1) = = = =(2) , ,。任取，(i) 若 则 且 从而， ；(ii) 若 则 即 从而， 且 于是， 故 。举例说明“”成立。设，于是，而，因此，。（3）证明：因为又设 A= 1, 2, 3 , ，于是， 而，故 .10有人说，“如果集合上的二元关系是对称和传递的，则必是自反的. 因此，等价关系定义中的自反性可以去掉”. 并给出如下证明，如果，由的对称性有，再由的传递性知，且，即是自反的. 你的看法如何?分析：本题主要是没有弄明白对称和传递都是满足一定前提条件的，而自反关系则是中每个元素都必须满足这个条件。解：说法不正确。 对任意, 对称性并不要求一定有， 因此也就不一定有。于是 。例如：设,，则是对称和传递的，但是不是自反的，因为中不包含，这是因为如果是自反的必须包含。11设是集合上的自反关系. 试证明是等价关系当且仅当若，则. 分析：本题主要是利用等价关系中自反性、对称性、传递性的定义来证明。解：设R是等价关系。若 , R , 则由R的对称性知, R。再由R的传递性有R。反之, 假设只要, R, 就有R。(1) 对称性。 设R，由自反性有R。于是R。(2) 传递性。 设, R。 由对称性有R, 再由假设有R。12设和都是集合上的等价关系，试证明当且仅当. 分析：本题主要是根据等价类的定义及性质可以得到。证明：设 , 则显然 。反之, 设。若 , 则不妨设 但 .于是 , .由划分之定义得知 , 矛盾.。故。13设是定义在整数集Z上的模5同余关系，求Z/R. 分析：本题主要是等价类的定义及性质可以得到。解：设 R= | xy(mod 5).于是0 =-15,-10,-5,0,5,10,151 =-14,-9,-4,1,6,11,16,2 =-13,-8,-3,2,7,12,17,3 =-12,-7,-2,3,8,13,18,4 =-11,-6,-1,4,9,14,19,A/R = 0 ,1 ,2 ,3 ,4 .14设和是集合的两个划分，令试证明也是的一个划分. 证明：本题主要是根据划分的定义以及集合的性质可以得到。 证明: .(1) 由S 定义知, ;(2) 任取和, 1=i ,j=r, 1=j,m1,且1kn,设b是A的某个元素,若b组成一个块,则有f(n-1,k-1)种方法能将Ab分成k-1块,另一方面, Ab分成块的每个划分允许b被接纳到一块中,有k种方法,因此我们有f(n,k)=f(n-1,k-1)+kf(n-1,k).16设，偏序关系为整除. 试分别画出，以及的Hasse图. 12解： 15 54 6 3 5 2 3 27 9 1 3 x1x2x3x4x5图2.317设的Hasse图如图2. 3所示：（1）求的最大（小）元，极大（小）元；（2）分别求和的上（下）界，上（下）确界.分析：本题主要是根据极大（小）元，最大（小）元 ，上（下）界，上（下）确界的定义进行求解。 解：(1) 最大元x1, 无最小元;(2) 上界 下界 上确界 下确界x2, x3, x4 x1 x4 x1 x4x3, x4, x5 x1,x3 无 x3 无x1, x2, x3 x1 x4 x1 x418请分别举出满足下列条件的偏序集的实例：（1）为全序集，但的某些非空子集无最小元；（2）不是全序集，的某些非空子集无最大元；（3）的某些非空子集有下确界，但该子集无最小元；（4）的某些非空子集有上界，但该子集无上确界分析：本题主要是根据全序集的定义以及最大（小）元的定义进行举例。解：(1) 为全序集, Z 整数集,但无最小元 , 其中=;(2)题16中的,子集3 ,5无最大元;(3) 题16中的,子集2,3,6有下确界但无最小界;(4) 子集a,b,e有上界d, e,但无上确界。19试证明：每一个有限的全序集必是良序集. 分析：本题主要是说明全序集、良序集的关系，根据他们的定义很容易得到。证明：设为全序集, 且|A| = n。任取 ,因B中的任意两个元素x, y均有x=y或者y=x。因此, B中必有最小元a.故为良序集。20设为偏序集. 试证明的每个非空有限子集至少有一个极小元和极大元. 分析：本题注意是根据题设的子集的有限性以及极大元、极小元的定义很容易求的。证明：设B是