离散数学教程四川大学出版个人整理
总评
整理开始日期:2017-06-21
整理结束日期:2017-06-22
第1章 命题逻辑
~ 否定命题
∧ 合取命题 and
∨ 析取命题 or
→ 条件命题
P→ Q = ~P∨ Q
P↑ Q = ~(P∧ Q)
P↓ Q = ~(P∨ Q)
T 永真式 重言式 可满足公式
F 不可满足公式
不同取值让不同命题有相同结果 则 命题等价
子公式等价替换后保持等价A(A1)=A(A2) 如果A1=A2
可互推则双条件命题为永真
A*与 A处处真值表为反为A的对偶式
$A\cup B={x\in A\bigvee x\in B}$
析取 子句
合取 合取范式
凡不是永真的，命题公式都存在与之等价的主合取范式
CP规则
右箭头上加c表示推的否定
第2章 一阶谓词逻辑
A是人 PEOPLE(A)
x大于y GREATER-THAN(x,y)
∀ 任意
∃ 存在
(∀ x)P(x) = (∃ x)[P(x)]
(∃ x)P(x) = (∀ x)[P(x)]
Skolem 将合取范式的所有存在用函数与任意进行替换(∀ x)(∀ y)(∃ z)P(z) = (∀ x)(∀ y)P(f(x,y))
∃ x ∀ y → ∀ y ∃ x
第3章 集合及其运算
$A\cup B={x\in A\bigvee x\in B}$
$A\cap B={x\in A\bigwedge x\in B}$
$A\bigoplus B={x\in A - B\bigvee x\in B - A}$
2^A={ X | X \subseteq A}$
运算$\times$为集合的直径 不满足交换律 结合律
形式语言
第4章 初等数论和证明方法
n=d×k -> d | n
最大公因子gcd，最小公倍数lcm
数学归纳法
第5章 二元关系
R 关系 {(A的元素,B的元素)} 也可以画成矩阵表示
性质(自反 对称 可传递)对应的现象({(x,x)} {(x,y)(y,x)} {(x,y) (y,z) (x,z)})
关系的运算 $\cup \cap \bigoplus$
同时有 自反 对称 可传递 为等价关系
同时有 自反 反对称 传递 为偏序关系 如整除，有最小值的偏序集为良序
第6章 函数
f: X→ Y
单射、满射、双射
$\pi_1\circ \pi_2 = \pi_1(\pi_2())$
循环的积
与自然数集N等势的为可数集
集合的基数card()
阿列夫 =。=
f(x)=O(g(x))不能写成O(g(x))=f(x) 表示f(x)的上界,f(x) <=M |g(x)|
第7章 基本计数方法
排列计数，组合计数
圆排列！！
组合恒等式!!!
容斥原理
抽屉原理/鸽巢原理
第8章 生成函数和递推关系
定义 生成函数!!!!!!!!!!!!! (排列的生成函数 组合的生成函数)
递推关系及其解 差分方程
递推关系和生成函数 6666666
第9章 无向图和有向图
V为节点 E为边 度 sum(每个点度)=2倍边数
G(V,E)
定义…
图的矩阵表示
独立集 点团 极图，布尔表达式 析取范式，诱导子图？？
图的着色？？
第10章 基本图类和算法
树与生成树
每个连通图都含有生成树，图的任何割集至少与树有一个公共边，图的圈至少与树有一个公共边
如果有向图G的图是树，则称G为有向树
平面图(画为平面图可以让连线没有额外焦点)和对偶图
面数为f的连通平面图G(n,m) 有n-m+f=2
阶数大于2的(n,m)连通平面图 m<=3n-6,至少存在一个度不超过5的结点
Kuratowski 定理
欧拉图及其应用
哈密顿图及其应用
图的匹配与匈牙利算法
网络无环又有向权图
第11章 群和环
群 环 域 格 和 布尔代数是典型的系统
运算与代数系统
集合的二元运算 封闭的 可交换的 可结合的 可分配的 吸收率
常见的代数系统 $<Z,+>$,$<Q,+,*>$
封闭 广群
广群+可结合 半群
群 和 子群
群=有逆元的含幺半群
群的运算满足交换律则为交换群/Abel群 充要条件 $a,b \in G, (a\cdot b)^2=a^2\cdot b^2$
陪集与拉格朗日定理
同态与同构
环和域
群码
第12章 格与布尔代数
格 交换 结合 吸收
格的性质和同态，逆关系 互为 对偶
分配格和有补格
格+分配+有界+有补 = 布尔格