华师 离散数学 作业

华东师范大学离散数学章炯民课后习题第6章答案p992.f：x?y。

对任意a?x，定义f(a)={f(x)|x?a}。

（1）证明f(a?b)=f(a)?f(b)；（3）举例说明f(a?b)≠f(a)?f(b)。

证明：（1）?y∈f(a?b)??x∈a?b，并使y=f(x)??x∈a或?x∈b，并使y=f(x)?y=f(x)∈f(a)或y=f(x)∈f(b)?y∈f(a)?f(b)?f(a?b)=f(a)?f(b)（2）举例：令f(x)＝x2,a={1，2}，b={1，-2}。

则f(a?b)={1}，而f(a)={1,4}f(b)={1,4}f(a)?f(b)={1,4}故，f(a?b)≠f(a)?f(b)基本正确。

少数学生出现函数值为一个数值而不是集合的错误4.f：x?y，下列命题是否成立？（1）f就是一对一的当且仅当对任一a,b?x，当f(a)=f(b)时，必存有a=b；（2）f 就是一对一的当且仅当对任一a,b?x，当f(a)≠f(b)时，必存有a≠b。

求解：（1）成立（2）不设立，如f(x)=x2,部分学生第（2）推论错误5.下图展示了五个关系的关系图。

问：这些关系中，哪些是函数？哪些是一对一的函数？哪些是到上的函数？哪些是一一对应？求解：1是函数，一对一，但不是到上的；2是函数，到上的，但不是一对一；3是函数，一一对应；4是函数；5不是函数。

正确9(1).f：x?y，g：y?z。

命题“f?g是一对一的当且仅当f和g都是一对一的”是否成立？解：不设立。

f是一对一的。

假设f不是一对一的,何不设f(a)=b,f(b)=b(a≠b)f?g(a)=g(f(a))=g(b),f?g(b)=g(f(b))=g(b)即f?g(a)=f?g(b),这与f?g是一对一的相矛盾。

但g不一定是一对一的。

反例:如f的论域{1,2}:f(1)=5,f(2)=6,g的论域{4,5,6}:g(4)=a,g(5)=a,g(6)=c,f就是一对一的,f?g也就是一对一的,但g不是一对一的部分学生推论错误。

离散数学第3版习题答案【篇一：华东师范大学离散数学章炯民课后习题第3章答案】xt>（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) 011. 将下列两个命题符号化，并分别用真值表和等值演算的方法证明所得到的那两个命题公式是等值的。

（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. 构造下列推理的形式证明：“今天下午没有出太阳并且今天比昨天冷。

Attention: 某些答案有问题的已用灰色标出，请大家注意(P123) 2，6，71. 6个学生：Alice 、Bob 、Carol 、Dean 、Santos 和tom ，其中，Alice 和Carol 不和，Dean 和Carol 不和，Santos 、Tom 和Alice 两两不和。

请给出表示这种情形的图模型。

2. 至少含一个顶点的C3的子图有多少个？答：9个。

单个顶点有三种，单条边有三种，两条边时有三种，共9个子图。

3. 证明：在顶点个数不小于2的简单无向图中，必有度数相同的顶点。

证明：假设简单图G 有n (n >2)个顶点，各顶点的度数均不相同，因为简单图△(G )≦n-1，所以度数列应为0，1，2，…，n-1。

其中的n-1度顶点应与其余所有顶点邻接，而这与G 中有0度顶点矛盾，故G 中必有度数相同的顶点。

4. 对哪些n 值来说下列图是偶图？a) Kn b) Cn c) Wn d) Qn答：a) K n 完全图 n =2时是偶图b)C n 圈图 n 为偶数时候为偶图c)W n 轮图 不是偶图d)Q n 立方图 n 为自然数时是偶图(P123) 4，*12，*补充1. 简单无向图G 有n 个顶点，n+1条边，证明G 中至少有一个顶点的度大于或等于3。

证明： 因为|E|= n+1,所以∑d(V)=2n+2 ，假设G 中所有顶点度数都小于3，则∑d(V) ≦2n ,矛盾。

得证。

2. 一天晚上张先生夫妇参加了一个聚会，参加聚会的人中还有另外三对夫妇，他们相互握了手。

假设没有人自己与自己握手，没有夫妻之间的握手，且同两个人握手不超过一次。

当其他人告诉张先生，他或她握了多少次手时，答案都不相同。

问张先生和太太分别握了几次手？ BobAlice Carol DeanSantostom答：因为当其他人告诉张先生，他或她握了多少手时，答案都不相同，所以除张先生外，其他人握手次数为0，1，2，3，4，5，6。

k4
k 4 ： ak 1 k 5 ： ak 3 k 6 ： ak 6 k 7 ： ak 10 k 8 ： ak 13 k 9 ： ak 15 k 10 ： ak 16
七.
(a).解：设 an 是长度为 n 的包含 3 个连续零的 01 串，则 2 an 是长度为 n 的不包含 3 个连
考虑顶点 a，b，d，e，f，g 其中<a,b>,<a,e>,<a,f> <g,b>,<g,f>,<g,e>(通过<g,h>,<h,e>相连) <d,b><d,e><d,f>（通过<d,c>,<c,f>相连) 则 a，b，d，e，f，g 构成 K 3,3 ，所以原图非平面。
n n
n
九. (a). ( p3 n p2 n p1n p0 )
3 2
(b). p0 (2)
3
n
(c). n ( p4 n p3n p2 n p1n p0 )2
4 3 2
n
十 1. 不存在，所有度的和为 21，是个奇数，所以不可能。 2. 不同构，左图有 2 个二度顶点，右图一个二度顶点都没。 3. 不是。u1 与 u2 相连，u1 与 u5 相连，但是 u2 与 u5 也相连。 4. u6 十一 1. m n 2 2. 4 十二
华东师范大学期末试卷（B）
2007—2008 学年第二学期
软件工程数学参考答案
一．
N x ： x 是自然数 x N x y N y y x
二． 1.自反性： a 2 0(a 0) ，所以 (a bi) R (a bi) 2.对称性： (a bi) R (c di) ac 0 (c di) R (a bi) 3.传递性： (a bi) R (c di) ac 0,

第一章命题逻辑1.1命题与命题联结词P6.T2.判断下列语句是否为命题，为什么？若是命题判断是原子命题还是复合命题，并把复合命题符号化，要求符号化到原子命题。

（1）他们明天或后天去百货公司。

（2）你能告诉我，我什么时候一定会死吗？你不能！（3）如果这个语句是命题，那么它是一个假命题。

（4）李刚和李春是兄弟。

（5）王海和李春在学习。

（6）只要努力学习，就一定能取得优异成绩。

（7）李春对李刚说：“今天天气真好呀！”（8）你知道这是个真命题还是假命题就请告诉我！（9）王海不是女孩子。

答案解⑴是复合命题。

设p：他们明天去百货公司；q：他们后天去百货公司。

命p∨。

题符号化为q⑵是疑问句，所以不是命题。

⑶是悖论，所以不是命题。

⑷是原子命题。

⑸是复合命题。

设p：王海在学习；q：李春在学习。

命题符号化为p∧q。

⑹是复合命题。

设p：你努力学习；q：你一定能取得优异成绩。

p→q。

⑺不是命题。

⑻不是命题⑼。

是复合命题。

设p：王海是女孩子。

命题符号化为：⌝p。

P7.T4.设p表示命题“天下大雨”，q表示命题“他乘公共汽车上班”，r表示命题“他骑自行车上班”。

请将下列命题符号化。

（1）如果天不下大雨，他乘坐公共汽车或者骑自行车上班。

（2）只要天下大雨，他就乘公共汽车上班。

（3）只要天下大雨，他才乘公共汽车上班。

（4）除非天下大雨，否则他不乘公共汽车上班。

答案解⑴⌝p→(q∨r)。

⑵p→q。

⑶q→p。

⑷q → p。

1.2命题公式及其分类P10.T4.构造下列公式的真值表，并据此说明它是重言式、矛盾式或者仅为可满足式。

（1）p ∨⌝（p ∧q ）。

（2）（p ∧q ）∧⌝（p ∨q ）。

（3）（p →q ）↔（⌝p ↔q ）。

（4）（（p →q ）∧（q →r ））→（p →r ）。

答案解 ⑴设)(q p p A ∧⌝∨=，其真值表如表2-1所示：故)(q p p A ∧⌝∨=为重言式。

⑵设A =(p ∧q )∧⌝(p ∨q )，其真值表如表2-2所示：表2-2故∧∧⌝∨为矛盾式。

华师《离散数学》在线作业一、单选题（共50 道试题，共100 分。

）1.题面见图片：A. AB. BC. CD. D正确答案：D2. 无向图G是欧拉图，当且仅当( )。

A. G的所有结点的度数全为偶数B. G的所有结点的度数全为奇数C. G连通且所有结点的度数全为偶数D. G连通且所有结点的度数全为奇数正确答案：C3.题面见图片:A.AB. BC. CD. D正确答案：D4. 平面连通图G有4个顶点，5条边，则其面数为()。

A. 3B. 4C. 5D. 不能确定正确答案：A5. 下面说法中正确的是（）。

A. 所有可数集合都是等势的B. 任何集合都有与其等势的真子集C. 有些无限集合没有可数子集D. 有理数集合是不可数集合6. 下列集合不是连接词极小全功能集的为()。

A. {?,∧,∨}B. {?,→}C. {↓}D. {↑}正确答案：A7. 设R是实数集合，在上定义二元运算*：a，b↔R，a*b=a+b-ab，则下面的论断中正确的是（）。

A. 0是*的零元B. 1是*的幺元C. 0是*的幺元D. *没有等幂元正确答案：C8.题面见图片：A. AB. BC. CD. D正确答案：C9.题面见图片：A. AB. BC. CD. D正确答案：D10.题面见图片：A. AB. BC.CD. D正确答案：B11. 图的构成要素是()。

A. 结点B. 边C. 结点与边D. 结点、变和面12.题面见图片：A. AB. BC. CD. D正确答案：B13. 设集合A={1,2,3,…,10}，下面定义的哪种运算关于集合A是不封闭的？（）A. x*y=max{x,y}B. x*y=min{x,y}C. x*y=GCD(x,y)，即x,y的最大公约数D. x*y=LCM(x,y)，即x,y的最小公倍数正确答案：D14. 若图G有一条开路经过图中每个结点恰好一次,则G()。

A. 有一条欧拉路径B. 是欧拉图C. 有一条哈密顿通路D. 是哈密顿图正确答案：C15.题面见图片：A. AB. BC. CD. D正确答案：C16.题面见图片：A. AB. BC. CD. D正确答案：A17.题面见图片：A. AB. BC. CD. D18. G是一棵根树，则（）。

2、
这个很容易，但是需要话一个图，有4个二度节点，树叶有5片，所以一个三度节点都木有。
要算也简单，叶子数=总度数-节点数+1设：三度节点个数为x
即：2*4+x*3-4-x+1=5
解得x=0
∴一个三度节点都木有
3、B∪~((~A∪B)∩A)=B∪~((~A∩A)∪(B∩A))=B∪~(B∩A)=B∪(~B∪~A)=B∪~B∪~A=U∪~B=U
所以4-x是x的幺元
综上所述：<Z,☉>是群
5、证明：(P→Q)∧(Q→P)<=>(﹁P∨Q)∧(﹁Q∨P)<=>((﹁P∨Q)∧﹁Q)∨((﹁P∨Q)∧P)<=>
((﹁P∧﹁Q)∨(Q∧﹁Q))∨((﹁P∧P)∨(Q∧P))<=>(﹁P∧﹁Q)∨(Q∧P)<=>
﹁(P∨Q)∨(Q∧P)<=>(P∨Q)→(Q∧P)
4、
证明：如果x，y∈Z，则x☉y=x+y-2∈Z
∴<Z,+y-2)+z-2=x+(y+z-2)-2=x+(y☉z)-2=x☉(y☉z)
∴<Z,☉>是可结合的。
对于任意x∈Z
x☉2=x+2-2=x
2☉x=2+x-2=x
∴2是<Z,☉>的幺元
x☉(4-x)=x+(4-x)-2=2=幺元
三项比赛都参加的有4这个很容易但是需要话一个图有4个二度节点树叶有5片所以一个三度节点都木有
1、
足球：|A|=28篮球：|B|=29排球：|C|=26 |A∩B|=7 |B∩C|=9 |A∩C|=11
|A|+|B|+|C|-|A∩B|-|B∩C|-|A∩C|+|A∩B∩C|=|A∪B∪C|=60

华南师范大学数学基础期末考试计算题答案
1、设树T有2个2度结点，1个3度结点，3个4度结点，其余都是树叶，求有多少片树叶？
握手定理：设树叶数为x，2*2+1*3+3*4+x = (2+1+3+x-1)*2，所以x=9，答：共有9片树叶。

（结点与分支的关系）
2、设树T有6片树叶，3个2度结点，其余都是4度结点，求4度结点的个数。

解：设4度结点个数为x，6+3*2+4*x = (6+3+x-1)*2，所以x=2，答：2个4度结点。

3、设树T有3个3度结点，7片树叶，其余都是4度结点，问T中有多少4度结点？
7+3*3+4x=2(7+3+x-1)，x=1
4、某共有60人，其中参加足球比赛的有25人，有26人参加篮球比赛，26人参加排球比赛，7人既踢足球又打篮球，9人既打篮球又打排球，11人既打排球又踢足球，求同时参加三种比赛的人数
5、某共有60人，其中参加足球比赛的有25人，有26人参加篮球比赛，26人参加排球比赛，9人既踢足球又打篮球，11人既打篮球又打排球，9人既打排球又踢足球，求仅仅参加足球比赛的人数
6、在1到200的所有整数中，能且只能被2、3、5之一整除的数有多少个？。

离散数学大作业答案2022-2022学年第一学期期末《离散数学》大作业一、简要回答下列问题：（每小题3分，共30分）1．请给出集合的结合率。

答：结合律(AUB)UC=AU(BUC)某∈(AUB)UC，即某∈AUB或某∈C即某∈A或某∈B或某∈C即某∈A或某∈B∪C即某∈AU(BUC)说明(AUB)UC包含于AU(BUC)同理可证AU(BUC)包含于(AUB)UC所以(AUB)UC=AU(BUC) 2．请给出一个集合A，并给出A上既不具有自反性，又不具有反自反性的关系。

3．设A={1，2}，问A上共有多少个不同的对称关系？答：不同的对称关系有：8种R=ΦR={<1,1>}R={<2,2>}R={<1,1>,<2,2>}R={<1,2>,<2,1>}R={<1,1>,<1,2>,<2,1>}R={<1,2>,<2,1>,<2,2>}R={<1,1>,<1,2>,<2,1>,<2,2>}4．设A={1，2，3，4，5，6}，R是A上的整除关系，M={2,3}，求M 的上界，下界。

5．关于P，Q，R请给出使极小项m0，m4为真的解释。

答：m0=┐p∧┐q∧┐rm4=p∧┐q∧┐r6．什么是图中的简单路？请举一例。

答：图的通路中，所有边e1,e2,…,ek互不相同，称为简单通路。

7．什么是交换群，请举一例。

答：如果群〈G，某〉中的运算某是可以交换的，则称该群为可交换群，或称阿贝尔群。

如〈I，+〉是交换群。

8．什么是群中右模H合同关系？答：设G是群，H是G的子群，a,b∈G，若有h∈H，使得a=bh，则称a合同于b（右模H），记为a≡b（右modH）。

9．什么是有壹环？请举一例。

答：幺元：如果A中的一个元素e，它既是左幺元又是右幺元，则称e为A中关于运算☆的幺元。

华南师范大学网络教育离散数学期末考试题及答案一．单选题(本题总分20分，每小题2分)1．以下语句是命题的是( D )。

A．你喜欢唱歌吗？ B．x+y=20C．给我一杯水吧！ D．若7+818，则三角形有4条边。

2．A={a,b}，B={c,d}，A和B的笛卡尔积A×B是( C )。

A． {<a,c>, <a,d>} B．{}C．{<a,c>, <b,d>, <b,c>, <a,d>} D．{<a,c>, <a,d> }3．设A={a,{a}}，下列命题错误的是( B )。

A．{a}P(A) B．{a}P(A)C．{{a}}P(A) D．{{a}}P(A)4．设A={1, 2, 3, 4}，下列( D )不是A的划分。

A．{{1}, {2}, {3}, {4}} B．{{1, 2}, {3}, {4}}C．{{1, 2}, {3, 4}} D．{, {1, 2, 3}, {4}}5．下列式子( D )不正确。

A．{} B．{}{{}} C．{} D．{}{{}}6．假设论域是整数集合，下列自然语言的符号化表示中，( C )的值是假的。

A．xyG(x,y)，其中G(x,y)表示xy=xB．yxH(x,y)，其中H(x,y)表示xy=xC．yxF(x,y)，其中F(x,y)表示x+y=10D．xyM(x,y)，其中M(x,y)表示x+y=107．以下联结词的集合( D )不是完备集。

A．{, , , , } B．{, , } C．{, } D．{, }8．下面哪个谓词公式是前束范式( C )。

A．x(A(x)B(x)) B．xA(x) xB(x)C．xx (A(x) B(x)) D．xx (A(x) B(x))9．以下式子错误的是( D )。

A．xA(x)xA(x) B．x(A(x)B(x)) xA(x) x B(x)C．x(A(x)B(x)) xA(x)x B(x) D．x(A(x)B(x)) xA(x)x B(x) 10．以下命题公式是重言式的是( D )。

作业1．第1题您的答案：答：利用集合设集合A，B，C分别表示从1到200的整数中能被2,3,5整除的整数集，则从1到200的整数中能被2整除的集合含有200/2=100，也即集合A中有100个元素；从1到200的整数中能被3整除的集合含有200/3=66.67，也即集合B中有66个元素；从1到200的整数中能被5整除的集合含有200/5=40，也即集合C中有40个元素；从1到200的整数中能被2,3整除的集合含有200/（2*3）=33.33，也即集合AB（表示集合A与B的交集）中有33个元素；从1到200的整数中能被2,5整除的集合含有200/（2*5）=20，也即集合AC（表示集合A与C的交集）中有20个元素；从1到200的整数中能被3,5整除的集合含有200/（3*5）=13.33，也即集合BC（表示集合B与C的交集）中有13个元素；从1到200的整数中能被2,3,5整除的集合含有200/（2*3*5）=6.67，也即集合ABC（表示集合A、B、C的交集）中有6个元素；所以，从1到200的整数中能被2,3,5中任意一个数整除的整数个数为A+B+C-AB-AC-BC+ABC=100+66+40-33-20-13+6=146题目分数：30此题得分：20.02．第2题您的答案：答：设3度结点的个数为x,则 1*5+4*2+3+x=2(5+4+x-1) 解此方程得 x=3题目分数：10此题得分：10.03．第3题您的答案：答：A-(B∪C)=(A-B)∩(A-C) =A∩2(B∪C) =A∩(2B∩2C) =A∩2B∩A∩2C （补一个A等式仍成立） =(A-B)∩(A-C) （其中2代表求补集）题目分数：20此题得分：20.04．第4题您的答案：证明：∵ a∧b是a，b的最大下界，a∨c是a，c的最小上界，∴ a∧b<=a ，a<=a∨c 再由关系《的传递性得a∧b<= a∨c 同理，∵ c∧d是c，d的最大下界，a∨c是a，c的最小上界，∴ c∧d<=c ，c<= a∨c 再由关系<= 的传递性得c∧d <= a∨c 由a∧b<=a∨c，c∧d<=a∨c 可知a∨c是a∧b，c∧d的上界，而（a∧b）∨（c∧d）是a∧b，c∧d的最小上界，∴（a∧b）∨（c∧d）<=a∨c。

m为奇数 m 2 或 ，有 Euler Path。 n为奇数 n 2
十二、 Proof： 假设每个连通分支含有 ri 个区域， ei 条边和 vi 个顶点 (i 1, 2,..., k ) ，那么，根据 Euler 定 理，有 ri ei vi 2 ，
ri ei vi 2k
i 1 k i 1 i 1
k
k
k
(r 1) 1 k 1 e v 2k ，
i 1 i
即 r k 1 e v 2k ， 那么： r e v k 1
C (100,
八、
100 k ) 2
n2
（a） an an 1 an 2 2 （b） a0 0, a1 0
(n 1)
九、 Solution： a) 相应的齐次递推关系的特征方程为 r 2 ， 所以相应的齐次递推关系的通解为： an
( p)
1n ，又 1 不是相应的齐次 1 2n ，而 2n 2 2n 2
[ a ] [b] . It follows that [ a ] [b] since [ a ] is nonempty.
Next, we will show that (3) implies (1). Suppose that [ a ] [b] . Then there is an element c with c [ a ] and c [b] . In other words, aRc and bRc . By the symmetric property, cRb . Then by transitivity, since aRc and cRb , we have

第一章
1. 假定 A 是 ECNU 二年级的学生集合， B 是 ECNU必须学离散数学的学生的集合。请用 A 和 B 表示 ECNU 不必学习离散数学的二年级的学生的集合。
2. 试求： (1) P( ) (2) P(P( )) (3) P(P(P( )))
3. 在 1 200 的正整数中，能被 3 或 5 整除，但不能被 15 整除的正整数共有多少个？ 能被 5 整除的有 40 个， 能被 15 整除的有 13 个， ∴能被 3 或 5 整除，但不能被 15 整除的正整数共有
第十章
1. 求初值问题的通项公式： an=10a n-1-25an-2； a0=-7 ， a1=15。 解： 特征方程： r2-10r+25=0 ，特征根： r2=r 1=5 通解： an=( +βn)5n 由 a0= 50= =-7 和 a1= (-7+ β)51 =15解得： =-7 ， β=10 初值问题的解： an=(-7+10n)2 n
Fortran 语言， 345 人选修了 JAVA ，876 人选修了 C 语言和 Fortran 语言， 231 人选修 了 Fortran 和 JAVA， 290 人选修了 C 和 JAVA ， 189 个学生同时选了 C 、Fortran 和 JAVA。问没有选这 3 门程序设计语言课中的任何一门的学生有多少个？
的方法数，求 {ar} 的生成函数。
第六章
1. f： X Y ，下列命题是否成立？ （ 1） f 是一对一的当且仅当对任意 a,b X ，当 f(a)=f(b) 时，必有 a=b ； （ 2） f 是一对一的当且仅当对任意 a,b X ，当 f(a) ≠f(b时) ，必有 a≠ｂ。
2. 下图展示了五个关系的关系图。 问： 这些关系中， 哪些是函数？哪些是一对一的函数？ 哪些是到上的函数？哪些是一 一对应 ？

6
特异元素：单位元、零元
定义9.5 设◦为S上的二元运算, (1) 如果存在el (或er)S，使得对任意 x∈S 都有 el◦x = x (或 x◦er = x)， 则称el (或er)是S中关于◦运算的左(或右)单位元. 若e∈S关于◦运算既是左单位元又是右单位元，则称e为S上 关于◦运算的单位元. 单位元也叫做幺元. (2) 如果存在 l (或 r)∈S，使得对任意 x∈S 都有 l ◦x = l (或 x◦ r = r)， 则称 l (或 r)是S 中关于◦运算的左(或右)零元. 若 ∈S 关于◦运算既是左零元又是右零元，则称为S上关 于运算◦的零元.
27
循环群的生成元
定理10.13 设G=<a>是循环群. (1) 若G是无限循环群，则G只有两个生成元，即a和a1. (2) 若G是 n 阶循环群，则G含有(n)个生成元. 对于任何小 于n且与 n 互质的数r∈{0,1,…,n-1}, ar是G的生成元.
(n)成为欧拉函数，例如 n=12，小于或等于12且与12互素的
24
Lagrange定理
定理10.12 （Lagrange）设G是有限群，H是G的子群，则 |G| = |H|· [G:H] 其中[G:H] 是H在G中的不同右陪集(或左陪集) 数，称为H在 G 中的指数. 推论1 设G是n阶群，则a∈G，|a|是n的因子，且有an = e. 推论2 对阶为素数的群G，必存在a∈G使得G = <a>.
例 5 设G是群，a,b∈G是有限阶元. 证明 (1) |b1ab| = |a| (2) |ab| = |ba|
18
10.2 子群与群的陪集分解
定义10.5 设G是群，H是G的非空子集， (1) 如果H关于G中的运算构成群，则称H是G的子群, 记作 H≤G. (2) 若H是G的子群，且HG，则称H是G的真子群，记作 H<G. 例如 nZ (n是自然数) 是整数加群<Z,+> 的子群. 当n≠1时, nZ是Z的真子群.

华师《离散数学》在线作业-0001
无向完全图K3的不同构的生成子图有（）个。

A:6
B:5
C:4
D:3
参考选项：D
若图G有一条开路经过图中每个结点恰好一次,则G()。

A:有一条欧拉路径
B:是欧拉图
C:有一条哈密顿通路
D:是哈密顿图
参考选项：C
相邻矩阵具有对称性的图一定是( )。

A:有向图
B:无向图
C:混合图
D:简单图
参考选项：B
题面见图片：
A:选择图中A选项
B:选择图中B选项
C:选择图中C选项
D:选择图中D选项
参考选项：A
下列集合不是连接词极小全功能集的为()。

A:{?,∧,∨}
B:{?,→}
C:{↓}
D:{↑}
参考选项：A
平面连通图G有4个顶点，5条边，则其面数为()。

A:3
B:4
C:5
D:不能确定
参考选项：A
1。

第一章 习题解答
• 1-4 (8) c)
– (A∧B∧C)∨(┐A∧B∧C)
• (A∨┐A) ∧(B∧C) • T∧(B∧C) • B∧C
ቤተ መጻሕፍቲ ባይዱ
第一章 习题解答
• • 1-5 (1) a) 证明：
– – – – – – – – (P∧(P→Q))→Q (P∧(┐P∨Q))→Q (P∧┐P)∨(P∧Q)→Q (P∧Q)→Q ┐(P∧Q)∨Q ┐P∨┐Q∨Q ┐P∨T T
第一章 习题解答
• • 1-6 (3) c) 证明：
• • • • • • P→(┐P→Q) ┐P∨(P∨Q) T ┐P∨P (┐P↑┐P)↑(P↑P) P↑(P↑P)
P26(3) P26(1)
第一章 习题解答
• • 1-6 (3) c) 证明：
• • • • • • P→(┐P→Q) ┐P∨(P∨Q) T ┐P∨P (┐P↓P) ↓ (┐P↓P) ((P↓P)↓P)↓((P↓P)↓P)
习题2-5
(7) – 证明：(x)( y)(P(x)→Q(y)) – (x)( y)( ┐P(x) ∨Q(y)) – (x) ┐P(x) ∨( y)Q(y) – ┐(x)P(x) ∨( y)Q(y) – ( x)P(x)→(y)Q(y)
习题2-6
(1) b) – (x)(┐((y)P(x,y))→((z)Q(z)→R(x))) – (x)((y)P(x,y)∨((z)Q(z)→R(x))) – (x)((y)P(x,y) ∨(┐(z)Q(z) ∨R(x))) – (x)((y)P(x,y) ∨((z)┐Q(z) ∨R(x))) – (x) (y) (z) ( P(x,y) ∨┐Q(z) ∨R(x))
• • • • • (Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q 设R→Q为F，则R为T，且Q为F，又P∧┐P为F 所以Q→(P∧┐P)为T，R→(P∧┐P)为F 所以R→(R→(P∧┐P))为F，所以 (Q→(P∧┐P))→(R→(R→(P∧┐P)))为F 即(Q→(P∧┐P))→(R→(R→(P∧┐P)))R→Q成 立。

填空题
第1题 (4) 分
打开可视化编辑器输入内容
第2题 (4) 分
打开可视化编辑器输入内容
第3题 (4) 分
9阶无向完全图的边数为______________________ .
打开可视化编辑器输入内容
第4题 (4) 分
8阶无向完全图的边数为__________________________ .
打开可视化编辑器输入内容
第5题 (4) 分
打开可视化编辑器输入内容
第6题 (4) 分
打开可视化编辑器输入内容
第7题 (4) 分
打开可视化编辑器输入内容
第8题 (4) 分
打开可视化编辑器输入内容
第9题 (4) 分
打开可视化编辑器输入内容
第10题 (4) 分
打开可视化编辑器输入内容计算题
第11题 (10) 分
打开可视化编辑器输入内容
第12题 (10) 分
打开可视化编辑器输入内容证明题
第13题 (10) 分
打开可视化编辑器输入内容
第14题 (10) 分
打开可视化编辑器输入内容问答题
第15题 (10) 分
打开可视化编辑器输入内容
第16题 (10) 分
打开可视化编辑器输入内容。