《离散数学》期末复习提要
《离散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。
离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。
课程的主要内容
1、集合论部分（集合的基本概念和运算、关系及其性质）；
2、数理逻辑部分（命题逻辑、谓词逻辑）；
3、图论部分（图的基本概念、树及其性质）。
学习建议
离散数学是理论性较强的学科，学习离散数学的关键是对离散数学（集合论、数理逻辑和图论）有关基本概念的准确掌握，对基本原理及基本运算的运用，并要多做练习。
教学要求的层次
各章教学要求的层次为了解、理解和掌握。了解即能正确判别有关概念和方法；理解是能正确表达有关概念和方法的含义；掌握是在理解的基础上加以灵活应用。
一、各章复习要求与重点
第一章集合
[复习知识点]
1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集
2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、De Morgan 律等），文氏（Venn）图
3、序偶与迪卡尔积
本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明
[复习要求]
1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。
2、掌握集合的表示法和集合的交、并、差、补等基本运算。
3、掌握集合运算基本规律，证明集合等式的方法。
4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [本章重点习题]
P5~6，4、6； P14~15，3、6、7； P20，5、7。 [疑难解析]
1、集合的概念
因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。
2、集合恒等式的证明
通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在{ EMBED Equation.3 |B A B A ~?=-证明中的特殊作用。 [例题分析]
例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则 。 解
于是 例2 设，试求：
(1)； (2)； (3)； (4)； (5)； (6)。 解 (1) (2) (3) (4) (5) (6) 例3 试证明 证明
第二章二元关系
[复习知识点]
1、关系、关系矩阵与关系图
2、复合关系与逆关系
3、关系的性质（自反性、对称性、反对称性、传递性）
4、关系的闭包（自反闭包、对称闭包、传递闭包）
5、等价关系与等价类
6、偏序关系与哈斯图（Hasse）、极大/小元、最大/小元、上/下界、最小上界、最大下界
7、函数及其性质（单射、满射、双射）
8、复合函数与反函数
本章重点内容：二元关系的概念、关系的性质、关系的闭包、等价关系、半序关系、映射的概念
[复习要求]
1、理解关系的概念：二元关系、空关系、全关系、恒等关系；掌握关系的集合表示、关系矩阵和关系图、关系的运算。
2、掌握求复合关系与逆关系的方法。
3、理解关系的性质（自反性、对称性、反对称性、传递性），掌握其判别方法（定义、矩阵、图）。
4、掌握求关系的闭包（自反闭包、对称闭包、传递闭包）的方法。
5、理解等价关系和偏序关系的概念，掌握等价类的求法和偏序关系做哈斯图的方法，极大/小元、最大/小元、上/下界、最小上界、最大下界的求法。
6、理解函数概念：函数、函数相等、复合函数和反函数。
7、理解单射、满射、双射等概念，掌握其判别方法。
[本章重点习题]
P25，1；P32~33，4，8，10；P43，2，3，5；P51~52，5，6；P59，1，2；P64，3；P74~75，2，4，6，7；P81，5，7；P86，1，2。
[疑难解析]
1、关系的概念
关系的概念是第二章全章的基础，又是第一章集合概念的应用。因此，学生应该真正理解并熟练掌握二元关系的概念及关系矩阵、关系图表示。
2、关系的性质及其判定
关系的性质既是对关系概念的加深理解与掌握，又是关系的闭包、等价关系、半序关系的基础。对于四种性质的判定，可以依据教材中P49上总结的规律。这其中对传递性的判定，难度稍大一点，这里要提及两点：一是不破坏传递性定义，可认为具有传递性。如空关系具有传递性，同时空关系具有对称性与反对称性，但是不具有自反性。另一点是介绍一种判定传递性的“跟踪法”，即若，则。如若，则有，且。
３、关系的闭包
在理解掌握关系闭包概念的基础上，主要掌握闭包的求法。关键是熟记三个定理的结论：定理2，；定理3，；定理4，推论。
４、半序关系及半序集中特殊元素的确定
理解与掌握半序关系与半序集概念的关键是哈斯图。哈斯图画法掌握了，对于确定任一子集的最大（小）元，极大（小）元也就容易了。这里要注意，最大（小）元与极大（小）元只能在子集内确定，而上界与下界可在子集之外的全集中确定，最小上界为所有上界中最小者，最小上界再小也不小于子集中的任一元素，可以与某一元素相等，最大下界也同样。
５、映射的概念与映射种类的判定
映射的种类主要指单射、满射、双射与非单非满射。判定的方法除定义外，可借助于关系图，而实数集的子集上的映射也可以利用直角坐标系表示进行，尤其是对各种初等函数。
[例题分析]
例1 设集合，判定下列关系，哪些是自反的，对称的，反对称的和传递的：
解：均不是自反的；R4是对称的；R1 ,R2 ,R3 , R4 ,R5是反对称的；R1 ,R2 ,R3 , R4 ,R5是传递的。例2 设集合，A上的二元关系R为
（１）写出R的关系矩阵，画出R的关系图；
（２）证明R是A上的半序关系，画出其哈斯图；
（３）若，且，求B的最大元，最小元，极大元，极小元，最小上界和最大下界。
解（1）R的关系矩阵为
R的关系图略
（2）因为R是自反的，反对称的和传递的，所以R是A上的半序关系。(A,R)为半序集，
(A,R)的哈斯图如下
。4
。1
。3
。2
。5
(3) 当，B的极大元为2，4；极小元为2，5；B无最大元与最小元；B也无上界与下界，更无最小上界与最大下界。
第三章命题逻辑
[复习知识点]
１、命题与联结词（否定、析取、合取、蕴涵、等价），复合命题
２、命题公式与解释，真值表，公式分类（恒真、恒假、可满足），公式的等价
３、析取范式、合取范式，极小（大）项，主析取范式、主合取范式
４、公式类别的判别方法（真值表法、等值演算法、主析取/合取范式法）
５、公式的蕴涵与逻辑结果
６、形式演绎
本章重点内容：命题与联结词、公式与解释、析取范式与合取范式、公式恒真性的判定、形式演绎
[复习要求]
１、理解命题的概念；了解命题联结词的概念；理解用联结词产生复合命题的方法。
２、理解公式与解释的概念；掌握求给定公式真值表的方法，用基本等价式化简其他公式，公式在解释下的真值。
３、了解析取（合取）范式的概念；理解极大（小）项的概念和主析取（合取）范式的概念；掌握用基本等价式或真值表将公式化为主析取（合取）范式的方法。
４、掌握利用真值表、等值演算法和主析取/合取范式的唯一性判别公式类型和公式等价的方法。
５、理解公式蕴涵与逻辑结果的概念，掌握基本蕴涵式。
6、掌握形式演绎的证明方法。
[本章重点习题]
P93，1；P98，2，3；P104，2，3；P107，1，3；P112，5；P115，1，2，3。[疑难解析]
1、公式恒真性的判定
判定公式的恒真性，包括判定公式是恒真的或是恒假的。具体方法有两种，一是真值表法，对于任给一个公式，主要列出该公式的真值表，观察真值表的最后一列是否全为1（或全为0），就可以判定该公式是否恒真（或恒假），若不全为0，则为可满足的。二是推导法，即利用基本等价式推导出结果为1，或者利用恒真（恒假）判定定理：公式G是恒真的（恒假的）当且仅当等价于它的合取范式（析取范式）中，每个子句（短语）均至少包含一个原子及其否定。
这里要求的析取范式中所含有的每个短语不是极小项，一定要与求主析取范式相区别，对于合取范式也同样。
2、范式
求范式，包括求析取范式、合取范式、主析取范式和主合取范式。关键有两点：一是准确理解掌握定义；另一是巧妙使用基本等价式中的分配律、同一律和互补律，结果的前一步适当使用等幂律，使相同的短语（或子句）只保留一个。
另外，由已经得到的主析取（合取）范式，根据原理，参阅《离散数学学习指导书》P71例15，可以求得主合取（析取）范式。
3、形式演绎法
掌握形式演绎进行逻辑推理时，一是要理解并掌握14个基本蕴涵式，二是会使用三个规则：规则P、规则Q和规则D，需要进行一定的练习。
[例题分析]
例1 求的主析取范式与主合取范式。
解（1）求主析取范式，
方法1：利用真值表求解
因此
方法2：推导法
（2）求主合取范式
方法1：利用上面的真值表
为0的有两行，它们对应的极大项分别为
因此，
方法2：利用已求出的主析取范式求主合取范式
已用去6个极小项，尚有2个极小项，即
与于是
例2 试证明公式为恒真公式。
证法一：见〈离散数学学习指导书〉P60例6（4）的解答。（真值表法）证法二：
G=?（（?P∨Q）∧（?Q∨R））∨（?P∨R）
=（P∧?Q）∨（Q∧?R）∨?P∨R
=（（（P∨Q）∧（P∨?R）∧（?Q∨Q）∧（?Q∨?R））∨?P）∨R
=（（P∨Q∨?P）∧（P∨?R∨?P）∧（?Q∨?R∨?P））∨R
=（1∧（?Q∨?R∨?P））∨R
=?Q∨?R∨?P∨R
=1
故G为恒真公式。
例3 利用形式演绎法证明{ P→（Q→R），?S∨P，Q}蕴涵S→R。
证明：
（1）?S∨P 规则P
（2）S 规则D
（3）P 规则Q，根据（1），（2）
（4）P→（Q→R）规则P
（5）Q→R 规则Q，根据（3），（4）
（6）Q 规则P
（7）R 规则 Q，根据（5），（6）
（8）S→R 规则D，根据（2），（7）
第四章谓词逻辑
[复习知识点]
1、谓词、量词、个体词、个体域、变元（约束变元与自由变元）
2、谓词公式与解释，谓词公式的类型（恒真、恒假、可满足）
3、谓词公式的等价和蕴涵
4、前束范式
本章重点内容：谓词与量词、公式与解释、前束范式
[复习要求]
1、理解谓词、量词、个体词、个体域、变元的概念；理解用谓词、量词、逻辑联结词描述一个简单命题；了解命题符号化。
2、理解公式与解释的概念；掌握在有限个体域下消去公式量词，求公式在给定解释下真值的方法；了解谓词公式的类型。
3、理解用解释的方法证明等价式和蕴涵式。
4、掌握求公式前束范式的方法。
[本章重点习题]
P120，1，2；P125~126，1，3；P137，1。
[疑难解析]
1、谓词与量词
反复理解谓词与量词引入的意义，概念的含义及在谓词与量词作用下变量的自由性、约束性与改名规则。
2、公式与解释
能将一阶逻辑公式表达式中的量词消除，写成与之等价的公式，然后将解释I中的数值代入公式，求出真值。
3、前束范式
在充分理解掌握前束范式概念的基础上，利用改名规则、基本等价式与蕴涵式（一阶逻辑中），将给定公式中量词提到母式之前称为首标。
[典型例题]
例1 设I是如下一个解释：
F(2) F(3) P(2) P(3) Q(2,2) Q(2,3) Q(3,2) Q(3,3)
3 2 0 1 1 1 0 1
求的真值。
解
例2 试将一阶逻辑公式化成前束范式。
解
第五章图论
[复习知识点]
1、图、完全图、子图、母图、支撑子图、图的同构
2、关联矩阵、相邻矩阵
3、权图、路、最短路径，迪克斯特拉算法（Dijkstra）
4、树、支撑树、二叉树
5、权图中的最小树，克鲁斯卡尔算法（Kruskal）
6、有向图、有向树
本章重点内容：权图的最短路、二叉树的遍历、权图中的最优支撑树
[复习要求]
1、理解图的有关概念：图、完全图、子图、母图、支撑子图、图的同构。
2、掌握图的矩阵表示（关联矩阵、相邻矩阵）。
3、理解权图、路的概念，掌握用Dijkstra算法求权图中最短路的方法。
4、理解树、二叉树与支撑树的有关概念；掌握二叉树的三种遍历方法，用Kruskal算法求
权图中最小树的方法。
5、理解有向图与有向树的概念。
[本章重点习题]
P221，2；P225，1；P231，2，3；P239，5；P242，1，2。
[疑难解析]
1.本章的概念较多，学习时需要认真比较各概念的含义，如：图、子图、有向图、权图；树、支撑树、二叉树、有向树；路、简单路、回路等，这些都是图的基本概念，今后将在数据结构、数据库、计算机网络等课程中用到。
2、权图中的最短路
严格执行迪克斯特拉（Dijkstra）算法步骤，从起点起，到每一点求出最短路，然后进行仔细比较，最后到达终点，算出最小权和。
3、权图中的最优支撑树
权图中的最优支撑树是图中所带权和最小的支撑树，使用克鲁斯卡尔（Kruskal）算法。[典型例题]
例1在具有n个顶点的完全图K n中删去多少条边才能得到树？
解：n个顶点的完全图K n中共有n?（n-1）/2条边，
n个顶点的树应有n-1条边，
于是，删去的边有：n?（n-1）/2-（n-1）=（n-1）?（n-2）/2
例2求下面有限图中点u到各点间的最短路。（图上数字见教材P231，第3题。）
解u→u1 ，d(u, u1)=1, 路(u, u1)
u→ u2 , d(u, u2)=9, 路(u, u4, u3, u7, u2)
u→ u3 , d(u, u3)=5, 路(u, u4, u3 ,)
u→ u4 , d(u, u4)=3, 路(u, u4 )
u→ u5 , d(u, u5)=11, 路(u, u1, u5)或路(u, u4, u3 , u7 , u2 , u5)
u→ u6 , d(u, u6)=13, 路(u, u1, u5, u6)
u→ u7 , d(u, u7)=8, 路(u, u4 , u3 , u7)
u→ u8 , d(u, u8)=11, 路(u, u4, u8)
u→v, d(u, v)=15, 路(u, u1, u5 , u6 ,v) 或路(u, u4 , u3 , u7 , u6 ,v)
二、考核说明
本课程的考核实行形成性考核和终结性考核的形式。形成性考核占总成绩的20%，以课程作业的形式进行（共三次，由中央电大统一布置）；终结性考核即期末考试，占总成绩的80%。总成绩为100分，60分及格。
期末考试实行全国统一闭卷考核，试卷满分为100。由中央电大统一命题，统一评分标准，统一考试时间（考试时间为120分钟）。
1、试题类型
试题类型有填空题（分数约占20%）、单项选择题（分数约占14%）、计算题（分数约占50%）和证明题（分数约占16%）。
填空题和单项选择题主要涉及基本概念、基本理论，重要性质和结论、公式及其简单计算。计算题主要考核学生的基本运算技能，要求书写计算、推论过程或理由。证明题主要考查应用概念、性质、定理及主要结论进行逻辑推理的能力，要求写出推理过程。
2、考核试卷题量分配
试卷题量在各部分的分配是：集合论约占40%，数理逻辑约占40%，图论约占20%。
具体课程考核情况见课程考核说明。
附录：试题类型及规范解答举例
[填空题]
1.设R 是集合A上的二元关系，如果关系R同时具有自反性、对称性和传递
性，则称R是等价关系。
2.命题公式G=（P∧Q）→R，则G共有8 个不同的解释；把G在其所有解释
下所取真值列成一个表，称为G的真值表；解释（?P，Q，?R）或（0，1，0）使G的真值为 1 。
3.设G=（P，L）是图，如果G是连通的，并且无回路，则G是树。如果
根树T的每个点v最多有两棵子树，则称T为二叉树。
[单项选择题]（选择一个正确答案的代号，填入括号中） 1. 由集合运算定义，下列各式正确的有（ A ）。
A ． X ?X ?Y B.X ?X ?Y C.X ?X ?Y D.Y ?X ?Y
2. 设R 1，R 2是集合A={a ，b ，c ，d}上的两个关系，其中R 1={（a ，a ），（b ，b ），（b ，c ），
（d ，d ）}，R 2={（a ，a ），（b ，b ），（b ，c ），（c ，b ），（d ，d ）}，则R 2是R 1的（ B ）闭包。
A ．自反
B ．对称
C ．传递
D ．以上都不是 3. 设G 是由5个顶点组成的完全图，则从G 中删去（ C ）条边可以得到树。
A ．4
B ．5
C ．6
D ．10 [计算题] 1. 化简下式：
（A -B -C ）?（（A -B ）?C ）?（A ?B -C ）?（A ?B ?C ） 2. 通过求主析取范式判断下列命题公式是否等值。
（1）（P ∧Q ）∨（?P ∧Q ∧R ）；
（2）（P ∨（Q ∧R ））∧（Q ∨（?P ∧R ））；
3. 求图中A 到其余各顶点的最短路径，并写出它们的权。
[证明题]
1. 利用基本等价式证明下面命题公式为恒真公式。
（（P →Q ）∧（Q →R ））→（P →R ）
2. 用形式演绎法证明：{P →Q ， R →S ，P ∨R }蕴涵Q ∨S 。 试题答案及评分标准 [填空题]
B 7 C
A D
4
6
E 1 F
1、自反；传递
2、8；真值表；1
3、无回路；二叉树
[单项选择题]（选择一个正确答案的代号，填入括号中）
1、A
2、B
3、C
[计算题]
1.解：
（A-B-C）?（（A-B）?C）?（A?B-C）?（A?B?C）
=（A?~B?~C）?（A?~B?C）?（A?B?~C）?（A?B?C）
=（（A?~B）?（~C?C））?（（A?B）?（~C?C））
=（（A?~B）?E）?（（A?B）?E）E为全集
=（A?~B）?（A?B）
= A?（~B?B）
= A?E
= A
2.解：
（P∧Q）∨（?P∧Q∧R）
?（P∧Q∧（?R∨R））∨（?P∧Q∧R）
?（P∧Q∧?R）∨（P∧Q∧R）∨（?P∧Q∧R）
?m6∨m7∨m3
?m3∨m6∨m7
（P∨（Q∧R））∧（Q∨（?P∧R））
?（P∧Q）∨（Q∧R）∨（P∧?P∧R）∨（?P∧ Q ∧R）（分配律）?（P∧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）
?m6∨m7∨m3∨m7∨m3
?m3∨m6∨m7
由此可见（P∧Q）∨（?P∧Q∧R）?（P∨（Q∧R））∧（Q∨（?P∧R））
3.解：
A到B的最短路径为AB，权为1；
A到E的最短路径为ABE，权为3；
A到F的最短路径为ABEF，权为4；
A到C的最短路径为ABEFC，权为7；
A到D的最短路径为ABEFCD，权为9。
[证明题]
1.证明：
（（P→Q）∧（Q→R））→（P→R）
?（（?P∨Q）∧（?Q∨R））→（?P∨R）
??（（?P∨Q）∧（?Q∨R））∨（?P∨R）
?（P∧?Q）∨（Q∧?R）∨?P∨R
?（（P∧?Q）∨?P ）∨（（Q∧?R）∨R）
?（1∧（?Q∨?P ））∨（（Q∨R）∧1）
??Q∨?P∨Q∨R
?（?Q∨Q）∨?P ∨R
? 1 ∨?P ∨R
? 1
2.证明：
（1）P∨R 规则P
（2）?R→P 规则Q ，根据（1）
（3）P→Q 规则P
（4）?R →Q 规则Q，根据（2）（3）
（5）?Q→R 规则Q，根据（4）
（6）R→S 规则P
（7）?Q→S 规则Q，根据（5）（6）
（8）Q∨S 规则Q ，根据（7）
三、综合练习及解答
（一）填空题
1、集合的表示方法有两种：列举法和描述法。请把“大于3而小于或等于7的整数集合”用任一种集合的表示方法表示出来
A={ x|3 2、 A ，B 是两个集合，A={1，2，3，4}，B={2，3，5}，则B-A= {5} ，ρ （B ）-ρ（A ）= ，ρ（B ）的元素个数为 8 。 3、 设}2,1{}, ,{==B b a A ，则从A 到B 的所有映射是 。 4、 设命题公式，则使公式G 为假的解释是 、 和 。 5、设G 是完全二叉树，G 有15个点，其中8个叶结点，则G 的总度数为 28 ，分枝点数为 7 。 6、全集E={1，2，3，4，5}，A={1，5}，B={1，2，3，4}，C={2，5}， 求A ?~B= {5} ，ρ（A ）?ρ（C ）= ， ~C= {1,3,4} 。 7、设A 和B 是任意两个集合，若序偶的第一个元素是A 的一个元素，第二个元素是B 的一个元素，则所有这样的序偶集合称为集合A 和B 的 ， 记作A ?B ，即A ?B= 。A ?B 的子集R 称为A ，B 上的 。 8、将几个命题联结起来，形成一个复合命题的逻辑联结词主要有否定、 、 、 和等值。 9、表达式?x ?yL （x ，y ）中谓词的定义域是{a ，b ，c}，将其中的量词消除，写成与之等价的命题公式为 。 10、一个无向图表示为G=（P ，L ），其中P 是 的集合，L 是 的集合，并且要求 。 （二）单项选择题（选择一个正确答案的代号，填入括号中） 1. 设命题公式，则G 是（ C ）。 A.恒真的 B.恒假的 C.可满足的 D.析取范式 2、设集合，A 上的关系，则=（ A ）。 3、一个公式在等价意义下，下面哪个写法是唯一的（ C ）。 A．析取范式B．合取范式C．主析取范式D．以上答案都不对 4、设命题公式G=?（P→Q），H=P→（Q→?P），则G与H的关系是（ A ）。 A．G?H B．H?G C．G=H D．以上都不是 5、已知图G的相邻矩阵为，则G有（ C ）。 A.5点，8边 B. 6点，7边 C. 5点，7边 D. 6点，8边 6、下列命题正确的是（ A ）。 A．φ?{φ}=φB．φ?{φ}=φC．{a}∈{a，b，c} D．φ∈{a，b，c} 7、设集合A={a，b，c}，A上的关系R={（a，b），（a，c），（b，a），（b，c），（c，a），（c， b），（c，c）}，则R具有关系的（ B ）性质。 A．自反B．对称C．传递D．反对称 8、设R为实数集，映射σ=R→R，σ（x）= -x2+2x-1，则σ是（D ）。 A．单射而非满射B．满射而非单射C．双射D．既不是单射，也不是满射9、下列语句中，（ C ）是命题。 A．下午有会吗？B．这朵花多好看呀！C．2是常数。D．请把门关上。10、下面给出的一阶逻辑等价式中，（ A ）是错的。 A．?x（A（x）∨B（x））=?xA（x）∨?xB（x） B．A→?xB（x）=?x （A→B（x）） C．?x（A（x）∨B（x））=?xA（x）∨?xB（x） D．??xA（x）=?x（?A（x）） （三）计算题 1、设R和S是集合上的关系，其中，试求：（1）写出R和S 的关系矩阵； （2）计算。 2、设A={a，b，c，d}，R1，R2是A上的关系，其中R1={（a，a），（a，b），（b，a），（b， b），（c，c），（c，d），（d，c），（d，d）}，R2={（a，b），（b，a），（a，c），（c，a），（b，c），（c，b），（a，a），（b，b），（c，c）}。 （1）画出R1和R2的关系图； （2）判断它们是否为等价关系，是等价关系的求A中各元素的等价类。 3、用真值表判断下列公式是恒真？恒假？可满足？ （1）（P∧?P）?Q （2）?（P→Q）∧Q （3）（（P→Q）∧（Q→R））→（P→R） 4、设解释I为： （1）定义域D={-2，3，6}； （2）F（x）：x≤3； G（x）：x>5。 在解释I下求公式?x（F（x）∨G（x））的真值。 5、求下图所示权图中从u到v的最短路，画出最短路并计算它们的权值。 V17 V3 1 2 U 2 5 3 V 4 6 V2 1 V4 6、化简下式： （（A?B?C）?（A?B））-（（A?（B-C））?A） 7、已知A={1，2，3，4，5}，B={1，2，3}，R是A到B的二元关系，并且R={（x，y） |x∈A且y∈B且2≤ x+y ≤4}，画出R的关系图，并写出关系矩阵。 8、画出下面偏序集（A，≤）的哈斯图，并指出集合A的最小元、最大元、极大元和极小 元。其中A={a，b，c，d，e}，≤={（a，b），（a，c），（a，d），（a，e），（b，e），（c，e），（d，e）}?I A。 9、求命题公式?（P∨Q）?（P∧Q）的析取范式与合取范式。 10、给定解释I如下： 定义域D={2，3}； f（2）f（3）F（2，2）F（2，3）F（3，2）F（3，3） 3 2 0 0 1 1 求?x?y（F（x，y）→F（f（x），f（y）））。 11、设有5个城市v1，v2，v3，v4，v5，任意两城市之间铁路造价如下：（以百万元为单位） w （v 1，v 2）=4， w （v 1，v 3）=7， w （v 1，v 4）=16， w （v 1，v 5）=10， w （v 2，v 3）=13， w （v 2，v 4）=8， w （v 2，v 5）=17， w （v 3，v 4）=3， w （v 3，v 5，）=10， w （v 4，v 5）=12 试求出连接5个城市的且造价最低的铁路网。 （四）证明题 1、证明等价式。 2、 利用形式演绎法证明：},,,,{T R S T S R P Q P ?→?→?→∨蕴涵Q 。 3、 A ，B ，C 为任意的集合，证明： （A -B ）-C=A -（B ?C ） 4、 利用一阶逻辑的基本等价式，证明： ?x ?y （F （x ）→G （y ））=?xF （x ）→?yG （y ） 练习解答 （一）填空题 1、列举；描述；A={4，5，6，7}或A={x|3 2、{5}；{{5}，{2，5}，{3，5}，{2，3，5}}；8 3、σ1={（a ，1），（b ，1）}；σ2={（a ，2），（b ，2）}；σ3={（a ，1），（b ，2）}；σ4={（a ， 2），（b ，1）} 4、（1，0，1）； （1，1，1）； （1，0，0） 5、 28； 7 6、{5}；{φ，{5}}；{1，3，4} 7、笛卡尔积（或直乘积）；{（x ，y ）|x ∈A 且y ∈B}；二元关系 8、并且（或合取）；或者（或析取）；蕴涵 9、（L （a ，a ）∨L （a ，b ）∨L （a ，c ））∧（L （b ，a ）∨L （b ，b ）∨L （b ，c ））∧（L （c ，a ） ∨L （c ，b ）∨L （c ，c ）） 10、点；连接某些不同点对的边；一对不同点之间最多有一条边 （二）单项选择题（选择一个正确答案的代号，填入括号中） 1、C 2、A 3、C 4、A 5、C 6、A 7、B 8、D 9、C 10、A （三）计算题 1、解：（1） （2）={（1，2），（3，4）} ={（1，1），（1，2），（1，3），（2，3），（2，4）， （3，4），（4，4）} ={（1，1），（3，1），（3，2），（4，3）} ={（2，1），（4，3）} 2、解： R1和R2的关系图略。 由关系图可知，R1是等价关系。R1不同的等价类有两个，即{a，b}和{c，d}。 由于R2不是自反的，所以R2不是等价关系。 3、解： （1）真值表 因此公式（1）为可满足。 （2）真值表 因此公式（2）为恒假。 （3）真值表 因此公式（3）为恒真。 4.解： ?x（F（x）∨G（x）） ?（F（-2）∨G（-2））∨（F（3）∨G（3））∨（F（6）∨G（6））?（1∨0）∨（1∨0）∨（0∨1） ? 1 5.解： 从U到V的最短路为U→V1→V2→V4→V3→V。最短路权值为9。 图中圆圈中的数字为使用迪克斯特拉算法添加边的次序。 6、解： （（A?B?C）?（A?B））-（（A?（B-C））?A） =（A?B）- A （利用两次吸收律） =（A?B）?~ A =（A?~ A）?（B?~ A） = φ?（B?~ A） = B- A 7、解： 离散数学试题(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={ 郫县友爱职业技术学校2013——2014学年度下期 高一财经就业班《基础会计》期末复习题 一、单项选择题 1.企业收到投资者投入设备一台，原价 60000 元，双方评估确认价 50000 元，则实收资本账户贷方登记的金额为( )元。 A.60000 B.50000 C.10000 D.70000 2.不属于产品成本项目的费用有( )。 A.直接材料 B.直接人工 C.制造费用 D.管理费用 3.企业购入材料发生的运杂费等采购费用应计入( )。 A.管理费用 B.材料物资采购成本 C.生产成本 D.销售费用 4.期末结转后可能有余额的账户是( )。 A.生产成本 B.营业税金及附加 C.财务费用 D.制造费用 5.( )不应计入当期损益的。 A.管理费用 B.财务费用 C.所得税费用 D.制造费用 6.( )不能计入产品成本的是。 A.制造费用 B.原材料 C.工资及福利费 D.管理费用 7.“ 主营业务成本” 账户的借方余额登记从( )账户中结转的本期已售产品的生产成本。 A.生产成本 B.库存商品 C.销售费用 D.在途物资 8.资本公积是企业( )中的主要组成部分。 A.资产 B.负债 C.所有者权益 D.收入 9.8月31日“ 本年利润” 账户有贷方余额 50000 元，表示( )。 A.8月份实现利润 50000 元 B.8月31日现利润 50000 元 C.1月1日至8月31日共计实现的利润为 50000 元 D.1月1日年初未分配利润为 50000 元 10.固定资产因损耗而减少的价值，应贷记( )账户。 A.“ 固定资产” B.“ 累计折旧” C.“ 管理费用” D.“ 制造费用” 11.企业应交纳的教育费附加应计入( )账户贷方。 离散数学复习注意事项： 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为实数。命题“任何有理数都是实数”的符号化为（） 离散数学复习要点第一章命题逻辑 一、典型考查点 1、命题的判断方法：陈述句真值唯一，特殊：反问句也是命题。其它疑问句、祈使句、感叹句、悖论等皆不是。详见教材P1 2、联结词运算定律┐∧∨→记住特殊的：1∧1?1，0∨0?0，1→0?0，11?1，00?1详见P5 3、命题符号化步骤：A划分原子命题，找准联结词。特殊自然语言：不但而且，虽然但是用∧，只有P才Q，应为Q→P；除非P否则Q，应为┐P→Q。B设出原子命题写出符号化公式。详见P5 4、公式的分类判定（重言式、矛盾式、可满足式）方法：其一根据所有真值赋值情况，其二根据等价演算来判断。详见P9 5、真值表的构造步骤：①命题变元按字典序排列，共有2n个真值赋值。②对每个指派，以二进制数从小到大或从大到小顺序列出。③若公式较复杂，可先列出各子公式的真值(若有括号，则应从里层向外层展开)，最后列出所求公式的真值。详见P8。 6、基本概念：置换规则，P规则，T规则，详见P24；合取范式，析取范式，详见P15；小项详见P16；大项详见P18，最小联结词组详见P15 7、等价式详见P22表1.6.2 证明方法：①真值表完全相同②用等价演算③利用A?B的充要条件是A?B且B?A。主要等价式：(1)双否定：??A?A。(2)交换律：A∧B?B∧A，A∨B?B∨A，A?B?B?A。3)结合律：(A∧B)∧C?A ∧(B∧C)，(A∨B)∨C?A∨(B∨C)，(A?B)?C?A?(B?C)。(4) 分配律：A∧(B∨C)?(A∧B)∨(A∧C)，A∨(B∧C)?(A∨B)∧(A∨C)。(5) 德·摩根律：?(A∧B)??A∨?B，?(A∨B)??A∧?B。(6) 等幂律：A∧A?A，A∨A?A。(7) 同一律：A∧T?A，A∨F?A。(8) 零律：A∧F?F，A∨T?T。(9) 吸收律：A∧(A∨B)?A，A∨(A∧B)?A。(10) 互补律：A∧?A?F，(矛盾律)，A∨?A?T。(排中律)(11) 条件式转化律：A→B??A∨B，A→B??B→?A。(12) 双条件式转化律：A?B?(A→B)∧(B→A)?(A∧B)∨(?A∧?B) 8、蕴含式详见P23表1.6.3 证明方法：①前件真导后件真方法②后件假导前件假方法③真值表中，前件为真的行，后件也为真或者后件为假的行，前件也为假。④用定义，证A?B，即证A→B是永真式。 9、范式求法步骤：①使用命题定律，消去公式中除∧、∨和?以外公式中出现的所有联结词；②使用?(?P)?P和德·摩根律，将公式中出现的联结词?都移到命题变元之前；③利用结合律、分配律等将公式化成析取范式或合取范式。10、主范式的求法重点步骤：(a)把给定公式化成析取（合取）范式；(b)删除析取范式中所有为永假的简单合取（析取）式；(c)用等幂律化简简单合取（析取）式中同一命题变元的重复出现为一次出现，如P∧P?P。(d)用同一律补进简单合取（析取）式中未出现的所有命题变元，如Q，则P?P∧（?Q∨Q)或P?P∨（?Q∧Q)，并用分配律展开之，将相同的简单合取式的多次出现化为一次出现，这样得到了给定公式的主析取（合取）范式。 注意：主析取范式与主合取范式之间的联系。例如：(P→Q)∧Q?m1∨m3?M0∧M2，即剩下的编码就是另一个主范式的编码，因此，求主范式，哪一个简单易求，就先求哪个，然后对应出所求结果。详见P16 11、推理证明：重点方法：演算、演绎法（常用的格式）、反证法、CP规则即附加前提等。 重点规则（主要蕴含式）：(1) P∧Q?P化简(2) P∧Q?Q化简(3) P?P∨Q附加(4) ?P?P→Q变形附加(5)Q?P→Q变形附加(6) ?(P→Q)?P变形化简(7) ?(P→Q)??Q变形化简(8) P，(P→Q)?Q假言推理(9) ?Q，(P→Q)??P拒取式(10) ?P，(P∨Q)?Q析取三段论(11) (P→Q)，(Q→R)?P→R条件三段论(12) (P?Q)，(Q?R)?P?R 双条件三段论 文字证明推理三步：一命题符号化，二写出前提和结论，三进行证明。详见P21 二、强化练习 1.命题的是( )A.走，看电影去B.x+y>0C.空集是任意集合的真子集D.你明天能来吗? 2.下列式子为重言式的是( ) A.P→P∨Q B.(┐P∧Q)∧(P∨┐Q) C.┐ (P Q) D.(P∨Q) (P→Q) 3．下列为两个命题变元P，Q的小项是（） A．P∧Q∧? P B．? P∨Q C．? P∧Q D．? P∨P∨Q 4．下列语句中是真命题的是（） A．我正在说谎B．严禁吸烟C．如果1+2=3，那么雪是黑的D．如果1+2=5，那雪是黑的 5．设P：我们划船，Q：我们跑步。命题“我们不能既划船又跑步”符号化为（） A．? P∧? Q B．? P∨? Q C．?（P?Q） D．?（? P∨? Q） 6．命题公式（P∧（P→Q））→Q是（）A．矛盾式B．蕴含式C．重言式D．等价式 7．命题公式?（P∧Q）→R的成真指派是（） A．000，001，110，B．001，011，101，110，111 C．全体指派D．无 系 专业 年级 班级 学号 姓名 ……………………装……………………订……………………线…………………… 泉州师院2009-2010学年度第一学期 2008级计算机《离散数学》期中试卷 题 序 一 二 三 四 五 总分 成 绩 签 名 一、单项选择题:（20%，每空2分） 1．设A={a,{a}}，下列命题错误的是（ B ）。 A ．{a}P(A) B ．{a}P(A) C ．{{a}}P(A) D ．{{a}}P(A) 2、假定全集E ＝{1,2,3,4,5,6,7,8,9,10},A={3,4,5}，B ＝{2,3,4,7,8,9}，则A ∪B 的位串是（ D ）。 A ．01 B ．0011100000 C ．00 D ．00 3、下列文氏图阴影部分所表示的集合是( A )。 A. (A-(B ∪C))∪((B ∪C)-A) B. (A-(B ∩C))∪((B ∩C)-A) C. (A-(B ∩C))∪((B ∪C)-A) D. (A-(B ∪C))∪((B ∩C)-A) 4．设p ：你主修计算机科学，q ：你是新生， r ：你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 A ．r →p ∨q B ．r →p ∧q C ．r →p ∨q D ．r →p ∨q 5．下列是两个命题变元p ，q 的极小项是（ A ） A ．┐p ∧q B ．┐p ∨q C ．p ∧┐p ∧q D ．┐p ∨p ∨q 6、下列等值式不正确的是（ C ） A ．┐(x)A(x)┐A B ．(x)(B →A(x))B →(x)A(x) C ．(x)(A(x)∧B(x))(x)A(x)∧(x)B(x) D ．(x)(y)(A(x)→B(y))( x)A(x)→(y)B(y) 7、若s={1,2,3,4}，S 上关系R 的关系图为： 则R 具有（ B ）性质。 A 、自反性 B 、自反性、对称性 C 、反自反性、反对称性 D 、自反性、对称性、传递性 8．设A={a,b,c,d}，A 上的等价关系R={ 基础会计学练习题以及答案 一、 1、现代会计的开端是（管理会计的形成并与财务会计相分离而单独成科） 2、会计的最基本的两项职能是（反映职能和监督职能） 3、凡支出的效果与几个会计年度相关的，应作为（资本性支出） 4、对于与本期收有关的一切未来费用，应在本期内预提，属于（配比）原则的规定 5、会计等式的标准形式（资产=负债+所有者权益） 6.按照借贷记账法的记录方法,下列四组账户中,增加额均记在贷方的是(负债、所有者权益) 9.不单独设置"预付账款"账户的企业,发生预付货款业务应记入的账户是(应收账款) 10.原始凭证的概念是(在经济业务发生或完成时取得或填制的，用来证明经济业务的发生或者完成的情况，并作为记账的原始依据) 11.属于记账编制凭证的是(记账凭证) 12.对于经营性租入的固定资产,应登记的账簿是(备查账) 13."管理费用"明细账一般采用的账页格式是(多栏式) 15.平时对各项财产物资的增加数和和减少数,都要根据会计凭证连续记入有关账簿,并且随时结出账面结存数的盘存方法叫(永续盘存制) 16.既属于财务成果报表又属于月报表的是（利润表） 17.按照报送对象的不同利润表属于(对外会计报表) 18.特定的会计凭证账簿组织和特定的记账程序相互结合的方式称为(会计核算) 19.会计核算形式中最基本的一种会计核算形式是(记账凭证核算) 20.位于我国会计法规体系中最高层次的是(《中华人民共和国会计法》) 21.会计主体是指会计所服务的（特定单位） 22.存货在物价上涨时的计价采用后进先出法，体现了（谨慎性原则） 23.科目属于负债的是(流动负债、长期负债) 24.按照借贷记账法的记录方法,记录在账户的贷方的是(负债、所有者权益) 25.对于需要安装的机器设备,应将其购进时支付的价款、包装费、运输费和安装费记入（固定资产）账户的借方． 26.按用途和结构分,"盈余公积"账户属于(所有者投资账户) 28.属于外来原始凭证的是(购买货物取得的发货票、增值税专用发票、银行为企业待收款项的收款通知单等) 29.原始凭证的基本内容包括(1、原始凭证的名称2、填制凭证的日期3、填制凭证单位名称或者填制人姓名4、经办人员的签名或盖章5、接受凭证单位名称6、经济业务内容（以上通称为凭证要素） 30.按账簿的用途的分类,现金日记账属于(序时账簿) 31."原材料"明细账一般采用的账页格式是(数量金额式) 32账簿按用途可分为(序时账簿、分类账簿、联合账簿、备查账簿) 33.在核对银行存款时,如果企业银行存款日记账余额与银行对账单余额不符,应编制(银行存款对账单) 34.银行存款清查的方法是(与开户银行核对账) 35.(记账凭证)不能作为调整或登记账簿的凭证 36.按照反映的内容不同，现金流量表属于（会计报表） 38.直接根据记账凭证,逐笔登记总分类账的依据是(记账凭证核算形式) 39.我国会计法规体系主要由(《会计法》、〈〈企业会计准则〉〉、〈〈企业会计制度〉〉等会计核算方面法规制度) 40.集中核算方式就是把(企业)主要会计核算工作都集中在企业一级的会计部门进行. 41.在社会主义市场经济条件下，会计的对象是社会再生产过程中主要（以货币表现的经济活动） 42.企业资产以历史成本计价现不以现行成本或清算价格计价，依据的会计核算基本前提是（历史成本原则） 43.经济业务中引起资产和负债同时减少的是(还款) 44.按照借贷记账法的记录方法,下列账户中,账户的贷方登记增加额的是(负债所有者权益) 45."材料采购"账户应按(数量金额)设置明细账. 46."待摊费用"按经济内容分类属于(流动资产) 47"预提费用"按用途和结构分类属于(负债) 48.将会计凭证划分为原始凭证和记账凭证的依据是(填制的程序和用途) 离散数学期末复习 一、选择题 1、下列各选项错误的是 A、??? B、??? C、?∈{?} D、??{?} 2、命题公式(p∧q)→p是 A、矛盾式 B、重言式 C、可满足式 D、等值式 3、如果是R是A上的偏序关系，R-1是R的逆关系，则R∪R-1是 A、等价关系 B、偏序关系 C、全序关系 D、都不是 4、下列句子中那个是假命题？ A、是无理数. B、2 + 5＝8. C、x+ 5＞3 D、请不要讲话！ 5、下列各选项错误的是？ A、??? B、??{?} C、?∈{?} D、{?}?? 6、命题公式p→（p∨q∨r）是？ A、重言式 B、矛盾式 C、可满足式 D、等值式 7、函数f : N→N, f(x)=x+5,函数f是 A、单射 B、满射 C、双射 D、都不是 8、设D= D、不连通的 9、关系R1和R2具有反自反性，下面运算后，不能保持自反性的是 A、R1?R2 B、R1-1 C、R1?R2 D、R1-R2 10、连通平面图G有4个结点，3个面，则G有（）条边。 A、7 B、6 C、5 D、4 二、填空题 1、将下面命题符号化。设p:天冷，q:小王穿羽绒服。只要天冷，小王就穿羽绒服.符号化为 2、将下面命题符号化，设p:天冷，q:小王穿羽绒服。因为天冷，所以小王穿羽绒服.符号化为 3、将下面命题符号化，设p:天冷，q:小王穿羽绒服。若小王不穿羽绒服，则天不冷.符号化为 4、将下面命题符号化，设p:天冷，q:小王穿羽绒服。只有天冷，小王才穿羽绒服.符号化为 离散数学 一、逻辑和证明 1.1命题逻辑 命题：是一个可以判断真假的陈述句。 联接词：∧、∨、→、?、?。记住“p仅当q”意思是“如果p，则q”，即p→。记住“q除非p”意思是“?p→q”。会考察条件语句翻译成汉语。 系统规范说明的一致性是指系统没有可能会导致矛盾的需求，即若pq无论取何值都无法让复合语句为真，则该系统规范说明是不一致的。 1.3命题等价式 逻辑等价：在所有可能情况下都有相同的真值的两个复合命题，可以用真值表或者构造新的逻辑等价式。 谓词+量词变成一个更详细的命题，量词要说明论域，否则没有意义，如果有约束条件就直接放在量词后面，如?x>0P(x)。 当论域中的元素可以一一列举，那么?xP(x)就等价于P(x1)∧P(x2)...∧P(xn)。同理，?xP(x)就等价于P(x1)∨P(x2)...∨P(xn)。 两个语句是逻辑等价的，如果不论他们谓词是什么，也不论他们的论域是什么，他们总有相同的真值，如?x（P(x)∧Q(x))和(?xP(x))∧(?xQ(x))。 量词表达式的否定：??xP(x) ??x?P(x)，??xP(x) ??x?P(x)。 1.5量词嵌套 我们采用循环的思考方法。量词顺序的不同会影响结果。语句到嵌套量词语句的翻译，注意论域。嵌套量词的否定就是连续使用德摩根定律，将否定词移入所有量词里。 1.6推理规则 一个论证是有效的，如果它的所有前提为真且蕴含着结论为真。但有效论证 二、集合、函数、序列、与矩阵 2.1集合 ∈说的是元素与集合的关系，?说的是集合与集合的关系。常见数集有N={0,1,2,3...}，Z整数集，Z+正整数集，Q有理数集，R实数集，R+正实数集，C复数集。 A和B相等当仅当?x(x∈A?x∈B)；A是B的子集当仅当?x(x∈A→x∈B)；A是B的真子集当仅当?x(x∈A→x∈B)∧?x(x?A∧x∈B)。 幂集：集合元素的所有可能组合，肯定有?何它自身。如?的幂集就是{?}，而{?}的幂集是{?，{?}}。 考虑A→B的函数关系，定义域、陪域（实值函数、整数值函数）、值域、像集（定义域的一个子集在值域的元素集合）。 一对一或者单射：B可能有多余的元素，但不重复指向。 映上或者满射：B中没有多余的元素，但可能重复指向。 一一对应或者双射：符合上述两种情况的函数关系。 反函数：如果是一一对应的就有反函数，否则没有。 合成函数：fοg(a)=f(g(a))，一般来说交换律不成立。 2.4序列 无限集分为：一组是和自然数集合有相同基数，另一组是没有相同基数。前者是可数的，后者不可数。想要证明一个无限集是可数的只要证明它与自然数之间有一一对应的关系。 如果A和B是可数的，则A∪B也是可数的。 离散数学期末试题及答 案 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分，共20分) 1．不能作为记账依据的是( )。 A．发货票B．收货单C．入库单 D.经济合同 2．通过试算平衡能够查出的错误有( )。 A．漏记经济业务B．重汇经济业务C．记账方向错误D．借贷金额不对 3．企业预付保险金，应借记( )账户。 A．预提费用B．待摊费用C．银行存款 D.管理费用 4．通常在年度决算之前，要( )。 A对企业所有财产进行技术推算盘点B．对企业所有财产进行全面清查 C．对企业一部分财产进行清查D．对企业流动性较大的财产进行全面清查 5．下列不属于采购费用的项目有( )。 A．材料买价B．运杂费C．途中合理损耗 D.采购员差旅费 6.三栏式现金日记账一般由( )登记。 A．会计B．经手人C．出纳D．会计主管 7．在实地盘存制下，平时账面上应登记的内容有( )。 A．存货的增加B．存货的减少C．结存的存货D．存货的损耗 8．损益类账户期末应( )。 A．没有余额 B．借方余额C．贷方余额D．借贷方均有余额 9．企业本月销售产品10000元，收到货款6000元，收到上月产品成本销售货款8000元，收到预收货款7000元，则在收付实现制原则下，应确认为本月收入的是( )元。 A．21000 B．18000 C．14000 D．10000 10．下列凭证中，不能用来登记总分类账户的是( )。 A．原始凭证B．记账凭证C．汇总记账凭证D．科目汇总表 11．某企业购入丙材料，增值税专用发票上注明货款20000元，增值税3400元，发生包装费，运杂费共计300元，丙材料的采购成本为( )。 A．20000元B．23400元C．20300元D．23700元 离散数学期末复习要点与重点 离散数学是中央广播电视大学开放教育本科电气信息类计算机科学与技术专业的一门统设必修学位课程，共72学时，开设一学期．该课程的主要内容包括：集合论、图论、数理逻辑等． 下面按章给出复习要点与重点． 第1章 集合及其运算 复习要点 1．理解集合、元素、集合的包含、子集、相等，以及全集、空集和幂集等概念，熟练掌握集合的表示方法． 具有确定的，可以区分的若干事物的全体称为集合，其中的事物叫元素.． 集合的表示方法：列举法和描述法. 注意：集合的表示中元素不能重复出现，集合中的元素无顺序之分． 掌握集合包含(子集)、真子集、集合相等等概念． 注意：元素与集合，集合与子集，子集与幂集，∈与?(?),空集?与所有集合等的关系. 空集?，是惟一的，它是任何集合的子集． 集合A 的幂集P (A )＝}{A x x ?， A 的所有子集构成的集合．若∣A ∣＝n ，则∣P (A )∣=2n ． 2．熟练掌握集合A 和B 的并A ?B ，交A ?B ，补集~A (~A 补集总相对于一个全集).差集A －B ，对称差⊕，A ⊕B ＝(A －B )?(B －A )，或A ⊕B ＝(A ?B )－（A ?B ）等运算，并会用文氏图表示． 掌握集合运算律(见教材第9～11页)(运算的性质). 3．掌握用集合运算基本规律证明集合恒等式的方法． 集合的运算问题：其一是进行集合运算；其二是运算式的化简；其三是恒等式证明． 证明方法有二：(1)要证明A ＝B ，只需证明A ?B ，又A ?B ； (2)通过运算律进行等式推导． 重点：集合概念，集合的运算，集合恒等式的证明． 第2章 关系与函数 复习要点 1．了解有序对和笛卡儿积的概念，掌握笛卡儿积的运算． 有序对就是有顺序二元组，如 离散数学习题参考答案 第一章集合 １.分别用穷举法,描述法写出下列集合 （１）偶数集合 (２)36的正因子集合 (３)自然数中3的倍数 (４)大于１的正奇数 (1)E={?,-6,-4,-2,0,2,4,6,?} ={2 i | i∈I } (2) D= { 1, 2, 3, 4, 6, } = {x>o | x|36 } (3) N3= { 3, 6, 9, ```} = { 3n | n∈N } (4) A d= {3, 5, 7, 9, ```} = { 2n+1 | n∈N } ２.确定下列结论正确与否 (１)φ∈φ× (２)φ∈｛φ｝√ (３)φ?φ√ (４)φ?｛φ｝√ (５)φ∈｛ａ｝× (６)φ?｛ａ｝√ (７)｛ａ,ｂ｝∈｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝× (８)｛ａ,ｂ｝?｛ａ,ｂ,ｃ,｛ａ,ｂ,ｃ｝｝√(９)｛ａ,ｂ｝∈｛ａ,ｂ,｛｛ａ,ｂ｝｝｝× (１０)｛ａ,ｂ｝?｛ａ,ｂ,｛｛ａ,ｂ｝｝｝√ ３.写出下列集合的幂集 (１)｛｛ａ｝｝ {φ, {{ a }}} ( 2 ) φ {φ} (３)｛φ,｛φ｝｝ {φ, {φ}, {{φ}}, {φ,{φ}} } (４)｛φ,ａ,｛ａ,ｂ｝｝ {φ, {a}, {{a,b }}, {φ}, {φ, a }, {φ, {a,b }}, {a, {a b }}, {φ,a,{ a, b }} } (５)Ｐ(Ｐ(φ)) {φ, {φ}, {{φ}}, {φ,{φ}} } ４.对任意集合Ａ,Ｂ,Ｃ,确定下列结论的正确与否(１)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ∈Ｃ√ (２)若Ａ∈Ｂ,且Ｂ?Ｃ,则Ａ?Ｃ× (３)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ∈Ｃ× (４)若Ａ?Ｂ,且Ｂ∈Ｃ,则Ａ?Ｃ × ５.对任意集合Ａ,Ｂ,Ｃ,证明 右 分配差差左=--=--)C A ()B A ()C B (A M .D )C B (A )C B (A ) C A ()B A ()C B (A )1(I Y I Y I I I I I Y 右 差分配差左右差的结论差左=--=-------=-)C A ()B A ()C A ()B A () C B (A M . D )C B (A )2)C A ()B A ()C A ()B A ()1()C B (A )1) C A ()B A ()C B (A )2(Y I Y I Y I I I Y I Y Y I 右 交换结合幂等差左=--=-)C A ()B A (,)C B ()A A () C B (A M . D )C B (A ) C A ()B A ()C B (A )3(I I I I I I I I Y I I Y ))B )B (A ())B B ()B A ((,)B )B A (()B )B A ((B )B A (B A B )B A )(4(I I Y I Y I I Y I I Y --⊕=⊕+结合分配对称差差左 右 零一互补==φ-φ-)B A ()B A () A ()U ) B A ((Y Y I I Y 《离散数学》试卷（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人同时选修三门课程。问 （１）三门课程都不选的学生有多少？ （２）只选修计算机课程的学生有多少？ 《基础会计》（专科）复习题一 一、单项选择题(每题1分，共20分) 1．不能作为记帐依据的是( )。 A．发货票 B．收货单 C．入库单 D.经济合同 2．通过试算平衡能够查出的错误有( )。 A．漏记经济业务 B．重汇经济业务 C．记帐方向错误 D．借贷金额不对 3．企业预付保险金，应借记( )帐户。 A．预提费用 B．待摊费用 C．银行存款 D.管理费用 4．通常在年度决算之前，要( )。 A对企业所有财产进行技术推算盘点 B．对企业所有财产进行全面清查 C．对企业一部分财产进行清查 D．对企业流动性较大的财产进行全面清查 5．下列不属于采购费用的项目有( )。 A．材料买价 B．运杂费 C．途中合理损耗 D.采购员差旅费 6.三栏式现金日记帐一般由( )登记。 A．会计 B．经手人 C．出纳 D．会计主管 7．在实地盘存制下，平时帐面上应登记的内容有( )。 A．存货的增加 B．存货的减少 C．结存的存货 D．存货的损耗 8．损益类帐户期末应( )。 A．没有余额 B．借方余额 C．贷方余额 D．借贷方均有余额 9．企业本月销售产品10000元，收到货款6000元，收到上月产品成本销售货款8000元，收到预收货款7000元，则在收付实现制原则下，应确认为本月收入的是( )元。 A．21000 B．18000 C．14000 D．10000 10．下列凭证中，不能用来登记总分类帐户的是( )。 A．原始凭证 B．记帐凭证 C．汇总记帐凭证 D．科目汇总表 11．某企业购入丙材料，增值税专用发票上注明货款20000元，增值税3400元，发生包装费，运杂费共计300元，丙材料的采购成本为( )。 A．20000元 B．23400元 C．20300元 D．23700元 12．“预提费用”帐户是用来核算( )。 A．先计入成本后支付的费用 B．先支付后计入成本的费用 C．先预提后计入成本的费用 D．先预提后摊销的费用 13．某企业99年末负债与所有者权益的比例为1：3，则所有者权益是资产的( ) A．40％ B．25％ C．33％ D．75％ 14．对应收帐款进行明细分类核算时，其明细帐格式应采用( ) A．多栏式 B．三栏式 C．数量金额式 D.数量式 15．将现金2000元存入银行，出纳人员应填制( )。 A．转帐凭证 B．原始凭证 C．收款凭证 D．付款凭证 16．会计报表中反映一定日期财务情况的报表是( )。 A．损益表 B．利润分配表 C．资产负债表 D．财务状况变动表 17．企业发生原材料盘亏价值500元，经查明属企业管理制度不严所致，此项业务应在( )帐户中核算． A．应付帐款 B．营业外支出 C．管理费用 D．其他应收款 18．限额领料单属于( )。 A．累计原始凭证 B．汇总原始凭证 C．一次凭证 D．转帐凭证 泉州师院2009-2010学年度第一学期 2008级计算机《离散数学》期中试卷 一、单项选择题:（20%，每空2分） 1．设A={a,{a}}，下列命题错误的是（ B ）。 A ．{a}∈P(A) B ．{a}?P(A) C ．{{a}}∈P(A) D ．{{a}}?P(A) 2、假定全集E ＝{1,2,3,4,5,6,7,8,9,10},A={3,4,5}，B ＝{2,3,4,7,8,9}，则A ∪B 的位串是（ D ）。 A ．1000000001 B ．0011100000 C ．0111001110 D ．0111101110 3、下列文氏图阴影部分所表示的集合是( A )。 A. (A-(B ∪C))∪((B ∪C)-A) B. (A-(B ∩C))∪((B ∩C)-A) C. (A-(B ∩C))∪((B ∪C)-A) D. (A-(B ∪C))∪((B ∩C)-A) 4．设p ：你主修计算机科学，q ：你是新生， r ： 你可以从校园网访问因特网。只有你主修计算机科学或不是新生，你才可以从校园网访问因特网。可符号化为( C )。 A ．r →p ∨q B ．r →p ∧q C ．r →p ∨?q D ．r →p ∨?q 5．下列是两个命题变元p ，q 的极小项是（ A ） A ．┐p ∧q B ．┐p ∨q C ．p ∧┐p ∧q D ．┐p ∨p ∨q 6、下列等值式不正确的是（ C ） A ．┐(?x)A ?(?x)┐A B ．(?x)(B →A(x))?B →(?x)A(x) C ．(?x)(A(x)∧B(x))?(?x)A(x)∧(?x)B(x) D ．(?x)(?y)(A(x)→B(y))?( ?x)A(x)→(?y)B(y) 7、若s={1,2,3,4}，S 上关系R 的关系图为： 则R 具有（ B ）性质。 A 、自反性 B 、自反性、对称性 C 、反自反性、反对称性 D 、自反性、对称性、传递性 8．设A={a,b,c,d}，A 上的等价关系R={离散数学期末考试试题(有几套带答案)
2014基础会计期末复习题
(完整word版)离散数学期末练习题带答案
离散数学复习要点
计算机《离散数学》期中试卷答案
基础会计学练习题以及答案
离散数学期末复习
离散数学知识点整理
离散数学期末试题及答案完整版
基础会计精选期末试题及复习资料
离散数学期末复习要点与重点
离散数学期末复习试题及答案
离散数学期末试卷A卷及答案
基础会计(专科) 期末考试试题及参考答案
08计算机《离散数学》期中试卷答案
相关主题
文本预览