0%

离散数学(上)概念及公式

自制,Anki用

概念

第一章

英文 中文
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{array}{l}P\wedge T\Leftrightarrow P \\ P\vee F\Leftrightarrow P\end{array}\]
零律 \[\begin{array}{l}P\vee T\Leftrightarrow T \\ P\wedge F\Leftrightarrow F\end{array}\]
等幂律 \[\begin{array}{l}P\wedge P\Leftrightarrow P \\ P\vee P\Leftrightarrow P\end{array}\]
双重否定律 \[\neg(\neg P))\Leftrightarrow P\]
交换律 \[\begin{array}{l}P\wedge Q\Leftrightarrow Q\wedge P \\ P\vee Q\Leftrightarrow Q\vee P\end{array}\]
结合律 \[\begin{array}{l}(P\vee Q)\vee R\Leftrightarrow P\vee(Q\vee R) \\ (P\wedge Q)\wedge R\Leftrightarrow P\wedge(Q\wedge R)\end{array}\]
分配律 \[\begin{array}{l}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{array}\]
德摩根律 \[\begin{array}{l}\neg(P\wedge Q)\Leftrightarrow \neg P\vee\neg Q \\ \neg(P\vee Q)\Leftrightarrow \neg P\wedge\neg Q\end{array}\]
蕴含等价式 \[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{array}{l}P\vee(P\wedge Q)\Leftrightarrow P \\ P\wedge(P\vee Q)\Leftrightarrow P\end{array}\]
输出律 \[(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{array}{l}\neg\exists xP(x)\Leftrightarrow \forall x\neg P(x) \\ \neg\forall xP(x)\Leftrightarrow \exists x\neg P(x)\end{array}\]
嵌套量词的交换律 \[\begin{array}{l}\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{array}\]
量词的分配律 \[\begin{array}{l}\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{array}\]
量词作用域的收缩和扩张 \[\begin{array}{l}\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{array}\]
附加律 \[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{array}{l}\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{array}\]
附加前提推理规则(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{array}{ll}A\cap U=A \\ A\cup\varnothing=A\end{array}\]
支配律 \[\begin{array}{ll}A\cup U=U \\ A\cap\varnothing=\varnothing\end{array}\]
幂等律 \[\begin{array}{ll}A\cap A=A \\ A\cup A=A\end{array}\]
补律 \[\overline{(\overline{A})}=A\]
交换律 \[\begin{array}{ll}A\cup B=B\cup A \\ A\cap B=B\cap A\end{array}\]
结合律 \[\begin{array}{ll}A\cup (B\cup C)=(A\cup B)\cup C \\ A\cap (B\cap C)=(A\cap B)\cap C\end{array}\]
分配律 \[\begin{array}{ll}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{array}\]
德摩根律 \[\begin{array}{ll}\overline{A\cap B}=\overline{A}\cup\overline{B} \\ \overline{A\cup B}=\overline{A}\cap\overline{B}\end{array}\]
吸收律 \[\begin{array}{ll}A\cup (A\cap B)=A \\ A\cap (A\cup B)=A\end{array}\]
互补律 \[\begin{array}{ll}A\cup \overline{A}=U \\ A\cap \overline{A}=\varnothing\end{array}\]
集合\(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{array}{c}x\equiv a_1\pmod{m_1} \\ x\equiv a_2\pmod{m_2} \\ \vdots \\ x\equiv a_n\pmod{m_n} \\\end{array}\] \(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)\]