离散数学中等价关系的性质
【摘要】等价关系是离散数学中非常重要的内容之一，文[1]研究了等价关系的一些性质，本文在[1]的基础上对等价关系的性质做进一步的研究，得出了新的结论。
【关键词】离散数学；二元关系；等价关系
1 预备知识
“离散数学”是计算机专业的重要基础课程和核心课程，等价关系是离散数学中非常重要的内容之一，本文介绍了等价关系的概念，给出了等价关系的一些性质。
定义 1 设R 为非空集合A 上的二元关系，如果对任意x∈A，都有∈R，则称R具有自反性。
定义 2 设R 为非空集合A 上的二元关系，如果对任意x，y∈A，若∈R，则∈R，称R具有对称性。
定义 3 设R 为非空集合A 上的二元关系，如果对任意x，y，z∈A，若∈R且∈R，都有∈R，称R具有传递性。
定义 4 设R 为非空集合A 上的二元关系，如果R具有自反性、对称性和传递性，则称R 为A 上的等价关系。
2 主要结果
定理1 设R是集合A上的二元关系，令S={∣？埚z∈A使∈R且∈R}，若R是等价关系，则S也是等价关系。
证明：因为R是等价关系
（1）由于R是自反的，所以对任意x∈A有∈R，由S的定义知∈R且∈R，所以∈S，所以S是自反的。
（2）若∈S，则？埚z∈A使∈R且∈R。
因为R是对称的，所以∈R且∈R，由S的定义知∈S，所以S是对称的。
（3）若∈S且∈S，
则？埚u∈A使∈R且∈R
“离散数学”中的等价关系 “离散数学”是计算机专业的重要基础课程和核心课程。通过该课程的教学，不仅要为学生们进一步学习本专业的后续课程提供必备的数学理论基础，更重要的是培养和提高学生的抽象思维能力和逻辑推理能力。与高等数学主要以连续量作为研究对象不同，离散数学主要以离散量作为主要的研究对象，内容包括数理逻辑、集合论、代数结构、图论以及组合数学、数论和离散概率等。由于这些内容在描述形式、研究方法和计算机应用领域等方面均存在着较大差异，且含有大量比较抽象的概念、定理和各种各样的形式化描述，因而学生普遍感到困难重重，学习效果不理想。因此，如何改进教学方法，提高教学效果，使学生们的抽象思维能力和逻辑推理能力真正得到提升，是“离散数学”课程教学过程中必须认真解决的重要课题。 1离散数学课程中的等价关系 1.1离散数学课程中等价关系的概念 定义1 设R为非空集合A上的二元关系。如果R是自反的、对称的和可传递的，则称R为A上的等价关系。 定义2 设R为非空集合A上的等价关系，x∈A，令[ x ]R={ y | y ∈A ∧xRy }， 则称[ x ]R 为x关于R的等价类，简记为[ x ]。 定义3 设R为非空集合A上的等价关系，以R的所有等价类作元素的集合称为A关于R的商集，记为A/R，即A/R={ [ x ]R| x∈A }。 根据定义1，很容易证明矩阵理论中的矩阵合同关系、相似关系都是等价关系；线性空间的同构关系也是一种等价关系。下面主要讨论离散数学中一些常见的等价关系。 1.2离散数学课程中各种具体的等价关系 数理逻辑中，命题公式A和B等值(记为A B)是指由它们构成的等价式A B 为永真式。命题公式的等值关系是建立在由所有命题公式构成的集合上的一种等价关系，这种等价关系将所有命题公式按其是否等值划分成若干个等价类，属于同一个等价类中的命题公式彼此等值，因而，只要清楚了等价类中某一个公式的性质，则与该公式同类的公式的性质也就完全清楚了。因此，命题公式的等值关系(等价关系)是获取命题公式性质的基石。 集合论中，集合A和B的等势是指从A到B存在一个双射函数即集合A中
集合论部分 第四章、二元关系和函数 集合的笛卡儿积与二元关系有序对 定义由两个客体x 和y，按照一定的顺序组成的 二元组称为有序对，记作
不适合交换律A B B A (A B, A, B) 不适合结合律 (A B)C A(B C) (A, B)对于并或交运算满足分配律 A(B C)=(A B)(A C) (B C)A=(B A)(C A) A(B C)=(A B)(A C) (B C)A=(B A)(C A) 若A或B中有一个为空集，则A B就是空集. A=B= 若|A|=m, |B|=n, 则 |A B|=mn 证明A(B C)=(A B)(A C) 证任取
§3.4 等价关系与划分 习题3.4 1. 对于给定的集合A 和其上的二元关系R ，判断R 是否为等价关系。 （1）A 为实数集，A y x ∈?，，2=-?y x xRy 。 （2）}321{，，=A ，A y x ∈?，，3≠+?y x xRy 。 （3）+=Z A ，即正整数集，A y x ∈?，，是奇数xy xRy ?。 （4）)(X P A =，集合X 的基数2||≥X ，A y x ∈?，，x y y x xRy ?∨??。 （5）)(X P A =，集合X 和C 满足X C ?，A y x ∈?，，C y x xRy ?⊕?。 解 略 2. 设}{d c b a A ，，，=，对于A 上的等价关系 A I c d d c a b b a R }{><><><><=，，，，，，， 画出R 的关系图，并求出A 中各元素关于R 的等价类。 解 R 的关系图如下： A 中各元素关于R 的等价类分别为： },{][][b a b a ==，},{][][d c d c == 3. 考虑单词的集合}{sit wind wash sky last sheet W ，，，，，=。1R 和2R 分别是由“具有同样多的字母”和“具有相同的开头字母”定义的等价关系。求由1R 和2R 确定的商集1/R W 和2/R W 。 解 略 4. 给出模6同余关系，并求出所有的模6同余类。 解 模6同余关系)}6(mod |{b a b a b a R ≡∧∈><=Z ，， 所有的模6同余类为： 510}|5{][，，，， =∈+=i z i z i Z 即 },20,15,10,5,0,5,10,15,20,{]0[ ----= },21,16,11,6,1,4,9,14,19,{]1[ ----=
离散数学知识点总结 一、各章复习要求与重点 第一章 集 合 [复习知识点] 1、集合、元素、集合的表示方法、子集、空集、全集、集合的包含、相等、幂集 2、集合的交、并、差、补等运算及其运算律（交换律、结合律、分配律、吸收律、 De Morgan 律等），文氏（V enn ）图 3、序偶与迪卡尔积 本章重点内容：集合的概念、集合的运算性质、集合恒等式的证明 [复习要求] 1、理解集合、元素、子集、空集、全集、集合的包含、相等、幂集等基本概念。 2、掌握集合的表示法和集合的交、并、差、补等基本运算。 3、掌握集合运算基本规律，证明集合等式的方法。 4、了解序偶与迪卡尔积的概念，掌握迪卡尔积的运算。 [本章重点习题] P5~6，4、6； P14~15，3、6、7； P20，5、7。 [疑难解析] 1、集合的概念 因为集合的概念学生在中学阶段已经学过，这里只多了一个幂集概念，重点对幂集加以掌握，一是掌握幂集的构成，一是掌握幂集元数为2n 。 2、集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 [例题分析] 例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。 解 }}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A }}2,1{},2{},1{,{)(φρ=B 于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ
1.【实验目的】 对称： 通过算法设计并编程实现对给定集合上的关系是否为对称关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法 自反： 通过算法设计并编程实现对给定集合上的关系是否为自反关系的判断，加深学生对关系性质的理解，掌握用矩阵来判断关系性质的方法。 2.【实验内容】 已知关系R 由关系矩阵M 给出，要求判断由M 表示的这个关系是否为对称关 系。假定R 的关系矩阵为：?????? ? ??=1234210330124321M 3.【实验要求】 C 语言编程实现 4.【算法描述】 对称： 从给定的关系矩阵来判断关系R 是否为对称是很容易的。若M （R 的关系矩阵）为对称矩阵，则R 是对称关系；若M 为反对称矩阵，则R 是反对称关系。因为R 为对称的是等价关系的必要条件，所以，本算法可以作为判等价关系算法的子程序给出。 算法实现： （1） 输入关系矩阵M （M 为n 阶方阵）； （2） 判断对称性，对于i=2，3，….，n ；j=1，2,……，i-1，若存在m ij =m ji ， 则R 是对称的； （3） 判断反对称性； （4） 判断既是对称的又是反对称的； （5） 判断既不是对称的又不是反对称的； （6） 输出判断结果。
自反： 从给定的关系矩阵来断判关系R是否为自反是很容易的。若M（R的关系矩阵）的主对角线元素均为1，则R是自反关系；若M（R的关系矩阵）的主对角线元素均为0，则R是反自反关系；若M（R的关系矩阵）的主对角线元素既有1又有0，则R既不是自反关系也不是反自反关系。本算法可以作为判等价关系算法的子程序给出。 算法实现 （1）输入关系矩阵M（M为n阶方阵）。 （2）判断自反性，对于i=1，2，….，n；若存在m =0，则R不是自反 ii =1，则R是自反的；否则R既不是自反关系也不是的；若存在m ii 反自反关系。 （3）输出判断结果。 源代码 #include
离散数学试题一（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分）若
离散数学是一门研究离散量结构及其相互关系的数学学科，是现代数学的重要分支。离散的含义是指不同的连接元素，主要根据离散量研究结构和它们之间的关系，其对象通常是有限的或可数的元素。离散数学已广泛应用于各个学科，尤其是计算机科学和技术。同时，离散数学也是计算机专业许多专业课程必不可少的高级课程，例如编程语言，数据结构，操作系统，编译技术，人工智能，数据库，算法设计和分析以及计算机理论基础。通过对离散数学的研究，我们不仅可以掌握处理离散结构的描述工具和方法，为后续课程创造条件，还可以提高抽象思维和严格的逻辑推理能力，打下坚实的基础。参与未来的创新研发工作。 随着信息时代的到来，以微积分为代表的连续数学在工业革命时代的主导地位发生了变化，离散数学的重要性逐渐为人们所认识。离散数学教授的思想和方法广泛地反映在计算机科学和技术及相关专业的各个领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，所有这些都与离散数学密切相关。因为数字电子计算机是离散结构，所以它只能处理离散或离散的定量关系。因此，计算机科学本身以及与计算机科学及其应用密切相关的现代科学研究领域都面临着如何为离散结构建立相应的数学模型的问题。以及如何离散化通过连续数量关系建立的数学模型，以便可以通过计算机对其进行处理。
离散数学是一门综合性学科，由传统逻辑，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系论，图论和树，抽象代数（包括代数系统，组）组成。，环，域等），布尔代数和计算模型（语言和自动机）。离散数学已应用于现代科学和技术的许多领域。 离散数学也可以说是计算机科学的基本核心学科。离散数学中有一个著名的典型例子-四色定理，也称为四色猜想，它是现代世界上三个主要的数学问题之一。它是由英国制图员弗朗西斯·古斯里（Francis guthrie）于1852年提出的。当他为地图着色时，他发现了一种现象：“每张地图只能用四种颜色着色，而具有共同边界的国家可以使用不同的颜色。”那么可以通过数学证明吗？100多年后的1976年，肯尼思·阿佩尔（Kenneth Appel）和沃尔夫冈·哈肯（Wolfgang Haken）使用了计算机辅助计算，这花了1200个小时和100亿次判断，终于证明了四色定理，这在世界上引起了轰动。这是离散数学与计算机科学合作的结果。 离散数学可以看作是数学与计算机科学之间的桥梁，因为离散数学不仅可以与诸如集合论和图论之类的数学知识区分开，而且与计算机科学中的数据库理论和数据结构有关，这可以导致人们进入计算机科学的思维领域，促进计算机科学的发展。
第四章二元关系 例1 设A={0,1}，B={a,b}，求A?B ，B?A，A?A 。 解：A?B={<0,a>,<0,b>,<1,a>,<1,b>} B?A={
离散数学等价关系 等价关系是设是非空集合A上的二元关du系，若R是自反的、对称的、传递的，则称R是A上的等价关系。给定非空集合A,若有集合S={S ,S ,…,S }，其中S A，S（i=1,2,…,m）且S S = (i j)同时有S =A，称S是A的划分。研究等价关系的目的在于将集合中的元素进行分类，选取每类的代表元素来降低问题的复杂度，如软件测试时，可利用等价类来选择测试用例。 分成一块的有： 划分1：{{1,2,3,4}}，对应的等价关系就是全域关系E，也就是A×A。分成两块的有： 划分2：{{1,2},{3,4}}， 划分3：{{1,3},{2,4}}， 划分4：{{1,4},{2,3}}，分成三块的有： 划分5：{{1},{2,3,4}}， 划分6：{{2},{1,3,4}}， 划分7：{{3},{1,2,4}}， 划分8：{{4},{1,2,3}}，分成四块的有： 划分9：{{1},{2},{3},{4}}，对应的等价关系就是恒等关系I。 由划分求等价关系：
定义：若关系R在集合A中是自反、对称和传递的，则称R为A 上的等价关系。所谓关系R 就是笛卡尔积 A×A 中的一个子集。A 中的两个元素x,y有关系R，如果(x,y)∈R。我们常简记为 xRy。 自反：任意x属于A，则x与自己具有关系R，即xRx； 对称：任意x,y属于A，如果x与y具有关系R，即xRy，则y与x也具有关系R，即yRx； 传递：任意x,y,z属于A，如果xRy且yRz，则xRz。 x,y具有等价关系R，则称x,y R等价，有时亦简称等价。
等价类： 在离散数学中，等价关系是指定义在集合A上的关系，满足自反的、对称的和传递的等性质。设R是定义在集合A上的等价关系，与A中一个元素a有关系的所有元素的集合叫做a的等价类。等价类应用十分广泛，如在编程语言中，我们使用等价类来判定标识符是不是表示同一个事物。 定义： 在离散数学中，等价关系是指定义在集合A上的关系，满足自反的、对称的和传递的等性质。设R是定义在集合A上的等价关系，与A中一个元素a有关系的所有元素的集合叫做a的等价类。A的关于R的等价类记作。当只考虑一个关系时，我们省去下表R并把这个等价类写作[a]。 在软件工程中，是把所有可能输入的数据，即程序的输入域划分成若干部分（子集），然后从每一个子集中选取少数具有代表性的数据作为测试用例，从而减少了数据输入量从而提高了效率，称之为等价类方法，该方法是一种重要的、常用的黑盒测试用例设计方法。 分类： 在离散数学中，等价类的划分基于以下定理：设R是定义在集合A上的等价关系。那么R的等价类构成S的划分。反过来，给定集合S的划分{ |i∈I},则存在一个等价关系R，它以集合作为它的等价类。 因为等价关系的a 在a 中和任何两个等价类要么相等要么不
交集不相交的性质。得出X 的所有等价类的集合形成X 的集合划分划分: 所有X 的元素属于一且唯一的等价类。反过来，X 的所有划分也定义了在X 上等价关系。 在软件工程中等价类划分及标准如下： 划分等价类 等价类是指某个输入域的子集合。在该子集合中，各个输入数据对于揭露程序中的错误都是等效的，并合理地假定：测试某等价类的代表值就等于对这一类其他值的测试，因此，可以把全部输入数据合理划分为若干等价类，在每一个等价类中取一个数据作为测试的输入条件就可以用少量代表性的测试数据取得较好的测试结果。等价类划分有两种不同的情况：有效等价类和无效等价类。 1）有效等价类 是指对于程序的规格说明来说是合理的、有意义的输入数据构成的集合。利用有效等价类可检验程序是否实现了规格说明所规定的功能和性能。 2）无效等价类 指对程序的规格说明是不合理的或无意义的输入数据所构成的集合。对于具体的问题，无效等价类至少应有一个，也可能多个。 设计测试用例时，要同时考虑这两种等价类。因为软件不仅要能接收合理的数据，也要能经受意外的考验，这样的测试才能确保软件具有更高的可靠性。 3.划分等价类的标准
离散数学期末复习题 第一章集合论 一、判断题 （1）空集是任何集合的真子集． （ 错 ） （2）{ }φ是空集． （ 错 ） （3）{}{ }a a a },{∈ （ 对 ） （4）设集合{}{ }{}{}A A 22,1,2,1,2,1?=则. ( 对 ） （5）如果 B A a ??，则A a ?或B a ?． （ 错 ） 解 B A a ??则B A B A a ?=?∈，即A a ∈且B a ∈，所以A a ?且B a ? （6）如果A ∪.,B A B B ?=则 （ 对 ） （7）设集合},,{321a a a A =，},,{321b b b B =，则 },,,,,{332211><><><=?b a b a b a B A （ 错 ） （8）设集合}1,0{=A ，则}1},0{,0},0{,1,,0,{><><><><=φφρ是A 2到A 的关系． （ 对 ） 解 A 2}},1{},0{,{A φ=， =?A A 2}1,,0,,1},1{,0},1{,1},0{,0},0{,1,,0,{><><><><><><><>∈ 《离散数学》符号表 ? 全称量词（任意量词） ? 存在量词 ├ 断定符（公式在L 中可证） ╞ 满足符（公式在E 上有效，公式在E 上可满足） ┐ 命题的“非”运算 ∧ 命题的“合取”（“与”）运算 ∨ 命题的“析取”（“或”，“可兼或”）运算 → 命题的“条件”运算 ? 命题的“双条件”运算的 B A ? 命题A 与B 等价关系 B A ? 命题A 与B 的蕴涵关系 * A 公式A 的对偶公式 wff 合式公式 iff 当且仅当 V 命题的“不可兼或”运算（ “异或门” ） ↑ 命题的“与非” 运算（ “与非门” ） ↓ 命题的“或非”运算（ “或非门” ） □ 模态词“必然” ◇ 模态词“可能” φ 空集 ? 属于（?不属于） A μ（·） 集合A 的特征函数 P （A ） 集合A 的幂集 A 集合A 的点数 n A A A ??? （n A ） 集合A 的笛卡儿积 R R R =2 )(1R R R n n -= 关系R 的“复合” 0? 阿列夫零 ? 阿列夫 ? 包含 ? 真包含 ∪ 集合的并运算 ∩ 集合的交运算 - （～） 集合的差运算 ⊕ 集合的对称差运算 m + m 同余加 m ? m 同余乘 〡 限制 R x ][ 集合关于关系R 的等价类 A /R 集合A 上关于R 的商集 )(A R π 集合A 关于关系R 的划分 )(A R π 集合A 关于划分π的关系 ][a 元素a 产生的循环群 R a ][ 元素a 形成的R 等价类 r C 由相容关系r 产生的最大相容类 I 环，理想 )/(n Z 模n 的同余类集合 ) (mod k b a ≡ a 与b 模k 相等 )(R r 关系R 的自反闭包 )(R s 关系R 的对称闭包 +R ，)(R t 关系R 的传递闭包 *R ，)(R rt 关系R 的自反、传递闭包 .i H 矩阵H 的第i 个行向量 j H . 矩阵H 的第j 个列向量 CP 命题演绎的定理（CP 规则） EG 存在推广规则（存在量词引入规则） ES 存在量词特指规则（存在量词消去规则） UG 全称推广规则（全称量词引入规则） 第二章二元关系 习题2.1 1. a)R = {<0, 0>, <0, 2>, <2, 0>, <2, 2>} b)R = {<1, 1>, <4, 2>} 2. R1? R2 = {<1, 2>, <2, 4>, <3, 3>, <1, 3>, <4, 2>} R1? R2 = {<2, 4>} dom R1= {1, 2, 3} dom R2= {1, 2, 4} ran R1= {2, 3, 4} ran R2= {2, 3, 4} dom (R1? R2) = {1, 2, 3, 4} ran (R1? R2) = {4} 3. 证明：（根据定义域和值域的定义进行证明） 因为 x ∈ dom (R1? R2) 当且仅当有y ∈ B使得 概念问题 二进制关系：A和B的笛卡尔积的子集称为从A到B的二进制关系。集合上的关系：从a到a的关系。 关系的性质 反射，抗反射，对称，抗对称和传输。 没有列出概念，但应注意以下方面： （1）所有属性的概念都是逻辑表达式，即判断是非，必须严格按照定义判断是非； （2）它们都是用全名量词表示的逻辑表达式，因此必须为真才能保持一致； （3）它们全部由隐含条件语句表示。如果前提为假，则它也为真，也就是说，所有未出现在真之后再为假的内容都为真。 关系代表 （1）设置符号（适合定义和表示）； （2）图表表示（适合直观感觉和观察特性）； （3）关系矩阵表示（适合计算）；特别地，关系矩阵是布尔矩阵，即逻辑矩阵，其描述A中的第i个元素是否与B中的第j个元素有关。 关系运作 （1）交叉，合并与区别 R1?R2————M1ùM2 R1èR2————M1úM2 （2）综合 合成操作非常重要且容易出错。注意其顺序以及对集合，图形和矩阵的相应计算。 自我及其综合运算形成力量。 例如，R 2对应于由点直接连接的边，这些点可以从图形上的每个点分两步到达。 另一个例子 R1°R2 ————M2M1 R ^ 2 ————M ^ 2 关系的应用 （1）n元关系的应用 一般来说，当2元关系扩展到N元关系时，它就成为数据库的基本框架。N元有序对是N个字段的记录，因此关系操作对应于数据库操作。我们只知道这部分内容（与数据库重复）。 （2）封闭的应用 首先，介绍了三种闭包的概念。如果用一句话来概括，R的自反/对称/传递闭包是包含R的自反/对称/传递关系中最小的。 然后其应用着重于掌握传递闭包的应用，它可以显示传递性直接通过连接边可到达的点的连通性。 然后讨论三个闭包的计算： （3）等价关系的应用 首先是等价关系的概念，以及等价类和划分的扩展概念。 其次，等价关系的应用仅仅是分类。因为等价与划分之间存在一一对应的关系。 A.如果一个关系是集合a上的等价关系，写出每个元素的等价类，然后删除重复项，则由非重复等价类组成的集合就是原始集合a的除法。B，如果子集族是集合A的划分，则根据“属于同一个子集的人如果有关系就可以配对”的规则，二元有序对的集合必须满足反射性，对称性和可传递性，是等价的关系。 （4）偏序关系的应用 第一个是偏序的概念，并扩展了“小于或等于”，“小于”和“可比”。然后是整个顺序，然后是良好顺序（自己比较概念）。 《离散数学》期末复习提要 《离散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。 离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。 课程的主要内容 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、集合恒等式的证明 通过对集合恒等式证明的练习，既可以加深对集合性质的理解与掌握；又可以为第三章命题逻辑中公式的基本等价式的应用打下良好的基础。实际上，本章做题是一种基本功训练，尤其要求学生重视吸收律和重要等价式在B A B A ~?=-证明中的特殊作用。 [例题分析] 例1 设A ，B 是两个集合，A={1，2，3}，B={1，2}，则=-)()(B A ρρ 。 解 }}3,2,1{},3,2{},3,1{},2,1{},3{},2{},1{,{)(φρ=A }}2,1{},2{},1{,{)(φρ=B 于是}}3,2,1{},3,2{},3,1{},3{{)()(=-B A ρρ 例2 设{}{}Φ=,,,,b a b a A ，试求： (1){}b a A ,-； (2)Φ-A ； (3){}Φ-A ； (4){}{}A b a -,； (5)A -Φ； (6){}A -Φ。 解 (1){}{}{ }Φ=-,,,b a b a A (2)A A =Φ- (3){}{}{}b a b a A ,,,=Φ- (4){}{ }Φ=-A b a , (5)Φ=-ΦA (6){}Φ=-ΦA 例3 试证明()()()()B A B A B A B A ~~~~???=??? 证明 等价关系（4学时） 【教学目的】 了解、掌握等价关系及相应的等价类与集合划分的基本概念及例子 【教学要求】 正确地掌握等价关系及相应的等价类与集合划分之间的关系；给定A上的等价关系R，会求所有的等价类和商集A/R，或者求与R相对应的划分；反之给定集合 A上的划分π，求对应于π的等价关系 【教学重点】 等价关系、偏序关系的各种性质的判断和证明； 【教学难点】 如何正确地掌握等价关系及相应的等价类与集合划分之间的关系 【教学方法】 讲练结合教学法、提问式与启发式相结合教学法。 【教学手段】 传统板书与多媒体课件辅助教学相结合。 【课型】新授课 教学过程 4.1一种特殊的二元关系——等价关系(Equivalence Relation). 一、等价关系(Equivalence Relation) 1、定义4.18 设R为非空集合上的关系.如果R是自反的、对称的和传递的, 则称R为A 上的等价关系.设R是一个等价关系, 若 湖南师范大学硕士研究生入学考试自命题考试大纲 考试科目代码：考试科目名称：离散数学 一、试卷结构 1) 试卷成绩及考试时间 本试卷满分为100分，考试时间为180分钟。 2)答题方式：闭卷、笔试 3)试卷内容结构 集合论40% 数理逻辑40% 图论20% 4)题型结构 a: 填空题，5小题，每小题5分，共25分 b: 计算题，3小题，每小题10分，共30分 c: 证明题，3小题，每小题15分，共45分 二、考试内容与考试要求 1、集合论 考试内容 集合及其表示集合的运算与性质二元关系的概念二元关系的五种性质关系矩阵与关系图关系的各种运算与性质关系闭包与性质相容关系等价关系序关系部分函数、满射、内射、双射的概念可逆、左可逆、右可逆函数特征函数集合的基数与性质 考试要求 （1）理解集合的表示、二元关系的概念、部分函数、满射、内射、双射的概念可逆、左可逆、右可逆函数的概念； （2）掌握集合的运算与性质、关系的五种性质、关系的运算与性质、关系闭包与性质、相容关系、等价关系、序关系. （3）了解特征函数集合的基数与性质． 2、数理逻辑 考试内容 命题与命题的真值五个基本联结词命题符号化合式公式真值表合式公式的类型等价式、蕴含式的证明范式和判定问题求主范式的方法变元、谓词和量词量词的辖域、前束范式合式公式的解释、求合式公式在给定解释下真值的方法 考试要求 （1）理解命题与命题的真值、联结词、合式公式与真值表、变元、谓词和量词等概念． （2）掌握合式公式的类型、等价式、蕴含式的证明、求主范式的方法、合式公式的解释、以及求在给定解释下真值的方法． （3）了解量词的辖域、前束范式． 3、图论 考试内容 图的基本概念路与回路和连通性图的矩阵表示欧拉图和哈密顿图平面图对偶图与着色树与生成树根树及其应用 考试要求 （1）理解图、路、回路和连通性等基本概念． （2）掌握一些特殊图类的性质，树的特征与应用． 三、参考书目 [1] 左孝凌等，《离散数学》，上海科技文献出版社，1982年 [2] 王兵山、张强、毛晓光，《离散数学》，国防科技大学出版社，1998年 [3] 耿素云、屈宛玲，《离散数学》，高等教育出版社，2003年 离散数学考试题(后附详细答案) 一、命题符号化（共6小题，每小题3分，共计18分） 1.用命题逻辑把下列命题符号化 a)假如上午不下雨，我去看电影，否则就在家里读书或看报。 设P表示命题“上午下雨”，Q表示命题“我去看电影”，R表示命题“在家里读书”，S表示命题“在家看报”，命题符号化为：（P?Q）(P?R S) b)我今天进城，除非下雨。 设P表示命题“我今天进城”，Q表示命题“天下雨”，命题符号化为：Q→P或P→Q c)仅当你走，我将留下。 设P表示命题“你走”，Q表示命题“我留下”，命题符号化为： Q→P 2.用谓词逻辑把下列命题符号化 a)有些实数不是有理数 设R(x)表示“x是实数”，Q(x)表示“x是有理数”，命题符号化为： x(R(x) Q(x)) 或x(R(x) →Q(x)) b)对于所有非零实数x，总存在y使得xy=1。 设R(x)表示“x是实数”，E(x,y)表示“x=y”,f(x,y)=xy, 命题符号化为：x(R(x) E(x,0) →y(R(y) E(f(x,y),1)))) c) f 是从A到B的函数当且仅当对于每个a∈A存在唯一的b∈B，使得f(a)=b. 设F(f)表示“f是从A到B的函数”, A(x)表示“x∈A”, B(x)表示“x∈B”,E(x,y)表示“x=y”, 命题符号化为：F(f)??a(A(a)→?b(B(b) ∧ E(f(a),b) ∧?c(S(c) ∧ E(f(a),c) →E(a,b)))) 二、简答题（共6道题，共32分） 1.求命题公式(P→(Q→R))(R→(Q→P))的主析取范式、主合取范式，并写出所有成真赋 值。（5分） (P→(Q→R))(R→(Q→P))（P Q R）(P Q R) (（P Q R）→(P Q R)) ∧((P Q R) →（P Q R）). (（P∧Q∧R） (P Q R)) ∧ ((P∧Q∧R) （P Q R）) (P Q R) ∧(P Q R) 这是主合取范式 公式的所有成真赋值为000,001,010,100,101,111,故主析取范式为 （P∧Q∧R)（P∧Q∧R)（P∧Q∧R)（P∧Q∧R)（P∧Q∧R)（P∧Q∧R) 2.设个体域为{1,2,3}，求下列命题的真值（4分） a)x y(x+y=4) b)y x (x+y=4) a) T b) F 3.求x(F(x)→G(x))→(xF(x)→xG(x))的前束范式。（4分） x(F(x)→G(x))→(xF(x)→xG(x)) x(F(x)→G(x))→(yF(y)→zG(z)) 离散数学等价关系 一、离散数学是一门什么样的学科？ 与数学的主流分支不同，离散数学看上去似乎没有一个确定的中心话题，内容很庞杂。我曾做过一个粗略的统计，离散数学的内容涉及大约43个左右大大小小不同的话题，从集合、函数、关系、命题逻辑、谓词逻辑，到算法、计数、数据结构、递归、图论、概率、数论、形式语言与自动机，布尔代数、向量与矩阵，线性规划、抽象代数，编码理论、信息论，博弈论、运筹学、理论计算机科学等，真是那句俗话，XXXX是个筐，什么都可以往里装。由于离散数学的内容包括面很广，一本通常意义上的教科书不可能全部涵盖，因此我们看到的教科书基本是上述内容集合的不同子集。 那么到底应当如何定义「离散数学」这门学科呢？如果我们使用集合的语言表达就是： （1）离散数学= {x∈数学| 离散结构(x)} 其中，「离散数学」是「数学」的一个子集，「离散结构」是一个谓词，x代表任意数学学科。 现在来详细考察一下这个「离散数学」的定义式。我们的考察，从为什么会出现这样一个学科开始。 首先，离散数学和其它数学分支不同，它并没有开辟数学的新领域，而是在既有的数学领域划出一个范围，以「离散结构」这个性质为标准，若某个数学内容具有「离散结构」的属性就划入。 那为什么会出现「离散数学」这门学科呢？回答是——是因为计算机的出现！！！因为计算机只能处理「离散」对象。生活中「离散」对象和「连续」对象的例子是大米和水，前者是离散的，后者是连续的，因为米粒是可列举的、可数的，英语属于可数名词，中文可以用单位量词「粒」等表示，水是无法列举的、也是不可数的，因而在英语中属于不可数名词，中文则不可直接用单位量词表示。形象地说， 离散数学关系部分综合练习 一、单项选择题 1．设集合A = {1, a }，则A 的幂集P (A ) = ( )． A ．{{1}, {a }} B ．{?,{1}, {a }} C ．{?,{1}, {a }, {1, a }} D ．{{1}, {a }, {1, a }} 2．若集合A 的元素个数为10，则其幂集的元素个数为（ ）． A ．1024 B ．10 C ．100 D ．1 7．集合A ={1, 2, 3, 4, 5, 6, 7, 8}上的关系R ={离散数学符号表
二元关系(离散数学)
离散数学等价关系
离散数学复习要点
等价关系离散数学
010_离散数学
离散数学考试题详细答案
离散数学等价关系
离散数学关系部分经典练习及答案
相关主题
文本预览