天津理工大学离散数学(魏雪丽版)检测题答案
天津理工大学《离散数学》第一章检测题答案
一、填空题（每空2分，共30分）
1．P Q → 2．P Q ?→ 3．→，∨，∧，←?→， ∨ ，↑， ↓ ， c
??
→ 。 4．()()()P Q R P Q R P Q R ?∧∧?∨∧?∧?∨∧?∧，
()()()()()P Q R P Q R P Q R P Q R P Q R ∨∨∧∨∨?∧∨?∨?∧?∨?∨∧?∨?∨?
5．()(())P Q P R S ?→∧→∨ 6．Q P ?→? 7．()()P Q Q P ∧?∨∧?
二、单项选择题（每小题2分，共20分）
三、简答题（每小题6分，共12分）
1．构造命题公式)(R Q P →∨的真值表．
2．求命题公式 (())P Q R P ∨→→的主析取范式和主合取范式。
()() (())(())1(())1()()()
P Q R P P Q R P P Q R P P R Q R P P Q R ∨→→???∨∨∨?∨∧?∨?∧?∨∧?∨?∨∧?分分
()()
(()())(()())1()()()()()()1P 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 ?∧∧∨∧?∧∨∧∧?∨∧?∧?∨?∧∧?
()()
24567013(1(()()()1m m m m m M M M P Q R P Q R P Q R ?∨∨∨∨?∧∧?∨∨∧∨∨?∧∨?∨?这是主析取范式))分这是主合取范式)
分
3．判断命题公式 ()()P Q P R →∧→与 ()P Q R →∧是否等价。 解：()()()()A P Q P R P Q P R =→∧→??∨∧?∨
()()()()B P Q R P Q R P Q P R =→∧??∨∧??∨∧?∨
等价
四．证明题（共32分）
１．（10分）用CP 规则证明S Q P S R Q R Q P →?→→∨?∨?),(),(；
1. P P 6. )(S R → T(4,5) I （2分）
2. ()P Q R ?∨?∨ P 7. R T(3,4) I （2分）
3. Q R ?∨ T(1, 2) I （2分） 8. S T(6,7) I （2分）
4. Q P(附加前提) 9. )(S Q → CP （2分）
5. )(S R Q →→ P
２．（10分）用归谬法证明 ,(),A B C B C S A →??∨∧???．
证: 1
(A P 附加前提) （1分） 2 A B P →?
3 1,2B T I ? （2分）
4 C B P ?∨
5 3,4C T I ? （2分）
6 C S P ∧?
7 6C T I （2分）
8 5,7C C T I ∧? （2分）
由8得出了矛盾，根据归谬法说明原推理正确（1分）
3．（12分）公安人员审理某珠宝商店的钻石项链的失窃案，已知侦察结果如下： （1）营业员A 或B 盗窃了钻石项链 （2）若B 作案，则作案时间不在营业时间
（3）若A 提供的证词正确，则货柜未上锁
（4）若A 提供的证词不正确，则作案发生在营业时间
（5）货柜上了锁
试问：作案者是谁？要求写出推理过程。
解：令A 表示“营业员A 盗窃了钻石项链”； B 表示“营业员B 盗窃了钻石项链”；
P 表示“作案时间在营业时间”；Q 表示“A 提供的证词正确”；R 表示“货柜上
了锁”。
则侦察结果如下：
A B ∨， B P →?，Q R →?，Q P ?→，R ．由此可推出作案者是A ．（4分）
推理过程如下：
(1) R P (6) B P →? P
(2) Q R →? P (7) B ? T (5)，(6) I （2分） (3) Q ? T (1)，(2) I （2分） (8) A B ∨ P
(4) Q P ?→ P (9) A T (7)，(8) I （2分） (5) P T (3)，(4) I （2分）
天津理工大学《离散数学》第二章检测题答案
一、填空题（每空3分，共30分）
1．()(()())()(()())x G x F x x F x G x ?→∧??→ 或()(()())()(()())x G x F x y F y G y ?→∧?∧?
2．()()()[(()(,))((,)(,))]x z w P x R x w Q z y R x w ????∨?∧?∨? 3．()()()(()()())P a P b P c Q a Q b Q c ∧∧∧∨∨
4．))()()(())()()((c P b P a P c P b P a P ∧∧∨?∧?∧? 5．(),()()(,)P x x y P x y ???? 6．（,x y ；y ） 7．(()(,))P x yR x y ∨? 8．()(()())x F x G x ??∨?
二、单项选择题（每小题2分，共20分）
三、 简答题（每小题6分，共12分）
1．求謂词公式)),()()()(()),()()((z y Q z y P y y x Q x P x ?∧?→→?的前束析取范式．
))
,()()()(()),()()((z y Q z y P y y x Q x P x ?∧?→→?
))],()(()),()()[()()(()),()()()(()),()(()),()()()(()),()(()),()()()(()),()()((z y Q u P y x Q x P z u x z y Q z u P u y x Q x P x z y Q z y P y y x Q x P x z y Q z y P y y x Q x P x ∧∨?∧?????∧?∨?∧???∧?∨?∧???∧?∨∨????
2．证明：(()())()()x P x Q x xP x xQ x ?→??→? 证：
(()())()())(())()
()()()())
x P x Q x x P x Q x x P x xQ x xP x xQ x xP x xQ x =?→???∨???∨????∨???→?左式(
四．证明题（共38分）
1．（12分）用谓词演算的推理规则证明:
))()((x Q x P x →?，))()()((x S x R x Q x →∧?，)(a P )(a R ∧?)(a S
（1）))()((x Q x P x →? P （2）)()(a Q a P → )1(US （2分） （3）)(a P )(a R ∧ P （4）)(a Q )3)(2(T I （2分） （5）))()()((x S x R x Q x →∧? P
（6）)()()(a S a R a Q →∧ )5(US （2分） （7）)(a R )3(T I （2分） （8）)()(a R a Q ∧ )7)(4(T I （2分） （9）)(a S )8)(6(T I （2分） 2．(10分) 指出下面推理证明过程中的错误，并给出正确的证明．
用谓词演算的推理规则证明：
))()(())()(())()((x Z x R x x Z x Q x x R x Q x ∧??∧?∧→?
证:：(1) ))()((x R x Q x →? P (6) )(a Z T(4) I (2) )()(a R a Q → US(1) (7) )(a R T(2),(5) I (3) ))()((x Z x Q x ∧? P (8) )()(a Z a R ∧ T(6),(7) I (4) )()(a Z a Q ∧ ES(3) (9) ))()((x Z x R x ∧? EG(8) (5) )(a Q T(4) I
该证明的错误在于: (1)、 (2) 与 (3)、 (4) 的顺序颠倒了，应该先指定存在后指定全称。 （2分）正确的证明是：（4分）
(1) ))()((x Z x Q x ∧? P (6) )(a Z T(2) I （1分） (2) )()(a Z a Q ∧ ES (1) （2分） (7) )(a R T(4),(5) I （1分） (3) ))()((x R x Q x →? P (8) )()(a Z a R ∧ T(6),(7) I （1分） (4) )()(a R a Q → US (3) （2分） (9) ))()((x Z x R x ∧? EG(8) （1分） (5) )(a Q T(2) I
3．（16分）符号化下列命题并推证其结论．
任何人如果他喜欢音乐,他就不喜欢体育．每个人或者喜欢体育，或者喜欢美术．有的人不喜欢美术．因而有的人不喜欢音乐．（设M(x)：x 喜欢音乐，S(x)：x 喜欢体育，Ａ(x)：ｘ喜欢美术．） 该推理符号化为：
((()
())(()())())(x M x S x x S x A x x A x x M x ?→?∧?∨∧????? 或 前提：(()()),(()()),()x M x S x x S x A x x A x ?→??∨??
结论：()x M x ?? （4分）证：
（1）()x A x ?? P （2）()A a ? ES （1） （2分） （3）(()())x S x A x ?∨ P （4）()()S a A a ∨ US （3） （2分）（5）()S a T （2）（4）I （2分） （6）(()())x M x S x ?→? P
（7）()()M a S a →? US （6）（2分） （8）()()S a M a →? T （7）E （1分） （9）()M a ? T （5）（8）I （2分） （10）()x M x ?? EG （9） （1分）
天津理工大学《离散数学》第三、四章检测题答案
一、填空题（每空2分，共40分）
1． 2n
n ? ２．{,{}},{,{}{,}},{}ΦΦΦΦΦΦ 3．
,{{,{}{},}}a b c Φ
4．反对称，传递。 5．1R R - ；1
i
i R ∞
= 6． A I ，100010001??
?
?
?
?
??
?
或单位矩阵
7． 4,6 ， 2,3 ， 无 ， 无 ， 12 ， 1 。
8． 1f ={,0,{},1}φ, 2f ={,1,},0}φφ。 9．单射，满射；既是单射又是满射； B I ； A I
二、单项选择题（每小题2分，共20分）
三、简答题（共30分）
1．（6分）设A ={1,2,3,5,6,10,15,30} ， “／” 为集合A 上的整除关系。〈A ，／〉是否为偏
序集? 若是，画出其哈斯图；
解：〈A ，／〉是偏序集。其哈斯图为：
2．（12分）对下图所给的偏序集≤,A ，求下表所列集合的上（下）界，上（下）确界，并将结果填入表中。
3．（6分）设 A ={1,2,3,4,5,6}，集合A 上的关系
R ={〈1,3〉,〈1,5〉,〈2,5〉,〈4,4〉,〈4,5〉,〈5,4〉,〈6,3〉,〈6,6〉}。 （1）画出R 的关系图，并求它的关系矩阵； （2）求(),()r R S R 及 ()t R 。 解：（1）R 的关系图为
R 的关系矩阵为
??
?
???
???
?
?????
?????=10010
0001000011000000000010000010100R M （2分）
（2）(){1,1,2,2,3,3,5,5}r R R = ， （1分） (){3,1,5,1,5,2,3,6}S R R = （1分） (){1,4,2,4,5,5}t R R = （2分）
4．设Z 是整数集，R 是Z 上的模3同余关系，即{,,,(mod3)}R x y x y Z x y =∈≡，试根据等价关系R 决定Z 的一个划分 。
答案：由R 决定的Z 的划分为：[][][]}2,1,0{R R R ， 其中：
[][][]}
,8,5,2,1,4,7,{2},7,4,1,2,5,8,{1}
,9,6,3,0,3,6,9,{0 ---=---=---=R R R
四．证明题（共10分）
１．设,,,b a R b a <∈ 定义]1,0[],[:→b a f 为 a
b a
x x f --=
)(，证明：f 是双射，并求出其逆映射。
证：1）先证明f 是入射（2分）
对任意的[]),()(,,,2121x f x f b a x x =∈若则有a
b a
x a b a x --=--21，从而有21x x =，故f 是入射。
2) 再证明f 是满射（2分）
对任意的[][],)(,,)(,1,0y x f b a a y a b x y =∈+-=∈使得都存在从而f 是满射。 综合（1）、（2）知f 是双射。 ],[]1,0[:1
b a f
→-为 a x a b x f +-=-)()(1，对任意[]1,0∈x 。
（1分）
天津理工大学《离散数学》第五章检测题答案
一、填空题（每空2分，共30分）
1. 1
1
b a --* 2．a 3．,,,S S ΦΦ 4．a ；1 5．S 关于+运算不封闭
6． 2，1
4a
a -=- 7循环群，生成元 8．
9．B 关于*封闭
二、单项选择题（每小题2分，共20分）
三、简答题（共30分）
1．设*是实数集R 上的二元运算，其定义如下：
2a b a b ab *=++
（1）求2*3， 3*(-5)和7*1/2 。
（2）
,R *是半群吗？*可交换吗？
（3）求R 中关于*的单位元。
（4）R 中哪些元素有逆元素，其逆元素是什么？ 答案：（1）17，-32，14.5 。 2）
,R *是半群，*可交换。 （3）0。
（4）当,1/2a R a ∈≠-时，a 有逆元素，1
/(12)a a a -=-+。
2．设{,,,}A a b c d =，,A *
*的运算表如下：
求123456,,,,,x x x x x x ，并说明道理。
答案：123456,,,,,x d x c x b x d x c x b ======。因为有限群的运算表中的每行、每列都是群中元素的一个置换。
3．设集合{1,3,4,5,9}G =，*是定义在G 上的模11乘法（即任意a ,b ∈G ，有
a *
b =(a ×b )(m o d 11)，×是普通乘法），问,G *是循环群吗？若是，试找出它的生成元。
答： ,G *的运算表如下表所示。
从运算表可知，*在G 上封闭、有幺元1，且5143213,33,43,53,93=====，再由*是可结合的得,G *是循环群，3，4，5和9均为其生成元。
四．证明题（共20分）
１．（4分）设
,G *是独异点，e 为其幺元，且对a G ?∈，有a a e *=，证明
,G *是一个交换群。
证明： 对a G ?∈，由于a a e *=，则 1
a a -=， 即G 中的每一个元素a 都有逆元
素,故
,G *是一个群。
又对,a b G ?∈，有
111()a b a b b a b a ---*=*=*=*，
所以
,G *是一个Abel 群。
２．（6分）设,G *是一个群，a G ∈，:f G G →，x G ?∈，有
1()f x a x a -=**
试证明f 是,G *一个自同构． 证：首先证明f 是入射。（3分）
111212121
12,,()(),,.
x x G f x f x a x a a x a a a x x f f ---?∈=**=**=对若则有,该式两边同时左乘及右乘得,故为入射
其次证明f 是满射。
对1
,,(),y G x a y a G y f x f -?∈=**∈=都存在使得因此是满射. 综合以上两点，知f 是双射。（3分）
1111212121212,,,()()()()(),.
x x G f x x a x x a a x a a x a f x f x f G G ---?∈*=***=*****=*最后对都有从而是到的自同构
天津理工大学《离散数学》第六章检测题答案
一、填空题（每空2分，共40分）
1. 上确界 和下确界，a ，b 2．至少有一个补元素，不一定 3．0，1；1，0
4．1,0a a a a ∨=∧= 5．a b ∧；a b ∨ 6． n
A
A
，2n
A
二、单项选择题（每小题2分，共20分）
三、简答题（共30分）
1．下面哈斯图表示的格中哪个元素无补元？对有补元的元素求出它们的补元． 解：c 无补元（1分），a 的补元为e （1分），b 的补元为d （1分），d 的补元为b 、e （1分），e 的补元为a 、d （1分），0与1互为补元。（1分）
2．设,,,,0,1B ∨∧是一个布尔代数且{0,,,1}B a b =，求布尔表达式
1231213()()(())f x x x a x x x x b =∧∧∨∧∨,,
的析取范式和合取范式并计算(1)f b a ,,的值。 解：123()f x x x ,,的析取范式为：
123123123123()()()()x x x x x x x x x b x x x ∧∧∨∧∧∨∧∧∨∧∧∧（4分）
123()f x x x ,,的合取范式为：
123123123123123()()()()()x x x x x x x x x x x x b x x x ∨∨∧∨∨∧∨∨∧∨∨∧∨∨∨（4分） (1)f b a b =,,（2分）
3．设A ={1,2,3,5,6,10,15,30} ， “／” 为集合A 上的整除关系。 (1)．〈A ，／〉是否为偏序集? 若是，画出其哈斯图；
(2)．〈A ，／〉是否构成格？为什么？ (3)．〈A ，／〉是否构成布尔代数？为什么？ 解：(1)．〈A ，／〉是偏序集。 其哈斯图为： (2)．〈A ，／〉构成格。因为其任意两个元素都有上确界和下确界。 (3)．〈A ，／〉构成布尔代数。因为它是有界分配格，且其任意 元素都有唯一补元素。
四．证明题（共10分） １．（4分）设
,G *是独异点，e 为其幺元，且对a G ?∈，有a a e *=，证明
,G *是一个交换群。
证明： 对a G ?∈，由于a a e *=，则 1
a
a -=， 即G 中的每一个元素a 都有逆元素,故
,G *是一个群。
又对,a b G ?∈，有
111()a b a b b a b a ---*=*=*=*，
所以
,G *是一个Abel 群。
２．（6分）设,G *是一个群，a G ∈，:f G G →，x G ?∈，有
1()f x a x a -=**
试证明f 是,G *一个自同构． 证：首先证明f 是入射。（3分）
111212121
12,,()(),,.
x x G f x f x a x a a x a a a x x f f ---?∈=**=**=对若则有,该式两边同时左乘及右乘得,故为入射
其次证明f 是满射。
对1,,(),y G x a y a G y f x f -?∈=**∈=都存在使得因此是满射. 综合以上两点，知f 是双射。（3分）
1111212121212,,,()()()()(),.
x x G f x x a x x a a x a a x a f x f x f G G ---?∈*=***=*****=*最后对都有从而是到的自同构
离散数学第七章检测题答案
一、 单项选择题（每小题2分，共20分）
二、 填空题（每空3分，共45分）
1． 4 ， 3 。 2． __0___， _1__。 __0___， __0___。 3．(2121,V V V V ?= 4． 2 │E│ ， 偶数 。5．___5__； __9___。 6． 3 ， 1 。7． 7 。
三、 简答题（每小题5分，共25分）
1．对有向图,G V E =求解下列问题： （1）写出邻接矩阵A ；
（2）,G V E =中长度为3的不同的路有几条？其中不同的回路有几条？
解：（1）邻接矩阵为：
1001001000
00011100000010A ??
??????=??
??????
，
（2）2
3
011011
0010000100010,0
001011
0000110100
1111
100001
101A A ????
????????????==???
?
????????????
则，,G V E =中长度为3的不同的路有10条，其中有1条不同的回路。
2．设有２８盏灯，拟公用一个电源，求至少需要４插头的接线板的数目。
解：设至少需要4插头的接线板i 个，则有
（4-1）i=28-1 （3分）
故 i=9
即至少需要9个4插头的接线板。 （2分）
3．设有6个城市V 1，V 2，…，V 6，它们之间有输油管连通，其布置如下图,S i (数字)中S i 为边的编号，括号内数字为边的权，它是两城市间的距离，为了保卫油管不受破坏，在每段油管间派一连士兵看守，为保证每个城市石油的正常供应最少需多少连士兵看守?输油管道总长度越短，士兵越好防守。求他们看守的最短管道的长度。(要求写出求解过程) 解：为保证每个城市石油的正常供应最少需 5连士兵看守.求看守的最短管道相当于求图 的最小生成树问题，此图的最小生成树为：
因此看守的最短管道的长度为： Ｗ（Ｔ）＝１＋1＋2＋2＋2＝８．
4．以给定权1, 4, 9, 16, 25, 36, 49, 64, 81, 100构造一棵最优二叉树。
5．一次学术会议的理事会共有20个人参加，他们之间有的相互认识，但有的相互不认识。但对任意两个人，他们各自认识的人的数目之和不小于20，说明能否把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人？根据是什么？
解：可以把这20个人排在圆桌旁，使得任意一个人认识其旁边的两个人。（1分）
根据是：分别用20个结点代表这20个人，将相互认识的人之间连一条线，便得到一个 无向简单图,G E =，每个结点i v V ∈的度数是与i v 认识的人的数目，由题意知
,i j v v V ∈，有d e g ()d e g ()2i j v v +≥，于是,G V E =中存在哈密尔顿回路，设12201i i i i C v v v v = 是,G V E =中的一条哈密尔顿回路，按此回路安排园桌座位即符合要
求。（4分）
四．证明与应用题（10分）
1． 某次聚会的成员到会后相互握手，试用图论的知识说明与奇数个人握手的人数一定是一
个偶数。
证: 用结点代表成员, 握手的成员之间连一条线, 则所有聚会的成员之间的握手
情况可以用一个图来表示，其中每个结点的度数就是该结点所代表的成员握手的人数,由于任一图中奇数度结点的个数为偶数,所以与奇数个人握手的人数一定是一个偶数。
19春华南理工《离散数学》随堂练习答案
第一章命题逻辑·第一节命题与联结词 当前页有10 题，你已做10 题，已提交10 题，其中答对10 题 1. (单选题) 在下面句子中，是命题的是( ) A ．明年“五一”是晴天。 B ．这朵花多好看呀！。 C ．这个男孩真勇敢啊！ D ．明天下午有会吗？ 参考答案：A 2. (单选题) 在下面句子中，是命题的是( ) A．1＋101＝110 B ．中国人民是伟大的。 C．这朵花多好看呀！ D ．计算机机房有空位吗？ 参考答案：B 3. (单选题) 在下面句子中( )是命题 A ．如果天气好，那么我去散步。 B ．天气多好呀！ C．x=3 。 D ．明天下午有会吗？ 参考答案：A 4. (单选题) 下面的命题不是简单命题的是( ) A．3是素数或4是素数B．2018 年元旦下大雪
C．刘宏与魏新是同学D．圆的面积等于半径的平方与之积参考答案：A 5. (单选题) 下面的表述与众不一致的一个是( ) A．P ：广州是一个大城市B．：广州是一个不大的城市 C．：广州是一个很不小的城市 D ．：广州不是一个大城市
参考答案：C 6. (单选题) 设，P：他聪明；Q：他用功。在命题逻辑中，命题： “他既聪明又用功。” 可符号化为：( ) 参考答案：A 7. (单选题) 设：P ：刘平聪明。Q：刘平用功。在命题逻辑中，命题： “刘平不但聪明，而且用功” 可符号化为：( ) 参考答案：A 8. (单选题) 设：P：他聪明；Q：他用功。则命题“他虽聪明但不用功。” 在命题逻辑中可符号化为( ) 参考答案：D 9. (单选题) 设：P：我们划船。Q：我们跑步。在命题逻辑中，命题： “我们不能既划船又跑步。” 可符号化为：( ) 参考答案：B 10. (单选题) 设：P：王强身体很好；Q：王强成绩很好。命题“王强身体很好，成绩也很好。”在命题逻辑中可符号化为( ) 参考答案：D 11. (单选题) 设：P：你努力；Q：你失败。则命题“除非你努力，否则你将失败。”在命题逻辑中可符号化为( ) 12. （单选题）设：p：派小王去开会。q：派小李去开会。则命题： “派小王或小李中的一人去开会” 可符号化为：（） 参考答案：C
100道离散数学填空题分解
离散数学试题库——填空题 （每空2分） 1 命题: ? ? {{a }} ? {{a },3,4,1} 的真值 = __ __ . 2. 设A= {a,b}, B = {x | x 2－(a+b) x+ab = 0}, 则两个集合的关系为: __ __. 3. 设集合A ＝{a ,b ,c },B ={a ,b }, 那么 P(B )－P(A )=__ __ . 4. 无孤立点的有限有向图有欧拉路的充分必要条件为: 5.公式))(),(()),()((x S z y R z y x Q x P x →?∨→?的自由变元是 , 约束变元是 . 6.)))()()(()),()(()((x R z Q z y x P y x →?→???的前束范式是 . 7．设 }7|{)},5()(|{<∈=<∈=+ x E x x B x N x x A 且且（N ：自然数集，E + 正偶 数） 则 =?B A 。 8．A ，B ，C 。 9．设P ，Q 的真值为0，R ，S 的真值为1，则 )()))(((S R P R Q P ?∨→?∧→∨?的真值= 。 10．公式P R S R P ?∨∧∨∧)()(的主合取范式为 。 11．若解释I 的论域D 仅包含一个元素，则 )()(x xP x xP ?→? 在I 下真值为 。 12．设A={1，2，3，4}，A 上关系图为 则 R 2 = 。 13．设A={a ，b ，c ，d}，其上偏序关系R 的哈斯图为
则 R= 。 14．图的补图为。15．设A={a，b，c，d} ，A上二元运算如下： 那么代数系统
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 (数理逻辑部分) 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),(5),(6) 4、公式?x((A(x)→B(y,x))∧ ?z C(y,z))→D(x)中,自由变元就是( ),约束变元就是( )。 答:x,y, x,z 5、判断下列语句就是不就是命题。若就是,给出命题的真值。( ) (1) 北京就是中华人民共与国的首都。 (2) 陕西师大就是一座工厂。 (3) 您喜欢唱歌不？ (4) 若7+8＞18,则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答:(1) 就是,T (2) 就是,F (3) 不就是 (4) 就是,T (5) 不就是 (6) 不就是 6、命题“存在一些人就是大学生”的否定就是( ),而命题“所有的人都就是要死的”的否定就是( )。 答:所有人都不就是大学生,有些人不会死 7、设P:我生病,Q:我去学校,则下列命题可符号化为( )。 (1) 只有在生病时,我才不去学校 (2) 若我生病,则我不去学校 (3) 当且仅当我生病时,我才不去学校(4) 若我不生病,则我一定去学校 答:(1) P Q →? (2) Q P ?→ (3) Q P ?? (4)Q P →? 8、设个体域为整数集,则下列公式的意义就是( )。 (1) ?x ?y(x+y=0) (2) ?y ?x(x+y=0) 答:(1)对任一整数x 存在整数 y 满足x+y=0(2)存在整数y 对任一整数x 满足x+y=0 9、设全体域D 就是正整数集合,确定下列命题的真值: (1) ?x ?y (xy=y) ( ) (2) ?x ?y(x+y=y) ( ) (3) ?x ?y(x+y=x) ( ) (4) ?x ?y(y=2x) ( ) 答:(1) F (2) F (3)F (4)T 10、设谓词P(x):x 就是奇数,Q(x):x 就是偶数,谓词公式 ?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答:(1) 11、命题“2就是偶数或-3就是负数”的否定就是( )。 答:2不就是偶数且-3不就是负数。 12、永真式的否定就是( ) (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能
《离散数学》题库及答案
《离散数学》题库与答案 一、选择或填空 （数理逻辑部分） 1、下列哪些公式为永真蕴含式？( A ) (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）不是（命题必须满足是陈述句，不能是疑问句或者祈使句。） 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死（命题的否定就是把命题前提中的量词“换成存在，换成”，然后将命题的结论否定，“且变或或变且”） 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校(2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校答：（1）P ?（注意“只有……才……”和“除非……就……”两者都是一个 Q→ 形式的）（2）Q P→ ? P? ?（4）Q P? →（3）Q 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x存在整数y满足x+y=0 （2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1）F (反证法：假若存在，则（x- 1）*y=0 对所有的x都成立，显然这个与前提条件相矛盾) （2）F （同理）（3）F （同理）（4）T（对任一整数x存在整数y满足条件y=2x 很明显是正确的）
(完整word版)离散数学期末练习题带答案
离散数学复习注意事项： 1、第一遍复习一定要认真按考试大纲要求将本学期所学习内容系统复习一遍。 2、第二遍复习按照考试大纲的要求对第一遍复习进行总结。把大纲中指定的例题及书后习题认真做一做。检验一下主要内容的掌握情况。 3、第三遍复习把随后发去的练习题认真做一做，检验一下第一遍与第二遍复习情况，要认真理解,注意做题思路与方法。 离散数学综合练习题 一、选择题 1．下列句子中，（）是命题。 A．2是常数。B．这朵花多好看呀！ C．请把门关上！D．下午有会吗？ 2．令p: 今天下雪了，q:路滑，r:他迟到了。则命题“下雪路滑，他迟到了” 可符号化为（）。 A. p q r ∨→ ∧→ B. p q r C. p q r ∨? ∧∧ D. p q r 3．令:p今天下雪了，:q路滑，则命题“虽然今天下雪了，但是路不滑”可符号化为（）。 A.p q ∧ ∧? B.p q C.p q →? ∨? D. p q 4．设() Q x:x会飞，命题“有的鸟不会飞”可符号化为（）。 P x:x是鸟，() A. ()(()()) Q x ??∧()) x P x Q x ??→ B. ()(() x P x C. ()(()()) Q x ??∧()) x P x Q x ??→ D. ()(() x P x 5.设() L x y：x大于等于y；命题“所有整数 f x:x的绝对值，(,) P x:x是整数，() 的绝对值大于等于0”可符号化为（）。 A. (()((),0)) ?→ x P x L f x ?∧B. (()((),0)) x P x L f x C. ()((),0) ?→ xP x L f x ?∧ D. ()((),0) xP x L f x 6.设() F x:x是人，() G x:x犯错误，命题“没有不犯错误的人”符号化为（）。 A．(()()) ??→? x F x G x ?∧B．(()()) x F x G x C．(()()) ??∧? x F x G x ??∧D．(()()) x F x G x 7.下列命题公式不是永真式的是（）。 A. () p q p →→ →→ B. () p q p C. () →∨ p q p p q p ?∨→ D. () 8．设() R x:x为有理数；() Q x:x为实数。命题“任何有理数都是实数”的符号化为（）
华南理工离散数学作业题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
大学本科高等数学《离散数学》试题及答案
本科高等数学离散数学试题及答案 一、填空题 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变成完全图。
华南理工离散数学作业题版
华南理工离散数学作业题 版 The document was prepared on January 2, 2021
华南理工大学网络教育学院 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) (QP) 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 (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) 5．设R是集合A = {1, 2, 3, 4, 6, 12}上的整除关系。
中国石油大学大学《离散数学》期末复习题及答案
《离散数学》期末复习题 一、填空题（每空2分，共20分） 1、集合A上的偏序关系的三个性质是、 和。 2、一个集合的幂集是指。 3、集合A={b,c}，B={a,b,c,d,e}，则A?B= 。 4、集合A={1,2,3,4}，B={1,3,5,7,9}，则A?B= 。 5、若A是2元集合, 则2A有个元素。 6、集合A={1,2,3｝，A上的二元运算定义为：a* b = a和b两者的最大值，则 2*3= 。 7、设A={a, b,c,d }, 则∣A∣= 。 8、对实数的普通加法和乘法，是加法的幂等元， 是乘法的幂等元。 9、设a,b,c是阿贝尔群
19、代数系统是指由及其上的或 组成的系统。 20、设
华南理工网络教育离散数学同步练习册
离散数学 同步练习册 学号＿＿＿＿＿＿＿＿姓名＿＿＿＿＿＿＿＿专业＿＿＿＿＿＿＿＿教学中心＿＿＿＿＿＿＿＿ 华南理工大学 二O一O年九月
第一章命题逻辑 一填空题 （1）设：p：派小王去开会。q：派小李去开会。则命题： “派小王或小李中的一人去开会”可符号化 为：p∨q。 （2）设A，B都是命题公式，A?B，则A→B的真值是T 。 （3）设：p：刘平聪明。q：刘平用功。在命题逻辑中，命题：“刘平不但不聪明，而且不用功”可符号化为：﹃p∧﹃ q 。 （4）设A , B 代表任意的命题公式，则蕴涵等值式为 A → B?﹃P∨Q 。 （5）设，p：径一事；q：长一智。在命题逻辑中，命题： “不径一事，不长一智。”可符号化为：﹃p→﹃ q 。 （6）设A , B 代表任意的命题公式，则德?摩根律为 ?（A ∧ B）?﹃A∨﹃B 。 （7）设，p：选小王当班长；q：选小李当班长。则命题：“选小王或小李中的一人当班长。”可符号化为：(A∧﹃B)∨(﹃A∧ B) 。 （8）设，P：他聪明；Q：他用功。在命题逻辑中，命题： “他既聪明又用功。”可符号化为：P∧Q 。（9）对于命题公式A，B，当且仅当A→B 是重言式时，称“A 蕴含B”，并记为A?B。 （10）设：P：我们划船。Q：我们跑步。在命题逻辑中，命题：“我们不能既划船又跑步。”可符号化为：﹃(P∧ Q) 。 （11）设P , Q是命题公式，德·摩根律为： ?（P∨Q）?﹃P∧﹃Q 。 （12）设P：你努力。Q：你失败。在命题逻辑中，命题：“除非你努力，否则你将失败。”可符号化为：﹃P→
Q。 （13）设p：小王是100米赛跑冠军。q：小王是400米赛跑冠军。在命题逻辑中，命题：“小王是100米或400米赛跑冠军。”可符号化为： p∨q。 （4）设A，C为两个命题公式，当且仅当 A →C 为一重言式时，称C可由A逻辑地推出。 二．判断题 1.设A，B是命题公式，则蕴涵等值式为A→B??A∧B。（F ） 2.命题公式?p∧q∧?r是析取范式。（T ） 3.陈述句“x + y > 5”是命题。（T ） 4.110 (p=1,q=1, r=0)是命题公式((?(p∧q))→r)∨q 的成真赋值。（T ） 5.命题公式p→(?p∧q) 是重言式。（ F ） 6.设A，B都是合式公式，则A∧B→?B也是合式公式。（ F ） 7.A∨(B∧C)?( A∨B)∨(A∨C)。（F ） 8.陈述句“我学英语，或者我学法语”是命题。（T ） 9.命题“如果雪是黑的，那么太阳从西方出”是假命题。（T ） 10.“请不要随地吐痰！”是命题。（ F ） 11.P →Q ??P∧Q 。（ F ） 12.陈述句“如果天下雨，那么我在家看电视”是命题。（T ） 13.命题公式（P∧Q）∨（?R→T）是析取范式。（T ） 14.命题公式(P∧?Q)∨R∨ (?P∧Q) 是析取范式。（T ） 三、选择题：在每小题的备选答案中只有一个正确答案，将正确答案序号填入下列叙述中的内。 1．设：P：天下雪。Q：他走路上班。则命题“只有天下雪，他才走路上班。” 可符号化为（1）。 （1）P→Q （2）Q → P （3）? Q →? P （4）Q ∨?P
离散数学 练习题七
9.给定算式: {[(a ＋b)＊c]＊(d ＋e)}＋[f －(g ＊h)] 此算式的波兰符号表示式为( ), 逆波兰符号表示式为( ). A 、＋＊＊a ＋bc ＋def －g ＊h B 、＋＊＊＋abc ＋de －f ＊gh C 、＊－＊＋abc ＋de －fgh ＋ D 、ab ＋c ＊de ＋＊fgh ＊－＋ 10．设R,Z,N 分别为实数,整数和自然数集，函数f ：R →R ，f(x)＝x ，f 是（ ）; g: Z →N, g(x)＝|x|, g 是( ); h: N →N ×N. h(n)＝﹤n,n ＋1﹥,h({5})＝( ) A ．满射函数 B ．单射函数 C ．双射函数 D ．非单射非满射 E. 满射非单射 F.单射非满射 G ,<5,6> H,{<5,6>} J,以上答案都不对. 11. 75个学生去书店买语文,数学,英语书,每种书每个学生至多买1本.已知20个学生每人 买3本书,55个学生每人至少买2本书.每本书的价格都是1元,所有学生总共花费 140元,恰好买2本书的有( )多少个学生.至少买2本书的学生花费( )元.买 1本书的有( )个学生.至少买1本书的有( )个学生.没买书的有( )个学生. A.55 B.40 C.35 D.15 E.30 F.130 G.65 H.140 J.60 K.10 12. 为每个逻辑断言选择正确的解释。T(x)：x 今天来上课，S(x)：x 学计算机专业的学生， P(x)：x 编程序，G(x)：x 玩游戏。个体域是殷都大学。 ?x T(x)表示（ ），??x T(x)表示（ ），?x ? T(x)表示（ ），?x(S(x)→P(x))表示（ ），?x(S(x)∧G(x))表示（ ），?x(S(x)∧P(x))表示（ ），?x(S(x)→G(x))表示（ ）。 A 学计算机专业的学生会编程序， B 殷都大学的学生都是计算机专业且会编程序。 C 有些计算机专业的学生玩游戏， D 所有同学今天都来上课了， E 今天有同学没来上课。 F 计算机专业的学生玩游戏， G 今天没有同学来上课。 二、计算与应用题（共40分） 1. S={ 1，2，…，10 }，定义S 上的关系R={
山东大学离散数学题库及答案
《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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），（5），（6） 4、公式 x((A(x) B(y ，x)) z C(y ，z))D(x)中，自由变元是( )，约束变元是( )。 答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) (1) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。 (3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。 (5) 前进！ (6) 给我一杯水吧！ 答：（1） 是，T （2） 是，F （3） 不是 （4） 是，T （5） 不是 （6） 不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P ：我生病，Q ：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q →? （2） Q P ?→ （3） Q P ?? （4）Q P →? 8、设个体域为整数集，则下列公式的意义是( )。 (1) x y(x+y=0) (2) y x(x+y=0) 答：（1）对任一整数x 存在整数 y 满足x+y=0（2）存在整数y 对任一整数x 满足x+y=0 9、设全体域D 是正整数集合，确定下列命题的真值： (1) x y (xy=y) ( ) (2) x y(x+y=y) ( ) (3) x y(x+y=x) ( ) (4) x y(y=2x) ( ) 答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x 是奇数，Q(x)：x 是偶数，谓词公式 x(P(x)Q(x))在哪个个体域中为真?( ) (1) 自然数 (2) 实数 (3) 复数 (4) (1)--(3)均成立 答：（1） 11、命题“2是偶数或-3是负数”的否定是（ ）。 答：2不是偶数且-3不是负数。 12、永真式的否定是（ ） (1) 永真式 (2) 永假式 (3) 可满足式 (4) (1)--(3)均有可能 答：（2） 13、公式(?P ∧Q)∨(?P ∧?Q)化简为（ ），公式 Q →(P ∨(P ∧Q))可化简为（ ）。 答：?P ，Q →P
(完整版)华南理工《离散数学》命题逻辑练习题(含答案)
第一章命题逻辑 1.1命题与联结词 一、单项选择题 1、A .明年“五一”是晴天 B .这朵花多好看呀! C.这个男孩真勇敢啊! D .明天下午有会吗? 在上面句子中，是命题的是 2. A . 1 + 101 = 110 ?中国人民是伟大 的。 C.这朵花多好看呀! 计算机机房有空位吗? 在上面句子中，是命题的是 3. A .如果天气好，那么我去散步。 B ?天气多好呀! C. x=3。?明天下午有会吗? 在上面句子中（）是命题 下面的命题不是简单命题的是 4. A. 3是素数或4是素数） .2018年元旦下大雪 C. 刘宏与魏新是同学?圆的面积等于半径的平方与之积 5. 下面的表述与众不一致的一个是 A. P :广州是一个大城市（） .P:广州是一个不大的城市 C. 6 .设，P:他聪明；Q:他用功。在命题逻辑中，命题： “他既聪明又用功。”可符号化为：（） A. P Q B . P Q C. P Q D . P Q 7.设：P :刘平聪明。Q刘平用功。在命题逻辑中，命题： “刘平不但聪明，而且用功”可符号化为：（） A. P Q B . P Q C. P Q D . P Q &设：P:他聪明；Q:他用功。则命题“他虽聪明但不用功。” 在命题逻辑中可符号化为() A. P Q B . P Q C. P Q D . P Q 9 .设：P:我们划船。Q：我们跑步。在命题逻辑中，命题： “我们不能既划船又跑 步 。”可符号化为：（） A. P Q B . (P Q C. P Q D . P Q 10 .设: P：王强身体很好；Q:王强成绩很好。命题“王强身体很好 化为（) A. P Q B . P Q C. P Q D . P Q P :广州是一个很不小的城市D. P:广州不是一个大城市 11 .设：P：你努力；Q你失败。则命题“除非你努力，否则你将失败 ，成绩也很好。”在命题逻辑中可符号
《离散数学》练习题和参考答案
《离散数学》练习题和参考答案 一、选择或填空（数理逻辑部分） 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），（5），（6） 4、公式?x((A(x)→B(y，x))∧?z C(y，z))→D(x)中，自由变元是( )，约束变元是( )。答：x,y, x,z 5、判断下列语句是不是命题。若是，给出命题的真值。( ) 北京是中华人民共和国的首都。 (2) 陕西师大是一座工厂。(3) 你喜欢唱歌吗？ (4) 若7+8＞18，则三角形有4条边。(5) 前进！ (6) 给我一杯水吧！ 答：（1）是，T （2）是，F （3）不是 （4）是，T （5）不是（6）不是 6、命题“存在一些人是大学生”的否定是( )，而命题“所有的人都是要死的”的否定是( )。 答：所有人都不是大学生，有些人不会死 7、设P：我生病，Q：我去学校，则下列命题可符号化为( )。 (1) 只有在生病时，我才不去学校 (2) 若我生病，则我不去学校 (3) 当且仅当我生病时，我才不去学校(4) 若我不生病，则我一定去学校 答：（1） P Q→ ?（2）Q P? →（3）Q P? ?（4）Q P→ ? 8、设个体域为整数集，则下列公式的意义是( )。 (1) ?x?y(x+y=0) (2) ?y?x(x+y=0) 答：（1）对任一整数x存在整数 y满足x+y=0（2）存在整数y对任一整数x满足x+y=0 9、设全体域D是正整数集合，确定下列命题的真值： (1) ?x?y (xy=y) ( ) (2) ?x?y(x+y=y) ( ) (3) ?x?y(x+y=x) ( ) (4) ?x?y(y=2x) ( )答：（1） F （2） F （3）F （4）T 10、设谓词P(x)：x是奇数，Q(x)：x是偶数，谓词公式?x(P(x)∨Q(x))在哪个个体域中为真?( ) (1) 自然数(2) 实数 (3) 复数(4) (1)--(3)均成立答：（1） 11、命题“2是偶数或-3是负数”的否定是（）。答：2不是偶数且-3不是负数。 12、永真式的否定是（） (1) 永真式(2) 永假式(3) 可满足式(4) (1)--(3)均有可能答：（2） 13、公式(?P∧Q)∨(?P∧?Q)化简为（），公式 Q→(P∨(P∧Q))可化简为（）。答：?P ，Q→P 14、谓词公式?x(P(x)∨?yR(y))→Q(x)中量词?x的辖域是（）。答：P(x)∨?yR(y) 15、令R(x):x是实数，Q(x):x是有理数。则命题“并非每个实数都是有理数”的符号化表示为（）。
离散数学图论部分经典试题及答案
离散数学图论部分综合练习 一、单项选择题 1．设图G 的邻接矩阵为 ??? ???? ? ????? ???0101 010******* 11100100110 则G 的边数为( )． A ．6 B ．5 C ．4 D ．3 2．已知图G 的邻接矩阵为 ， 则G 有（ ）． A ．5点，8边 B ．6点，7边 C ．6点，8边 D ．5点，7边 3．设图G ＝
图三 7．设有向图（a ）、（b ）、（c ）与（d ）如图四所示，则下列结论成立的是 ( ) ． 图四 A ．（a ）是强连通的 B ．（b ）是强连通的 C ．（c ）是强连通的 D ．（d ）是强连通的 应该填写：D 8．设完全图K n 有n 个结点(n ≥2)，m 条边，当（ ）时，K n 中存在欧拉回路． A ．m 为奇数 B ．n 为偶数 C ．n 为奇数 D ．m 为偶数 9．设G 是连通平面图，有v 个结点，e 条边，r 个面，则r = ( )． A ．e －v ＋2 B ．v ＋e －2 C ．e －v －2 D ．e ＋v ＋2 10．无向图G 存在欧拉通路，当且仅当( )． A ．G 中所有结点的度数全为偶数 B ．G 中至多有两个奇数度结点 C ．G 连通且所有结点的度数全为偶数 D ．G 连通且至多有两个奇数度结点 11．设G 是有n 个结点，m 条边的连通图，必须删去G 的( )条边，才能确定G 的一棵生成树． A ．1m n -+ B ．m n - C ．1m n ++ D ．1n m -+ 12．无向简单图G 是棵树，当且仅当( )． A ．G 连通且边数比结点数少1 B ．G 连通且结点数比边数少1 C ．G 的边数比结点数少1 D ．G 中没有回路． 二、填空题 1．已知图G 中有1个1度结点，2个2度结点，3个3度结点，4个4度结 点，则G 的边数是 ． 2．设给定图G (如图四所示)，则图G 的点割 ο ο ο ο c a b f
离散数学试题与答案
试卷二试题与参考答案 一、填空 1、 P ：你努力，Q ：你失败。 2、 “除非你努力，否则你将失败”符号化为 ； “虽然你努力了，但还是失败了”符号化为 。 2、论域D={1，2}，指定谓词P 则公式x ??真值为 。 3设A={2，3，4，5，6}上的二元关系}|,{是质数x y x y x R ∨<><=，则 R= （列举法）。 R 的关系矩阵M R = 。 4、设A={1，2，3}，则A 上既不是对称的又不是反对称的关系 R= ；A 上既是对称的又是反对称的关系R= 。 5、设代数系统，其中A={a ，b ，c}, 则幺元是 ；是否有幂等 性 ；是否有对称性 。 6、4阶群必是 群或 群。 7、下面偏序格是分配格的是 。
8、n 个结点的无向完全图K n 的边数为 ，欧拉图的充要条件是 。 二、选择 1、在下述公式中是重言式为（ ） A ．)()(Q P Q P ∨→∧； B ．))()(()(P Q Q P Q P →∧→??； C ．Q Q P ∧→?)(； D ．)(Q P P ∨→。 2、命题公式 )()(P Q Q P ∨?→→? 中极小项的个数为（ ），成真赋值的个数为（ ）。 A ．0； B ．1； C ．2； D ．3 。 3、设}}2,1{},1{,{Φ=S ，则 S 2 有（ ）个元素。 A ．3； B ．6； C ．7； D ．8 。 4、设} 3 ,2 ,1 {=S ，定义S S ?上的等价关系 },,,, | ,,,{c b d a S S d c S S b a d c b a R +=+?>∈∈<><><<=则由 R 产 生 的S S ?上一个划分共有（ ）个分块。 A ．4； B ．5； C ．6； D ．9 。 5、设} 3 ,2 ,1 {=S ，S 上关系R 的关系图为 则R 具有（ ）性质。 A ．自反性、对称性、传递性； B ．反自反性、反对称性； C ．反自反性、反对称性、传递性； D ．自反性 。