《离散数学》作业
《离散数学》作业
一、选择或填空
1．下列公式中哪些是永真式？( B C D )
A.(┐P∧Q)→(Q→?R)
B.P→(Q→Q)
C.(P∧Q)→P
D.P→(P∨Q)
2．设全体域D是正整数集合，确定下列命题的真值：
A. ?x?y (xy=y) (F )
B. ?x?y(x+y=y) ( F )
C. ?x?y(x+y=x) ( F )
D. ?x?y(y=2x) ( T )
3．有n个结点的树，其结点度数之和是( 2n-2 )。
4．举出集合A上的既是等价关系又是偏序关系的一个例子。( I A )
5．群
6．下面给出的集合中，哪一个不是前缀码( A )。
A. {a，ab，110，a1b11}
B. {01，001，000，1}
C. {1，2，00，01，0210}
D. {12，11，101，002，0011}
7．下列哪些公式为永真蕴含式？( A D )
A.?Q=>Q→P
B.?Q=>P→Q
C.P=>P→Q
D.?P∧(P∨Q)=>?P
8．设P：我生病，Q：我去学校，则下列命题可符号化为( (1) P→?Q (2) P??Q )。
（1）若我生病，则我不去学校 (2) 当且仅当我生病时，我才不去学校
9．任一有向图中，度数为奇数的结点有( 偶数)个。
10．集合A上的等价关系的三个性质是什么？( 自反性、对称性和传递性 )
11．群＜A,*＞的等幂元有( 1 )个，是( 单位元)，零元有( 0 )个。
12．一个图的欧拉回路是一条通过图中( 所有边一次且恰好一次 )的回路。
13．设有下列公式，请问哪几个是永真蕴涵式?( B C D E F )
A.P=>P∧Q
B. P∧Q=>P
C. P∧Q=>P∨Q
D.P∧(P→Q)=>Q
E. ?(P→Q)=>P
F. ?P∧(P∨Q)=>?P
14．判断下列命题哪几个为正确？( B D )
A. {Ф}∈{Ф，{{Ф}}}
B. {Ф}?{Ф，{{Ф}}}
C. Ф∈{{Ф}}
D. Ф?{Ф}
E. {a,b}∈{a,b,{a},{b}}
15．设a是10阶群的生成元，则a4是( 5 )阶元素，a3是( 10 )阶元素。
16．设G是一个哈密尔顿图，则G一定是( D )。
A. 欧拉图
B. 树
C. 平面图
D. 连通图
17．设G是一棵树，则G 的生成树有( B )棵。
A. 0
B. 1
C. 2
D. 不能确定
18．设无向图G有16条边且每个顶点的度数都是2，则图G有(D )个顶点。
A. 10
B. 4
C. 8
D. 16
19．Ａ，Ｂ，Ｃ是三个集合，则下列哪几个推理正确：(A)
A. A?B，B?C=> A?C
B. A?B，B?C=> A∈B
C. A∈B，B∈C=> A∈C
20．设S={１，２，３，４}，Ａ上的关系Ｒ＝｛〈1，2〉，〈2，1〉，〈2，3〉，〈3，4〉｝，求(1)R R (2) R-1。
（1）R R={ 〈1，1〉，〈1，3〉，〈2，2〉，〈2，4〉}
（2）Ｒ-1＝｛〈1，2〉，〈2，1〉，〈3，2〉，〈4，3〉｝
21．一棵无向树的顶点数n与边数m关系是( m=n-1 )。
22．设A={3，6，9}，A上的二元运算*定义为：a*b=min{a，b}，则在独异点
23．设G是有n个结点m条边的连通平面图，且有k个面，则k等于:( A )
A. m-n+2
B. n-m-2
C. n+m-2
D. m+n+2。
24．设无向图G有18条边且每个顶点的度数都是3，则图G有( D )个顶点。
A. 10
B. 4
C. 8
D. 12
25、A，B，C是三个集合，则下列哪个推理正确?( 1 )
(1) A?B，B?C ?A?C
(2) A?B，B?C ?A∈B
(3) A∈B，B∈C ?A∈C
26、判断下列命题哪个正确?( 2 )
(1) {Ф}∈{Ф,{{Ф}}} (2) {Ф}?{Ф,{{Ф}}
(3) Ф∈{{Ф}} (4) Ф={Ф}
27、设T是一棵树，则T是一个( 3 ).
(1) 欧拉图(2) 哈密尔顿图(3) 连通图
28、下列公式中哪个不是蕴涵式?( 1 )
(1) P?P∧Q (2) P∧Q?P
(3) P∧Q?P∨Q (4) P∧(P→Q)?Q
39、下面给出的集合中，哪一个不是前缀码( 1 ).
(1) {a，ab，110，a1b11} (2) {01，001，000，1}
(3) {1，2，00，01，0210} (4) {12，11，101，002，0011}
30 6阶有限群的任何子群一定不是( 3 ).
(1) 2阶(2) 3 阶(3) 4 阶(4) 6 阶
31、在有n个顶点的连通图中，其边数( 2 ).
(1) 最多有n-1条(2) 至少有n-1 条
(3) 最多有n条(4) 至少有n 条
32、下列哪一种图不一定是树?( 3 )
(1) 无简单回路的连通图(2) 有n个顶点n-1条边的连通图
(3) 每对顶点间都有通路的图(4) 连通但删去一条边便不连通的图
33、下面给出的集合中，哪一个是前缀码?(2)
(1) {0，10，110，101111}(2) {01，001，000，1}
(3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011}
34、有限布尔代数的元素的个数一定等于( 4 ).
(1) 偶数(2) 奇数(3) 4的倍数(4) 2的正整数次幂
35、在自然数集N上，下列哪种运算是可结合的?( 2 )
(1) a*b=a-b(2) a*b=max{a,b}(3) a*b=a+2b(4) a*b=|a-b|
36、判断下列命题哪个为真?( 1 )
(1) A-B=B-A ?A=B (2) 空集是任何集合的真子集
(3) 空集只是非空集合的子集(4) 若A的一个元素属于B，则A=B
二、求下列各公式的主析取范式和主合取范式
1．P∨?Q
解：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（主合取范式）
?（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（主合取范式）
?(?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∧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（主析取范式）
?(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（主合取范式）
?(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）（主析取范式）
7 (P→Q)∧(P→R)
解：(P→Q)∧(P→R)
?(?P∨Q)∧(?P∨R) (合取范式)
?(?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)∧(P→R)
?(?P∨Q)∧(?P∨R)
??P∨(Q∧R)(合取范式)
?(?P∧(Q∨?Q)∧(R∨?R))∨((?P∨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∧?Q∧R)∨(?P∧Q∧?R)∨(?P∧?Q?R)∨(P∧Q∧R) (主析取范式)
三、证明
1．P∨Q， P→R, Q→S => R∨S
证明：（1）?R 附加前提
（2） P→R 前提
（3）?P （1），（2）
（4） P∨Q 前提
（5） Q （3），（4）
（6） Q→S 前提
（7） S （5），（6）
（8） R∨S CP，（1），（8）
2．A→(C∨B)，B→?A，D→?C => A→?D
证明：（1） A 附加前提
（2）A→(C∨B) 前提
（3）C∨B （1），（2）
（4）B→?A 前提
（5）?B （1），（4）
（6） C （3），（5）
（7）D→?C 前提
（8）?D （6），（7）
（9）A→?D CP，（1），（8）
3．P→Q，?Q∨R，?R，?S∨P=>?S
证明：
（1）?R 前提
（2）?Q∨R 前提
（3）?Q （1），（2）
（4）P→Q 前提
（5）?P （3），（4）
（6）?S∨P 前提
（7）?S （5），（6）
4．?B∨D，(E→?F)→?D，?E=>?B
证明：
（1） B 附加前提
（2）?B∨D 前提
（3） D （1），（2）
（4）(E→?F)→?D 前提
（5）?(E→?F) （3），（4）
（6）E∧?F （5）
（7） E （6）
（8）?E 前提
（9） E∧?E （7），（8）
5．A→(B→C)，C→(?D∨E)，?F→(D∧?E),A=>B→F 证明：
（1） A 前提
（2） A→(B→C) 前提
（3）B→C （1），（2）
（4）B 附加前提
（5）C （3），（4）
（6）C→(?D∨E) 前提
（7）?D∨E （5），（6）
(8)?F→(D∧?E) 前提
(9)F （7），（8）
(10)B→F CP，（4），（9）
6、A→(B→C)，C→(?D∨E)，?F→(D∧?E),A ?B→F.
证明：
(1) A 前提
(2) A→(B→C) 前提
(3) B→C （1），（2）
(4) B 附加前提
(5) C （3），（4）
(6) C→(?D∨E) 前提
(7) ?D∨E （5），（6）
(8) ?F→(D∧?E) 前提
(9) F （7），（8）
(10) B→F CP
7、?B∨D，(E→?F)→?D，?E ??B.
证明：
(1) B 附加前提
(2) ?B∨D 前提
(3) D （1），（2）
(4) (E→?F)→?D 前提
(5) ?(E→?F) （3），（4）
(6) E∧?F （5）
(7) E （6）
(8) ?E 前提
(9) E∧?E （7），（8）
8、A→(C∨B)，B→?A，D→?C ?A→?D.
证明：
（1） A 附加前提
(2) A→(C∨B) 前提
(3) C∨B （1），（2）
(4) B→?A 前提
(5) ?B （1），（4）
(6) C （3），（5）
(7) D→?C 前提
(8) ?D （6），（7）
(9) A→?D CP，（1），（8）
9、P→?Q，Q∨?R，R∧?S ??P.
证明、
(1) P 附加前提
（2）P→?Q 前提
（3）?Q （1），（2）
（4）Q∨?R 前提
(5) ?R （3），（4）
(6 ) R∧?S 前提
（7）R （6）
（8）R∧?R （5），（7）
四、设Ａ，Ｂ，Ｃ是三个集合，证明
1．(A－B)∪(A－C)=A－(B∩C)
B?= A-(B∩C)
证明： (A-B)?(A-C)=(A∩B)?(A∩C) =A∩(B?C)=A∩C
2．A∩B=A∩C，A∩B=A∩C，则C=B
证明：
B=B∩(A?A)=(B∩A)?(B∩A) =(C∩A)?(C∩A)=C∩(A?A)=C
3．A∩(B－C)＝(A∩B)－(A∩C)
证明：
A?=(A∩B) ∩（A?C）=(A∩B∩A)?(A∩B∩C) (A∩B)－(A∩C)= (A∩B) ∩C
= A∩B∩C=A∩（B∩C）=A∩（B-C）
4．A－(B∪C)＝(A－B)－C
证明：
B?=A∩(B?C)=(A∩B)∩C= (A-B)∩C=(A-B)-C
A－(B?C)= A∩C
5．(A－B)∩(A－C)=A－(B∪C)
证明：
B?=A－(B∪C)
（A-B）∩(A－C)=(A∩B)∩(A∩C)=(A∩A)∩(B∩C)= A∩C
五、证明
1．设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e≠0。
证明：
用反证法证明。假设e=0。
对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元，
则a=a*e=a*0=0。即A的所有元素都等于0,这与已知条件|A|>1矛盾。
从而假设错误。
2．任一图中度数为奇数的结点是偶数个。
证明：
设G=〈V,E〉是任一图。设|V|=n。
deg(v)=2|E|可得，图中所有结点度数之和是偶数。显然所有偶数度结点的度数由欧拉握手定理可得∑
v
∈V
之和仍为偶数，从而所有奇数度结点的度数之和也是偶数。因此，图中度数为奇数的结点一定为偶数个。
3．设群＜G ，＊＞除单位元外每个元素的阶均为2，则＜G ，＊＞是交换群。 证明：
对任一a ∈G ，由已知可得a*a=e ，即a -1
=a 。
对任一a,b ∈G ，因为a*b=(a*b)-1
=b -1
*a -1
=b*a ，所以运算*满足交换律。
从而＜G,*＞是交换群。
4．在一个连通简单无向平面图G=〈V ，E ，F 〉中若|V|≥3，则 |E|≤3|V －6。 证明：
因为|V|≥3，且G=〈V,E,F 〉是一个连通简单无向平面图， 所以对任一f ∈F ，deg(f)≥3。 由公式
∑
∈F
f deg(f)=2|E|可得，2|E|≥3|F|。
再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+3
2
|E|≥2。 所以|E|≤3|V|－6。 5．单位元有惟一逆元。 证明：
设
因为e 是关于运算*的单位元，所以e 1=e 1*e=e=e 2*e=e 2。 即单位元有惟一逆元。
6．设
因为a -1
*b ∈G ，且a*(a -1
*b)=(a*a -1
)*b=e*b=b ，所以对于a,b ∈G ，必有x=a-1*b ∈G ，使得a *x=b 。
若x 1,x 2都满足要求。即a *x 1=b 且a *x 2=b 。故a *x 1=a *x 2。 由于*满足消去律，故x 1=x 2。
从而对于a,b ∈G ，必有唯一的x ∈G ，使得a *x=b 。 7．设代数系统
设e 是该群的单位元。若a 是
8．若连通简单无向平面图G 有n 个结点，m 条边，k 个面，且每个面至少由k(k ≥3)条边围成，则 m ≤k(ｎ－
2)／(ｋ－2)。 证明：
设连通简单无向平面图G=〈V,E,F 〉，则|V|=n,|E|=m,|F|=p 。 由已知对任一f ∈F, deg(f)≥k 。
由公式
∑
∈F
f deg(f)=2|E|可得，2|E|≥k|F|。
再由欧拉公式|V|-|E|+|F|=2可得|V|-|E|+k
2
|E|≥2。 即k(n-2)≥(k-2)m 。
所以m ≤k(ｎ－2)／(ｋ－2)。
9．证明在元素不少于两个的群中不存在零元。 证明：（用反证法证明）
设在群
因为
设
对G 中任一非单位元a 。设a 的阶为k,则k ≠1。
由拉格朗日定理，k 是p 的正整因子。因为p 是素数，故k=p 。 即a 的阶就是p ，即群G 的阶。故a 是G 的生成元。
11．设G=〈V ，E 〉是一个连通且|V|=|E|+1的图，则G 中有一个度为1的结点。 证明：（用反证法证明）
设|V|=n ，则|E|=n-1。 由欧拉握手定理可得
∑
∈V
v deg(v)=2|E|=2n-2。
因为G 连通，所以?v ∈V ，deg(v)≥1。假设G 中没有1片树叶，则∑
∈V
v deg(v)≥2n>2n-2。
得出矛盾。 12．给定无向连通简单平面图G=
证明：
因为|V|=6≥3，且G=〈V,E,F 〉是一个连通简单无向平面图， 所以对任一f ∈F ，deg(f)≥3。 由欧拉公式|V|-|E|+|F|=2可得|F|=8。 再由公式
∑
∈F
f deg(f)=2|E|，
∑
∈F
f deg(f)=24。
因为对任一f ∈F ，deg(f)≥3，故要使上述等式成立， 对任一f ∈F ，deg(f)=3。 13．证明在一个群中单位元是惟一的。 证明：
设e 1,e 2都是群〈G,*〉的单位元, 则e 1=e 1*e 2=e 2。 所以单位元是惟一的。 14．在一个群〈G ，*〉中，若G 中的元素a 的阶是k ，即 | a |=k ，则a -1
的阶也是k 。 证明：
因为| a |=k ，所以a k
=e 。即（a -1
）k
=(a k )-1
=e 。 从而a -1
的阶是有限的，且|a -1
|≤k 。
同理可证，a的阶小于等于|a-1|。
故a-1的阶也是k。
15．若有n个结点的连通图中恰有n-1 条边，则图中至少有一个结点度数为1。
证明：（用反证法证明）
设G=〈V,E〉有n-1条边且|V|=n-1。
deg(v)=2|E|=2n-2。
由欧拉握手定理可得∑
∈V
v
因为G是连通图，所以G中任一结点的度数都大于等于1。
deg(v)≥2n>2n-2。
假设G中不存在度数为1 的结点，则G中任一结点的度数都大于等于2.故∑
v
∈V
得出矛盾。
16、设e和0是关于A上二元运算*的单位元和零元，如果|A|>1，则e≠0.
证明：
（用反证法证明）假设e=0.
对A的任一元素a，因为e和0是A上关于二元运算*的单位元和零元，
则a=a*e=a*0=0. 即A的所有元素都等于0,这与已知条件|A|>1矛盾.
从而假设错误. 即e≠0.
17、设T=
证明：
（用反证法证明）设|V|=n.
因为T=〈V,E〉是一棵树，所以|E|=n-1.
deg(v)=2|E|=2n-2.
由欧拉握手定理可得∑
v
∈V
deg(v)≥2(n-1)+1>2n-2.
假设T中最多只有1片树叶，则∑
∈V
v
得出矛盾。
18、若n阶连通图中恰有n-1 条边，则图中至少有一个顶点度数为1.
证明：
（用反证法证明）设G=
deg(v)=2|E|=2n-2.
由欧拉握手定理可得∑
∈V
v
因为G 是连通图，所以G 中任一顶点的度数都大于等于1.
假设G 中不存在度数为1 的顶点，则G 中任一顶点的度数都大于等于2. 故∑
∈V
v deg(v)≥
2n>2n-2.
得出矛盾.
19、证明对于连通无向简单平面图，当边数e ＜30时，必存在度数≤4的顶点.
证明：
若顶点个数小于等于3时，结论显然成立.
当顶点多于3 个时，用反证法证明. 记|V|=n,|E|=m,|F|=k. 假设图中所有顶点的度数都大于等于5. 由欧拉握手定理得
∑
∈V
v deg(v)=2|E|得 5n ≤2m.
又因为G=〈V ,E,F 〉是一个连通简单无向平面图，所以对每个面f ，deg(f)≥3. 由公式
∑
∈F
f deg(f)=2|E|可得，2m ≥3k.
再由欧拉公式|V|-|E|+|F|=2可得2≤52m-m+32m=15
1m 从而30≤m ，这与已知矛盾.
离散数学作业
第一章命题逻辑的基本概念 一、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）你去图书馆吗？ （7）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子?显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则3≥2。 （3）只有2<1，才有3≥2。 （4）除非2<1，才有3≥2。 （5）除非2<1，否则3≥2。 （6）2<1仅当3<2。 三、将下列命题符号化 (1)小丽只能从筐里拿一个苹果或一个梨。 (2)王栋生于1992年或1993年。 - 1 -
四、设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。（1）p∨(q∧r) （2）（p?r）∧(﹁q∨s) （3）（?p∧?q∧r）?(p∧q∧﹁r) (4)（?r∧s）→(p∧?q) 五．判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2也是无理数。另外6能被2整除，6才能被4整除。” 六、用真值表判断下列公式的类型： (1) p∧(p→q)∧(p→?q) (2) (p∧r) ?(?p∧?q) (2)((p→q) ∧(q→r)) →(p→r) - 2 -
第二章命题逻辑等值演算 一、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ?(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 二、用等值演算法证明下面等值式 (1)(p→q)∧(p→r)?(p→(q∧r)) (2)(p∧?q)∨(?p∧q)?(p∨q) ∧?(p∧q) - 3 -
离散数学 第1章 习题解答
习题 1. 下列句子中，哪些是命题哪些不是命题如果是命题，指出它的真值。 ⑴中国有四大发明。 ⑵计算机有空吗 ⑶不存在最大素数。 ⑷21+3＜5。 ⑸老王是山东人或河北人。 ⑹2与3都是偶数。 ⑺小李在宿舍里。 ⑻这朵玫瑰花多美丽呀! ⑼请勿随地吐痰! ⑽圆的面积等于半径的平方乘以。 ⑾只有6是偶数，3才能是2的倍数。 ⑿雪是黑色的当且仅当太阳从东方升起。 ⒀如果天下大雨，他就乘班车上班。 解：⑴⑶⑷⑸⑹⑺⑽⑾⑿⒀是命题，其中⑴⑶⑽⑾是真命题，⑷⑹⑿是假命题，⑸⑺⒀的真值目前无法确定；⑵⑻⑼不是命题。 2. 将下列复合命题分成若干原子命题。 ⑴李辛与李末是兄弟。 ⑵因为天气冷，所以我穿了羽绒服。 ⑶天正在下雨或湿度很高。 ⑷刘英与李进上山。 ⑸王强与刘威都学过法语。 ⑹如果你不看电影，那么我也不看电影。 ⑺我既不看电视也不外出，我在睡觉。 ⑻除非天下大雨，否则他不乘班车上班。 解：⑴本命题为原子命题； ⑵p：天气冷；q：我穿羽绒服； ⑶p：天在下雨；q：湿度很高； ⑷p：刘英上山；q：李进上山； ⑸p：王强学过法语；q：刘威学过法语； ⑹p：你看电影；q：我看电影； ⑺p：我看电视；q：我外出；r：我睡觉； ⑻p：天下大雨；q：他乘班车上班。 3. 将下列命题符号化。 ⑴他一面吃饭，一面听音乐。 ⑵3是素数或2是素数。 ⑶若地球上没有树木，则人类不能生存。
⑷8是偶数的充分必要条件是8能被3整除。 ⑸停机的原因在于语法错误或程序错误。 ⑹四边形ABCD是平行四边形当且仅当它的对边平行。 ⑺如果a和b是偶数，则a+b是偶数。 解：⑴p：他吃饭；q：他听音乐；原命题符号化为：p∧q ⑵p：3是素数；q：2是素数；原命题符号化为：p∨q ⑶p：地球上有树木；q：人类能生存；原命题符号化为：p→q ⑷p：8是偶数；q：8能被3整除；原命题符号化为：pq ⑸p：停机；q：语法错误；r：程序错误；原命题符号化为：q∨r→p ⑹p：四边形ABCD是平行四边形；q：四边形ABCD的对边平行；原命题符号化为：pq。 ⑺p：a是偶数；q：b是偶数；r：a+b是偶数；原命题符号化为：p∧q→r 4. 将下列命题符号化，并指出各复合命题的真值。 ⑴如果3+3=6，则雪是白的。 ⑵如果3+3≠6，则雪是白的。 ⑶如果3+3=6，则雪不是白的。 ⑷如果3+3≠6，则雪不是白的。 ⑸3是无理数当且仅当加拿大位于亚洲。 ⑹2+3=5的充要条件是3是无理数。(假定是10进制) ⑺若两圆O1，O2的面积相等，则它们的半径相等，反之亦然。 ⑻当王小红心情愉快时，她就唱歌，反之，当她唱歌时，一定心情愉快。 解：设p：3＋3＝6。q：雪是白的。 ⑴原命题符号化为：p→q；该命题是真命题。 ⑵原命题符号化为：p→q；该命题是真命题。 ⑶原命题符号化为：p→q；该命题是假命题。 ⑷原命题符号化为：p→q；该命题是真命题。 ⑸p：3是无理数；q：加拿大位于亚洲；原命题符号化为：pq；该命题是假命题。 ⑹p：2+3＝5；q：3是无理数；原命题符号化为：pq；该命题是真命题。 ⑺p：两圆O1,O2的面积相等；q：两圆O1,O2的半径相等；原命题符号化为：pq；该命题是真命题。 ⑻p：王小红心情愉快；q：王小红唱歌；原命题符号化为：pq；该命题是真命题。 习题
离散数学作业答案
离散数学作业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)
离散数学第1章习题答案
#include
N=N/2; } while(!Empty(S)) { Pop(S,&e); printf("%d ",e); } } void main() { int n; printf("请输入待转换的值n：\n"); scanf ("%d",&n); conversion(n); }习题 1.判断下列语句是否是命题，为什么？若是命题，判断是简单命题还是复合命题？ (1)离散数学是计算机专业的一门必修课。 (2)李梅能歌善舞。 (3)这朵花真美丽！ (4)３＋２＞６。 (5)只要我有时间，我就来看你。 (6)x＝５。 (7)尽管他有病，但他仍坚持工作。 (8)太阳系外有宇宙人。 (9)小王和小张是同桌。 (10)不存在最大的素数。 解在上述10个句子中，(3)是感叹句，因此它不是命题。(6)虽然是陈述句，但它没有确定的值，因此它也不是命题。其余语句都是可判断真假的陈述句，所以都是命题。其中：(1)、(4) 、(8) 、(9) 、是简单命题，、(2) 、(5) 、(7)、(10) 是复合命题。 2.判断下列各式是否是命题公式，为什么？ (1)(P→(P∨Q))。 (2)(?P→Q)→(Q→P)))。 (3)((?P→Q)→(Q→P))。 (4)(Q→R∧S)。 (5)(P∨QR)→S。 (6)((R→(Q→R)→(P→Q))。 解 (1)是命题公式。 (2)不是命题公式，因为括号不配对。 (3)是命题公式。 (4)是命题公式。
《离散数学》及答案
《离散数学》+答案 一、选择或填空: 1、下列哪些公式为永真蕴含式？( ) (1)?Q=>Q→P (2)?Q=>P→Q (3)P=>P→Q (4)?P∧(P∨Q)=>?P 答：在第三章里面有公式（1）是附加律，（4）可以由第二章的蕴含等值式求出（注意与吸收律区别） 2、下列公式中哪些是永真式？( ) (1)(┐P∧Q)→(Q→?R) (2)P→(Q→Q) (3)(P∧Q)→P (4)P→(P∨Q) 答：（2），（3），（4）可用蕴含等值式证明 3、设有下列公式，请问哪几个是永真蕴涵式?( ) (1)P=>P∧Q (2) P∧Q=>P (3) P∧Q=>P∨Q (4)P∧(P→Q)=>Q (5) ?(P→Q)=>P (6) ?P∧(P∨Q)=>?P 答：（2）是第三章的化简律，（3）类似附加律，（4）是假言推理，（3），（5），（6）都可以用蕴含等值式来证明出是永真蕴含式 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z（考察定义在公式?x A和?x A中，称x为指导变元，A为量词的辖域。在?x A和?x A的辖域中，x的所有出现都称为约束出现，即称x为约束变元，A中不是约束出现的其他变项则称为自由变元。于是A(x)、B(y，x)和?z C(y，z)中y为自由变元，x和z为约束变元，在D(x)中x为自由变元） 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1)北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是（4）是，T （5）不是（6） 44
离散数学作业(2)
离散数学作业布置 第1次作业（P15） 1.16 设p、q的真值为0；r、s的真值为1，求下列各命题公式的真值。 解：（1）p∨(q∧r)=0∨(0∧1)=0 （2）（p?r）∧(﹁q∨s)=（0?1）∧(1∨1)=0∧1 =0 （3）（﹁p∧﹁q∧r）?(p∧q∧﹁r)=（1∧1∧1）? (0∧0∧0)=0 (4)（r∧s）→(p∧q)=（0∧1）→(1∧0)=0→0=1 1.17 判断下面一段论述是否为真：“π是无理数。并且，如果3是无理数，则2 也是无理数。另外只有6能被2整除，6才能被4整除。” 解：p: π是无理数 1 q: 3是无理数0 r: 2是无理数 1 s:6能被2整除 1 t: 6能被4整除0 命题符号化为：p∧(q→r)∧(t→s)的真值为1，所以这一段的论述为真。 1.19 用真值表判断下列公式的类型： （4）(p→q) →(﹁q→﹁p) （5）(p∧r) ? (﹁p∧﹁q) （6）((p→q) ∧(q→r)) →(p→r) 解：（4） p q p→q q p q→p (p→q)→( q→p) 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 0 0 1 1 1 1 0 0 1 1 所以公式类型为永真式，最后一列全为1 （5）公式类型为可满足式（方法如上例），最后一列至少有一个1 （6）公式类型为永真式（方法如上例，最后一列全为1）。 第2次作业（P38） 2.3 用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出成真赋值. (1) ﹁(p∧q→q) (2)(p→(p∨q))∨(p→r) (3)(p∨q)→(p∧r) 解：(1) ﹁(p∧q→q) ?﹁(﹁(p∧q) ∨q) ?(p∧q) ∧﹁q?p∧(q ∧﹁q) ? p∧0 ?0 所以公式类型为矛盾式 (2)（p→(p∨q)）∨(p→r) ? (﹁p∨(p∨q))∨(﹁p∨r) ?﹁p∨p∨q∨r?1 所以公式类型为永真式 (3) (p∨q) → (p∧r) ?￢(p∨q) ∨ (p∧r) ? (￢p∧￢q) ∨(p∧r) 易见, 是可满足式, 但不是重言式. 成真赋值为: 000,001, 101, 111
离散数学作业答案
第一章 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．下列语句中不是命题的有（ ）. A 9+5≤12 B. 1+3=5 C. 我用的电脑CPU 主频是1G 吗D.我要努力学习。 2. 下列语句是真命题为( )． A. 1+2=5当且仅当2是偶数 B. 如果1+2=3，则2是奇数 C. 如果1+2=5，则2是奇数 D. 你上网了吗 3. 设命题公式)(r q p ∧→?,则使公式取真值为1的p ，q ，r 赋值分别是 ( ) 0,0,1)D (0 ,1,0)C (1 ,0,0)B (0 ,0,0)A ( 4. 命题公式q q p →∨ )(为 ( ) (A) 矛盾式 (B) 仅可满足式 (C) 重言式 (D) 合取范式 5. 设p:我将去市里,q ：我有时间． 命题“我将去市里，仅当我有时间时”符号化为为( ) q p q p q p p q ?∨??→→)D ()C ()B ()A (6．设P ：我听课,Q ：我看小说. “我不能一边听课，一边看小说”的符号为（ ） A. Q P ?→ ； B. Q P →?； C. P Q ?∧? ； D. )(Q P ∧? 二、判断下列语句是否是命题，若是命题是复合命题则请将其符号化 （1）中国有四大发明。 （2）2是有理数。 （3）“请进！” （4）刘红和魏新是同学。 （5）a+b （6）如果买不到飞机票，我哪儿也不去。 （8）侈而惰者贫，而力而俭者富。（韩非：《韩非子显学》） （9）火星上有生命。 （10）这朵玫瑰花多美丽啊！ 二、将下列命题符号化，其中p:2<1,q:3<2 （1）只要2<1，就有3<2。 （2）如果2<1，则32。 （3）只有2<1，才有32。 （4）除非2<1，才有32。 （5）除非2<1，否则32。
离散数学课后答案
离散数学课后答案 习题一 6.将下列命题符号化。 （1）小丽只能从框里那一个苹果或一个梨. （2）这学期，刘晓月只能选学英语或日语中的一门外语课. 答： （1）（p Λ?q ）ν（?pΛq）其中p:小丽拿一个苹果，q:小丽拿一个梨（2）（p Λ?q ）ν（?pΛq）其中p:刘晓月选学英语，q:刘晓月选学日语 14.将下列命题符号化. (1) 刘晓月跑得快, 跳得高. (2)老王是山东人或河北人. (3)因为天气冷, 所以我穿了羽绒服. (4)王欢与李乐组成一个小组. (5)李辛与李末是兄弟. (6)王强与刘威都学过法语. (7)他一面吃饭, 一面听音乐. (8)如果天下大雨, 他就乘班车上班. (9)只有天下大雨, 他才乘班车上班. (10)除非天下大雨, 他才乘班车上班. (11)下雪路滑, 他迟到了. (12)2与4都是素数, 这是不对的. (13)“2或4是素数, 这是不对的”是不对的. 答： (1)p∧q, 其中, p: 刘晓月跑得快, q: 刘晓月跳得高. (2)p∨q, 其中, p: 老王是山东人, q: 老王是河北人. (3)p→q, 其中, p: 天气冷, q: 我穿了羽绒服. (4)p, 其中, p: 王欢与李乐组成一个小组, 是简单命题. (5)p, 其中, p: 李辛与李末是兄弟. (6)p∧q, 其中, p: 王强学过法语, q: 刘威学过法语. (7)p∧q, 其中, p: 他吃饭, q: 他听音乐. (8)p→q, 其中, p: 天下大雨, q: 他乘班车上班. (9)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (10)p→q, 其中, p: 他乘班车上班, q: 天下大雨. (11)p→q, 其中, p: 下雪路滑, q: 他迟到了. (12) ? (p∧q)或?p∨?q, 其中, p: 2是素数, q: 4是素数. (13) ? ? (p∨q)或p∨q, 其中, p: 2是素数, q: 4是素数. 16. 19.用真值表判断下列公式的类型: (1)p→ (p∨q∨r) (2)(p→?q) →?q
离散数学作业
离散数学作业 软件0943 张凌晨38 李成16 1.设S={1,2,3,4}，定义S上的二元运算*如下： x*y=(xy) mod 5任意x,y属于S 求运算*的运算表. 解(xy) mod 5表示xy除以5的余数，所以运算表如下： 2.设*为Z+上的二元运算，任意x,y属于Z+， x*y=min(x,y),即x和y之中的较小数. (1)求4*6,7*3. (2)*在Z+上是否满足交换律、结合律和幂等律？ (3)求*运算的单位元、零元及Z+中所有可逆元素的逆元.
解 (1)由题得：4*6=min(4,6)=4； 7*3=min(7,3)=3. (2)由题分析知： *运算是取x和y之中的较小数，即x和y调换位置不影响结果，所以*在Z+上满足交换律. *运算满足结合律，因为任意x,y属于Z+，有 (x*y)*z=min(x,y)*z=min(min(x,y),z) x*(y*z)=x*min(y,z)=min(x,min(y,z)) 无论x,y,z三数中哪个较小，*运算的最终结果都是较小的那个，所以满足结合律. *运算满足幂等律，因为在Z+上任意 x*x=min(x,x)=x (3)在Z+中最小的数字是1 任意x属于Z+，有 x*1=1=1*x 所以1是*运算的零元，*运算没有单位元，也没有可逆元素的逆元。
3．令S={a,b},S 上有四个二元运算：*，&,@和#，分别由下表确定. (1)这四个运算中哪些运算满足交换律、结合律、幂等律？ (2)求每个运算的单位元、零元及所有可逆元素的逆元. 解 （1）*，&和@满足交换律；*，@和#满足结合律；#满足幂等律。 （2）*运算没有单位元和可逆元素，a 是零元；&运算的单位元为a ,没有零元,每个元素都是自己的逆元；@运算和#运算没有单位元, 零元和可逆元素.
离散数学答案(尹宝林版)第一章习题解答
第一章 命题逻辑 习题与解答 ⒈ 判断下列语句是否为命题，并讨论命题的真值。 ⑴ 2x - 3 = 0。 ⑵ 前进！ ⑶ 如果8 + 7 > 20，则三角形有四条边。 ⑷ 请勿吸烟！ ⑸ 你喜欢鲁迅的作品吗？ ⑹ 如果太阳从西方升起，你就可以长生不老。 ⑺ 如果太阳从东方升起，你就可以长生不老。 解 ⑶,⑹,⑺表达命题，其中⑶,⑹表达真命题，⑺表达假命题。 ⒉ 将下列命题符号化： ⑴ 逻辑不是枯燥无味的。 ⑵ 我看见的既不是小张也不是老李。 ⑶ 他生于1963年或1964年。 ⑷ 只有不怕困难，才能战胜困难。 ⑸ 只要上街，我就去书店。 ⑹ 如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐。 ⑺ 如果林芳在家里，那么他不是在做作业就是在看电视。 ⑻ 三角形三条边相等是三个角相等的充分条件。 ⑼ 我进城的必要条件是我有时间。 ⑽ 他唱歌的充分必要条件是心情愉快。 ⑾ 小王总是在图书馆看书，除非他病了或者图书馆不开门。 解 ⑴ p ：逻辑是枯燥无味的。 “逻辑不是枯燥无味的”符号化为 ?p 。 ⑵ p ：我看见的是小张。q ：我看见的是老李。 “我看见的既不是小张也不是老李”符号化为q p ?∧?。 ⑶ p ：他生于1963年。q ：他生于1964年。 “他生于1963年或1964年”符号化为p ⊕ q 。 ⑷ p ：害怕困难。q ：战胜困难。 “只有不怕困难，才能战胜困难”符号化为q → ? p 。 ⑸ p ：我上街。q ：我去书店。 “只要上街，我就去书店”符号化为p → q 。 ⑹ p ：小杨晚上做完了作业。q ：小杨晚上没有其它事情。 r ：小杨晚上看电视。s ：小杨晚上听音乐。 “如果晚上做完了作业并且没有其它事情，小杨就看电视或听音乐”符号化为s r q p ∨→∧。 ⑺ p ：林芳在家里。q ：林芳做作业。r ：林芳看电视。 “如果林芳在家里，那么他不是在做作业就是在看电视”符号化为r q p ∨→。 ⑻ p ：三角形三条边相等。q ：三角形三个角相等。
离散数学作业答案完整版
离散数学作业答案 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={
离散数学答案
02任务_000 1 试卷总分：100 测试时间：0 单项选择题 一、单项选择题（共10 道试题，共100 分。） 1. 设集合A = {1, a }，则P(A) = ( )． A. {{1}, {a}} B. {,{1}, {a}} C. {{1}, {a}, {1, a }} D. {,{1}, {a}, {1, a }} 2. 集合A={1, 2, 3, 4}上的关系R={
5. 设集合A={1 , 2 , 3 , 4}上的二元关系R={<1, 1>，<2, 2>，<2, 3>，<4, 4>}，S={<1, 1>，<2, 2>，<2, 3>，<3, 2>，<4, 4>}，则S是R的（）闭包． A. 自反 B. 传递 C. 对称 D. 自反和传递 6. 若集合A={1，2}，B={1，2，{1，2}}，则下列表述正确的是( )． A. A B，且A B B. B A，且A B C. A B，且A B D. A B，且A B 7. 设集合A={1，2，3，4，5}，偏序关系≤是A上的整除关系，则偏序集
华南理工离散数学作业题2017版
华南理工大学网络教育学院 2014–2015学年度第一学期 《离散数学》作业 （解答必须手写体上传，否则酌情扣分） 1．设命题公式为?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）该公式为重言式 2．用直接证法证明 前提：P∨Q，P→R，Q→S 结论：S∨R 解：（1）?S P (2)Q →S P (3) ? Q (1)(2) (4)P∨ Q P
(5)P (3)(4) (6) P → R P (7)R (5)(6) (8)?S→ R （1）（7） 即SVR得证 3．在一阶逻辑中构造下面推理的证明 每个喜欢步行的人都不喜欢坐汽车。每个人或者喜欢坐汽车或者喜欢骑自行车。有的人不喜欢骑自行车。因而有的人不喜欢步行。 令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 ?F (x) p (2) ?H (x) ES(1) (3) ?x (G (x) ∨H (x))P (4)G(c) vH(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) 4．用直接证法证明： 前提：（?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
离散数学 作业及答案
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、下列语句中哪个就是真命题(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 )
离散数学试题及答案(1)
离散数学试题及答案 一、填空题 1设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝____________________; ρ(A) - ρ(B)＝__________________________ . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = __________________________. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是__________________________ _____________, 其中双射的是__________________________. 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是_______________________________ __________________________________________________________. 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为__________，分枝点数为________________. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝_________________________; A?B ＝_________________________;A－B＝_____________________ . 7. 设R是集合A上的等价关系，则R所具有的关系的三个特性是______________________, ________________________, _______________________________. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有__________________________， _____________________________, __________________________. 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R1 = {(2,1),(3,2),(4,3)}, 则 R1?R2 = ________________________,R2?R1 =____________________________, R12 =________________________. 10. 设有限集A, B，|A| = m, |B| = n, 则| |ρ(A?B)| = _____________________________. 11设A,B,R是三个集合，其中R是实数集，A = {x | -1≤x≤1, x∈R}, B = {x | 0≤x < 2, x∈R},则A-B = __________________________ , B-A = __________________________ , A∩B = __________________________ , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除，则R以集合形式(列举法)记为___________ _______________________________________________________. 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是__________________________ _____. 15.设G是具有8个顶点的树，则G中增加_________条边才能把G变成完全图。
离散数学答案【2】
第四章部分课后习题参考答案 3. 在一阶逻辑中将下面将下面命题符号化,并分别讨论个体域限制为(a),(b)条件时命题的真值: (1) 对于任意x,均有2=(x+)(x). (2) 存在x,使得x+5=9. 其中(a)个体域为自然数集合. (b)个体域为实数集合. 解： F(x): 2=(x+)(x). G(x): x+5=9. (1)在两个个体域中都解释为) xF ?，在（a）中为假命题，在(b)中为真命题。 (x (2)在两个个体域中都解释为) ?，在（a）(b)中均为真命题。 xG (x 4. 在一阶逻辑中将下列命题符号化: (1) 没有不能表示成分数的有理数. (2) 在北京卖菜的人不全是外地人. 解: (1)F(x): x能表示成分数 H(x): x是有理数 命题符号化为: )) F x∧ ? x ?? ( ) ( (x H (2)F(x): x是北京卖菜的人 H(x): x是外地人 命题符号化为: )) F x→ ?? x ) H ( ( (x 5. 在一阶逻辑将下列命题符号化: (1) 火车都比轮船快. (3) 不存在比所有火车都快的汽车. 解: (1)F(x): x是火车; G(x): x是轮船; H(x,y): x比y快 命题符号化为: )) F x G y x→ ? ? ∧ y H )) ( , x ( ((y ( ) (2) (1)F(x): x是火车; G(x): x是汽车; H(x,y): x比y快
命题符号化为: ))) y F x G y→ ?? ∧ ? H x ) x , ( ( (y ( ( ) 9.给定解释I如下: (a) 个体域D为实数集合R. (b) D中特定元素=0. (c) 特定函数(x,y)=x y,x,y D ∈. (d) 特定谓词(x,y):x=y,(x,y):x