南京工程学院
实验报告
课程名称离散数学
实验项目名称关系
实验学生班级 K网络工程121
实验学生姓名王云峰
学号 240121525
实验时间11月15日
实验地点信息楼
实验成绩评定
指导教师签字年月日
)若?x?y(x、y∈A∧xRy→yRx)称R是对称的；(3)若?x?y?z(x、y、z∈A∧xRy∧yRz→xRz)，称R是传递的；
4)若R是自反的、对称的和传递的，则称R是等价关系。
在程序实现中，集合和关系用都用集合方式输入。
六、实验总结与思考
判断任意一个关系是否为自反关系、对称关系、传递关系和等价关系？
若是等价关系，求出其所有等价类。
设R?A×A，(1)若?x(x∈A→xRx)，称R是自反的；(2)若?x?y(x、y
∈A∧xRy→yRx)，称R是对称的；(3)若?x?y?z(x、y、z∈A∧xRy∧yRz→xRz)，称R是传递的；(4)若R是自反的、对称的和传递的，则称R是等价关系。
在程序实现中，集合和关系用都用集合方式输入。抽象原则：任给一
个性质P，就确定了一个集合A，A的元素恰好是具有性质P的对象。子集、包含、包含于、真包含、全集U 、基数#A-元素个。幂集ρ(A)：A的全部子
集的集合交∩、并∪、差—、补~集。有穷集的计数原理：
#(A∪B∪C)=#A+#B+#C-#(A∩B) -#(A∩C) -#(B∩C)+#(A∩B∩C)4. 空串ε、连接运算、字母表Σ、Σ*、语言、闭包A*=A^0∪A^1∪… A^0=ε
正闭包A+= A^1∪…5. 有序偶
序列。笛卡尔乘积A×B={
序偶的集合R。
全域关系Ux、恒等关系Ix关系矩阵、关系图自反的、反自反的、对称的、
反对称的、传递的复合关系RοS：R是X到Y的关系，S是从Y到Z的关系，则X到Z的一个关系RοS满足结合律逆关系R^-1 （RοS)^-1=S^-1 ο R^-1自反闭包r(R)=R∪Ix、对称闭包s(R)=R∪R^-1、传递闭包t(R)=R^1 ∪
R^2…偏序≤：关系是自反的、反对称的、传递的全序、线序：可比严格偏序：反自反、传递的遮盖、哈斯图、最大元、极大元、上界、最小上界良序的：每个非空子集有最小元覆盖、划分、等价关系：自反的、对称的、传递
集合与关系《应用离散数学》 第3章 21世纪高等教育计算机规划教材
目录 3.1 集合及其运算 3.2 二元关系及其运算3.3 二元关系的性质与闭包3.4 等价关系与划分 3.5 偏序关系与拓扑排序3.6 函 数 3.7 集合的等势与基数3.8 多元关系及其应用
集合是现代数学中最重要的基本概念之一，数学概念的建立由于使用了集合而变得完善并且统一起来。集合论已成为现代各个数学分支的基础，同时还渗透到各个科学技术领域，成为不可缺少的数学工具和表达语言。对于计算机科学工作者来说，集合论也是必备的基础知识，它在开关理论、形式语言、编译原理等领域中有着广泛的应用。 本章首先介绍集合及其运算，然后介绍二元关系及其关系矩阵和关系图，二元关系的运算、二元关系的性质、二元关系的闭包，等价关系与划分、函数，最后介绍多元关系及其在数据库中的应用等。
3.1 集合及其运算 3.1.1 基本概念 集合是数学中最基本的概念之一，如同几何中的点、线、面等概念一样，是不能用其他概念精确定义的原始概念。集合是什么呢？直观地说，把一些东西汇集到一起组成一个整体就叫做集合，而这些东西就是这个集合的元素或叫成员。 例3.1 （1）一个班级里的全体学生构成一个集合。 （2）平面上的所有点构成一个集合。 （3）方程 的实数解构成一个集合。 （4）自然数的全体（包含0）构成一个集合，用N表示。 （5）整数的全体构成一个集合，用Z表示。 （6）有理数的全体构成一个集合，用Q表示。 （7）实数的全体构成一个集合，用R表示。
（8）复数的全体构成一个集合，用C表示。 （9）正整数集合Z+，正有理数集合Q+，正实数集合R+。（10）非零整数集合Z*，非零有理数集合Q*，非零实数集合R*。（11）所有n 阶(n≥2)实矩阵构成一个集合，用M n(R)表示，即
集合论练习题 一、选择题 1．设B = { {2}, 3, 4, 2}，那么下列命题中错误的是（ ）． A ．{2}∈ B B ．{2, {2}, 3, 4}B C ．{2}B D ．{2, {2}}B 2．若集合A ={a ，b ，{ 1，2 }}，B ={ 1，2}，则（ ）． A ． B A ，且BA B ．B A ，但BA C ．B A ，但BA D ．B A ，且BA 3．设集合A = {1, a }，则P (A ) = ( )． A ．{{1}, {a }} B ．{?,{1}, {a }} C ．{?,{1}, {a }, {1, a }} D ．{{1}, {a }, {1, a }} 4.已知AB ={1,2,3}, AC ={2,3,4},若2 B,则（ ） A ． 1?C B ．2? C C ．3?C D ．4?C 5. 下列选项中错误的是( ) A ． ??? B ． ?∈? C ． {}??? D ．{}?∈? 6. 下列命题中不正确的是（ ） A ． x {x }-{{x }} B ．{}{}{{}}x x x ?- C ．{}A x x =?,则xA 且x A ? D ． A B A B -=??= 7. A , B 是集合，P (A ),P (B )为其幂集，且A B ?=?，则()()P A P B ?=( ) A ． ? B ． {}? C ． {{}}? D ．{,{}}?? 8. 空集?的幂集()P ?的基数是( ) A ． 0 B ．1 C ．3 D ．4 9．设集合A = {1，2，3，4，5，6 }上的二元关系R ={a , b ∈A , 且a +b = 8}，则R 具有的性质为（ ）． A ．自反的 B ．对称的 C ．对称和传递的 D ．反自反和传递的
离散数学知识点总结 一、各章复习要求与重点 第一章 集 合 [复习知识点] 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
基本等值式 1.双重否定律A?┐┐A 2.幂等律 A ? A∨A, A ? A∧A 3.交换律A∨B ? B∨A，A∧B ? B∧A 4.结合律(A∨B)∨C ? A∨(B∨C) (A∧B)∧C ? A∧(B∧C) 5.分配律A∨(B∧C) ? (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) ? (A∧B)∨(A∧C) （∧对∨的分配律） 6.德·摩根律┐(A∨B) ?┐A∧┐B ┐(A∧B) ?┐A∨┐B 7.吸收律 A∨(A∧B) ? A，A∧(A∨B) ? A 8.零律A∨1 ? 1,A∧0 ? 0 9.同一律A∨0 ? A，A∧1 ? A 10.排中律A∨┐A ? 1 11.矛盾律A∧┐A ? 0 12.蕴涵等值式A→B ?┐A∨B 13.等价等值式A?B ? (A→B)∧(B→A) 14.假言易位A→B ?┐B→┐A 15.等价否定等值式 A?B ?┐A?┐B 16.归谬论(A→B)∧(A→┐B) ?┐A 求给定公式范式的步骤 (1)消去联结词→、?(若存在)。 (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。 推理定律--重言蕴含式 (1) A ? (A∨B) 附加律 (2) (A∧B) ? A 化简律 (3) (A→B)∧A ? B 假言推理 (4) (A→B)∧┐B ?┐A 拒取式 (5) (A∨B)∧┐B ? A 析取三段论 (6) (A→B) ∧(B→C) ? (A→C) 假言三段论 (7) (A?B) ∧(B?C) ? (A ? C) 等价三段论 (8) (A→B)∧(C→D)∧(A∨C) ?(B∨D) 构造性二难 (A→B)∧(┐A→B)∧(A∨┐A) ? B 构造性二难(特殊形式) (9)(A→B)∧(C→D)∧(┐B∨┐D) ?(┐A∨┐C) 破坏性二难
大连民族学院 计算机科学与工程学院实验报告实验题目：集合的运算 课程名称：离散数学 实验类型：□演示性□验证性□操作性□设计性□综合性专业：网络工程班级：网络111班 学生姓名：张山学号：2011083123 实验日期：2013年12月22日实验地点：I区实验机房 实验学时：8小时实验成绩： 指导教师签字：年月日老师评语：
1 实验题目：集合的运算 实验原理： 1、实验内容与要求： 实验内容：本实验求两个集合间的运算，给定两个集合A、B，求集合A与集合B之间的交集、并集、差集、对称差集和笛卡尔乘积。 实验要求：对于给定的集合A、B。用C++/C语言设计一个程序（本实验采用 C++），该程序能够完成两个集合间的各种运算，可根据需要选择输出某种运算结果，也可一次输出所有运算结果。 2、实验算法： 实验算法分为如下几步： （1）、设计整体框架 该程序采取操作、打印分离（求解和输出分开）的思想。即先设计函数求解各部分运算并将相应结果传入数组（所求集合）中，然后根据需要打印运算结果。 （2）、建立一个集合类（Gather） 类体包括的数组a、b、c、d、e、f、g分别存储集合A、B以及所求各种运算的集合。接口（实现操作的函数）包括构造函数，菜单显示函数，求解操作函数，打印各种运算结果等函数。 （3）、设计类体中的接口 构造函数：对对象进行初始化，建立集合A与集合B。 菜单显示函数：设计提示选项，给使用者操作提示。 操作函数：该函数是程序的主题部分，完成对集合的所有运算的求解过程，并将结果弹入（存入）对应数组（集合）中，用于打印。 具体操作如下： 2 1*求交集：根据集合中交集的定义，将数组a、b中元素挨个比较，把共同元素选出来，并存入数组c（交集集合）中，即求得集合A、B的交集。 2*求并集：根据集合中并集的定义，先将数组a中元素依次存入数组g（并集集合）中，存储集合A中某元素前，先将其与已存入g中的元素依次比较，若相同则存入下一个元素，否则直接存入g中，直到所有A中元素存储完毕。接着
计算机专业通知：计算机资料就是同学们网上学习的阶段测试和简答练习等资料，请同学们打印下来复习，如有新的资料更新会通知大家！（以下资料只是网上一部分） 离散数学 一、单项选择题 1、（p∨(q∧r)）→(p∧q∧r)的主析取范式是：（B ） A. ∑(0,1) B. ∑(0,1,7) C. ∑(0,7) D. ∑(1,7) 2、下列是真命题的是（A ） A. 2是素数 B. 2+3=6 C. 雪是黑色的 D. 3能被2整除 3、设P：我们划船，Q：我们跳舞，命题“我们不能既划船又跳舞”符号化为（B ） A. P Q B. ┐（P∧Q） C. ┐P∧┐Q D. ┐P∧Q 4、设谓词P(x):x是奇数,Q(x):x是偶数,谓词公式 x(P(x)Q(x))在哪个个体域中为真 (A) A. 自然数 B. 实数 C. 复数 D. 前面三者均成立 5、当P的真值是1,Q的真值是1 R的真值是0，下列复合命题中真值为0的是（D ） A. （PvQ）→R B. R→(P ? Q) C. (PvR) →Q D. (P ?R)??Q 6、设A=｛1，2，3｝，则下列说法正确的是（C ） A. R={<1,1>，<2，2>，<3，3>，<1,2>}在A上是反自反的 B. R=｛<2，3>，<3，2>｝在A上是自反的 C. R=｛<1，2>，<2，1>，<3，3>在A上是对称的 D. R={<1，2>，<1，3>}在A上是对称的 7、下面关于集合的表示中，正确的是(B )． A. φ＝0 B. φ∈{φ} C. φ∈φ D. φ∈{a，b} 8、设A={?}，B=P（P（A）），以下不正确的式子是（）（分数：1分） A. ．{{? }，{{? }}，{?，{? }}}包含于B B. {{{? }}}包含于B C. {{?，{? }}}包括于B D. {{? }，{{?，{? }}}}包含于B 标准答案是：D。您的答案是： 9、六阶群的子群的阶数可以是（）。（分数：1分） A. 1，2，5 B. 2，4 C. 3，6，7 D. 2，3 标准答案是：D。您的答案是： 10、设G是n个结点、m条边和r个面的连通平面图，则m等于（）。（分数：1分） A. n+r-2 B. n-r+2 C. n-r-2 D. n+r+2 标准答案是：A。您的答案是：
Author ：ssjs Mail ： 看了离散数学中的关系整理了一点关于n 元集合中各种关系的计算，现写下这个方便大家学习交流理解。对文章所致一切后果不负任何责任，请谨慎使用。 如有错误之处请指正。 定义： 1，对称：对于a,b R a b ∈∈∈),b (),a (,A 有如果只要 2，反对称：如果R a b R b a b b ∈∈=∈),(),(a ,A ,a 和时仅当 3，自反：如果对每个元素R ),(A a ∈∈a a 有 4，反自反：如果对于每个R ),(A a ?∈a a 有 5，传递：如果对R ),(,R ),(R ),(,A ,,∈∈∈∈c a c b b a c b a 则且 6，非对称：如果R ),(R ),(?∈a b b a 推出【注】其中是含（a,a)这样的有序对的。 【重要】集合A 的关系是从A 到A 的关系 （也就是说集合A 的关系是A A ?的子集）。 如下结论： N 元集合上的自反关系数为：)1(2 -n n N 元集合上的对称关系数为：2/)1(2+n n N 元集合上的反对称关系数为：2/)1(n 3 2-n n N 元集合上的非对称关系数为：2/)1(3-n n N 元集合上的反自反关系数为：)1(n 2-n N 元集合上的自反和对称关系数为：2/)1(n 2-n N 元集合上的不自反也不反自反关系数为：)1(n n 222 2-?-n 下面是上面结论的计算 1，自反 2A A ,A n n =?=因为也就是说集合A 有n 平方个有序对，由自反定义可知，对R ),(A a ∈∈?a a 有所以n 个有序对()).....3,2,1i X ,X (n i i =其中一定在所求关系中，否则的话此关系就不是自反的了，那么还有n n -2个有序对，所以由集合子集对应二进制串可得自反关系数为)1(n 222--=n n n 下图有助于理解。 （1,1) (2,2).......(n,n) | (1,2) (1,3).........(n-1,n) N n n -2 个有序对
一、已知A、B、C是三个集合，证明(A∪B)－C＝(A－C)∪(B－C) 证明：因为 x∈(A∪B)－C?x∈(A∪B)－C ?x∈(A∪B)∧x?C ?(x∈A∨x∈B)∧x?C ?(x∈A∧x?C)∨(x∈B∧x?C) ?x∈(A－C)∨x∈(B－C) ?x∈(A－C)∪(B－C) 所以，(A∪B)－C＝(A－C)∪(B－C)。 二、设R={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>}，求r(R)、s(R)和t(R)，并作出它们及R的关系图。 解：r(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，1>，<2，2>，<3，3>，<4，4>，<5，5>} s(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<1，2>，<4，2>，<4，3>} R2=R5={<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>} t(R)={<2，1>，<2，5>，<2，4>，<3，4>，<4，4>，<5，2>，<2，2>，<5，1>，<5，4>， <5，5>} 三、证明等价关系 设R是集合A上的一个具有传递和自反性质的关系，T是A上的关系，使得
湖南师范大学硕士研究生入学考试自命题考试大纲 考试科目代码：考试科目名称：离散数学 一、试卷结构 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年
离散数学作业1_集合与关系 1. 设A、B、C为任意三个集合，判断下列命题的真与假。如命题为真，则证明之；否则，举反例说明。 （1）若A?C=B?C，则A=B(假命题) （2）若A?C=B?C ，则A=B(假命题) （3）若A?C=B?C 且A?C=B?C ，则A=B (真命题,参考ppt 1.2节例8) 2.证明A-B=A∩~B. 证明思路：任取x∈A-B?……? x∈A∩~B 证明：任取x∈A-B?x∈A且x/∈B（根据相对补的定义） ? x∈A且x∈~B(根据绝对补的定义) ? x∈A∩~B 3. 设A={1，2，3，4，5，6},下面各式定义的R都是A上的二元关系。试分别以序偶、关系矩阵、关系图三种形式分别写出R。 (1) R={
>,<6,1>,<6,2>,<6,3>,<6,6>} (3) R={<1,2>,<1,3>,<2,1>,<2,3>,<2,4>,<3,2>,<3,4>,<3,1>,<3,5>,<4,3 >,<4,5>,<4,2>,<4,6>,<5,4>,<5,6>,<5,3>,<6,5>,<6,4>} (4) 质数又称素数。指在一个大于1的自然数中，除了1和此整数自身外，不能被其他自然数整除的数。 100以内的质数有2，3，5，7，11，13，17，19，23，29，31，37，41，43，47，53，59，61，67，71，73，79，83，89，97，在100内共有25个质数。 注：1既不是质数也不是合数。因为它的约数有且只有1这一个约数。 R={<2,1>,<3,1>,<4,2>,<5,1>,<6,2>,<6,3>} 4. 设R是A到B的二元关系，证明：对于A的任意子集A1和A2, R(A1∩A2) = R(A1)∩R(A2)当且仅当? a∈A,b∈A,且a≠b有R(a)∩R(b) = Φ. 证明(1)先证充分性（由后推前）即已知 ? a∈A， b∈A ，有R(a)∩R(b) = Φ， 目的是证明对于A的任意子集A1和A2, 有 R(A1∩A2) = R(A1)∩R(A2) （下面通过证明R(A1∩A2) ?R(A1)∩R(A2)，以及R(A1)∩R(A2) ? R(A1∩A2)）
《离散数学》符号表 ? 全称量词（任意量词） ? 存在量词 ├ 断定符（公式在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. 设A={1,2,3,4,5}，R是集合A上的二元关系，aRb当且仅当a
2. 设A={a,b,c}, R={
离散数学作业 作业6 ——等价关系 1. 设R和S均为A上的等价关系，确定下列各式，哪些是A上的等价关系？如果是，证明之；否则，举反例说明。 （1）R∩S （2）R∪S （3）r (R-S) （4）R- S （5）R?S （6）R2 解：(1),(6)正确，其余错误。 2. R是集合A上的二元关系， a,b,c ,若aRb,且bRc,有cRb,则称R是循环关系。证明R是自反和循环的，当且仅当R是一等价关系。 分析: 需要证明两部分: (1)已知R是自反和循环的，证明:R是一等价关系 (2)已知R是一等价关系, 证明R是自反和循环的. 证明：（1）先证必要性。只需要证明R是对陈的和传递的。 任取(x,y)∈R。因为R是自反的，所以(y,y)∈R。由R是循环的可得(y,x)∈R，即R是对陈的。 任取(x,y)，(y,z)∈R。因R是循环的，所以(z,x)∈R。由R对称性得(x,z)∈R，即R是传递的。 （2）证充分性。只需要证明R是循环的。任取(x,y)，(y,z)∈R，下证(z,x)∈R。由于R是传递的，所以(x,z)∈R。又由R是对称的得(z,x)∈R。所以R是循环的。 3. 设|A|=n，在A上可以确定多少个不同的等价关系？ 解：2n!/((n+1)n!n!)
4. 给定集合S={ 1 , 2 , 3, 4, 5 }，找出S 上的等价关系R ，此关系R 能够产生划分{{1，2}，{3}，{4，5}}，并画出关系图。 解：{(1,2),(2,1),(4,5),(5,4)}S R I =? 5. 设A={1，2，3，4，5}。R 是集合A 上的二元关系，其关系矩阵如下图所示。求包含R 的最小等价关系和该等价关系所确定的划分。 ????????????????=0010001000 000000101000001R M 分析: 可以证明tsr(R)是包含R 的最小等价关系. 解：包含R 的最小等价关系的矩阵表示如下： 100000 1010001010 101000101?? ? ? ? ? ? ??? 上述等价关系确定的划分为{{1},{2,4},{3,5}}. 6. 自学华氏(WalShall)算法，写出算法的基本概念、基本步骤和一个 求解传递闭包的具体实例，并可清晰讲解算法整体实现过程。 7. （选做题）设R 与S 是A 上的等价关系，证明： （1）R S 是A 上的等价关系，iff R S=S R ； （2）R ∪S 是A 上的等价关系，if R S ?S 且 S R ?R. 分析: iff 是if and only if 的缩写, 是当且仅当的意思. 证明：（1）先证必要性。任取(x,z)∈R S ，则存在y 使得xRy,ySz 。因为R 与S 是A 上的等价关系，所以R 与S 是对陈的，即yRx,zSy,所以
《离散数学》期末复习提要 《离散数学》是中央电大“数学与数学应用专业”（本科）的一门选修课。该课程使用新的教学大纲，在原有离散数学课程的基础上削减了教学内容（主要是群与环、格与布尔代数这两章及图论的后三节内容），使用的教材为中央电大出版的《离散数学》（刘叙华等编）和《离散数学学习指导书》（虞恩蔚等编）。 离散数学主要研究离散量结构及相互关系，使学生得到良好的数学训练，提高学生抽象思维和逻辑推理能力，为从事计算机的应用提供必要的描述工具和理论基础。其先修课程为：高等数学、线性代数；后续课程为：数据结构、数据库、操作系统、计算机网络等。 课程的主要内容 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 ~~~~???=??? 证明
第一章命题逻辑 1,否定 1) 幂等律 p ∧ p ? p 2) 交换律 p ∧ q ? q ∧ p 3) 结合律（ p ∧q）∧ r ? p ∧ (q ∧ r ) 4) 零律 p ∧ F ? F 5) 同一律 p ∧ T ? p 6) 否定律 p ∧? p ? F 3,析取(+) 1) 幂等律 2) 交换律 3) 结合律 4) 同一律 5) 零律 6) 否定律 7) 吸收律 8) 分配律 9) 德、摩根律 4,蕴含 P→ Q读作“P蕴含Q”，“如果P则Q”，“当P，则Q”，“P是Q的充分条
是Q的充要条件”。 1.1) 交换律 2.2) 结合律 3.说明：1)?是逻辑联结词，而?是公式关系符。A、B是命题，A ?B 仍是命题，而A ? B不是命题。(2) P、Q两命题，没有内在联系 P ?Q 仍有意义。例：2+2=5的充要条件是太阳从西边升起。该命题为真 几个重要定理 ? 1.若A ? B， B ? C，则A ? C.传递性 ? 2. A ? B的充要条件是A ? B且B ? A(逻辑等价的另一种定义） 其他的连接词符号 ?或非词符号 ?定理: A↓B等价于?(AVB) ?定理:{↓}是功能完备集 ?与非词符号 ?定理:A↑B等价于?(A∧B) ?定理:{↑}是功能完备集 ?异或词符号 ?举例说明:周末,我或者在北京或者在上海 ?定理:A异或B等价于?(A?B) 第二章谓词逻辑 谓词演算的推理规则 US 全称指定规则（消去量词） UG 全称推广规则对命题量化（添加量词） ES 存在指定规则（消去量词） EG 存在推广规则（添加量词） 第三章集合 第四章关系 （R ? S） （R·S）2=（R·S）·（R·S）= R·（S·R）·S R-1 ?逆运算的性质 ?定理：设R和S均是A到B的关系，则 ?（1）（R-1）-1=R，
离散数学测验题——集合与关系(2012--2013) 班级学号姓名 注意事项： 1.独立完成，严禁抄袭！满分100分。 2.最迟上交时间：2012年10月31日（星期三）上课之前交齐。过时不交，成绩记为零。 3.在A4大小的纸上完成并装订好。 一、（52分）给定集合A={a, b, c, d}，且A中的关系R： R ={
() ()()2 34() ()()11111111 (11111) 11 1sr R sr R sr R M M M ??????====?????? 故()()*3 () ()()2()...tsr R sr R sr R sr R R M M M M M ∨∨∨==1111111111111 111????? ?=?????? ， 即R *={
├断定符（公式在L中可证） ╞满足符（公式在E上有效，公式在E上可满足）┐命题的“非”运算 ∧命题的“合取”（“与”）运算 ∨命题的“析取”（“或”，“可兼或”）运算 → 命题的“条件”运算 A<=>B 命题A 与B 等价关系 A=>B 命题A与B的蕴涵关系 A* 公式A 的对偶公式 wff 合式公式 iff 当且仅当 ↑ 命题的“与非” 运算（“与非门” ） ↓ 命题的“或非”运算（“或非门” ） □模态词“必然” ◇模态词“可能” φ 空集 ∈属于（??不属于） P（A）集合A的幂集 |A| 集合A的点数 R^2=R○R [R^n=R^(n-1)○R] 关系R的“复合” ∪集合的并运算 ∩集合的交运算
- （～）集合的差运算 〡限制 [X](右下角R) 集合关于关系R的等价类 A/ R 集合A上关于R的商集 [a] 元素a 产生的循环群 I (i大写) 环，理想 Z/(n) 模n的同余类集合 r(R) 关系R的自反闭包 s(R) 关系的对称闭包 CP 命题演绎的定理（CP 规则） EG 存在推广规则（存在量词引入规则） ES 存在量词特指规则（存在量词消去规则）UG 全称推广规则（全称量词引入规则）US 全称特指规则（全称量词消去规则） R 关系 r 相容关系 R○S 关系与关系的复合 domf 函数的定义域（前域） ranf 函数的值域 f:X→Y f是X到Y的函数 GCD(x,y) x,y最大公约数 LCM(x,y) x,y最小公倍数
aH(Ha) H 关于a的左（右）陪集 Ker(f) 同态映射f的核（或称f同态核）[1，n] 1到n的整数集合 d(u,v) 点u与点v间的距离 d(v) 点v的度数 G=(V,E) 点集为V，边集为E的图 W(G) 图G的连通分支数 k(G) 图G的点连通度 △（G) 图G的最大点度 A(G) 图G的邻接矩阵 P(G) 图G的可达矩阵 M(G) 图G的关联矩阵 C 复数集 N 自然数集（包含0在内） N* 正自然数集 P 素数集 Q 有理数集 R 实数集 Z 整数集 Set 集范畴 Top 拓扑空间范畴 Ab 交换群范畴
基本等值式 1.双重否定律A ┐┐A 2.幂等律 A A∨A, A A∧A 3.交换律A∨B B∨A，A∧B B∧A 4.结合律(A∨B)∨C A∨(B∨C) (A∧B)∧C A∧(B∧C) 5.分配律A∨(B∧C) (A∨B)∧(A∨C) （∨对∧的分配律） A∧(B∨C) (A∧B)∨(A∧C) （∧对∨的分配律） 6.德·摩根律┐(A∨B) ┐A∧┐B ┐(A∧B) ┐A∨┐B 7.吸收律A∨(A∧B) A，A∧(A∨B) A 8.零律A∨1 1,A∧0 0 9.同一律A∨0 A，A∧1 A 10.排中律A∨┐A 1 11.矛盾律A∧┐A 0 12.蕴涵等值式A→B ┐A∨B 13.等价等值式AB (A→B)∧(B→A) 14.假言易位A→B ┐B→┐A 15.等价否定等值式AB ┐A┐B 16.归谬论(A→B)∧(A→┐B) ┐A 求给定公式范式的步骤 (1)消去联结词→、(若存在)。 (2)否定号的消去(利用双重否定律)或内移(利用德摩根律)。 (3)利用分配律：利用∧对∨的分配律求析取范式，∨对∧的分配律求合取范式。推理定律--重言蕴含式 (1) A (A∨B) 附加律 (2) (A∧B) A 化简律 (3)(A→B)∧A B 假言推理 (4) (A→B)∧┐B ┐A 拒取式 (5) (A∨B)∧┐B A 析取三段论 (6)(A→B) ∧(B→C) (A→C) 假言三段论 (7)(AB) ∧(BC) (A C) 等价三段论 (8)(A→B)∧(C→D)∧(A∨C) (B∨D) 构造性二难 (A→B)∧(┐A→B)∧(A∨┐A) B 构造性二难(特殊形式) (9)(A→B)∧(C→D)∧(┐B∨┐D) (┐A∨┐C) 破坏性二难 设个体域为有限集D={a1,a2,…,an},则有 （1）xA(x) A(a1)∧A(a2)∧…∧A(an) （2）xA(x) A(a1)∨A(a2)∨…∨A(an) 设A(x)是任意的含自由出现个体变项x的公式，则 （1）┐xA(x) x┐A(x) （2）┐xA(x) x┐A(x) 设A(x)是任意的含自由出现个体变项x的公式，B中不含x的出现，则 （1）x(A(x)∨B) xA(x)∨B