离散数学(胡海涛)第3章答案

1、离散数学第三章(胡海涛版)1。下列集合分别用描述和枚举表示：(1)非负偶集合；(2)整数24的所有正因子的集合；(3)一组不超过9且以9为素数的正整数(这组中的元素数称为欧拉函数(9)。解答：说明(1)x|x是一个非负偶数(2)x|x是一个24 (3)x| x的正因子，x是一个不超过9的正整数，并且与9 (1) 0，2，4，(2) 1，2，3，4，6，8，12，24()是素数。如果是这样，请给出一个例子。解决方案：存在。A=1，B=1，1，那么AB和AB都有效。3.找出下列集合的幂集：(1)；(2)；(3)a，a；(4)1，2 .解答：解答：(1) p ()=(2) p ()=，(3) p (

2、a，a)=，a，a，a (4) p (1，2)=，1，24。设S=0，1，求集合SP(S)解：解：p (s)=，0，1，0，1 sp (s)=，5。证明对于任何集合A和B，都有P(A)P(B)P(AB)，P(A)P(B)P(AB)并证明：对于任何集合C，如果CP(A)P(B)CP(A)CP(B)CACBCAB，那么P(A)P(B)P(AB)成立。在任意集合c中，如果CP(A)P(B)CP(A)CP(B)CACBCAB，那么P(A)P(B)P(AB)成立。例如：A=1，2，B=2，3，P(A)=，1，2，1，2，P(B)=，2，3，2，3，P(A)P(B)=，1，2，1，2，3，2因此，P(A)

3、P(B)P(AB)。6.设甲、乙、丙为任意集合，并证明：(1)丙(乙)=(甲)(乙)；(2)如果ABBC是已知的，并且有A-BB-C，那么AB。证明：(1)C(AB)=C(AB)(BA)=(C(AB)(C(BA)=(CA)(CB)(CB)=(CA)(CB)(2)证明定律如果结论不正确，那么就有xA和xB，然后是xA-B和xB-C，也就是xB。与xB的矛盾。7.下列关系的属性是什么？(1)有mRn当且仅当|i-k|8(m，Nn)；(3)当且仅当ik(i，kN)时，存在iRk。解答：解答：(1)自反，对称(2)对称(3)自反，对称，传递8。请在满足下列条件的集合Aa，b，c上构造二元关系：(1)对

4、称和反对称；(2)既不反身也不反身；(3)对称性和自反性；(4)反身性、对称性和传递性；(5)作为子集，是可传递的。解决方案：(1)、(2)、(3)、(4)、(5)、(9)。设Rj代表Z上模J的等价关系，Rk代表Z上模K的等价关系，证明了当且仅当K是J的整数倍时，Z/Rk细分Z/Rj。证明：充分性：如果K是J的整数倍，即lZ，设k=lj，Z/Rk=aRk| aZ，Z/Rj=aRj| aZ，ark=x | xzarxx，arj=x | xzarxx，显然对于任何xaRk，ax(mod k)，即必要性证明如果关系r是对称的，那么Rk(k1，kN)也是对称的。证明：设R是A上的二元关系，并且X，yA

5、，如果xRky成立，那么根据关系式的定义，存在x0=x，x1，x2，xk- 1，xk=y，这使得X0RX1，X1RX2，XK-1RXK成立，并且R是对称的，所以xKx0-1，11.设集合A=a，b，c，d上的关系R=，用矩阵运算求R的自反性，对称性和传递闭包。解：0100 1010 0001 0000 R M，1000 0100 0010 0001 A I，1 0100 1000 0100 0010 r m，0100 1010 00001 0000 1000 0100 00100 0010 000010因此，r (r)=，0100 1010 0001 0000 0100 1000 0010=0

6、100 1010 0101 0010 so s(R)=，2 01000100100101010010000100000000000000000000000000000000000000000000000000000000000000000000000000000000000000000设R和S是a和RS上的二元关系，证明：(1)r(R)r(S) (2) S (R)S (S)(3)T(R)T(S)证明：(1)r(R)定义的R(R)有RIA，如果R是RS定义的，R(S)(2)S (R)，S(R)定义的，有RR1，如果R是RS定义的，s(S)，如果R1有R，所以S，所以S1是S(S)，所以S (R)

7、 S (S)。(3)由t(R)定义的t(R)具有Rk(k1，kN)，即x0=x，x1，x2，xk-1，xk=y，这使得x0rx1，x1rx2，xk-1rxk保持不变，并由RS定义，因此x0sx1，x1sx2，13.设R和S是a上的二元关系，并证明：(1)R(RS)=R(R)R(S)(2)S(RS)=S(R)S(S)(3)t(R)t(S)t(RS)证明：(1)(2)S(RS)=(RS)(RS)1=(RS)(R1S1)=(RR1)(SS1)=S(R)S(S).(3) t (r) t (s)=I I r 1 I s 1，t(t(RS)=I I S)R(1=I I R 1 I S 1 Ji SR，1

8、1，显式t(R)t(S)t(RS)。14.找出集合a，b，c和D的所有划分和等价关系.解决方案：集合A、B、C、D共有四个元素，可分为如下四类：1) 41111类型划分，只有一个，即A、B、C、D，对应的等价关系为：2)4211有2 4个C6类型，即A、B、C、D、A、C、B、D、A、D、B、B、C、A、D、B、D、A、C、D、A、B。对应的等价关系如下5)440型分为1，即甲、乙、丙、丁，对应的等价关系为：综上所述，集合a、b、c和D有15个划分和等价关系.15.设R是非空集A上的二元关系，如果A、B和CA满足aRb和bRccRa，那么R称为A上的循环关系，证明了当且仅当R是等价的，R是自反

9、循环的。证明：证明：必要性：如果R是自反的和循环的，它适用于a，b，cA，aRa如果aRc成立，R和cRa是循环的，所以R是对称的；如果aRb和bRc与cRa是循环的，那么R与aRc是对称的，所以R是传递的，所以R是等价的。充分性：如果R是等价的，很明显R是自反的，并且只需要证明R是循环的。对于a，b，cA，如果aRb和bRc，从R的传递性来看，有aRc，然后从R的对称性来看，有cRa，所以R是循环的。16.假设a和B是非空集合，f是从a到B的映射.将A上的二元关系R定义为：x，yA，xRy当且仅当f(x)=f(y)，证明R是A上的等价关系，并描述由R生成的A的除。证明：证明：显然f(x)=f

10、(x)，所以xRx是自反的。如果xRy有f(x)=f(y)，那么f(y)=f(x)，那么yRx，也就是r，是对称的。如果xRy和yRz有f(x)=f(y)，f(y)=f(z)，那么f(x)=f(z)，xRz，也就是说，r是可传递的。因此，r是a上的等价关系.在由R生成的A的除法中，所有具有相同对应值的独立变量都属于同一个块。17.给出一个二元关系，它既是等价关系又是偏序关系。解决方案：R=，在aa，b，c上。18.假设A1、A2和A3是完备集u的子集，那么形式为3 1i Ai(Ai是Ai或Ai)的集合称为由A1、A2和A3产生的次项。证明了A1、A2、A3产生的所有非空项的集合构成了完整集合U

11、的一个划分，证明：(1)3 1 ai(2)3 1 ai 3 1 AIJ=(3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)(a1a 2 A3)=(A1 A2)(a1a 2 19)。设R和S是a上的相容关系，并问：(1)复合关系R和S是a上的相容关系吗？(2)2)RS是A上的相容关系吗？(3)3)RS是A上的相容关系吗？解决方案：(1)让A=1，2，3，R=，S=，R=，不兼容。(2)RS显然是自反的，所以RS是R和S，所以R和S是RS，所以RS是a上的相容关系。在偏序关系“可分”下画出集合S=1，2，3，4，5，6的哈斯图，(1)写出1，2，3，4，5，6的最大(小)元素和最大(小)元素；(2)分别写出2，3，6和2，3，5的上(下)界和上(下)界。解决方案：哈斯图如下：5 4 6