Discrete Math

• Important

\[p \to q \equiv \lnot p \lor q\]

• Contrapositive

\[p \to q \equiv \lnot q \to \lnot p\]

• others

\[p \lor q \equiv \lnot p \to q\] \[p \land q \equiv \lnot (p \to \lnot q)\] \[\lnot (p \to q) \equiv p \land \lnot q\] \[(p \to q) \land (p \to r) \equiv p \to (q \land r)\] \[(p \to r) \land (q \to r) \equiv (p \lor q) \to r\] \[(p \to q) \lor (p \to r) \equiv p \to (q \lor r)\] \[(p \to r) \lor (q \to r) \equiv (p \land q) \to r\]

\[p \leftrightarrow q \equiv (p \to q) \land (q \to p)\] \[p \leftrightarrow q \equiv \lnot p \leftrightarrow \lnot q\] \[p \leftrightarrow q \equiv (p \land q) \lor (\lnot p \land \lnot q)\] \[\lnot (p \leftrightarrow q) \equiv p \leftrightarrow \lnot q\]

\[\forall x(P(x)\land Q(x)) \equiv \forall xP(x)\land \forall xQ(x)\]

• De Morgen's Laws for Quantifiers

\[\lnot \forall xP(x) \equiv \exists x \lnot P(x)\] \[\lnot \exists x Q(x) \equiv \forall x \lnot Q(x)\]

\[\forall x \forall y P(x, y) = \forall y \forall x P(x, y)\] \[\forall x \exists y P(x, y) \ne \exists x \forall y P(x, y)\] \(\forall x \exists y P(x, y)\) There is a \(y\) such that for every \(x\), \(P(x, y)\).

Fallacy of affirming the conclusion
\(((p\to q)\land q) \to p\) is not a tautology. (when p is false, q is true)

Fallacy of denying the hypothesis
\(((p\to q)\land \lnot p\) is not a tautology. (when p is false, q is true)

• prove p is true

We want to prove p is true,
If we can find a contradiction q(q is always false), such that \(\lnot p \to q\) is true.
then p is true.
Simple Explanation: \((\lnot q) \land (\lnot p \to q) \to p\)
Simple contradiction: \(r\land \lnot r\)
Steps:
 1 get \(\lnot p\)
 2 find some argument \(\lnot p \to q\) (q is a contradiction)

• prove \(p\to q\) is true
  1. first get the negation \(\lnot(p\to q)\)
  2. we know \(\lnot(p\to q) \equiv p\land \lnot q\) , so \(\lnot (p \to q) \to p\land \lnot q\)
  3. if we can prove \(p\land \lnot q\) is always false, then \(p\to q\) is true.
     • Note that: prove \(p\) and \(\lnot q\) can not be both true.(If we can prove \(\lnot q \to \lnot p\) )(Proof by Contraposition)
• prove several proposition are equivalent

\[p_1\leftrightarrow p_2 \leftrightarrow ... \leftrightarrow p_n\] One way to prove: \[\equiv (p_1\to p_2)\land(p_2\to p_3)\land ... \land (p_n \to p_1)\]

Each inhabitant of a remote village always tells the truth
or always lies. A villager will give only a“Yes”or a“No”
response to a question a tourist asks. Suppose you are a
tourist visiting this area and come to a fork in the road.
One branch leads to the ruins you want to visit; the other
branch leads deep into the jungle. A villager is standing
at the fork in the road.What one question can you ask the
villager to determine which branch to take?

A: If I were to ask you whether the right branch
leads to the ruins, would you answer yes?

The nth statement in a list of 100 statements is“Exactly
n of the statements in this list are false.”
a) What conclusions can you draw from these state-
ments?
b) Answer part (a) if the nth statement is “At least n of
the statements in this list are false.”
c) Answer part (b) assuming that the list contains 99
statements.

Answer:
a) All statements are mutually exclusive. It means at most 1 statement is true.
    If 0 statement is true, then 100th says "all 100 statements are false" which is a true statement.
    This lead to a parabox.
    If 1 statement is true, then 99 statements are false. 99th statement fits this situation.

b) if n+1 is true, then n is true. We need to find the boundary.
    Assume n is true and n+1 is false. The statements from n+1 to 100 are false.
    So we get the inequality, \(100-n \ge n\) and \(100-(n+1) < n\).
    Solution: \(49.5 < n \le 50\)

c) Same as Question b). Get solution \(49.5 < n \le 49.5\). Lead to a parabox.
    For the confused case, let 49th statement be true and 50th statement be false.
    50th statement's complement: Less than n of the statements are false.
    But if 50th is false, then the count of false statements is 50.

Albert Einstein

• A set is an unordered collection of objects.
• Set A = B when \(\forall x (x \in A) \leftrightarrow (x\in B)\) .
• Set A is a subset of B. \(A\subseteq B\) . \(\forall x (x \in A \to x\in B)\)
• \(\forall S (\emptyset \subseteq S) \land (S\subseteq S)\)
• Set A is a proper subset of B. \(A\subset B\) . \(\forall x (x \in A \to x\in B)\land \exists x (x\in B \land x\notin A)\)

• \((f_1+f_2)(x) = f_1(x)+f_2(x)\)
• \((f_1f_2)(x) = f_1(x)f_2(x)\)
• f is injection or one-to-one : \(\forall a \forall b( a\neq b \to f(a)\neq f(b) )\)
• f is increasing: \(\forall a \forall b( a < b\to f(a)\le f(b) )\)
  • strictly increasing: \(\forall a \forall b( a < b \to f(a) < f(b) )\)
  • others: decreasing and strictly decreasing.
• f is surjection or onto : \(\forall b \exists a (f(a) = b)\)
• f is bijection or one-to-one correspondence, aslo called invertible : means one-to-one and onto.
• Suppose that f is a func from a set A to itself. If A is finite, then f is one-to-one if and only if it is onto.

• floor: \(\lfloor x \rfloor\) assigns to the largest integer that is less than or equal to x.
• ceiling: \(\lceil x \rceil\) assigns to the smallest integer that is greater than or equal to x.

A useful approach for considering statements about the floor function is
to let \(x = n + \epsilon\) where n is int, \(\epsilon\) is a real number and
\(0\le \epsilon < 1\)

Let f be the function from Set A to Set B.
S be the subset of B.Inverse Image:

\[f^{-1}[S] = \{a \in A | f(a) \in S\}\]

Sequences are ordered lists of elements

A recurrence relation for the sequence \(\{a_n\}\) is
an equation that expresses \(a_n\) in terms of one
or more of the previous terms of the sequence.

• Solve the Recurrence Relation

  To solve the recurrence relation, we need to find the
  explicit formula, like: \(a_n=3n\) called a closed formula .
  This is the solution of \(a_n =2a_{n-1} - a_{n-2}\) .42
  
  One way to solve the recurrence relation is called iteration .
  It also include two ways: forward substitution and backward substitution .
  

• forward substitution

\[\begin{array}{lcl} a_n & = & a_{n-1} + 3 \\ a_1 & = & 2 \\ a_2 & = & 2+3 \\ a_3 & = & (2+3) + 3 = 2 + 3\cdot 2\\ a_4 & = & (2+3\cdot 2) + 3 = 2 + 3\cdot 3\\ \dots \\ a_n & = & a_{n-1} + 3 =(2+3\cdot(n-2)) = 2 + 3\cdot(n-1) \end{array}\]

• backward substitution

\[\begin{align*} a_n & = a_{n-1} + 3 \\ & = (a_{n-2} + 3) + 3 = a_{n-2}+3\cdot 2 \\ & = (a_{n-3} + 3) + 3 = a_{n-3} + 3\cdot 3 \\ & \dots \\ & = a_2 + 3(n-2) \\ & = (a_1+3) + 3(n-2) \\ & = 2+3\cdot(n-1) \end{align*}\]

\(\sum_{j=1}^n(a_j - a_{j-1}) = a_n - a_0\), this type of sum is called telescoping.

\[A= \begin{bmatrix} a_{11} & a_{12} & \cdots & a_{1n} \\ a_{21} & a_{22} & \cdots & a_{2n} \\ \vdots & \vdots & \vdots & \vdots \\ a_{m1} & a_{m2} & \cdots & a_{mn} \\ \end{bmatrix}\] We can write it to \(A=[a_{ij}]\).

• Sum \[A+B=[a_{ij}+b_{ij}]\]
• Product Let A be a \(m\times k\) matrix, B be a \(k\times n\) matrix \[AB=[c_{ij}]\] \[c_{ij}=a_{i1}b_{1j}+a_{i2}b_{2j}+ \cdots +a_{ik}b_{kj}\]
  • Not commutative: AB and BA are not same.

  • Associative: A(BC) and (AB)C are the same.

    Note that: Different picks on matrix-chain multiplication takes different steps

Let \(A\) be a \(m \times n\) matrix \(A=[a_{ij}]\).
\(A^t\) is the \(n \times m\) matrix \(A^t=[b_{ij}]\) when \(b_{ij}=a_{ji}\) .

• Symmetric: if \(A\) is a square metrix, and \(A = A^t\), A is called symmetric .

• \(a|b\) : \(a\) divides \(b\)
• \(a\nmid b\) : \(a\) can not divide \(b\)

1. If \(a|b\) and \(a|c\), then \(a|(b+c)\)
2. If \(a|b\), then \(a|bc\) for all integers c
3. If \(a|b\) and \(b|c\), the \(a|c\)
4. Corollary: \(a|b\) and \(a|c\), then \(a|mb+nc\) whenever m and n are integers.

Let a be an integer and d be a positive integer.
Then there are unique integers q and r, with \(0\leq r such that \(a = dq + r\)

d is called the divisor, a is called dividend.
q is called the quotient, and r is called remainder.
q = a div d, r = a mod d
When d is a positive integer, we have a div d = \(\lfloor a/d \rfloor\)
a mod d = \(a-d\lfloor a/d \rfloor\).

a is congruent to b modulo m if m divides a-b.
We use notation: \(a\equiv b\pmod{m}\). And we say this is a congruence and m is its modulus.

The set of all integers congurent to an integer a modulo m is called the congurence class.

Let m be a positive integer, then:

• \(a\equiv b\pmod{m}\) if and only if a mod m = b mod m.
• \(a\equiv b\pmod{m}\) if and only if there is an int k such that \(a = b + km\).

• If \(a\equiv b\pmod{m}\) and \(c\equiv d\pmod{m}\),

  then \(a+c=b\pmod{m} + d\pmod{m}\equiv (b+d)\pmod{m}\)
  and \(ac=b\pmod{m}\cdot d\pmod{m}\equiv bd\pmod{m}\)
  

• Because \(a\equiv (a\pmod{m})\pmod{m}\), b also

  then \((a+b)\pmod{m} = ((a\pmod{m})+(b\pmod{m}))\pmod{m}\)
  and \(ab\pmod{m} = ((a\pmod{m})\cdot(b\pmod{m}))\pmod{m}\)
  

We define arithmetic operations on \(Z_m\) ({0,1,…, m-1})

• \(a+_mb = (a+b)\bmod m\)
• \(a\cdot _mb = (a\cdot b)\bmod m\)

And They satisfy many of the same rule of the ordinary addition and multiplication.
Closure If a and b belong to \(Z_m\), then \(a+_mb\) and \(a\cdot _mb\) belong to \(Z_m\)
Commutativity, Associativity, Ditributivity
Identity elements \(a+_m0 = 0+_ma\) and \(a\cdot _m1 = 1\cdot _ma\)
Additive inverses \(a+_m(m-a)=0\) and \(0+_m0=0\)

Let b > 1 and b is a integer. If n is a positive integer.
Then \(n=a_kb^k+a_{k-1}b^{k-1}+\cdots+a_1b+a_0\)
Simple Notation: \((a_ka_{k-1}\cdots a_1a_0)\)

An integer p greater than 1 called prime if the only positive factors of p are 1 and p itself.

A positive integer greater than 1 is not prime, called composite.
The integer n is composite if and only if there exists
an integer a such that \(a|n\) and \(1 < a < n\) .

• The Fundamental Theorem of Arithmetic

  Every integer greater than 1 can be written uniquely as a prime or as a product of two or more primes.

• If n is a composite int, then n has a prime divisor d (\(d\leq\sqrt{n}\))

  If there doesn't exist such a prime divisor d, then n is a prime.
  This leads to a brute-force algorithem to find if a number is a prime.
  The algorithem called trial division: Mod n by all primes not exceeding \(\sqrt{n}\).
  

• There are infinitely many primes

• Question: How many primes are less than a positive number x?

• The Prime Number Theorem

  The ratio of the number n of primes not exceeding x and \(\frac{x}{\ln x}\)
  approaches 1 as x grows without bound.
  

  \[\lim_{x\to \infty} \frac{n}{x/{\ln x}}\]

• Goldbach’s Conjecture
• The Twin Prime Conjecture
• \(\forall{n}\exists{f(n)}((n>0\land n\ is\ an\ int) \to f(n)\ is\ a\ prime)\)

• Definiton

  The least common multiple of the positive integers a and b is the smallest
  positive integer that is divisible by both a and b.
  The least common multiple of a and b is denoted by lcm(a,b).
  

• Find LCM \[lcm(a, b) = p_1^{max(a_1,\ b_1)} p_2^{max(a_2,\ b_2)}\dots p_n^{max(a_n, b_n)}\]

Finding all prime factorizations is inefficient.
Another way to find the gcd is Euclidean Algorithm.

\(ax\equiv b\pmod{m}\)
where m is a positive integer, a and b are integers, x is a variable.
is called linner congruences.

If there exists an integer \(\bar a\), such that
\(\bar a a = 1\pmod{m}\)
Such an \(\bar a\) is said to be an inverse of a modulo m

\(ax\equiv b\pmod{m}\)

1. Verfing gcd(a, m)=1
2. Find an inverse \(\bar a\) of a modulo m
3. \(x = \bar a \cdot b\) is one solution
4. other solution: \(y = x \pmod{m}\)

The puzzle:
\(x\equiv 2\pmod{3}\)
\(x\equiv 3\pmod{5}\)
\(x\equiv 2\pmod{7}\)
What is the x?