当前位置：文档视界 › 离散数学第九章

离散数学第九章

离散数学第10章

第十章 3. 在R 中定义二元运算，使得,a b R ?∈有 *a b a b ab =++ 证明构成独异点解：（1）,,R a b R φ≠?∈，存在唯一*a b a b ab R =++∈，所以为代数系统。 (2) Z z y x ∈?,,,有(*)**(*)x y z x y z xy yz xz xyz x y z =++++++=，所以结合律成立。 (3) 设存在幺元为e R ∈，对x R ?∈，幺元应满足 e x e x ex x =++= x e x e xe x =++= 所以幺元为0R ∈。所以构成独异点 8. 设{}0,1,2,3G =,若4?为模4乘法，则4,?G 构成什么？（2）零元为0，幺元为1，且运算表对称，结合律考虑4种情况 222,333,223,233,结合律成立。（3）幺元为1 （4）零元为0，所以0的逆元不存在。所以4,?G 构成半群，独异点，不能构成群。 10. 设{0,1}A x x R x =∈≠且，在A 上定义了六个函数如下： 11231 1 1 456(),(),()1()(1),()(1),()(1) f x x f x x f x x f x x f x x x f x x x ----===-=-=-=- 令F 为这6个函数构成的集合，运算为函数合成运算 (1) 给出运算的运算表 (2) 验证,F <> 是一个群。解：(1)

(2) a) 由运算表可得：运算封闭，且F 不是空集，所以,F <> 为一个代数系统。 b) 函数复合运算满足结合律。 c) 单位元为f1 d) f1-1=f1, f2-1=f2, f3-1=f3, f4-1=f5, f5-1=f4, f6-1 =f6, 所以,F <> 为群

离散数学--第九章--作业答案

习题9 1-7 1、答、运算表如下表所示： 2、答、（1），；，；，；，（2）、运算标如下表： 3、答、（1）可以，（2）不可以 4、答、（1）封闭（2）不封闭

（3）加法、乘法都封闭（4）加法不封闭，乘法封闭（5）不封闭（6）加法、乘法都封闭（7）封闭（8）加法不封闭，乘法封闭（9）加法不封闭，乘法封闭（10）加法不封闭，乘法封闭 5、答、（1）没有交换律、结合律，对于一个运算不能考虑分配率（3）加法满足交换律、结合律，乘法满足结合律，乘法对加法满足分配率（4）乘法满足结合律（6）加法和乘法都满足交换律、结合律，乘法对加法满足分配率（7）满足结合律（8）乘法满足交换律、结合律（9）乘法满足交换律、结合律（10）乘法满足交换律、结合律 6、答、（1）没有单位元、零元，没有可逆元素（3）n阶全0矩阵是加法单位元，也是乘法的零元；n阶单位矩阵是乘法单位元；加法没有零元。任意n阶矩阵M对于加法都是可逆元素，其逆元为-M；只有n阶可你矩阵（行列式不为0）对乘法是可逆元素，其逆元为

（4）乘法单位元为n阶单位矩阵，没有零元。每个矩阵M都是逆元（6）加法单位元0，没有零元，每个元素x都可逆，其逆元是它的相反数-x，当n=1时，乘法有单位元1，只有两个可逆元素：，。当＞时乘法没有单位元和可逆元素。（7）没有单位元和零元，也没有可逆元素（8）乘法单位元为1，只有1是可逆元素，（9）乘法单位元为1，只有1是可逆元素，，乘法零元是0 （10）乘法没有单位元、零元以及可逆元素 7、答、（1）4*6=4,7*3=3 （2）满足交换律、结合律、幂等律（3）没有单位元，1是零元，没有可逆元素

离散数学章节练习 1 KEY

离散数学章节练习 1 范围：命题逻辑班级：________________ 学号：________________ 姓名： ________________ 一、单项选择题 1.给定如下4个语句，其中是命题的是 ( ) A.现在开始考试！ B. 我正在考试。 C.我正在说谎话。 D. 你是大学生吗? 2. 设p:17=5,q 地球是方的,r ：4×4>8,s 现在是夏季,结果为真的公式是 ( ) A ． r →p ∧s B. p →q ∧r C. s →q ∧r D. (p ∧r)∨(q ∧s) 3.给定如下4个语句，其中是复合命题的是 ( ) A. 我会游泳。 B.如果天不下雨,我就去踢足球。 C.新闻联播每天都有。 D.火星上有人吗? 4.命题公式(p ∧q)→q 为 ( ) A.矛盾式； B.可满足式； C.重言式； D.合取范式。 5．设P ：我是青年学生，Q ：我有社会责任感。命题：“除非我不是青年学生，否则我有社会责任感”符号化正确的是 ( ) A ．?P ∧Q B ． P →?Q C ．?P →?Q D ．?Q →?P 6. 下列命题公式为重言式的是 ( ) A ．(P ∨?P)→Q B ．P →(P ∨Q) C ．Q ∧?Q D ．P →?Q 7.命题逻辑中一组公式H 1，H 2， ···,H n .，C ，存在关系H 1∧ H 2∧···∧H n ?C 当且仅当H 1∧H 2∧···∧H n →C 是 ( ) A. 矛盾式。 B. 永假式。 C. 可满足式。 D. 永真式。 8.给定如下4个语句，其中是不是命题的是 ( ) A.我现在在考试 B. 今天没有下雨 C.如果你来，我就来 D. 2X+3>8 9. 设p:现在是白天,q ：1中国比日本人口少，,r ：猪是可以飞的,s 我是女生,结果为真的公式是 ( ) A ． r →p ∧s B. p →q ∧r C. s ∨q →q ∧r D. (p ∧r)∨(q ∧s) 10.公式p ∧ q ∨ r 合取范式是 ( ) A. (p ∧r)∨(q ∧r) B. (p ∨r) ∧ (q ∨r) C. (p ∨q) ∧ (q ∨r)) D. (p ∨q) ∧ (p ∨r)) 11. 命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为 ( ) A ．0 B ．1 C ．2 D ．3 。 12. 下列语句中，是命题的是。 ( ) A 请把门关上 B 地球外的星球上也有人 C x + 5 > 6 D 下午有会吗？ 13. 设p:17>5,q:正常人会走路,r ：美国不在亚洲,s:太阳比月亮小，结果为假的公式是 ( ) A ． r →p ∧s B. p →q ∧r C. s →q ∧r D. (?p ∧r)∨( ?q ∧s) 14. 命题公式((p →q) →(?q →?p)) ∨r 的类型是 ( ) A. 永真式。 B.永假式。 C. 非永真式可满足式。 D. 重言式 15.给定如下4个语句，其中是真命题的是 ( ) A.冬天会下雪 B. 请给我一个苹果 C.我正在说谎话。 D. 3+4<20 16.下烈公式中是矛盾式的是 ( ) A ． r →p ∧s B. p ∨?p → p ∧?p C. s →q ∧r D. (p ∧r)∨(q ∧s) 17. 对命题“除非交通阻塞，否则他不会迟到”符号化（p ：交通阻塞，q:他迟到）后的公式正确的是 ( ) A. p →?q B. p →q C.q →p D. ? p →q 18.给定如下4个语句，其中是命题的是 ( ) A.2055年元旦会下雪。 B. 我是一名在校大学生？ C.我现在说的不是真话。D. 请向国旗敬礼！ 19. 设p:我是少先队员,q 太阳每天从东方升起,r ：黄山是世界上最高的山,s 所有人都喜欢中国,结果为假的公式是 ( ) A ． r →p ∧s B. p →q ∧r C. s →q ∧r D. (p ∧r)∨(q ∧s) 20.公式(p ∧r)∨(p ∧s)的主析取范式中有几个最小项 ( ) A.1 B. 3 C. 5 D.7 21. 下列是真命题的有 ( ) A ．3>7； B ．不是每一个人都会飞； C ．你不能说假话； D ．有的人会飞。 22. 下列公式中为永真式的公式是 ( ) A ． r → r ∨（p ∧s ） B. p →q ∧r C. s →q ∧r D. (p ∧r)∨(q ∧s) 23.给定如下4个语句，其中是假命题的是 ( ) A.这次，我一定要考好！ B. “15>27”是错的 C.我正在说谎话。 D.15>27 24.下列公式为永假式的是 ( ) A ． r →p ∧s B. p →q ∧r C. s →q ∧r D. (p ∧r) ∧ (?p ∧s) 25. 设 p ：天冷，q ：小王穿羽绒服，命题“除非天冷，小王才穿羽绒服”.符号化为 ( ) A ．p →q B. q →p C ．?q →p D . q →?p 26.下列公式中，不是p →(q →p)的代换实例的是 ( ) A. F(x,y)→(G(x,y)→F(x,y)) B. F(x,y)→G(x,y)→F(x,y) C. F(y,x)→(G(x,y)→F(x,y)) D. F(x,y)→(G(x,y)→F(y,x)) 27.给定如下4个语句，其中是假命题的是 ( ) A.请来北京参加会议！ B. 北京是中国的首都。 C 上海人口比长沙多 D. 中国人均身高2.48米 28. 下面那个公式不是可满足式 ( ) A ． r →p ∧s B. p →q ∧r

离散数学第10章习题答案

第10章习题答案 1.解 (1)设G 有m 条边，由握手定理得2m ＝∑∈V v v d )(＝2＋2＋3＋3＋4＝14，所以G 的边数7条。 (2)由于这两个序列中有奇数个是奇数，由握手定理的推论知，它们都不能成为图的度数列。 (3) 由握手定理得∑∈V v v d )(＝2m ＝24，度数为3的结点有6个占去18度，还有6度由其它结点占有，其余结点的度数可为0、1、2，当均为2时所用结点数最少，所以应由3个结点占有这6度，即图G 中至多有9个结点。 2.证明设1v 、2v 、…、n v 表示任给的n 个人，以1v 、2v 、…、n v 为结点，当且仅当两人为朋友时其对应的结点之间连一条边，这样得到一个简单图G 。由握手定理知 ∑=n k k v d 1 )(＝3n 必为偶数，从而n 必为偶数。 3. 解由于非负整数列d ＝(d 1，d 2，…，d n )是可图化的当且仅当∑=n i i d 1 ≡0(mod 2)，所以(1)、(2)、 (3)、(5)能构成无向图的度数列。 (1)、(2)、(3)是可简单图化的。其对应的无向简单图如图所示。 (5)是不可简单图化的。若不然，存在无向图G 以为1，3，3，3度数列，不妨设G 中结点为1v 、2v 、 3v 、4v ，且d(1v )＝1，d(2v )＝d(3v )＝d(4v )＝3。而1v 只能与2v 、3v 、4v 之一相邻，设1v 与2v 相邻，于是d(3v )＝d(4v )＝3不成立，矛盾。 4.证明因为两图中都有4个3度结点，左图中每个3度结点均与2个2度结点邻接，而右图中每个3度结点均只与1个2度结点邻接，所以这两个无向图是不同构的。 5. 解具有三个结点的所有非同构的简单有向图共16个，如图所示，其中(8)~(16)为其生成子图。 6. 解 (1)G 的所有子图如图所示。 (1)(3)(5) (6) (9)(10) (13) (14)

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

P179 1. 给出下列序列的一个递推关系：（4）{n 2+3n} （6）{1+(-1)n } 解： (4) a n =a n-1+2n+2(n>0)，a 0=0 (6) a n =a n-1+2(-1)n (n>0)，a 0=2 或110 220n n n a a a --=?=?=?，a 0=2 3. 设含连续三个0的n 位二进制串的数目是s n ，请给出{s n }的递推关系和初始条件。解：a n = a n-1 +a n-2 +a n-3+2n-3 (n≥3)，a 0=0，a 1=0，a 2=0 4. 设{1,2,…,n}的错排列数是D n ，请给出{D n }的递推关系和初始条件。解：D n =(n-1)(D n-1+D n-2)，D 1=0，D 2=1 10（2）求初值问题的通项公式：a n =10a n-1-25a n-2；a 0=-7，a 1=15。解：特征方程：r 2-10r+25=0，特征根：r 2=r 1=5 通解：a n =(α+βn)5n 由a 0=α50=α=-7和a 1= (-7+β)51 =15解得：α=-7，β=10 初值问题的解：a n =(-7+10n)2n *12（2）. 求递推关系的一个特解： a n ＝8a n-2-16a n-4+n 24n 。解：特征方程：x 4=8x 2-16，特征根：x 1=-2，x 2=2 一个特解：T n =n 0(a+bn+cn 2) 4n = (a+bn+cn 2)4n 代入递推关系：(a+bn+cn 2)4n =8(a+b(n-2)+c(n-2)2)4n-2-16(a+b(n-4)+c(n-4)2)4n-4 即9cn 2+(9b+8c)n+(8a+4b-16+c)=0 9c=0 9b+8c=0 8a+4b-16+c=0 解得：c=0,b=0,a=2 特解：2n 24n 13（2）. 写出序列{1,0,1,0,1,0,…}的生成函数。解：1+x 2+x 4+x 6+…=2i 2i 01x 1x ∞ ==-∑

离散数学答案第十章格和布尔代数

第十章格和布尔代数习题10.1 1．解 ⑴不是，因为L 中的元素对{2,3}没有最小上界； ⑵是，因为L=｛1,2,3,4,6,9,12,18,36｝任何一对元素a ,b ，都有最小上界和最大下界； ⑶是，与⑵同理； ⑷不是，因为L 中的元素对{6,7}没有最小上界不存在最小上界。 2．证明 ⑴因为，a ≤b,所以，a ∨b=b ；又因为，b ≤c,所以，b ∧c=b 。故a ∨b=b ∧c ； ⑵因为，a ≤b ≤c,所以，a ∧b=a,b ∧c=b,而a ∨b=b ，因此，(a ∧b )∨(b ∧c )=b ；又a ∨b=b,b ∨c=c,而b ∧c=b, 因此，(a ∨b )∧(b ∨c )=b 。即 (a ∧b)∨(b ∧c)=(a ∨b)∧(b ∨c)。习题10.2 1．解由图1知：＜S 1,≤＞不是＜L,≤＞的子格，这是因为，e ∨f=g ?S 1; ＜S 2,≤＞不是＜L,≤＞的子格， ∵e ∧f=c ?S 2; ＜S 3,≤＞是＜L,≤＞的子格. 2．解 S 24的包含5个元素的子格有如下的8个： S 1={1,3,6,12,24}, S 2={1,2,6,12,24}, S 3={1,2,4,12,24}, S 4={1,2,4,8,24}, S 5={1,2,3,6,12}, S 6={1,2,4,6,12}, S 7={2,4,6,12,24}, S 7={2,4,8,12,24}. 3．证明因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是的子集，即是的子代数，故是子格。 4．证明由(10-4)有，a ∧b ≤a ,由已知a ≤c ,由偏序关系的传递性有，a ∧b ≤c ；同理 a ∧b ≤d 。由(10-5)和以上两式有，a ∧b ≤c ∧d . 5．证明因为由(10-4)有，a ∧b ≤a ，因此， (a ∧b )∨(c ∧d )≤a ∨(c ∧d ) ① 由分配不等式有， a ∨(c ∧d )≤(a ∨c )∧(a ∨d ) ② 再由由(10-4)有， (a ∨c )∧(a ∨d ) ≤a ∨c ③ 由偏序关系的传递性和①②③则有， (a ∧b )∨(c ∧d )≤a ∨c 同理 (a ∧b )∨(c ∧d )≤b ∨d 因此有， (a ∧b )∨(c ∧d )≤(a ∨c ) ∧(b ∨d )。习题10.3 1．解 ⑴ 是，全上界是24，全下界是1； ⑵1的补元是24；3的补元是8；8的补元是3，4、6没有补元。图1 图2

离散数学屈婉玲版

1 离散数学（第四版） ( ( ( (耿素云屈婉玲张立昂著) ) ) ) 清华大学出版社第第第第 1 1 1 1 章章章章习题解答习题解答习题解答习题解答 1．1 除（3），（ 4），（ 5），（ 11）外全是命题，其中，（1），（ 2），（ 8），（ 9），（10），（ 14），（ 15）是简单命题，（6），（ 7），（ 12），（ 13）是复合命题。分析首先应注意到，命题是陈述句，因而不是陈述句的句子都不是命题。本题中，（3）为疑问句，（5）为感叹句，（11）为祈使句，它们都不是陈述句，所以它们都不是命题。其次，（4）这个句子是陈述句，但它表示的判断结果是不确定。又因为（1），（2），（ 8），（ 9），（ 10），（ 14），（ 15）都是简单的陈述句，因而作为命题，它们都是简单命题。（6）和（7）各为由联结词“当且仅当”联结起来的复合命题，（12）是由联结词“或”联结的复合命题，而（13）是由联结词“且”联结起来的复合命题。这里的“且”为“合取”联结词。在日常生活中，合取联结词有许多表述法，例如，“虽然……，但是……”、“不仅……，而且……”、“一面……，一面……”、“……和……”、“……与……”等。但要注意，有时“和”或“与”联结的是主语，构成简单命题。例如，（14）、（ 15）中的“与”与“和”是联结的主语，这两个命题均为简单命题，而不是复合命题，希望读者在遇到“和”或“与”出现的命题时，要根据命题所陈述的含义加以区分。 1．2 （1）是无理数，p 为真命题。 2: p （2）能被 2 整除，p 为假命题。 :5 p （6）。其中，是素数，q：三角形有三条边。由于 p 与 q 都是真 qp → 2 : p 命题，因而为假命题。 qp → （7），其中，p：雪是黑色的，q：太阳从东方升起。由于 p 为假命 qp → 题，q 为真命题，因而为假命题。 qp → （8）年 10 月 1 日天气晴好，今日（1999 年 2 月 13 日）我们还不 :2000 p 课后答案网 https://www.docsj.com/doc/3213650883.html, 2 知道 p 的真假，但 p 的真值是确定的（客观存在的），只是现在不知道而已。（9）p：太阳系外的星球上的生物。它的真值情况而定，是确定的。（10）p：小李在宿舍里. p 的真值则具体情况而定，是确定的。（12），其中，是偶数，是奇数。由于 q 是假命题，所以，q qp ∨ 4 : p 4: q 为假命题，为真命题。 qp ∨ （13），其中，是偶数，是奇数，由于 q 是假命题，所以， qp ∨ 4 : p 4: q 为假命题。 qp ∨ （14） p：李明与王华是同学，真值由具体情况而定（是确定的）。（15） p：蓝色和黄色可以调配成绿色。这是真命题。分析命题的真值是唯一确定的，有些命题的真值我们立即可知，有些则不能马上知道，但它们的真值不会变化，是客观存在的。 1．3 令则以下命题分别符号化为 6,33:4,22: +=+= qp （1） qp → （2） qp →?

离散数学结构第14章图的基本概念

第十四章图的基本概念 14.1 图 (2) 一．无向图与有向图 (2) 1．无序积与多重集 (2) 2．无向图与有向图的定义及表示法 (2) 二．简单图与多重图 (4) 1．顶点的度数 (5) 2．握手定理 (5) 四．图的同构 (8) 1．两图同构的定义 (8) 2．图之间的同构关系是等价关系 (8) 五．完全图与正则图 (9) 1．完全图 (9) 2．正则图 (9) 六．子图与补图 (9) 1．子图 (9) 2．补图与自补图 (12) 14.2 通路与回路 (15) 一．通路与回路的定义 (15) 二. n阶图中通路与回路的性质 (17) 14.3 图的连通性 (17) 一、无向图的连通性 (17) 二、无向图中顶点之间的线程线及距离 (18) 三、无向图的连通度 (18) 四、有向图的连通性及其分类 (20) 五、扩大路径法及极大路径 (21) 六、二部图及判别定理 (22) 14.4 图的矩阵表示 (26) 一、无向图与有向图的关联矩阵 (26) 二、有向图的邻接矩阵 (27) 三、有向图的可达矩阵 (29) 典型习题 (29) 14.5 图的运算 (33)

14.1 图主要内容无向图与有向图。简单图与多重图。顶点的度数与握手定理。图的同构。完全图与正则图。子图与补图。学习要求熟练掌握握手定理及其推论的内容及其应用。掌握图同构的概念。加深对简单图、完全图、正则图、子图、补图等概念的理解。一．无向图与有向图 1．无序积与多重集设A，B为任意的两个集合，称{{a,b}|a∈A∧b∈B}为A与B的无序积，记作A&B. 为方便起见，将无序积中的无序对{a,b}记为(a,b),并且允许a=b.需要指出的是，无论a,b是否相等，均有(a,b)=(b,a),因而A&B=B&A. 元素可以重复出现的集合称为多重集合或者多重集，某元素重复出现的次数称为该元素的重复度。例如，在多重集合{a,a,b,b,b,c,d}中，a,b,c,d的重复度分别为2,3,1,1. 2．无向图与有向图的定义及表示法定义14.1一个无向图是一个有序的二元组,记作G，其中（1）V≠称为顶点集，其元素称为顶点或结点。（2）E称为边集，它是无序积V&V的多重子集，其元素称为无向边，简称边。定义14.2一个有向图是一个有序的二元组，记作D，其中（1）V同无向图。（2）E为边集，它是笛卡儿积V×V的多重子集，其元素称为有向边，简称边。上面给出了无向图和有向图的集合定义，但人们总是用图形来表示它们，即用小圆圈（或实心点）表示顶点，用顶点之间的连线表示无向边，用有方向的连线表示有向边。例14.1 (1) 给定无向图G=，其中， V={v1,v2,v3,v4,v5}， E={(v1,v1),(v1,v2),(v2,v3),(v2,v3),(v2,v5),(v1,v5),(v4,v5)}. (2) 给定有向图D=，其中， V={a,b,c,d}，

第十章习题答案

第十章博弈论初步 1.什么是纳什均衡？纳什均衡一定是最优的吗？解答：(1)所谓纳什均衡，是参与人的一种策略组合，在该策略组合上，任何参与人单独改变策略都不会得到好处。 (2)不一定。纳什均衡可能是最优的，也可能不是最优的。例如，在存在多个纳什均衡的情况下，其中有一些纳什均衡就不是最优的；即使在纳什均衡是唯一时，它也可能不是最优的——因为与它相对应的支付组合可能会小于与其他策略组合相对应的支付组合。 2.在只有两个参与人且每个参与人都只有两个策略可供选择的情况下，纯策略的纳什均衡最多可有几个？为什么？解答：在只有两个参与人(如A 和B)且每个参与人都只有两个策略可供选择的情况下，纯策略的纳什均衡最多可有四个。例如，当A 与B 的支付矩阵可分别表示如下时，总的支付矩阵中所有四个单元格的两个数字均有下划线，从而，总共有四个纳什均衡。 A 的支付矩阵＝??????22211211 a a a a B 的支付矩阵＝?? ????22211211b b b b 3.在只有两个参与人且每个参与人都只有两个策略可供选择的情况下，纯策略的纳什均衡可能有三个。试举一例说明。解答：例如，当参与人A 与B 的支付矩阵可分别表示如下时，总的支付矩阵中恰好有三个单元格的两个数字均有下划线，从而，总共有三个纳什均衡。 A 的支付矩阵＝ ??????22211211a a a a B 的支付矩阵＝?? ????22211211b b b b 4.在只有两个参与人且每个参与人都只有两个策略可供选择的情况下，如何找到所有的纯策略纳什均衡？解答：可使用条件策略下划线法。具体步骤如下：首先，设两个参与人分别为左参与人和上参与人，并把整个的支付矩阵分解为这两个参与人的支付矩阵；其次，在左参与人的支付矩阵中，找出每一列的最大者，并在其下划线；再次，在上参与人的支付矩阵中，找出每一行的最大者，并在其下划线；再再次，将已经划好线的两个参与人的支付矩阵再合并起来，得到带有下划线的整个支付矩阵；最后，在带有下划线的整个支付矩阵中，找到两个数字之下均划有线的所有的支付组合。这些支付组合所代表的策略组合就是纳什均衡。 5.设有A 、B 两个参与人。对于参与人A 的每一个策略，参与人B 的条件策略有无可能不止一个。试举一例说明。解答：例如，在如下的二人同时博弈中，当参与人A 选择上策略时，参与人B 既可以选择左策略，也可以选择右策略，因为他此时选择这两个策略的支付是完全一样的。因此，对于参与人A 的上策略，参与人B 的条件策略有两个，即左策略和右策略。 6.如果无论其他人选择什么策略，某个参与人都只选择某个策略，则该策略就是该参与人的绝对优势策略(简称优势策略)。试举一例说明某个参与人具有某个优势策略的情况。

离散数学第9章习题答案

习题9 1. 设G 是一个(n ，m)简单图。证明：，等号成立当且仅当G 是完全图。证明：（1）先证结论：因为G 是简单图，所以G 的结点度上限 max(d(v)) ≤ n-1, G 图的总点度上限为 max(Σ(d(v)) ≤ n ﹒max(d(v)) ≤ n(n-1) 。根据握手定理，G 图边的上限为 max(m) ≤ n(n-1)/2,所以。（2） =〉G 是完全图因为G 具有上限边数，假设有结点的点度小于n-1,那么G 的总度数就小于上限值，边数就小于上限值，与条件矛盾。所以，G 的每个结点的点度都为n-1，G 为完全图。 G 是完全图 =〉因为G 是完全图，所以每个结点的点度为n-1, 总度数为n(n-1)，根据握手定理，图G 的边数。■ 2. 设G 是一个（n ，n +1）的无向图，证明G 中存在顶点u ，d （u ）≥3。证明：反证法，假设,则G 的总点度上限为max(Σ(d(u)) ≤2 n ，根据握手定理，图边的上限为max(m) ≤ 2n/2=n 。与题设m = n+1，矛盾。因此，G 中存在顶点u ，d （u ）≥3。■ 3．确定下面的序列中哪些是图的序列，若是图的序列，画出一个对应的图来: （1）（3，2，0，1，5）；（2）（6，3，3，2，2）（3）（4，4，2，2，4）；（4）（7，6，8，3，9，5）解：除序列（1）不是图序列外，其余的都是图序列。因为在（1）中，总和为奇数，不满足图总度数为偶数的握手定理。可以按如下方法构造满足要求的图：序列中每个数字ai 对应一个点，如果序列数字是偶数，那么就在对应的点上画ai/2个环，如果序列是奇数，那么在对应的点上画(ai-1)/2个环。最后，将奇数序列对应的点两两一组，添加连线即可。下面以（2）为例说明： (6 , 3, 3, 2, 2 ) 对应图G 的点集合V= { v 1,v 2,v 3,v 4,v 5} 每个结点对应的环数(6/2, (3-1)/2, (3-1)/2, 2/2,2/2) = (3,1,1,1,1) v 1 v 5 v 3 v 4 v 2

离散数学古天龙14章答案

P20 1.用枚举法写出下列集合。 ○2大于5小于13的所有偶数。 A={6,8,10,12} ○520的所有因数 A={1,2,4,5,10,20} ○6小于20的6的正倍数 A={6,12,18} 2.用描述法写出下列集合 ○3能被5整除的整数集合 A{5x|x是整数} ○4平面直角坐标系中单位圆内的点集 A{|x2+y2≤1} 4.求下列集合的基数 ○19 ○3 1 ○7 3 ○8 2 ○10 1 6.求下列集合的幂集 ○6{1，{2}} 解：{空集，{1}，{{2}}，{1，{2}}} ○7解：{空集，{空集}，{a}，{空集，a}} ○9解：{空集，{{1，2}}，{{2}}，{{1，2}，{2}}} 15.设全集U={1，2，3,4,5}，集合A={1，4}，B={1，2，5}，C={2，4}，确定下列集合。 ○2{1，3,5} ○3{1，4,}

○8{5} ○9{空集，{1}，{2}，{4}，{1，4}，{2，4}} 18.对任意集合A，B和C，证明下列各式 ○2（A-(BUC)）=((A-B)-C) 证：（A-(BUC)）=A∩~(BUC)=A∩(~B∩~C) ((A-B)-C)=(A∩~B)∩~C=A∩~B∩~C 所以（A-(BUC)）=((A-B)-C) ○3（A-(BUC)）=((A-C)-B 证：（A-(BUC)）=A∩~(BUC)=A∩~B∩~C ((A-C)-B)=(A∩~C)∩~B 所以（A-(BUC)）=((A-C)-B ○5P(A)UP(B)≤P(A UB) 原题有错（注这里○5○6中的“≤”代表包含于符号）证：任取C∈P（A）U P(B)由定义 C∈P（A）或C∈P（B）若C∈P（A），则C≤A,则C≤A UB 若C∈P(B)，则C≤B,则C≤A UB 故C≤A UB，即C∈P(A U B) 证毕 ○6P(A)∩P(B)=P(A∩B) 证：先证P(A)∩P(B)≤P(A∩B) 任取C∈P(A)∩P(B)，且C∈P(A), C∈P(B) 由定义C≤A且C≤B,得C≤A∩B,即C∈P(A∩B) 所以P(A)∩P(B)≤P(A∩B) 再证P(A∩B)≤P(A)∩P(B) 任取C∈P(A∩B),即C=A∩B C≤A,且C≤B,C∈P(A)且C∈P(B) 所以C∈P(A)∩P(B) 得证

离散数学第九章树知识点总结

图论部分第九章、树 9.1 无向树及生成树无向树、森林无向树的性质定理设G=是n阶m条边的无向图，则下面各命题是等价的：（1）G是树(连通无回路); （2）G中任意两个顶点之间存在惟一的路径; （3）G中无回路且m=n-1; （4）G是连通的且m=n-1; （5）G是连通的且G中任何边均为桥; （6）G中没有回路, 但在任何两个不同的顶点之间加一条新边后所得图中有惟一的一个含新边的圈. 定理设T 是n 阶非平凡的无向树，则T中至少有两片树叶. 证设T有x片树叶，由握手定理及前一个定理可知

生成树的存在性定理任何无向连通图都有生成树. 证用破圈法. 若图中无圈, 则图本身就是自己的生成树. 否则删去圈上的任一条边, 这不破坏连通性, 重复进行直到无圈为止,剩下的图是一棵生成树. 推论1 设n阶无向连通图有m条边, 则m≥n-1.

推论2 设n阶无向连通图有m条边, 则它的生成树的余树有m-n+1条边. 推论3 设为G的生成树T 的余树，C 为G 中任意一个圈，则C与一定有公共边. 基本回路与基本回路系统定义设T是n阶m条边的无向连通图G的一棵生成树，设e1', e2', … , e'm-n+1为T的弦. 设C r为T添加弦e r' 产生的G中惟一的圈(由e r'和树枝组成), 称C r为对应弦e r'的基本回路或基本圈, r=1, 2, …, m-n+1. 称{C1, C2, …, C m-n+1}为对应T的基本回路系统. 求基本回路的算法: 设弦e=(u,v), 先求T中u到v的路径 Γuv, 再并上弦e, 即得对应e的基本回路. 基本割集与基本割集系统定义设T是n阶连通图G的一棵生成树, e1', e2', …, e'n-1为T的树枝，S i是G的只含树枝e i', 其他边都是弦的割集, 称S i为对应生成树T由树枝e i'生成的基本割集, i=1, 2, …, n-1. 称{S1, S2, …, S n-1}为对应T的基本割集系统. 求基本割集的算法: 设e'为生成树T的树枝, T-e'由两棵子树T1与T2组成, 令 S e'={e | e∈E(G)且e的两个端点分别属于T1与T2} 则S e'为e'对应的基本割集.

离散数学章节总结

离散数学章节总结第一章 [命题逻辑] 1.逻辑运算 1.否定:Negation? NOT 2.交:Conjunction AND 3.并:Disjunction OR 4.蕴含:Implication IMPLIES 5. Biconditional ? IFF XOR 2.逆/否/逆否 1.逆:converse 2.否:inverse 3.逆否:conytrapositive 3.问题的一致性 [逻辑等价] →q 等价于?p q 等价于? q→?p 2. p q 等价于?p→q p q 等价于?( p→?q) 3.(p→q)(p→r) 等价于p→(q r) (p→r)(q→r) 等价于(p q)→r (p→r)(q→r)等价于(p q) →r 4.证明等价: 真值表逻辑符号证明找反例 (假设左为假右必为假假设右为假左必为假) [ 谓词逻辑] 1.量词存在任意量词顺序不能随机改变不全为真:(p1p2…p n) (p1p2…p n) x P(x ) x P(x ) 没有一个为真:(p1p2…p n) (p1p2…p n) x P(x ) x P(x ) [ 推理]

[ 证明] 1.证明方法:直接证明间接证明反证列举证明(列举所有情况) 构造证明(构造出满足结论的元素) 2.证明步骤:正向证明反向证明

第二章 [ 集合及运算] 1.特殊集合: R Q Z 无穷/有限集 2.集合表述方法: 列举法描述法图表法 3.集合运算: 交/并/补/差/取子集P(S)/元素数|S|/乘积P ×Q / B A B A B A B A ?=??=? n i i A 1 = X A A ∈ n i i A 1= X A A ∈ 容斥原理 A i i =1n = A i 1≤i ≤n ∑- A i ?A j 1≤i

离散数学第四章部分答案

（1）设S={1，2}，R 是S 上的二元关系，且xRy 。如果R=Is ，则（A ）；如果R 是数的小于等于关系，则（B ），如果R=Es ，则（C ）。（2）设有序对与有序对<5,2x+y>相等，则 x=(D),y=(E). 供选择的答案 A 、 B 、 C ：① x,y 可任意选择1或2；② x=1,y=1；③ x=1,y=1 或 2；x=y=2；④ x=2,y=2；⑤ x=y=1或 x=y=2；⑥ x=1,y=2；⑦x=2,y=1。 D 、 E ：⑧ 3；⑨ 2；⑩-2。答案： A: ⑤ B: ③ C: ① D: ⑧ E: ⑩ 设S=<1,2,3,4>,R 为S 上的关系，其关系矩阵是 ? ? ??? ???????0001 100000011001 则（1）R 的关系表达式是（A ）。（2）domR=(B),ranR=(C). （3）R R 中有（D ）个有序对。（4）R ˉ1的关系图中有（E ）个环。供选择的答案 A :①<1,1>,<1,2>,<1,4>,<4,1>,<4,3>； ②<1,1>,<1,4>,<2,1>,<4,1>,<3,4>； B 、 C ：③1，2，3，4；④1，2，4；⑤1，4⑥1，3，4。 D 、 E ⑦1；⑧3；⑨6；⑩7。答案： A:② B:③ C:⑤ D:⑩ E:⑦ 设R 是由方程x+3y=12定义的正整数集Z+上的关系，即 {＜x,y ＞︳x,y ∈Z+∧x+3y=12}, 则（1）R 中有A 个有序对。（2）dom=B 。 (3)R ↑{2,3,4,6}=D 。 (4){3}在R 下的像是D 。（5）R 。R 的集合表达式是E 。供选择的答案 A:①2;②3;③4. B 、 C 、 D 、E:④{＜3，3＞}；⑤{＜3，3＞，＜6，2＞}；⑥{0，3，6，9，12}；