关系
July 8, 2022
Binary Relation # 二元关系，用来表示两个集合里元素的关系 从集合 A 到集合 B 的二元关系为 AxB 的子集 n-ary，n 元关系，用来表示 n 个集合里元素的关系
math
矩阵
June 18, 2022
定义 # m 行 n 列的矩阵称为 \(m \times n\) 矩阵，\(m = n\) 时，称为方阵 在离散数学里，常用来表示集合里元素的关系 矩阵加法 # 若 \(A = [a_{ij}]，B = [b_{ij}]\) 均为 \(m \times n\) 矩阵，则 \(A + B = [a_{ij} + b_{ij}]\) 矩阵乘法 # 设 \(\textbf A = [a_{ij}]\) 为 \(m \times n\) 矩阵，\( \textbf B = [b_{ij}]\) 为 \( n \times k\) 矩阵，则 \(AB = C = [c_{ij}]\) 为 \(m \times k\) 矩阵 \[c_{ij}=a_{i1} \cdot b_{1j} + a_{i2} \cdot b_{2j} + … + a_{ik} \cdot b_{kj} \]
数列
June 16, 2022
定义 # 有序元素集，整数子集到另一个集合的映射 例: \( \{a_{n}\} \)， \(a_n = \frac {1}{n}\)，\(n \in \mathbb{Z^+} \) 等比级数 # \(a, ar, ar^2,…,ar^n\), (\(a,r \in R\))，r 为 公比 等差数列 # \(a, a+d, a+2d, … ,a+nd, …\), d 为 公差 Fibonacci sequence # 斐波那契数列 \(f_0 = 0, f_1 = 1, f_n = f_{n-1} + f_{n-2}, ( n \geq 2, n \in \mathbb{Z^+} ) \)
集合
June 13, 2022
定义 # 不同 对象（元素）的 无序 集合 允许包含相同元素的集合称为 multiset（多集） 表示 # Roster method # 花名册法，枚举集合里的每个元素 Set builder notation # 集合构造器表示法 例如： \( O = \{x \mid x 为奇数 \} \) 或 \( O = \{x: x 为奇数 \} \) 集合的操作 # 差集 # A - B = {x: \(x \in A \) and \( x \not\in B \) } 交集 # 并集 # 子集 # Cardinality # 集的势 (size)，集合里元素的数量,表示为 |S| ...
离散概率
June 5, 2022
概率 # 抽样实验 # 从可能的结果集里取值的过程 取样空间 # 可能的结果集 抽样事件 # 取样空间的子集 定义 # 如果 \( S \) 为有限的非空的等概率的取样空间，\(E\) 为抽样事件，那么 \(E\) 的概率为 \(p(E) = \frac{\vert E \vert}{\vert S \vert}\) 定理 # 抽样事件 \(E\) 的补集 \(\bar E\) 的概率为 \(p(\bar E)= 1 - p(E)\)
计数问题
June 5, 2022
计数法则 # 积法则 # 从两个不相集里选择有序对的方法数 假定任务 Task 可以分两步去解决，第一步有 \(n_1\) 种解决方法，第二步有 \(n_2\) 种解决方法，那么解决任务 Task 总共有 \(n_1 \times n_2\) 种方法 和法则 # 从两个不相交集里选一个元素的方法数 如果任务 Task 在条件一下有 \(n_1\) 种方法解决，在条件二下有 \(n_2\) 种方法解决，那么在两种条件都考虑的情况下，任务 Task 共有 \(n_1 + n_2\) 种解决方法 Permutations and Combinations # 排列组合 排列 # 有序 n 元集里的 r 排列： \[ n, r \in \mathbb{Z^{+}}, 1 \leq r \leq n ，P(n,r)=n(n-1)(n-2)…(n-r+1)= \frac{n!}{(n-r)!} \] 0 的阶乘为 1 组合 # 无序 ...
指数和对数
June 4, 2022
指数 # 定义： \( b \in \mathbb{R^+}, n \in \mathbb{R^+} \), \(f_b(n) = b^n = b \cdot b \cdot b \cdot … \cdot b\)，n 个 b 相乘 定理： \(b^{x+y} = b^x \cdot b^y\) \((b^x)^y=b^{x \cdot y}\) 对数 # 定义： \(f = \log_b x \)，以 b 为底的 x 的对数值 \(b^x = a, x = \log_b a\) \(b^{\log_b a} = a\) 定理： \(\log_b (x \cdot y)=\log_b x + \log_b y\) \(\log_b (x^y)=y \cdot \log_b x\) \(\log_a x = \frac{\log_b x}{\log_b a}=\frac{1}{ \log_b a} \cdot \log_b x\)，（换底，常量值乘以 b 为底的对数） 在计算机领域，\(\log x\)，底省略时，通常指以 2 为底的对数
常用数学符号
June 3, 2022
SETS # 符号 含义 \(\mathbb{N}\) 自然数 \(\mathbb{Z}\) 整数 \(\mathbb{Z^+}\) 正整数 \(\mathbb{Q}\) 有理数 \(\mathbb{R}\) 实数
归纳和递归
June 1, 2022
数学归纳和递归 # 数学归纳 # 证明：当 \( n \in \mathbb{Z^+} \) 时，\(P(n)\) 成立。 基础条件： 证明 \(P(1)\) 成立 归纳条件： 证明对 \(\forall k \in \mathbb{Z^+} \)， \(P(k) \rightarrow P(k+1) \) 成立 即可证原命题成立 推理公式： \( (P(1) \land \forall k (P(k) \rightarrow P(k+1))) \rightarrow \forall n P(n) \)，\(n,k \in \mathbb{Z^+}\) 递归 #
如何证明
June 1, 2022
Proof method # 证明方法 Theorem # 定理： 可证明为真的语句 （事实，真相） Axioms # 公理： 假定为 true 的语句 (statements) Lemma # 引理，辅助定理 Proof # 证明 p true， q 为 true Direct proof # 直接证明 if p true, p -> q true, q true Contraposition # ~q -> ~p Contradiction # 矛盾法