离散数学作业标准答案.docx
离散数学作业
一、选择题
1、下列语句中哪个是真命题（ C ）。
A ．我正在说谎。
B ．如果 1+2=3，那么雪是黑色的。
C ．如果 1+2=5，那么雪是白色的。
D ．严禁吸烟！ 2、设命题公式 A. 恒假的
G
p
( p (q
B. 恒真的
r )) ，则 G 是
（ C. 可满足的
C
）。
D. 析取范式
3、谓词公式
F (x, y, z)
x yG( x, y, z) 中的变元
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 和普通的减法运算
n ，n
Z + ， S 关于普通的加法运算
D. S={x | x=2 }
7、* 运算如下表所示，哪个能使（ {a,b}， * ）成为含幺元半群（
D ）
a b
a b
a b
a b
a a
b a a a a a a a a b b a b
b b
b
b a a
b b a
A
B
C
D
8、下列图中是欧拉图的是（
A
）。
A B C D
9、下列各组数中,能构成无向图的度数列是（D）
A． 1,1,1,2,4B． 1,2,3,4,5
C． 0,1,0,2,4D． 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( A( x)B( x))xA( x)xB( x);
B. x( A( x)B( x))xA( x)xB (x);
C.xA( x)x(A(x));
D. A xB( x)x( A B(x)).
（ C
17、下列各代数系统中，不含零元素的是）
A．M n (R), ， M n (R) 是全体n阶实矩阵集合，是矩阵乘法运算。
B．p(S),， p( S) 是集合S的幂集合，是集合的并运算。
C．R,， R 是有理数集，是数的加法运算。
D．I ,， I 是整数集，是数的乘法运算。
18、G 是有6 个点的通，度数20，从G 中去（B）
后使之成。
A .10 B. 5 C. 3 D. 2
19、在具有n 个点的无向通中，（B）。
A. 恰好有C. 最多有n 条
n 条
B. 恰好有
D. 至少有
n-1 条
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）
a
a a
b a b
b
b
a
a a
b b
b
a
b
a
a a
b a
b
a
a
a
a a
b b
b
b
a
(A)(B)(C)(D)
25.P：三可以做件事，Q：李四可以做件事。命“ 三或李四可以
做件事”符号化???????????????????（A）
(A) P Q(B) P~ Q(C) P Q(D) ~ (~ P~ 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) 半群(B) 独异点(C) 群(D) 交群
41.R 是 A 上的等价关系 ,即 R 是?????????????????（D）
（A）反自反的 ,称的，的（B）自反的,反称的,的
（C）反自反的 ,反称的 ,的（D）自反的,称的,的
42．下列哪一命公式是等价的????????????????（B）
(A) (C)~ P~ Q ， P Q(B)A(B A) ， ~ A ( A ~ B) Q( P Q) ， ~ Q (P Q)(D)~ A( A B ) ，B
43. S={0,1}, S???????????????????????（ A ）（ A）在普通乘法下封，在普通加法下不封; （B）在普通加法和乘法下都封；
（C）在普通加法下封，在普通乘法下不封；（D）在普通加法和乘法下都不封；
44. 下面公式是前束范式的是（ A ）
A.x y z( B(x, y)A( z))
B.x y(B( x, y)
C.x y z( B( x, y)A(z))
D.x(B( x, y)yB( y))
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) 水开了
49. 函数f : A
(A) A=B
(B) 花多好看呀！(C) 2 是常数。
B 可逆的充要条件是（D）
(B)A与 B 有相同的基数(C)f 射
(D)我正在
(D)f 双射
二、填空题
1、公式 (P∧ Q)→(R∨ S)真表中共有16种真指派。
2、A(x):x 是运 ,B(x):x是壮的 .命“没有一个运不是壮的”可符号
化。
3、是公式xF ( y, x)yG ( y) 的前束范式。
4、集合 A={1,2,3}上两个二元关系 R1={＜ 1,3＞，＜ 2,1＞，＜ 3,2＞} 和
R2={＜1,2＞，＜ 2,3＞，＜ 3,1＞}，
R1R2=,
t (R1 )。
5、集合 Z m={[0],[1],[2] ，?， [m-1]} ，在 Z m上定运算 +m：任意的 [i] ，[j] ∈
Z m有： [i]+m[j]=[ （i+j）（ modm）]，
∈ Z m的逆元是[m-i]。
6、无向G 如 1 所示，G 的点通度1。
图 1图2
7、有向图 D 如图 2 所示，则有向图 D 的邻接矩阵
中长度为 2 的回路有2条。
A=， D
8、设 p：1+1=5，q：明天是阴天。则命题“只要1+1=5，那么明天是阴天”可符
号化为 _________，其真值为 ________1_。
9、设F ( x) : x是兔子，G y : y是乌龟，H ( x, y) : x比 y 跑得快，则“并不是所有
的兔子都比乌龟跑得快。”可符号化为
1 2 10
10、设有向图 D 的邻接矩阵 A(D)=0010,则长度为 2 的通路有10 条.
0001
0010
11、设Z4{ 0,1,2,3}, x y
x y x y4
) 的生成元{
y 4x y
，则 ( Z 4 ,
x4
是1或3。
12、具有 16 个结点的完全无向图其边数一定为120条。
13、设集合A{ 2, 3, 4, 6, 8, 12, 24} ，R为A上的整除关系，集合A中的极大元是
24；极小元 2， 3；
14、整数加群的幺元是
15 若 A={1,2,3 }, x, y _
A, x
0___。
y min{ x, y},则* 的运算表为
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 (x)xS(x)在A 中消去量词后应是
21.设 M(x):x 是人， D(x):x 是要死的，则命题“所有的人都是要死的”可符号化
为 ______,其中量词的辖域是 _____
22.画出完全图 K 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：小李；则命题“小李非常聪明
和能干”的为谓词表达式为 _______。
{1.4.5}
.
27. 设 A，B 是两个集合， A={1, 2, 3, 4}，B={2, 3, 5}，则 A B=
28. 公式 A→ (x)B(x)的前束范式为 ____________________。
29. 一个简单连通无向图有n 个节点，它的边数至少有n-1 条。
30.画出完全图K3,3
三、计算题
1、求公式( p q)r 的主析取范式和主合取范式。
解：方法一（等值演算法）
( p q)r
(( p q)r )(r( p q))
((p q )r )((p q )r )
(( p q) r )(p q r )
( p q r )(p r )( q r )
( p
m1m3q
m4
r )
m7
(p q r )(p q r )( p q r )
方法二（真值表法）
公式( p q)r 真值表如下：
p q r p q( p q)r r( p q)( p q)r
0001010
0011111
0101010
0111111
1000111
1010100
1101010
1111111
根据真值表可以得到主析取范式为：m1m3 m4m7
2、列出命题公式（( p q)p)p 的真值表。
解：
p q p q( p q)p)( pq)p)
p
00101
01101
10011
11111
3、设集合 A= 1,2,3，R 为 A 上的二元关系， R={＜1,2＞＜ 3,1＞,＜2,3＞} ，求 R2，r ( R) ， s( R) ， t( R) 的集合表达式。
解：因为 R={<1,2>,<2,3>,<3,1>},所以
R2={<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；
最大元：无；最小元：无；
上界： 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
36
15
217
8
10
7
11
4
6
13
6、用 Kruskal 算法求下列权图的最小生成树,并求最小生成树的权数 ,要求写出解的
过程 .
B7 D 2E
3
14
A25
97
C4E
解 : 取数的由小到大的排列为1＜2＜3＜4＜5＜7＜9
B2
D F
3
14
A2
E
C
最小生成树如图所示：
最小生成树的权数为其权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 片树叶
根据握手定理可知
2 2 4
3 (n 6) 2(n1)
于是 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 种情况如下：）
A B C D（ 1）（2）（3）G
0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 1 0 1 1 0 1 0 1 0 1 0 0 1 0 1 1 0 1
1
1
1 1 1 1 1 0 0 0
1
1
由真值表知有两种派法 A ，C 去或 B ， D 去。
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 条边，
x y
由握手定理知 T 中所有顶点的度数之和
d (v i )
i 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
34
19
15
7 8
10
7
9
5
5
2
3
14、带权无向图 G 如下，求 G 的最小生成树 T 及 T 的权总和，要求写出解的过程。
a
20 b
4 23 36
1
15
f
g
9
c
28 8
16
3
e
17
d
解：取数的由小到大的排列为1＜ 3＜ 4＜ 8＜ 9＜ 15＜16<17<20<23<28<36
a
4b
231
g9
f c
83
e d
最小生成树如图所示：
最小生成树的权数为其权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|＝360-|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 的所有子群。
解：因为 12 的正因子是 1,2,5， 10
所以 G 的子群有 4 个，分别是
四、证明题
1、设 R1，R2为 A 上的关系，证明：( R1R2 ) 1R11R21 。
证明：对任意的 x, y A ，有
x, y( R1R2 ) 1
y, x R1R2
( y, x R1 ) ( y, x R2 )
( x, y R1 ) ( x, y R 1 )
12
x, y R11R21
故 (R1 R2 ) 1R11R21
2、设 R1，R2为 A 上的关系，证明：( R1R2 ) 1R11R21 。
证明：对任意的 x, y A ，有
x, y( R1R2 ) 1
y, x R1R2
( y, x R1 ) ( y, x R2 )
( x, y R1 ) ( x, y R1 )
12
x, y R11R21
故 (R1R2 ) 1R11R21
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(F ( x) H ( x)), x(G( x) H ( x)).
结论 :
x(G( x)
F ( x)).
证明 :
(1)
x( F (x) H ( x))
(2)
x( F (x)H (x))
(3) x( H ( x)
F ( x))
(4) H ( y)F ( y)) (5) x(G (x) H ( x)) (6) G ( y) H ( y)) (7) G ( y)F ( y))
(8) x(G(x)F (x)).
7、、构造下列推理的证明 .
前提引入
(1)置换
(2)置换 (3)UI 前提引入
(5)UI
(6)(4)假言三段论
(7)UG
前提 : p q, p r, s
t, s r , t
结论 :q 证明：
(1)
s
t
前提引入 (2) t
前提引入
(3) s
(1)(2)拒取式 (4) s r
前提引入
(5)
r
(3)(4)假言推理
(6)
p
r
前提引入 (7) p (5)(6)拒取式 (8) p
q
前提引入
(9)
q
(7)(8)析取三段论
8、设 Z 为整数集合 ,在 Z 上定义二元运算 *, x, y
Z 有
x y x
y 1
证明 : (Z, *) 是群 . 证明 : (1) 封闭性：
(2) 可结合性： (3)幺元为 1 ：
(4)x 的逆元为 X 1
2 x
9、试证：任一棵非平凡树 G 至少有两片树叶。
证明：设 T 中有 x 片树叶，y 个分支点。于是 T 中有 x+y 个顶点，有 x+y-1 条
x y
边，由握手定理知 T 中所有顶点的度数之和
d (v i )
i 1
=2(x+y-1)。
又树叶的度为 1，任一分支点的度大于等于
2 于是
x y
≥x ·1+2y
d (v i )
i 1
从而 2(x+y-1)≥x+2y
x ≥2
证毕。
10、设 Q 为有理数集合 ,在 Q-{1}上定义二元运算 *,
x, y Q -{1}有
x y x y xy
证明：
(1) 封闭性：
(2) 可结合性： (3)幺元为 0 ：
(4)x 的逆元为 x 1
x
x 1
11、有代数系统 V1 =
j :R → R j (x)=e x , 试证 j 映射为同构映射。
证明： (1)" x,y ∈R,j(x ＋ y)= e x y e x e y
· 所以 是 = ·
, j V1
=j(x) j(y), 到 V2 的同态 .
∈ ， y 则有 e x
e y ，即 j(x)
，所以
, j 是 V1 到 (2) " x,y R x
j(y) V2 的单射
（ 3） " y ∈ R
，有 x=lny ∈R , 所以 , j 是 V1 到 V2 的满射综上三点，所以 j 是 V1 到 V2 的同构映射 12、在自然推理系统 F 中，构造下面推理的证明：
任何人如果喜欢音乐就不喜欢体育。每个人或者喜欢体育或者喜欢美术。有的人不喜欢美术，因而有的人不喜欢音乐。 （个体域为人类集合）
命题符号化： F (x) ： x 喜欢音乐
G (x) ： x 喜欢体育
H (x) ： x 喜欢美术
前提： x(F ( x)
G ( x)) ， x(G ( x) H ( x))
结论：
x H ( x)
x F ( x)
证明：附加前提证明法
①
x H ( x)
附加前提引入
②
H (c)
EI 规则
③
x(G( x)
H ( x))
前提引入
④ G (c)
H (c)
UI 规则
⑤ G(c)
②④析取三段论
⑥x( F (x)G ( x))前提引入
⑦F (c)G (c)UI 规则
⑧ F (c)⑤⑦拒取
⑨x F (x)EG规则
13、设R 是 A 上的自反的和传递的，如下定义 A 上的关系T，使得
x, y A，x, y T x, y R y, x R 证明： T 是A 上的等价关系。
证明：因为R 具有自反性 ,所以对任意的x A ，x, x R 故x, x R x, x R x, x T
所以 T 具有自反性。
对任意的x, y T ，有
x, y T
x, y y, x y, x R
R
T
y, x
x, y
R
R
所以T 具有对称性；
利用R 具有传递性，若x, y,y, z T ，则x, y T y, z T
( (x, y
x, y
R y, x
R y, z
R) (
R) (
y, z
z, y
R
R
z, y
y, x
R)
R)
x, z R z, x R
x, z T
所以 T 具有传递性；
因为 T 具有自反性、对称性和传递性，所以R 是一个等价关系。
14、设 Z 为整数集合，在 Z 上定义二元运算如下：x, y Z , x y x y2
证明： Z 关于运算构成群。
证明：
因为对任意的 x, y Z ，有 x y 2Z ，所以整数集合Z 关于运算封闭。
对x, y, z Z 有
( x y) z( x y 2) z x y z4
x (y z)x ( y z 2) x y z4
故 (x y) z(x y)z ，即运算满足结合律。
2 Z ，且对任意的x Z 有 x22x x ，所以2是Z,的单位元。
对任意的 x Z 有4 x Z，且 x(4x) (4 x) x2，即 x 1 4 x 综合上述可知 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 去工作，
离散数学(大作业)与答案
一、请给出一个集合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答案
离散数学作业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章作业答案
第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
吉林大学2019-2020学年第一学期期末考试《离散数学》大作业参考答案
吉林大学网络教育学院2019-2020学年第一学期期末考试《离散数学》大作业 学生姓名专业 层次年级学号 学习中心成绩 年月日
作业完成要求：大作业要求学生手写，提供手写文档的清晰扫描图片，并将图片添加到word 文档内，最终wod文档上传平台，不允许学生提交其他格式文件（如JPG，RAR等非word 文档格式），如有雷同、抄袭成绩按不及格处理。 一、简答题（每小题7分，共56分） 1、什么是命题公式的演绎？ 答：首先定义了消解复杂性的两种范式:最简范式和文字范式,在此基础上采用演绎方法证明了L中的可判定性定理,并设计了命题公式的演绎判定算法P(F).P(F)的时间复杂度为O(n3),远远小于基于真值表法的O(2n)和基于策略方案HAL的O(n5)。 2、什么是子句？请给出一例。 答：子句是一组包含一个主词和一个动词的关连字。子句与片语有明显的不同，后者为一组不含主词与动词关系的关连字，如"in the morning" 或"running down the street" 或"having grown used to this harassment." 3、什么是短语？请给出一例。 答：短语是由句法、语义和语用三个层面上能够搭配的语言单位组合起来的没有句调的语言单位，又叫词组。它是大于词而又不成句的语法单位。简单的短语可以充当复杂短语的句法成分，短语加上句调可以成为句子。由语法上能够搭配的词组合起来的没有句调的语言单位 例如：粮食//丰收（名//动）（什么//怎么样） 4、什么是命题逻辑中的文字？ 答：检测和消除命题逻辑公式中的冗余文字,是人工智能领域广泛研究的基本问题。针对命题逻辑的子句集中子句的划分,结合冗余子句和冗余文字的概念,将命题逻辑的子句集中的文字分为必需文字、有用文字和无用文字3类。 5、什么是析取范式？请给出一例。 答：在离散数学中，仅由有限个文字构成的合取式称为简单合取式，而由有限个简单合取式构成的析取式称为析取范式。范式存在定理说明了它的存在性：任一命题公式都存在着与之等值的析取范式与合取范式。但它并不是惟一的。主析取范式是惟一的。
离散数学作业答案完整版
离散数学作业答案 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={
华南理工网络教育2018年离散数学大作业参考答案#试题
华南理工大学网络教育学院 2018–2019学年度第一学期 《离散数学》作业 1、用推理规则证明?（P∧?Q），?Q∨R，? R??P 证（1）?Q∨R P （2）? R P （3）?Q（1）（2）析取三段论 （4）?（P∧?Q）P （5）?P ∨ Q （4）等价转换 （6）?P （3）（5）析取三段论 2、用推理规则证明Q，?P → R，P → S，? S?Q∧R 证（1）P → S P （2）? S P （3）?P（1）（2）拒取式 （4）?P → R P （5）R （3）（4）假言推理 （6）Q P （7）Q∧R（5）（6）合取 3．设命题公式为?Q∧（P→Q）→?P。 （1）求此命题公式的真值表； （2）求此命题公式的析取范式； （3）判断该命题公式的类型。 解（1）真值表如下 P Q ?Q P→Q ?Q∧（P→Q）?P?Q∧（P→Q）→?P 0 0 1 1 1 1 1 0 1 0 1 0 1 1 1 0 1 0 0 0 1 1 1 0 1 0 0 1 （2）?Q∧（P→Q）→?P??（?Q∧（?P∨Q））∨?P ?（Q∨?（?P∨Q））∨?P??（?P∨Q）∨（Q∨?P）?1（析取范式）?（?P∧?Q）∨（?P∧Q）∨（P∧?Q）∨（P∧Q）（主析取范式） （3）该公式为重言式 4．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。
令F(x)：x喜欢步行。G(x)：x喜欢坐汽车。H(x)：x喜欢骑自行车。 解前提：?x（F（x）→? G（x）），?x（G（x）∨H（x））， ? x? H（x）。 结论：? x ?F（x）。 证(1)? x ?H（x）P (2)?H（c）ES(1) (3)?x（G（x）∨H（x））P (4) G（c）∨H（c）US(3) (5) G（c）T(2，4)I (6)?x（F（x）→? G（x））P (7)F（c）→? G（c）US(6) (8)? F（c）T(5,7)I (9)（?x）? F（x）EG(8) 5．用直接证法证明： 前提：（?x）（C（x）→W（x）∧R（x）），（?x）（C（x）∧Q（x）） 结论：（?x）（Q（x）∧R（x））。 证(1)（?x）（C（x）∧Q（x））P (2)C（c）∧Q（c）ES(1) (3)（?x）（C（x）→W（x）∧R（x））P (4) C（c）→W（c）∧R（c）US(3) (5) C（c）T(2)I (6)W（c）∧R（c）T(4,5)I (7)R（c）T(6)I (8)Q（c）T(2)I (9)Q（c）∧R（c）T(7,8)I (10) （?x）（Q（x）∧R（x））EG(9) 6．设R是集合A = {1, 2, 3, 4, 5, 6, 7, 8, 9}上的整除关系。 （1）给出关系R；（2）画出关系R的哈斯图； （3）指出关系R的最大、最小元，极大、极小元。 解R={<1,2>,<1,3>,<1,4>,<1,5>,<1,6>，<1,7>,<1,8>,<1,9>,<2,4>,<2,6>，<2,8>，<3,6>，<3,9>，<4,8>}∪I A COV A={<1,2>,<1,3>,<1,5>,<1,7>,<2,4>,<2,6>，<3,6>，<3,9>，<4,8>} 作哈斯图如右： 极小元和最小元为1； 极大元为5,6,7,8,9, 无最大元 8
离散数学作业标准答案
离散数学作业 一、选择题 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秋课件作业【离散数学】及答案
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纸打印出来，手工书写答题，字迹工整，解答题要有 解答过程，要求本学期第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={
吉大网院 离散数学 大作业及答案 201903
一、简要回答下列问题（每小题5分，共30分） 1、请给出集合的吸收率。 2、设A={1，2}，请给出A上的所有关系。 答：集合A上的全部关系有2^(2^2)=16种：空关系{}，全关系 {<1,1>,<1,2>,<2,1>,<2,2>}{<1,1>}{<2,2>}{<1,2>}{<2,1>}{<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,1>,<2,1>,<2,2>}{<1,2>,<2,1>,<2,2>} 3、什么是子句？请给出一例。 答：子句集S称为是可满足的，如果存在一个个体域和一种解释，使S中的每一个子句均为真，或者使得S的每一个子句中至少有一个文字为真。否则, 称子句集S是不可满足的 4、什么是前束范式？ 答：前束范式亦称前束式，一种谓词演算公式。指其一切量词都未被否定地处于公式的最前端且其辖域都延伸至公式的末端的谓词演算公式。设Q∈{?，?}，一个公式α是前束范式，当且仅当存在一个不含量词的公式β，使得 α=(Q?x?)(Q?x?)…(Q?x?)β. 5、什么是谓词逻辑中的项？ 答：谓词逻辑中的项指变项和常项，变项又分为自由变项和约束变项。 6、什么是命题公式的演绎？ 答：用A'表示非A,则 (A+B)'=A'B', (AB)'=A'+B'. 二、设A是m元集合，B是n元集合。问A到B共有多少个不同的二元关系？设A={a，b}，B={1， 2}，试写出A到B上的全部二元关系。（8分） 答：解：A 到B 上共有2mn 个二元关系。本题中A×B 的全部子集φ，{(a,1)}，{(a,2)}，{(b,1)}， {(b,2)}， {(a,1),(a,2)}，{(a,1),(b,1)}，{(a,1),(b,2)}，{(a,1),(b,2)}，{(a,2),(b,1)}，{(a,2),(b,2)}， {(a,1),(a,2),(b,1)}，{(a,1),(a,2),(b,2)}，{(a,1),(b,1),(b,2)}，{(a,2),(b,1),(b,2)}，{(a,1),(a,2),(b,1),(b,2)}为A 到B 的全部二元关系。 三、R，S是集合A上的两个关系。试证明下列等式：（10分） （1）(R?S)-1= S-1?R-1 （2）(R-1)-1= R 证明：先证(R?S)--1?R-1，对任意(x，-1，则(y，，则存在，满足(y，且(a，，那么(x，-1且(a，-1，
吉林大学离散数学课后习题答案
第一章集合论基础 §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，