离散数学--期末复习
离散数学知识要点总结
第1章 命题逻辑
1、会判断一个语句是否为命题（如P31-习题1.1题）
练习：判断下列语句是否为命题。
(1).3+8=13； (2).离散数学是计算机系的一门必修课； (3).太阳系以外的星球上有生物； (4).你打算考硕士研究生吗？ (5).9+5≤12 ； (6). 天上有三个月亮。 (7).x+5 > 6； (8).一定要努力学习！ (9).2是素数； (10).x+5 > 6； (11).我正在说谎； (12).x=13. (13).这朵花多好看呀！ (14).7能被2整除. (15).我用的计算机CPU 主频是1G 吗？ (16).蓝色和黄色可以调成绿色；
(17). 雪是黑色的. (18). 明天会下雨吗？； (19).我能进来吗？ (20).这个男孩真勇敢呀！ (21).蓝色和黄色可以调成绿色； (22).x ≤3； (23)地球饶着太阳转. (24)青年人多么朝气蓬发呀！ (25).5能被2整除. (26).嫦娥一号太棒了！
(27).台湾是中国的一部分； (29) 你下午有会吗？若无会，请
到我这儿来！
(30).请不要讲话！
(31) 5是奇数；
(32).032>+x
2、注意五个命题联结词的使用，会将命题进行符号化（如P32-1.3，1.4，1.5题的题型）或在判断体现逻辑联结词的逻辑有关系等。 练习：将以下命题符号化
(1)如果你不去逛街，那么我也不去逛街。
(2)小李边吃饭边看电视。
(3)林芳学过英语或日语。
(4)张辉与王丽都是三好生.
(5)小王住在101室或102室。
(6).2+2≠4当且仅当王红没努力学习离散数学。
(7)4或6是素数.
(8).王晓聪明，但是他不用功.
(9)如果今天是1号，则明天是5号。
(10).小潘不能既跳舞又唱歌。 (11)如果你来了，他就唱歌而且陪你跳舞。 (12).或者雪是黑色的，或者太阳从东方升起。 (13).王晓既用功又聪明。 (14)2 + 2 ≠ 4 当且仅当美国位于非洲。 (15)小李学过英语或法语。 (16）如果石头会说话，那么月亮上就会出现海洋。 (17）.如果天气寒冷，小梅就不去游泳 。 （18）小红喜欢看书和画画。
s q r p ∨?∧?
3、会求命题公式的真值表，当一个命题公式中的命题变项被指定具体某组真值时，能求整个公式的真值。 练习：请回答下列问题。
（1）设p ，q 的真值为0，r ，s 的真值为1，则公式s r q p →∨∨))((的真值是？
（2）设p ，q 的真值为1，r ，s 的真值为0，则公式的真值是？ （3）设p ，q 的真值为0，r ，s 的真值为1,则公式)()(s r p q ∨→?∧?的真值是？ （4）设p ，q 的真值为0，r ，s 的真值为1,则公式)
(s r q p p ∧∨∨→的真值是？
（5）设p ，q 的真值为0，r ，s 的真值为1,则公式s r p q p ∨∧→→)(的真值是？
在画真值表时注意的知识点：一个命题公式中含有n 个原子命题，则
对其所有可能赋值有 2n 种。 4、会判断一个命题公式的类型（包括：重言式（永真式），矛盾式（永假式），可满足式）,(如P33-1.7，1.9题，方法可以用真值表，也可以用等值演算，但是如果指定方法，必须按指定方法做。)
练习：判断下列公式的类型
（1）)(q p p ∨→； （2）))((p q p →∧?；（3）q q p ∧→?)(； (4))()(q p q p ∨?→? （5）．)(r q p p ∨∨→； （6）．)(q p ??；（7）．)(q p p ∧→ (8))()(q p q p →??（9）．q q p →?∧)(；（10）．)(q p p ∨→；（11）．)(q p p ∨→?；(12))()(p q q p ?∨?→（13）)
()(q p q p ∨→∧（14）．q p p ??∧)(；
（15）．)(r q p ∨→；（16
5、掌握基本等值式，并会运用基本等值式，会证明等值式，会判断公式的类型：方法一，真值表法，方法二，等值演算法。（如P34-1.8，1.9题题型）
练习：证明下列等值式。
（1）r p q r q p ∨∧??→→)()( （2）)()()(r p q p r q p →∧→?∧→
（3）)()()(r p q p r q p →∨→?∨→ （4）p r r q p q p ?∨?→?∧∨∧))()((
6、关于主析取范式与主合取范式的求法及应用。（例1.14,习题1.12题型。）
要求：会判断什么是极小项与极大项，并会求主析取范式与主合取范式，可以通知所求式子判断成真赋值与成假赋值，及判断命题公式类型。
（1）、)())((r q p r q p ∧∧→∧∨ （2）、(p ∨(q ∧r ))→(p ∨q ∨r ) （3）、)()(r p q p ∧→→
（4）、)()(r q p q →∧?∨
（5）、)()(p q q p ∨?→→?
（6）、﹁(p ∧q ) ?﹁(﹁p →r )
（7）、(﹁q ∨﹁p )→r （8）、 )()(q p p q ∨?∧→ 7、命题逻辑推理
掌握基本理论，基本推理定律规则。见课本与课堂的练习题
（1）如果教练教得好而且我努力练习，那么我就一定能学好轮滑。我努力练习了，但我还是没有学好轮滑。所以是教练教得不好。
（2）如果今天我没有课，则我去机房上机或去图书馆查资料。若机房没有空机器，则我没法去上机。今天我没课，机房也没有空机器。所以我去图书馆查资料。
（3）或者C++程序设计难学，或者学生喜欢C++程序设计。如果编程语言容易学，那么C++程序设计并不难学。因此，如果学生不喜欢C++程序设计，那么编程语言并不容易学。
（4）今天或者天晴或者下雨。如果天晴，我去看电影。若我去看电影，我就不看书。我今天在看书。所以今天下雨。
（5）若星期天不下雪且能买到票，我就去体育馆看球。我买到票了，但是我没有去体育馆看球。所以星期天下雪了。
（6）若小张喜欢数学，则小李或小赵也喜欢数学。若小李喜欢数学，则他也喜欢物理。小张确实喜欢数学，可小李不喜欢物理。所以小赵喜欢数学。
(7)如果今天是星期五，那么我会有离散数学或数字逻辑考试。如果离散数学老师有事，那么没有离散数学考试。今天是星期五且离散数学老师有事。所以我有一次数字逻辑考试。
（8）若明天是星期一或星期三，我就有课. 若有课，今天必备课. 我今天下午没备课. 所以，明天不是星期一和星期三.
8、一些综合知识的认知。
练习：判断下列语句是否正确。
（1）、矛盾式一定不是可满足式，可满足式也一定不是
矛盾式。
（2）、q p ?的逻辑关系是：p 是q 的充分必要条件。
（3）、若A 至少存在一种赋值是成假赋值，则称A 为矛
盾式。
（4）、若A 至少存在一种赋值是成真赋值，则称A 为重
言式。
（5）、一般地说，排斥或不能用q p ∨的方式表示. （6）、q p →的逻辑关系是：p 是q 的必要条件。 （7）在命题逻辑中，任何命题公式的主合取范式都是存在的，并且是唯一的. （8）、矛盾式一定不是可满足式，但可满足式可能是矛盾式。 （9）、含有联结词“和”的命题一定是复合命题。 （10）五个基本联结词的运算顺序是：?，∨，∧，?，→。
第2章 一阶逻辑
1、一阶逻辑中的命题符号化问题（要求：注意区分全称量词与存在量词的提取，注意命题的个体域（若题目没有特别指明时，均指全总个体域），如何引入特性谓词。例2.2—2.5，P52—习题2.1，2.3）在引入特性量词后，使用全称量词与存在量词符号化的形式是不同的，则有全称量词时，“所有的……是……”应表示为：?x(A(x)→B(x))，存在量词时，“存在……是……”应表示为：?x(A(x)∧B(x))。
练习： （1）没有不爱看电影的人。 （2）并非所有的人都喜欢吃辣椒。 （3）素数不全是奇数。 （4）没有一个人不爱美。 （5）没有不吃饭的人。 （6）没有不呼吸的人。 （7）在北京工作的人未必都是北京
人。
(8)每个兔子都比某些乌龟跑得快。
(9)任何人都喜欢某些花。
2、解释：要求在给定解释下求公式的真值。（如P44-例2.7，2.8）
练习：论域D={1，2，3}，特定元素a =1
，指定谓词P 为如下表，则公式的),(x a xP ?的真值为？
3、求公式的前束范式。（注意：代替规则与换名规则的使用，等值式、基本等值式、量词否定等值式、量词辖域收缩与扩张等值式（只有遇到→B 时量词才互换）、量词分配等值式，P48-例题2.11，P54-习题2.14，2.15） 练习：（1）?x (F (x ,y ) →?y (G (x ,y )∧H (x ,z ))) （2）),(),(y x yG y x xF ?→?
（3）),()(y x yG x xF ?→? （4）))(),((()(y H y x G y x xF ?∧?→?
3、一些基本概念：变量的约束出现、变量的自由出现、闭式、解释，逻辑有效式，矛盾式，可满足式，代换实例。
第3章 集合的基本概念和运算
1、集合的相关概念：空集、子集、幂集、基数
设A 为一有限集合，|A |=n ，那么A 的子集个数为n 2 。
练习：（1）设A ={1,2,3}，B=P(A)，则|P(B)|=（ ）
（2）设}}2,1{},1{,{Φ=S ，则 P (P (S )) 有（ ）个元素
（3）设A ={Φ} ，B =Р(Р(A ))，则P (B )有( )个元素。
2、注意集合中元素与集合的关系及集合与集合的关系的表示。例如：
（1）下列关系式正确的是（ ）。
（2）下列关系式正确的有（ ）
A ）φ?φ且φ?{φ}， B)φ?φ且φ∈{φ}， C)φ∈φ且φ∈{φ} D ）φ∈φ且φ?{φ}
3、有关集合的计数问题，特别是对两个基本事件与三个基本事件的情形（P73-3.5，3.6，课堂练习） ||||||||B A B A B A ?-+=?
-?-++=??||||||||||B A C B A C B A ||||||C B A A C C B ??+?-?
练习：
（1）设集合A 的基数｜A ｜=4，集合B 的基数|B|=5，且集合A 与集合B 有3个相同的元素，则=?)(B A P （ ）
（2）某幼儿园大班一共有28个小朋友，其中有15人学钢琴，12人学围棋，有5人兼学钢琴和围棋，那么有多少人没有学钢琴也没有学围棋？
（3）如练习3.6中从1到300的整数中，有多少个不能被3也不能被5整除的数。
4、本章节中特别一些基本概念的准确性认知。
练习：判断下列语句是否正确。
（1）如果集合A 有6个元素，则A 的子集最多有5个元素。
（2）任何集合都至少含有一个元素。
（3）任何一个集合都不可以是另一个集合的元素。
第4章 二元关系与函数
1、笛卡尔积的定义与计算及相关性质：
（1）语句“A ，B ，C 为任意集合，若D B C A ?=?，则D C B A ==且。”是否正确？
（2）设A 、B 、C 为任意的三个集合，则笛卡尔积：A ×(B ×C)=A ×(B ×C)。是否正确？
2、二元关系的定义与表示：
练习：（1）}3,2,1{=A ，},,,{d c b a B =，则A 至B 的笛卡尔积=?B A ？从A 到B 有多少个不同的二元关系，A 上的有多少个不同的二元关系?
3、表示二元关系的方法：描述、关系矩阵、关系图。（注意几种方法表示关系是一一对应，给出其中一个都要能表示出其他，例如给出关系矩阵，要能写出表达式中的具体元素，能画出关系图。）
练习：设A={2，3，4，5，6}上的二元关系，}|,{是质数x y x y x R ∨<><=，则R 的表达式为？关系矩阵为?关系图为？
4、关系的运算：关系的定义域、值域、域，逆、合成、F 在A 上的限制、A 在F 下的像，会求关系的幂。（课
本练习题与留过的作业，P107——例4.28重点）
练习：P107—例 4.28一共有十六种不同的情形：设R 和S 是P 上的关系，P 是所有人的集合，},|,{的父亲是y x P y x y x R ∧∈><=，},|,{的母亲是y x P y x y x S ∧∈><=，则
（1）R R ο表示},|,{的祖父是y x P y x y x ∧∈><
（2）S R ο表示},|,{的祖母是y x P y x y x ∧∈><
（3）1-R R ο表示},|,{兄弟，妹或姐弟妹与y x P y x y x ∧∈>< 。
（4）1-S R ο表示关系Φ。
（5）R R ο1-表示Φ.
（6）S R ο1-表示},|,{的妻子是y x P y x y x ∧∈><。
（7）R S ο1-表示},|,{的丈夫是y x P y x y x ∧∈><.
（8）11--R R ο表示},|,{的孙子或孙女是y x P y x y x ∧∈><. （9）11--S R ο表示},|,{的外孙子或外孙女是y x P y x y x ∧∈><.
(10) S S ο1-表示Φ.
（11）R S ο表示},|,{的外祖父是y x P y x y x ∧∈><.
(12)S S ο 表示},|,{的外祖母是y x P y x y x ∧∈><.
(13)1-R S ο表示},|,{的丈夫是y x P y x y x ∧∈><
(14)1-S S ο 表示},|,{兄弟，妹或姐弟妹与y x P y x y x ∧∈><。
(15) 11--R S ο表示},|,{的孙子或孙女是y x P y x y x ∧∈><
(16) 11--S S ο均表示},|,{的外孙子或外孙女是y x P y x y x ∧∈>< 。
5、关系的性质的讨论（自反性、对称性、反对称性、传递性）（注意从关系图观察更方便）（P114页—4.4）
（1）自反关系的关系图中每一个结点都有环。
（2）对称关系的关系图中，如果两个结点间有有向边，则必成对出现。
（3）反对称关系的关系图中，如果两个结点间有有向边，则必不是成对出现的。
（4）传递关系的关系图中，如果有从结点a 到结点b 的有向边，同时又有从结点b 到结点c 的有向边，则必定有从结点a 到结点c 的有向边。
练习：（1）判断下列关系的所具有的性质。
（2）设集合A ={a ，b ，c }，A 上的关系R ={< a ，a >，< a ，b >，< b ，b >，< c ，c >，< c ，b >}，则R 具备
什么性质？不具备什么性质？
特别注意:(1) 一个关系可以既不是对称的，也不是反对称的。
(2) 一个关系可以既是对称的，也是反对称的。
一些特殊关系的性质如下：
（1）空关系是对称的、反对称的和传递的。
（2）全关系是自反的、对称的和传递的。
（3）恒等关系是自反的、对称的、反对称的和传递的。
6、会求关系的闭包（自反闭包，对称闭包，传递闭包）。
练习：（1）设},,{c b a A =，A 上的关系 },,,,,,,{><><><><=b c c b b a a a ρ，
a)求出ρ的关系矩阵。b)画出ρ的关系图。c)求出自反闭包)(ρr 对称闭包)(ρr 传递闭包)(ρr .
(2) 设集合{}c b a A ,,=上的二元关系R 的关系矩阵????
? ??=100011011R M ,
a)求出关系R 的表示式，b)画出R 的关系图，c) R 具有哪些性质？ d) 求出)(),(),(R t R s R r 的表达式。
7、关于等价关系：（要求会从定义上判断一个关系是否为等价关系，会求等价类，商集，理解等价关系的商集与集合的划分是一一对应的。）
定义：设R 是集合A 上的二元关系，如果关系R 同时具有自反性、对称性和传递性，则称R 是等价关系。 练习：
（1）前面6中的练习（2）加一问e) 它是一个等价关系吗？为什么？
(2):设}4,3,2,1{=A ，A 上的关}4,4,1,4,3,3,2,3,3,2,2,2,4,1,1,1{><><><><><><><><=R ，要求：（a ）请画出关系R 的关系矩阵与关系图；（b ）R 是否为等价关系，请说明理由；
（c ）若R 是等价关系，请求出关系R 的所有等价类与求商集A/R 。 (3) 设集合A={1，2，3，4，5，6}，A 上的关系R 满足：R={
∧x ≡y(mod)3}，)
（a ）请写出关系R 的元素，画出关系R 的关系矩阵与关系图； （b ）R 是否为等价关系，请说明理由； （c ）若R 是等价关系，请求出关系R 的所有等价类与求商集A/R 。
（4）试判断下列关系到是否为等价关系.
1）在一群人所组成的集合上定义的“同姓”关系； 2）在一群人所组成的集合上定义的“朋友”关系； 3）整数集上的“小于”关系； 4）整数集上的“等于”关系；
5）直线间的“平行”关系；
6）幂集上的“”关系。
8、关于偏序关系：（会定义，会画偏序关系的哈斯图，会根据哈斯图写出关系的表达式）。
定义：设R 是集合A 上的二元关系，如果关系R 同时具有自反性、反对称性和传递性，则称R 是偏序关系。 练习：设A={1，2，3，4}，其上偏序关系R 的 哈斯图如右图所示，则关系R 的表达式为？
第5章 图的基本概念 1、掌握图的基本概念：图，环，平行边，平凡图(只有一个顶点的零图，实际上是只有一
个
孤立点的图)，简单图，顶点的度
练习：求下列各图中指定点的度
（1）设图G = < V ，E >，如右图所示，则b 的入度)(deg b -= ， a 的度)deg(a = ，b 的出度)(deg b += ，d 的度)deg(d = 。
（2）设图G = < V ，E >，如右图所示，则v 1的入度)(deg 1v -= ，v 1的出度)(deg 1v += .
（3）设图G = < V ，E >，如右图所示，v 2的
)deg(2v = 。（4）v 3的度)deg(3v = 。
2、理解“握手定理”及其推理的定理内容，并能熟练应用定理。
握手定理：任意无向图和有向图的所有顶点度数之和都等于边数的2倍, 并且有向图的所有顶点入度之和等于出度之和等于边数.
握手定理推论 在任何无向图和有向图中，奇度顶点的个数必为偶数.所以不存在有5个度数为奇数的顶点。 练习：请回答下列各题。
（1）、设一个图有20个顶点，且所有顶点的度数都为3，则这个图中有多少条边？
（2）、已知图G 有10条边, 4个3度顶点, 其余顶点的度数均为2度,则这个图中有多少个顶点？
（3）、已知图G 有16条边, 每个顶点的度数均为2度,，则这个图中有多少个顶点？
（4）、已知图G 有12条边, 其中有3个4度点，其余的顶点的度数均为3度,，则这个图中有多少个顶点？
（5）、已知图G 有28条边, 其中有4个3度点，其余的顶点的度数均为4度,，则这个图中有多少个顶点？
（6）存在有5个度数为奇数的顶点吗？
3、会判断一组数组是否为图的度数列。
1 2 3
4
1
2
3 4
练习：给定下列序列，可以构成无向图的结点度数的序列有：（），
能构成无向简单图的结点度数序列的有：（）。
（1）、（1，1，2，2，3）；（2）、（1，1，2，2，2）；（3）、（5, 5, 4, 4, 2, 1）；（4）、（1，3，4，4，5）；
（5）、（1，3，2，2，3）；（6）、（1，3，2，2，2）；（7）、（3, 5, 4, 2, 2, 1）；（8）、（2，2，2，2，2）；
（9）、（1，1，2，5，2）；（10）、（1，1，3，3，3）；（11）（3，2，2，4，2）；（12）（1，4，2，2，3）；
（13）、（1，3，2，5，2）；（14）、（2，3，2，2，2）；（15）、（3，3，3，3，3）。
4、会求一个图的补图：设G=
所有使G成为完全图Kn的添加边组成的集合为边集的图，称为G的补图.
练习：求下列图的补图。
5、会判断图的连通性（有向图与无向图）
特别是对于有向图有：一个有向图，如果它是强连通图，那么它一定是单
向连通图，也一定是弱连通图。但是反之不然。
6、会求矩阵的邻接矩阵和关联矩阵，可达矩阵。（课本例题）
练习：求下列矩阵的邻接矩阵
（1）（2）（3）（4）（5）
练习：有向图G，如上图（1）所示，a) 求G的邻接矩阵A;b) G中v1到v3长度为3的路径有几条？分别是什么路径？c) G中v1到自身长度为3的回路有几条？d)求出G的可达矩阵P。
第6章一些特殊的图
会判断一图是否为欧拉图或说是否可以一笔画，或是否为哈密顿图。
例如：下面那一个图可一笔画出（欧拉图）（无向图是欧拉图的充要条件是图连通且无奇度的顶点。）一笔画出：连通的无向图G若度数为奇数的结点个数为0个或2个则可一笔画出。
第7章树
1、无向树的基本定义与性质：（P157-定理7.1）
无向树：连通且不含回路的无向图称为无向树，简称树。
重要性质：树是连通且无回路的无向图，则顶点个数n与边数m之间有m=n-1.
结合树的定义与性质和握手定理有一些重要的应用计算。（可以演变很多个题，注意知识点）
练习：(1)在一棵树中有7片树叶，3个3度顶点，其余都是4度顶点，则该树有多少个4度顶点？
（2）一棵树有2个4度顶点，3个3度顶点，其余顶点都是树叶，则该树有多少片树叶？
（3）一棵无向树T有8个顶点，4度、3度、2度的分枝点各1个，其余顶点均为树叶，则T中有多少片树叶？（4）在一棵树中有8片树叶，2个3度结点，其余都是4度结点，则该树有多少个4度结点？
（5）一颗树有两个2度结点，1个3度结点和3个4度结点，则1度结点数为多少？
(6)设G是有6个顶点的完全图，则从G中删去多少条边可以得到树？
2、最优生成树的求法（课堂练习与课本-7.8题）
离散数学图论与系中有图题目
离散数学图论与系中有图题目
————————————————————————————————作者：————————————————————————————————日期：
图论中有图题目 一、 没有一个简单的办法能确定图的色数以及用尽可能少的颜色给图的节点着色。Welch-Powell 给出了一个使颜色数尽可能少（不一定最少）的结点着色方法，在实际使用中比较有效： 第1步、 将图的结点按度数的非增顺序排列；第2步、用第1种颜色给第1个结点着色，并按照结点排列顺序，用同一种颜色给每个与前面已着色的结点不邻接的结点着色；第3步、换一种颜色对尚未着色的结点按上述方法着色，如此下去，直到所有结点全部着色为止。 例1 分别求右面两图的色数 （1）由于（1）中图G 中无奇数长的基本回路，由定理可知()2G χ=。 （2）由于（2）中图G 含子图轮图4W ，由于()44W χ=，故()4G χ≥。又因 为此图的最大度()4G ?=，G 不是完全图，也不是奇数长的基本回路，由定理可知()()4G G χ≤?=，因而()4G χ=。 （对n 阶轮图n W ，n 为奇数时有()3n W χ=，n 为偶数时有()4n W χ=；对n 阶零图n N ，有()1n N χ=；完全图n K ，有()n K n χ=；对于二部图12,,,G V V E E =<>=Φ时即()1n N χ=，E ≠Φ时即()2G χ=；在彼得森图G 中，存在奇数长的基本回路，因而()3G χ≥，又彼得森图既不是完全图也不是长度为奇数的基本回路，且()3G ?=，由定理()3G χ≤，故()3G χ=） 例 2 给右边三个图的顶点正常着 色，每个图至少需要几种颜色。 答案：（1） ()2G χ=；（2） ()3G χ=； （3）()4G χ= 例3 有8种化学品A,B,C,D,P,R,S,T 要放进贮藏室保管。出于安全原因， 下列各组药品不能贮在同一个室内：A-R, A-C, A-T, R-P, P-S, S-T, T-B, B-D, D-C, R-S, R-B, 4个结点、6个结点和8个结点的三次正则图 (2) (1) (3) (2)(1)
离散数学模拟题一套及答案
离散数学考试（试题及答案） 一、（10分）某项工作需要派A、B、C和D4个人中的2个人去完成，按下面3个条件，有几种派法？如何派？ (1)若A去，则C和D中要去1个人； (2)B和C不能都去； (3)若C去，则D留下。 解设A：A去工作；B：B去工作；C：C去工作；D：D去工作。则根据题意应有：ACD，(B∧C)，CD必须同时成立。因此 (ACD)∧(B∧C)∧(CD) (A∨(C∧ D)∨(C∧D))∧(B∨C)∧(C∨D) (A∨(C∧ D)∨(C∧D))∧((B∧C)∨(B∧D)∨C∨(C∧D)) (A∧B∧C)∨(A∧B∧D)∨(A∧C)∨(A∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧ D∧C∧D) ∨(C∧D∧B∧C)∨(C∧D∧B∧D)∨(C∧D∧C)∨(C∧D F∨F∨(A∧C)∨F∨F∨(C∧ D∧B)∨F∨F∨(C∧D∧B)∨F∨(C∧D)∨F (A∧C)∨(B∧C∧ D)∨(C∧D∧B)∨(C∧D) (A∧C)∨(B∧C∧ D)∨(C∧D) T 故有三种派法：B∧D，A∧C，A∧D。 二、（15分）在谓词逻辑中构造下面推理的证明：某学术会议的每个成员都是专家并且是工人，有些成员是青年人，所以，有些成员是青年专家。 解：论域：所有人的集合。()：是专家；()：是工人；()：是青年人；则推理化形式为： (()∧())，()(()∧())
下面给出证明： (1)() P (2)(c) T(1)，ES (3)(()∧()) P (4)( c)∧( c) T(3)，US (5)( c) T(4)，I (6)( c)∧(c) T(2)(5)，I (7)(()∧()) T(6) ，EG 三、（10分）设A、B和C是三个集合，则AB(BA)。 证明：ABx(x∈A→x∈B)∧x(x∈B∧xA)x(xA∨x∈B)∧x(x∈B∧xA) x(x∈A∧xB)∧x(xB∨x∈A)x(x∈A∧xB)∨x(x∈A∨xB) (x(x∈A∧xB)∧x(x∈A∨xB))(x(x∈A∧xB)∧x(x∈B→x∈A)) (BA)。 四、（15分）设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)。 解 r(R)＝R∪I A＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)＝R∪R－1＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>， <5，2>，<1，2>，<4，2>，<4，3>} R2＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>} R3＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<5，4>} R4＝{<2，2>，<2，4>，<3，4>，<4，4>，<5，1>，<5，5>，<5，4>}＝R2 t(R)＝R i＝{<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>，<5，5>}。
离散数学期末试题及答案完整版
离散数学期末试题及答 案 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的补元( ).
离散数学测验题--图论部分(优选.)
离散数学图论单元测验题 一、单项选择题(本大题共10小题，每小题2分，共20分) 1、在图G ＝
离散数学模拟试题讲解
1 离散数学模拟试题Ⅰ 一、单项选择题(本大题共15小题,每题1分,共15分)在每小题列出的四个备选项中只有一个就是符合题目要求的,请将其代码填写在题后的括号内。错选、多选或未选均无分 1.设 }16{2<=x x x A 是整数且,下面哪个命题为假( A )。 A 、A ?}4,2,1,0{; B 、A ?---}1,2,3{; C 、A ?Φ; D 、A x x x ?<}4{是整数且。 2.设}}{,{,ΦΦ=Φ=B A ,则B －A 就是( C )。 A 、}}{{Φ; B 、}{Φ; C 、}}{,{ΦΦ; D 、Φ。 3.右图描述的偏序集中,子集},,{f e b 的上界为 ( B )。 A 、b,c; B 、a,b; C 、b; D 、a,b,c 。 4.设f 与g 都就是X 上的双射函数,则1)(-g f ο为( C )。 A 、11--g f ο; B 、1)(-f g ο; C 、11--f g ο; D 、1-f g ο。 5.下面集合( B )关于减法运算就是封闭的。 A 、N ; B 、}2{I x x ∈; C 、}12{I x x ∈+; D 、}{是质数x x 。 6.具有如下定义的代数系统>*<,G ,( D )不构成群。 A 、G={1,10},*就是模11乘 ; B 、G={1,3,4,5,9},*就是模11乘 ; C 、G=Q(有理数集),*就是普通加法; D 、G=Q(有理数集),*就是普通乘法。 7.设 },32{I n m G n m ∈?=,*为普通乘法。则代数系统>*<,G 的幺元为( B )。 f
2 A 、不存在 ; B 、0032?=e ; C 、32?=e ; D 、1132--?=e 。 8.下面集合( C )关于整除关系构成格。 A 、{2,3,6,12,24,36} ; B 、{1,2,3,4,6,8,12} ; C 、{1,2,3,5,6,15,30} ; D 、{3,6,9,12}。 9.设},,,,,{f e d c b a V =, },,,,,,,,,,,{><><><><><><=e f e d d a a c c b b a E ,则有向图 >= 《离散数学》期末考试题(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 是欧拉图. 二、单选题(每小题3分，共15分) 1.设R 是集合A 上的偏序关系，1-R 是R 的逆关系，则1 -?R R 是A 上的 (A)偏序关系 (B)等价关系 (C)相容关系 (D)以上结论都不成立 2.由2个命题变元p 和q 组成的不等值的命题公式的个数有 (A)2 (B)4 (C)8 (D)16 3.设p 是素数且n 是正整数，则任意有限域的元素个数为 (A)n p + (B)pn (C)n p (D)p n 4.设R 是实数集合，≤是其上的小于等于关系，则(R, ≤)是 (A)有界格 (B)分配格 (C)有补格 (D)布尔格 5.3阶完全无向图3K 的不同构的生成子图有 (A)2 (B)3 (C)4 (D)5 三、判断题(每小题3分，共15分): 正确打“√”，错误打“×”. 1.若一个元素a 既存在左逆元l a ，又存在右逆元r a ，则r l a a =. ( ) 2.命题联结词→不满足结合律. ( ) 3.在Z 8 = {0，1，2，3，4，5，6，7}中，2关于“?8”的逆元为 4. ( ) 4.整环不一定是域. ( ) 《离散数学》模拟题（补） 一．单项选择题 1．下面四组数能构成无向图的度数列的有( )。 A、 2,3,4,5,6,7； B、 1,2,2,3,4； C、 2,1,1,1,2； D、 3,3,5,6,0。 2．图的邻接矩阵为( )。 A、； B、； C、； D、。 3.设S1={1，2，…，8，9}，S2={2，4，6，8}，S3={1，3，5，7，9}，S4={3，4，5}，S5={3，5}，在条件下X与（）集合相等。 A、X=S2或S5 ； B、X=S4或S5； C、X=S1，S2或S4； D、X与S1，…，S5中任何集合都不等。 4．下列图中是欧拉图的有( )。 5.下述命题公式中，是重言式的为（）。 A、； B、； C、； D、。 6.的主析取范式中含极小项的个数为（）。 A 、2； B、 3； C、5； D、0 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 ?? ? ? ? ? ? ? ? 1 1 1 1 1 1 1 3 1 S X S X? ?且 ) ( ) (q p q p∨ → ∧)) ( )) (( ) (p q q p q p→ ∧ → ? ? q q p∧ → ?) (q p p? ? ∧) ( r q p wff→ ∧ ?) ( 7.给定推理 ① P ② US ① ③ P ④ ES ③ ⑤ T ②④I ⑥ UG ⑤ 推理过程中错在（ ）。 A 、①->②; B 、②->③; C 、③->④; D 、④->⑤ 8.设S 1={1，2，…，8，9}，S 2={2，4，6，8}，S 3={1，3，5，7，9}，S 4={3，4，5}， S 5={3，5}，在条件 下X 与（ ）集合相等。 A 、X=S 2或S 5 ； B 、X=S 4或S 5； C 、X=S 1，S 2或S 4； D 、X 与S 1，…，S 5中任何集合都不等。 9.设R 和S 是P 上的关系，P 是所有人的集合， ， 则表示关系 （ ） 。 A 、； B 、 ； C 、 ； D 、 。 10.下面函数（ ）是单射而非满射。 A 、 ； B 、 ； C 、 ； D 、。 ))()((x G x F x →?)()(y G y F →)(x xF ?)(y F )(y G )(x xG ?)())()((x xG x G x F x ??→?∴3 1S X S X ??且},|,{的父亲是y x P y x y x R ∧∈><=},|,{的母亲是y x P y x y x S ∧∈><=R S 1-},|,{的丈夫是y x P y x y x ∧∈><},|,{的孙子或孙女是y x P y x y x ∧∈><Φ},|,{的祖父或祖母是y x P y x y x ∧∈><12)(,:2-+-=→x x x f R R f x x f R Z f ln )(,:=→+的最大整数表示不大于x x x x f Z R f ][],[)(, :=→12)(,:+=→x x f R R f 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 离散数学试题(Ｂ卷答案１） 一、证明题(10分） 1）(P∧（Ｑ∧Ｒ）)∨(Q∧R）∨（Ｐ∧R)R 证明: 左端(P∧Q∧Ｒ）∨((Q∨P）∧R) ((P∧Q)∧R))∨((Q∨P)∧R) ((Ｐ∨Ｑ）∧R）∨((Ｑ∨P)∧Ｒ) (（P∨Q）∨（Ｑ∨P))∧Ｒ （(P∨Ｑ)∨(Ｐ∨Q))∧R T∧Ｒ(置换)Ｒ 2) x (A(x)B(ｘ）)xA(x)xＢ(ｘ) 证明：x(A(ｘ)B(x))x(Ａ(ｘ)∨B(x)） x A(ｘ)∨xB（ｘ) xA(x)∨xB(x） xＡ(x)xB(x) 二、求命题公式(P∨（Q∧R)）(P∧Q∧R)的主析取范式和主合取范式(10分）。 证明：(P∨（Q∧R))(P∧Q∧R)（P∨(Q∧R)）∨(P∧Q∧R)) (P∧(Q∨Ｒ))∨（P∧Q∧Ｒ） （Ｐ∧Q)∨（P∧R)）∨(P∧Q∧R) (P∧Q∧R)∨(P∧Q∧Ｒ)∨(P∧Q∧Ｒ))∨(P∧Ｑ∧R）)∨(Ｐ∧Q∧R） m0∨ｍ1∨m２∨ｍ７ Ｍ３∨M４∨Ｍ５∨M6 三、推理证明题（１0分) 1）Ｃ∨D，（C∨D)E, E(A∧B)，(A∧Ｂ)(R∨S)R∨Ｓ证明：(１） (C∨D) E ?P (2) E（A∧Ｂ) ??P （3) (Ｃ∨D）（A∧B) Ｔ（1）(2），I (4) （A∧B)(R∨S）??P (5) (Ｃ∨D)(Ｒ∨S) ? T(3)(4)，I (6） C∨Ｄ P (7) R∨S T(5)，I 2) x(P(ｘ)Ｑ(y)∧R(ｘ)），xＰ(ｘ)Q（y)∧x(Ｐ(x)∧R(x)) 证明(1)ｘP(x) Ｐ （2)Ｐ(ａ） T(1），ＥS (3)ｘ（P(x)Q（y)∧R(x）) Ｐ (４)P(a)Q（y)∧R(a） T(3)，ＵS (５)Q（ｙ)∧R(a） T(2)（4），I （6）Q(y) Ｔ(５)，I （7)R(ａ) T(5),I (8)P(a)∧Ｒ（ａ) T(2)(7),I （9)x(Ｐ(x）∧R(x)) Ｔ(8),ＥG (10)Q(ｙ)∧x(P(x)∧R(ｘ)) Ｔ(６）(9)，I 四、某班有２5名学生,其中14人会打篮球,１2人会打排球，6人会打篮球和排球,5人会打篮球和网球,还有2人会打这三种球。而6个会打网球的人都会打另外一种球,求不会打这三种球的人数(10分)。 解：A，B,C分别表示会打排球、网球和篮球的学生集合。则｜A|=1２，|Ｂ|＝6,｜Ｃ|=14，｜A∩C|=6，｜B∩C｜=5，|Ａ∩Ｂ∩C｜=２。 先求|A∩B|。 ∵6＝|（Ａ∪C)∩B|=|（A∩B）∪（Ｂ∩C)|=|（A∩B）|＋|（B∩C）｜-|A∩B∩C|=|(Ａ∩B)|+5-２，∴|(A∩B）|=３。 于是|A∪Ｂ∪C｜=12+6+14-6-5－３＋２=20。不会打这三种球的人数25-20=5。五、已知Ａ、B、Ｃ是三个集合,证明A-(B∪Ｃ)=(A-B)∩(Ａ-C）(10分)。 证明：∵x A-（B∪C） x A∧x（B∪C） xＡ∧(xＢ∧x C） （x A∧x B）∧(x A∧ｘC） x（A-B）∧x(Ａ-C） ｘ（Ａ-Ｂ）∩(A-C） ∴Ａ-（B∪Ｃ)=（Ａ－B）∩(A－Ｃ） 六、已知R、S是Ｎ上的关系,其定义如下：R={ 《离散数学》模拟试题 一、 填空题（每小题2分，共20分） 1. 已知集合A ={φ，1，2}，则A 得幂集合p （A ）=_____ _。 2. 设集合E ={a , b , c , d , e }, A = {a , b , c }, B = {a , d , e }, 则A ∪B =___ ___， A ∩ B =____ __，A －B =___ ___，～A ∩～B =____ ____。 3. 设A ，B 是两个集合，其中A = {1, 2, 3}, B = {1, 2}，则A －B =____ ___， ρ（A ）－ρ（B ）=_____ _ _。 4. 已知命题公式，则G 的析取范式为 。 5. 设P ：2＋2＝4，Q ：3是奇数；将命题“2＋2＝4，当且仅当3是奇数。”符号化 ，其真值为 。 二、单项选择题（选择一个正确答案的代号填入括号中，每小题4分，共16分。） 1. 设A 、B 是两个集合，A ＝{1,3,4}，B ＝{1,2}，则A －B 为（ ）. A. {1} B. {1, 3} C. {3,4} D. {1,2} 2. 下列式子中正确的有（ ）。 A. φ＝0 B. φ∈{φ} C. φ∈{a,b} D. φ∈φ 3. 设集合X ＝{x , y }，则ρ（X ）＝（ ）。 A. {{x },{y }} B. {φ,{x },{y }} C. {φ,{x },{y },{x , y }} D. {{x },{y },{x , y }} 4. 设集合 A ＝{1,2,3}，A 上的关系 R ＝ {(1,1),(2,2),(2,3),(3,3),(3,2)}， 则R 不具备（ ）. 三、计算题（共50分） R Q P G →∧?=)( 离散数学试题(B卷答案1） 一、证明题（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 P (2) ?E→(A∧?B) P (3) (C∨D)→(A∧?B) T(1)(2)，I (4) (A∧?B)→(R∨S) P (5) (C∨D)→(R∨S) T(3)(4)， I (6) C∨D P (7) R∨S T(5)，I 2) ?x(P(x)→Q(y)∧R(x))，?xP(x)?Q(y)∧?x(P(x)∧R(x)) 证明(1)?xP(x) P 北京语言大学网络教育学院 《离散数学》模拟试卷一 注意： 1.试卷保密，考生不得将试卷带出考场或撕页，否则成绩作废。请监考老师负责监督。 2.请各位考生注意考试纪律，考试作弊全部成绩以零分计算。 3.本试卷满分100分，答题时间为90分钟。 4.本试卷分为试题卷和答题卷，所有答案必须答在答题卷上，答在试题卷上不给分。 一、【单项选择题】(本大题共15小题，每小题3分，共45分)在每小题列出的四个选项中只有一个选项是符合题目要求的，请将正确选项前的字母填在答题卷相应题号处。 1、在由3个元素组成的集合上，可以有 ( ) 种不同的关系。 [A] 3 [B] 8 [C]9 [D]27 2、设{}{}1,2,3,5,8,1,2,5,7A B A B ==-=,则（ ）。 [A] 3,8 [B]{}3 [C]{}8 [D]{}3,8 3、若X 是Y 的子集，则一定有（ ）。 [A]X 不属于Y [B]X ∈Y [C]X 真包含于 Y [D]X∩Y=X 4、下列关系中是等价关系的是（ ）。 [A]不等关系 [B]空关系 [C]全关系 [D]偏序关系 5、对于一个从集合A 到集合B 的映射，下列表述中错误的是（ ）。 [A]对A 的每个元素都要有象 [B] 对A 的每个元素都只有一个象 [C]对B 的每个元素都有原象 [D] 对B 的元素可以有不止一个原象 6、设p:小李努力学习，q:小李取得好成绩，命题“除非小李努力学习，否则他不能取得好成绩”的符号化形式为（ ）。 [A]p→q [B]q→p [C]┐q→┐p [D]┐p→q 7、设A={a,b,c},则A 到A 的双射共有（ ）。 [A]3个 [B]6个 [C]8个 [D]9个 离散数学考试试题(A卷及答案） 一、证明题（10分） 1) (P∧Q∧A C)∧(A P∨Q∨C ) (A∧(P Q ))C。P<->Q=(p->Q)合取（Q->p） 证明: (P∧Q∧A C)∧(A P∨Q∨C) (P ∨Q ∨A∨C)∧(A∨P∨Q∨C) ((P ∨Q ∨A)∧(A∨P∨Q))∨C反用分配律 ((P∧Q∧A)∨(A ∧P ∧Q))∨C ( A∧((P∧Q)∨(P ∧Q)))∨C再反用分配律 GAGGAGAGGAFFFFAFAF ( A∧(P Q))∨C (A∧(P Q ))C 2) (P Q)P Q。 证明：(P Q)((P∧Q))(P ∨Q))P Q。 二、分别用真值表法和公式法求(P(Q∨R))∧(P∨(Q R))的主析取范式与主合取范式，并写出其相应的成真赋值和成假赋值（15分）。 主析取范式与析取范式的区别：主析取范式里每个括号里都必须有全部的变元。 主析取范式可由析取范式经等值演算法算得。 GAGGAGAGGAFFFFAFAF 证明： 公式法：因为(P(Q ∨R))∧(P∨(Q R)) (P∨Q∨R)∧(P∨(Q ∧R )∨(Q ∧R)) (P∨Q ∨R)∧(((P∨Q)∧(P ∨R ))∨(Q ∧R ))分配律 (P∨Q∨R)∧(P∨Q ∨Q)∧(P∨Q ∨R)∧(P∨R ∨Q)∧(P∨R ∨R) (P∨Q ∨R)∧(P∨Q ∨R )∧(P ∨Q∨R) M∧5M∧6M使（非P析取Q析取R）为0 4 GAGGAGAGGAFFFFAFAF 所赋真值，即100，二进制为4 GAGGAGAGGAFFFFAFAF 《离散数学》期末考试试题 一、 填空题（每空2分，合计20分） 1. 设个体域为{2,3,6}D =-, ():3F x x ≤，():0G x x >。则在此解释下公式 ()(()())x F x G x ?∧的真值为______。 2. 设:p 我是大学生，:q 我喜欢数学。命题“我是喜欢数学的大学生”为可符合化 为 。 3. 设{1,2,3,4}A =，{2,4,6}B =，则A B -=________，A B ⊕=________。 4. 合式公式()Q P P ?→∧是永______式。 5. 给定集合{1,2,3,4,5}A =，在集合A 上定义两种关系： {1,3,3,4,2,2}R =<><><>, {4,2,3,1,2,3}S =<><><>， 则_______________S R =ο，_______________R S =ο。 6. 设e 是群G 上的幺元，若a G ∈且2a e =,则1a -=____ , 2a -=__________。 7． 公式))(()(S Q P Q P ?∧?∨∧∨?的对偶公式为 。 8. 设{2,3,6,12}A =, p 是A 上的整除关系，则偏序集,A <>p 的最大元是________，极小元是_ _。 9. 一棵有6个叶结点的完全二叉树，有_____个内点；而若一棵树有2个结点度数为2，一 个结点度数为3，3个结点度数为4，其余是叶结点，则该树有_____个叶结点。 10. 设图,G V E =<>, 1234{v ,v ,v ,v }V =，若G 的邻接矩阵????????????=0001001111011010A ，则1()deg v -=________, 4()deg v +=____________。 二、选择题（每题2分，合计20分） 1．下列各式中哪个不成立（ ）。 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 ∧??∧?)())((。 图论练习题 一.选择题 1、设G是一个哈密尔顿图，则G一定是( )。 (1) 欧拉图(2) 树(3) 平面图(4)连通图 2、下面给出的集合中，哪一个是前缀码？() (1) {0，10，110，101111}(2) {01，001，000，1} (3) {b，c，aa，ab，aba}(4) {1，11，101，001，0011} 3、一个图的哈密尔顿路是一条通过图中()的路。 4、设G是一棵树，则G 的生成树有( )棵。 (1) 0(2) 1(3) 2(4) 不能确定 5、n阶无向完全图Kn 的边数是( )，每个结点的度数是( )。 6、一棵无向树的顶点数n与边数m关系是()。 7、一个图的欧拉回路是一条通过图中( )的回路。 8、有n个结点的树，其结点度数之和是()。 9、下面给出的集合中，哪一个不是前缀码( )。 (1) {a，ab，110，a1b11} (2) {01，001，000，1} (3) {1，2，00，01，0210} (4) {12，11，101，002，0011} 10、n个结点的有向完全图边数是( )，每个结点的度数是( )。 11、一个无向图有生成树的充分必要条件是( )。 12、设G是一棵树，n,m分别表示顶点数和边数，则 (1) n=m (2) m=n+1 (3) n=m+1 (4) 不能确定。 13、设T=〈V,E〉是一棵树，若|V|>1，则T中至少存在( )片树叶。 14、任何连通无向图G至少有( )棵生成树，当且仅当G 是( )，G的生成树只有一棵。 15、设G是有n个结点m条边的连通平面图，且有k个面，则k等于: (1) m-n+2 (2) n-m-2 (3) n+m-2 (4) m+n+2。 16、设T是一棵树，则T是一个连通且( )图。 17、设无向图G有16条边且每个顶点的度数都是2，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 16 18、设无向图G有18条边且每个顶点的度数都是3，则图G有( )个顶点。 (1) 10 (2) 4 (3) 8 (4) 12 《离散数学》试卷（A 卷） 一、 选择题（共5 小题，每题 3 分，共15 分） 1、设A={1,2,3},B={2,3,4,5},C={2,3},则C B A ⊕?)(为(C )。 A 、{1,2} B 、{2,3} C 、{1,4,5} D 、{1,2,3} 2、下列语句中哪个是真命题 ( A ) A 、如果1+2=3，则4+5=9； B 、1+2=3当且仅当4+5≠9。 C 、如果1+2=3，则4+5≠9； D 、1+2=3仅当4+5≠9。 3、个体域为整数集合时，下列公式（ C ）不是命题。 A 、)*(y y x y x =?? B 、)4*(=??y x y x C 、)*(x y x x =? D 、)2*(=??y x y x 4、全域关系A E 不具有下列哪个性质（ B ）。 A 、自反性 B 、反自反性 C 、对称性 D 、传递性 5、函数612)(,:+-=→x x f R R f 是（ D ）。 A 、单射函数 B 、满射函数 C 、既不单射也不满射 D 、双射函数 二、填充题（共 5 小题，每题 3 分，共15 分） 1、设|A|=4，|P(B)|=32，|P(A ?B)|=128，则|A ?B|=??2???. 2、公式)(Q P Q ?∨∧的主合取范式为 。 3、对于公式))()((x Q x P x ∨?，其中)(x P ：x=1， )(x Q ：x=2，当论域为{0,1,2}时，其真值为???1???。 4、设A ＝{1,2,3,4}，则A 上共有???15????个等价关系。 5、设A ＝{a ，b ，c }，B={1,2},则|B A |= 8 。 三、判断题（对的填T ，错的填F ，共 10 小题，每题 1 分，共计10 分） 1、“这个语句是真的”是真命题。 （ F ） 2、“张刚和小强是同桌。”是复合命题。 （ F ） 3、))(()(r q q p p ∧?∧→?∨是矛盾式。 （ T ） 4、)(T S R T R S R ??????。 （ F ） 5、恒等关系具有自反性，对称性，反对称性，传递性。 （ T ） 6、若f 、g 分别是单射,则g f ?是单射。 （ T ） 7、若g f ?是满射，则g 是满射。 （ F ） 8、若A B ?，则)()(A P B P ?。 （ T ） 9、若R 具有自反性，则1-R 也具有自反性。 （ T ） 10、B A ∈并且B A ?不可以同时成立。 （F ） 四、计算题（共 3 小题，每题 10 分，共30 分） 1、调查260个大学生，获得如下数据：64人选修数学课程，94人选修计算机课程，58人选修商贸课程，28人同时选修数学课程和商贸课程，26人同时选修数学课程和计算机课程，22人同时选修计算机课程和商贸课程，14人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 离散数学-期末考试卷-A卷 东莞理工学院城市学院（本科）试卷（A卷） 2013-2014学年第一学期 开课单位：计算机与信息科学系，考试形式：闭卷，允许带入场 科目：离散数学，班级：软工本2012-1、2、3 姓名：学号： 题序一二三四总分 得分 A评 卷人 一、单项选择题（每小题2分，共20分） 在每小题列出的四个备选项中只有一个是符合题目要求的，错选、多选或未选均无分。 1. 下述不是命题的是( ) A. 做人真难啊! B. 后天是阴天。 C. 2是偶数。 D. 地球是方的。 2. 命题公式P→(P∨Q∨R)是( ) A. 永假的 B. 永真的 C. 可满足的 D. 析取范式 3. 命题公式﹁B→﹁A等价于( ) A. ﹁A∨﹁ B B. ﹁(A∨B) C. ﹁A∧﹁ B D. A→B 4．设P：他聪明，Q：他用功，命题“他虽聪明但不用功”的符号化正确的是（）A．?P∧Q B．P∧?Q C．P→?Q D．P∨?Q 5．设A（x）:x是人，B（x）：x犯错误，命题“没有不犯错误的人”符号化为（）A．?x(A(x))∧B(x) B．??x( A(x)→?B(x) ) C．??x( A(x)∧B(X)) D．??x( A(x)∧?B(x) ) 6. 设有A={a,b,c}上的关系R={ 7. 设A={1,2,3,4,5,6},B={a,b,c,d,e}，以下哪一个关系是从A到B的满射函数( ) A. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>} B. f={<1,e>,<2,d>,<3,c>,<4,b>,<5,a>,<6,e>} C. f={<1,a>,<2,b>,<3,c>,<4,a>,<5,b>,<6,c>} D. f={<1,a>,<2,b>,<3,c>,<4,d>,<5,e>,<1,b>} 8．设简单图G所有结点的度数之和为10，则G一定有（） A．3条边B．4条边C．5条边 D．6条边 9．下列不．一定是树的是（） A．每对结点之间都有通路的图 B．有n个结点，n-1条边的连通图 C．无回路的连通图D．连通但删去一条边则不连通的图 10．下列各图中既是欧拉图，又是哈密顿图的是（） 《离散数学》课程试题(A)卷 课程代码： 080800111 本试卷适用理学系数学与应用数学专业和信息与计算科学专业 （时量：120分钟；总分为100分） 注 意： 1、所有答案和解答均应写在答题纸上，答在试卷上不记分 2、答案必须写明题目序号，并按题号顺序答题 3、请保持行距，保持卷面整洁 一、填空题：（每题3分，本大题共24分） 1．设}4,}3{,,2{a A =，}1,4,3,}{{a B =，请在下列每对集合中填入适当的符号：?∈, 。 （1）}{a B , (2) }}3{,4,{a A 。 2．设}1,0{=A ，N 为自然数集，???=是偶数。，是奇数， ，x x x f 10)( 若A A f →： ，则f 是 射的，若A N f →： ，则f 是 射的。 3．设图G = < V ，E >中有7个结点，各结点的次数分别为2，4，4，6，5，5，2， 则G 中有 条边，根据 。 4．两个重言式的析取是 ，一个重言式和一个矛盾式的合取是 。 5．在一阶逻辑中将命题：凡对顶角都相等，符号化为_____________________。 6.集合A 有n 个元素，则A 上共有_____________________个既是对称又是反对称的的关系。 7. 连通简单无向图有17条边。则该图至少有_____________________个结点。 8. 某班有学生50人，有26人在第一次考试中得优，有21人在第二次考试中得优，有17人两次考试都没得优，那么两次考试都得优的学生的人数是_____________________。 二、单项选择题：（每小题3分，本大题共30分） 1．设}16{2<=x x x A 是整数且，下面哪个命题为假（ ） 。 A 、A ?}4,2,1,0{ ； B 、A ?---}1,2,3{ ； C 、A ?Φ ； D 、A x x x ?<}4{是整数且。 2．设}}{,{,ΦΦ=Φ=B A ，则B －A 是（ ）。 A 、}}{{Φ ； B 、}{Φ ； C 、}}{,{ΦΦ ； D 、Φ。 华南理工大学网络教育学院 2016–2017学年度第一学期期末考试 《 离散数学 》试卷（模拟卷） （客观题电脑给分，主观题依过程给分） 教学中心： 专业层次： 学 号： 姓 名： 座号： 注意事项：1. 本试卷共 三 大题，满分100分，考试时间90分钟，闭卷； 2. 考前请将以上各项信息填写清楚； 3. 所有答案必须做在答题纸上,做在试卷、草稿纸上无效； 4．考试结束，试卷、答题纸、草稿纸一并交回。 一、单项选择题（本大题30分，每小题6分） 1．设，P ：他聪明；Q ：他用功。在命题逻辑中，命题： “他既聪明又用功。” 可符号化为：( ) A ．P ∧ Q B ．P → Q C ．P ∨ ?Q D ．P ∧?Q 【答案：A 】 2．下列式子( )是永真式 A ．Q →（P ∧ Q ） B ．P →（P ∧ Q ） C ．（P ∧ Q ）→ P D ．（P ∨Q ）→ Q 【答案：C 】 3．设S （x ）：x 是运动员，J （y ）：y 是教练员，L （x ，y ）：x 钦佩y 。命题“所有运动员都钦佩一些教练员”的符号化公式是( ) A ．?x （S （x ）∧ ? y （J （y ）∧ L （x ，y ））） B ．?x ?y （S （x ）→（J （y ）→ L （x ，y ））） C ．?x （S （x ）→ ?y （J （y ）∧ L （x ，y ））） D ．?y ?x （S （x ）→（J （y ）∧ L （x ，y ））） 【答案：C 】 4．下列命题是真的是( ) A ．如果A ? B 及B ∈C,则A ? C B ．如果A ?B 及B ∈C,则A ∈C C ．如果A ∈B 及B ?C,则A ?C D ．如果A ∈B 及B ?C,则A ∈C 【答案：D 】 5．设G 是n 有个结点，m 条边的简单有向图。若G 是连通的，则m 的下界是（ ） A ．n B ．1n - C ．()1n n - D ．()1 12 n n - 【答案：B 】 二、 判断题（本大题20分，每小题4分） 1. 设A ，B 是命题公式，则蕴涵等值式为A →B ??A ∧B 。 （ × ） 2、?x ?yA(x,y)? ?y ?xA(x,y) 。 （ × ）【浙江工商大学】《离散数学》期末考试题(B)
离散数学模拟题(开卷)
离散数学模拟试卷和答案
离散数学期末考试试题及答案
离散数学模拟试题及答案
离散数学期末考试试题及答案
离散数学模拟试卷和答案
离散数学考试试题(A、B卷及答案)
《离散数学》期末考试试题
离散数学图论练习题
离散数学期末试卷A卷及答案
离散数学-期末考试卷-A卷
离散数学模拟卷(简单)
离散数学试题2018模拟1+答案