离散数学（上）概念及公式

BUPT 离散数学（上）课程（计算机学院）涉及的概念和公式，自制

概念

第一章

英文	中文
proposition	命题
propositional variable	命题变元
truth value	真值
logical operators	逻辑运算符
compound propositions	复合命题
negation	否定
truth table	真值表
connective	联结词
conjunction	合取
disjunction	析取
exclusive or	异或
hypothesis	假设
antecedent	前件
premise	前提
conclusion	结论
consequence	后件
implication	蕴含
converse	逆命题
contrapositive	逆否命题
inverse	否命题
equivalent	等价的
biconditional	双条件
bi-implication	双向蕴含
bit	位
Boolean variable	布尔变量
bit operation	位运算
bit string	位串
bitwise operations	按位运算
logic gate	逻辑门
logic circuit	逻辑电路
consistent	一致的
tautology	永真式
contradiction	永假式
contingency	可能式
satisfiable	可满足的
normal form	范式
principal conjunctive normal form	主合取范式
principal disjunctive normal form	主析取范式
predicate	谓词
propositional function	命题函数
n-ary predicate	n 元谓词
precondition	前置条件
postcondition	后置条件
quantification	量化
domain of discourse	论域
universe of discourse	全体域
universal quantification	全称量化
universal quantifier	全称量词
counterexample	反例
existential quantification	存在量化
existential quantifier	存在量词
uniqueness quantifier	唯一性量词
bound	约束的
free	自由的
scope	作用域
nested quantifier	嵌套量词
prenex normal form	前束范式
argument	论证
valid	有效性
fallacy	谬误
argument form	论证形式
rule of inference	推理准则
proof	证明
formal proofs	形式化证明
informal proofs	非形式化证明
theorem	定理
fact	事实
result	结论
axiom	公理
lemma	引理
corollary	推论
conjecture	猜想
vacuous proof	空证明
trivial proof	平凡证明
direct proof	直接证明法
proof by contraposition	反证法
proof by contradiction	归谬证明法
exhaustive proof	穷举证明法
proof by cases	分情形证明法
without loss of generality	不失一般性
constructive existence proof	构造性的存在性证明
nonconstructive existence proof	非构造性的存在性证明
rational number	有理数
uniqueness proof	唯一性证明

第二章

英文	中文
set	集合
element	元素
member	成员
contain	包含
roster method	花名册方法
set builder	集合构造器
interval	区间
closed interval	闭区间
open interval	开区间
empty set	空集
null set	空集
singleton set	单元素集合
naive set theory	朴素集合论
universal set	全集
subset	子集
proper subset	真子集
finite	有限的
cardinality	基数
infinite	无限的
power set	幂集
ordered n-tuple	有序 n 元组
ordered pair	序偶
Cartesian product	笛卡尔积
relation	关系
truth set	真值集
the union of sets	集合的并集
the intersection of sets	集合的交集
disjoint	不相交的
principle of inclusion-exclusion	容斥原理
the difference of sets	集合的差集
the symmetric difference of sets	集合的对称差
the complement of set	集合的补集
membership tables	成员表
function	函数
mapping	映射
transformation	变换
domain	定义域
codomain	陪域
image	像
preimage	原像
range	值域
real-valued function	实值函数
integer-valued function	整数值函数
one-to-one	一对一
injection	单射函数
injective	单射的
increasing	递增的
strictly increasing	严格递增的
decreasing	递减的
strictly decreasing	严格递减的
onto	映上
surjection	满射函数
surjective	满射的
one-to-one correspondance	一一对应
bijection	双射函数
bijective	双射的
identity function	恒等函数
inverse function	反函数
invertible	可逆的
composition	复合
floor function	下取整函数
ceiling function	上取整函数
partial function	部分函数
total function	全函数
geometric progression	几何级数，等比数列
arithmetic progression	算术级数，等差数列
sequence	序列
term	项
recurrence relation	递推关系
summation	求和
countable	可数的
uncountable	不可数的
matrix	矩阵
square	方阵
row	行
column	列
identity matrix	单位矩阵
transpose	转置
symmetric	对称的
the join of matrices	01 矩阵的并
the meet of matrices	01 矩阵的交
Boolean product	布尔积
Boolean power	布尔幂

第三章

英文	中文
algorithm	算法
pseudocode	伪代码
input	输入
output	输出
definiteness	确定性
correctness	正确性
finiteness	有限性
effectiveness	有效性
generality	通用性
searching problem	搜索问题
linear search	线性搜索
binary search	二分搜索
sorting	排序
bubble sort	冒泡排序
insert sort	插入排序
optimization problem	最优化问题
greedy algorithm	贪婪算法
halting problem	停机问题
big-O notation	大 O 记号
witness	凭证
same order	同阶的
big-Omega notation	大\(\Omega\)记号
big-Theta notation	大\(\Theta\)记号
computational complexity	计算复杂度
time complexity	时间复杂度
worst-case complexity	最坏情形复杂度
average-case complexity	平均情形复杂度
algorithmic paradigm	算法范型
brute-force algorithm	蛮力算法
constant complexity	常量复杂度
linear complexity	线性复杂度
logarithmic complexity	对数复杂度
linearithmic complexity	线性对数复杂度
polynomial complexity	多项式复杂度
exponential complexity	指数复杂度
factorial complexity	阶乘复杂度
tractability	易解性
tractable	易解的
intractable	难解的
solvable	可解的
unsolvable	不可解的

第四章

英文	中文
division	除法
a divides b	a 整除 b
factor	因子
divisor	除数
multiple	倍数
dividend	被除数
quotient	商
remainder	余数
a is congruent to b modulo m	a 模 m 同余 b
congruence	同余式
modulus	模
congruence class	同余类
arithmetic modulo m	模 m 算术
base b expansion of n	n 的 b 进制展开式
decimal expansions	十进制展开式
binary expansions	二进制展开式
octal expansions	八进制展开式
hexadecimal expansions	十六进制展开式
modular exponentiation	模指数运算
prime	素数
composite	合数
trial division	试除法
the sieve of Eratosthenes	埃拉托斯特尼筛法
greatest common divisor	最大公约数
relatively prime	互质
pairwise relatively prime	两两互质
least common multiple	最小公倍数
Euclidean algorithm	欧几里得算法
Bézout's theorm	贝祖定理
Bézout coefficients	贝祖系数
inverse of a modulo m	a 模 m 的逆
linear congruence	线性同余方程
the Chinese remainder theorem	中国剩余定理
Fermat’s little theorem	费马小定理
pseudoprime	伪素数
primitive root	原根
discrete logarithm	离散对数
hashing function	散列函数
collision	冲突
linear probing function	线性探测函数
pseudorandom numbers	伪随机数
linear congruential method	线性同余法
encryption	加密
key	密钥
shift cipher	移位密码
affine cipher	仿射密码
character cipher	字符密码
block ciphers	分组密码
transposition cipher	换位密码
cryptosystem	密码系统
plaintext strings	明文串
ciphertext strings	密文串
keyspace	密钥空间
encryption functions	加密函数
decryption functions	解密函数

第五章

英文	中文
mathematical induction	数学归纳法
basis step	基础步骤
inductive step	归纳步骤
strong induction	强归纳法
second principle of mathematical induction	数学归纳法第二原理
well-ordering property	良序性公理
recursive definition	递归定义
inductive definition	归纳定义
well defined	良定义的
Lamé's Theorem	拉梅定理

第六章

英文	中文
the product rule	乘法法则
the sum rule	加法法则
the subtraction rule	减法法则
the division rule	除法法则
the pigeonhole principle	鸽巢原理
permutation	排列
combination	组合
binomial coefficient	二项式系数

公式

第一章

卡片正面	卡片背面
同一律	\[\begin{align*}&P\wedge T\Leftrightarrow P \\ &P\vee F\Leftrightarrow P\end{align*}\]
零律	\[\begin{align*}&P\vee T\Leftrightarrow T \\ &P\wedge F\Leftrightarrow F\end{align*}\]
等幂律	\[\begin{align*}&P\wedge P\Leftrightarrow P \\& P\vee P\Leftrightarrow P\end{align*}\]
双重否定律	\[\neg(\neg P))\Leftrightarrow P\]
交换律	\[\begin{align*}&P\wedge Q\Leftrightarrow Q\wedge P \\& P\vee Q\Leftrightarrow Q\vee P\end{align*}\]
结合律	\[\begin{align*}&(P\vee Q)\vee R\Leftrightarrow P\vee(Q\vee R) \\& (P\wedge Q)\wedge R\Leftrightarrow P\wedge(Q\wedge R)\end{align*}\]
分配律	\[\begin{align*}&P\wedge(Q\vee R)\Leftrightarrow (P\wedge Q)\vee(P\wedge R) \\& P\vee(Q\wedge R)\Leftrightarrow (P\vee Q)\wedge(P\vee R)\end{align*}\]
德摩根律	\[\begin{align*}&\neg(P\wedge Q)\Leftrightarrow \neg P\vee\neg Q \\& \neg(P\vee Q)\Leftrightarrow \neg P\wedge\neg Q\end{align*}\]
蕴含等价式	\[P\rightarrow Q\Leftrightarrow \neg P\vee Q\]
排中律	\[P\vee\neg P\Leftrightarrow T\]
矛盾律	\[P\wedge\neg P\Leftrightarrow F\]
双向蕴含等价式	\[P\leftrightarrow Q\Leftrightarrow (P\rightarrow Q)\wedge(Q\rightarrow P)\Leftrightarrow\neg(P\oplus Q)\]
归谬论	\[(P\rightarrow Q)\wedge(P\rightarrow\neg Q)\Leftrightarrow \neg P\]
蕴含逆反式	\[P\rightarrow Q\Leftrightarrow \neg Q\rightarrow\neg P\]
吸收律	\[\begin{align*}&P\vee(P\wedge Q)\Leftrightarrow P \\ &P\wedge(P\vee Q)\Leftrightarrow P\end{align*}\]
输出律	\[(P\wedge Q)\rightarrow R\Leftrightarrow P\rightarrow(Q\rightarrow R)\]
异或等价式	\[P\oplus Q\Leftrightarrow (P\vee Q)\wedge\neg(P\wedge Q)\Leftrightarrow(P\wedge\neg Q)\vee(Q\wedge\neg P)\]
量词的德摩根律	\[\begin{align*}&\neg\exists xP(x)\Leftrightarrow \forall x\neg P(x) \\& \neg\forall xP(x)\Leftrightarrow \exists x\neg P(x)\end{align*}\]
嵌套量词的交换律	\[\begin{align*}&\forall x\forall yP(x,y)\Leftrightarrow\forall y\forall xP(x,y) \\ &\exists x\exists yP(x,y)\Leftrightarrow\exists y\exists xP(x,y)\end{align*}\]
量词的分配律	\[\begin{align*}&\forall x(P(x)\wedge Q(x))\Leftrightarrow\forall xP(x)\wedge\forall xQ(x) \\& \exists x(P(x)\vee Q(x))\Leftrightarrow\exists xP(x)\vee\exists xQ(x)\end{align*}\]
量词作用域的收缩和扩张	\[\begin{align*}&\forall x(A(x)\vee B)\Leftrightarrow\forall xA(x)\vee B \\& \forall x(A(x)\wedge B)\Leftrightarrow\forall xA(x)\wedge B \\& \forall x(A(x)\rightarrow B)\Leftrightarrow\exists xA(x)\rightarrow B \\&\forall x(B\rightarrow A(x))\Leftrightarrow B\rightarrow\forall xA(x) \\& \exists x(A(x)\vee B)\Leftrightarrow\exists xA(x)\vee B \\& \exists x(A(x)\wedge B)\Leftrightarrow\exists xA(x)\wedge B \\& \exists x(A(x)\rightarrow B)\Leftrightarrow\forall xA(x)\rightarrow B \\& \exists x(B\rightarrow A(x))\Leftrightarrow B\rightarrow\exists xA(x)\end{align*}\]
附加律	\[A\Rightarrow A\vee B\]
化简律	\[A\wedge B\Rightarrow A\]
假言推理	\[(A\rightarrow B)\wedge A\Rightarrow B\]
拒取式	\[(A\rightarrow B)\wedge\neg B\Rightarrow\neg A\]
析取三段论	\[(A\vee B)\wedge\neg B\Rightarrow A\]
假言三段论	\[(A\rightarrow B)\wedge(B\rightarrow C)\Rightarrow (A\rightarrow C)\]
等价三段论	\[(A\leftrightarrow B)\wedge(B\leftrightarrow C)\Rightarrow(A\leftrightarrow C)\]
一阶逻辑推理定律	\[\begin{align*}&\forall xF(x)\Rightarrow\exists xF(x)\\&\forall xA(x)\vee \forall xB(x)\Rightarrow\forall x(A(x)\vee B(x)) \\& \exists x(A(x)\wedge B(x))\Rightarrow\exists xA(x)\wedge\exists xB(x) \\&\forall x(A(x)\rightarrow B(x))\Rightarrow\forall xA(x)\rightarrow \forall xB(x) \\&\exists x(A(x)\rightarrow B(x))\Rightarrow\exists xA(x)\rightarrow \exists xB(x) \end{align*}\]
附加前提推理规则（CP 规则）	\[\textrm{如果}\Sigma,A\Rightarrow B\textrm{则}\Sigma\Rightarrow A\rightarrow B\]
反证推理规则	\[\textrm{如果}\Sigma,\neg A\Rightarrow F\textrm{则}\Sigma\Rightarrow A\]

第二章

卡片正面	卡片背面
\(A\subseteq B\)用命题表示	\[\forall x(x\in A\rightarrow x\in B)\]
\(A\subset B\)用命题表示	\[\forall x(x\in A\rightarrow x\in B)\wedge\exists x(x\in B\wedge x\notin A)\]
\(A=B\)用命题表示	\[\forall x(x\in A\leftrightarrow x\in B)\]
\(A\cup B\)用集合构造器表示	\[\{x|x\in A\vee x\in B\}\]
\(A\cap B\)用集合构造器表示	\[\{x|x\in A\wedge x\in B\}\]
\(A-B\)用集合构造器表示	\[\{x|x\in A\wedge x\notin B\}\]
恒等律	\[\begin{align*}&A\cap U=A \\& A\cup\varnothing=A\end{align*}\]
支配律	\[\begin{align*}&A\cup U=U \\ &A\cap\varnothing=\varnothing\end{align*}\]
幂等律	\[\begin{align*}&A\cap A=A \\& A\cup A=A\end{align*}\]
补律	\[\overline{(\overline{A})}=A\]
交换律	\[\begin{align*}&A\cup B=B\cup A \\& A\cap B=B\cap A\end{align*}\]
结合律	\[\begin{align*}&A\cup (B\cup C)=(A\cup B)\cup C \\ &A\cap (B\cap C)=(A\cap B)\cap C\end{align*}\]
分配律	\[\begin{align*}&A\cup (B\cap C)=(A\cup B)\cap(A\cup C) \\& A\cap (B\cup C)=(A\cap B)\cup (A\cap C)\end{align*}\]
德摩根律	\[\begin{align*}&\overline{A\cap B}=\overline{A}\cup\overline{B} \\& \overline{A\cup B}=\overline{A}\cap\overline{B}\end{align*}\]
吸收律	\[\begin{align*}&A\cup (A\cap B)=A \\& A\cap (A\cup B)=A\end{align*}\]
互补律	\[\begin{align*}&A\cup \overline{A}=U \\& A\cap \overline{A}=\varnothing\end{align*}\]
集合\(A\)和\(B\)有相同基数的充要条件	存在从\(A\)到\(B\)的一个一一对应

第三章

卡片正面	卡片背面
\(\log(n!)\)是\(O(n\cdot\log(n))\)的

第四章

卡片正面	卡片背面
\(a\equiv b\pmod m\)的定义	\[a\bmod m=b\bmod m\]
\(a\equiv b\pmod m\)的充要条件	存在整数\(k\)使得\(a=b+km\)
素数定理	\(x\rightarrow\infty\)时，不超过\(x\)的素数个数\(\rightarrow\frac x{\ln x}\)
贝祖定理	如果\(a\)和\(b\)为正整数，则存在整数\(s\)和\(t\)使得\(\gcd(a,b)=sa+tb\)
中国剩余定理，求解\[\begin{align*}&x\equiv a_1\pmod{m_1} \\& x\equiv a_2\pmod{m_2} \\ &\vdots \\& x\equiv a_n\pmod{m_n} \end{align*}\]	\(x=\sum_i a_iM_iy_i\)，其中\(m=\prod_i m_i,M_i=\frac m{m_i},M_iy_i\equiv 1\pmod{m_i}\)
费马小定理，如果\(p\)为素数且\(p\not|a\)，则	\[a^{p-1}\equiv 1\pmod p\]
原根的定义	模素数\(p\)的一个原根是\(Z_p\)中的整数\(r\)使得\(Z_p\)中的每个非零元素都是\(r\)的一个幂次

第五章

卡片正面	卡片背面
拉梅定理	欧几里得算法求\(\gcd(a,b)\)使用除法的次数小于等于\(b\)的十进制位数的 5 倍

第六章

卡片正面	卡片背面
广义鸽巢原理	如果\(N\)个物体放入\(k\)个盒子，那么至少有一个盒子包含了至少\(\lceil\frac Nk\rceil\)个物体
每个由\(n^2+1\)个不同实数构成的序列都包含一个长为\(n+1\)的严格递增子序列或严格递减子序列
排列\(P(n,r)=\)	\[\frac{n!}{(n-r)!}\]
组合\(C(n,r)=\)	\[\frac{n!}{(n-r)!r!}\]
\(n\)个元素的集合允许重复的\(r\)排列	\[n^r\]
\(n\)个元素的集合允许重复的\(r\)组合	\[C(n+r-1,r)\]
设类型\(k\)的相同的物体有\(n_k\)个，那么\(n\)个物体的不同排列数是	\[\frac{n!}{n_1!n_2!\ldots n_k!}\]
\(n\)个不同的物体分配到\(k\)个不同的盒子，使得盒子\(i\)中有\(n_i\)个物体	\[\frac{n!}{n_1!n_2!\ldots n_k!}\]
\(n\)个相同的物体分配到\(k\)个不同的盒子	\[C(n+k-1,k)\]