离散数学试题一（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分）若
八、（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-1H。
八、（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 o g o f＝I A，f o h o g＝I B，g o f o 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＝
一、（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－1o f和f o 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)=log2n ,则f（）
A ．仅是入射
B ．仅是满射
C ．是双射
D ．不是函数
8．下列关系矩阵所对应的关系具有反对称性的是（ ）
A ．????
??????001110101
B ．??????????101110001
C ．??????????001100100
D ．????
??????001010101 9．设R 1和R 2是集合A 上的相容关系，下列关于复合关系R 1R 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>}，则R2S=___________，(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 ∈I
C ．若a A B ∈I ，则a A ∈
D ．若B ?A ，则A B A =I
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．复合语句“他工作很努力；但是思想僵化”中的逻辑联结词为（ ）
离散数学必备知识点总 结 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．设
离散数学试题(A卷及答案） 一、证明题（10分） 1)(?P∧(?Q∧R))∨(Q∧R)∨(P∧R)?R 证明: 左端?(?P∧?Q∧R)∨((Q∨P)∧R)?((?P∧?Q)∧R))∨((Q∨P)∧R) ?(?(P∨Q)∧R)∨((Q∨P)∧R)?(?(P∨Q)∨(Q∨P))∧R ?(?(P∨Q)∨(P∨Q))∧R?T∧R(置换)?R 2)?x(A(x)→B(x))??xA(x)→?xB(x) 证明：?x(A(x)→B(x))??x(?A(x)∨B(x))??x?A(x)∨?xB(x)???xA(x)∨?xB(x)??xA(x)→?xB(x) 二、求命题公式(P∨(Q∧R))→(P∧Q∧R)的主析取范式和主合取范式（10分） 证明：(P∨(Q∧R))→(P∧Q∧R)??(P∨(Q∧R))∨(P∧Q∧R)) ?（?P∧(?Q∨?R)）∨(P∧Q∧R) ?(?P∧?Q)∨(?P∧?R))∨(P∧Q∧R) ?(?P∧?Q∧R)∨(?P∧?Q∧?R)∨(?P∧Q∧?R))∨(?P∧?Q∧?R))∨(P∧Q∧R) ?m0∨m1∨m2∨m7 ?M3∨M4∨M5∨M6 三、推理证明题（10分） 1）C∨D, (C∨D)→?E, ?E→(A ∧?B), (A∧?B)→(R∨S)?R∨S 证明：(1) (C∨D)→?E (2) ?E→(A∧?B) (3) (C∨D)→(A∧?B) (4) (A∧?B)→(R∨S) (5) (C∨D)→(R∨S) (6) C∨D
(7) R∨S 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明（1）?xP(x) (2)P(a) (3)?x(P(x)→Q(y)∧R(x)) (4)P(a)→Q(y)∧R(a) (5)Q(y)∧R(a) (6)Q(y) (7)R(a) (8)P(a) (9)P(a)∧R(a) (10)?x(P(x)∧R(x)) (11)Q(y)∧?x(P(x)∧R(x)) 四、设m是一个取定的正整数，证明：在任取m＋1个整数中，至少有两个整数，它们的差是m的整数倍 证明设 1 a，2a，…，1+m a为任取的m＋1个整数，用m去除它们所得余数 只能是0，1，…，m－1，由抽屉原理可知， 1 a，2a，…，1+m a这m＋1个整 数中至少存在两个数 s a和t a，它们被m除所得余数相同，因此s a和t a的差是m的整数倍。 五、已知A、B、C是三个集合，证明A-(B∪C)=(A-B)∩(A-C) （15分）证明∵x∈ A-（B∪C）? x∈ A∧x?（B∪C）? x∈ A∧（x?B∧x?C）?（x∈ A∧x?B）∧（x∈ A∧x?C）? x∈（A-B）∧x∈（A-C）? x∈（A-B）∩（A-C）∴A-（B∪C）=（A-B）∩（A-C） 六、已知R、S是N上的关系，其定义如下：R={
第二章谓词逻辑 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))在全总个体域却不是永真式。
离散数学实验报告（实验ABC） 专业班级 学生姓名 学生学号 指导老师 完成时间
目录 第一章实验概述..................................... 错误!未定义书签。 实验目的....................................... 错误!未定义书签。 实验内容....................................... 错误!未定义书签。 实验环境....................................... 错误!未定义书签。第二章实验原理和实现过程........................... 错误!未定义书签。 实验原理....................................... 错误!未定义书签。 建立图的邻接矩阵，判断图是否连通 ............ 错误!未定义书签。 计算任意两个结点间的距离 ................... 错误!未定义书签。 对不连通的图输出其各个连通支 ................ 错误!未定义书签。 实验过程（算法描述）........................... 错误!未定义书签。 程序整体思路 ............................... 错误!未定义书签。 具体算法流程 ................................ 错误!未定义书签。第三章实验数据及结果分析........................... 错误!未定义书签。 建立图的邻接矩阵并判断图是否连通的功能测试及结果分析错误!未定义书签。 输入无向图的边 .............................. 错误!未定义书签。 建立图的连接矩阵 ............................ 错误!未定义书签。 其他功能的功能测试和结果分析................... 错误!未定义书签。 计算节点间的距离 ............................ 错误!未定义书签。 判断图的连通性 .............................. 错误!未定义书签。 输出图的连通支 .............................. 错误!未定义书签。 退出系统 .................................... 错误!未定义书签。第四章实验收获和心得体会........................... 错误!未定义书签。
试卷二试题与参考答案 一、填空 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设集合A,B，其中A＝{1,2,3}, B= {1,2}, 则A - B＝{3} ; ρ(A) - ρ(B)＝{3},{1,3},{2,3},{1,2,3}} . 2. 设有限集合A, |A| = n, 则|ρ(A×A)| = 2 2n. 3.设集合A = {a, b}, B = {1, 2}, 则从A到B的所有映射是α1= {(a,1), (b,1)}, α2= {(a,2), (b,2)},α3= {(a,1), (b,2)}, α4= {(a,2), (b,1)}, 其中双射的是α3, α4 . 4. 已知命题公式G＝?(P→Q)∧R，则G的主析取范式是(P∧?Q∧R) 5.设G是完全二叉树，G有7个点，其中4个叶点，则G的总度数为12，分枝点数为3. 6设A、B为两个集合, A= {1,2,4}, B = {3,4}, 则从A?B＝{4} ; A?B＝{1,2,3,4}; A－B＝{1,2} . 7.设R是集合A上的等价关系，则R所具有的关系的三个特性是自反性, 对称性传递性. 8. 设命题公式G＝?(P→(Q∧R))，则使公式G为真的解释有(1, 0, 0), (1, 0, 1),(1, 1, 0) 9. 设集合A＝{1,2,3,4}, A上的关系R1 = {(1,4),(2,3),(3,2)}, R2 = {(2,1),(3,2),(4,3)}, 则 R1?R2 ={(1,3),(2,2),(3,1)} , R2?R1 = {(2,4),(3,3),(4,2)} _ R12 ={(2,2),(3,3). 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 = -1<=x<0 , B-A = {x | 1 < x < 2, x∈R} , A∩B ={x | 0≤x≤1, x∈R} , . 13.设集合A＝{2, 3, 4, 5, 6}，R是A上的整除关系，则R以集合形式(列举法)记为 {(2, 2),(2, 4),(2, 6),(3, 3),(3, 6),(4, 4),(5, 5),(6, 6)} . 14. 设一阶逻辑公式G = ?xP(x)→?xQ(x)，则G的前束范式是?x(?P(x)∨Q(x)) . 15.设G是具有8个顶点的树，则G中增加21 条边才能把G变成完全图。(完全图的边 数 2)1 (- n n ，树的边数为n-1) 16.设谓词的定义域为{a, b},将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是_ (R(a)∧R(b))→(S(a)∨S(b)) _. 17. 设集合A＝{1, 2, 3, 4}，A上的二元关系R＝{(1,1),(1,2),(2,3)}, S＝{(1,3),(2,3),(3,2)}。则
数理逻辑部分 第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)中
数理逻辑部分 选择、填空及判断 ?下列语句不就是命题的( 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 )。
离散数学部分概念和公式总结 命题：称能判断真假的陈述句为命题。 命题公式：若在复合命题中，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.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号。
离散数学练习题 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的解
离散数学期末试题及答 案 HEN system office room 【HEN16H-HENS2AHENS8Q8-HENH1688】
326《离散数学》期末考试题(B ) 一、填空题(每小题3分，共15分) 1.设,,},,{{b a b a A =?}，则-A ? = ( )，-A {?} = ( )， )(A P 中的元素个数=|)(|A P ( ). 2.设集合A 中有3个元素，则A 上的二元关系有( )个，其中有( )个是A 到A 的函数. 3.谓词公式))()(())()((y P y Q y x Q x P x ?∧?∧→?中量词x ?的辖域为( ), 量词y ?的辖域为( ). 4.设}24,12,8,6,4,3,2,1{24=D ，对于其上的整除关系“|”，元素( )不存在补元. 5.当n ( )时，n 阶完全无向图n K 是平面图，当当n 为( )时，n K 是欧拉图. 二．1. 若n B m A ==||,||，则=?||B A ( )，A 到B 的2元关系共有( )个，A 上的2元关系共有( )个. 2. 设A = {1, 2, 3}, f = {(1,1), (2,1), (3, 1)}, g = {(1, 1), (2, 3), (3, 2)}和h = {(1, 3), (2, 1), (3, 1)}，则( )是单射，( )是满射，( )是双射. 3. 下列5个命题公式中，是永真式的有( )(选择正确答案的番号). (1)q q p p →→∧)(； (2))(q p p ∨→； (3))(q p p ∧→； (4)q q p p →∨∧?)(； (5)q q p →→)(. 4. 设D 24是24的所有正因数组成的集合，“|”是其上的整除关系，则3的补元( )，4的补元( )，6的补元( ).
欢迎共阅 一、填空题 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.6设A 、7.设R 8.9.设集合 R 1?R 2 R 1210.11设A ∩13.14.设一阶逻辑公式G=?xP(x)??xQ(x)，则G 的前束范式是_______________________________. 16.设谓词的定义域为{a ,b },将表达式?xR(x)→?xS(x)中量词消除，写成与之对应的命题公式是__________________________________________________________________________. 17.设集合A ＝{1,2,3,4}，A 上的二元关系R ＝{(1,1),(1,2),(2,3)},S ＝{(1,3),(2,3),(3,2)}。则R ?S ＝_____________________________________________________, R 2＝______________________________________________________. 二、选择题
离散数学试题一（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分）若
1. 写出命题公式 ﹁（P →（P ∨ Q ））的真值表。 答案： 2.证明 答案： 3. 证明以下蕴涵关系成立： 答案： 4. 写出下列式子的主析取范式： 答案： )()(Q P Q P Q P ?∧?∨∧??Q)P (Q)(P P) (Q P)P (Q)(Q Q)P (P) Q)P ((Q)Q)P (P)Q (Q)P (Q P ?∧?∨∧?∧∨∧?∨?∧∨?∧??∧∨?∨?∧∨??∨?∧∨???Q Q P P ?∨∧?)()()(R P Q P ∨∧∧?
5. 构造下列推理的论证：p ∨q, p →?r, s →t, ?s →r, ?t ? q 答案： ①s →t 前提 ②t 前提 ③s ①②拒取式I12 ④s →r 前提 ⑤r ③④假言推理I11 ⑥p →r 前提 ⑦p ⑤⑥拒取式I12 ⑧p ∨q 前提 ⑨q ⑦⑧析取三段论I10 6. 用反证法证明：p →(?(r ∧s)→?q), p, ?s ? ?q ) ()(R P Q P ∨∧∧?) ()(R P Q P ∨∧?∨??))(())(R Q P P Q P ∧?∨?∨∧?∨??) ()()()(R Q R P P Q P P ∧?∨∧?∨∧?∨∧??) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) ()()(P R Q P R Q Q R P ?∧∧?∨∧∧?∨?∧∧?∨) ()()(Q R P R P Q R P Q ∧∧?∨?∧∧?∨∧∧??) (Q R P ?∧∧?∨
7. 请将下列命题符号化： 所有鱼都生活在水中。 答案： 令 F( x )：x 是鱼 W( x )：x 生活在水中 ))((W(x)F(x)x →? 8. 请将下列命题符号化： 存在着不是有理数的实数。 答案： 令 Q ( x )：x 是有理数 R ( x )：x 是实数 Q(x))x)(R(x)(?∧? 9. 请将下列命题符号化： 尽管有人聪明，但并非一切人都聪明。 答案： 令M(x)：x 是人 C(x)：x 是聪明的 则上述命题符号化为 10. 请将下列命题符号化： 对于所有的正实数x,y ，都有x+y ≥x 。 答案： 令P(x):x 是正实数 S(x,y): x+y ≥x 11. 请将下列命题符号化： 每个人都要参加一些课外活动。 答案： 令P(x):x 是人 Q(y): y 是课外活动 S(x,y):x 参加y )))()((())()((x C x M x x C x M x →??∧∧?)),()()((y x S y P x P y x →∧??))(),()((y Q y x S x P y x ∧→??
总结离散数学知识点 第二章命题逻辑 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、知识点集中，概念和定理多。《离散数学》是建立在大量概念之上的逻辑推理学科，概念的理解是我们学习这门学科的核心。不管哪本离散数学教材，都会在每一章节列出若干定义和定理，接着就是这些定义定理的直接应用。掌握、理解和运用这些概念和定理是学好这门课的关键。要特别注意概念之间的联系，而描述这些联系的则是定理和性质。 2、方法性强：离散数学的特点是抽象思维能力的要求较高。通过对它的学习，能大大提高我们本身的逻辑推理能力、抽象思维能力和形式化思维能力，从而今后在学习任何一门计算机科学的专业主干课程时，都不会遇上任何思维理解上的困难。《离散数学》的证明题多，不同的题型会需要不同的证明方法（如直接证明法、反证法、归纳法等），同一个题也可能有几种方法。但是《离散数学》证明题的方法性是很强的，如果知道一道题用什么方法讲明，则很容易可以证出来，否则就会事倍功半。因此在平时的学习中，要勤于思考，对于同一个问题，尽可能多探讨几种证明方法，从而学会熟练运用这些证明方法，再者要善于总结。 在学习《离散数学》的过程中，我明白了理解概念是至关重要的。只有概念明确，才有可能将离散数学学好。但是初学者往往不能够将概念与现实世界中的事物联系起来，这是学好离散数学的基础，因此也是初学者面临的一个困难。只有克服它，你才能有可能学好《离散数学》。 学完这门课后，我总结到了，如果你想学得更好——你可以在进行完一章的学习后，用专门的时间对该章包括的定义与定理实施强记。只有这样才可能本课程的抽象能够适应，并为后续学习打下良好的基础。而且必须及时复习和总结。 《离散数学》是一门数学科，大家都知道学数学就是要大量做数学，因此《离散数学》也不会例外。学习数学不仅限于学习数学知识，更重要的还在于学习数学的思维方法。这一点非常重要。 课程虽然是上完了，但是老师你的教学方法独特而新颖，思想开化而先进，是个容易沟通的老师。有你带着我们学习《离散数学》就是我们不想学好，我想也是很难吧！就我来说每次上课时在我快要与“周公”会面之际，你突然一个笑话和雷人的语录，我和“周公”迫不得已就分开了。当我再次看到周公时，耳边