离散数学答案屈婉玲版 第二版高等教育出版社课后答案 第一章部分课后习题参考答案 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 所以公式类型为永真式
（5）公式类型为可满足式（方法如上例） （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)
第十五章习题解答 1. ()()x xS x xR ?∧?)1( ())()()()()()()(c S b S a S c R b R a R ∨∨∧∧∧解： ())()()2(x Q x P x →? ))((()()()()())()(c Q c P b Q b P a Q a P →∧→∧→解： )()()3(x xP x P x ?∨?? )(()()()())()()(c P b P a P c P b P a P ∧∧∨?∧?∧?解： 2. 指出下列命题的真值： ??-=>=>∨→?}6,3,2{,5:,"5:")(,"3:")(,"23:",)())(((1)D e x x R x x Q P e R x Q P x 论域其中 ).2.(:时不成立为当假解-x 。论域其中，}2{,"4:")(,"3:")() ()(()2(==>→?D x x Q x x P x Q x P x 解：真。 3. 在一阶逻辑中，将下列命题符号化： （1）凡有理数均可表示为分数。 解：P(x)： x 是有理数； Q （x ）:x 可表示为分数。 ))()((x Q x P x →?
())())()((. :,:)(,:)(:. ,)4()) ()((. :)(:)()3()(:)(:)()2(x S x P x W W x x S x x P x Q x P x x x Q x x P x Q x P y x x Q x x P ∧?→→??∧??明天天气好是学生是公园解有一些学生将去公园如果明天天气好是有理数是实数，解：数。 并非所有实数都是有理。 是有理数。 是实数，解：有些实数是有理数。 );()), ()((,,:) ()())()(()1(. ,.4|))) )()(|,(),(()()0,(() ,(:)(,:),(:. |)()(|: ,),,(,0)6())). ,()(()((:),(,:)(:)()5(00000x R x Q x P x x z z Q x xR x Q x P x x f x f G N n G n N x S G x b a x x S y x y x G x f x f N n N b a x x y G y Q y x P x y x y x G x x Q x x P n n 第二个是的作用域是第一个约束变元自由变元解并指出各量词的作用域变元和约束变元指出下列公式中的自由解时有使当都存在对任意给是实数是正实数，解：在大于该实数的实数。 对任意的正实数，都存∧?∧?→∧?-∧??→ ∧??∈><->∈>∧?→?>εεεεε (2)))()(())(()((z Q x xP y Q y x P x →?∨?∧? 解：自由变元z ，约束为元：x ，y 。第一个的作用域为 第二个的作用域为第二个P(x)；第二个的作用域的作用域为 Q(y) （3）)()())()((z s y yR x Q x P x ∧?∧?? 解：自由变元z ，约束为元：x ，y 。 ))()((x Q x P x ??的作用域为 解：自由变元z ，约束为元：x ，y 。 ))()((x Q x P x ??的作用域为 y ?的作用域为R(y)
第一部分： 1.命题/谓词逻辑的推理 2.求析取合取范式 3.求给定解释下公式的值 第二部分： 1.关系的性质/判断，证明 2.偏序关系（哈斯图），极大值，极小值，上界下界 3.证明等价关系 第三部分： 1.证明半群，独异点，群 2.子群 3.同态映射 4.找特异元素 第四部分： 1.点和边的关系 2.邻接矩阵，可选矩阵 3.最优二叉树（哈夫曼的算法） 略过不考的部分： 第二部分：第八章8.3节 第九章全部 第三部分：第十一章11.7节 第十三章全部 第四部分：第十五单全部 第十七单全部 第十八单全部 自己通过网络及课本整理的，希望能帮到大家。内容在下面。。。。
一、命题：其一，语句是陈述句；其二，语句有唯一确定的真假意义. 1.命题公式分类，在各种赋值下均为真的命题公式A，称为重言式(永真式)；在各种赋值下均为假的命题公式A，称为矛盾式(永假式)；命题A不是矛盾式，称为可满足式； 2.主析取(合取)范式法判断命题公式类型，该公式的主析取范式有2n个极小项(即无极大项)，则该公式是永真式；该公式的主合取范式有2n个极大项(即无极小项)，则该公式是永假式；该公式的主析取(或合取)范式的极小项(或极大项)个数大于0小于2n,，则该公式是可满足式. 3.定理1设Φ(A)是含命题公式A的命题，Φ(B)是用命题公式B置换Φ(A)中的A之后得到的命题公式. 如果A?B，则Φ(A)?Φ(B). 4.求析取(合取)范式的步骤：①将公式中的联结词都化成?，∧，∨(即消去个数中的联结词→，?，?∨)；②将否定联结词?消去或移到各命题变项之前；③利用分配律、结合律等，将公式化为析取(合取)范式 5.求命题公式A的主析取(合取)范式的步骤：①求公式A的析取(合取)范式；②“消去”析取(合取)范式中所有永假式(永真式)的析取项(合取项)，如P∧?P(P∨?P)用0(1)替代. 用幂等律将析取(合取)范式中重复出现的合取项(析取项)或相同的变项合并，如P∧P(P∨P)用P替代，m i∨m i(M i∧M i)用m i(M i)替代. ③若析取(合取)范式的某个合取项(析取项)B不含有命题变项P i或?P i，则添加P i∨?P i(P i∧?P i)，再利用分配律展开，使得每个合取项(析取项)的命题变项齐全；④将极小(极大)项按由小到大的顺序排列，用∑(∏)表示. 6.求公式(p∧q)∨r的主析取范式及主合取范式。
第十章 3. 在R 中定义二元运算，使得,a b R ?∈有 *a b a b ab =++ 证明
(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 <> 为群
离散数学复习 第一章命题逻辑基本概念 1．掌握命题及相关概念 2．理解各联结词的逻辑关系 3．会将复合命题符号化 4．会求公式的真值表，并用它求公式的成真赋值、成假赋值及判断公式的类型 第二章命题逻辑等值演算 1．记住基本等值式，会应用它们进行公式的等值演算 2．了解简单析取式、简单合取式、析取范式、合取范式的概念 3．理解极大项、极小项的概念 4．掌握求主析取范式和主合取范式的方法(等值演算和真值表法) 5．会用主范式判断公式的类型及进行简单应用 6．了解联结词完备集的概念 第三章命题逻辑的推理理论 1．理解并记住推理形式结构的两种形式： (1) A1∧A2∧…∧A k→B (2) 前提：A1, A2, … , A k 结论：B 2．掌握判断推理是否正确的不同方法（如真值表法、等值演算法、主析取范式法等）3．记住自然推理系统P系统中的推理规则 4．掌握自然推理系统P系统中的推理方法 第四章一阶逻辑基本概念 1．会进行命题的符号化 2．理解公式的解释 3．理解永真式、矛盾式、可满足式的概念及相互之间的关系 4．对于给定的解释会判断公式的真值，或判定真值不确定（即仍不是命题） 第五章一阶逻辑等值演算与推理 1．理解并记住重要等值式，并能熟练地应用它们 2．会使用置换规则、换名规则(约束条变项)、代替规则(自由变项) 3．会求给定公式的前束范式 4．正确地使用UI, UG, EG, EI规则，特别要注意它们之间的关系 5．在F系统，对给定的推理，正确地构造出它的证明 第六章集合代数 1. 掌握集合的表示法 2．能够判别元素是否属于给定的集合 3．能够判别两个集合之间是否存在包含、相等、真包含等关系 第七章二元关系 1. 掌握二元关系、空关系、全域关系、恒等关系、关系的定义域、值域、域、逆关系、 左复合、右复合、限制、像的概念； 2．掌握关系的集合表达式、关系矩阵和关系图三种表示法； 3．掌握关系的基本运算和关系的幂的运算性质，掌握关系的五个性质：自反性、反自反性、对称性、反对称性和传递性等五个性质； 4．掌握关系的闭包的概念，会应用关系的性质求出关系的闭包（自反闭包、对称闭包和传递闭包）；
1.5集合的划分与覆盖 习题1.5 1.设},,,{d c b a A =，求出集合A 的所有不同的划分. 解 可以按照划分的块的数目依次求出A 的所有不同的划分共15个. 仅一个划分块:}},,,{{1d c b a =π. 有两个划分块: }},,{},{{2d c b a =π，}},,{},{{3d c a b =π， }},,{},{{4d b a c =π，}},,{},{{5c b a d =π； }},{},,{{6d c b a =π，}},{},,{{7d b c a =π， }},{},,{{8c b d a =π. 有三个划分块: }},{},{},{{9d c b a =π，}},{},{},{{10d b c a =π， }},{},{},{{11c b d a =π，}},{},{},{{12d a c b =π， }},{},{},{{13c a d b =π，}},{},{},{{14b a d c =π. 有四个划分块: }}{},{},{},{{15d c b a =π. 2.对于整数集合Z ，令 }Z |3{1∈=k k A ，}Z |13{2∈+=k k A ，}Z |23{3∈+=k k A , 则},,{321A A A 是Z 的划分. 试验证之. 解 因为(1)≠i A ?，3,2,1=i . (2)=?j i A A ?，3,2,1,,=≠j i j i . (3)=??321A A A Z. 所以，},,{321A A A 是Z 的划分. 3.设}|{I i A i ∈=π是集合A 的一种划分，对于集合B ，所有≠?B A i ?的B A i ?组成的集合是B A ?的划分. 试证明之. 证 对于任意j i ≠，因为=?j i A A ?，于是 =??=???B A A B A B A j i j i )()(?=?B ?.
习 题 十 三 1． 证明：对网络N 中的任意一个流f 和)(N V s ?，均有 ∑∈-=-s v s s f s s f v V f V v f ),(),()],(),([ 分析：根据定义∑∈= ∈∈=) ,()()(}|)(){()(V v f V v f V u N A u v V v α α，，，， 显然若)(),(,,2121N A v v S v v ∈∈且，则在）V v f ,(1中含）21,(v v f ，而）1,(v V f 中也含）21,(v v f ，故f 对端点同属于S 的这种弧在 ∑∈-s v v V f V v f )],(),([中不产生影响，故有： ∑∈-=-s v s s f s s f v V f V v f ),(),()],(),([ 证明： 左式)),(),(()),(),(((v u f u v f v u f u v f s v s u s u ∑∑∑∈∈∈-+-= ∑∑∑∑∑∈∈∈∈∈--+=s v s u s u s u s u v u f v u f u v f u v f )),(),(),(),(( ))),(),(()),(),(((∑∑∑∑∑∈∈∈∈∈-+-=s v s u s u s u s u v u f u v f v u f u v f )),(),((∑∑∑∈∈∈-=s u s v s u v u f u v f ∑∑∑∑∈∈∈∈-=s v s u s v s u v u f u v f ),(),( ),(),(S S f S S f -= 2．设),(S S 和),(T T 都是网络N 中的最小割，求证),(T S T S ??和),(T S T S ??也都是N 中 的最小割. 分析：由集合的运算和容量的定义，可直接验证下式成立： ),(),(),(),(T S T S C T T C S S C T S SUT C -+≤? 又由于),(S S 和),(T T 都是网络N 中的最小割，根据最小割的定义有： ),(),(T S SUT C S S C ?≤ ),(),(T S T S C T T C ??≤最后可得
第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)
离散数学(第2版)_在线作业 _4 交卷时间：2017-01-12 14:00:56 一、单选题 1. (5分) ? A. q ∧┐q ? B. p →┐q ? C. p → (p ∨q) ? D. (p ∨┐p)→q 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 2. (5分) ? A. ? B. ? C. ? D. 下列命题公式为重言式的是( )。 设，下列式子正确的是( )。
纠错 得分： 5 知识点： 离散数学(第2版 ) 收起解析 答案 C 解析 3. (5分) ? A. ? B. ? C. ? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 D 解析 4. (5分) ? A. ? B. ? C. 下列是两个命题变元的极小项的是( )。 设G 是有个顶点， 条边和个面的连通平面图，则 等于( )。
? D. 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 5. (5分) ? A. 满射函数 ? B. 非单射非满射函数 ? C. 双射函数 ? D. 单射函数 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 C 解析 6. (5分) 设R 是实数集合，函数，则是( )。
? A. 11，3，4 ? B. 10，4，3 ? C. 11，3，5 ? D. 12，3，6 纠错 得分： 5 知识点： 离散数学(第2版) 收起解析 答案 A 解析 7. (5分) ? A. x*y=gcd(x,y)，即x,y 的最大公约数 ? B. x*y=lcm(x,y)，即x,y 的最小公倍数 ? C. x*y=max{x,y} ? D. x*y=min{x,y} 纠错 得分： 5 知识点： 离散数学(第2版) 下列平面图的三个面的次数分别是( )。 设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A 是不封闭的？( )。
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．证明 因为，一条线上的任何两个元素都有（偏序）关系，所以，都有最大下界和最小上界，故它是格，又因为它是
第十五章欧拉图与哈密顿图 15.1 欧拉图 (2) 一、欧拉通路、欧拉回路、欧拉图、半欧拉图的定义 (3) 二、判别定理 (4) 三、求欧拉图中欧拉回路的算法 (6) 1．Fleury算法，能不走桥就不走桥： (6) 2．逐步插入回路法 (7) 四、中国邮路问题 (8) 练习题： (9) 15.2哈密顿图 (11) 一、哈密顿通路、哈密顿回路、哈密顿图、半哈密顿图的定义 (12) 二、哈密顿图与半哈密顿图的一些必要与充分条件 (12) 练习题 (18) 15.3 带权图与货郎担问题 (24) 一、带权图 (24) 二、货郎担问题 (24)
15.1 欧拉图 主要内容： 1. 欧拉通路、欧拉回路、欧拉图、半欧拉图的定义。 2. 判别定理。 3. 求欧拉图中欧拉回路的算法。 学习要求： 1. 深刻理解欧拉通路与欧拉回路的定义以及它们的区别与联系。 2. 以无向欧拉图为例，进一步理解欧拉图的结构，即，欧拉图是若干个边不重的圈之并。 让我们先从两个例子出发，获得有关图的一些直观认识。 图论的研究起源于哥尼斯堡七桥问题。哥尼斯堡城位于Pnsel河畔，河中有两个岛，有7座桥与4块陆地彼此相连，如上图所示。 居住于该城的居民想做这样的游戏：从4块陆地的任一块出发，经过每座桥一次且仅一次，最后返回原出发地。当地的人们进行了许多次尝试，都没有成功。后来，欧拉给出了问题的解。首先欧拉将4块陆地表示成4个结点，凡陆地间有桥相连的，便在两点间连一条边，从而可将左图改画为右图如下：这样，哥尼斯堡七桥问题可描述为：能否有从A、B、C、D任一点出发，经过每条边一次且仅一次而返回出发点的回路? 欧拉证明了这样的回路是不存在的。他的理由是，从图任一点出发，要回到原出发点，要求与每个点关联的边的数目为偶数，才能保证从一条边进入某点再从另一条边出去，一进一出才能回到原出发点。而图中的顶点A、B、C和D均有奇数条边与其相关联，显然这样的回路是不存在的。 另一个例子是20世纪40年代的一个数学游戏。
离散数学第二版邓辉文编著第一章第二节习题答案 1.2 映射的有关概念 习题1.2 1. 分别计算?1. 5?，?-1?，?-1. 5?，? 1. 5?，?-1?，?-1. 5?. 解?1. 5?=2，?-1?=-1，?-1. 5?=-1，?1. 5?=1，?-1?=-1，?-1. 5?=-2. 2. 下列映射中，那些是双射? 说明理由. (1)f :Z →Z , f (x ) =3x . (2)f :Z →N , f (x ) =|x |+1. (3)f :R →R , f (x ) =x 3+1. (4)f :N ?N →N , f (x 1, x 2) =x 1+x 2+1. (5)f :N →N ?N , f (x ) =(x , x +1). 解 (1)对于任意对x 1, x 2∈Z ，若f (x 1) =f (x 2) ，则3x 1=3x 2，于是x 1=x 2，所以f 是单射. 由于对任意x ∈Z ，f (x ) ≠2∈Z ，因此f 不是满射，进而f 不是双射. (2)由于2, -2∈Z 且f (2) =f (-2) =3，因此f 不是单射. 又由于0∈N ，而任意x ∈Z 均有f (x ) =|x |+1≠0，于是f 不是满射. 显然，f 不是双射. (3)对于任意对x 1, x 2∈R ，若f (x 1) =f (x 2) ，则x 1+1=x 2+1，于是x 1=x 2，所以f 是单射. 对于任意y ∈R ，取x =(y -1) ，这时 1??3f (x ) =x +1=?(y -1) 3?+1=(y -1) +1=y ， ??33313 所以f 是满射. 进而f 是双射.
第十四章图的基本概念 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一个无向图是一个有序的二元组
21st Century University Planned Textbooks of Computer Science (第2版) Discrete Mathematics (2nd Edition) 李盘林赵铭伟徐喜荣李丽双编著 □概念严谨精炼 □叙述简明清晰 □推理详尽严格 人民邮电出版社 POSTS & TELECOM PRESS
第2版前言 离散数学是现代数学的一个重要分支，是计算机科学与技术的理论基础。因此，它是计算机科学与技术专业的核心、骨干课程。一方面，它给后继课，如数据结构、编译系统、操作系统、数据库原理和人工智能等，提供必要的数学基础；另一方面，通过学习离散数学，培养和提高了学生的抽象思维和逻辑推理能力，为其今后继续学习和工作，进行科学研究，攀登科技高峰，打下扎实的数学基础。 本书第1版于2002年2月出版以来，六年来，先后多次印刷发行，已得到了普遍认可，被全国部分普通高校选作教材，本版除了勘误了第1版中的不妥之处外，还增加了一些新的章节，并相应补充了例题和习题，以适应高等学校教学改革的需要。 本书共12章，内容包括命题逻辑、谓词逻辑、集合、关系、函数、代数结构的概念及性质、半群与群、环和域、格与布尔代数、图的概念与表示、几类重要的图以及数论。 本书是笔者结合多年教学实践与科学研究，参考国内外教材，在力求通俗易懂、简明扼要的指导思想下编写而成的。在编写过程中有如下3点考虑。 1. 力求做到“少而精”，注意突出重点，论证详细明了，便于自学，在定理证明中多次运用归纳法，希望读者熟练掌握这一方法。 2. 在加强基本理论教学的同时，注意了分析问题、解决问题的技能培养和训练。书中各知识点均配有典型例子，并加以说明。此外，各章都配有适量的习题，希望通过做习题这个环节，来培养、提高学生解决问题的能力。 3. 一方面每章各有独立性，教师根据需要可以单独选讲几章；另一方面，尽可能注意各章之间的联系，规范并统一了符号和术语。 本书在编写过程中，得到了有关领导、老师和同学的热情关心、支持和帮助，在此一并表示感谢。 限于作者水平，书中难免有不当和疏漏之处，恳请读者批评指正。 编者 于大连理工大学 2008年9月
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{
○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) 得证
1.2 映射的有关概念 习题1.2 1. 分别计算??5.1，??1-，??5.1-，??5.1，??1-，??5.1-. 解 ??25.1=，??11-=-，??15.1-=-，??15.1=，??11-=-，??25.1-=-. 2.下列映射中，那些是双射? 说明理由. (1).3)(,Z Z :x x f f =→ (2).1||)(,N Z :+=→x x f f (3).1)(,R R :3+=→x x f f (4).1),(,N N N :2121++=→?x x x x f f (5)).1,()(,N N N :+=?→x x x f f 解 (1)对于任意对∈21,x x Z ，若)()(21x f x f =，则2133x x =，于是21x x =，所以f 是单射. 由于对任意∈x Z ，∈≠2)(x f Z ，因此f 不是满射，进而f 不是双射. (2)由于∈-2,2Z 且3)2()2(=-=f f ，因此f 不是单射. 又由于∈0N ，而任意∈x Z 均有01||)(≠+=x x f ，于是f 不是满射. 显然，f 不是双射. (3)对于任意对∈21,x x R ，若)()(21x f x f =，则113231+=+x x ，于是21x x =，所以f 是单射. 对于任意∈y R ，取3 1)1(-=y x ，这时 y y y x x f =+-=+??????-=+=1)1(1)1(1)(3313， 所以f 是满射. 进而f 是双射. (4)由于∈)1,2(),2,1(N ?N 且)1,2()2,1(≠，而4)1,2()2,1(==f f ，因此f 不是单射. 又由于∈0N ，而任意∈),(21x x N ?N 均有01),(2121≠++=x x x x f ，于是f 不是满射. 显然，f 就不是双射. (5)由于∈21,x x N ，若)()(21x f x f =，则)1,()1,(2211+=+x x x x ，于是21x x =，因此f 是单射. 又由于∈)0,0(N ?N ，而任意∈x N 均有)0,0()1,()(≠+=x x x f ，于是f 不是满射. 因为f 不是满射，所以f 不是双射.
《离散数学1-5章》练习题答案第2，3章(数理逻辑) 1.答：（2），（3），（4） 2.答：（2），（3），（4），（5），（6） 3.答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 4.答：（4） 5.答：?P ，Q→P 6.答：P(x)∨?yR(y) 7.答：??x(R(x)→Q(x)) 8、 c、P→(P∧(Q→P)) 解：P→(P∧(Q→P)) ??P∨(P∧(?Q∨P)) ??P∨P ? 1 (主合取范式) ? m0∨ m1∨m2∨ m3 （主析取范式） d、P∨(?P→(Q∨(?Q→R))) 解：P∨(?P→(Q∨(?Q→R))) ? P∨(P∨(Q∨(Q∨R))) ? P∨Q∨R ? M0 (主合取范式) ? m1∨ m2∨m3∨ m4∨ m5∨m6 ∨m7 (主析取范式) 9、
b、P→(Q→R)，R→(Q→S) => P→(Q→S) 证明： （1） P 附加前提 （2） Q 附加前提 （3） P→(Q→R) 前提 （4） Q→R （1），（3）假言推理 （5） R （2），（4）假言推理 （6） R→(Q→S) 前提 （7） Q→S （5），（6）假言推理 （8） S （2），（7）假言推理 d、P→?Q，Q∨?R，R∧?S??P 证明、 (1) P 附加前提 （2） P→?Q 前提 （3）?Q （1），（2）假言推理 （4） Q∨?R 前提 (5) ?R （3），（4）析取三段论 (6 ) R∧?S 前提 （7） R （6）化简 （8） R∧?R 矛盾（5），（7）合取 所以该推理正确 10.写出?x(F(x)→G(x))→(?xF(x) →?xG(x))的前束范式。 解：原式??x(?F(x)∨G(x))→(?(?x)F(x) ∨ (?x)G(x)) ??(?x)(?F(x)∨G(x)) ∨(?(?x)F(x) ∨ (?x)G(x)) ? (?x)((F(x)∧? G(x)) ∨G(x)) ∨ (?x) ?F(x)
习题一 1.下列句子中,哪些是命题？在是命题的句子中,哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （1）中国有四大发明. 答：此命题是简单命题，其真值为 1. （2）5 是无理数. 答：此命题是简单命题，其真值为 1. （3）3 是素数或 4 是素数. 答：是命题，但不是简单命题，其真值为1. （4）2x+ <3 5 答：不是命题. （5）你去图书馆吗？答：不是命题. （6）2 与3 是偶数. 答：是命题，但不是简单命题，其真值为0. （7）刘红与魏新是同学. 答：此命题是简单命题，其真值还不知道. （8）这朵玫瑰花多美丽呀！答：不是命题. （9）吸烟请到吸烟室去！答：不是命题. （10）圆的面积等于半径的平方乘以π. 答：此命题是简单命题，其真值为 1. （11）只有6 是偶数，3 才能是2 的倍数. 答：是命题，但不是简单命题，其真值为0. （12）8 是偶数的充分必要条件是8 能被3 整除. 答：是命题，但不是简单命题，其真值为0. （13）2008 年元旦下大雪. 答：此命题是简单命题，其真值还不知道. 2.将上题中是简单命题的命题符号化. 解:（1）p：中国有四大发明. （2）p: 是无理数. （7）p:刘红与魏新是同学. （10）p:圆的面积等于半径的平方乘以π. （13）p:2008 年元旦下大雪. 3.写出下列各命题的否定式,并将原命题及其否定式都符号化,最后指出各否定式的真值. （1）5 是有理数. 答：否定式：5 是无理数. p：5 是有理数.q：5 是无理数.其否定式q 的真值 为1.
（2）25 不是无理数. 答：否定式：25 是有理数. p：25 不是无理数. q：25 是有理数. 其否定式q 的 真值为1. （3）2.5 是自然数. 答：否定式：2.5 不是自然数. p：2.5 是自然数. q：2.5 不是自然数. 其否定式q 的真值为1. （4）ln1 是整数. 答：否定式：ln1 不是整数. p：ln1 是整数. q：ln1 不是整数. 其否定式q 的真值为1. 4.将下列命题符号化，并指出真值. （1）2 与5 都是素数 答：p：2 是素数，q：5 是素数，符号化为p q∧ ，其真值为 1. （2）不但π是无理数，而且自然对数的底e 也是无理数. 答：p：π 是无理数，q：自然对数的底e 是无理数，符号化为p q∧ ，其真值为1. （3）虽然2 是最小的素数，但2 不是最小的自然数. 答：p：2 是最小的素数，q：2 是最小的自然数，符号化为p q∧? ，其真值为1. （4）3 是偶素数. 答：p：3 是素数，q：3 是偶数，符号化为p q∧ ，其真值为0. （5）4 既不是素数，也不是偶数. 答：p：4 是素数，q：4 是偶数，符号化为? ∧?p q，其真值为0. 5.将下列命题符号化，并指出真值. （1）2 或3 是偶数. （2）2 或4 是偶数. （3）3 或5 是偶数. （4）3 不是偶数或4 不是偶数. （5）3 不是素数或4 不是偶数. 答: p：2 是偶数，q：3 是偶数，r:3 是素数，s:4 是偶数, t:5 是偶数 (1)符号化: p q∨ ，其真值为1. (2)符号化：p r∨ ，其真值为1. (3)符号化：r t∨ ，其真值为0. (4)符号化：? ∨?q s，其真值为1. (5)符号化：? ∨?r s，其真值为0. 6.将下列命题符号化. （1）小丽只能从筐里拿一个苹果或一个梨. 答：p：小丽从筐里拿一个苹果，q：小丽从筐里拿一个梨，符号化为: p q∨ . （2）这学期，刘晓月只能选学英语或日语中的一门外语课.