北京大学慕课学习笔记

课程内容

• 集合论
• 图论

集合论的主要内容:

• 研究对象：集合、关系、函数、自然数、基数

• 研究思想：
以逻辑为基础、以集合为工具、表示和构造各种数学对象

• 研究内容：

• 集合的基本概念：集合之间的关系、运算、恒等式
• 二元关系：表示、性质、函数、等价关系、序关系
• 自然数：皮亚诺系统、自然数的运算、性质
• 基数：有穷集与无穷集、基数的比较
• 序数：良序、超限归纳法

图论的主要内容

• 研究对象：由顶点和边构成的图

• 研究思想：
以集合论为基础、以图为工具、为各种二元关系建立模型

• 研究内容：

• 图的基本概念：连通性、矩阵表示、带权图
• 欧拉图、哈密顿图：边和顶点的遍历
• 树：表示层级组织关系
• 平面图：判定、表示、性质
• 图的着色：各种调度问题的模型
• 独立集、支配集、覆盖集、匹配：各种应用问题

集合论的主要模块

集合
基本概念
运算、性质
二元关系
表示、性质
等价关系
序关系
函数
自然数
皮亚诺系统
基数
序数

图论的主要模块

图
基本概念
连通性
欧拉图、哈密顿图
树
图的矩阵表示
平面图
着色
独立支配覆盖匹配
带权图

集合论中的问题

• 如何给集合下定义？
• 如何用集合去定义关系、函数、自然数？
• 如何比较集合的大小？
• 能否把每个集合的元素依次列举出来？
• 有没有最大的集合？

图论中的问题

• 什么是图？有哪些图？图有什么性质？
• 什么是欧拉图？什么是哈密顿图？
• 什么是树？如何用矩阵表示图？
• 什么是平面图？
• 什么是图的着色？
• 什么是支配集、独立集、覆盖、匹配？
• 什么是带权图？

过河问题

• 一个人带着一只狼、一只羊、一棵白菜要过河，小船一次只能容下一个人和一样动植物。人不在场的时候，狼要吃掉羊、羊要吃掉白菜。问应当如何渡河？
• 狼=W，羊=G，白菜=C，人=M
• (CGMW|) - (CW|GM) - (CMW|G) - (W|CGM) -
(GMW|C) - (G|CMW) - (GM|CW) - (|CGMW)

用图来表示问题的解

命题逻辑预备知识

命题逻辑中

– 最基本的逻辑符号、逻辑公式
– 基本的等值式
– 重要的推理定律（重言蕴涵式）

原子命题

用p,q,r,…表示原子命题(简单命题)；
用“1”表示命题的真值为真；
用“0”表示命题的真值为假。