离散数学平时作业

1、第一章假定A是ECNU二年级的学生集合，B是ECNU必须学离散数学的学生的集合。请用 A和B表示ECNU不必学习离散数学的二年级的学生的集合。解：三试求：P() P(P() P(P(P()(1) )(2) , 在1 -200的正整数中，能被 3或5整除，但不能被15整除的正整数共有多少个？能被5整除的有40个，能被15整除的有13个，能被3或5整除，但不能被 15整除的正整数共有66-13+40-13=80个。第三章下列语句是命题吗？2是正数吗？ 2x+x+1=0。(3)我要上学。(4)明年2月1日下雨。(5)如果股票涨了，那么我就赚钱。解：)不是)不是)不是)是)是请用自然语言表达命题 (p

2、Tr)(qTr),其中p、q、r为如下命题:p：你得流感了q：你错过了最后的考试r：这门课你通过了解:(1)如果你得流感了，你就不能通过这门课；或者你错过了最后的考试，你也不能通过这 门课。如果你得流感了并且错过了最后的考试，那么你就不能通过这门课。通过真值表求p-HpNqT p)的主析取范式和主合取范式。解：主析取范式：(p q)(p. q) (p. q) (p q)主合取范式不存在给出 (qTSbq,pLg is的形式证明。证明：前提引入附加前提引入(1 ) (2)析取三段 前提引入(3 ) ( 4 )假言推理 前提引入(5 ) ( 6 )假言推理(1 ) p -RP(4 ) p- (q-

3、 s)q-sQS第四章将以(5*)3丫(5丫)干代丫)翻译成汉语，其中 C(x层示x有电脑，F(x,y)表示x和y是同 班同学，个体域是学校全体学生的集合。解：学校的全体学生要么自己有电脑，要么其同班同学有电脑。构造 Vx(P(x)vQ(x), Vx(Q(xR(x)xR(xV xP(x)的形式证明。解：-xR(x) R(e)-x(Q(x) R(x) Q(e) -R(e)-RQ (e)- x(P(x) Q(x)P(e) Q(e)P(e)-x (P(x)前提引入US规则前提引入US规则析取三段论前提引入US规则析取三段论EG规则第五章. 设 r、s、t都是X 上的关系。证明：rsnTRr冶)n(R

4、T), (Rn s)T(r:jt)n (ST)。解：对x,y三X, R(Sn T)= u( 三R 三 SA T)= u( 三R 三S 三T)= u( 三R 三S 三T 三R)= u( 三R 三S)=u ( 三T 三 R)= ( R S) ( R T)二 三(RS)A (R T)故 R (SA T) (R S)A (R T)对-x,y三X, (RA S) T= u( 三RC S 三 T)= u( ER S T)= u( 三R S 三T 三T)=u( R T)=lu ( S T)= ( R T) ( ST)二 三(RT)A (S T)故(RA S) T (R T)A (S T).设X是所有人组成的

5、集合，定义 X上的关系Ri和R2： aRib当且仅当a比b高，aR2b 当且仅当a和b有共同的祖父母。问关系Ri和R2是否是自反、反自反、对称、反对称、传递的？. 设Ri和R2是X上的关系。证明t(R2R2)m(Ri)5(R2)。.下列集合关于整除关系I构成偏序集。请分别画出它们的哈斯图，判断它们是否是全序集，给出它们的极大元、极小元、最大元、最小元。2,4,8,i6;(4) 2,3,4,5,9/0,80。i.f: XtY,下列命题是否成立?f是一对一的当且仅当对任意f是一对一的当且仅当对任意第六章a,bWX,当 f(a)=f(b)时,必有 a=b;a,bX,当 f(a) wf(b),必有 a

6、wbo解：成立不成立，如f(x)=x22.下图展示了五个关系的关系图。 哪些是到上的函数？哪些是一问：这些关系中，哪些是函数？哪些是一对一的函数? 一对应？解：1是函数，一对一，但不是到上的;2是函数，到上的，但不是一对一;3是函数， 对应；4是函数；5不是函数。第七章6 个学生：Alices Bobh Carol、Dean、Santos和 tom,其中，Alice和 Carol不和，Dean和Carol不和，Santos Tom和Alice两两不和。请给出表示这种情形的图模型。设简单无向图 G=(V,E)若S (G)k(k1),则G有长度为k的基本通路。解：证明：我们假设存在k-1的基本通路

7、，则存在k个顶点，通路最后一个顶点与通路上顶点相连的度 数至多为k-1。因为S (G)k(k1),所以该顶点必定与其他顶点相连，那么存在长度为K的基本通路。得证。一大学有5个专业委员会：物理、化学、数学、生物、计算机，6位院士： B、C、D、G、S Wo专业委员会由院士组成，物理委员会有院士：C、S和W,化学委员会有院士： G D和W;数学委员会有院士：B、G G和S;生物委员会有院士：B和G;计算机委员会有院士： D和Go每个专业委员会每周开一小时例会，所有成员都不能缺席。如果某院士同时是两个专业委员会的成员，那么这两个专业委员会的例会就不能安排在同一个时间。现要为这些例会安排时间，希望它们

8、的时间尽可能集中。问最少需要 几个开会时间？请给出一种安排。答：顶点表示各个专业委员会，边表示两委员会有共同委员。画出如下无向图:3个。一种开会方案为对该图着色，可得最少的开会时间为 数学，生物和化学，物理和计算机。第八章解：从图中删除所标记的 6个顶点， 所得到白图由7个孤立点组成，有 7个连通分量。所 以，该图不满足哈密顿图的必要条件，因而不是哈密顿图。2.证明连通图的割边一定是每棵生成树的边。解:证明：删除割边后的图一定不连通，其中不存在生成树。所以，每课生成树都包含割边第九章.股评家推荐了 12个股票，一股民欲购买其中的3个。问在下列各种条件下，分别有多少种不同的投资方式？(1)每个股

9、票各投资 3000元；2) 3个股票分别投资 5000元、3000元和1000元。解： C123=220(2) P123=1320. 16支互不同颜色的蜡笔平分给4个孩子，有多少种不同的分法？解：C(16,4) C(12,4) C(8,4) C(4,4).某学校有2504个计算机科学专业的学生，其中1876人选修了 C语言，999人选修了Fortran语言，345人选修了 JAVA, 876人选彳了 C语言和Fortran语言，231人选修 了 Fortran 和JAVA, 290人选修了 C和JAVA, 189个学生同时选了 C、Fortran 和JAVA。问没有选这3门程序设计语言课中的任

10、何一门的学生有多少个？解：A表示选修了 C语言，B表示选修了 Fortran语言，C表示选修了 JAVA|A 一B 一C|=|A|+|B|+|C|-|A- B|-|B C|-|C A|+|A B C|=1876+999+345-876-231-290+189=2012则没有选这3门程序设计语言课中的任何一门的学生：2504-2012=492第十章1. 求初值问题的通项公式：an=10an-1-25an-2； a0=-7 , a1=15。解：特征方程：r2-10r+25=0 ,特征根：”=门=5通解：an=(a+函)5n由 a0=a50=a=-7 和 a1= (-7+ 951 =15 解得：=-7