本科离散数学 第9章

离散数学第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是零元，没有可逆元素

最新离散数学(屈婉玲)答案

第一章部分课后习题参考答案 16 设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: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 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 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式//最后一列全为1 （5）公式类型为可满足式（方法如上例）//最后一列至少有一个1 （6）公式类型为永真式（方法如上例）// 第二章部分课后习题参考答案 3.用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值.

(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 1 0 0 1 0 0 1 0 1 0 1 0 0 0 1 1 1 0 0 1 0 0 1 0 0 1 0 1 1 1 1 1 1 0 1 0 0 1 1 1 1 1 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)

离散数学第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.doczj.com/doc/329003896.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 →?

离散数学第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

离散数学章节总结

离散数学章节总结 第一章 [命题逻辑] 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

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

图论部分 第九章、树 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'对应的基本割集.