Sakana~
0%

Discrete Mathematics

发表于 更新于 分类于

Discrete Mathematics notes

Discrete Mathematics

mmexport1667521808587

mmexport1667521810543

Logic

Proposition： A declarative sentence that is either true or false, but not both

Logical operators

  • Negation operator ¬

  • Conjunction (and, ^)

  • Disjunction (or, v ) （相容或）

  • Conditional statement →

  • Biconditional statement ↔ (if and only if)

  • Exclusive Or (xor，⊕)

More about Conditional statement

only T→F get F

p only if q： p → q

q unless ¬p: p → q

p → q equals to (¬p v q)

whether these system specifications are consistent

All statements are not contradictory

Tautology and contradiction

Tautology: always true

Contradiction: always false

Contingency: neither a tautology nor a contradiction

Logical equivalence

**p ≡ q : p ↔ q is a tautology **

The symbol ≡ is not a logical connective,

and p ≡ q is not a compound proposition

Some laws

Predicates & Quantifiers

Predicates：involving variables

P(x): also called the value of the propositional function P at x

Once a value is assigned to the variable x, P(x) becomes a proposition and has a truth value

Quantifiers：

  • Universal：every
  • Existential：one or more
  • Uniqueness quantifier：There is exactly one

Translate between Quantifiers and Logical operators

  • have higher precedence than all logical operators from propositional calculus

  • The same letter is often used to represent variables bound by different quantifiers with scopes that do not overlap

Important： exist == v; all == →

Proof

Induction

Mathematical induction

image-20221103233035787

Strong induction

image-20221103233240044

Structural induction

递归？

Sets

Singleton: A set with one element

If a set has n elements, then its power set has 2n elements

集合证来证去，很像数字电路

Functions

image-20221103213504829

  • Onto: A function from A to B is onto or surjective, if and only if for every element b ∈ B there is an element a ∈ A with f(a)=b

  • A one-to-one correspondence is called invertible

Sequences

Countable

When the elements of an infinite set can be listed, the set is called countable

自然数集可数，实数集不可数

Geometric progression

$f(x)=a \cdot r^x$

Arithmetic progression

$f(x)=a+dx$

String

Sequences of the form a1, a2, …, an are often used in computer science

The empty string, denoted by 𝝺

image-20221103215237781

image-20221103215408121

image-20221103215520615

Cardinality

The sets A and B have the same cardinality, |A|=|B|, if and only if there is a one-to-one correspondence from A to B

Countable: A set that is either finite or has the same cardinality as the set of positive integers

有理数也可数：
image-20221103220033544

Algorithm

Prosperities of algorithm

Input，Output，Definiteness，Correctness，Finiteness，Effectiveness，Generality

二分，排序（冒泡，插入），贪心

The halting problem

判断任意一个程序是否能在有限的时间之内结束运行的问题

cannot be solved

image-20221103211631078

（形如理发师悖论）

时间复杂度

image-20221103211903404

image-20221103212419943

A problem that is solvable by an algorithm with a polynomial worst-case complexity is called tractable

P： can be solved with polynomial worst-case time complexity.

NP： problems for which a solution can be checked in polynomial time.

**NPC： **There is such a NP problem that all NP problems can be reduced to it.

NP-hard： All NP problems can be reduced to it, but it is not necessarily an NP problem

image-20221103213350730

Number theory

丢一个数论笔记在这里 https://i.cnblogs.com/posts?cateId=2230819

整除运算

$a | b$ $\leftrightarrow$ $b = ka$

$a|b\rightarrow a|(mb+nc)$

任意表示一个数：$a=dq+r,0\leq r< d$

==$a\equiv b(\mathrm{mod},m)\leftrightarrow (a-b)\mathrm{mod,}m=0\leftrightarrow a=km+b$==

$a\equiv b(\mathrm{mod},m),, \mathrm{and},, c\equiv d(\mathrm{mod,}m)\rightarrow a+c\equiv b+d(\mathrm{mod},m),, \mathrm{and},, ac\equiv bd(\mathrm{mod,}m)$

定义运算：

$a+_mb=(a+b)\mathrm{mod,}a,,,a\cdot_m b=(a\cdot b)\mathrm{mod,}m$

指数运算

指数计算 $b^n\mathrm{mod,}m$： $n=(a_{k-1}…a_1a_0)2$，则 $b^n=b^{a{k-1}\cdot 2^{k-1}}b^{a_{k-2}\cdot 2^{k-2}}b^{a_1\cdot 2}b^{a_0}$

即快速幂：

1
2
3
4
5
6
7
8
9
10
ll qmi(int a,int k,int p) {
	ll ans = 1;
	while (k) {
		if (k & 1)//末位1取出
			ans = (ll)ans * a % p;
		k >>= 1;//次末位
		a = (ll)a * a % p;
	}
	return ans;
}

手搓快速幂的例子：

image-20221103155720479

$power$ 从底数开始，每次平方后取模

$i$ 从0枚举到最高位，若该位为1，则 $x$ 乘上上一位计算出的 $power$

gcd

==$(a,b)[a,b]=a\times b$==

算术基本的定理：质因数分解唯一

  • If n is a composite integer, then n has a prime division less than or equal to $\sqrt{n}$

证明素数：
image-20221103161544683

Decomposition of prime factors by trial division

1
2
3
4
5
6
7
8
9
10
void divide (int x) {
    for (int i = 2; i <= x; i++) {
        if (x % i == 0) {
            int s = 0;
            while (x % i == 0)    x /= i, s++;
            cout << i << ' ' << s << endl;
        }
    }
    if (x > 1)    cout << x << ' ' << 1 << endl;
}

Euclidean algorithm

1
2
3
int gcd (int a, int b) {
	return b ? gcd(b, a % b) : a;
}

Lemma： $a = bq+r$，Then $gcd(a,b)=gcd(b,r)$

Primes

素数无限：$p_1,p_2,…,p_n\rightarrow Q=p_1p_2…p_n+1$

Mersenne primes： $2^p-1$

image-20221103163801956

  • Mersenne prime is prime for p=2, 3, 5, 7, 13, 17, 19, 31, 67, 127, 257 but is composite for all other primes less than 257

  • The largest Mersenne prime known is $2^{43112609}-1$

$\pi(n)$ ：小于等于n的素数个数
$$
\lim_{n\rightarrow\infty}\frac{\pi(n)\ln n}n=1\
P_n=O(n\log n)\
\sum_{i=1}^n \frac1i=O(\log n)\
\sum_{1\leq p\leq n} \frac 1p=O(\log\log n)\
$$

  • Goldbach’s conjecture: every even integer n, n>2, is the sum of two primes

image-20221103171355618

the gcd is the last nonzero remainder in the sequence of divisions

Bezout’s Theorem

一定存在整数解，满足 ax + by = gcd (a, b)

(a, b) | d $\leftrightarrow$ au + bv = d，存在整数解 u, v

扩展欧几里得

系数化为欧几里得，分解a
$$
ax+by=1\rightarrow b(\lfloor \frac ab \rfloor +a \mathrm{,,mod,,} b)x+by=1\
\rightarrow b(\lfloor \frac ab\rfloor x+y)+(a\mathrm{,,mod,,} b)x=1,
令x’=\lfloor \frac ab\rfloor x+y,y’=x,
\则x=y’,y=x’-\lfloor \frac ab\rfloor y’,转化为bx’+(a\mathrm{,,mod,,} b)y’=1
$$

1
2
3
4
5
6
7
8
9
10
ll exgcd(ll a, ll b, ll &x, ll &y) {
    if (b == 0) {
        x = 1;
        y = 0;
        return a;
    }
    ll d = exgcd(b, a % b, y, x);
    y -= (a / b) * x;
    return d;
}

image-20221103171919583

同余

$$
a\equiv b (\mathrm{mod,,} m) \leftrightarrow m|b-a\
a\equiv b(\mathrm{mod,,} m), a\equiv b (\mathrm{mod,,}n)\rightarrow a\equiv b(\mathrm{mod,,}[m,n])\
\bbox[yellow]{
(k,m)=d, ka\equiv ka’(\mathrm{mod,,} m)\rightarrow a\equiv a’(\mathrm{mod,,} \frac md)}
$$

公式三更一般的结论：
$$
ka\equiv ka’(\mathrm{mod,,} m)\rightarrow a\equiv a’(\mathrm{mod,,} \frac m{(m,k)})
$$

Linear Congruences

Modular Inverse

$ax\equiv b(\mathrm{mod,}m)\rightarrow x\equiv a^{-1}b(\mathrm{mod,}b)$

逆元存在且唯一

求逆元

手算

求101模4620的逆元：

image-20221103183948013

最好用线性递推，即方法三来算

快速幂求逆元模板（素数）：

$a^{p-1}\equiv1(\mathrm{mod},,p)\rightarrow aa^{p-2}\equiv1(\mathrm{mod,,p)\rightarrow a^{p-2}\equiv a^{-1}(\mathrm{mod},,p})$

扩展欧几里得求逆元模板（非素数）：

$a^{\phi(m)}\equiv1(\mathrm{mod,,}m)\rightarrow a^{\phi(m)-1}\equiv a^{-1}(\mathrm{mod,,}m)$

1
2
3
int d = exgcd(a, p, x, y);
if (d == 1) 	cout << (1ll * x + p) % p << endl;
else 	puts("impossible");
线性递推求逆元（1 - n）：

inv[i] = (p - p / i) * inv[p % i] % p

1
2
3
4
inv[1] = 1;
for (int i = 2; i <= n; i++) {
    inv[i] = (p - p / i) * inv[p % i] % p;
}

线性同余方程组

中国剩余定理

模数两两互质（手算）：

image-20221103191431022

即 $x=a_1M_1y_1+a_2M_2y_2+…+a_nM_ny_n$

$$
令M=\prod_{i=1}^n m_i,M_i=\frac M{m_i},,,
解若干个
\begin{cases}
x_i\mathrm{,,mod,,}m_i=1\
x_i\mathrm{,,mod,,}M_i=0
\end{cases}\
设x_i=M_it_i,则解M_it_i\mathrm{,,mod,,} m_i=1,,,,
然后x=\sum_{i=1}^n a_ix_i
$$

代入法解

image-20221103192100071

image-20221103192220826

杜爹法

$$
\begin{cases}
100x\equiv 0(\mathrm{mod,,}100),(1)\
87x\equiv3(\mathrm{mod,,}100),(2)
\end{cases}
$$

$$
(1)-(2)得,13x\equiv97(\mathrm{mod,,}100),(3)\
(2)-6\times(-3)得,9x\equiv 21(\mathrm{mod,,}100),(4)\
(3)-(4)得,4x\equiv 76(\mathrm{mod,,}100)\
(4)-2\times(5)得，x\equiv69(\mathrm{mod,,}100)
$$

欧拉函数

指数：$\phi(p)=p-1$

一般：

1
2
3
4
5
6
7
8
9
10
11
ll phi (ll n) {
    ll ans = n;
    for (int i = 2; i*i <= n; i++) {
        if (n % i == 0) {
            ans = ans / i * (i - 1); //*(1-1/i)
            while (n % i == 0)  n /= i;
        }
    }
    if (n > 1)  ans = ans / n * (n - 1); 
    return ans;
}

欧拉定理

==若 $(a,m)=1$,则 $a^{\phi(m)}\equiv1(\mathrm{mod,,}m)$==

费马小定理

$ a^{p-1}\equiv1(\mathrm{mod,,}p)$

image-20221103193009391

Hash

伪随机Pseudorandom numbers：$x_{n+1}=(ax_n+c) \mathrm{mod,} m$

RSA

image-20221103194402425

手算：
image-20221103194827337

RSA证明（还没看）：

image-20221103195529058

image-20221103195544508

Counting

Relations

Graph

Tree

Boolean algebra