离散数学

离散数学 笔记

1.3

1.合取式 and 析取式
2.逻辑运算整理

与非（NAND）：有假即真，无假即假。
或非 (NOR)：只有两个命题在同时为假时才为真
异或（exclusive-or XOR）：不同为1，相同为0

3.逻辑运算符 | 不满足结合律

1.4

1.前置条件和后置条件：描述合法输入的语句叫做前置条件，程序运行输出应该满足条件称为后置条件
2.全称量化和合取式等价
$\forall xP(x) \equiv P(x_1)\land P(x_2)\land P(x_3)\land ...\land P(x_n)$
3.存在量化$\exists xP(x)$与析取式$P(x_1)\lor P(x_2)\lor P(x_3)\lor ...\lor P(x_n)$
4.全称量化的约束和一个条件语句的全称量化等价
$\forall x < (x^2>0)\equiv\forall x(x<0\to x^2>0)$
存在量化的约束和一个合取士的存在量化等价
$\exists z>0(z^2=2)\equiv\exists(z>0\land z^2 =2)$
5.量词的德·摩根律

• $\lnot\forall xP(x)\equiv \exists x\lnot P(x)$
• $\lnot\exists xP(x)\equiv \forall x\lnot P(x)$

6.一些结论

• $\exists x(P(x)\lor Q(x))\equiv\exists xP(x)\lor \exists xQ(x)$
• $\forall x(P(x)\land Q(x))\equiv\foralāl xP(x)\land \exists xQ(x)$
• $\forall xP(x)\land \exists xQ(x)\equiv \forall x\exists y(P(x)\land Q(y))$
• $\forall xP(x)\lor \exists xQ(x)\equiv \forall x\exists y(P(x)\lor Q(y))$
  
  • 助记：合并量词，同逻辑
• $(p\land \lnot q )\lor q\equiv (p\lor q)$
  
  • 助记：括号内外，析合取相反，有一相反命题，消除括号外的命题。

7.蕴含的符号:A蕴含B,记为"A→B"

8.空量化规则的一些结论

$\forall x (A(x)\lor B) \Longleftrightarrow \forall xA(x)\lor B$
$\forall x (A(x)\land B) \Longleftrightarrow \forall xA(x)\land B$

$\forall x (A(x)\to B) \Longleftrightarrow \exists xA(x)\to B$

$\forall x (B \to A(x) ) \Longleftrightarrow B\to \forall xA(x)$

$\exists x (A(x)\lor B) \Longleftrightarrow \exists xA(x)\lor B$

$\exists x (A(x)\land B) \Longleftrightarrow \exists xA(x)\land B$

$\exists x (A(x)\to B) \Longleftrightarrow \forall xA(x)\to B$

$\exists x (B \to A(x)) \Longleftrightarrow B\to \exists xA(x)$
9.量词分配等值式
$\forall x(A(x)\land B(x)) \Longleftrightarrow \forall xA(x)\land \forall xB(x)$
$\exists x(A(x)\lor B(x)) \Longleftrightarrow \exists xA(x)\lor \exists xB(x)$

助记，$\forall$不能$\lor$,$\exists$不能$\land$

1.6

1.推理规则

2.肯定结论的谬误
$((p\to q)\land q)\to p$

1.7

1.归谬法是（$p\to q$）先将结论否定$\lnot q$，然后（$p\land q \equiv F$）
2.反证法的原理是 $p\to q \equiv \lnot q \to \lnot p$

1.8

助记 交叉
文字：原子命题及其否定式统称为文字（形）。

1.概念

• 简单析取式：有限个命题变元或命题变元的否定式构成的析取式
• 简单合取式: 有限个命题变元或命题变元的否定式构成的合取式
• 重言式： 永真式
• 矛盾式： 永假式
• 析取范式： 由有限个合取式构成的析取式
• 合取范式： 由有限个析取式构成的合取式
• 一般公式的析取/合取范式：若A是一个公式，B是一个析取/合取范式，A$\equiv$B则称B是A的一个析取/合取范式
• 公式的极小项 形如$P_1 \land P_2 \land ...\land P_3$的简单合取式，其中包含公式中所有的命题变元极其否定式
• 公式的极大项：参考极小项的定义
• 主析取范式：A是公式，B是A的一个析取范式，若B中的每个简单合取式都是极小项，则称B是A的一个主析取范式
• 主合取范式： 参考主析取范式的定义

注意：
+ 每个极小项的编号即使使其真值为1的赋值说构成的二进制数或十进制数

2.定理

• 对于任何一个命题公式，都存在与之等值的析取范式和合取范式
• 任何命题公司都存在与其等值的的主析取范式和主合取范式，并且公式的主析取范式和主合取范式的唯一。

2.2集合运算

证明集合相等的一种方法是证明每一个是另一个的子集

2.3函数

函数的定义，参照课本
令A和B为非空集合。从A到B的函数f是对元素的一种指派，对A的每个元素敲好指派B的一个元素。如果B中元素b是唯一有函数f指派给A中元素a的，则我们就写成f(a) = b。如果f是从A到B的函数，就写成$f:A\to B$。

取整函数性质

单射、满射、双射

单射：$\forall a\forall b(f(a)=f(b)\to a=b)$
满射：对每个$b\in B$有元素$a\in A$使得f(a) = b，（就是培域中所有元素在定义域中都有元素对应。）
即是$\forall y\exists x(f(x) = y)$
例题
$f:N\to N,f(x) = (x)mod3$,
f(x),既不单射，也不满射，因为f（x）的培域不是{0,1,2,3}
双射：单射且满射

自然映射

设R是A上的等价关系，令 g：A$\to$A/R ，g(a)=[A]$_R$ ，则称g为从A到商集A/R的典型映射或自然映射。
　　一般说来，自然映射函数均为满射的，但当等价关系R不是恒等关系时，自然映射均不是单射的。严格单调函数（严格单调递增或严格单调递减的函数统称为严格单调函数）是单射的。
例9: 设A={1,2,3}, R是A上的等价关系, 它诱导的等价类是{1,2},{3} 则从A到A/R的自然映射g为:
　　　g:{1,2,3}→{{1,2},{3}},
　　　g(1)={1,2},g(2)={1,2},g(3)={3}.

3.算法

1.在每一步都选择最好的选项称为“贪婪算法”
2.f(x)是O(g(x))的事实有时写作f(x)=O(g(x))
O(g(x))可以表示那些事O(g(x))函数的集合

3.当使用大O记号时，在f(x）是O（g（x））这一关系中函数g的选择应该尽可能的小

4数论与密码学

除法定义：把a|b表示成$(\exists c(ac=b))$,其中论语是整数集合。
定理2 ** 整数除法** 令a为整数，d为正整数，则存在唯一的整数q和r，满足$0\leq r <d$,使得a = dq + r

定理三 $a\equiv b(mod\;m)$当且仅当a mod m = b mod m
定理四 令m为正整数。整数a和b是模m同余的当且仅当存在整数k使得 a = b +km
定理五 说明加法和乘法是同余的
推论二

模m算术

性质：封闭性、结合律、交换律、单位元、加法逆元、分配律。

关系(relation)

关系R是反对称的当且仅当不存在由不同元素a和b构成的有序对，使得a与b有关系并且b与a也有关系。
非对称的关系一定是反对称的，反对称关系不一定是非对称的。非对称一定反自反。

递推方程

见教材P436
cnm，他喵的忙的都不知道自己在干什么了。

等价关系

等价类

如果R是定义在集合A上的等价关系，则元素a的等价类，则元素a的等价类$[a]_R = \{s|(a,s)\in R\}$
代表元，选择特定元素作为一个类的代表元并没有什么特殊的要求。

等价类的划分

集合S的划分是S的不相交的非空子集构成的集合。

商集

（小）书上 第七章P125 定义 7.17
可以认为全集是商集的广义概念.

偏序集

注意偏序关系使非空集合A上的自反、反对称和传递的关系。
注意最大元和最小元，是对于任意。
若一个元素与其他任何元素没有关系，则判定为极小元（极大元）

上界和下界，注意定义中$a\in S$

拓扑排序

在扩张成全序关系时，原来偏序集中不可比的元素之间的次序可以任意确定。这也是出现多个结果的原因。

有重复的排列

当元素被允许重复是，使用乘积法则可以很容易技术排列数。
定理：设定类型1的相同的无题有$n_1$个，类型2的相同的无题有$n_2$个，···，类型k的相同无题有$n_k$个，那么n个物体的不同排列数是

有重复的组合

定理: n个元素的集合中允许重复的r组合有C(n+r-1,r) = C(n+r-1,n-1)个。

递推方程

一阶的递推方程$a_n = f(a_{n-1})$转化为等差或等比数列求解。
二阶用特征方程法。

常系数线性齐次递推方程求解

定义：

常系数线性非齐次递推方程

图

以下三个问题能够帮助我们解决图的结构

• 图的边是有向的还是无向的（还是两者皆有）？

• 如果是无向图，是否存在链接相同顶点的多重边？如果是有向图，是否存在多重有向边？

• 是否存在环

  图的术语

  $N(A)$表示图G中至少和A中一个顶点相邻的所有顶点的集合。 所以N(A)=

  二分图

  图着色定理

  一个简单图是二分图，当且仅当能够对图中的每个顶点赋予两种不同的颜色，并使得两个相邻的顶点被赋予相同的颜色。

  霍尔婚姻定理

  带有二部划分($V_1,V_2$)的二分图G = (V,E)中有一个从$V_1$到$V_2$的完全匹配当期仅当对于$V_1$的所有子集A，有|N(A)|>=|A|。