离散数学试题一（A 卷答案）
一、（10分）证明?(A ∨B )→?(P ∨Q )，P ，(B →A )∨?P A 。
二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4种判断都是正确的：
(1)甲和乙只有一人参加；
(2)丙参加，丁必参加；
(3)乙或丁至多参加一人；
(4)丁不参加，甲也不会参加。
请推出哪两个人参加了围棋比赛。
三、（10分）指出下列推理中，在哪些步骤上有错误？为什么？给出正确的推理形式。
(1)?x (P (x )→Q (x )) P
(2)P (y )→Q (y ) T (1)，US
(3)?xP (x ) P
(4)P (y ) T (3)，ES
(5)Q (y ) T (2)(4)，I
(6)?xQ (x ) T (5)，EG
四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、
五、（15分）设函数g ：A →B ，f ：B →C ，
(1)若f g 是满射，则f 是满射。
(2)若f g 是单射，则g 是单射。
六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得∈T ?∈R 且∈R ，证明T 是一个等价关系。
七、（15分）若
1∈H 。 八、（15分）(1)若无向图G 中只有两个奇数度结点，则这两个结点一定是连通的。
(2)若有向图G 中只有两个奇数度结点，它们一个可达另一个结点或互相可达吗？
离散数学试题一（B 卷答案）
一、（15分）设计一盏电灯的开关电路，要求受3个开关A 、B 、C 的控制：当且仅当A 和C 同时关闭或B 和C 同时关闭时灯亮。设F 表示灯亮。
(1)写出F 在全功能联结词组{↑}中的命题公式。
(2)写出F 的主析取范式与主合取范式。
二、（10分）判断下列公式是否是永真式？
u v
w
(1)(?xA(x)→?xB(x))→?x(A(x)→B(x))。
(2)(?xA(x)→?xB(x))→?x(A(x)→B(x)))。
三、（15分）设X为集合，A＝P(X)－{?}－{X}且A≠?，若|X|＝n，问
(1)偏序集
(2)偏序集
(3)偏序集
四、（10分）设A＝{1，2，3，4，5}，R是A上的二元关系，且R＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)。
六、（10分）有幺元且满足消去律的有限半群一定是群。
证明设
考虑a，a2，…，a k，…。因为G只有有限个元素，所以存在k＞l，使得a k＝a l。令m＝k－l，有a l*e ＝a l*a m，其中e是幺元。由消去率得a m＝e。
于是，当m＝1时，a＝e，而e是可逆的；当m＞1时，a*a m-1＝a m-1*a＝e。从而a是可逆的，其逆元是a m-1。总之，a是可逆的。
七、（20分）有向图G如图所示，试求：
(1)求G的邻接矩阵A。
(2)求出A2、A3和A4，v1到v4长度为1、2、3和4的路有多少？
(3)求出A T A和AA T，说明A T A和AA T中的第(2，2)元素和第(2，3)元素的意义。
(4)求出可达矩阵P。
(5)求出强分图。
离散数学试题二（A卷答案）
一、（10分）判断下列公式的类型（永真式、永假式、可满足式）？
1)((P→Q)∧Q)?((Q∨R)∧Q) 2)?((Q→P)∨?P)∧(P∨R)
3)((?P∨Q)→R)→((P∧Q)∨R)
二、（8分）个体域为{1，2}，求?x?y（x+y=4）的真值。
三、（8分）已知集合A和B且|A|=n，|B|=m，求A到B的二元关系数是多少？A到B的函数数是多少？
四、（10分）已知A={1,2,3,4,5}和R={<1,2>,<2,1>,<2,3>,<3,4>,<5,4>}，求r(R)、s(R)和t(R)。
五、(10分) 75个儿童到公园游乐场，他们在那里可以骑旋转木马，坐滑行铁道，乘宇宙飞船，已知其中20人这三种东西都乘过，其中55人至少乘坐过其中的两种。若每样乘坐一次的费用是0.5元，公园游乐场总共收入70元，求有多少儿童没有乘坐过其中任何一种。
六、（12分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R
∩S=[a]R∩[a]S。
七（10分）设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C→B×D且?
∈A×C，h(
八、（12分）
九、（10分）已知：D=
离散数学试题二（B卷答案）
一、（10分）求命题公式?(P∧Q)??(?P→R)的主合取范式。
解：?(P∧Q)??(?P→R)?（?(P∧Q)→?(?P→R)）∧（?(?P→R)→?(P∧Q)）
?（(P∧Q)∨(?P∧?R)）∧（(P∨R)∨(?P∨?Q)）
?(P∧Q)∨(?P∧?R)
?(P∨?R)∧（Q∨?P）∧（Q∨?R）
?(P∨Q∨?R)∧(P∨?Q∨?R)∧（?P∨Q∨R）∧（?P∨Q∨?R）
?M1∧M3∧M4∧M5
二、（8分）叙述并证明苏格拉底三段论
三、（8分）已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C)
四、（10分）已知R和S是非空集合A上的等价关系，试证：1）R∩S是A上的等价关系；2）对a∈A，[a]R
∩S=[a]R∩[a]S。
五、(10分) 设A＝{a，b，c，d}，R是A上的二元关系，且R＝{
求r(R)、s(R)和t(R)。
六、(15分) 设A、B、C、D是集合，f是A到B的双射，g是C到D的双射，令h：A×C→B×D且?
∈A×C，h(
七、(12分)设
有a*b-1∈H。
八、（10分）设G=
九.G=
（1）G是否为阿贝尔群？
（2）找出G的单位元；（3）找出G的幂等元（4）求b的逆元和c的逆元
离散数学试题三(A卷答案）
一、证明题（10分）
1) (P∧Q∧A→C)∧(A→P∨Q∨C)? (A∧(P?Q))→C。
2) ?(P↑Q)??P↓?Q。
二、分别用真值表法和公式法求(P→(Q∨R))∧(?P∨(Q?R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。
三、推理证明题（10分）
1）?P∨Q，?Q∨R，R→S P→S。
2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x))
四、某班有学生60人，其中有38人学习PASCAL语言，有16人学习C语言，有21人学习COBOL语言；有3个人这三种语言都学习，有2个人这三种语言都不学习，问仅学习两门语言的学生数是多少？(10分)
五、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) （10分）
六、已知R、S是N上的关系，其定义如下：R={
七、证明：R是传递的?R*R?R（10分）。
八、证明整数集I上的模m同余关系R={
九、若f:A→B和g:B→C是双射，则（gf）-1=f-1g-1（10分）。
离散数学试题三(B卷答案）
一、证明题（10分）
1)((P∨Q)∧?(?P∧(?Q∨?R)))∨(?P∧?Q)∨(?P∧?R)?T
2) ?x?y(P(x)→Q(y))??(?xP(x)→?yQ(y))
三、推理证明题（10分）
1)(P→(Q→S))∧(?R∨P)∧Q?R→S
2) ?x(A(x)→?yB(y))，?x(B(x)→?yC(y))?xA(x)→?yC(y)。
四、只要今天天气不好，就一定有考生不能提前进入考场，当且仅当所有考生提前进入考场，考试才能准时进行。所以，如果考试准时进行，那么天气就好（15分）。
五、已知A、B、C是三个集合，证明A∩(B∪C)=(A∩B)∪(A∩C) （10分）
六、A={ x1,x2,x3 }，B={ y1,y2}，R={
七、设R={<2,1>,<2,5>,<2,4>,<3,4>,<4,4>,<5,2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图（15分）。
八、设R1是A上的等价关系，R2是B上的等价关系，A≠?且B≠?。关系R满足：<
九、设f：A→B，g：B→C，h：C→A，证明：如果h g f＝I A，f h g＝I B，g f h＝I C，则f、g、h均为双射，并求出f－1、g－1和h－1（10分）。
离散数学试题四（A卷答案）
一、（10分）求(P↓Q)→(P∧?(Q∨?R))的主析取范式
二、（10分）在某次研讨会的休息时间，3名与会者根据王教授的口音分别作出下述判断：
甲说：王教授不是苏州人，是上海人。
乙说：王教授不是上海人，是苏州人。
丙说：王教授既不是上海人，也不是杭州人。
王教授听后说：你们3人中有一个全说对了，有一人全说错了，还有一个人对错各一半。试判断王教授是哪里人？
三、（10分）证明tsr(R)是包含R的且具有自反性、对称性和传递性的最小关系。
四、（15分）集合A＝{a，b，c，d，e}上的二元关系R为R＝{
(1)写出R的关系矩阵。
(2)判断R是不是偏序关系，为什么？
五、（10分）设A、B、C和D为任意集合，证明(A－B)×C＝(A×C)－(B×C)。
七、（15分）设
八、（20分）（1）证明在n个结点的连通图G中，至少有n－1条边。
（2）给定简单无向图G＝
C＋2，则G是哈密尔顿
m
1-
图
离散数学试题（四B卷答案）
一、（10分）使用将命题公式化为主范式的方法，证明(P→Q)→(P∧Q)?(Q→P)∧(P∨Q)。
二、（10分）证明下述推理：如果A努力工作，那么B或C感到愉快；如果B愉快，那么A不努力工作；如果D愉快那么C不愉快。所以，如果A努力工作，则D不愉快。
三、（10分）证明?x?y(P(x)→Q(y))?(?xP(x)→?yQ(y))。
四、（10分）设A＝{?，1，{1}}，B＝{0，{0}}，求P(A)、P(B)－{0}、P(B)⊕B。
五、（15分）设X＝{1，2，3，4}，R是X上的二元关系，R＝{<1，1>，<3，1>，<1，3>，<3，3>，<3，2>，<4，3>，<4，1>，<4，2>，<1，2>}
(1)画出R的关系图。
(2)写出R的关系矩阵。
(3)说明R是否是自反、反自反、对称、传递的。
六、（15分）设函数f：R×R→R×R，f定义为：f(
(1)证明f是单射。
(2)证明f是满射。
(3)求逆函数f－1。
(4)求复合函数f－1 f和f f。
七、（15分）给定群
八、（15分）（1）证明在n个结点的连通图G中，至少有n－1条边。
1(n－1)(n－2)的简单无向图G＝
（2）试给出|V|＝n，|E|＝
2
全国2010年7月高等教育自学考试
离散数学试题
课程代码：02324
一、单项选择题（本大题共15小题，每小题1分，共15分）
在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。
1．下列句子不是
．．命题的是（）
A．中华人民共和国的首都是北京B．张三是学生
C．雪是黑色的D．太好了！
2．下列式子不是
．．谓词合式公式的是（）
A．（?x）P(x)→R(y)
B．(?x) ┐P（x）?(?x)(P(x)→Q(x))
C．(?x)(?y)(P(x)∧Q(y))→(?x)R(x)
D．(?x)(P(x,y)→Q(x,z))∨(?z)R(x,z)
3．下列式子为重言式的是（）
A．(┐P∧R)→Q B．P∨Q∧R→┐R
C．P∨(P∧Q) D．(┐P∨Q)?(P→Q)
4．在指定的解释下，下列公式为真的是（）
A．(?x)(P(x)∨Q(x)),P(x):x=1,Q(x):x=2,论域:{1,2}
B．(?x)(P(x)∧Q(x)),P(x):x=1,Q(x):x=2,论域: {1,2}
C．(?x)(P(x) →Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4}
D．(?x)(P(x)→Q(x)),P(x):x>2,Q(x):x=0,论域:{3,4}
5．对于公式(?x) (?y)(P(x)∧Q(y))→(?x)R(x,y)，下列说法正确的是（）
A．y是自由变元B．y是约束变元
C．(?x)的辖域是R(x, y) D．(?x)的辖域是(?y)(P(x)∧Q(y))→(?x)R(x,y)
6．设论域为{1,2}，与公式(?x)A(x)等价的是（）
A．A(1)∨A(2) B．A(1)→A(2)
C．A(1)∧A(2) D．A(2)→A(1)
7．设Z +是正整数集，R 是实数集，f :Z +→R , f (n )=log 2n ,则f （ ）
A ．仅是入射
B ．仅是满射
C ．是双射
D ．不是函数
8．下列关系矩阵所对应的关系具有反对称性的是（ ）
A ．????
??????001110101 B ．??????????101110001 C ．??????????001100100 D ．????
??????001010101 9．设R 1和R 2是集合A 上的相容关系，下列关于复合关系R 1?R 2的说法正确的是（ ）
A ．一定是等价关系
B ．一定是相容关系
C ．一定不是相容关系
D ．可能是也可能不是相容关系
10．下列运算不满足．．．
交换律的是（ ） A ．a *b =a+2b
B ．a *b =min(a ,b )
C ．a *b =|a -b |
D ．a *b =2ab 11．设A 是偶数集合，下列说法正确的是（ ）
A ．是群
B ．是群
C ．是群
12．设*是集合A 上的二元运算，下列说法正确的是（ ）
A ．在A 中有关于运算*的左幺元一定有右幺元
B ．在A 中有关于运算*的左右幺元一定有幺元
C ．在A 中有关于运算*的左右幺元，它们不一定相同
D ．在A 中有关于运算*的幺元不一定有左右幺元
13．题13图的最大出度是（ ）
A ．0
B ．1
C ．2
D ．3
14．下列图是欧拉图的是（ ）
15．一棵树的3个4度点，4个2度点，其它的都是1度，那么这棵树的边数是（ ）
A ．13
B ．14
C ．15
D ．
16
二、填空题（本大题共10小题，每小题2分，共20分）
请在每小题的空格中填上正确答案。错填、不填均无分。
16．请写出表示德摩根律的两个命题公式等价定理___________，___________。
17．n个命题变元的___________称为小项，其中每个变元与它的否定不能同时出现，但两者必须___________。
18．前提引入规则：在证明的任何步骤上都可以___________，简称___________规则。
19．自由变元代入规则是指对某___________出现的个体变元可用个体常元或用与原子公式中所有个体变元不同的个体变元去代入，且___________。
20．设A=?,B={2,4}，则((A)=___________，A×B___________。
21．设A={1,2,3,4}, A上的二元关系R={<1,2>,<2,4>,<3,3>},S={<1,3>,<2,4>,<4,2>}，则R2?S=___________，(R-1)2=___________。
22．设代数系统
23．在
三、计算题（本大题共6小题，每小题5分，共30分）
26．给定论域D={1,2}，f(1)=2, f(2)=1, S(1)=F, S(2)=T, G(1,2)=T, G(2,1)=T,在该赋值下，求式子?x(S( f(x))∧G(x, f(x)))的真值。
27．请通过等值演算法求┐(P∧Q)→(P∨Q)的主析取范式。
28．设A={1,2,3,4}，给定A上二元关系R={<1,1>,<1,2>,<2,4>,<4,2>}，求R的传递闭包。
29．对题29图所示格，找出它的所有的4元子格。
30．用矩阵的方法求题30图中结点u i，u5之间长度为2的路径的数目。
31．求题31图的最小生成树。
四、证明题（本大题共3小题，第32小题8分，第33、34小题各6分，共20分）
32．用推理方法证明(A∨B)→(C∧D),(D∨F)→E├A→E。
33．证明：设
34．设图G有n个结点，n+1条边，证明：G中至少有一个结点度数≥3。
五、应用题（本大题共2小题，第35小题9分，第36小题6分，共15分）
35．符合化下列命题，并构造推理证明：三角函数都是周期函数，有些三角函数是连续函数，所以有些
周期函数是连续函数。
36．两个等价关系的并集不一定是等价关系，试举例说明。
一、单项选择题：（每小题1分，本大题共10分）
1．命题公式)(P Q P ∨→是（ ）。
A 、 矛盾式；
B 、可满足式；
C 、重言式；
D 、等价式。
2．下列各式中哪个不成立（ ）。
A 、)()())()((x xQ x xP x Q x P x ?∨??∨? ；
B 、)()())()((x xQ x xP x Q x P x ?∨??∨?；
C 、)()())()((x xQ x xP x Q x P x ?∧??∧?；
D 、Q x xP Q x P x ∧??∧?)())((。
3．谓词公式)())()((x Q y yR x P x →?∨?中的 x 是（ ）。
A 、自由变元；
B 、约束变元；
C 、既是自由变元又是约束变元；
D 、既不是自由变元又不是约束变元。
4．在0 Φ之间应填入（ ）符号。
A 、= ；
B 、? ；
C 、∈ ；
D 、? 。
5．设< A ， > 是偏序集，A B ?，下面结论正确的是（ ）。
A 、
B 的极大元B b ∈且唯一； B 、B 的极大元A b ∈且不唯一；
C 、B 的上界B b ∈且不唯一；
D 、B 的上确界A b ∈且唯一。
6．在自然数集N 上，下列（ ）运算是可结合的。
（对任意N b a ∈,）
A 、b a b a -=* ；
B 、),max(b a b a =* ；
C 、b a b a 5+=* ；
D 、b a b a -=*。
7．Q 为有理数集N ，Q 上定义运算*为a*b = a + b – ab ,则的幺元为（
）
。 A 、a ； B 、b ； C 、1； D 、0。
8．给定下列序列，（ ）可以构成无向简单图的结点次数序列。
A 、（1，1，2，2，3）；
B 、（1，1，2，2，2）；
C 、（0，1，3，3，3）；
D 、（1，3，4，4，5）。
9．设G 是简单有向图，可达矩阵P(G)刻划下列 （ ）关系。
A 、点与边；
B 、边与点；
C 、点与点；
D 、边与边。
10．一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为（ ）。
A 、5；
B 、7；
C 、9；
D 、8。
二、填空：（每空1分，本大题共15分）
1．在自然数集中，偶数集为1N 、奇数集为2N ，则21N N ?= ；
21N N ? = 。
2．设}3,34,2,2,1{,}4,3,2,1{><><><==，R X ，则
r (R) = ；s (R) = ；t (R) = 。
3．设R 为集合A 上的等价关系，对A a ∈?，集合R a ][= ， 称为元素a 形成的R 等价类，Φ≠R a ][，因为 。
4．任意两个不同小项的合取为 ，全体小项的析取式为 。
5．设为偶数x x Q :)(，为素数x x P :)(，则下列命题：（1）存在唯一偶素数；（2）至多有一个偶素数；分别形式化：（1） ；
（2） 。
6．设T 为根树，若 ，则称T 为m 元树；
若 则称T 为完全m 叉树。
7．含5个结点，4条边的无向连通图（不同构）有 个，
它们是 。
三、判断改正题：（每小题2分，本大题共20分）
1．命题公式B B A A →→∧))((是一个矛盾式。 （ ）
2．任何循环群必定是阿贝尔群，反之亦真。 （ ）
3．根树中最长路径的端点都是叶子。 （ ）
4．若集合A 上的关系R 是对称的，则1-R 也是对称的。 （ ）
5．数集合上的不等关系（≠）可确定A 的一个划分。 （ ）
6．设集合A 、B 、C 为任意集合，若A×B = A×C ，则B = C 。 （ ）
7．函数的复合运算“。”满足结合律。 （ ）
8．若G 是欧拉图，则其边数e 合结点数v 的奇偶性不能相反。 （ ）
9．图G 为（n , m ）图，G 的生成树G T 必有n 个结点。 （ ）
10．使命题公式)(R Q P ∨→的真值为F 的真值指派的P 、Q 、R 值分别是T 、F 、F 。
（ ）
四、简答题（每小题5分，本大题共25分）
1．设>< ,H 和>< ,K 都是群>< ,G 的子群，问>?< ,K H 和>?< ,K H 是否是>< ,G 的子并说明理由
2．设}9432{，，，=A ，}12,10742{，，，=B ，从A 到B 的关系
},,,{b a B b A a b a R 整除且∈∈><=，试给出R 的关系图和关系矩阵，并说明此关系是否为函数？为什么？
3．设>*<,S 是半群，L O 是左零元，对任L O x S x *∈,是否是左零元？为什么？
4．某次会议有20人参加，其中每人至少有10个朋友，这20人拟围一桌入席，用图论知识说明是否可能每人邻做的都是朋友？（理由）
5．通过主合取范式，求出使公式R Q P ∨→??)(的值为F 的真值指派。
五、证明题：（共30分）
1．设R 为集合A 上的二元关系，如果R 是反自反的和可传递的，则R 一定是反对称的。
2．试证明若>*<,G 是群，G H ?，且任意的H a ∈，对每一个G x ∈，有a x x a *=*，则>*<,H 是>*<,G 的子群。
3．设G 是每个面至少由k （3≥k ）条边围成的连通平面图，试证明2
)2(--≤
k v k e ，其中v 为结点数，e 为边数。
4．符号化下列各命题，并说明结论是否有效（用推理规则）。任何人如果他喜欢美术，他就不喜欢体育。每个人或喜欢体育，或喜欢音乐，有的人不喜欢音乐，因而有的人不喜欢美术。
离散数学试题<二>
一、选择题（10×2）
1．下述说法错误的是（ ）
A ．若a A ∈则a A
B ∈? B ．若a A ∈则a A B ∈
C ．若a A B ∈ ，则a A ∈
D ．若B ?A ，则A B A =
2．设G 是连通平面图，G 中有11个结点，5个面，则G 中边的条数是（ ）
A ．10
B ．12
C ．16
D ．14
3．以下关系中能构成函数的是（ ）
A ．{}(1.2),(2.1),(3.4),(4.3)
B ．{}(1.2),(1.1),(2.2),(3.2)
C ．{}(1.2),(2.3),(3.4),(4.1)
D ．{}(1.4),(3.1),(2.3),(4.1),(3.2)
4．图G 如下图所示，则G 是（ ）
A ．欧拉图，非哈密顿图
B ．哈密顿图，非欧拉图
C ．非欧拉图，非哈密图
D ．欧拉图且哈密顿图
5．下列代数系统能够构成群的是（ ）
A ．（Q ；+）
B ．（Q ，-）
C ．（R ；·）
D ．（I ，+）
6．关于有补格的描述不正确的是（ ）
A ．有补格必有界
B ．有补格中每个元素的补元一定存在
C ．有补格满足德摩根定律
D ．有补格的元素不一定有限
7．若图G 的所有回路均为偶数长，则G （ ）
A ．G 是欧拉图
B ．G 是哈图
C ．G 是平面图
D ．G 是二部图
8．下述公式正确的是（ ）
A ． P Q Q P →?→
B ．P Q Q P →?∨
C ．P Q Q P →??→?
D ．P Q P Q →??→?
9．设A=｛a,b,c,d ｝，A 上的关系ρ=｛（a,b),(b,a),(c,a),(c,b),(a,a),(b,b)｝,则
ρ是（ ）
A ．自反的
B ．对称的
C ．反对称的
D ．传递的
10．复合语句“他工作很努力；但是思想僵化”中的逻辑联结词为（ ）
A ．∨
B ．∧
C ．→
D ．?
二、填空（10×2）
1、设{1,2,3,4,5,6,7},{1,3,5,7},{1,2,6,7}U A B ===
则=-'B A ________________________________。
2、已知{0,1,2,3},{(0,1),(1,2),(2,1),(0,0)}A ρ==，那么2ρ=_______________
3、已知2()42()5f x x g x x gf =-=+=则__________________
4、,R 为实数及四则运算的乘法，请写出的幂等元___________________
5、相比于独异点和半群，群的最重要性质是___________________
6、设;,L <∨∧>为代数系统，,∧∨为二元运算若,∧∨还满足交换律，结合律和__________律，
则;,L <∨∧>为一个格。
7、图G 中长度最短的路称为___________________
8、符号化下列语句：他不但学习好，而且身体棒___________________
9、集合代数是一种___________________格
10、半群（A ：是/B ：不是）___________________群
三、简答题（3×10）
1、一棵树有1个结点度数为5，2个结点度数为4，5个结点度数为2，14个结点度数为1，问度数为3的结点有几个？
2、判断下面两个图是否为平面图，若认为是平面图，请画出其相应的平面图解，否则说明它为什么不是平面图。（10分）
G １ G ２
3、:,:f A B g B C →→，且f 和g 都是可逆的，证明函数复合运算满足：111()gf f g ---=
四、证明题（3×10）
1、试证明群
2、若G 是连通平面图，则G 中必有一个结点V ，使得deg(V)≤5
3、形式证明：如果他努力学习，则他不会不及格；如果他不爱打麻将，则他会努力学习；结果是他考试不及格，那么他肯定爱打麻将。
24
3V
没有标题
一、填空题：（每空1分，本大题共15分）
1．给定命题公式A 、B ，若 ，则称A 和B 是逻辑相等的。
2．命题公式)(Q P →?的主析取范式为 ，主合取范式的编码表示
为 。
3．设E 为全集， ，称为A 的绝对补，记作～A ，
且～（～A ）= ，～E = ，～Φ= 。
4．设},,{c b a A =考虑下列子集
}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =，}},{},{{3c b a S =，}},,{{4c b a S =
}}{},{},{{5c b a S =，}},{},{{6c a a S =
则A 的覆盖有 ，A 的划分有 。
5．设S 是非空有限集，代数系统＜ （S ），?，?＞中， （S ）对?的幺元为 ， 零元为 。 （S ）对?的幺元为 ，零元为 。
6．若>= W(G-S) S 成立，其中W(G-S)是 。 二、单项选择题：（每小题1分，本大题共10分） 1．下面命题公式（ ）不是重言式。 A 、)(Q P Q ∨→； B 、P Q P →∧)(； C 、)()(Q P Q P ∨?∧?∧?； D 、)()(Q P Q P ∨??→。 2．命题“没有不犯错误的人”符号化为（ ）。 设x x M ： )(是人，x x P ：)(犯错误。 A 、))()((x P x M x ∧?； B 、)))()(((x P x M x ?→??； C 、)))()(((x P x M x ∧??； D 、)))()(((x P x M x ?∧??。 3．设}{Φ=A ，B = ( (A))，下列各式中哪个是错误的（ ）。 A 、 B ?Φ； B 、B ?Φ}{， C 、B ∈Φ}}{{； D 、?ΦΦ}}{,{ (A)。 4．对自然数集合N ，哪种运算不是可结合的，运算定义为任N b a ∈,（ ）。 A 、),min(b a b a =*； B 、b a b a 2+=*； C 、3++=*b a b a ； D 、)3(mod ,b a b a =*。 5．设Z 为整数集，下面哪个序偶不够成偏序集（ ）。 A 、)(,小于关系：<>< B 、)(,小于等于关系：≤>≤ C 、)(,于关系：等=>= D 、)(,关系：整除> 6．任意具有多个等幂元的半群，它（ ）。 A 、不能构成群； B 、不一定能构成群； C 、不能构成交换群； D 、能构成交换群。 7．设≤><,A 是一个有界格，它也是有补格，只要满足（ ）。 A 、每个元素都有一个补元； B 、每个元素都至少有一个补元； C 、每个元素都无补元； D 、每个元素都有多个补元。 8．设>= A 、完全图； B 、树； C 、简单图； D 、多重图。 9．给定无向图>= A 、},,,{4341><> B 、},,,{6451><> C 、},,,{8474><> D 、},,,{3221><> 10．有n 个结点)3(≥n ，m 条边的连通简单图是平面图的必要条件（ ）。 A 、63-≥m n ； B 、63-≤m n ； C 、63-≥n m ； D 、63-≤n m 。 三、判断改正题：（每小题2分，本大题共20分） 1．设A ，B 为任意集合，不能B A B A ∈?且。 （ ） 2．设R 是集合A 上的关系，若21,R R 是对称的，则21R R 也是对称的。（ ） 3．群中可以有零元（对阶数大于1的群）。 （ ） 4．循环群一定是Abel 群。 （ ） 5．每一个链都是分配格。 （ ） 6．不可能有偶数个结点，奇数条边的欧拉图。 （ ） 7．图G 中的每条边都是割边，则G 必是树。 （ ） 9．公式)())()((y R x Q x P x ∧→?中x ?的辖域为)(x P 。 （ ） 10．公式),()(y x yQ x xP ?→?的前束范式为 )),()((y x Q x P y x →??。 （ ） 四、简答题（共20分） 1．用等值演算法求下面公式的主析取范式，并求其成真赋值。 R Q P →∨)( 2．集合}4,3,2,1{=A 上的关系 }4,4,3,4,4,3,1,3,3,3,2,2,3,1,1,1{><><><><><><><><=R ，写出关系矩阵R M ，画出关系图并讨论R 的性质。 3．有n 个药箱，若每两个药箱里有一种相同的药，而每种药恰好在两个药箱中，问共有多少种 药品？ 4．一棵树T 中，有3个2度结点，一个3度结点，其余结点都是树叶。 （1）T 中有几个结点； （2）画出具有上述度数的所有非同构的无向图。 五、证明题：（35分） 1．符号化下列各题，并说明结论是否有效（用推理规则）。 凡15的倍数都是3的倍数，凡15的倍数都是5的倍数，所以有些5的倍数是3的倍数。 2．用推理规则证明： C A F E F D E B D C B A →∧?∨?∧∨?→∧→,)(,)()(,)()(├ A 3．设函数B A f →：，C B g →：，若f g 是满射的，则g 是满射的。 4．当且仅当G 的一条边e 不包含在G 的闭迹中时，e 才是G 的割边。 5．设>∧∨<,,S 是一个分配格，S a ∈，令a x x f ∨=)(，对任意S a ∈，证明：f 是>∧∨<,,S 到自身的格同态映射。 2006～2007学年 第1学期 《离散数学》试卷 A （试卷共6页，答题时间120分钟） 一、选择题（每小题 2分，共 20 分。请将答案填在下面的表格内） 1、从集合分类的角度看,命题公式可分为( ) A.永真式、矛盾式 B. 永真式、可满足式、矛盾式 C. 可满足式、矛盾式 D. 永真式、可满足式 2、设B 不含有x ，))((B x A x →?等值于 ( ) A.B x xA →?)( B.))((B x A x ∨? C.B x xA →?)( D.))((B x A x ∧? 3、设S,T,M 是集合，下列结论正确的是（ ） A ．如果S ∪T=S ∪M ，则T=M B ．如果S-T=Φ，则S=T C ．S S S =⊕ D ．)(~T S T S =- 4、设R 是集合A 上的偏序关系，则R 不一定是( ) A.自反的 B. 对称的 C. 反对称的 D. 传递的 5 设R 为实数集，定义R 上4个二元运算，不满足结合律的是（ ）。 A. f 1(x,y)= x+y B. f 2(x,y)=x-y C. f 3(x,y)=xy D. f 4(x,y)=max{x,y} 6、设 A.交换律 B. 结合律 C. 吸收律 D. 消去律 7、设A={1,2},则群>?<),(A P 的单位元和零元是( ) A. Φ与A B. A 与Φ C. {1}与Φ D. {1}与A 8、下列编码是前缀码的是( ). A.{1,11,101} B.{1,001,0011} C. {1,01,001,000} D.{0,00,000} 9、下图中既是欧拉图又是哈密顿图的是（ ） A ． 9K B ．10K C ．3,2K D ．3,3K 10、下图所示的二叉树中序遍历的结果是（ ） A ．abcde B ．edcba C ．bdeca D ．badce 二、填空题（每题3分，共24分） 1、含3个命题变项的命题公式的主合取范式为76430M M M M M ∧∧∧∧, 则它的主析取范式为 。(的形势表示成m m ∨) 2、〈4Z ，⊕〉模4加群， 则3是 阶元，3⊕3= ，3的逆元是 。 3、设V= 4、设??? ? ??=645132654321π是集合A={1，2，3，4,5,6}上的一个置换，则把它表示成不相交的轮换的积是 。 4、已知n 阶无向简单图G 有m 条边，则G 的补图有 条边。 5、一个有向图是强连通的充分必要条件是 。 7、已知n 阶无向图G 中有m 条边，各顶点的度数均为3。又已知2n-3=m ， 则m= . 8、在下图中从A 点开始，用普里姆算法构造最小生成树，加入生成树的第三条边是 （ ）。 A B C D 24 三、计算题（每题9分，共 36分） 1、已知命题公式)()(p q q p ∨?→→?， (1) 构造真值表。 (2) 求主析取范式(要求通过等值演算推出)。 2、R 1={<1,2>,<1,3>,<2,3>}, R 2={<2,2>,<2,3>,<3,4>},求： (1)21R R - （２）11-R (３) 求12R R ３、设 （1）画R 出的哈斯图； （2）求A 的极大元和极小元； （3）求B={4,6}的上确界和下确界。 ４、画一棵带权为1，1，1，3，3，5，8的最优二叉树T ，并计算它的权W （T ）。 四、证明题（共 20分） 1、（7分）前提： r p q s q p ?∨→→,),( 结论: s r → 2、（7分）A={(0,0),(0,1),(1,0),(1,3),(2,2),(2,3),(3,1)}, R={<(a,b),(c,d)>| (a,b),(c,d)∈A 且a+b=c+d }. (1)证明：R 是A 上的等价关系． (2)给出R 确定的对A 的划分(分类). 3、（6分）设>< ,G 是群, },|{x y y x G y G x x S =∈?∈=且对于, 证明S 是G 的子群. 离散数学必备知识点总 结 Document number：NOCG-YUNOO-BUYTT-UU986-1986UT 总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项(m)之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R的顺序依次写； 6.真值表中值为1的项为极小项，值为0的项为极大项； 7.n个变元共有n2个极小项或极大项，这n2为(0~n2-1)刚好为化简完后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法(=>)：真值表法；分析法(假定前键为真推出后键为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P规则，T规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取^; 3.既有存在又有全称量词时，先消存在量词，再消全称量词； 第四章集合 1.N，表示自然数集，1,2,3……，不包括0； 2.基：集合A中不同元素的个数，|A|； 3.幂集：给定集合A，以集合A的所有子集为元素组成的集合，P(A)； 4.若集合A有n个元素，幂集P(A)有n2个元素，|P(A)|=||2A=n2； 5.集合的分划：(等价关系) ①每一个分划都是由集合A的几个子集构成的集合； ②这几个子集相交为空，相并为全(A)； 6.集合的分划与覆盖的比较： 分划：每个元素均应出现且仅出现一次在子集中； 覆盖：只要求每个元素都出现，没有要求只出现一次； 第五章关系 1.若集合A有m个元素，集合B有n个元素，则笛卡尔A×B的基 2种不同的关系； 数为mn，A到B上可以定义mn 2.若集合A有n个元素，则|A×A|=2n，A上有22n个不同的关系； 常熟理工学院20 ～20 学年第学期 《离散数学》考试试卷（试卷库01卷） 试题总分： 100 分考试时限：120 分钟 题号一二三四五总分阅卷人得分 一、单项选择题（每题2分，共20分） 1.下列表达式正确的有( ) （A）（B）（C）（D） 2.设P：2×2=5，Q：雪是黑的，R：2×4=8，S：太阳从东方升起，下列( )命题的真值为 真。 （A）（B）（C）（D） 3.集合A={1,2,…,10}上的关系R={ 1．n个命题变元组成的命题公式共有种不同的等价公式。 2．设〈L，≤〉为有界格，a为L中任意元素，如果存在元素b∈L,使，则称b是a 的补元。 3．设*，Δ是定义在集合A上的两个可交换二元运算，如果对于任意的x,y∈A,都有 ,则称运算*和运算Δ满足吸收律。 4．设T是一棵树，则T是一个连通且的图。 5．一个公式的等价式称作该公式的主合取范式是指它仅由组成。 6．量词否定等价式? ("x)P(x) ?，? ($x)P(x) ?。 7．二叉树有5个度为2的结点，则它的叶子结点数为。 8．设 第一章习题 1.1&1.2 判断下列语句是否为命题,若是命题请指出是简单命题还 是复合命题.并将命题符号化,并讨论它们的真值. (1) √2是无理数. 是命题,简单命题.p:√2是无理数.真值:1 (2) 5能被2整除. 是命题,简单命题.p:5能被2整除.真值:0 (3)现在在开会吗? 不是命题. (4)x+5>0. 不是命题. (5) 这朵花真好看呀! 不是命题. (6) 2是素数当且仅当三角形有3条边. 是命题,复合命题.p:2是素数.q:三角形有3条边.p?q真值:1 (7) 雪是黑色的当且仅当太阳从东方升起. 是命题,复合命题.p:雪是黑色的.q:太阳从东方升起. p?q真值:0 (8) 2008年10月1日天气晴好. 是命题,简单命题.p:2008年10月1日天气晴好.真值唯 一. (9) 太阳系以外的星球上有生物. 是命题,简单命题.p:太阳系以外的星球上有生物.真值唯一. (10) 小李在宿舍里. 是命题,简单命题.P:小李在宿舍里.真值唯一. (11) 全体起立! 不是命题. (12) 4是2的倍数或是3的倍数. 是命题,复合命题.p:4是2的倍数.q:4是3的倍数.p∨q 真值:1 (13) 4是偶数且是奇数. 是命题,复合命题.P:4是偶数.q:4是奇数.p∧q真值:0 (14) 李明与王华是同学. 是命题,简单命题.p: 李明与王华是同学.真值唯一. (15) 蓝色和黄色可以调配成绿色. 是命题,简单命题.p: 蓝色和黄色可以调配成绿色.真值:1 1.3 判断下列各命题的真值. (1)若 2+2=4,则 3+3=6. (2)若 2+2=4,则 3+3≠6. (3)若 2+2≠4,则 3+3=6. (4)若 2+2≠4,则 3+3≠6. (5)2+2=4当且仅当3+3=6. (6)2+2=4当且仅当3+3≠6. (7)2+2≠4当且仅当3+3=6. (8)2+2≠4当且仅当3+3≠6. 答案: 设p:2+2=4,q:3+3=6,则p,q都是真命题. (1)p→q,真值为1. (2)p→┐q,真值为0. (3)┐p→q,真值为1. (4)┐p→┐q,真值为1. (5)p?q,真值为1. (6)p?┐q,真值为0. (7)┐p?q,真值为0. (8)┐p?┐q,真值为1. 1．4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号。 p:今天是1号。 q:明天是2号。 符号化为：p→q 真值为：1 （2）如果今天是1号，则明天是3号。 p:今天是1号。 第二章谓词逻辑 2—1基本概念 例题1. 所有的自然数都是整数。 设N(x):x是自然数。I(x):x是整数。此命题可以写成?x(N(x)→I(x)) 例题2. 有些自然数是偶数。 设E(x):x是偶数。此命题可以写成?x(N(x)∧E(x)) 例题3. 每个人都有一个生母。 设P(x):x是个人。M(x,y):y是x的生母。此命题可以写 成:?x(P(x)→?y(P(y)∧M(x,y))) 2-2 谓词公式及命题符号化 例题1. 如果x是奇数,则2x是偶数。 其中客体x与客体2x之间就有函数关系,可以设客体函数g(x)=2x, 谓词O(x):x是奇数,E(x):x是偶数, 则此命题可以表示为:?x(O(x)→E(g(x))) 例题2 小王的父亲是个医生。 设函数f(x)=x的父亲,谓词D(x):x是个医生,a:小王,此命题可以表示为D(f(a))。 例题3 如果x和y都是奇数,则x+y是偶数。 设h(x,y)=x+y ,此命题可以表示为:?x?y((O(x)∧O(y))→E(h(x,y)) 命题的符号表达式与论域有关系 两个公式:一般地,设论域为{a1,a2,....,an},则有 (1). ?xA(x)?A(a1)∧A(a2)∧......∧A(an) (2). ?xB(x)?B(a1)∨B(a2)∨......∨B(an) 1.每个自然数都是整数。该命题的真值是真的。 表达式?x(N(x)→I(x))在全总个体域的真值是真的, 因?x(N(x)→I(x))?(N(a1)→I(a1))∧(N(a2)→I(a2))∧…∧(N(an)→I(an)) 式中的x不论用自然数客体代入,还是用非自然数客体代入均为真。例如(N(0.1)→I(0.1))也为真。 而?x(N(x)∧I(x))在全总个体域却不是永真式。 试卷二试题与参考答案 一、填空 1、 P:您努力,Q:您失败。 2、 “除非您努力,否则您将失败”符号化为 ; “虽然您努力了,但还就是失败了”符号化为 。 2、论域D={1,2},指定谓词P P (1,1) P (1,2) P (2,1) P (2,2) T T F F 则公式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、设代数系统 二、选择 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.自反性 。 6、设 ο,+ 为普通加法与乘法,则( )>+<ο,,S 就是域。 A.},,3|{Q b a b a x x S ∈+== B.},,2|{Z b a n x x S ∈== C.},12|{Z n n x x S ∈+== D.}0|{≥∧∈=x Z x x S = N 。 7、下面偏序集( )能构成格。 第一章习题 1.1判断下列语句是否为命题，若是命题请指出是简单命题还是复合命题。（1）2是无理数。 （2）5能被2整除。 （3）现在开会吗？ （4）x+5>0 （5）这朵花真是好看！ （6）2是素数当且仅当三角形有三条边。 （7）雪是黑色的当且仅当太阳是从东方升起。 （8）2000年10月1日天气晴好。 （9）太阳系以外的星球上有生物。 （10）小李在宿舍里。 （11）全体起立。 （12）4是2的倍数或是3的倍数。 （13）4是偶数且是奇数。 （14）李明和王华是同学。 （15）蓝色和黄色可以调配成绿色。 1..2 将上题中的命题符号化，并讨论他们的真值。 1.3判断下列各命题的真值。 （1）若2+2=4，则3+3=6； （2）若2+2=4，则3+3≠6； （3）若2+2≠=4，则3+3=6； （4）若2+2≠=4，则3+3≠=6； （5）2+2=4，当且仅当3+3=6； （6）2+2=4，当且仅当3+3≠6； （7）2+2≠4，当且仅当3+3=6； （8）2+2≠4，当且仅当3+3≠6； 1.4将下列命题符号化，并讨论其真值。 （1）如果今天是1号，则明天是2号； （2）如果今天是1号，则明天是3号； 1.5将下列命题符号化。 （1）2是偶数不是素数； （2）小王不但聪明而且用功； （3）虽然天气冷。老王还是来了； （4）他一边吃饭，一边看电视； （5）如果天下大雨，他就乘公交汽车来； （6）只有天下大雨，他才乘公交汽车来； （7）除非天下大雨，否则他不乘公交汽车来； （8）不经一事，不长一智； 1.5设p,q的真值为0 ，r,s的真值为1，求下列命题公式的真值。（1）p∨(q∧r); 离散数学试题及答案 Company number【1089WT-1898YT-1W8CB-9UUT-92108】 一、填空题 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＝(PQ)∧R，则G的主析取范式是 _______________________________ __________________________________________________________. 6设A、B为两个集合,A={1,2,4},B={3,4},则从AB＝ _________________________;AB＝_________________________;A－B＝_____________________. 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是 ______________________,________________________,__________________ _____________. 8.设命题公式G＝(P(QR))，则使公式G为真的解释有 __________________________， _____________________________,__________________________. 9.设集合A＝{1,2,3,4},A上的关系 R 1={(1,4),(2,3),(3,2)},R 2 ={(2,1),(3,2),(4,3)},则 数理逻辑部分 第2章一阶逻辑 2.1 一阶逻辑基本概念 个体词（个体）: 所研究对象中可以独立存在的具体或抽象的客体个体常项：具体的事物，用a, b, c表示 个体变项：抽象的事物，用x, y, z表示 个体域: 个体变项的取值范围 有限个体域，如{a, b, c}, {1, 2} 无限个体域，如N, Z, R, … 全总个体域: 宇宙间一切事物组成 谓词: 表示个体词性质或相互之间关系的词 谓词常项：F(a)：a是人 谓词变项：F(x)：x具有性质F 一元谓词: 表示事物的性质 多元谓词(n元谓词, n≥2): 表示事物之间的关系 如L(x,y)：x与y有关系L，L(x,y)：x≥y，… 0元谓词: 不含个体变项的谓词, 即命题常项或命题变项 量词: 表示数量的词 全称量词?: 表示任意的, 所有的, 一切的等 如?x 表示对个体域中所有的x 存在量词?: 表示存在, 有的, 至少有一个等 如?x表示在个体域中存在x 一阶逻辑中命题符号化 例1 用0元谓词将命题符号化 要求：先将它们在命题逻辑中符号化，再在一阶逻辑中符号化(1) 墨西哥位于南美洲 在命题逻辑中, 设p:墨西哥位于南美洲 符号化为p, 这是真命题 在一阶逻辑中, 设a：墨西哥，F(x)：x位于南美洲 符号化为F(a) 例2 在一阶逻辑中将下面命题符号化 (1)人都爱美; (2) 有人用左手写字 分别取(a) D为人类集合, (b) D为全总个体域 . 解：(a) (1) 设G(x)：x爱美, 符号化为?x G(x) (2) 设G(x)：x用左手写字, 符号化为?x G(x) (b) 设F(x)：x为人，G(x)：同(a)中 离散数学（本）复习题 1.请给出公式G=（P→（Q→P））→（?P→（P→Q））的真值表。 2.设A={1，2，3，4，5，6}，其上一个划分为C={{1}，{2，4}，{3，5，6}}，请给出对应划分C的等价关系R C。 3.R，S是集合A上的两个关系。试证明下列等式： （1）(R?S)-1= S-1?R-1 （2）(R-1)-1= R （3）(R∪S)-1= R-1∪S-1 （4）(R∩S)-1= R-1∩S-1 4.设R是集合A上的关系，令 R+={(x, y)|x∈A，y∈A，并且存在n>0，使得xR n y}， 则称R+是R的传递闭包，证明：R+是包含R的最小具有传递性的关系。 5.若非空集合上的非空关系R是反自反的，是对称的，试证明R不是传递的。 6.设A={1，2，3，4，5，6，7，8，9}，R为A上的整除关系，请给出部分序集（A，R）的Hasse图。 7.设G是含有3个不同原子的命题公式，当G是恒假公式的时候，G的主析取范式中有多少极小项，主合取范式中有多少极大项？ 8.有人说：“等价关系中的反身性可以不要，因为反身性可以从对称性和传递性推出：由对称性，从a ? b可得b ? a，再由传递性得a ? a”。你的意见呢？ 9.若集合A上的关系R，S具有对称性，证明：R?S具有对称性的充要条件为R?S= S?R。 10.若R是等价关系，试证明R-1也是等价关系。 11.给P和Q指派真值1，给R和S指派真值0，求出下面命题的真值： a) (P∧(Q∧R))∨?((P∨Q)∧(R∨S)) b) (?(P∧Q)∨?R)∨(((?P∧Q)∨?R)∧S) c) (?(P∧Q)∨?R)∨((Q??P)→(R∨?S)) d) (P∨(Q→(R∧?P)))?(Q∨?S) 12.试将下列公式化成等价的前束范式： (1)?x(P(x)→?yQ(x，y))； (2)?x((??yP(x，y))→(?zQ(z)→R(x)))； (3)?x?y(?zP(x，y，z)∧(?uQ(x，u)→?vQ(y，v)))。 13.设S={G1，…，G n}是命题公式集合。试求出在不增加新原子的情况下从S出发演绎出的所有命题公式。 14.证明下面的等价式： (1) (?P∧(?Q∧R))∨(Q∧R)∨(P∧R)=R (2) P→(Q→P)=?P→(P→Q) (3) P→(Q∨R)=(P→Q)∨(P→R) (4) (P→Q)∧(R→Q)=(P∨R)→Q 15．找出下面公式的Skolem范式： (1)?(?xP(x)→?y?zQ(y，z))； (2)?x(?E(x，0)→(?y(E(y，g(x))∧?z(E(z，g(x))→E(y，z)))))。 16．G=(P，L)是有限图，设P(G)，L(G)的元数分别为m，n。证明：n≤2 C，其中2m C表示 m m中取2的组合数。 离散数学部分概念和公式总结 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，p、q、r等不仅可以代表命题常项，还可以代表命题变项，这样的复合命题形式称为命题公式。 命题的赋值：设A为一命题公式，p ,p ,…,p 为出现在A中的所有命题变项。给p ,p ,…,p 指定一组真值，称为对A的一个赋值或解释。若指定的一组值使A的值为真，则称成真赋值。真值表：含n（n≥1）个命题变项的命题公式，共有2^n组赋值。将命题公式A在所有赋值下的取值情况列成表，称为A的真值表。 命题公式的类型：（1）若A在它的各种赋值下均取值为真，则称A为重言式或永真式。 （2）若A在它的赋值下取值均为假，则称A为矛盾式或永假式。 （3）若A至少存在一组赋值是成真赋值，则A是可满足式。 主析取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合取式全是极小项，则称该析取范式为A的主析取范式。 主合取范式：设命题公式A中含n个命题变项，如果A得析取范式中的简单合析式全是极大项，则称该析取范式为A的主析取范式。 命题的等值式：设A、B为两命题公式，若等价式A?B是重言式，则称A与B是等值的，记作A<=>B。 约束变元和自由变元：在合式公式?x A和?x A中，称x为指导变项，称A为相应量词的辖域，x称为约束变元，x的出现称为约束出现，A中其他出现称为自由出现（自由变元）。一阶逻辑等值式：设A，B是一阶逻辑中任意的两公式，若A?B为逻辑有效式，则称A与B是等值的，记作A<=>B，称A<=>B为等值式。 前束范式：设A为一谓词公式，若A具有如下形式Q1x1Q2x2Q k…x k B，称A为前束范式。集合的基本运算：并、交、差、相对补和对称差运算。 笛卡尔积：设A和B为集合，用A中元素为第一元素，用B中元素为第二元素构成有序对组成的集合称为A和B的笛卡尔积，记为A×B。 二元关系：如果一个集合R为空集或者它的元素都是有序对，则称集合R是一个二元关系。特殊关系：（1）、空关系：Φ（2）全域关系：EA={ 离散数学练习题 1、图中度为零的结点称为孤立结点。 A. 正确 B. 错误 正确：【A】 2、域是整环。 A. 正确 B. 错误 正确：【A】 3、有限格都是有界格。 A. 正确 B. 错误 正确：【A】 4、连通且不含圈的图称为树。 A. 正确 B. 错误 正确：【A】 5、“如果1+1≠3，则2+2≠4”是真命题。 A. 正确 B. 错误 正确：【B】 6、无向图G为欧拉图，则G是连通的。 A. 正确 B. 错误 正确：【A】 7、若A和B都是谓词公式，则(A∧B)、(A∨B)、(A→B)、(A<->B)都是谓词公式。 A. 正确 B. 错误 8、设A, B, C是命题公式，则AVBV﹁C 也是命题公式。 A. 正确 B. 错误 正确：【A】 9、设〈L，≤〉是格，则格的交∧和并∨运算满足等幂律。 A. 正确 B. 错误 正确：【A】 10、“x+3>1。”是命题。 A. 正确 B. 错误 正确：【B】 11、半群满足交换律。 A. 正确 B. 错误 正确：【B】 12、在任何图中，奇数度的结点数必是偶数。 A. 正确 B. 错误 正确：【A】 13、在格〈L，∨，∧〉中，如果交运算对并运算是可分配的，则并运算对交运算也是可分配的。 A. 正确 B. 错误 正确：【A】 14、完全图Kn没有割集，它的连通性能是最好的。 A. 正确 B. 错误 15、对任意集合A，都有??A。 A. 正确 B. 错误 正确：【A】 17、强连通图一定是单向连通图。 A. 正确 B. 错误 正确：【A】 18、代数系统〈G，°〉为群的条件是存在零元素。 A. 正确 B. 错误 正确：【B】 19、对应日常生活中的“任意的”，“所有的”，“一切的”等词，用符号“任意”表示。 A. 正确 B. 错误 正确：【A】 20、如果a是集合A中的元素，则称a属于A，记作a?A。 A. 正确 B. 错误 正确：【B】 21、A,B是集合,P（A），P（B）为其幂集,且,则P(A)∩P(B)为（） A. B. C. D. 正确：【B】 22、设M={x|f1(x)=0},N={x|f2(x)=0}，则方程f1(x)?f2(x)=0的解 离散数学试题一（A 卷答案） 一、（10分）证明(A ∨B )(P ∨Q )，P ，(B A )∨P A 。 二、（10分）甲、乙、丙、丁4个人有且仅有2个人参加围棋优胜比赛。关于谁参加竞赛，下列4 种判断都是正确的： (1)甲和乙只有一人参加； (2)丙参加，丁必参加； (3)乙或丁至多参加一人； (4)丁不参加，甲也不会参加。 请推出哪两个人参加了围棋比赛。 三、（10分）指出下列推理中，在哪些步骤上有错误为什么给出正确的推理形式。 (1)x (P (x ) Q (x )) P (2)P (y )Q (y ) T (1)，US (3)xP (x ) P (4)P (y ) T (3)，ES (5)Q (y ) T (2)(4)，I (6)xQ (x ) T (5)，EG 四、（10分）设A ＝{a ，b ，c}，试给出A 上的一个二元关系R ，使其同时不满足自反性、反自反性、 五、（15分）设函数g ：A →B ，f ：B →C ， (1)若f o g 是满射，则f 是满射。 (2)若f o g 是单射，则g 是单射。 六、（15分）设R 是集合A 上的一个具有传递和自反性质的关系，T 是A 上的关系，使得T R 且R ，证明T 是一个等价关系。 七、（15分）若 数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( A )。 (A) 您打算考硕士研究生不？ (B) 太阳系以外的星球上有生物。 (C) 离散数学就是计算机系的一门必修课。 (D) 雪就是黑色的。 ?命题公式P→(P∨?P)的类型就是( A ) (A) 永真式(B) 矛盾式 (C) 非永真式的可满足式(D) 析取范式 ?A就是重言式,那么A的否定式就是( A ) A、矛盾式 B、重言式 C、可满足式 D、不能确定 ?以下命题公式中,为永假式的就是( C ) A、p→(p∨q∨r) B、(p→┐p)→┐p C、┐(q→q)∧p D、┐(q∨┐p)→(p∧┐p) ?命题公式P→Q的成假赋值就是( D ) A、 00,11 B、 00,01,11 C、10,11 D、 10 ?谓词公式) x xP∧ ?中,变元x就是 ( B ) R , ( x ) (y A、自由变元 B、既就是自由变元也就是约束变元 C、约束变元 D、既不就是自由变元也不就是约束变元 ?命题公式P→(Q∨?Q)的类型就是( A )。 (A) 永真式 (B) 矛盾式 (C) 非永真式的可满足式 (D) 析取范式 ?设B不含变元x,) x x→ ?等值于( A ) A ) ( (B A、B (D、B x xA→ x ?) ( ( ?C、B x∧ A ?) (B、) ?) xA→ x ) ( A x (B x∨ ?下列语句中就是真命题的就是( D )。 A.您就是杰克不？ B.凡石头都可练成金。 C.如果2+2=4,那么雪就是黑的。 D.如果1+2=4,那么雪就是黑的。 ?从集合分类的角度瞧,命题公式可分为( B ) A、永真式、矛盾式 B、永真式、可满足式、矛盾式 C、可满足式、矛盾式 D、永真式、可满足式 ?命题公式﹁p∨﹁q等价于( D )。 A、﹁p∨q B、﹁(p∨q) C、﹁p∧q D、 p→﹁q ?一个公式在等价意义下,下面写法唯一的就是( D )。 (A) 范式 (B) 析取范式 (C) 合取范式 (D) 主析取范式 ?下列含有命题p,q,r的公式中,就是主析取范式的就是( D )。 离散数学复习资料 一、填空 1. 命题“对于任意给定的正实数，都存在比它大的实数”令F(x)：x 为实数，y x y x L >:),(则命题的逻辑谓词公式为 。 2. 设p ：王大力是100米冠军，q ：王大力是500米冠军，在命题逻辑中，命题“王大力不 但是100米冠军，而且是500米冠军”的符号化形式为 。命题“存在一个人不但是100米冠军，而且是500米冠军”的符号化形式为____。 3. 选择合适的论域和谓词表达集合A=“直角坐标系中，单位元（不包括单位圆周）的点集” 则A= 。 4. 设 P （x ）：x 是素数， E(x)：x 是偶数，O(x)：x 是奇数 N (x,y)：x 可以整数y 。则谓词 (()(()(,)))x P x y O y N y x ?→?∧ 的自然语言是 对于任意一个素数都存在一个奇数使 该素数都能被整除 。 5. 设个体域是{a,b}，谓词公式()()()()x P x x P x ??∨?写成不含量词的形式是 。 6. 谓词(((,)(,))(,,))x y z P x z P y z uQ x y u ???∧→?的前束范式为 。 7. 命题公式)))(((R Q Q P P A →?∧→?∨?的主合取范式为 ，其编码表示为 。 8. 设E 为全集， ，称为A 的绝对补，记作～A ，且～（～A ）= ，～E = ， ～Φ= 。 9. 设={256},{234},{134}A B C ==， ，，，，，，则A-B= ，A ⊕B = ，A ×C = 。 10. 设},,{c b a A =考虑下列子集}},{},,{{1c b b a S =，}},{},,{},{{2c a b a a S =， 总结离散数学知识点 第二章命题逻辑 1.→，前键为真，后键为假才为假；<—>，相同为真，不同为假； 2.主析取范式：极小项 (m) 之和；主合取范式：极大项(M)之积； 3.求极小项时，命题变元的肯定为1，否定为 0，求极大项时相反； 4.求极大极小项时，每个变元或变元的否定只能出现一次，求极小项 时变元不够合取真，求极大项时变元不够析取假； 5.求范式时，为保证编码不错，命题变元最好按P,Q,R 的顺序依次写； 6.真值表中值为 1 的项为极小项，值为0 的项为极大项； 7.n 个变元共有2n个极小项或极大项，这2n为(0~ 2n -1)刚好为化简完 后的主析取加主合取； 8.永真式没有主合取范式，永假式没有主析取范式； 9.推证蕴含式的方法 (=>) ：真值表法；分析法 (假定前键为真推出后键 为真，假定前键为假推出后键也为假) 10.命题逻辑的推理演算方法：P 规则， T 规则 ①真值表法；②直接证法；③归谬法；④附加前提法； 第三章谓词逻辑 1.一元谓词：谓词只有一个个体，一元谓词描述命题的性质； 多元谓词：谓词有n 个个体，多元谓词描述个体之间的关系； 2.全称量词用蕴含→，存在量词用合取 ^; 3.既有存在又有全称量，先消存在量，再消全称量； 第四章集合 1.N ，表示自然数集， 1,2,3 ??，不包括 0； 2.基：集合 A 中不同元素的个数， |A|； 3.集：定集合 A，以集合 A 的所有子集元素成的集合，P(A) ； 4.若集合 A 有 n 个元素，集 P(A) 有2 n个元素， |P(A)|= 2| A| = 2 n； 5.集合的分划： (等价关系 ) ①每一个分划都是由集合 A 的几个子集构成的集合； ② 几个子集相交空，相并全(A)； 6.集合的分划与覆盖的比： 分划：每个元素均出且出一次在子集中； 覆盖：只要求每个元素都出，没有要求只出一次； 第五章关系 1.若集合 A 有 m 个元素，集合 B 有 n 个元素，笛卡 A×B 的基数mn， A 到 B 上可以定2mn种不同的关系； 2.若集合 A 有 n 个元素， |A ×A|= n2，A 上有2n2个不同的关系； 3.全关系的性：自反性，称性，性； 空关系的性：反自反性，反称性，性； 离散数学试题 一、单项选择题 在每小题列出的四个备选项中只有一个是符合题目要求的，请将其代码填写在题后的括号内。错选、多选或未选均无分。 1.设P：天下大雨,Q：他在室内运动,命题“如果天下大雨，他就．在室内运动”可符合化为 （B） A. P∧Q B. P→Q C. Q→P D. P∨Q 2.设G=(V , E)为任意一图（无向或有向的），顶点个数为n，边的条数为m， 则各顶点的度数之和等于（ D ）。 A.n B. m C. 2n D. 2m 3.下列命题为假．命题的是（A） A.如果2是偶数，那么一个公式的析取范式惟一 B.如果2是偶数，那么一个公式的析取范式不惟一 C.如果2是奇数，那么一个公式的析取范式惟一 D.如果2是奇数，那么一个公式的析取范式不惟一 4.谓词公式(?x(P(x)∨?yR(y))→Q(x) 中变元x是（D） A.自由变元 B.约束变元 C.既不是自由变元也不是约束变元 D.既是自由变元也是约束变元 5.若个体域为整数域，下列公式中值为真的是（A） A.?x?y(x+y=0) B.?y?x(x+y=0) C.?x?y(x+y=0) D.??x?y(x+y=0) 6.下列命题中不．正确的是（D） A.x∈{x}-{{x}} B.{x}?{x}-{{x}} C.A={x}∪x,则x∈A且x?A D.A-B=??A=B 7.设P={x|(x+1)2≤4}，Q={x|x2+16≥5x},则下列选项正确的是（C） A.P?Q B.P?Q C.Q?P D.Q=P 8.下列表达式中不．成立的是（A） A.A∪(B⊕C)=(A∪B) ⊕ (A∪C) B.A∩(B⊕C)=(A∩B) ⊕ (A∩C) C.(A⊕B)×C=(A×C) ⊕ (B×C) D.(A-B) ×C=(A×C)-(B×C) 9.半群、群及独异点的关系是（A） A.{群}?{独异点}?{半群} B.{独异点}?{半群}?{群} 《离散数学》题库答案 一、选择或填空 （数理逻辑部分） 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、知识点集中，概念和定理多。《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。《离散数学》的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法等），同一个题也可能有几种方法。但是《离散数学》证明题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法，再者要善于总结。 在学习《离散数学》的过程中，我明白了理解概念是至关重要的。只有概念明确，才有可能将离散数学学好。但是初学者往往不能够将概念与现实世界中的事物联系起来，这是学好离散数学的基础，因此也是初学者面临的一个困难。只有克服它，你才能有可能学好《离散数学》。 学完这门课后，我总结到了，如果你想学得更好——你可以在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能够适应，并为后续学习打下良好的基础。而且必须及时复习和总结。 《离散数学》是一门数学科，大家都知道学数学就是要大量做数学，因此《离散数学》也不会例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学的思维方法。这一点非常重要。 课程虽然是上完了，但是老师你的教学方法独特而新颖，思想开化而先进，是个容易沟通的老师。有你带着我们学习《离散数学》就是我们不想学好，我想也是很难吧！就我来说每次上课时在我快要与“周公”会面之际，你突然一个笑话和雷人的语录，我和“周公”迫不得已就分开了。当我再次看到周公时，耳边 15.设D的结点数大于1，D=离散数学必备知识点总结
离散数学题库
离散数学屈婉玲版第一章部分习题汇总
离散数学谓词逻辑课后总结
离散数学试题与答案
离散数学习题
离散数学试题及答案精选版
离散数学第二章一阶逻辑知识点总结
离散数学(本)复习题
离散数学部分概念和公式总结
离散数学练习题
离散数学题目大汇总
离散数学题库及答案
离散数学深刻复知识题(全)
(完整word版)离散数学必备知识点总结.docx
离散数学练习题及答案
山东大学离散数学题库及答案
离散数学总结
最新离散数学试题库
相关主题
文本预览