大三上离散数学期末复习提纲

大三上离散数学期末复习提纲

命题逻辑

命题及其表示

具有唯一真值的陈述句称为命题

原子命题：没有联结词的命题

复合命题：有联结词的命题

命题通常使用大写字母P,Q,R等表示

命题变元，命题常元

命题常元如：P:今天下雨

逻辑联结词

  1. 否定

    P非P
    01
    10

  2. 合取

    PQP ^ Q
    000
    010
    100
    111

  3. 析取

    PQP v Q
    000
    011
    101
    111

  4. 条件

    PQP -> Q
    001
    011
    100
    111

  5. 双条件

    PQP ^ Q
    001
    010
    100
    111

命题公式与符号化

单个的命题变元也是命题公式

命题符号化案例

1
2
3
4
张三和李四都是班干部

设 P：张三是班干部，  Q：李四是班干部。
则命题符号化为： P ^ Q

真值表与等价公式

一般，在含有n个命题变元的命题公式中，共有2^n种指派

蕴含式

最小联结词组

范式

推理理论

谓词逻辑

谓词的基本概念

谓词公式与翻译

变元的约束

谓词演算的等价式与蕴含式

谓词公式的范式

谓词演算的推理理论

集合与关系

集合的基本概念

集合的运算

序偶与笛卡尔积

关系及其表示

关系的性质及其判定方法

复合关系和逆运算

关系的闭包运算

等价关系与相融关系

偏序关系

代数系统

代数系统的概念

半群与含幺半群

  • 半群
    • 运算是封闭的
    • 运算是可结合的
  • 含幺半群
    • 运算是可封闭的
    • 运算时可结合的
    • 含有幺元e

群与子群

群

定义（四个条件）

  1. 运算是封闭的

  2. 运算是可结合的

  3. 含有幺元e

  4. 每个成员都含有逆元（成员与逆元运算后的结果为幺元e）

子群

几类特殊的群

  1. 交换群

    运算满足交换律

  2. 循环群

    群中存在一个元素a，使得群中任意元素都是a的幂

    任何一个循环群都是交换群

代数系统的同态与同构

环与域

设X是非空集合，<X,Δ，*>是代数系统，Δ和*都是二元运算。如果：

  1. <X,Δ>是交换群

  2. <X,*>是半群

  3. 运算*对于运算Δ是可分配的

    即任意a,b,c ∈ Z，有 a * (b Δ c) = (a * b) Δ (a * c) 和 (b Δ c) * a = (a * b) Δ (c * a)

    则称<X,Δ,*>是环。在环<X,Δ,*>中，若运算*是可交换的，则称环<X,Δ,*>为交换环，否则称为非交换环。

格与布尔代数

格

任意两个元素都有上、下确界，把具体这种性质的偏序集称为格

图论初步

图的基本概念

定义：一个图G是一个二元组<V,E>，简记G = <V,E>，其中V是一个非空的结点集合，E是边的集合

有向边的关系序偶用<x,y>表示，无向边的关系序偶用(x,y)表示

名词概念
  • 孤立点：不与任何结点邻接的结点称为孤立点（就是只有一个点，没边）
  • 零图：全由孤立点构成的图（就是这个图就只有点，没有边）
  • 平凡图：一阶零图（即零图的一种特殊情况，只有一个点）
  • 有向图：每一条边都是有向边的图
  • 无向图：每一条边都是无向边的图
  • 混合图：既有有向边，又有无向边的图
  • 基础图：将有向图中的有向边的方向去掉，就得到一个无向图，则称得到的无向图为这个有向图的基础图
  • 度：结点所关联的边数称为度d(v)
    • 如果无向图中有自回路则一个回路算2度
    • 出度：d+(v)，+是上标，有向图中分为出度和入度，有多少边出去则有多少出度
    • 入度：d-(v)，-是上标，有多少边进来则有多少入度
  • 奇结点：度数为基数的结点
  • 偶结点：度数为偶数的结点
  • 子图：结点集合包含于原图结点集合，边的集合包含于原图边的集合
  • 生成子图：（支撑子图）结点集合等于原图结点集合，边的集合包含与原图边的集合
  • 导出子图：以图G的顶点集V的非空子集V1为顶点集，以两端点均在V1中的全体边为边集的G的子图，称为V1导出的导出子图
  • 完全图：（无向完全图）任意两个不同结点都是相邻接的，具有n个结点的完全图记作Kn（n为下标）
定理
  1. 如果无向图有m条边，那么它的总度数为2m度
  2. 无向图中奇结点的个数必须为偶数个
  3. 有向图的总出度 = 总入度 = 边数
  4. 最大度数 <= 结点数-1

图的连通性

路与回路

路中边的数目n称为该路的长度

若路的始点与终点相同，则称为回路

如果路中所有边互不相同，则称为迹（或简单路），若回路中的所有边互不相同，则称为简单回路

如果路中所有结点互不相同（当然所有边也互不相同），则称为初级路（或基本路），如果为回路的话，则为初级回路（或圈或基本回路）

图的矩阵表示

邻接矩阵

1
2
3
4
5
6
7
8
9
10
11
设图D＝<V，E>，其中V＝｛v1,v2,v3,v4｝，E＝｛<v¬1,v2>, <v¬2,v3>, <v¬2,v4>, <v3,v2>, <v¬3,v4>, <v¬3,v1>, <v4,v1>｝
邻接矩阵如下，表示结点到结点有多少条长度为1的路径，则可以使用邻接矩阵求出度序列与入度序列
__            __
|  0  1  0  0  |
|  0  0  1  1  |
|  1  1  0  1  |
|  1  0  0  0  |
__            __
出度序列：1,2,3,1
入度序列：2,2,1,2
度序列：3,4,4,3

可达性矩阵

首先求出n阶图的邻接矩阵，然后再求邻接矩阵的次方，如是m次方则代表结点到结点有多少条长度为m的路径，最多求到n次方就会循环

此时将各个邻接矩阵的次方相加，如果元素不为0则变为1，得到的元素只有0,1的矩阵就是可达性矩阵，1表示可达，0表示不可达

欧拉图和哈密顿图

欧拉图

名词概念

  • 欧拉路：每条边走一次的路

  • 欧拉回路：每条边走一次并且回到原点的路

定义：具有欧拉回路的图称为欧拉图

定理
  1. 无向图G具有一条欧拉路当且仅当G是连通的并且有零个或2个奇结点
  2. 一个无向图是欧拉图的充要条件是该图是连通的并且它的结点全是偶结点

哈密顿图

哈密顿路：把图中每个结点走一次且仅走一次的路

哈密顿回路：把图中每个结点走一次且仅走一次能够回到出发结点的路

具有哈密顿回路的图称为哈密顿图

n阶图（n>=3）中每一对不相邻的结点的度的和都>=n，则为哈密顿图

n阶图（n>=3）中每一对结点的度的和都>=n-1，则存在一条哈密顿路，如果每一对结点的度的和>=n，则存在一条哈密顿回路

树

一个连通无回路的无向图称为无向树，简称树，记为T

树中度数为1的结点称为树叶；度数大于1的结点称为分支点（内部结点）

m = n - 1，树的 边数 等于 节点数-1

平面图与欧拉公式

欧拉公式

设G是一个连通平面图，则有n - m + r = 2，其中n,m,r分别是图G的结点数、边数、面数

二部图