§3.3 二元关系的性质与闭包
习题3.3
1. 确定下列整数集合上的关系R 是否是自反的、反自反的、对称的、反对称的和传递的，其中R y x >∈<，，当且仅当 （1）y x ≠
（2）1≥xy
（3）11-=+=y x y x 或
（4）)7(mod y x ≡
（5）2
y x =
（6）2
y x ≥
（7）x 是y 的倍数
（8）x 与y 都是负的或都是非负的
解 （2）、（4）、（6）、（8）略
（1）不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。 （3）不是自反的，是反自反的，是对称的，不是反对称的，不是传递的。 （5）不是自反的，不是反自反的，不是对称的，是反对称的，不是传递的。 （7）是自反的，不是反自反的，不是对称的，是反对称的，是传递的。
2. 设}{d c b a A ，，，=，
（1）给出A 上的一个关系R ，要求R 既不是自反的又不是反自反的； （2）给出A 上的一个关系R ，要求R 既是对称的又是反对称的； （3）给出A 上的一个关系R ，要求R 既不是对称的又不是反对称的； （4）给出A 上的一个关系R ，要求R 是传递的但1
-R R 不是传递的。
解 略
3. 设A 是一个n 元集合，问A 上有多少个关系？这其中又有多少个关系是
（1）对称的？ （2）反对称的？
（3）非对称的？
（4）反自反的？
（5）自反的和对称的？
（6）既不是自反的也不是反自反的？
解 （2）、（4）、（6）略
A 是一个n 元集合，所以A A ?有2
n 个元素，它的子集的个数为2
2n ，所以A 上有2
2n
个关系。
（1）将A A ?中的元素分为三部分：第一部分是n 个> ))((102/)1(2/)1(12/)1(02/)1(n n n n n n n n n n n n C C C C C C ++++++=---- n n n 22 2 /)1(?=-2/)1(2+=n n （2）A 上反对称关系的个数与A 上对称关系的个数相等2 /)1(2+=n n 。 （ 3 ） A 上对称关系的个数为 ))((102/)1(2/)1(1 2 /)1(02/)1(n n n n n n n n n n n n C C C C C C ++++++---- ，其中又是自反的仅为 n n n n n n n n n n C C C C ?+++----)(2/)1(2/)1(12/)1(02/)1( 2/)1(2-=n n 个。 4. 根据下列关系的关系矩阵判断它们是否是自反的？反自反的？对称的？反对称的？ 传递的？并求出相应的关系，画出相应的关系图。 ????? ?????=??????????=??????????=111 111111 011000011 1011110112 13R M M M ，，R R ??????????=??????????=??????????=001 001111 001111110 1101101115 46R M M M ，，R R ??????????=??????????=??????????=111 101110 110111011 1100111018 79R M M M ，，R R ??????????=??????????=??????????=110 011100 101 11001 010******** 1012R M M M ，，R R 解 略 5. 设R 和S 是集合A 上的二元关系，试证表3.2的有关论断，即： （1）当R 和S 是自反的，则S R 、S R 、S R 和1 -R 也是自反的；而c R 和S R -则不一定。 （2）当R 和S 是反自反的，则S R 、S R 、S R -和1 -R 也是反自反的；而c R 和 S R 则不一定。 （3）当R 和S 是对称的，则S R 、S R 、c R 、S R -和1 -R 也是对称的；而S R 则不一定。 （4）当R 和S 是反对称的，则S R 、S R -和1 -R 也是反对称的；而S R 、c R 和 S R 则不一定。 （5）当R 和S 是传递的，则S R 和1 -R 也是传递的。而S R 、c R 、S R -和S R 则不一定。 解 （2）、（4）、（5）略 （1）因为R 和S 是自反的，所以A a ∈?，都有S a a R a a >∈<∧>∈<,,，从而 A a ∈?，都有>∈∈∈∈ 所以他们也是自反的。 而c R 和S R -则不一定是自反的，例如：取集合}{c b a A ，，=及其上的自反关系 },,{><><><><=c c b b b a a a R ，，，，，和},,{><><><=b b b a a a S ，，，，而 },,,,,,,,,{><><><><><=b c a c c b a b c a R c 和},{><=-b a S R 都不是自反的。 （3）因为R 和S 是对称的，所以A b a ∈?,，若R b a >∈<,则R a b >∈<,，若 S b a >∈<,则S a b >∈<,，从而A b a ∈?,，若>∈∈ 若>∈∈∈∈ R ；若 >∈∈∈∈ 是对称的。 而S R 则不一定是对称的，例如：取集合}{c b a A ，，=及其上的对称关系 },,{><><=a b b a R ，和}{><=b b S ，，而},{><=b a S R 不是对称的。 6. 设 } {c b a A ，，=及其上的关系 }{><><><><=c c c b b a a a R ，，，，，，，，求自反闭包)(R r 、对称闭包)(R s 和传 递闭包)(R t 。 解 自反闭包)(R r },,{><><><><><=c c c b b b b a a a ，，，，，， ， 对称闭包)(R s },,,,{><><><><><><=c c b c c b a b b a a a ，，，，，， ， 传递闭包)(R t },,{><><><><><=c a c c c b b a a a ，，，，，， ， 7. 设关系}14334121 {><><><><=，，，，，，，R ，求包含R 的最小关系使得它是 （1）自反的和传递的。 （2）对称的和传递的。 （3）自反的、对称的和传递的。 解 略 8. 根据下列关系的关系矩阵分别求出它们的自反闭包)(R r 、对称闭包)(R s 和传递闭包)(R t 的关系矩阵。 ?? ??? ?????=011000011R M ?? ??? ?????=001111110S M 解 两个关系的闭包的关系矩阵分别如下： ??????????=111010011)(R r M ，?? ????? ???=01110111 1)(R s M ， ????? ?????=011000011)(R t M ?? ????????=101111111)(S r M ， ??????????=011111110 )(S s M ，????? ?????=111111111)(S t M 9. 设R 的关系图如图3.5所示，试给出自反闭包)(R r 、对称闭包)(R s 和传递闭包)(R t 的关系图。 图3.5 习题9的图 解 略 10. 设R 是集合A 上的关系， （1）若R 是自反的，证明)(R s 和)(R t 也是自反的。 （2）若R 是对称的，证明)(R r 和)(R t 也是对称的。 （3）若R 是传递的，证明)(R r 也是传递的。 解 略 11. 设R 和S 是集合A 上的关系，且S R ?，证明 )()(S r R r ?，)()(S s R s ?，)()(S t R t ? 解 略 信息技术与课程整合本栏目责任编辑：贾薇薇离散数学在计算机学科中的应用 陈敏，李泽军 （湖南工学院计算机科学系，湖南衡阳421002） 摘要：离散数学作为有利的数学工具，对计算机的发展与计算机科学的研究起着重大的作用。阐述了离散数学在计算机科学的几个不同领域中的应用，分析了离散数学与计算机专业其他学科间的关系，指出了离散数学在从事计算机及相关科学工作中的重要性。关键词：离散数学；数据结构；编译原理；人工智能 中图分类号：O158,TP305文献标识码：A 文章编号：1009-3044(2009)01-0251-02 The Application of Discrete Mathematics in Computer Science CHEN Min,LI Ze-jun (Department of Computer Science and Technlology,Hunan Insititute of Technology,Hengyang 421002,China) Abstract:Being a helpful mathematical tool,discrete mathematics plays a significant role in the development and research of computer sci -ence.This paper introduces the application of discrete mathematics in different fields of computer science,analyzes the relationship between discrete mathematics and other subjects in computer specialty and points out the importance of discrete mathematics in computer science and related fields. Key words:discrete mathematics;data structure;decoding principles;artificial intelligence 1引言 离散数学是现代数学的一个重要分支，是计算机科学中基础理论的核心课程。它是以研究离散性的结构和相互间的关系为主要目标，其研究对象一般地是有限个或可数个元素。由于计算机科学的迅速发展，与其有关的领域中，提出了许多有关离散量的理论问题，需要用某些数学的工具做出描述和深化[1]。离散数学把计算机科学中所涉及到的研究离散量的数学综合在一起，进行较系统的、全面的论述，为研究计算机科学的相关问题提供了有力的工具。 离散数学课程所涉及的概念、方法和理论，大量地应用在数据结构、数据库系统、编译原理、人工智能、计算机体系结构、算法分析与设计、软件工程、多媒体技术、数字电路、计算机网络等专业课程以及信息管理、信号处理、模式识别、数据加密等相关课程中[2-4]。它所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。这些能力与态度是一切软、硬件计算机科学工作者所不可缺少的，为学习计算机科学的后续课程、从事科研或工程技术工作以及进一步提高科学技术水平奠定理论基础。离散数学提供的营养滋补了计算机科学的众多领域，学好了离散数学就等于掌握了一把开启计算机科学之门不可缺少的钥匙。 2离散数学在数据结构中的应用 计算机要解决一个具体问题，必须运用数据结构知识。对于问题中所处理的数据，必须首先从具体问题中抽象出一个适当的数学模型，然后设计一个解此数学模型的算法，最后编出程序，进行测试、调整直至得到问题的最终解答。而寻求数学模型就是数据结构研究的内容。寻求数学模型的实质是分析问题，从中提取操作的对象，并找出这些操作对象之间含有的关系，然后用数学的语言加以描述。数据结构中将操作对象间的关系分为四类：集合、线性结构、树形结构、图状结构或网状结构。数据结构研究的主要内容是数据的逻辑结构，物理存储结构以及基本运算操作。其中逻辑结构和基本运算操作来源于离散数学中的离散结构和算法思考。离散数学中的集合论、关系、图论、树四个章节就反映了数据结构中四大结构的知识。如集合由元素组成，元素可理解为世上的客观事物。关系是集合的元素之间都存在某种关系。例如雇员与其工资之间的关系。图论是有许多现代应用的古老题目。伟大的瑞士数学家列昂哈德·欧拉在18世纪引进了图论的基本思想，他利用图解决了有名的哥尼斯堡七桥问题。还可以用边上带权值的图来解决诸如寻找交通网络里两城市之间最短通路的问题[5]。而树反映对象之间的关系，如组织机构图、家族图、二进制编码都是以树作为模型来讨论。 3离散数学在数据库中的应用 数据库技术被广泛应用于社会各个领域，关系数据库已经成为数据库的主流，离散数学中的笛卡儿积是一个纯数学理论，是研究关系数据库的一种重要方法，显示出不可替代的作用。不仅为其提供理论和方法上的支持，更重要的是推动了数据库技术的研究和发展。关系数据模型建立在严格的集合代数的基础上，其数据的逻辑结构是一个由行和列组成的二维表来描述关系数据模型。在研究实体集中的域和域之间的可能关系、表结构的确定与设计、关系操作的数据查询和维护功能的实现、关系分解的无损连接性分析、连接依赖等问题都用到二元关系理论[6]。 4离散数学在编译原理中的应用 编译程序是计算机的一个十分复杂的系统程序。一个典型的编译程序一般都含有八个部分：词法分析程序、语法分析程序、语义分析程序、中间代码生成程序、代码优化程序、目标代码生成程序、错误检查和处理程序、各种信息表格的管理程序[7]。离散数学里的计算模型章节里就讲了三种类型的计算模型：文法、有限状态机和图灵机。具体知识有语言和文法、带输出的有限状态机、不带输出的有限状态机、语言的识别、图灵机等。短语结构文法根据产生式类型来分类：0型文法、1型文法、2型文法、3型文法。以上这些收稿日期：2008-12-10 基金项目：“湖南省教育厅教学改革研究项目（湘教通2008第263号） ISSN 1009-3044 Computer Knowledge and Technology 电脑知识与技术 Vol.5,No.1,January 2009,pp.251-252E-mail:kfyj@https://www.doczj.com/doc/c411731289.html, https://www.doczj.com/doc/c411731289.html, Tel:+86-551-56909635690964251 §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 The Foundations: Logic and Proofs（逻辑与证明） 1.1 Propositional Logic（命题逻辑） Propositions（命题）——declarative sentence that is either true or false, but not both.判断性语句，正确性唯一。 Truth Table（真值表） Conjunction（合取，“与”，and），Disjunction（析取，or，“相容或”），Exclusive（异或），Negation（非，not），Biconditional（双条件，双向，if and only if） Translating English Sentences 1.2 Propositional Equivalences（命题等价） Tautology（永真式、重言式），Contradiction（永假式、矛盾式），Contingency（偶然式） Logical Equivalences（逻辑等价）——Compound propositions that have the same truth values in all possible cases are called logical equivalent.（真值表相同的式子，p<->q是重言式） Logical Equivalences——Page24 Disjunctive normal form(DNF，析取范式) Conjunctive normal form(CNF，合取范式) 见Page27～29 1.3 Predicates and Quantifiers（谓词和量词） Predicates——谓词，说明关系、特征的修饰词 Quantifiers——量词 ? Universal Quantifier(全称量词) " 浅论离散数学的实际应用 摘要： 离散数学是现代数学的重要分支，是研究离散量的结构及相互关系的学科，它在计算机理论研究及软、硬件开发的各个领域都有着广泛的应用。作为一门重要的专业基础课，对于我们电子专业的同学来说，学习离散数学史有其重要现实意义：它不仅能为我们的专业课学习打下基础，也为我们今后将要从事的软、硬件开发和应用研究打下坚实的基础，同时也有助于培养我们的抽象思维、严格的逻辑推理和创新能力。离散数学的应用非常广泛，本文主要研究其在我们所学的重要课程中的应用：数字电路中的门电路设计、软件技术基础中的一些技术以及解决现实生活中的一些问题的应用。 关键字：离散数学、电路设计、软件技术、应用 1.什么是离散数学 1.1简介 离散数学(Discrete mathematics)是研究离散量的结构及其相互关系的数学学科，是现代数学的一个重要分支。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。1.2离散数学的内容 离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学的应用遍及现代科学技术的诸多领域，它通常研究的领域包括：数理逻辑、集合论、代数结构、关系论、函数论、图论、组合学、数论等。 2.离散数学在门电路设计中的应用 2.1 逻辑门的概念 逻辑门是集成电路中的基本组件。简单的逻辑门可由晶体管组成。这些晶体管的组合可以使代表两种信号的高低电平在通过它们之后产生高电平或者低电平的信号。高、低电平可以分别代表逻辑上的“真”与“假” 1． ,为上关系，关系图为 下图，则 具有性质（） A ．反自反 B. 对称 C ．反对称 D ．传递 2.给定A={1，2，3，4}，A 上的关系R={(1,3),(1,4),(2,3)，(2,4),(3,4)}满足的性质是 ( )。 A ．自反的 B ．对称的 C ．传递的 D ．不可传递的 3．R={<1,1>,<2,2>,<2,3>,<4,4>},S={<1,1>,<2,2>,<2,3>,<3,2>,<4,4>}。则S 是R 的 对称 闭包。 4、已知集合 {,,}A a b c =，A 上的两个关系：1{,,,,,}R a b a c b c =<><><>， 2{,,,}R a b a a =<><>，则12R R =（ ） 。 A. φ B.{,,,,,}a b a c b c <><><> C.{,,,}a b a c <><> D.{,,,}a b a a < ><> 5.对集合A={1,2,3,4,6,8,12,14}中的整除关系, 画出哈斯图,并写出集合A 中的最大元, 最小元, 极大元, 极小元。 6。集合 }4,3,2,1{=A ，A 上的关系}4,3,3,2,1,2,2,1{><><><><=R ， 求)(R r 、)(R s 、)(R t ，并分别画出它们的关系图。（12分） 解：}4,4,3,3,2,2,1,1{E ><><><><=A } 4,4,3,3,2,2,1,1,4,3,3,2,1,2,2,1{)(><><><><><><><><==A E R R r }3,4,2,3,2,1,1,2{1><><><><=-R }3,4,2,3,4,3,3,2,1,2,2,1{)(1><><><><><><==-R R R s }4,2,2,2,3,1,1,1{2><><><><==R R R }3,2,1,2,4,1,2,1{23><><><><==R R R }4,2,2,2,3,1,1,1{34><><><><==R R R } 4,1,4,2,2,2,3,1,1,1,4,3,3,2,1,2,2,1{)(4 32><><><><><><><><><==R R R R R t …………（9分） )(R r 的关系图1所示： 3 4 1 2 习题1.1 2. 指出下列命题是原子命题还是复合命题。 （3）大雁北回，春天来了。 （4）不是东风压倒西风，就是西风压倒东风。 （5）张三和李四在吵架。 解：（3）和（4）是复合命题，（5）是原子命题。 习题1.2 1. 指出下列命题的真值： （1）若224+>，则太阳从西方升起。 解：该命题真值为T （因为命题的前件为假）。 （3）胎生动物当且仅当是哺乳动物。 解：该命题真值为F （如鸭嘴兽虽是哺乳动物，但不是胎生动物）。 2. 令P ：天气好。Q ：我去公园。请将下列命题符号化。 （2）只要天气好，我就去公园。 （3）只有天气好，我才去公园。 （6）天气好，我去公园。 解：（2）P Q →。 （3）Q P →。 （6）P Q ?。 习题1.3 2. 将下列命题符号化（句中括号内提示的是相应的原子命题的符号表示）： （1）我去新华书店（P ），仅当我有时间（Q ）。 （3）只要努力学习（P ），成绩就会好的（Q ）。 （6）我今天进城（P ），除非下雨（Q ）。 （10）人不犯我（P ），我不犯人（Q ）；人若犯我，我必犯人。 解：（1）P Q →。 （3）P Q →。 （6）Q P ?→。 （10）()()P Q P Q ?→?∧→。 习题1.4 1. 写出下列公式的真值表： （2）()P Q R ∨→。 解：该公式的真值表如下表： 2. 证明下列等价公式： （2）()()()P Q P Q P Q ∨∧?∧???。 证明： ()(()()) ()()) ()() ()() P Q P Q P Q P Q P Q P Q P Q P Q P Q ????∧∨?∧???∧∧??∧???∧∧∨?∨∧?∧ （4）()()()P Q P R P Q R →∧→?→∧。 证明： ()()()() () () P Q P R P Q P R P Q R P Q R →∧→??∨∧?∨??∨∧?→∧ 3. 甲、乙、丙、丁4人参加考试后，有人问他们谁的成绩最好，甲说，不是我。乙说：是丁。丙说：是乙。丁说：不是我。已知4个人的回答只有一个人符合实际，问成绩最好的是谁？ 解：设A ：甲成绩最好。B ：乙成绩最好。C ：丙成绩最好。D ：丁成绩最好。 四个人所说的命题分别用P Q R S 、、、表示，则 P A ??；Q A B C D ??∧?∧?∧；R A B C D ??∧∧?∧?；S D ??。 则只有一人符合实际的命题K 符号化为 ()()()() K P Q R S P Q R S P Q R S P Q R S ?∧?∧?∧?∨?∧∧?∧?∨?∧?∧∧?∨?∧?∧?∧ 第4章 二元关系的基本运算与性质 一、选择题（每题3分） 1、 设A I 为集合A 上的恒等关系，而A 上的关系R 是自反的，1R -为其逆，则必有（ A ） A 、A I R ? B 、1 A R R I -? C 、A R I =? D 、1A R I -=? 2、 设A I 为集合A 上的恒等关系，而A 上的关系R 是反自反的，1R -为其逆，则必有（ C ） A 、A I R ? B 、1 A I R -? C 、A R I =? D 、1 A R R I -= 3、 设A I 为集合A 上的恒等关系，而A 上的关系R 是对称的，1R -为其逆，则必有（ C ） A 、A I R ? B 、1 A I R -? C 、1R R -= D 、1 A R R I -= 4、 设A I 为集合A 上的恒等关系，而A 上的关系R 是反对称的，1R -为其逆，则必有（ D ） A 、A I R ? B 、1 A I R -? C 、1 A I R R -? D 、1 A R R I -? 5、 设A I 为集合A 上的恒等关系，而A 上的关系R 是传递的，1R -为其逆，则必有（ B ） A 、2 R R ? B 、2 R R ? C 、1 R R -= D 、1 A R R I -= 6、设R 是集合A 上的自反关系，则其关系矩阵中主对角线上的元素（ B ） A 、全为0 B 、全为1 C 、不全为0 D 、不全为1 7、设R 是集合A 上的反自反关系，则其关系矩阵中主对角线上的元素（ A ） A 、全为0 B 、全为1 C 、不全为0 D 、不全为1 8、设R 是集合A 上的反对称关系，其关系矩阵中的任一元素为ij a ，当i j ≠时，总有（ D ） A 、ij ji a a = B 、1ij ji a a += C 、0ij ji a a = D 、若1,ij a =则0ji a = 9、非空集合X 上的空关系?不具备的性质是（ A ） A 、自反性 B 、反自反性 C 、对称性 D 、传递性 10、设{1,2,3}A =上的关系R 的关系图如下，则R 不具备的性质为（ A ） A 、自反性 B 、反自反性 C 、反对称性 D 、传递性 11、设R 为{1,2,3}A =上的关系，其关系图如下，则下列为真命题的是（ C ） A 、R 对称，但不反对称 B 、R 反对称，但不对称 C 、R 对称，又反对称 D 、R 不对称，也不反对称 12、设R 为{1,2,3,4}A =上的关系，其关系图如下，则下列为假命题的是（ C ） A 、R 不自反，也不反自反 B 、R 不对称，也不反对称 C 、R 传递 D 、R 不传递 13、{1,2,3,4}A =上的关系{}1 ,3,1,4,2,3,2,4,3,4R =<><><><><> 只不具备（ C ） A 、 反自反性 B 、 反对称性 C 、对称性 D 、传递性 14、设12,R R 是集合A 上的关系，1 1 12,R R --分别为12,R R 的逆，则下列命题错误的是（ D ） A 、1 111212()R R R R ---= B 、111 1212()R R R R ---= C 、1 111212() R R R R ----=- D 、1111212()R R R R ---= 离散数学知识点总结 一、各章复习要求与重点 第一章 集 合 [复习知识点] 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 ρρ 集合与关系《应用离散数学》 第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.3 1. 下列命题公式哪些是析取范式哪些是合取范式？ （1）)()(r q q p ∧∨?∧? （2）)()(q p q p ∨?∧?∨ （3）q r p ∨?∧?)( （4）q q p ?∧∨)( （5）q p ∨? （6）r q p ?∧?∧? （7）p ? （8）q （9）1 （10）0 解 是析取范式的有：(1)、(3)、（5）、（6）、(7)、 (8)、（9）、（10）；是合取范式有：（2）、（4）、（5）、（6）、(7)、 (8)、（9）、（10）。 2. 在下列由3个命题变元r q p 、、组成的命题公式中，指出哪些是标准析取范式哪些是标准合取范式？ （1）)()(r q p r q p ∧∧?∨∧?∧? （2）)()(r q p r q p ∨∨?∧?∨?∨ （3）q r q p ∨?∧?∧?)( （4）)()()(r q r p q p ∨∧?∨?∧∨ （5）r q p ?∨∨? （6）r q p ?∧?∧? （7）1 （8）0 解 是标准析取范式的有：（1）、（6）、（8）；是标准合取范式的有：（2）、（5）、（7）。 3. 找出一个只含命题变元p 、q 和r 的命题公式，当p 和q 为真而r 为假时命题公式为真，否则为假。 解 r q p ?∧∧。 4. 找出一个只含命题变元p 、q 和r 的命题公式，在p 、q 和r 中恰有两个为假时命题公式为真，否则为假。 解 ))()()(r q p r q p r q p ∧?∧?∨?∧∧?∨?∧?∧。 5. 利用等价演算法求下列命题公式的标准析取范式，并求其成真赋值。 （1）)()(p q q p ∨?→→? （2）r q q p ∧∧→?)( （3）)())((r q p r q p ∨∨→∧∨ 解（1） )()(p q q p ∨?→→? )()(p q q p ∨?∨∨?= p q q p ∨?∨?∧?=)( )()()()()(q p q p q p q p q p ∧∨?∧∨?∧?∨?∧∨?∧?= )()()(q p q p q p ∧∨?∧∨?∧?= 习题5.1 1. 下面哪些集合是偏序集？ （1）=><，Z （2）≠><，Z （3）≥><， Z （4）>/<|， Z 解 （1）是偏序集，（2）不是偏序集，（3）是偏序集，（4）不是偏序集 2. 确定由下面的关系图5.6表示的表示的3个关系是否为偏序？并列出这些关系中的所有序偶来进行验证。 解 略 图5.6 习题2的图 3. 确定由下面的关系矩阵表示的关系是否为偏序？ （1）? ? ????? ???100011 101 （2）? ???? ?? ???101010001 （3）??????????????10 11 11000110010 1 解 略 4. 画出在下述集合上的整除关系的哈斯图。 （1）}87654321 {，，，，，，， （2）}131175321 {，，，，，， （3）}483624126321 {，，，，，，， （4）}6432168421 {，，，，，， 解 （1）、（2）的哈斯图如下： （3）、（4）略 5. 在下面偏序集中找出两个不可比的元素。 （1）?><，，， })210{(p （2）><|}86421{，， ，， 解 略 6. ><|}452415953{，，，，，， 是偏序集。 （1）求极大元素和极小元素。 （2）存在最大元素吗？存在最小元素吗？如果存在，请求出。 （3）找出子集}53{，的所有上界。如果它的上确界存在的话，上确界。 （4）找出子集}4515 {，的所有下界。如果它的下确界存在的话，求出下确界。 解 （1）极大元素为9，15，24和45，极小元素为3和5。 （2）不存在最大元素，也不存在最小元素。 （3）子集}53{，的上界有15和45，上确界是15。 （4）子集}4515 {，的下界有3，5和15，下确界是15。 7. ?><，，，，，，，，，，，，，，，，， }}432{}431{}43{}42{}41{}21{}4{}2{}1{{是偏序集。 （1）求极大元素和极小元素。 （2）存在最大元素吗？存在最小元素吗？ （3）找出子集}}4{}2{{， 的所有上界。如果它的上确界存在的话，上确界。 （4）找出子集}}432{}321 {{，，，，，的所有下界。如果它的下确界存在的话，求出下确界。 解 略 8. 给出满足下列性质的偏序集。 （1）有一个极小元素但没有极大元素。 （2）有一个极大元素但没有极小元素。 （3）既没有极大元素也没有极小元素。 解 略 9. 设R 是集合X 上的半序。 （1）证明1 -R R 是等价关系。 （2）定义商集 )/(1 -=R R X Y 上的关系S ：Y D C ∈?，，S D C >∈<，当且仅当在C 、D 中分别存在元素d c 、使得R d c >∈<，。证明S 是商集Y 上的偏序。 解 略 10. 给出下面小写英文字母串的字典序。 离散数学二元关系传递性判别、闭包方法实验报告 学院：理学院班级：11信息与计算科学1班 姓名：***学号：************* 一、实验目的 1. 通过上机程序，进一步加深对二元关系传递性判别，自反闭包，对称闭包，传递闭 包的理解。 2. 掌握传递性判别，Warshall算法。 3. 学会用程序解决离散数学中的问题。 4. 增强我们编写程序的能力 二、实验内容 实验1：二元关系传递性判别 实验2：有限集上给定关系的自反、对称和传递闭包（用Warshall算法）。 三、实验环境 在microsoft visual c++实验环境下完成的，而所设计的程序也在这个环境下通过了编译，运行和测试。 四、实验原理和实现过程 实验1： #include } cout< §4.2 半群与群 习题4.2 1. 设G 是所有形如 ???? ? ?001211 a a 的矩阵组成的集合， *表示矩阵乘法。试问>*<， G 是半群吗？是有么半群吗？这里1211a a 、是实数。 解 任取G 中的2个元素 =A ???? ? ?001211a a 、=B ???? ??001211b b 、 ∵ =*B A ???? ??001211a a ???? ??001211b b ＝???? ??0012111111b a b a G ∈ ∴ >*<，G 是一个代数系统。且因为矩阵的乘法满足结合律，所以>*<， G 是半群。 又因为，只要11a ＝1，则 =*B A ???? ??00 1211 a a *???? ??001211 b b ＝???? ??0012111111b a b a ＝???? ??001211b b B = 对任何的G B ∈成立，即???? ??00112a 是左单位元（不论12a 取什么值）。但右单位元不存在， 因为不论11b ，12b 取什么值， = *B A ???? ??001211a a ???? ??001211b b ＝???? ??0012111111b a b a ＝???? ??001111 a a B = 不可能对任何的G A ∈成立。 所以单位元不存在（事实上，若单位元存在，则左、右单位元都存在且相等还唯一）， 所以>*<，G 不是有么半群。 2. 在正实数集合+ R 上定义运算*如下 ab b a b a ++= *1 试问 >*<+ ，R 是半群吗？是有么半群吗？ 解 略 3. 在自然数集合N 上定义运算∨和∧如下： }max {b a b a ，=∨， }min{b a b a ，=∧ 试问>∨<，N 和>∧<，N 是半群吗？是有么半群吗？ 解 略 4. 设>*<， G 是半群，它有一个左零元θ，令 }|{G x x G ∈*=θθ 证明>*<，θG 构成半群。 解 略 离散数学及应用课后习题答案 【篇一：离散数学及其应用图论部分课后习题答案】 p165:习题九 1、给定下面4个图（前两个为无向图，后两个为有向图）的集合 表示，画出它们的图形表 示。 （1）g1??v1,e1?，v1?{v1,v2,v3,v4,v5}， e1?{(v1,v2),(v2,v3),(v3,v4),(v3,v3),(v4,v5)} （2）g2??v2,e2?， v2?v1，e1?{(v1,v2),(v2,v3),(v3,v4),(v4,v5),(v5,v1)} （3） d1??v3,e3?,v3?v1,e3?{?v1,v2?,?v2,v3?,?v3,v2?,?v4,v5?,?v5,v 1?} （4） d2??v4,e4?,v4?v1,e3?{?v1,v2?,?v2,v5?,?v5,v2?,?v3,v4?,?v4,v 3?} 解答：（1） （2） 10、是否存在具有下列顶点度数的5阶图？若有，则画出一个这样 的图。 （1）5，5，3，2，2；（2）3，3，3，3，2；（3）1，2，3，4，5；（4）4，4，4，4，4 解答：（1）（3）不存在，因为有奇数个 奇度顶点 。 14、设g是n(n?2)阶无向简单图，g是它的补图，已 知?(g)?k1,?(g)?k2，求?(g)， ?(g)。 解答：?(g)?n?1?k2；?(g)?n?1?k1。 15、图9.19中各对图是否同构？若同构，则给出它们顶点之间的双 射函数。 解答： （c）不是同构，从点度既可以看出，一个点度序列为4，3，3，3，3而另外一个为4，4，3，3，1 （d）同构，同构函数为 ?1?2??f(x)??3 ?4???5 解答： （1）三条边一共提供6度；所以点度序列可能是 作业答案：数理逻辑部分 P14：习题一 1、下列句子中，哪些是命题？在是命题的句子中，哪些是简单命题？哪些是真命题？哪些命题的真值现在还不知道？ （3 答：简单命题，真命题。 （9）吸烟请到吸烟室去！ 答：不是命题。 （12）8是偶数的充分必要条件是8能被3整除。 答：复合命题，假命题。 14、讲下列命题符号化。 （6）王强与刘威都学过法语。 答：:p 王强学过法语；:q 刘威学过法语。 符号化为： p q ∧ （10）除非天下大雨，他就乘班车上班。 答：:p 天下大雨；:q 他乘班车上班。 符号化为： p q → （13）“2或4是素数，这是不对的”是不对的。 答：:p 2是素数；:q 4是素数。 符号化为：(())p q ??∨ 15、设:p 2+3=5. :q 大熊猫产在中国。 :r 太阳从西方升起。 求下列复合命题的真值。 （2）(())r p q p →∧?? （4）()(())p q r p q r ∧∧???∨?→ 解答： p 真值为1；q 真值为1；r 真值为0. （2）p q ∧真值为1；()r p q →∧真值为1；p ?真值为0； 所以(())r p q p →∧??真值为0. （4） p q r ∧∧?真值为1，p q ?∨?真值为0，()p q r ?∨?→真值为1； 所以()(())p q r p q r ∧∧???∨?→真值为1. 19、用真值表判断下列公式的类型。 （4）()()p q q p →→?→? 所以为重言式。 )s 所以为可满足式。 P36:习题二 3、用等值演算法判断下列公式的类型，对不是重言式的可满足式，再用真值表法求出其成真赋值。 （1）()p q q ?∧→ 解答： 所以为永假式。 （2）(())()p p q p r →∨∨→ 解答： 所以因为永真式。 （3）()()p q p r ∨→∧ 离散数学在人工智能方面的应用 摘要：离散数学，又称为组合数学。离散数学是计算机出现以后迅速发展起来的一门数学分支。计算机科学就是算法的科学，而计算机所处理的对象是离散的数据，所以离散对象的处理就成了计算机科学的核心，而研究离散对象的科学恰恰就是离散数学。离散数学的发展改变了传统数学中分析和代数占统治地位的局面。它在各学科领域，特别在计算机科学与技术领域有着广泛的应用，同时离散数学也是计算机专业的许多专业课程，如程序设计语言、数据结构、操作系统、编译技术、人工智能、数据库、算法设计与分析、理论计算机科学基础等必不可少的先行课程。人工智能是研究出具有智能行为的计算机系统，这种智能主要体现在计算机的推理能力上，而推理理论主要来自与离散数学。 关键词：离散数学人工智能数理逻辑应用 离散数学是现代数学的一个重要分支，是计算机类专业的重要课程。它以研究离散量的结构及其相互间的关系为主要目标，其研究对象一般是有限个或可数个元素，因此离散数学可以充分描述计算机学科离散性的特点。由于离散数学在计算机科学中的重要作用，国内外几乎所有大学的计算机类专业的教学计划中都将其列为核心课程进行重点建设，它是其他骨干课程，如数据结构、操作系统、人工智能、计算机网络、软件工程、编译原理等的先修课程，国内许多大学将其作为计算机专业类研究生入学考试的内容。 20世纪的计算机出现，带动了世界性的信息革命的伟大进程。计算机科学在信息革命中的学科地位有如牛顿力学在工业革命中的学科地位一样，由计算机出现带动的信息革命当然计算机科学将起着主导的作用。随着信息时代的到来，工业革命时代以微积分为代表的连续数学占主流的地位已经发生了变化，离散数学的重要性逐渐被人们认识。离散数学课程所传授的思想和方法，广泛地体现在计算机科学技术及相关专业的诸领域，从科学计算到信息处理，从理论计算机科学到计算机应用技术，从计算机软件到计算机硬件，从人工智能到认知系统，无不与离散数学密切相关。 离散数学是传统的逻辑学，集合论（包括函数），数论基础，算法设计，组合分析，离散概率，关系理论，图论与树，抽象代数（包括代数系统，群、环、域等），布尔代数，计算模型（语言与自动机）等汇集起来的一门综合学科。离散数学课程主要介绍离散数学的各个分支的基本概念、基本理论和基本方法。这些概念、理论以及方法大量地应用在数字电路、编译原理、数据结构、操作系统、数据库系统、算法的分析与设计、人工智能、计算机网络等专业课程中；同时，该课程所提供的训练十分有益于学生概括抽象能力、逻辑思维能力、归纳构造能力的提高，十分有益于学生严谨、完整、规范的科学态度的培养。 人工智能是计算机学科中一个非常重要的方向,离散数学在人工智能中的应用主要是数理逻辑部分在人工智能中的应用。数理逻辑又称符号逻辑、理论逻辑。它既是数学的一个分支，也是逻辑学的一个分支。是用数学方法研究逻辑或形式逻辑的学科。其研究对象是对证明和计算这两个直观概念进行符号化以后的形式系统。数理逻辑是数学基础的一个不可缺少的组成部分。虽然名称中有逻辑两字，但并不属于单纯逻辑学范畴。数理逻辑在离散数学中包括命题逻辑和谓词逻辑,命题逻辑就是研究以命题为单位进行前提与结论之间的推理, 谓词逻辑在命题逻辑的基础上更加细化了，谓词逻辑主要就是研究句子内在的联系。大家都知道,人工智能共有两个流派,连接主义流派和符号主义流派。其中在符号主义流派里,他们认为 §2.2 谓词公式及其解释 习题2.2 1. 指出下列谓词公式的指导变元、量词辖域、约束变元和自由变元。 （1）))()((y x Q x P x ，→? （2）)()(y x yQ y x xP ，，?→? （3）)())()((z y x xR z y Q y x P y x ，，，，?∨∧?? 解 （1）x ?中的x 是指导变元；量词x ?的辖域是),()(y x Q x P →；x 是约束变元，y 是自由变元。 （2）x ?中的x ，y ?中的y 都是指导变元；x ?的辖域是)(y x P ，，y ?的辖域是 )(y x Q ，；)(y x P ，中的x 是x ?的约束变元，y 是自由变元；)(y x Q ，中的x 是自由变元， y 是y ?的约束变元。 （3）x ?中的x ，y ?中的y 以及x ?中的x 都是指导变元；x ?的辖域是 ))()((z y Q y x P y ，，∧?，y ?的辖域是)()(z y Q y x P ，，∧，x ?的辖域是)(z y x R ，，；)(y x P ，中的x ，y 都是约束变元；)(z y Q ，中的y 是约束变元；z 是自由变元， )(z y x R ，，中的x 为约束变元，y ，z 是自由变元。 2. 设个体域}21{，=D ，请给出两种不同的解释1I 和2I ，使得下面谓词公式在1I 下都是真命题，而在2I 下都是假命题。 （1）))()((x Q x P x →? （2）))()((x Q x P x ∧? 解（1）解释1I ：个体域}21{，=D ，0:)(,0:)(>>x x Q x x P 。 （2）解释2I ：个体域}21{，=D ，2:)(,0:)(>>x x Q x x P 。 3. 对下面的谓词公式，分别给出一个使其为真和为假的解释。 （1）)))()(()((y x R y Q y x P x ，∧?→? （2）)),()()((y x R y Q x P y x →∧?? 解 （1）成真解释：个体域D ＝{1,2,3},0:)(离散数学在计算机学科中的应用
《应用离散数学》方景龙版3.4 等价关系与划分
离散数学及其应用 重要名词中英对应以及重要概念解释与举例
离散数学论文
二元关系、代数系统的一般性质(习题答案)
(完整版)离散数学及其应用(课后习题)
二元关系的基本运算与性质复习题答案
离散数学知识点总结
应用离散数学-集合与关系
《应用离散数学》方景龙版-1.3 命题公式的范式
《应用离散数学》方景龙版-5.1 偏序关系与偏序集
离散数学二元关系传递性判别、闭包方法实验报告
《应用离散数学》方景龙版-4.2 半群与群
离散数学及应用课后习题答案
离散数学及其应用数理逻辑部分课后习题答案
离散数学在人工智能方面的应用
《应用离散数学》方景龙版-2.2 谓词公式及其解释
相关主题
文本预览