离散数学笔记
Logic of Compound Statements
Concepts
| Concept | Meaning |
|---|---|
| Statement or Proposition | A sentence that is true or false but not both. |
| Argument | A sequence of statements aimed at demonstrating the truth of an assertion |
| Tautology | Statement form that is always true regardless of the truth values of individual statements |
| Contradiction | Statement form that is always false regardless of the truth values of the individual statements |
If \(t\) is a tautology and \(c\) is a contradiction, then \(p\wedge t\equiv p\) and \(p\wedge c\equiv c\)
Conditional
If \(p\) and \(q\) are statement variables, the conditional of \(q\) by \(p\) is “If \(p\) then \(q\)” or “\(p\) implies \(q\)” and is denoted \(p\rightarrow q\).
It is false when \(p\) is true and \(q\) is false; otherwise it is true.
A conditional statement that is true by virtue of the fact that its hypothesis is false is often called vacuously true or true by default.
Valid Argument Forms
Argument is valid if the conclusion is true whenever the premises are all true (A row of the truth table in which all premises are true is called a critical row)
Number Theory & Method of Proof
Unique Factorization of Integers
Given any integer \(n > 1\), there exist a positive integer \(k\), distinct prime numbers \(p_1,\,p_2,\,\cdots,\,p_k\), and positive integers \(e_1,\,e_2,\,\cdots,\,e_k\) such that \[n=p_1^{e_1}p_2^{e_2}p_3^{e_3}\cdots p_k^{e_k}\] \(n\) is called standard factored form of \(n\) when \(p_1<p_2<\cdots<p_k\)
The Quotient-Remainder Theorem
Given any integer \(n\) and positive integer \(d\), there exist unique integers \(q\) and \(r\) such that \(n = dq + r\) and \(0 \leq r < d\)
Euclidean Algorithm
1 | |
- If \(r\) is a positive integer, then \(\gcd(r,\,0) = r\)
- If \(a\) and \(b\) are any non-zero integers, and if \(q\) and \(r\) are any integers such that \(a = bq + r\), then \(\gcd(a,\,b) = \gcd(b,\,r)\)
Sequences, Mathematical Induction, and Recursion
Second-order linear homogeneous recurrence relation with constant coefficients
\(a_k = Aa_{k−1} + Ba_{k−2}\) \(\forall\) integers \(k\ge\) some fixed integer, \(A,\,B\) are fixed real numbers with \(B \neq 0\)
Characteristic Equation
Suppose a sequence \(a_0,\,a1,\,a_2,\,\cdots\) satisfies a recurrence relation \(a_k = Aa_{k−1} + Ba_{k−2}\) for some real numbers \(A\) and \(B\) with \(B \neq 0\) and all integers k ≥ 2. If the characteristic equation \(t^2 − At − B = 0\) has
- Two distinct roots \(r\) and \(s\), then \(a_n=Cr^n+Ds^n\)
- A single (real) root \(r\), then \(a_n=Cr^n+Dnr^n\)
where \(C\) and \(D\) are the numbers whose values are determined by the values \(a_0\) and \(a_1\)
Set Theory
Subset
Notation \(A=\left\{x\in S|P\left(x\right)\right\}\)
Subset \(A\subseteq B\Leftrightarrow\forall x,\,\mathrm{if}\;x\in A\;\mathrm{then}\;x\in B\)
Proper Subset: \(A\subseteq B\) and there is at least one element in \(B\) that is not in \(A\).
Method for proving one set is a subset of another
- Suppose that \(x\) is a particular but arbitrarily chosen element of \(X\)
- Show that \(x\) is an element of \(Y\)
Set Equality Given sets \(A\) and \(B\), \(A\) equals \(B\), written \(A = B\) if and only if every element of \(A\) is in \(B\) and every element of \(B\) is in \(A\).
Operations on Sets
Let \(A\) and \(B\) be subsets of a universal set \(U\).
| Operation | Definition |
|---|---|
| Union | \(A\cup B=\left\{x\in U\,\vert\,x\in A\;\mathrm{or}\;x\in B\right\}\) |
| Intersection | \(A\cap B=\left\{x\in U\,\vert\,x\in A\;\mathrm{and}\;x\in B\right\}\) |
| Difference | \(A-B=\left\{x\in U\,\vert\,x\in A\;\mathrm{and}\;x\notin B\right\}\) |
| Complement | \(A^c=\left\{x\in U\,\vert\,x\notin A\right\}\) |
| Cartesian Product | \(A_1\times A_2\times\cdots\times A_n=\left\{\left(a_1,\,a_2,\cdots,\,a_n\right)\vert a_i\in A_i\right\}\) |
Partitions of Sets
Disjoint Two sets are called disjoint if and only if they have no elements in common: \(A\cap B=\emptyset\).
Partition A finite or infinite collection of nonempty sets \(\left\{A_1, A_2,\,A_3,\,\cdots\right\}\) is a partition of a set \(A\) if and only if:
- \(A\) is the union of all the \(A_i\)
- \(A_1, A_2,\,A_3,\,\cdots\) are mutually disjoint
Functions
Categories of functions:
- One-to-one function: \(\forall x_1\;\mathrm{and}\;x_2\in X, \;\mathrm{if}\;F(x_1)=F(x_2),\;\mathrm{then}\;x_1=x_2\)
- Onto function: \(\forall y\in Y,\;\exists x\in X\;\mathrm{such\,that}\;F(x)=y\)
A one-to-one correspondence (or bijection) from a set \(X\) to a set \(Y\) is a function \(F:X\rightarrow Y\) that is both one-to-one and onto.
Cardinality
Definition The size of the set, denoted by \(|A|\) for a set \(A\).
- Finite set is \(\emptyset\) or a set \(\textcolor{orange}{\mathrm{can}}\) be put into one-to-one correspondence with \(\mathbf{Z}^+\)
- Infinite set is a nonempty or a set \(\textcolor{orange}{\mathrm{cannot}}\) be put into one-to-one correspondence with \(\mathbf{Z}^+\)
Set \(A\) has the same cardinality as set \(B\), if and only if there is a one-to-one correspondence from \(A\) to \(B\).
A set is called countable, if and only if it is finite or countably infinite.
- A set is called countably infinite, if and only if it has the same cardinality as the set of \(\mathbf{Z}^+\).
A set that is not countable is called uncountable.
Relations
Relation
Partial Order Relation: denoted by \(\preceq\)
Reflexive
Explained in simpler way: Related to itself.
Antisymmetric
Definition: \(a\;\mathrm{R}\;b\,\wedge\,b\;\mathrm{R}\;a\rightarrow a=b\)
Explained in simpler way: Never returns back.
Transitive
Hasse Diagrams
Every vertex is always transitive ("goes up") and if all redundant directions are eliminated, then the Hasse Diagram is obtained.
Partially and Totally Ordered Sets
Definition Comparable: Suppose \(\preceq\) is a partial order relation on a set \(A\) and elements \(a\) and \(b\) of \(A\) are comparable if and only if either \(a\preceq b\) or \(b\preceq a\).
Every element is comparable in the set should be called totally ordered sets.
Maximal, Minimal Elements
flowchart LR;
a & b --> c --> d --> e
\(a\) and \(b\) are minimal but not least (since \(a\) and \(b\) are not comparable)
Upper bound: \(\exists u\in S\subseteq A,\,\forall a\in A,\,a\preceq u\)
Lower bound:
Congruence Modulo
has exactly same remainder. e.g. \[\begin{array}{c}5 \,\mathrm{mod}\, 2 = 1\\3 \,\mathrm{mod}\, 2 = 1\end{array}\Rightarrow 5 \equiv 3 \left(\mathrm{mod}\, 2\right)\]
- \(n|(a-b)\) (Usually employed in proving)
- \(a\equiv b\,(\mathrm{mod}\,n)\)
- \(a\,\mathrm{mod}\,n=b\,\mathrm{mod}\,n\)
Modular Arithmetic
Let \(a,\,b,\,c,\,d\) and \(n\) be integers with \(n\gt1\) and suppose \(a\equiv c\left(\mathrm{mod}\, n\right)\) and \(a\equiv c\left(\mathrm{mod}\, n\right)\)
| Operation | Expression |
|---|---|
| Addition | \(\left(a+b\right)\equiv\left(c+d\right)\left(\mathrm{mod}\, n\right)\) |
| Subtraction | \(\left(a-b\right)\equiv\left(c-d\right)\left(\mathrm{mod}\, n\right)\) |
| Multiplication | \(ab\equiv cd\left(\mathrm{mod}\, n\right)\) |
| Power | \(a^m\equiv c^m\left(\mathrm{mod}\, n\right)\) |
| Modulo | \(ab\equiv\left(\left(a\,\mathrm{mod}\, n\right)\left(b\,\mathrm{mod}\, n\right)\right)\left(\mathrm{mod}\, n\right)\) |
| Cancellation | \(ac\equiv
bc\left(\mathrm{mod}\, n\right)\Rightarrow a\equiv b\left(\mathrm{mod}\,
n\right)\) \(\gcd\left(c,\,n\right)=1\) |
Bézout's identity
Let \(S=\left\{x\vert x=as+bt,\,x\in Z^+\right\}\)
(REVIEW: Euclid algorithm for calculating GCD \(d=\gcd\left(a,\,b\right)=\gcd\left(b,\,a\,\mathrm{mod} \,b\right),\quad a=bq+r\))
Proof: 1. \(S\) is non-empty (by choosing exact \(a\)) 2. By WOP, \(S\) has a least element \(c=as+bt\) 3. Prove that \(c=d\) via \(c\geq d\) and \(d\geq c\)
\(c\geq d\)
- \(d\vert a\) and \(d\vert b\) since \(d\) is the GCD of \(a\) and \(b\).
- \(a=kd,\,b=ld\)
- \(c=as+bt=s\cdot kd+t\cdot ld=d(ks+lt)\)
\(d\geq c\)
\(c\vert d\Rightarrow c\vert a\wedge c\vert b\)
Quotinent-Remainder Theorem \(a=cq+r,\;0\leq r\lt c\)
- \(r=a-cq=a-(as+bt)q=a(1-sq)+b(-tq)\) is also a combination of \(a\) and \(b\)
- \(c\) is the least element, \(r\) cannot be greater than \(c\) so it contradicts with \(r\gt 0\)
- \(r=0\) leads to \(a=cq\Rightarrow c\vert a\)
Application: 1. Express GCD in linear combination
Inverse Modulo
For all integers \(a\) and \(n\), if \(\gcd\left(a,\,n\right)=1\) (i.e. \(a\) and \(n\) are relatively prime) then there exists an integer \(a^{-1}\) such that \(aa^{-1}\equiv 1\)
RSA
- Select two prime number \(p,\,q\)
- \(e\) relatively prime to \((p-1)(q-1)\)
- Encryption: Cipher text \(C=M^e\,\mathrm{mod}\, pq\) where \(e,\,pq\) are public keys
- Decrpytion: Plain text \(M=C^d\,\mathrm{mod}\,pq\) where \(d\) is a positive inverse to \(e\) modulo \((p-1)(q-1)\)
Fermat's Little Theorem
If \(p\) is any prime number and \(a\) is any integer such that \(p\not\vert a\), then \(a^{p-1}\equiv 1\left(\mathrm{mod}\, p\right)\)
Proof:
The whole set of residues \(S=\left\{1,\,2,\,3,\,\cdots,\,p-1\right\}\), multiplied by \(a\) then \(aS=\left\{a,\,2a,\,3a,\,\cdots,\,(p-1)a\right\}\)
Cardinality of \(S\), i.e. \(|S|=p-1=|aS|\)
Since any element \(x\in aS\), \(x\,\mathrm{mod}\,p\in S\) as well.
Suppose \(ra=sa\left(\mathrm{mod}\,p\right)\quad 1\leq r\lt s\leq (p-1)\)
\(p\vert (s-r)a\Rightarrow p\vert(s-r)\) by Euclid's Lemma, which implies \(s-r\geq p\), contradicting against the condition
Thus \(ra\not\equiv sa\left(\mathrm{mod}\,p\right)\)
\(aS\) to \(S\) is one-to-one correspondance so \(a\cdot 2a\cdot 3a\cdots (p-1)a\equiv 1\cdot2\cdot3\cdots(p-1)\;(\mathrm{mod}\,p)\)
and \(\gcd\left(p,\,(p-1)!\right)=1\) would cancel the \((p-1)!\)
Hence, \(a^{p-1}\equiv1(\mathrm{mod}\,p)\)