离散数学作业标准答案
离散数学作业
一、选择题
1、下列语句中哪个是真命题（C ）。 A ．我正在说谎。
B ．如果1+2=3，那么雪是黑色的。
C ．如果1+2=5，那么雪是白色的。
D ．严禁吸烟！
2、设命题公式))((r q p p G →∧→=，则G 是（ C ）。
A. 恒假的
B. 恒真的
C. 可满足的
D. 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x （ C ）。 A ．是自由变元但不是约束变元 B ．既不是自由变元又不是约束变元 C ．既是自由变元又是约束变元 D ．是约束变元但不是自由变元
4、设A={1，2，3}，则下列关系R 不是等价关系的是（C ）
A ．R={<1，1>，<2，2>，<3，3>}
B ．R={<1，1>，<2，2>，<3，3>，<2，3>，<3，2>}
C ．R={<1，1>，<2，2>，<3，3>，<1，4>}
D ．R={<1，1>，<2，2>，<3，3>，<1，2>，<1，3>，<2，3>，<2，1>，
<3，1>，<3，2>} 5、设R 为实数集，映射σ=R →R ，σ（x ）= -x 2+2x-1，则σ是（ D ）。 A ．单射而非满射 B ．满射而非单射 C ．双射 D ．既不是单射，也不是满射 6、下列二元运算在所给的集合上不封闭的是（ D ） A. S={2x-1|x ∈Z +}，S 关于普通的乘法运算 B. S={0，1}，S 关于普通的乘法运算 C. 整数集合Z 和普通的减法运算
D. S={x | x=2n ，n ∈Z +}，S 关于普通的加法运算
7、*运算如下表所示，哪个能使（{a,b}，*）成为含幺元半群（ D ）
b a b b a a b a * b b b a a a b a * a a b a a a b a * a b b b a a b a *
A B C D
8、下列图中是欧拉图的是（ A ）。
A B C D 9、下列各组数中,能构成无向图的度数列是（ D ） A ．1,1,1,2,4 B ．1,2,3,4,5 C ．0,1,0,2,4 D ．1,2,3,3,5
10、一棵树有2个4度顶点，3个3度顶点，其余都是树叶，则该树中树叶的个
数是（ B ）
A .8 B.9 C. 10 D. 11 11、“所有的人都是要死的。苏格拉底是人，所以苏格拉底是要死的。”则该句话（
B ）
A ．不是命题
B ．是真命题
C ．是假命题
D ．是悖论
12、一个公式在等价意义下，下面哪个写法是唯一的（ C ）。 A ．析取范式 B ．合取范式 C ．主析取范式 D ．以上答案都不对 13、设论域E={a, b}，且P(a,a)=1 P(a,b)=0 P(b,a)=1 P(b,b)=0 则在下列公式中真值为1的是（ D ）
A.?x ?yP(x,y)
B.?x ?yP(x,y)
C.?xP(x,x)
D. ?x ?yP(x,y) 14、设集合A={1, 2, 3 }，A 上的关系R={<1, 1 >,<2, 2 > }，则R 不具有（ A ）性质。
A.自反性
B.对称性
C.传递性
D. 反对称性 15、设集合A={a,b,c,d},B={1,2,3,4},则从A 到B 的函数
f={
C. 满射函数
D. 即不是满射又是不是单射函数 16、下面给出的一阶逻辑等值式中，（ B ）是错的。 A.);()())()((x xB x xA x B x A x ?∨??∨? B.);()())()((x xB x xA x B x A x ?∨??∨? C.));(()(x A x x xA ?????
D.)).(()(x B A x x xB A →???→
17、下列各代数系统中，不含零元素的是 （ C ）
A ．>*<),(R M n ， )(R M n 是全体n 阶实矩阵集合，*是矩阵乘法运算。
B ．> C ．>+<,R ，R 是有理数集，+是数的加法运算。 D ．><ο,I ，I 是整数集，ο是数的乘法运算。 18、 设图G 是有6个顶点的连通图，总度数为20，则从G 中删去（ B ）边 后使之变成树。 A .10 B. 5 C. 3 D. 2 19、在具有n 个结点的无向连通图中，（ B ）。 A. 恰好有n 条边 B. 恰好有n-1条边 C. 最多有n 条边 D. 至少有n 条边 20、下列图是欧拉图的是（ C ） 21. 半群、群及独异点的关系是………………………………………………（ D ） （A ）{群}?{独异点}?{半群} （B ）{独异点}?{半群}?{群} （C ）{独异点}?{群}?{半群} （D ）{半群}?{独异点}?{群} 22. 设集合A={1, 2, 3 }，A 上的关系R={<1, 1 >,<2, 2 >,<3,3>}，则R 不具有下列性质中的……………………………………………………………… （D ） (A) 自反性 (B) 对称性 (C) 传递性 (D) 反自反性 23. 以下图中哪个是欧拉图…………………………………………… （D ） 24．*运算如下表所示，哪个能使<{a,b }，*>成为含幺元半群…………（D ） b a b b a a b a * b b b a a a b a * a a b a a a b a * a b b b a a b a * (A) (B) (C) (D) 25. 设P：张三可以做这件事，Q：李四可以做这件事。命题“张三或李四可以做这件事”符号化为…………………………………………………（A） (A) Q (~ ~Q P∨ ~ P∨ (B) Q P~ ∨ (C) Q P? (D) ) 26. 27. G是连通的平面图，有5个顶点，6个面，则G的边数为……………（C） (A) 6 (B) 5 (C) 9 (D) 11 28.下列句子中是命题的有……………………………………………（D） (A) 上课时请不要说话! (B) 我在说谎.（C）你吃饭了吗？（D）上海是中国的首都. 29. 以下命题公式中，为永假式的是( C ) (A) p→(p∨q∨r) (B) (p→┐p)→┐p （C）┐(q→q)∧p （D）┐(q∨┐p)→(p∧┐p) 30. 图的生成子图为……………………………（C） (A) (B) (C) (D) 31.如下图所示的有界格中，元素b的补元是( D ) （A）a （B）0 （C）c （D）d 32. 设A={a,b,c}，则下列是集合A的划分的是( D ) （A） {{b,c},{c}} （B）{{a,b},{a,c}} （C）{{a,b},c} （D）{{a},{b,c}} 33. 整数集合Z上“＜”关系的自反闭包是关系（D） (A) = (B)≠ (C)＞ (D) ≤ 34. 下列式子正确的是 ( B ) (A) ?∈? (B)??? (C){?}?? (D){?}∈? 35.设i是虚数，·是复数乘法运算，则G=<{1,-1,i,-i},·>是群，下列是G的 子群是( A ) （A ）<{1},·> （B ）〈{-1},·〉 （C ）〈{i},·〉 （D ）〈{-i},·〉 36.集合A={1，2}的幂集P(A)的基数是…………………………………………（ D ） （A ） 0 （B ） 1 （C ） 2 （D ） 4 37. 下列哪个联结词运算不可交换？………………………………………（A ） (A) → (B) ? (C) ∨ (D) ∧ 38. 设集合A={1，2，3，…，10},下列定义的哪种运算关于集合A 是不封闭的 (D ) (A) x*y=max{x,y} (B) x*y=(x,y) 即x,y 的最大公约数 (C) x*y=min{x,y} (D) x*y=[x,y] 即x,y 的最小公倍数 39.设R 为实数集，函数f ：R →R ，f(x)=2x ，则f 是（ B ） A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 40. 若是一个代数系统,且满足结合律,则必为…………………（A ） (A) 半群 (B) 独异点 (C) 群 (D) 交换群 41. 设R 是A 上的等价关系,即R 是……………………………………………（D ） （A ）反自反的,对称的，传递的 （B ）自反的,反对称的, 传递的 （C ）反自反的,反对称的,传递的 （D ） 自反的,对称的,传递的 42．下列哪一组命题公式是等价的……………………………………………（B ） (A) Q P ~~∧，Q P ∨ (B) )(A B A →→，)~(~B A A →→ (C) )(Q P Q ∨→，)(~Q P Q ∨∧ (D) )(~B A A ∧∨，B 43.设S={0,1},则S ……………………………………………………………（A ） （A ）在普通乘法下封闭，在普通加法下不封闭; （B ）在普通加法和乘法下都封闭； （C ）在普通加法下封闭，在普通乘法下不封闭； （D ）在普通加法和乘法下都不封闭； 44. 下面谓词公式是前束范式的是 （ A ） A. ))(),((z A y x B z y x →??? B. ),((y x B y x ??? C. ))(),((z A y x B z y x ∧???? D. ))(),((y yB y x B x ?→? 45. 整数集合Z 上“＜”关系的自反闭包是关系（D ） (A)= (B)≠ (C)＞ (D)≤ 11.下列图既是欧拉图,又是哈密顿图的是………………………………（C ） 46. 设A={a,b,c}，A 上二元关系R={〈a,a 〉，〈b,b 〉,〈a,c 〉}，则关系R 的对称闭包S(R)是( C ) (A) R ∪IA (B) R (C) R ∪{〈c,a 〉} (D) R ∩IA 47. 下列式子正确的是( B ) (A) ?∈? (B)??? (C) {?}?? (D) {?}∈? 48. 下列句子是命题的是( C ) (A) 水开了吗? (B) 这朵花多好看呀！ (C) 2是常数。 (D)我正在说谎 49. 函数B A f →:可逆的充要条件是 （ D ） (A) A=B (B)A 与B 有相同的基数 (C)f 为满射 (D)f 为双射 二、填空题 1、公式(P ∧Q)→(R ∨S)真值表中共有 16 种真值指派。 2、设A(x):x 是运动员,B(x):x 是强壮的.命题“没有一个运动员不是强壮的”可符号化为 。 3、 是公式)(),(y yG x y xF ?→?的前束范式。 4、设集合A={1,2,3}上两个二元关系为R 1={＜1,3＞，＜2,1＞，＜3,2＞} 和 R 2={＜1,2＞，＜2,3＞，＜3,1＞}，则 R 1ο R 2= , =)(1R t 。 5、 集合Z m ={[0],[1],[2]，…，[m-1]}，在Z m 上定义运算+m 为：对任意的[i]，[j]∈Z m 有：[i]+m [j]=[（i+j ）（modm ）]，则 (A) (B) (C) (D) [i]∈Z m 的逆元是 [m-i] 。 6、无向图G 如图1所示，则G 的点连通度为 1 。 图1 图2 7、有向图D 如图2所示，则有向图D 的邻接矩阵A= ， D 中长度为2的回路有 2 条。 8、设p ：1+1=5，q ：明天是阴天。则命题“只要1+1=5，那么明天是阴天”可符 号化为________ _，其真值为________ 1 _。 9、设x x F :)(是兔子，()y y G :是乌龟，x y x H :),(比y 跑得快，则“并不是所有 的兔子都比乌龟跑得快。”可符号化为 10、 设有向图D 的邻接矩阵A(D)=? ? ??? ???? ???0100 10000100 0121 ,则长度为2的通路有 10 条. 11、设4 44 { },3,2,1,0{4≥+-+<++=⊕=y x y x y x y x y x Z ，则),(4⊕Z 的生成元 是 1 或 3 。 12、具有16个结点的完全无向图其边数一定为 120 条。 13、设集合}24,12,8,6,4,3,2{=A ，R 为A 上的整除关系，集合A 中的极大元是 24 ；极小元2，3； 14、整数加群的幺元是_ 0___。 15若A ={1,2,3 },},min{,,y x y x A y x =*∈?,则*的运算表为 16.设A ={a,{a}}, A 的幂集P (A )是 。 17.设G 是n 阶无向完全图,则该图的边数为 。 18.在一棵根树中，仅有一个结点的入度为 0_，称为树根，其余结点的入度 均为 1。 19.设A、B是两个集合，其中A={a,b,c}，B={ 1，2}，则A× B= . 20. 设个体域A={a,b},公式) xP? ∧ ?在A中消去量词后应是 x xS ) (x ( 21. 设M(x):x是人，D(x):x是要死的，则命题“所有的人都是要死的”可符号化为__ ____,其中量词的辖域是___ __ K 22. 画出完全图 5 23. 设A={a,b,c},则A×A中的元素有9个。 24. 设集合A={1,2,3 ,4},R为A上的一个二元关系，R={<1,1>,<1,2>, <2,1>,<3,3>}则R的关系矩阵为 . 25. 设G是m阶有向完全图,则该图的边数为m(m-1) 26. 设P(x)：x非常聪明；Q(x):x非常能干；a：小李；则命题“小李非常聪明和能干”的为谓词表达式为_______。 27. 设A，B是两个集合，A={1, 2, 3, 4}，B={2, 3, 5}，则A⊕B={1.4.5}. 28. 公式A→(?x)B(x)的前束范式为____________________。 29. 一个简单连通无向图有n个节点，它的边数至少有 n-1条。 30. 画出完全图K3,3 三、计算题 1、求公式r (的主析取范式和主合取范式。 →) p? q 解：方法一（等值演算法） →) p? ( q r (q ( p → q r→ p)) → ∧ ?) → ) ((r ∧ ? ∨ ∨ ∨ ? ? p? ? ∨ ) ) (( ) q ( ) r (r p q ? ∨ ∨ ∧ ∧ p? ? ? ∨ q ( ) ) ) ((r p r q ∨ ? ∧ ∨ ? p∧ ∧ ? ∧ ? (r ( ) ( ) ) q r p r q )()()()(r q p r q p r q p r q p ∧∧∨∧?∧?∨∧∧?∨?∧?∧?7431m m m m ∨∨∨? 方法二（真值表法） 根据真值表可以得到主析取范式为：7431m m m m ∨∨∨ 2、列出命题公式（p p q p ?→→))(的真值表。 3、设集合A={ }3,2,1，R 为A 上的二元关系，R={＜1,2＞＜3,1＞,＜2,3＞} ，求R 2 ，)(R r ，)(R s ，)(R t 的集合表达式。 解：因为R={<1,2>,<2,3>,<3,1>},所以 R 2={<1,3>,<2,1>,<3,2>} r(R)={<1,1>,<2,2>,<3,3>,<1,2>,<2,3>,<3,1>} s(R)={<1,2>,<2,1>,<2,3>,<3,2>,<3,1>,<1,3>} t(R)=E A 4、在偏序集 1 3 6 4 10 11 21 7 8 36 157 求集合D={2,3,4,6}的极大元，极小元，最大元，最小元，上界，下界,最小上界和最大下界。 解： 极大元：4，6；极小元：2，3； 最大元：无；最小元：无； 上界：12；下界1： 最小上界：12;最大下界:1 5、求带权为1, 3, 6, 7,8,11的最优二叉树,编一个最佳2元前缀码，并求其权数. 解：最优二叉树如下图所示： 编码： 1：0000 ；3：0001 ；6：001； 7：10； 8：11； 11：01 最小生成树的权数为其权W(T)=(1+3)*4+6*3+(11+7+8)*12=86 6、用Kruskal 算法求下列权图的最小生成树,并求最小生成树的权数,要求写出解的过程. 解: 取数的由小到大的排列为1＜2＜3＜4＜5＜7＜9 A A C 2 B 最小生成树如图所示： 最小生成树的权数为其权W(T)=12 7、设A={a,b,c,d},R={ 传递闭包。 8、设G=＜a＞是10阶循环群，求出G的所有子群。 解：因为10的正因子是1,2,5，10 所以 G的子群有4个， 分别是 9、（1）在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶？（2）画出两棵非同构的满足（1）中顶点度数的无向树T1和T2。 解：（1）设树有n个顶点，则有n-6片树叶 根据握手定理可知 )1 (2 )6 ( 3 4 2 2- = - + ? + ?n n 于是n=12 因此有6片树叶。 (2)两棵非同构的树为 T 1 T 2 10、A、B、C、D四个人中要派两个人出差，需满足如下条件： （1）若A去，则C和D中要去一人； （2）B和C不能都去； （3）C去则D要留下。 问有几种派法？如何派？ 解：用A、B、C、D分别表示A去，B去，C去，D去出差，则命题符号化如下： （1）A →（C ⊙D ）（⊙表示异或，可用其它符号） （2）（B ∧┐C ）∨（┐B ∧C ） （3）C →┐D 出差的派法要同时满足上述三个条件，故 G= （A →（C ⊙D ）∧（（B ∧┐C ）∨（┐B ∧C ））∧（C →┐D ） 列该公式的真值表如下：（可以去掉所有不满足条件的，只剩6种情况如下：） 11、设A={1,2,3,6,12},对于整除关系构成偏序集R (1)作出偏序关系R 的哈斯图 (2)令B={2,3,6}，求B 的最大，最小元，极大、极小元，上界，最小上界，下界，最大下界。 12、一棵树有2个4度结点，3个3度结点，其余结点是叶子，求该树的叶子数。 解：设树的叶子数为x,于是T 中有x+2+3个顶点,有(x+2+3)-1条边， 由握手定理知T 中所有顶点的度数之和 ∑+=y x i i v d 1) (=2[(x+2+3)-1] 2*4+3*3+x*1=2*[(2+3+x)-1] X=9 13、求带权为2, 3, 5, 7,8,9的最优二叉树,并编一个最佳2元前缀码. 解：最优二叉树如下图所示： 编码： 2：0000； 3：0001 5：001 7：10 8：11 9：01 14、带权无向图G 如下，求G 的最小生成树T 及T 的权总和，要求写出解的过程。 2 3 5 5 10 9 19 7 8 34 15 7 解：取数的由小到大的排列为1＜3＜4＜8＜9＜15＜16<17<20<23<28<36 最小生成树如图所示： 最小生成树的权数为其权W(T)=48 15、 求┐(P →Q) ? (P →┐Q)的主合取范式并给出所有使命题为真的赋值。 解：原式?(┐(P →Q)→(P →┐Q))∧((P →┐Q)→┐(P →Q)) ? ((P →Q)∨(P →┐Q))∧(┐(P →┐Q)∨┐(P →Q)) ? (┐P ∨Q ∨┐P ∨┐Q)∧(┐(┐P ∨┐Q)∨(P ∧┐Q)) ? (┐(P ∧┐Q)∨(P ∧┐Q)) ? (P ∧Q)∨(P ∧┐Q) ? P ∧(Q ∨┐Q) ? P ∨(Q ∧┐Q) ? (P ∨Q)∧(P ∨┐Q) 命题为真的赋值是P=1,Q=0和P=1,Q=1 16、某班有学生60人，其中有38人选修Visual C++课程，有l6人选修Visual Basic 课程。有21人选修Java 课程；有3人这三门课程都选修，有2人这三门课程都不选修，问仅选修两门课程的学生人数是多少？ 解 设选修Visual C++课程的学生为集合A ；选修Visual Basic 课程的学生为集合B ；选修Java 课程的学生为集合C 。 由题意可知： |A|＝38 |B|＝16 |C|＝21 |A ∩B ∩C|＝3 60-|A ∪B ∪C|＝2 因为|A ∪B ∪C|＝|A|+|B|+|C|-|A ∩B|-|A ∩C|-|B ∩C|+|A ∩B ∩C| a b c g 23 3 8 9 4 1 a b c g 2336153 8 16 28 9 4 1 所以有：|A ∩B|+|A ∩C|+|B ∩C|=20。 所以仅选修两门课程的学生数是 |A ∩B|+|A ∩C|+|B ∩C|-3|A ∩B ∩C|=11。 17、设〈A,R 〉为一个偏序集，其中A={1，2，3，4，6，9，24，54} ，R 是A 上的整除关系。（1）画出〈A,R 〉的哈斯图；（2）求R 关于A 的极大元；（3）求B={4,6,9}的最小上界和最大下界。 18、设G=＜a ＞是12阶循环群，求出G 的所有子群。 解：因为12的正因子是1,2,5，10 所以 G 的子群有4个， 分别是 四、证明题 1、设R 1，R 2为A 上的关系，证明：1 211121)(---?=?R R R R 。 证明：对任意的A y x ∈,，有 121)(,-?>∈ 21,R R x y ?>∈?< ),(),(21R x y R x y ?>∈<∨>∈ 211--?>∈<∨>∈ 21 1,--∨>∈? 故1 211121)(---?=?R R R R 2、设R 1，R 2为A 上的关系，证明：1 211121)(---?=?R R R R 。 证明：对任意的A y x ∈,，有 121)(,-?>∈ 21,R R x y ?>∈?< ),(),(21R x y R x y ?>∈<∧>∈ 211--?>∈<∧>∈ 21 1,--?>∈? 故1211121)(---?=?R R R R 3、在自然推理系统P中，构造下面推理的证明： 只要A曾到过受害者房间并且11点以前没离开，A就犯了谋杀罪。A曾到过受害者房间。如果A在11点以前离开，看门人会看见他。看门人没有看见他，所以A犯了谋杀罪。 证明：命题符号化： p：A曾到过受害者房间 q：A11点以前离开 r ：A犯了谋杀罪 s：看门人会看见他 前提：（p∧┐q）→r，p，q→s，┐s 结论：r 证明：①┐s ② q→s ③┐q ④p ⑤（p∧┐q） ⑥（p∧┐q）→r ⑦ r 4、设C*={a+bi | a,b为实数，且a≠0}。其中i 是虚数单位。在C*上定义： R={ （1）证明：R是C*上的等价关系； （2）给出R产生的等价类。 证明：（1）对任意的a+bi∈C*， a≠0?aa＞0?（a+bi）R（a+bi） 所以R是自反的。 （2）对任意的a+bi，c+di∈C*， （a+bi）R（c+di）?ac＞0 ? ca＞0 ?（c+di）R（a+bi） 所以R是对称的。 （3）对任意的a+bi，c+di， e+fi∈C*， （a+bi）R（c+di），（c+di）R（e+fi）? ac＞0，ce＞0?ae＞0 ?（a+bi）R（e+fi） 所以R是传递的。 综上R是一个等价关系。 R有两个不同的等价类。设为K 1，K 2 K 1={（a+bi ）∧a ＞0}，K 2={（a+bi ）∧a ＜0} 5、证明：6阶群中必含3阶元。 证明：设G 是6阶群，由L —定理的推论1知G 中元素的阶只可能是1，2，3，6。 若G 中含有6阶元，设该元素为a ，则a 2为3阶元。 若G 中不含有6阶元，下面证明G 中必含有3阶元。若不然G 中只含有1阶和2阶元，即对任意a ∈G ，有a 2=e ，则G 是Abel 群，取G 中两个不同的2 阶元a,b ，令H={e,a,b,ab}，则H 是G 的子群，但|H|=4，|G|=6，4不整除6，矛盾。故G 中必含有3阶元。 6、构造下面推理的证明: 前提: )).()(()),()((x H x G x x H x F x →?∧?? 结论: )).()((x F x G x ?→? 证明: (1) ))()((x H x F x ∧?? 前提引入 (2) ))()((x H x F x ?∨?? (1)置换 (3) ))()((x F x H x ?→? (2)置换 (4) ))()(y F y H ?→ (3)UI (5) ))()((x H x G x →? 前提引入 (6) ))()(y H y G → (5)UI (7) ))()(y F y G ?→ (6)(4)假言三段论 (8) )).()((x F x G x ?→? (7)UG 7、、构造下列推理的证明. 前提:t r s t s r p q p ?→?→?→∨,,,, 结论:q 证明： (1)t s → 前提引入 (2)t ? 前提引入 (3)s ? (1)(2)拒取式 (4)r s →? 前提引入 (5)r (3)(4)假言推理 (6)r p ?→ 前提引入 (7)p ? (5)(6)拒取式 (8)q p ∨ 前提引入 (9)q (7)(8)析取三段论 8、设Z 为整数集合,在Z 上定义二元运算*, Z y x ∈?,有 1-+=*y x y x 证明: (Z , *)是群. 证明: (1) 封闭性： (2) 可结合性： (3)幺元为1 ： (4)x 的逆元为x X -=-21 9、试证：任一棵非平凡树G 至少有两片树叶。 证明：设T 中有x 片树叶，y 个分支点。于是T 中有x+y 个顶点，有x+y-1 条边，由握手定理知T 中所有顶点的度数之和 d v i i x y () =+∑1=2(x+y-1)。 又树叶的度为1，任一分支点的度大于等于2于是 ∑+=y x i i v d 1 )( ≥x ·1+2y 从而2(x+y-1)≥x+2y x ≥2 证毕。 10、设Q 为有理数集合,在Q-{1}上定义二元运算*, Q y x ∈?,-{1}有 xy y x y x -+=* 证明： (1) 封闭性： (2) 可结合性： (3)幺元为0 ： (4)x 的逆元为1 1-=-x x x 11、有代数系统V1 = ? :R →+R ? (x)=x e , 试证?映射为同构映射。 证明：(1)? x,y ∈R,?(x ＋y)= y x e += x e ·y e =?(x)·?(y),所以, ? 是V1 到V2的同态. (2) ? x,y ∈R ， x ≠y 则有x e ≠y e ，即?(x) ≠?(y)，所以, ? 是V1到 V2的单射 （3）? y ∈+ R ，有x=lny ∈R , 所以, ? 是V1到V2的满射 综上三点，所以? 是V1到V2的同构映射 12、在自然推理系统F 中，构造下面推理的证明： 任何人如果喜欢音乐就不喜欢体育。每个人或者喜欢体育或者喜欢美术。有的人不喜欢美术，因而有的人不喜欢音乐。（个体域为人类集合） 命题符号化：)(x F ：x 喜欢音乐 )(x G ：x 喜欢体育 )(x H ：x 喜欢美术 前提：))()((x G x F x ?→?，))()((x H x G x ∨? 结论：)()(x F x x H x ??→?? 证明：附加前提证明法 ①)(x H x ?? 附加前提引入 ②)(c H ? EI 规则 ③))()((x H x G x ∨? 前提引入 ④)()(c H c G ∨ UI 规则 ⑤)(c G ②④析取三段论 ⑥))()((x G x F x ?→? 前提引入 ⑦)()(c G c F ?→ UI 规则 ⑧)(c F ? ⑤⑦拒取 ⑨)(x F x ?? EG 规则 13、设R 是A 上的自反的和传递的，如下定义A 上的关系T ，使得 A y x ∈?, ，R x y R y x T y x >∈<∧>∈?<>∈<,,, 证明：T 是A 上的等价关系。 证明：因为R 具有自反性,所以对任意的A x ∈，R x x >∈<,故 T x x R x x R x x >∈?<>∈<∧>∈<,,, 所以T 具有自反性。 对任意的T y x >∈<,，有 T y x >∈<, R x y R y x >∈<∧>∈?<,, R y x R x y >∈<∧>∈?<,, T x y >∈?<, 所以T 具有对称性； 利用R 具有传递性，若T z y y x >∈<><,,,，则 T z y T y x >∈<∧>∈<,, ),,(),,(R y z R z y R x y R y x >∈<∧>∈<∧>∈<∧>∈ ),,(),,(R x y R y z R z y R y x >∈<∧>∈<∧>∈<∧>∈∈<∧>∈?<,, T z x >∈?<, 所以T 具有传递性； 因为T 具有自反性、对称性和传递性，所以R 是一个等价关系。 14、设Z 为整数集合，在Z 上定义二元运算ο如下：2,,-+=∈?y x y x Z y x ο 证明：Z 关于ο运算构成群。 证明： 因为对任意的Z y x ∈,，有Z y x ∈-+2，所以整数集合Z 关于运算ο封闭。 对Z z y x ∈?,,有 4)2()(-++=-+=z y x z y x z y x οοο 4)2()(-++=-+=z y x z y x z y x οοο 故z y x z y x οοοο)()(=，即运算ο满足结合律。 Z ∈2，且对任意的Z x ∈有x x x ==οο22，所以2是><ο,Z 的单位元。 对任意的Z x ∈有Z x ∈-4，且2)4()4(=-=-x x x x οο，即x x -=-41 综合上述可知Z 关于ο运算构成群。 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、 数理逻辑部分的综合练习，基本上是按照考试的题型(除单项选择题外) 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师(不收电子稿)。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1 .命题公式P (Q P)的真值是T或1 ______ . 2?设P:他生病了，Q:他出差了. R:我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P V Q)-R 3. ____________________________________________________________ 含有三个命题变项P，Q，R的命题公式P Q的主析取范式是__________________ _(P Q R) (P Q R)_ 4. 设P(x): x是人，Q(x): x去上课，则命题“有人去上课.” 可符号化为— x(P(x) Q(x))_ 5. 设个体域D = {a, b},那么谓词公式xA(x) yB(y)消去量词后的等值式为 (A(a) A(b)) (B(a) B(b))_ 6 .设个体域D = {1,2, 3}，A(x)为“x大于3”，则谓词公式(x)A(x)的真值为F 或0 ________________ . 7.谓词命题公式(x)((A(x) B(x)) C(y))中的自由变元为 ________ . 8 .谓词命题公式(x)(P(x) Q(x) R(x，y))中的约束变元为x _______ . 三、公式翻译题 1 .请将语句“今天是天晴”翻译成命题公式 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月19日前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1 ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为 (PQ)R ． 3．含有三个命题变项P ，Q ，R 的命题公式PQ 的主析取范式是 (PQR) (PQR) ． 4．设P(x)：x 是人，Q(x)：x 去上课，则命题“有人去上课．” 可符号化为 (x)(P(x) →Q(x)) ． 5．设个体域D ＝{a, b},那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) A(b)) (B(a) B(b)) ． 6．设个体域D ＝{1, 2, 3}，A(x)为“x 大于3”，则谓词公式(x)A(x) 的真值为 ． 7．谓词命题公式(x)((A(x)B(x)) C(y))中的自由变元为 ． 8．谓词命题公式(x)(P(x) Q(x) R(x ，y))中的约束变元为 X ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 1．解：设P ：今天是天晴； 则 P ． 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P ：小王去旅游，Q ：小李去旅游， 则 PQ ． 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P:明天天下雪 。 Q:我去滑雪 则 P Q ． 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 7．解：设 P ：他去旅游，Q ：他有时间， 则 P Q ． 5．请将语句 “有人不去工作”翻译成谓词公式． 11．解：设P(x)：x 是人，Q(x)：x 去工作， 离散数学形成性考核作业4作业与答案 离散数学综合练习书面作业 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档． 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、公式翻译题 1．请将语句“小王去上课，小李也去上课．”翻译成命题公式． 设Ｐ：小王去上课 Ｑ:小李去上课 则：命题公式Ｐ∧Ｑ 2．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 设Ｐ：他去旅游 Ｑ：他有时间 则命题公式为Ｐ→Ｑ 3．请将语句“有人不去工作”翻译成谓词公式． 设Ａ（x）:x是人 Ｂ（x）：去工作 则谓词公式为?x（A(x)∧－B（x）) 4．请将语句“所有人都努力学习．”翻译成谓词公式． 设A（x）: x是人 B（x）:努力学习 则谓词公式为?x（A（x）∧B（x）） 二、计算题 1．设A={{1},{2},1,2}，B={1,2,{1,2}}，试计算 （1）(A-B)；（2）(A∩B)；（3）A×B． 解： （1）（A-B）＝{{1}，{2}} （2）（A∩B）＝{1，2} （3）A×B＝ {<{1},1>,<{1},2>,<{1},{1,2}>,<{2},1>,<{2},2>,<{2},{1,2}>,<1,1>,<1, 2>,<1,{1,2}>,<2,1>,<2,2>,<2,{1,2}>} 2．设A={1，2，3，4，5}，R={ 一、请给出一个集合A，并给出A上既具有对称性，又具有反对称性的关系。（10分）解：A={1,2} R={（1,1），（2,2）} 二、请给出一个集合A，并给出A上既不具有对称性，又不具有反对称性的关系。（10分）集合A={1,2,3} A上关系{<1,2>,<2,1>,<1,3>}，既不具有对称性，又不具有反对称性 三、设A={1，2}，请给出A上的所有关系。（10分） 答：A上的所有关系: 空关系，{<1,1>,<1,2>,<2,1>,<2,2>} {<1,1>} {<1,2>} {<2,1>} {<2,2>} {<1,1>,<1,2>} {<1,1>,<2,1>} {<1,1>,<2,2>} {<1,2>,<2,1>} {<1,2>,<2,2>} {<2,1>,<2,2>} {<1,1>,<1,2>,<2,1>} {<1,1>,<1,2>,<2,2>} {<1,2>,<2,1>,<2,2>} {<1,1>,<2,1>,<2,2>} 四、设A={1，2，3}，问A 上一共有多少个不同的关系。（10分） 设A={1，2，3}，A 上一共有2^(3^2)=2^9=512个不同的关系。 五、证明： 命题公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。（10分） 证明：设公式G 的合取范式为：G ’=G1∧G2∧…∧Gn 若公式G 恒真，则G ’恒真，即子句Gi ；i=1,2,…n 恒真 为其充要条件。 Gi 恒真则其必然有一个原子和它的否定同时出现在Gi 中，也就是说无论一个解释I 使这个原子为1或0 ，Gi 都取1值。 若不然，假设Gi 恒真，但每个原子和其否定都不同时出现在Gi 中。则可以给定一个解释I ，使带否定号的原子为1，不带否定号的原子为0，那么Gi 在解释I 下的取值为0。这与Gi 恒真矛盾。 因此，公式G 是恒真的当且仅当在等价于它的合取范式中，每个子句均至少包含一个原子及其否定。 六、若G=(P ，L)是有限图，设P(G)，L(G)的元数分别为m ，n 。证明：n ≤2m C ，其中2m C 表 示m 中取2的组合数。（10分） 证明：如果G=(P,L)为完全图，即对于任意的两点u 、v （u ≠v ）,都有一条边uv ，则此时对于元数为m 的P(G)，L(G)的元数取值最大为C m 2。因此，若G=(P,L)为一有限图，设P(G)的元数为m ，则有L(G) 离散数学作业7 离散数学数理逻辑部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求本学期第17周末前完成并上交任课教师（不收电子稿）。并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．命题公式()P Q P →∨的真值是 1或T ． 2．设P ：他生病了，Q ：他出差了．R ：我同意他不参加学习. 则命题“如 果他生病或出差了，我就同意他不参加学习”符号化的结果为 （P ∨Q ）→R ． 3．含有三个命题变项P ，Q ，R 的命题公式P ∧Q 的主析取范式是 (P ∧Q ∧R)∨(P ∧Q ∧?R) ． 4．设P (x )：x 是人，Q (x )：x 去上课，则命题“有人去上课．” 可符号化为 ?x(P(x) ∧Q(x)) ． 5．设个体域D ＝{a , b },那么谓词公式)()(y yB x xA ?∨?消去量词后的等值式为 (A(a) ∨A(b)) ∨((B(a) ∧B(b)) ． 6．设个体域D ＝{1, 2, 3}，A (x )为“x 大于3”，则谓词公式(?x )A (x ) 的真值为 0(F) ． 7．谓词命题公式(?x )((A (x )∧B (x )) ∨C (y ))中的自由变元为 y ． 8．谓词命题公式(?x )(P (x ) →Q (x ) ∨R (x ，y ))中的约束变元为 x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 设P ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名： 离散数学作业答案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】 离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数 理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题 目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识 点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地 完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答 过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在03任务界 面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)- A B P(B )={{3},{1,3},{2,3},{1,2,3}}，A? B={<1,1>,<1,2>,<2,1>,<2,2>,<3,1>,<3,2>} ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为{<2,2>,<2,3>,<3,2>,<3,3>} ． 4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} ∈ y x∈ y < > = {B , , x , 2 y A x 那么R－1＝{<6,3>,<8,4>} 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 第一章 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整除的正整数共有 66-13+40-13=80个。 第三章 1.下列语句是命题吗？ (1)2是正数吗？ (2)x2+x+1=0。 (3)我要上学。 (4)明年2月1日下雨。 (5)如果股票涨了，那么我就赚钱。 2.请用自然语言表达命题(p?→r)∨(q?→r)，其中p、q、r为如下命题： p：你得流感了 q：你错过了最后的考试 3.通过真值表求p→(p∧(q→p))的主析取范式和主合取范式。 4.给出p→(q→s),q,p∨?r?r→s的形式证明。 第四章 1.将?x(C(x)∨?y(C(y)∧F(x,y)))翻译成汉语，其中C(x)表示x有电脑，F(x,y) 表示x和y是同 班同学，个体域是学校全体学生的集合。 解： 学校的全体学生要么自己有电脑，要么其同班同学有电脑。 2.构造?x(P(x)∨Q(x)),?x(Q(x)→?R(x)),?xR(x)??xP(x)的形式证明。 解： ①?xR(x) 前提引入 ②R(e) ①US规则 ③?x(Q(x)→?R(x)) 前提引入 ④Q(e) →?R(e) ③US规则 ⑤?Q (e) ②④析取三段论 ⑥?x(P(x)∨Q(x)) 前提引入 ⑦P(e) ∨Q(e) ⑥US规则 ⑧P(e) ⑤⑦析取三段论 ⑨?x (P(x)) ⑧EG规则 第五章 离散数学作业 一、选择题 1、下列语句中哪个就是真命题(C )。 A.我正在说谎。 B.如果1+2=3,那么雪就是黑色的。 C.如果1+2=5,那么雪就是白色的。 D.严禁吸烟！ 2、设命题公式))((r q p p G →∧→=,则G 就是( C )。 A 、 恒假的 B 、 恒真的 C 、 可满足的 D 、 析取范式 3、谓词公式),,(),,(z y x yG x z y x F ??→中的变元x ( C )。 A.就是自由变元但不就是约束变元 B.既不就是自由变元又不就是约束变元 C.既就是自由变元又就是约束变元 D.就是约束变元但不就是自由变元 4、设A={1,2,3},则下列关系R 不就是等价关系的就是(C ) A.R={<1,1>,<2,2>,<3,3>} B.R={<1,1>,<2,2>,<3,3>,<2,3>,<3,2>} C.R={<1,1>,<2,2>,<3,3>,<1,4>} D.R={<1,1>,<2,2>,<3,3>,<1,2>,<1,3>,<2,3>,<2,1>, <3,1>,<3,2>} 5、设R 为实数集,映射σ=R →R,σ(x)= -x 2+2x-1,则σ就是( D )。 A.单射而非满射 B.满射而非单射 C.双射 D.既不就是单射,也不就是满射 6、下列二元运算在所给的集合上不封闭的就是( D ) A 、 S={2x-1|x ∈Z +},S 关于普通的乘法运算 B 、 S={0,1},S 关于普通的乘法运算 C 、 整数集合Z 与普通的减法运算 D 、 S={x | x=2n ,n ∈Z +},S 关于普通的加法运算 7、*运算如下表所示,哪个能使({a,b},*)成为含幺元半群( D ) b b b a a a b a * a b b b a a b a * 8( A ) 2011-2012学年第一学期离散数学作业及参考答案---信息安全10级5-1 1.利用素因子分解法求2545与360的最大公约数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最大公约数的方法 gcd(a,b) = p1min(a1,b1)p2min(a2,b2)pn min(an,bn) 360=2332515090 2545=2030515091 gcd(2545,360) =2030515090=5 2.求487与468的最小公倍数。 解：掌握两点：(1) 如何进行素因子分解 从最小素数2的素数去除n。 (2) 求最小公倍数的方法 lcm(a,b) = p1max(a1,b1)p2max(a2,b2)pn max(an,bn) ab=gcd(a, b)﹡lcm (a, b) 487是质数，因此gcd(487,468)=1 lcm(487,468)= (487*468)/1=487*468=227916 3.设n是正整数，证明：6|n(n+1)(2n+1) 证明：用数学归纳法： 归纳基础：当n=1时，n(n+1)(2n+1)=1*2*3=6，6|6 归纳假设：假设当n=m时，6|m(m+1)(2m+1) 归纳推导：当n=m+1时， n(n+1)(2n+1)=(m+1)(m+1+1)[2(m+1)+1] =(m+1)(m+2)(2m+3) = m(m+1)(2m+3)+2(m+1)(2m+3) = m(m+1)(2m+1+2)+2(m+1)(2m+3) = m(m+1)(2m+1)+2 m(m+1)+ 2(m+1)(2m+3) = m(m+1)(2m+1)+ 2(m+1)(m+2m+3) = m(m+1)(2m+1)+ 2(m+1)(3m+3) = m(m+1)(2m+1)+ 6(m+1)2 因为由假设6|m(m+1)(2m+1)成立。 而6|6(m+1)2 所以6|m(m+1)(2m+1)+ 6(m+1)2 故当n=m+1时，命题亦成立。 所以6| n(n + 1)(2n + 1) 5-2 1 已知 6x ≡7 (mod 23),下列式子成立的是( D ): A. x ≡7 (mod 23) B. x ≡8 (mod 23) C. x ≡6 (mod 23) D. x ≡5 (mod 23) 2 如果a ≡b (mod m) , c是任意整数，则（A ）： 第三次在线作业 1.（ 2.5分）不能再分解的命题称为原子命题，至少包含一个联结词的命题称为复合命题 ?正确 ?错误 我的答案：正确此题得分：2.5分 2.（2.5分）命题是能够表达判断（分辩其真假）的陈述语句 ?正确 ?错误 我的答案：正确此题得分：2.5分 3.（2.5分）一个命题可赋予一个值，称为真值 ?正确 ?错误 我的答案：正确此题得分：2.5分 4.（2.5分）复合命题是由连结词、标点符号和原子命题复合构成的命题 ?正确 ?错误 我的答案：正确此题得分：2.5分 5.（2.5分）在条件命题P→Q中，命题P称为P→Q的前件或前提，命题Q称为P→Q的后件或结论 ?正确 ?错误 我的答案：正确此题得分：2.5分 6.（2.5分）给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为T，则称该 命题公式为重言式或永真公式 ?正确 ?错误 我的答案：正确此题得分：2.5分 7.（2.5分）给定一个命题，若无论对分量作怎样的指派，其对应的真值永远为F，则称该命题公式为矛盾式或永假公式 ?正确 ?错误 我的答案：正确此题得分：2.5分 8.（2.5分）任何两个重言式的合取或析取仍然是一个重言式 ?正确 ?错误 我的答案：正确此题得分：2.5分 9.（2.5分）一个命题称为合取范式，当且仅当它具有如下的形式： A1∧A2∧…∧An，(n≥1)其中A1A2…An都是由命题变元或其否定所组成的析取式 ?正确 ?错误 我的答案：正确此题得分：2.5分 10.（2.5分）一个命题称为析取范式，当且仅当它具有如下的形式： A1∨A2∨ … ∨An，(n≥1)其中A1A2…An都是由命题变元或其否定所组成的合取式 ?正确 离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第三次作业，大家要认真及时地完成数理逻辑部分的综合练习作业。 要求：将此作业用A4纸打印出来，并在07任务界面下方点击“保存”和“交卷”按钮，以便教师评分．作业应手工书写答题，字迹工整，解答题要有解答过程，完成后上交任课教师（不收电子稿）． 一、填空题 1．命题公式() →∨的真值是 1 ． P Q P 2．设P：他生病了，Q：他出差了．R：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为P∨Q→R ． 3．含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式是(P∧Q∧┐R)∨(P∧Q∧R) ． 4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”可符号化为?x ( P ( x) ∧Q ( x))． 5．设个体域D＝{a, b},那么谓词公式) xA? ∨ x ?消去量词后的等值式为 yB ( ) (y (A(a)∨A(b))∨(B(a) ∧B(b))． 6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(?x)A(x) 的真值为0 ． 7．谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(?x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 解： 国开放大学离散数学本离 散数学作业答案 The pony was revised in January 2021 离散数学集合论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握．本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业． 要求：学生提交作业有以下三种方式可供选择： 1. 可将此次作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，完成作业后交给辅导教师批阅． 2. 在线提交word文档 3. 自备答题纸张，将答题过程手工书写，并拍照上传． 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{1,2}，{2,3}，{1,3}， A B {1,2,3}} ，A B= {< 1,1>，<1,2>，<2，1>，<2，2>，<3，1>，<3， 2> } ． 2．设集合A有10个元素，那么A的幂集合P(A)的元素个数为 1024 ． 3．设集合A={0, 1, 2, 3}，B={2, 3, 4, 5}，R是A到B的二元关系， 则R的有序对集合为 {< 2,2>，<2,3>，<>，<> } ．4．设集合A={1, 2, 3, 4 }，B={6, 8, 12}，A到B的二元关系 R＝} y x y x∈ ∈ < > = A , , 2 , y {B x 那么R－1＝ {< 6，3>，<8，4> } ． 5．设集合A=｛a, b, c, d｝，A上的二元关系R={ 『离散数学』课程 作业3： P64：3 某班有25个学生，其中14人会打篮球，12人会打排球，6人会打篮球和排球，5人会打篮球和网球，还有2人会打这三种球。已知6个会打网球的人中有4人会打排球。求不会打球的人数。 解：直接使用容斥原理。我们做如下设定： A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生； 根据题意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|B∩C|=4，|A∩B∩C|=2 由容斥原理: |A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C|=14+12+6-6-5-4+2=19 —————————————————————————————————————— 但相当一部分同学没有直接使用容斥原理， 而是画了文氏图。 使用文氏图的方法，会发现此题存在问题： 表示只会打网球的同学是-1人， 此种情况与实际不符。 这可能是作者的疏忽，该教材第一版中， “已知6个会打网球的人中有4人会打排球。” 一句是写作 “已知6个会打网球的人都会打篮球或排球。” 则用容斥原理或文氏图，都可以得到5的结果。 A：会打篮球的学生；B：会打排球的学生；C：会打网球的学生； 根据题意：|E|=25，|A|=14，|B|=12，|C|=6，|A∩B|=6，|A∩C|=5，|A∩B∩C|=2 因为“会打网球的人都会打篮球或排球。” 所以C =（A∩C）∪（B∩C） 由容斥原理: |C|=|（A∩C）∪（B∩C）| = |（A∩C）|+|（B∩C）|-|（A∩C）∩（B∩C）| 可知|（B∩C）|= |C|-|（A∩C）|+|（A∩C）∩（B∩C）| = 6-5+2=3 |A∪B∪C|＝|A|＋|B|＋|C|－|A∩B|－|A∩C|－|B∩C|＋|A∩B∩C| =14+12+6-6-5-3+2=20 一、填空题 1．命题公式() →∨的真值是 1 ． P Q P 2．设P：他生病了，Q：他出差了．R：我同意他不参加学习.则命题“如果他生病或出差了，我就同意他不参加学习”符号化的结果为(P∨Q )→R ．3．含有三个命题变项P，Q，R的命题公式P∧Q的主析取范式是 (P∧Q∧R)∨(P∧Q∧┐R) ． 4．设P(x)：x是人，Q(x)：x去上课，则命题“有人去上课．”可符号化为x P Q x∧ ?． (x ( )) ( ) 5．设个体域D＝{a, b},那么谓词公式) x ∨ ?消去量词后的等值式为 xA? yB ) ( (y b B a A B ∨． ∨ A∧ a ) (b ( )) ( ( ) ) ( 6．设个体域D＝{1, 2, 3}，A(x)为“x大于3”，则谓词公式(?x)A(x) 的真值为0 ． 7．谓词命题公式(?x)((A(x)∧B(x)) ∨C(y))中的自由变元为y ．8．谓词命题公式(?x)(P(x) →Q(x) ∨R(x，y))中的约束变元为x ． 三、公式翻译题 1．请将语句“今天是天晴”翻译成命题公式． 解：设P：今天是晴天， 命题“今天是晴天”翻译成命题公式为P。 2．请将语句“小王去旅游，小李也去旅游．”翻译成命题公式． 解：设P：小王去旅游，Q：小李去旅游． 命题“小王去旅游，小李也去旅游”翻译成命题公式为P∧Q。 3．请将语句“如果明天天下雪，那么我就去滑雪”翻译成命题公式． 解：设P：明天天下雪，Q：我就去滑雪． 命题“如果明天天下雪，我就去滑雪”翻译成命题公式为P→Q。 4．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 2017秋课件作业 第一部分集合论 第一章集合的基本概念和运算 1-1设集合A={{2，3,4}，5，1}，下面命题为真是（选择题）[A] A．1∈A；B．2∈A；C．3∈A；D．{3，2,1}?A。 1-2A,B,C为任意集合，则他们的共同子集是（选择题）[D] A．C；B．A；C．B；D．?。 1-3设S={N，Z，Q，R}，判断下列命题是否正确（是非题） （1）N?Q，Q∈S，则N?S，［错］（2）-1∈Z，Z∈S，则-1∈S。［错］ 1-4设集合B={4，3}∩?，C={4，3}∩{?}，D={3，4，?}，E={x│x∈R并且x2-7x+12=0}，F={4，?，3，3}，试问：集合B与那个集合之间可用等号表示（选择题）[A] A.C; B.D; C.E; D. F. 1-5用列元法表示下列集合：A={x│x∈N且3－x〈3}（选择题）[D] A.N; B.Z; C.Q; D.Z+ 1-6为何说集合的确定具有任意性?(简答题) 答：按研究的问题来确定集合的元素。我们所要研究的问题当然是随意的呗。之所以，集合的定义（就是集合成分的确定）当然带有任意性哪。 第二章二元关系 2-1设A={1，2，3}，A上的关系R={〈1，2〉，〈2，1〉}∪IA， 试求：（综合题） (1)domR=?;(2)ranR=?;(3)R的性质。 （4）商集A/R=？（5）A的划分∏=？（6）合成运算（R。R）=？ 答：R={<1,2>,<1,3>,<2,3>，<1，1>，<2，2>，<3，3>}； (1)DomR={R中所有有序对的x}={3,2,1}; (2)RanR={R中所有有序对的y}={2,1,3}； (3)R的性质:自反,反对称,传递性质.这时，R不是等价关系。 （4）商集A/R={{1，2，3}，{2，3}，{3}}。由于R不是等价关系，所以，等价类之间出现交集。这是不允许的。请看下面的划分问题。 （5）A的划分∏={{1，2，3}，{2，3}，{3}}；也由于R不是等价关系，造成划分的荒谬结果：出现交集。试问：让“3”即参加第一组，又参加第二组，她该如何分配呢！！！ 所以，关系R必须是等价关系。至于作业中，此两题应说：因为R不是等价关系，此题无解。 2-2设R是正整数集合上的关系，由方程x+3y=12决定，即 R={〈x，y〉│x，y∈Z+且x+3y=12}， 试给出dom（R。R）。（选择题）[B] A.3； B.{3}； C.〈3，3〉； D.{〈3，3〉}。 离散数学(第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 是不封闭的？( )。 《离散数学》作业参考答案一、选择或填空： 1． B C D 2． A， F B，F C，F D，T 3． 2n-2 4． I A 5．单位元，1 6． A 7． A D 8． (1) P→?Q (2) P??Q 9．偶数 10．自反性、对称性和传递性 11． 1，单位元，0 12．所有边一次且恰好一次 13． B C D E F 14． B D 15． 5,10 16． D 17． B 18． D 19． A 20．（1）R R={ 〈1，1〉，〈1，3〉，〈2，2〉，〈2，4〉} （2）Ｒ-1＝｛〈1，2〉，〈2，1〉，〈3，2〉，〈4，3〉｝ 21． m=n-1 22． 9,3 23． A 24． D 25 (1) 26 (2) 27 (3) 28 (1) 29 (1) 30 (3) 31 (2) 32 (3) 33 (2) 34 (4) 35 (2) 36 (1) 二、求下列各公式的主析取范式和主合取范式 解：1． P∨?Q （主合取范式） ?（P∧(?Q∨Q)）∨（(?P∨P)∧?Q） ?(P∧?Q)∨（P∧Q）∨（?P∧?Q）∨（P∧?Q） ?(P∧?Q)∨（P∧Q）∨（?P∧?Q）（主析取范式） 2．Q→( P∨?R) ??Q∨P∨?R（主合取范式） ?（Q→( P∨?R)） ?（?P∨?Q∨?R）∧（?P∨?Q∨R）∧（?P∨Q∨?R）∧（?P∨Q∨R）∧（P∨?Q∨R）∧ （P∨Q∨?R）∧（P∨Q∨R）（原公式否定的主合取范式） Q→( P∨?R) ?（P∧Q∧R）∨（P∧Q∧?R）∨（P∧?Q∧R）∨（P∧?Q∧?R）∨（?P∧Q∧?R）∨（?P∧?Q∧R）∨（?P∧?Q∧?R）（主析取范式） 3． P→Q??P∨Q（主合取范式） ?(?P∧(Q∨?Q))∨((?P∨P)∧Q) ?(?P∧Q)∨(?P∧?Q)∨(?P∧Q)∨(P∧Q) ?(?P∧Q)∨(?P∧?Q)∨(P∧Q)（主析取范式） 4．?(P→Q)∨(R∧P)??(?P∨Q)∨(R∧P) ?(P∧?Q)∨(R∧P)（析取范式） ?(P∧?Q∧(R∨?R))∨(P∧(?Q∨Q) ∧R) ?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧?Q∧R)∨(P∧Q∧R) ?(P∧?Q∧R)∨(P∧?Q∧?R)∨(P∧Q∧R)（主析取范式） ?(?(P→Q)∨(R∧P)) ?(P∧Q∧?R)∨(?P∧Q∧R)∨(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R) （原公式否定的主析取范式） ?(P→Q)∨(R∧P) ?(?P∨?Q∨R)∧(P∨?Q∨?R)∧(P∨Q∨?R)∧(P∨Q∨R)∧(P∨?Q∨R)（主合取范式）5．P∧Q（主析取范式） ?(P∨(Q∧?Q))∧((P∧?P)∨Q) ?(P∨?Q)∧(P∨Q)∧(P∨Q)∧(?P∨Q) ?(P∨?Q)∧(P∨Q)∧(?P∨Q)（主合取范式） 6 Q→(P∨?R) ??Q∨P∨?R（主合取范式） ?(Q→(P∨?R)) 04任务_0010 1. 设无向图G的邻接矩阵为 ， 则G的边数为( )． A. 1 B. 6 C. 7 D. 14 2. 无向图G存在欧拉回路，当且仅当（）. A. G中所有结点的度数全为偶数 B. G中至多有两个奇数度结点 C. G连通且所有结点的度数全为偶数 D. G连通且至多有两个奇数度结点 3. 设图G＝ C. e－v－2 D. e＋v＋2 5. 若G是一个汉密尔顿图，则G一定是( )． A. 平面图 B. 对偶图 C. 欧拉图 D. 连通图 6. 以下结论正确的是( )． A. 无向完全图都是欧拉图 B. 有n个结点n－1条边的无向图都是树 C. 无向完全图都是平面图 D. 树的每条边都是割边 7. 已知一棵无向树T中有8个顶点，4度、3度、2度的分支点各一个，T的树 叶数为( )． A. 8 B. 5 C. 4 D. 3 8. 设有向图（a）、（b）、（c）与（d）如图四所示，则下列结论成立的是( )． 图四 A. （a）是强连通的 B. （b）是强连通的 C. （c）是强连通的 D. （d）是强连通的 9. 图G如图二所示，以下说法正确的是( )． A. a是割点 B. {b,c}是点割集 C. {b, d}是点割集 D. {c}是点割集 10. 无向树T有8个结点，则T的边数为( )． A. 6 B. 7 C. 8 D. 9 1. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )． A. （a）是强连通的 B. （b）是强连通的 C. （c）是强连通的 D. （d）是强连通的 2. 设有向图（a）、（b）、（c）与（d）如图所示，则下列结论成立的是( )． A. （a）是弱连通的 B. （b）是弱连通的 C. （c）是弱连通的 D. （d）是弱连通的 3. 设无向图G的邻接矩阵为则G的边数 为( )． A. 1 B. 6 C. 7 D. 14 4. 设无向图G的邻接矩阵为则G的边数为 ( )． A. 6 B. 5 C. 4 D. 3 5. 已知无向图G的邻接矩阵为则G有 （）． A. 5点，8边 B. 6点，7边 C. 6点，8边 D. 5点，7边 6. 如图所示，以下说法正确的是( )． A. e是割点 B. {a,e}是点割集 C. {b, e}是点割集 D. {d}是点割集 7. 如图所示，以下说法正确的是( ) ． A. {(a, e)}是割边 B. {(a, e)}是边割集 C. {(a, e) ,(b, c)}是边割集 D. {(d, e)}是边割集 8. 图G如图所示，以下说法正确的是( )． A. a是割点 B. {b,c}是点割集 C. {b, d}是点割集 D. {c}是点割集 9. 图G如图所示，以下说法正确的是( ) ． A. {(a, d)}是割边 B. {(a, d)}是边割集 C. {(a, d) ,(b, d)}是边割集 D. {(b, d)}是边割集 10. 设图G＝ 电大离散数学作业答案作 业答案 RUSER redacted on the night of December 17,2020 离散数学作业5 离散数学图论部分形成性考核书面作业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外）安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第二次作业，大家要认真及时地完成图论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有解答过程，要求2010年12月5日前完成并上交任课教师（不收电子稿）。并在05任务界面下方点击“保存”和“交卷”按钮，以便教师评分。 一、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结点，则G 的边数是 15 ． 2．设给定图G (如右由图所示)，则图G 的点割集是 {}f {}c e ,． 3．设G 是一个图，结点集合为V ，边集合为E ，则 G 的结点 度数之和 等于边数的两倍． 4．无向图G 存在欧拉回路，当且仅当G 连通且 不含奇数度结点 ． 5．设G=(完整版)离散数学作业答案一
离散数学作业答案
离散数学形成性考核作业4题目与答案
离散数学(大作业)与答案
电大 离散数学作业7答案
离散数学作业答案完整版
离散数学作业答案
离散数学作业标准答案
离散数学 作业及答案
离散数学第三次在线作业
离散数学作业7答案(数理逻辑部分)
国开放大学离散数学本离散数学作业答案
离散数学 作业 3~4 答案
离散数学形成性考核作业7答案
北京大学2017秋课件作业【离散数学】及答案
离散数学(第2版)_在线作业_4
《离散数学》作业参考答案
电大离散数学作业答案任务
离散数学形成性考核作业4答案教案资料
电大离散数学作业答案作业答案