离散数学作业标准答案
离散数学作业
一、选择题
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 为实数集，映射=RR ，（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={
是（ D ）。
A. 双射函数
B. 单射函数
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 (~ P∨ ~ ~Q P∨(B) Q P?(D) ) P~ ∨(C) Q 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 ） (A) (B) (C) (D) 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 ）]，则 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)=? ? ??????? ???010********* 0121 ,则长度为2的通路有 10 条. 11、设4 4 4 { },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 },公式)()(x xS x xP ?∧?在A 中消去量词后应是 21. 设M(x):x 是人，D(x):x 是要死的，则命题“所有的人都是要死的”可符号化为__ ____,其中量词的辖域是___ __ 22. 画出完全图5K 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. 画出完全图K 3,3 三、计算题 1、求公式r q p ?→)(的主析取范式和主合取范式。 解：方法一（等值演算法） r q p ?→)( ∧→→?))((r q p ))((q p r →→ ))(())((r q p r q p ?∨∨?∧∨∨??? )())((r q p r q p ?∨∨?∧∨?∧? )()()(r q r p r q p ∧∨∧?∨?∧?∧? )()()()(r q p r q p r q p r q p ∧∧∨∧?∧?∨∧∧?∨?∧?∧?7431m m m m ∨∨∨? 方法二（真值表法） 公式r q p ?→)(真值表如下： 根据真值表可以得到主析取范式为：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、在偏序集 极大元：4，6；极小元：2，3； 最大元：无；最小元：无； 1 3 6 4 10 11 21 7 8 36 15 7 上界：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 最小生成树如图所示： 最小生成树的权数为其权W(T)=12 7、设A={a,b,c,d},R={ 所以 G 的子群有4个， 分别是 A A C 2 B 9、（1）在一棵有2个2度顶点，4个3度顶点，其余顶点都是树叶的无向树中，应该有几片树叶（2）画出两棵非同构的满足（1）中顶点度数的无向树T1和T2。解：（1）设树有n个顶点，则有n-6片树叶 根据握手定理可知 - = + ? ?n 2- n + 2 )1 )6 (2 4 3 ( 于是n=12 因此有6片树叶。 (2)两棵非同构的树为 T1T2 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 c f 解：取数的由小到大的排列为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|+|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 的所有子群。 a b c f g 233 8 9 4 1 解：因为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 ?>∈<∨>∈ 21 1--?>∈<∨>∈ 1 211,--∨>∈? 故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 ?>∈<∧>∈ 21 1--?>∈<∧>∈ 1 211,--?>∈? 故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≠0aa＞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＞0ae＞0 （a+bi）R（e+fi） 所以R是传递的。 综上R是一个等价关系。 R有两个不同的等价类。设为K1，K2 K1={（a+bi）∧a＞0}，K2={（a+bi）∧a＜0} 5、证明：6阶群中必含3阶元。 证明：设G是6阶群，由L—定理的推论1知G中元素的阶只可能是1，2，3，6。 若G中含有6阶元，设该元素为a，则a2为3阶元。 若G中不含有6阶元，下面证明G中必含有3阶元。若不然G中只含有1阶和2阶元，即对任意a∈G，有a2=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 = j :R →+R j (x)=x e , 试证j 映射为同构映射。 证明：(1)" x,y ∈R,j(x ＋y)= y x e += x e ·y e =j(x)·j(y),所以, j 是V1 到V2的同态. (2) " x,y ∈R ， x ≠y 则有x e ≠y e ，即j(x) ≠j(y)，所以, j 是V1到 V2的单射 （3）" y ∈+ R ，有x=lny ∈R , 所以, j 是V1到V2的满射 综上三点，所以j 是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 去工作， 离散数学作业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 ：今天是晴天。 姓 名： 学 号： 得 分： 教师签名： 第5章作业答案 1. 用枚举法给出下列集合 解(2) {-3，2} (4) {5，6，7，8，9，10，11，12，13，14，15} 2. 用抽象法说明下列集合 解(6) {x|?k (k∈I∧x = 2k + 1)} 6．写出下列集合的幂集 解(2) ρ({1, ?}) = {?, {1}, {?}, {1, ?}} (4) ρ({?, {a}, {?}}) = {?, {?}, {{a}}, {{?}}, {?, {a}}, {?, {?}}, {{a}, {?}}, {?, {a}, {?}}} 9. 证明：如果B?C，则ρ(B) ?ρ(C)。 证明任取x∈ρ(B)，则x?B，又因为B?C，所以x?C，x∈ρ(C)。 10．设U = {1, 2, 3, 4, 5}，A = {1, 4}，B = {1, 2, 5}和C = {2, 4}，试写出下列集合。解(8) ρ(A) -ρ(C) = {?, {1}, {4}, {1, 4}} - {?, {2}, {4}, {2, 4}} = {{1}, {1, 4}} 11．证明下列恒等式 (7) (A-B) -C = (A-C) - (B-C) 证法1 对于任意x， x∈ (A-C) - (B-C) ?x∈A-C ∧x? B-C ?x∈A∧x?C ∧?(x∈ B∧x?C) ? x∈A∧x?C ∧ ( x?B ∨ x∈C) ?( x∈A∧x?C ∧ x?B)∨( x∈A∧x?C ∧ x∈C) ? x∈A∧x?C ∧ x?B ? x∈A∧ x?B∧x?C ? x∈A-B ∧ x?C ? x∈(A-B) -C 证法2 (A-C) - (B-C) = A?~C?~( B?~C) = A?~C? (~ B? C) = ( A?~C?~ B) ?( A?~C? C) =(A?~C?~ B) ?? = A?~B?~ C = (A-B) ?~ C = (A-B) -C 12．设A, B, C是集合，下列等式成立的条件是什么？ (3) (A-B ) ? (A-C) = ? 解因为(A- B) ?( A-C) = (A?~B) ? ( A?~C) = A? (~B?~C) = A?~(B ?C) = A- (B ?C) 所以(A-B)?(A-C) = ?iff A- (B?C) = ?iff A? (B?C) 第二章命题逻辑 §2.2 主要解题方法 2.2.1 证明命题公式恒真或恒假 主要有如下方法： 方法一.真值表方法。即列出公式的真值表，若表中对应公式所在列的每一取值全为1，这说明该公式在它的所有解释下都是真，因此是恒真的；若表中对应公式所在列的每 一取值全为0，这说明该公式在它的所有解释下都为假，因此是恒假的。 真值表法比较烦琐，但只要认真仔细，不会出错。 例2.2.1 说明G= (P∧Q→R)∧(P→Q)→(P→R)是恒真、恒假还是可满足。 解：该公式的真值表如下： 表2.2.1 由于表2.2.1中对应公式G所在列的每一取值全为1，故 G恒真。 方法二.以基本等价式为基础，通过反复对一个公式的等价代换，使之最后转化为一个恒真式或恒假式，从而实现公式恒真或恒假的证明。 例2.2.2 说明G= ((P→R) ∨? R)→ (? (Q→P) ∧ P)是恒真、恒假还是可满足。 解：由(P→R) ∨? R=?P∨ R∨? R=1，以及 ? (Q→P) ∧ P= ?（?Q∨ P）∧ P = Q∧? P∧ P=0 知，((P→R) ∨? R)→ (? (Q→P) ∧ P)=0，故G恒假。 方法三.设命题公式G含n个原子，若求得G的主析取范式包含所有2n个极小项，则G是恒真的；若求得G的主合取范式包含所有2n个极大项，则G是恒假的。 方法四. 对任给要判定的命题公式G，设其中有原子P1，P2，…，P n，令P1取1值，求G的真值，或为1，或为0，或成为新公式G1且其中只有原子P2，…，P n，再令P1取0值，求G真值，如此继续，到最终只含0或1为止，若最终结果全为1，则公式G恒真，若最终结果全为0，则公式G 离散数学作业答案 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={ 作业参考答案——10-特殊图 1.(a)(c)(d)是欧拉图，(a)(b)(c)(d)(e)可以一笔画，(a)(b)(c)(d)(e)(f)(g)是 哈密顿图。 2.根据给定条件建立一个无向图G= 数至少为2，而V2中的每个结点度数至多为2，从而它满足t条件t=1，因此存在从V1到V2的匹配，故可分配。 5.此平面图具有五个面，如下图所示。 a b c d e f g r1r2 r3 r4 r5 ?r1，边界为abca，D(r1)=3; ?r2，边界为acga，D(r2)=3; ?r3，边界为cegc，D(r3)=3; ?r4，边界为cdec，D(r4)=3; ?r5，边界为abcdefega，D(r5)=8;无限面 6.设该连通简单平面图的面数为r，由欧拉公式可得，6?12+r=2，所以 r=8，其8个面分别设为r1,r2,r3,r4,r5,r6,r7,r8。因是简单图，故每个面至少由3条边围成。只要有一个面是由多于3条边所围成的，那就有所有面的次数之和 8∑ i=1 D(r i)>3×8=24。但是，已知所有面的次数之和等于边数的两倍，即2×12=24。因此每个面只能由3条边围成。 2 第一章 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规则 第五章 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 ）： 国开放大学离散数学本离 散数学作业答案 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={ 离散数学作业 一、选择题 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 ) 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〉}。 离散数学数理逻辑部分形成性考核书面作业本课程形成性考核书面作业共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．请将语句“今天是天晴”翻译成命题公式． 解： 离散数学集合论部分形成性考核书面作 业 本课程形成性考核书面作业共3次，内容主要分别是集合论部分、图论部分、数理逻辑部分的综合练习，基本上是按照考试的题型（除单项选择题外） 安排练习题目，目的是通过综合性书面作业，使同学自己检验学习成果，找出 掌握的薄弱知识点，重点复习，争取尽快掌握。本次形考书面作业是第一次作业，大家要认真及时地完成集合论部分的综合练习作业。 要求：将此作业用A4纸打印出来，手工书写答题，字迹工整，解答题要有 解答过程，要求本学期第11周末前完成并上交任课教师（不收电子稿）。并在 03任务界面下方点击“保存”和“交卷”按钮，完成并上交任课教师。 一、填空题 1．设集合{1,2,3},{1,2} ==，则P(A)-P(B )= {{3}，{1,3}，{2,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>，<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.1 基本要求 1. 掌握集合、子集、超集、空集、幂集、集合族的概念。懂得两个集合间相等和包含关系 的定义和性质，能够利用定义证明两个集合相等。熟悉常用的集合表示方法。 2. 掌握集合的基本运算：并、交、余、差、直乘积、对称差的定义以及集合运算满足的基 本算律，能够利用它们来证明更复杂的集合等式。 3. 掌握关系、二元关系、空关系、全域关系、相等关系、逆关系的概念以及关系的性质： 自反性、对称性、反对称性、传递性。会做关系的乘积。了解关系的闭包运算：自反闭包、对称闭包、传递闭包。 4. 掌握等价关系、等价类、商集的概念，了解等价关系和划分的内在联系。 5. 掌握部分序关系、部分序集、全序关系、全序集的概念以及部分序集中的特殊元素：最 大元、最小元、极大元、极小元、上确界、小确界的定义。能画出有限部分序集的Hasse 图，并根据图讨论部分序集的某些性质。 6. 掌握映射、映像、1-1映射等概念，会做映射的乘积。了解可数集合的概念，掌握可数 集合的判定方法。 7. 了解关系在数据库中的应用（数据的增、删、改）以及划分在计算机中的应用。 §1.2 主要解题方法 1.2.1 证明集合的包含关系 方法一.用定义来证明集合的包含关系是最常用也是最基本的一种方法。要证明A?B，首先任取x∈A，再演绎地证出x∈B成立。由于我们选择的元素x是属于A的任何一个，而非特指的一个，故知给出的演绎证明对A中含有的每一个元素都成立。当A是无限集时，因为我们不能对x∈A，逐一地证明x∈B成立，所以证明时的假设“x是任取的”就特别重要。 例1.2.1 设A，B，C，D是任意四个非空集合，若A?C，B?D，则A×B?C×D。 证明：任取(x，y) ∈A×B，往证(x，y) ∈C×D。 由(x，y) ∈A×B知，x∈A，且y∈B。又由A?C，B?D知，x∈C，且y∈D，因此，(x，y) ∈C×D。故，A×B?C×D。 方法二.还有一种证明集合包含关系的方法，基于集合的交和并运算的两个基本性质 A?B?A?B=A?A?B=B 以及一些已经证出的集合等式。现在我们就用此方法将上例再证一次。 由下面例1.2.2证明的结论有（A×B）?（C×D）=（A?C）×（B?D），若A?C，B?D，则A?C=A，B?D=B，因此，（A×B）?（C×D）=A×B。因此，A×B?C×D。 1.2.2 证明集合的相等 方法一.若A，B 是有限集，要证明集合A=B当然可以通过逐一比较两集合所有元素均一一对应相等即可，但当A，B 是无限集时，一般通过证明集合包含关系的方法证得A?B，B?A即可。 例1.2.2 设A，B，C，D是任意四个集合，求证（A×B）?（C×D）=（A?C）×（B?D）。 证明：首先证明（A×B）?（C×D）?（A?C）×（B?D）。任取（x,y）∈（A×B）?（C×D），则（x,y）∈（A×B），且（x,y）∈（C×D），故x∈A，y∈B，x∈C，y∈D，即x∈A?C，y∈B?D，因此，（x,y）∈（A?C）×（B?D）。 由于以上证明的每一步都是等价的，所以上述论证反方向进行也是成立的。故可证得（A?C）×（B?D）?（A×B）?（C×D）。 因此，（A×B）?（C×D）=（A?C）×（B?D）。 方法二. 还有一种证明集合相等的方法，可以通过已证出的集合等式，通过相等变换将待证明的等式左（右）边的集合化到右（左）边的集合，或者两边同时相等变换到同一集合。 例1.2.2 设A，B，C是三个集合，已知A?B=A?C，A?B=A?C，求证B=C。 证法1：使用反证法。假设B≠C，则必存在x，满足x∈B，且x?C，或者x?B，且x∈C。不妨设x∈B，且x?C， [0004]《离散数学》网上作业题答案 第1次作业 [论述题]第1次作业 一、填空题 1. 设|A | = 5, |B | = 2, 则可定义A 到B 的函数( )个，其中有( )单射，( )个满射. 2. 令G (x ): x 是金子，F (x ): x 是闪光的，则命题“金子都是闪光的，但闪光的未必是金子”符号化为( ). 3. 设X 是非空集合，则X 的幂集P (X )关于集合的?运算的单位元是( )，零元是( )，P (X )关于集合的?运算的单位元是( ). 4. 6阶非Abel 群的2阶子群共有( )个，3阶子群共有( )个，4阶子群共有( )个. 5. 对于n 阶完全无向图K n , 当n 为( )时是Euler 图，当n ≥ ( )时是Hamilton 图，当n ( )时是平面图. 二、单选题 1. 幂集P (P (P (?))) 为( ) (A){{?}, {?, {?}}}. (B){?, {?, {?}}, {?}}. (C){ ?, {?, {?}}, {{?}}, {?}} (D){ ?, {?, {?}}}. 2. 设R 是集合A 上的偏序关系，则1 -?R R 是( ). (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上答案都不对 3. 下列( )组命题公式是不等值的. (A))(B A →?与B A ?∧. (B) )(B A ??与)()(B A B A ∧?∨?∧. (C))(C B A ∨→与C B A →?∧)(. (D))(C B A ∨→与)(C B A ∨∧?. 4.下列代数结构(G , *)中，( )是群. (A)G = {0, 1, 3, 5}, “*”是模7加法. (B) G = Q , “*”是数的乘法. (C)G = Z , “*”是数的减法. (D) G = {1, 3, 4, 5, 9}, “*”是模11乘法. 5.4阶完全无向图4K 中含3条边的不同构的生成子图有 (A)3 (B)4 (C)5 (D)2 离散数学作业答案 TYYGROUP system office room 【TYYUA16H-TYY-TYYYUA8Q8- 离散数学作业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},那么谓词公式) ∨ xA? ?消去量词后的等值式为 ) ( x (y yB (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：他有时间， 一、填空题 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．请将语句“他去旅游，仅当他有时间．”翻译成命题公式． 《离散数学》作业参考答案一、选择或填空： 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))(完整版)离散数学作业答案一
离散数学作业答案
电大 离散数学作业7答案
离散数学第5章作业答案
吉林大学离散数学课后习题答案
离散数学作业答案完整版
慕课 离散数学 电子科技大学 课后习题十 答案
离散数学作业答案
离散数学 作业及答案
国开放大学离散数学本离散数学作业答案
离散数学作业标准答案
北京大学2017秋课件作业【离散数学】及答案
离散数学作业7答案(数理逻辑部分)
离散数学作业答案
吉林大学离散数学课后习题答案
西南大学《离散数学》网上作业题及答案
离散数学作业答案
离散数学形成性考核作业7答案
《离散数学》作业参考答案