离散数学

李静、段冬燕、王凤玲

目录

  • 1 集合论
    • 1.1 集合的基本概念
    • 1.2 集合运算与幂集
    • 1.3 关系的预备知识和关系的基本概念
    • 1.4 关系运算与关系的性质
    • 1.5 关系的闭包运算
    • 1.6 次序关系
    • 1.7 等价关系
    • 1.8 函数
    • 1.9 知识拓展
  • 2 图论
    • 2.1 图的基本概念
    • 2.2 图的通路、回路与连通性
    • 2.3 图的矩阵表示法
    • 2.4 树
    • 2.5 一些特殊的图（一） (选读)
    • 2.6 一些特殊的图（二）（选读）
  • 3 数理逻辑
    • 3.1 命题及其联结词
    • 3.2 命题公式及其分类、真值表
    • 3.3 命题逻辑的等值演算
    • 3.4 命题逻辑的基本蕴含式及蕴含推理
    • 3.5 范式
    • 3.6 谓词与量词（选学）
    • 3.7 谓词公式及分类（选学）
    • 3.8 自然语句形式化（选学）
    • 3.9 谓词逻辑的等值演算（选学）
    • 3.10 前束范式（选学）
    • 3.11 谓词逻辑的推理（选学）
  • 4 代数系统
    • 4.1 代数系统的一般概念和常用性质
    • 4.2 代数系统的一般概念和常见性质
    • 4.3 同构
    • 4.4 同构与同态
    • 4.5 同态
    • 4.6 群的基本概念
    • 4.7 循环群与子群
    • 4.8 几个典型的代数系统（一）
    • 4.9 几个典型的代数系统（二）
知识拓展
  • 1 集合的计算机表示
  • 2 数学家简介
  • 3 计算机科学中的常...
  • 4 关系传递性的判定...
  • 5 偏序关系的应用

集合的计算机表示

计算机表示集合的方式有多种。一种办法是把集合的元素无序地存储起来。可是如果这样的话，再进行集合的并集、交集或差集等运算时会非常费时，因为这些运算将需要进行大量的元素搜索。我们将介绍一种利用全集中元素的任何一种顺序来存放集合元素的方法。集合的这种表示法使我们很容易计算集合的各种组合。

假定全集E是有限的（而且大小合适，使E得元素个数不超过计算机能使用的内存量）。首先为E的元素任意规定一个顺序，例如a1,a2,…,an。于是可以用长度为n的位串来表示E的子集A：其中位串中第i位是1，如果ai属于A；是0，如果ai不属于A。我们用例1阐明这一方法。

例1  令E={1,2,3,4,5,6,7,8,9,10}，而且E的元素以升序排序，即ai=i。表示E中所有奇数的集合、所有偶数的集合和不超过5的整数的集合的位串是什么？

解：表示E中所有奇数的集合{1,3,5,7,9}的位串，其第1、3、5、7、9位为1，其他位为0.即

10 1010 1010

（我们把长度为10的位串分成长度为4的片段组合以便阅读）。

类似地，E中所有偶数的集合，即{2,4,6,8,10}的位串为

01 0101 0101

E中不超过5的所有整数的集合，即{1,2,3,4,5}的位串为

                           11 1110 0000

结论：用位串表示集合便于计算集合的并集、交集、差集、补集。

①　要从表示集合的位串计算它的补集的位串，只需简单地把每个1改为0，每个0改为1。

②　要想得到两个集合的并集和交集的位串，只需对这两个集合的位串按位做布尔运算即可。