前言

 同前面几次数学帖子一样，为密码学在准备。说实话，离散数学我现在仍然不知道，重点讲的啥，可能还需要更深入地学习才行，就此放一放。

第一章 逻辑与谓词

第1节 真假值

 关于非（$\neg$）、 或（析取词，\or）、与（合取词，\and）、异或（\）、的真值表就没什么好写的，下面来看看条件词（$\rightarrow$）以及双条件词（$\leftrightarrow$）。

$P\rightarrow Q$的真值表：

$Q\rightarrow P$的真值表：

 下面来看看永真式和永假式，即无论命题如何变都为真或假。如A\or \neg A为永真式，A\and \neg A为永假式。接下来讲几条定理

• 定理1，永真（假）式的带入实例仍然是永真（假）式。

• 定理2，设P是任意命题变元，$\neg P$与P被称为“一对互补文字”

  • 子句A中至少含有一对互补文字 当且仅当 子句A为永真式
  • 短语A中至少含有一对互补文字 当且仅当 短语A为永假式

  注意：子句是由“或（析取）”组成，短语是由“与（合取）”组成。

第2节 等价与蕴含、范式与对偶式

A、B是两个由若干子命题组成的命题，无论自命题取值如何：A、B命题取值均相等称为等价；A正确则B正确称A蕴含B或者A推出B。

 接下来请自行带入，析取是或、合取是与。以及子句和短语的概念。

析取范式：项式为短语的析取式；合取范式：项式为子句的合取式；

第3节 演绎推理

第4节 谓词与量词

 什么是谓词呢？比如，令P(x)表示“x>3”，那么，这个P就是谓词。我们可以带入P(1)、P(5)等等表示另一个命题。参数的个数代表是几元命题。

 量词：全称量词（任取，$\forall$）和存在量词（存在，$\exist$）

第二章 集合论

第三章 数论

第1节 置换与轮换

 设有限集合$A = \{a_1, a_2, ...,a_n\}$，f是该集合上的一个双射函数，将f的关系表示成$P_f$的形式，则称$P_f$是一个n元置换。

$$P_f = \left( \begin{array}{l} a_1 & a_2 & ... & a_n\\ f(a_1) & f(a_2) &... & f(a_n) \end{array} \right)$$

如果说，$f(a)=a$，那么称a为不变元。

 同样A是一个有限集合，设$\tau = (b_1, b_2,...,b_r)$是A上的一个轮换，那么需要满足下面三条性质：

• $b_1,b_2,...,b_r \in A$，对任意$j=1,2,...,r-1$，有$\tau(b_j) = b_{j+1}$；
• 对$j=r$有$\tau(b_r)=b_1$；
• 对任意$a\in A - \{ b_1, b_2, ...,b_r \}$，有$\tau(a) = a$。

比如：集合$A = \{1,2,3,4,5\}$，下面是几个置换关系，请改成轮换关系。

$$P_{f1} = \left( \begin{array}{l} 1 & 2 & 3 & 4 & 5\\ 4 & 5 & 3 & 2 & 1 \end{array} \right) \\ \\ P_{f2} = \left( \begin{array}{l} 1 & 2 & 3 & 4 & 5\\ 3 & 4 & 5 & 2 & 1 \end{array} \right)\\$$

其对应的轮换关系是：$\tau_1 = (1,4,2,5)$，$\tau_2 = (1,3,5)(4,2)$。

解释：对于$P_{f1}$中，f(1) =4, f(4) = 2, f(2) = 5, f(5) = 1，而f(3) = 3。所以，就是对应的 1,4,2,5

 除此之外，我们先来看看逆序。如果$a_i < a_j$并且$\tau(a_i) > \tau(a_j)$（注意这里的“<”和“>”表示在A中位置的前后），那么这样的记作一个逆序，称$\tau(a_i)$在$a_j$出为逆序。如果逆序数为奇数，称为奇置换；为偶数，称为偶置换。

第四章 算法