华东师范大学离散数学章炯民课后习题第1章答案

第一篇：华东师范大学离散数学章炯民课后习题第1章答案

P10 1 对下面每个集合，判断2和{2}是否它的一个元素。

(1){xR | x是大于1的整数}

(2){xR | x是某些整数的平方}

(3){2, {2}}

(4){{2},{{2}}}

(5){{2}, {2,{2}}}

(6){{{2}}} 解：

{2}是(3)，(4)，(5)的元素。2是(1)，(3)的元素。下列哪些命题成立？哪些不成立？为什么？

（1）{,{}}

（2） {,{}}（3）{}{,{}}（4）{{}}{,{}} 解：

（1）

成立（2）成立（3）成立（4）成立 设A集合={a,b,{a,b},}。下列集合由哪些元素组成？

(1)A-{a,b};(2){{a.b}}-A;(3){a,b}-A;(4)A--;(5)-A;(6)A-{}.解：

(1){{a,b},}(2)(3)(4)A(5)

(6){a,b,{a,b}} 假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用A和B表示ECNU不必学习离散数学的二年级的学生的集合。解：A∩B 设A,B和C是任意集合，判断下列命题是否成立，并说明理由。(1)若AB,CD，则A∪CB∪D,A∩CB∩D；(2)若AÐB,CÐD，则A∪CÐB∪D,A∩CÐB∩D；(3)若A∪B=A∪C，则B=C；(4)若A∩B=A∩C，则B=C； 解：

(1)成立

(2)不一定成立(3)不一定成立(4)不一定成立

11（5）设A、B和C是集合，请给出(A-B)(A-C)=成立的充要条件。

解：错误！未找到引用源。AB∪C

试求：

(1)P();(2)P(P());(3)P({,a,{a}})解：

(1){}(2){，{}}(3){，{}，{a}，{{a}}} 设A是集合，下列命题是否必定成立?（1）AP(A)（2）AP(A)（3）{A}P(A)（4）{A}P(A)解：

(1)成立

(2)不一定成立(3)不一定成立(4)成立

设A＝{a,b}，B={b,c},下列集合由哪些元素组成？(1)A×{a}×B;(2)P(A)×B;(3)(B×B)×B;解：

(1){(a,a,b),(a,a,c),(b,a,b),(b,a,c)}(2){(,c),(,b),({a},c),({a},b),({b},c),({b},b),({a,b},c),({a,b},b)}(3){((b,b),c),((b,b),b),((b,c),c),((b,c),b),((c,b),c),((c,b),b),((c,c),c),((c,c),b)} 设A是任意集合，A3=(A×A)×A=A×(A×A)是否成立？为什么？ 解：不成立。22 证明证明：

x,xBBABA

AxABAB,xAB,xAxBA

综上，BBA

n-1*24 nN，An是集合，令Bn=An-∪Ak。证明：

k=1（1）i,j∈N，i≠j，Bi∩Bj=（2）An=Bn

n∈Nn∈N证明：（1）i,j∈N, i≠j，不妨设i

k1k1111(A1乔LAi-1乔AiAi+1 LAj-1)

n-1Bn=An-UAkk=1 Bn⊆An An⊆Bn

nNnN∀x，x∈UAn错误！未找到引用源。∃n∈N,使x∈An

nÎN设n0为满足x∈An的最小的自然数

n0-1n0-1k于是x∈An,xÏ0k=1UAx

?Bn0An0-k=1UAk尬xn NUBn

所以UAnÍn挝NnUBnN综上，An=Bn

nNnN 以1开头或者以00结束的不同的字节（8位的二进制串）有多少个? 解：27+26-25=160

补充：用谓词表示法给出集合{-3，-2，-1，0，1，2，3}。解：{x||x|<4  xZ}

第二篇：华东师范大学离散数学章炯民课后习题第2章答案

P32

11*2设n>1是奇数，证明n整除(1+++)(n-1)!2n-1证明：

11++)(n-1)!=[(11)(11)(11)](n1)!2n-11n12n2

nnn)(n1)!n1n1n12(n2)

111](n1)!n1n1n1n2(1+=(=n[

4求方程963x+657y=(963,657)的所有整数解。

解：

（1）

由辗转相除法可得到方程的一个解：x0 =-15，y0=22

设(x,y)也是一个解，则963x+657y=(963,657)

于是963(x-x0)+657(y-y0)=0，从而107(x-x0)=-73(y-y0)，所以10773(y-y0)。又因为(107,73)=1,所以107(y-y0)

设(y-y0)=107k，则(x-x0)=-73k，从而x=x0-73k，y=y0+107k

容易验证，对于任意整数k，(x0+73k,y0+107k)满足原方程。

所以，原方程有无穷多个解：x=-15-73k

y=22+107k

其中k=…,-2,-1,0,1,2,…

（2）

963x+657y=(963,657) 963x-9=-657y

x,yZ，963x-9=-657y  xZ，963x≡9(mod 657)

5．设a、b、c、d是正整数，满足ab=cd。证明：a4+b4+c4+d4不是素数。证明：设11)(n-1)!∴n整除(1+++2n-1adp，其中p和q是互素的正整数 cbq

aq=cp  paq  pa（∵p和q互素）

于是，uN，使a=pu  c=qu

同理vN，使d=pv  b=qv

从而，a4+b4+c4+d4=(p4+q4)(u4+v4) a4+b4+c4+d4不是素数

7团体操表演过程中，要求队伍在变换成10行、15行、18行、24行时均能成长方形，问需要多少人？

解：

由题意，所求之数为10,15,18,24的倍数，[10,15,18,24]＝360，故需360k(k>0)人。

10证明：如果p,p+2,p+4都是素数，则p=3。

证明：用反证法，假设p≠3。

p,p+1,p+2是3个连续的整数，其中有且仅有一个为3的倍数。

p,p+2是素数，且p≠3  p+1是3的倍数

不妨设p+1=3k(kN)。

于是，p+4=3(k+1)必为合数，与条件矛盾。

所以，p=3

11计算2400 mod 319。

解：

φ(n)=319*(1-1／11)(1-1／29)=280

2400 mod 319=2280·2120mod 319=2120mod 319=(210)12mod 319)=(3*319+67)12 mod 319=(672)6 mod 319=((23)2)3 mod 319=(210)3 mod 319=111

14(2)解同余方程：56x≡88(mod 96)。

解：

（1）(a,m)=(56,96)=8，8|96，方程有解

（2）a=56/8=7，b=88/8=11，m=96/8=12

（3）由辗转相除法可求得p和q满足pa+qm=1，p=-5，q=3

特解x0=pb=-511

（4）解为x-511+t12(mod 96)，t=0,1,,7 即x≡5,17,29,41,53,65,77,89(mod 96)

16(1)解同余方程组：x3(mod5)x7(mod9)

解：

m1=5，m2=9，M=45，M1=9，M2=5

9x≡1(mod 5),5x≡1(mod 9),的特解：c1=-1,c2=2原方程组的解：x≡-1×3×9+2×7×5≡43(mod 45)

5x7(mod 12)16(2)解同余方程组7x1(mod 10)

解：

5x≡7(mod 12) 12(5x-7) 4(5x-7)且3(5x-7) 5x≡7(mod 4)且5x≡7(mod 3)∴同余方程5x≡7(mod 12)与同余方程组5x7(mod 4)同解

5x7(mod 3)

x3(mod 4)后者可规约为 x2(mod 3)

类似地，同余方程7x≡1(mod 10)可规约为同余方程组

x1(mod 2)x3(mod 5)

x2(mod 3)x2(mod 3)x3(mod 4)x3(mod 4)∴原同余方程组可规约为，它与同余方程组同解 x3(mod 5)x1(mod 2)

x3(mod 5)

x2(mod 3)x3(mod 4)求解同余方程组： x3(mod 5)

m1=3，m2=4，m3=5，M=60，M1=20，M2=15，M3=12

20x≡1(mod 3),15x≡1(mod 4),12x≡1(mod 5)的特解：c1=2,c2=3,c3=3

原同余方程组的解：x≡2×2×20+3×3×15+3×3×12≡80+135+108≡23(mod 60)

*17解同余方程组：

x≡3(mod 8)，x≡11(mod 20)，x≡1(mod 15)。

解：

x3(mod 8)x3(mod8)x11(mod 4)x1(mod 3)原同余方程组与同余方程组x11(mod 5)同解，后者可规约为x1(mod 5)x1(mod 5)x1(mod 3)

x3(mod8)x1(mod 3)： 求解同余方程组x1(mod 5)

m1=8，m2=3，m3=5，M=120，M1=15，M2=40，M3=24

15x≡1(mod 8),40x≡1(mod 3),24x≡1(mod 5)的特解：

c1=7,c2=1,c3=4

原同余方程组的解：x≡7×3×15+1×1×40+4×1×24≡351+40+96≡91(mod 120)

19．*设m1和m2是正整数，b1和b2是整数。证明一次同余方程组

x≡b1(mod m1)，x≡b2(mod m2)

有解的充分必要条件是(m1,m2)|(b1-b2)；并且，当此条件成立时，该同余方程组的解可表示为x≡c(mod [m1,m2])，其中0

证明：用反证法，假设p≠3。

（1）

有解  可设x为一个解  m1x-b1，m2x-b2  k1,k2Z，使x-b1=k1m1, x-b2=k2m2  b2-b1=k1m1-k2m2

(m1,m2)|m1,(m1,m2)|m 2 (m1,m2)| k1m1-k2m2=(b1-b2)

（2）

(m1,m2)|(b1-b2) k,s,tN，使(b1-b2)=k(m1,m2)=k(sm1+tm2)

容易验证，x=b1-ksm1是同余方程组的解  有解

（3）容易验证，解x，kZ，x+k[m1,m2]也是解  结论

补充：编写一程序实现Miller-Rabin素性测试算法。已知RSA密码体制的公钥(e,n)=(5,35)，（1）请按本小节例题所示的方式将明文信息“rsa”加密；

（2）请破解出私钥。

解：

（1）

明文信息由26个小写字母构成，数字化编码为字母的序号：a01，r18，s19，明文“rsa”181901

取段长为2，明文” 181901”分为3段：m1=18，m2=19，m3=01

用公钥(5,35)加密得到3个密文：

c1=m1e mod n =185 mod 35=23

c2=m2e mod n =195 mod 35=24

c3=m3e mod n =015 mod 35=01

组合得到密文串：232401

（2）

由公钥：KU=(e,n)=(5,35)得到n=35的两个素因数p=5,q=7，(n)=(p-1)(q-1)=24，e=5(5,24)=1，解同余方程5d≡1(mod 24)，得到唯一解d=5

私钥： KR=(d,n)=(5,35)

请编写一个高效的指数取模运算算法

/*

exp_mod.c

handle the Modexp calculation((a^p)%m)using Montgomery algorithm(O(logn))*/

#include

int expmod(int a, int p, int m){

int r;

int k;

if(p==0)return 1;

r=a%m;

k=1;

while(p>1){

if((p&1)!=0)

k=(k*r)%m;

r=(r*r)%m;

p>>=1;

}

return(r*k)%m;

}

void main()

{

int a,b,c,r;

scanf(“%d%d%d”,&a,&b,&c);

r=expmod(a,b,c);

printf(“(%d^%d)%%%d=%dn”,a,b,c,r);

//getch();

}

编写一程序实现Miller-Rabin素性测试算法

#include

#include

int powmod(int i,int d,int n)//模n的大数幂乘快速算法

{

int c = 1;//c为余数，保存每次模后的数

while(d == 0)

{

if(d % 2 == 0){d = d / 2;i =(i * i)% n;}//d是偶数，就先求i平方的模

else {d--;c =(c * i)% n;}//d是奇数，就与上一次的模相乘后在求模

}

return c;//d为0，只能通过d--，所以返回的必是c

}

void main()

{

int i = 2,d,n;

d = n1){printf(“是素数”);break;} //如果模为n-1也结束，因为只有当模为1时才能不断地把d折半

}

else {printf(“ 不是素数”);printf(“%d”,powmod(i,d,n));break;}//如果在d折半的过程中出现的powmod不是1或n-1的话就结束

}

if(d == 1)printf(“是素数”);//如果d一直都能折半到1，也为素数

//getch();

}

第三篇：华东师范大学离散数学章炯民课后习题第3章答案

1.下列语句哪些是命题？（1）2是正数吗？（2）x2+x+1=0。（3）我要上学。

（4）明年2月1日下雨。

（5）如果股票涨了，那么我就赚钱。

解：

(1)不是(2)不是(3)不是(4)是(5)是

2.判断下列命题的真值：（1）若1+1=3，则2+2=4（2）若鸟会飞，则 1+1=3 解：

(1)1(2)0

11.将下列两个命题符号化，并分别用真值表和等值演算的方法证明所得到的那两个命题公式是等值的。

（1）你不会休息所以就不会工作，你没有丰富的知识所以你就不会工作；（2）你会工作所以一定会休息并具有丰富的知识。解：

设p：你会休息，q:你会工作，r:你有丰富的知识。原命题符号化为(1)(pq)(rq)(2)q(pr)

12.（1）用等值演算的方法证明命题恒等式p(qp)=p(pq)。

13.构造一个只含命题变量p、q和r的命题公式A，满足：p、q和r的任意一个赋值是A的成真赋值当且仅当p、q和r中恰有两个为真。解：(pqr)(pqr)(pqr)

14.通过等值演算求p(p(qp))的主析取范式和主合取范式。解：

主析取范式：(pq)(pq)(pq)(pq)主合取范式不存在

15.一教师要从3名学生A、B和C中选派1～2人参加市级科技竞赛，需满足以下条件：（1）若A去，则C同去；（2）若B去，则C不能去；

（3）若C不去，则A或B可以去。

问该如何选派？

解：为此问题建立数学模型。

有三个方案：仅C去，仅B去，仅A和C去

16.证明{,}是功能完备集。

17.（1）证明p(qs),q,prrs。证明：

① pr

前提引入

② r

附加前提引入 ③ p

①②析取三段 ④ p(qs)

前提引入 ⑤ qs

③④假言推理 ⑥ q

前提引入 ⑦ s

⑤⑥假言推理

19.构造下列推理的形式证明：

“今天下午没有出太阳并且今天比昨天冷。只有今天下午出太阳，我们才去游泳。若我们不去游泳，则我们乘独木舟游览。若我们乘独木舟游览，则我们在黄昏时回家。所以，我们在黄昏时回家。” 解：

设p: 今天下午出太阳,q: 今天比昨天冷,r: 我们去游泳m: 我们乘独木舟游览, n: 我们在黄昏时回家

命题符号化为：

前提：pq,rp, rm,mn 结论：n 证明：

① pq

前提引入 ② p

①化简 ③ rp

前提引入 ④ r

②③拒取式 ⑤ rm

前提引入 ⑥ m

④⑤假言推理 ⑦ mn

前提引入 ⑧ n

⑥⑦假言推理

补充：

1.将当当网的图书高级搜索符号化：http://search.dangdang.com/AdvanceSearch/AdvanceSearch.aspx?c=0

解：p:书名q:著译者r:ISBN s:折扣t:定价u:当当价v:出版时间w:出版时间

符号化为：pqrstuvw

2.请将语句“除非你已满16周岁，否则只要你身高不足1.2米就不能乘公园的滑行铁道”。解：

设p:你已满16岁，q:你身高足1.2米，r:你能乘公园的滑行铁道 命题符号化为：(pq)r

3.p、q、r为如下命题：

p：你得流感了

q：你错过了最后的考试

r：这门课你通过了

请用自然语言表达命题(pr)(qr)。解：

（1）如果你得流感了，你就不能通过这门课；或者你错过了最后的考试，你也不能通过这门课。（2）

如果你得流感了并且错过了最后的考试，那么你就不能通过这门课。

第四篇：离散数学课后习题答案

第一章部分课后习题参考答案 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。

（1）p∨(q∧r) 0∨(0∧1)0（2）（p↔r）∧(﹁q∨s)（0↔1）∧(1∨1)0∧10.（3）（p∧q∧r）↔(p∧q∧﹁r)（1∧1∧1）↔(0∧0∧0)0(4)（r∧s）→(p∧q)（0∧1）→(1∧0)0→01 17．判断下面一段论述是否为真：“是无理数。并且，如果3是无理数，则2也是无理数。另外，只有6能被2整除，6才能被4整除。”

答：p: 是无理数

q: 3是无理数

0

r: 2是无理数

s: 6能被2整除t: 6能被4整除

0

命题符号化为： p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。19．用真值表判断下列公式的类型：（4）(p→q)→(q→p)（5）(p∧r)(p∧q)（6）((p→q)∧(q→r))→(p→r)答：

（4）

p

q

p→q

q

p

q→p

(p→q)→(q→p)

0

0

0

0

0

0

0

0

0

0

所以公式类型为永真式

（5）公式类型为可满足式（方法如上例）（6）公式类型为永真式（方法如上例）

第二章部分课后习题参考答案

3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.1(1)(p∧q→q)(2)(p→(p∨q))∨(p→r)(3)(p∨q)→(p∧r)答：(2)（p→(p∨q)）∨(p→r)(p∨(p∨q))∨(p∨r)p∨p∨q∨r1

所以公式类型为永真式

(3)P

q

r

p∨q

p∧r

（p∨q）→(p∧r)0

0

0

0

0

0

0

0

0

0

0

0

0 0

0

0 1

0

0

0

0 1

0

1

0

0

0 1

所以公式类型为可满足式

4.用等值演算法证明下面等值式：(2)(p→q)∧(p→r)(p→(q∧r))(4)(p∧q)∨(p∧q)(p∨q)∧(p∧q)证明（2）(p→q)∧(p→r)(p∨q)∧(p∨r)p∨(q∧r))p→(q∧r)（4）(p∧q)∨(p∧q)(p∨(p∧q))∧(q∨(p∧q)(p∨p)∧(p∨q)∧(q∨p)∧(q∨q)1∧(p∨q)∧(p∧q)∧1 (p∨q)∧(p∧q)5.求下列公式的主析取范式与主合取范式，并求成真赋值

(1)(p→q)→(q∨p)(2)(p→q)∧q∧r(3)(p∨(q∧r))→(p∨q∨r)解：

（1）主析取范式

(p→q)→(qp)(pq)(qp)(pq)(qp)(pq)(qp)(qp)(pq)(pq)(pq)(pq)(pq)m0m2m3

∑(0,2,3)主合取范式：

(p→q)→(qp)(pq)(qp)(pq)(qp)(p(qp))(q(qp))1(pq)(pq) M1

∏(1)(2)主合取范式为：

(p→q)qr(pq)qr (pq)qr0 所以该式为矛盾式.主合取范式为∏(0,1,2,3,4,5,6,7)矛盾式的主析取范式为 0(3)主合取范式为：

(p(qr))→(pqr)(p(qr))→(pqr)(p(qr))(pqr)(p(pqr))((qr))(pqr))11 1 所以该式为永真式.永真式的主合取范式为 1 主析取范式为∑(0,1,2,3,4,5,6,7)第三章部分课后习题参考答案

14.在自然推理系统P中构造下面推理的证明：(2)前提：pq,(qr),r 结论：p(4)前提：qp,qs,st,tr 结论：pq

证明：（2）

①(qr)前提引入 ②qr ①置换 ③qr ②蕴含等值式 ④r 前提引入 ⑤q ③④拒取式 ⑥pq 前提引入 ⑦￢p（3）⑤⑥拒取式

证明（4）：

①tr 前提引入 ②t ①化简律 ③qs 前提引入 ④st 前提引入

⑤qt ③④等价三段论 ⑥（qt）(tq)⑤ 置换 ⑦（qt）⑥化简 ⑧q ②⑥ 假言推理 ⑨qp 前提引入 ⑩p ⑧⑨假言推理(11)pq ⑧⑩合取

15在自然推理系统P中用附加前提法证明下面各推理：

4(1)前提：p(qr),sp,q 结论：sr 证明

①s 附加前提引入 ②sp 前提引入 ③p ①②假言推理 ④p(qr)前提引入 ⑤qr ③④假言推理 ⑥q 前提引入 ⑦r ⑤⑥假言推理

16在自然推理系统P中用归谬法证明下面各推理：

(1)前提：pq,rq,rs 结论：p 证明：

①p 结论的否定引入 ②p﹁q 前提引入 ③﹁q ①②假言推理 ④￢rq 前提引入 ⑤￢r ④化简律 ⑥r￢s 前提引入 ⑦r ⑥化简律 ⑧r﹁r ⑤⑦ 合取

由于最后一步r﹁r 是矛盾式,所以推理正确.

第五篇：离散数学课后习题答案第三章

第六章部分课后习题参考答案

5.确定下列命题是否为真：

（1）

真

（2）

假（3）{}

真

（4）{}

真（5）｛a,b｝｛a,b,c,｛a,b,c｝｝

真（6）｛a,b｝｛a,b,c,｛a,b｝｝

真（7）｛a,b｝｛a,b,｛｛a,b｝｝｝

真（8）｛a,b｝｛a,b,｛｛a,b｝｝｝

假

6．设a,b,c各不相同，判断下述等式中哪个等式为真:（1）｛｛a,b｝，c,｝ =｛｛a,b｝,c｝

假（2）｛a ,b,a｝=｛a,b｝

真（3）｛｛a｝，{b}｝=｛｛a,b｝｝

假（4）｛，｛｝，a,b｝=｛｛,｛｝｝,a,b｝

假 8．求下列集合的幂集：

（1）｛a,b,c｝ P(A)={ ,{a},{b},{c},{a,b},{a,c},{b,c},{a,b,c}}（2）｛1，｛2，3｝｝ P(A)={ , {1}, {{2,3}}, {1，{2，3}} }（3）｛｝ P(A)={ , ｛｝ }

（4）｛，｛｝｝ P(A)={ , {1}, {{2,3}}, {1，{2，3}} } 14．化简下列集合表达式：（1）（AB）B）-（AB）（2）（（ABC）-（BC））A 解:(1)（AB）B）-（AB）=（AB）B）～（AB）

=（AB）～（AB）)B=B=

（2）（（ABC）-（BC））A=（（ABC）～（BC））A =（A～（BC））（（BC）～（BC））A =（A～（BC））A=（A～（BC））A=A 18．某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网 球，还有2人会打这三种球。已知6个会打网球的人都会打篮球或排球。求不会打球的人数。解: 阿A={会打篮球的人}，B={会打排球的人}，C={会打 |A|=14, |B|=12, |AB|=6,|AC|=5,| ABC|=2, 如图所示。

25-(5+4+2+3)-5-1=25-14-5-1=5 不会打球的人共5人

21.设集合A＝{{1，2}，{2，3}，{1，3},{}},计算下列表达式：（1）A（2）A（3）A（4）A 解:（1）A={1，2}{2，3}{1，3}{}={1，2，3,}

（2）A={1，2}{2，3}{1，3}{}=

（3）A=123=

（4）A=

27、设A,B,C是任意集合，证明(1)(A-B)-C=A-BC(2)(A-B)-C=(A-C)-(B-C)证明

(1)(A-B)-C=(A～B)～C= A(～B～C)= A～(BC)=A-BC(2)(A-C)-(B-C)=(A～C)～(B ～C)=(A～C)(～BC)=(A～C～B)(A～CC)=(A～C～B) = A～(BC)=A-BC 由（1）得证。

网球的人} |C|=6,CAB

第七章部分课后习题参考答案

7.列出集合A={2,3,4}上的恒等关系I A,全域关系EA,小于或等于关系LA,整除关系DA.解：IA ={<2，2>,<3,3>,<4,4>} EA={<2,2>,<2,3>,<2,4>,<3,4>,<4,4>,<3,2>,<3,3>,<4,2>,<4,3>} LA={<2,2>,<2,3>,<2,4>,<3,3>,<3,4>,<4,4>} DA={<2,4>} 13.设A={<1,2>,<2,4>,<3,3>}

B={<1,3>,<2,4>,<4,2>} 求AB,AB, domA, domB, dom(AB), ranA, ranB, ran(AB), fld(A-B).解：AB={<1,2>,<2,4>,<3,3>,<1,3>,<4,2>} AB={<2,4>} domA={1,2,3} domB={1,2,4} dom(A∨B)={1,2,3,4} ranA={2,3,4} ranB={2,3,4} ran(AB)={4} A-B={<1,2>,<3,3>}，fld(A-B)={1,2,3} 14.设R={<0,1><0,2>,<0,3>,<1,2>,<1,3>,<2,3>} 求RR, R-1, R{0,1,}, R[{1,2}] 解：RR={<0,2>,<0,3>,<1,3>} R-1,={<1,0>,<2,0>,<3,0>,<2,1>,<3,1>,<3,2>} R{0,1}={<0,1>,<0,2>,<0,3>,<1,2>,<1,3>} R[{1,2}]=ran(R|{1,2})={2,3}

16．设A={a,b,c,d}，R1，R2为A上的关系，其中

R1=a,a,a,b,b,d

R2a,d,b,c,b,d,c,b23求R1R2,R2R1,R1,R2。

解: R1R2={,,} R2R1={} R12=R1R1={,,} R22=R2R2={,,} R23=R2R22={,,}

36．设A={1，2，3，4}，在AA上定义二元关系R，,AA，〈u,v> R u + y = x + v.(1)证明R 是AA上的等价关系.(2)确定由R 引起的对AA的划分.（1）证明：∵R u+y=x-y ∴Ru-v=x-y AA ∵u-v=u-v ∴R ∴R是自反的

任意的,∈A×A 如果R，那么u-v=x-y ∴x-y=u-v ∴R ∴R是对称的

任意的,,∈A×A 若R,R 则u-v=x-y,x-y=a-b ∴u-v=a-b ∴R ∴R是传递的

∴R是A×A上的等价关系

(2)∏={{<1,1>,<2,2>,<3,3>,<4,4>}, {<2,1>,<3,2>,<4,3>}, {<3,1>,<4,2>}, {<4,1>}, {<1,2>,<2,3>,<3,4>}, {<1,3>,<2,4>}, {<1,4>} }

41.设A={1，2，3，4}，R为AA上的二元关系, 〈a，b〉，〈c，d〉 AA ，〈a，b〉R〈c，d〉a + b = c + d(1)证明R为等价关系.(2)求R导出的划分.(1)证明：

a+b=a+b ∴R ∴R是自反的

任意的,∈A×A 设R，则a+b=c+d ∴c+d=a+b ∴R ∴R是对称的 任意的,,∈A×A 若R,R 则a+b=c+d,c+d=x+y ∴a+b=x+y ∴R ∴R是传递的

∴R是 A×A上的等价关系

(2)∏={{<1,1>}, {<1,2>,<2,1>}，{<1,3>,<2,2>,<3,1>}，{<1,4>,<4,1>,<2,3>,<3,2>}, {<2,4>,<4,2>,<3,3>}, {<3,4>,<4,3>}, {<4,4>}}

43.对于下列集合与整除关系画出哈斯图:(1){1,2,3,4,6,8,12,24}(2){1,2,3,4,5,6,7,8,9,10,11,12} 解: ***19511

42(1)(2)45.下图是两个偏序集的哈斯图.分别写出集合A和偏序关系R的集合表达式.debafc

gbcfdeag

(a)(b)解:(a)A={a,b,c,d,e,f,g} R={,,,,,,,,,}IA

(b)A={a,b,c,d,e,f,g} R={,,,,,,}IA 46.分别画出下列各偏序集的哈斯图,并找出A的极大元`极小元`最大元和最小元.(1)A={a,b,c,d,e} R={,,,,,,}IA.(2)A={a,b,c,d,e}, R={}IA.解:

edbcadeabc

(1)

(2)项目(1)(2)极大元: e a,b,d,e 极小元: a a,b,c,e 最大元: e 无 最小元: a 无

第八章部分课后习题参考答案

1．设f :NN,且

1，若x为奇数

f(x)=x

若x为偶数2，求f(0), f({0}), f(1), f({1}), f({0,2,4,6,…})，f({4,6,8}), f-1({3,5,7}).解：f(0)=0, f({0})={0}, f(1)=1, f({1})={1}, f({0,2,4,6,…})=N，f({4,6,8})={2,3,4}, f-1({3,5,7})={6,10,14}.4.判断下列函数中哪些是满射的?哪些是单射的?哪些是双射的?(1)f:NN, f(x)=x2+2

不是满射，不是单射

(2)f:NN,f(x)=(x)mod 3,x除以3的余数

不是满射，不是单射

1，若x为奇数(3)f:NN,f(x)=

不是满射，不是单射

0，若x为偶数

0，若x为奇数(4)f:N{0,1},f(x)=

是满射，不是单射

1，若x为偶数(5)f:N-{0}R,f(x)=lgx

不是满射，是单射

(6)f:RR,f(x)=x2-2x-15

不是满射，不是单射

5.设X={a,b,c,d},Y={1,2,3},f={,,,}判断以下命题的真假:(1)f是从X到Y的二元关系,但不是从X到Y的函数;

对

(2)f是从X到Y的函数,但不是满射,也不是单射的;

错

(3)f是从X到Y的满射,但不是单射;

错

(4)f是从X到Y的双射.错