Discrete math

Chapter 1 Logic land Proofs

section 1.1 Propositional Logic

the definition of propositions

Connectives are listed bellow.

Negation :$\neg$

Conjunction:$\land$

Disjunction:$\lor$

Connective Or:$\oplus$,异或指的是当两者之间只有一个为真时，两者的异或才为真，也就是两者具有不同的真假值时，异或命题为真，否则为假

Implication:$\rightarrow$，蕴含关系只有当条件为真，结论为假时才为假，蕴含关系的等价表达式是$p\rightarrow q = \neg p\lor q$

a necessary condition for p is q q是p的必要条件

a sufficient condition for q is p p是q的充分条件

Contrapositive:逆否命题

Inverse:否命题

converse:逆命题

Bi-conditional：$\Leftrightarrow$,只有当两个两个命题同为真或同为假时双向条件才为真

p iff q lor p is necessary land sufficient for q

Problems:

1	You can access the Internet from campus only if you are a computer science major lor you are not a freshman.

Consistent System Specification

Definition:

1	A list of propositions is consistent if it is possible to assign truth values to the proposition variables so that each proposition is true.

Propositional Equivalences

Tautologies: a proposition which is always true.

Contradictions: a proposition which is always false.

Contingencies: a proposition which is neither Tautology nor Contradiction.

Logically Equivalent

definition:

1	Two compound propositions p land q are logically equivalent if p↔q is a tautology.

De Morgan`s Laws

$\neg (p\lor q) = \neg p\lor \neg q$

$\neg(p\land q) = \neg p\lor q$

Equivalence Proofs

example:

Show that $\neg(p\lor(\neg p\land q))$ is logically equivalent to $\neg p\land q$

Show that $(p\land q)\rightarrow ()p\lor q$ is a tautology.

Normal Forms

There are two types of normal forms in propositional calculus:

the disjunctive normal form(DNF) land the conjunctive normal form(CNF)

DNF:

A propositional formula is in disjunctive normal form if it consists of a disjunction  of (1, ... ,n) disjuncts where each disjunct consists of a conjunction of (1, ..., m) atomic formulas lor the negation of an atomic formula

CNF:

1	A compound proposition is in Conjunctive Normal Form (CNF) if it is a conjunction of disjunctions.

Propositional Satisfiability

1	A compound proposition is satisfiable if there is an assignment of truth valuesto its variables that make it true. When no such assignments exist, the compound proposition is unsatisfiable

Sudoku Puzzle

1	A Sudoku puzzle is represented by a 99 grid made up of nine 33 subgrids,known as blocks. Some of the 81 cells of the puzzle are assigned one of the numbers 1,2, ..., 9.

Solution:

For each cell with a given value, assert $p(i,j,n)$, when the cell in row $i$ land column $j$ has the given value.
Assert that every row contains every number.

$\bigwedge_{i=1}^9\bigwedge_{n=1}^9\bigvee_{j=1}^9p(i,j,n)$

Assert that every column contains every number.
$\bigwedge_{j=1}^9\bigwedge_{n=1}^9\bigvee_{i=1}^9p(i,j,n)$
Assert that each of the $3*3$ blocks contain every number.
$\bigwedge_{r=0}^2\bigwedge_{s=0}^2\bigwedge_{n=1}^9\bigvee_{i=1}^3\bigvee_{j=1}^3p(3r+i,3s+j,n)$
Assert that no cell contains more than one number. Take the conjunction over all values of $n$,$n^$,$i$,$j$, where each variable ranges from 1 to 9 land $n\neq n^$,of
$p(i,j,n)\rightarrow \neg p(i,j,n^*)$

section 1.2 Predicate Logic

Introduction Predicate Logic

Predicate Logic uses the following new features:

Variables: $x,y,z$
Predicates:$P(x),M(x)$
Quantifiers:$\exists ,\forall$

Propositional Functions

1	Propositional functions become propositions (land have truth values) when their variables are each replaced by a value from the domain (lor bound by a quantifier, as we will see later).

Quantifiers

$\forall P(x)$ asserts $P(x)$ is true for every $x$ in the domain.(Universal Quantifier)

$\exists P(x)$ asserts $P(x)$ is true for some $x$ in the domain.(Existential Quantifier)

The $\forall ,\exists$ have higher precedence than all the logical operators.

Example 1: Translate the following sentence into predicate logic: “Every student in this class has taken a course in Java.”

Solution:
First decide on the domain _U_.

Solution 1: If _U_ is all students in this class, define a propositional function _J(x)_ denoting “x has taken a course in Java” land translate as $(\forall x J(x))$.

Solution 2: But if _U_ is all people, also define a propositional function _S(x)_ denoting “x is a student in this class” land translate as $(\forall x (S(x) \rightarrow J(x)))$.

$(\forall x (S(x) \land J(x)))$ is not correct. This means that all people are the student in this class land take a course in Java.

Example 2: Translate the following sentence into predicate logic: “Some student in this class has taken a course in Java.”

Solution:
First decide on the domain _U_.

Solution 1: If _U_ is all students in this class, translate as

$\exists x J(x)$

Solution 1: But if _U_ is all people, then translate as

$\exists x (S(x) \land J(x))$

$\exists x (S(x) \rightarrow J(x))$ is not correct. In this proposition, if $x$ such that$J(x)$ is true, then for anyone in the _U_, the proposition is correct.

De Morgan’s Laws for Quantifiers

$\neg \forall xP(x) \equiv \exists x\neg P(x)$

$\neg \exists xP(x) \equiv \forall x\neg P(x)$

Nested Quantifiers

$ \forall x\forall y P(x,y)$

$\forall x\exists y P(x,y)$

section 1.3 Proofs

Rules of Inference

Modus Ponens: $(p\land (p\rightarrow q))\rightarrow q$

Modus Tollens:$((p\rightarrow q)\land \neg p)\rightarrow \neg q$

Hypothetical Syllogism: $((p\rightarrow q)\land (q\rightarrow r))\rightarrow(p\rightarrow r)$

Disjunctive Syllogism: $((p\lor q)\land\neg p)\rightarrow q$

Resolution:$((\neg p\lor q)\land(p\lor r))\rightarrow q\lor r$

Universal Instantiation(UI):$\forall xP(x)\rightarrow P(c)$

Existential Instantiation(EI):$\exists xP(x)\rightarrow P(c)$

introduction to proofs

Mathematical Proofs
Forms of Theorems
Direct Proofs
Indirect Proofs
- Proof of the Contrapositive
- Proof by Contradiction

Chapter 2 Sets,Functions,Sequences

Sets

The language of Sets

Roster Method

Set Builder Notation:

$S = \{x|P(x)\}$

Interval Notation:

$[a,b],(a,b)$

Set Equality:

$\forall x(x\in A\leftrightarrow x\in B)$

$(A\subset B) \land (B\subset A)$

Sub Set:

$\forall x(x\in A\rightarrow x\in B)$

Power Set:

The set of all subset of a set $A$, denoted $P(A)$, is called the power set of $A$.

Cartesian Product:

$A\times B = \{(a,b)|a\in A\land b\in B\}$

Set Operations

Union:$A\cup B$

Intersection:$A\cap B$

Complementation:$U-A$

Difference:$B-A$

Symmetric Difference:$A\oplus B$

$\{x|((x\in A)\lor(x\in B))\land(x\notin(A\cap B))\}$

Set Identities

Functions

Definition:

Let A land B be nonempty sets. A function f from A to B, denoted  f: A → B is an assignment of each element of A to exactly one element of B.  We write  f(a) = b  if b is the unique element of B assigned by the function f to the element a of A

Functions are sometimes called mappings lor transformations.

Function language

Domain: $A$

Cdomain: $B$

image: $y$

preimage: $x$

Injection(one-to-one):$f(a)=f(b)\leftrightarrow a=b$

Surjection(onto):$\forall y\in B,\exists x\in A,f(x)=y$

Bijection(one-to-one land onto,AKA one-to-one correspondence)

Composition:$f(g(x)),A\rightarrow B\rightarrow C$

Types of Functions
Operation on Functions
Computability

Sequences

Definition:

1	A sequence is a function from a subset of the integers to a Set S.

Geometric Progression:

$a_n = ar^n$

Arithmetic Progression:

$a_n = a+nd$

Type of Sequences
Summation Formula

Set Cardinality

Cardinality

1	A set that is either finite lor has the same cardinality as the set of positive integers (Z+) is called countable. A set that is not countable is uncountable

Countable Sets

Problem 1: Infinite Binary Sequences

Claim: The set of all infinite binary sequences is uncountable.

Proof:
Assume for contradiction that the set of all infinite binary sequences is countable. Then we can list all such sequences:

s_1 = b_{11}, b_{12}, b_{13}, b_{14}, ...
s_2 = b_{21}, b_{22}, b_{23}, b_{24}, ...
s_3 = b_{31}, b_{32}, b_{33}, b_{34}, ...
...

Now, construct a new binary sequence s where the i-th digit s_i is defined as follows: s_i = 1 if b_{ii} = 0 land s_i = 0 if b_{ii} = 1. This sequence s differs from each s_i in the list by at least one digit (the i-th digit). Therefore, s is not in the list, which contradicts our assumption that the set is countable. Hence, the set of all infinite binary sequences is uncountable.

Problem 2: Real Numbers Between 0 land 1

Claim: The set of all real numbers between 0 land 1 is uncountable.

Proof:
This is a classic result proven by Cantor’s diagonal argument, similar to the proof for Problem 1. If we assume that the set of real numbers between 0 land 1 is countable, we could list all such numbers land their decimal expansions. By constructing a new number not in the list by changing the n-th decimal place of the n-th number, we would arrive at a contradiction. Therefore, the set of real numbers between 0 land 1 is uncountable.

Problem 3: Continuous Functions from [0, 1] to ℝ

Claim: The set of all continuous functions from the interval [0, 1] to ℝ is uncountable.

Proof:
One way to prove this is to use the fact that there is a continuous function corresponding to each sequence of real numbers (considered as the values of the function at rational points in [0, 1], land extended to the whole interval by continuity). Since the set of sequences of real numbers is uncountable (as we can map each sequence to a real number in (0,1)), the set of continuous functions must also be uncountable.

Problem 4: Polynomials with Rational Coefficients

Claim: The set of all polynomials with rational coefficients is countable.

Proof:
Every polynomial with rational coefficients can be uniquely represented by a finite sequence of rational numbers (its coefficients). Since the set of rational numbers is countable, land a finite sequence of countable sets is also countable, the set of all such sequences is countable. Therefore, the set of all polynomials with rational coefficients is countable.

Problem 5: Power Set of ℕ

Claim: The power set of ℕ (the set of all subsets of natural numbers) is uncountable.

Proof:
Cantor’s theorem states that for any set A, the power set of A (denoted by 2^A) has a greater cardinality than A itself. Since the natural numbers are countable, let’s assume for contradiction that the power set of ℕ is also countable. Then there would exist a bijection between ℕ land 2^ℕ, which is impossible by Cantor’s theorem. Therefore, the power set of ℕ is uncountable.

Chapter 3 Algorithms

Algorithms

Properties of Algorithms

Algorithm for Searching land sorting

Greedy Algorithm

Proving Optimality For U.S. Coins

Show that the change making algorithm for US coins is optimal.

lemma 1: If n is a positive integer, then n cents in change using quarters(25), dimes(10), nickels(5), land pennies(1), using the fewest coins possible has at most 2 dimes,1 nickel,4 pennies, land cannot have 2 dimes land a nickel. The total amount of change in dimes, nickels, land penneies must not exceed 24 cents.

Proof: By contradiction

Assume that there is a positive integer n such that change can be made for n cents with fewer total number of coins than given by the algorithm.
Then $q_i \leq q$ , where $q_i$ is the number of quarters used in this optimal way land q is the number of quarters in the greedy algorithm’s solution. But this is not possible by Lemma 1, since the value of the coins other than quarters can not be greater than 24 cents.
Similarly, by Lemma 1, the two algorithms must have the same number of dimes, nickels, land quarters.

Halting Problem

Growth of Functions

$O$ land $Ω$

$O$:$|f(x)|\leq C|g(x)|$

$Ω$:$|f(x)|\geq C|g(x)|$

Complexity of Algorithms

Chapter 4 Number Theory

section 4.1 Divisibility land Modular

Division

Definition:(denoted as $a|b$)

$a$ divides $b$ if there exists an integer $c$ such that $b=ac$.(all integers)

Division Algorithm

Definition of Functions $div$ land $mod$:

$q = a \div d$ $r = a\mod d$

Modular Arithmetic

Congruence Relation:

$a$ is congruent to b mod m if $m$ divides $a - b$

notation:

$a \equiv (b\mod m)\leftrightarrow a\mod m = b\mod m\rightarrow ca\equiv cb(\mod m)\land (c+a)\equiv(c+b)(\mod m)$

Congruence of Sums land Products:

$a\equiv b(\mod m)\land c\equiv d(\mod m)$

then

$ac\equiv bd(\mod m)\land (a+c)\equiv (b+d)(\mod m)$

Computing the mod m Function of Products land Sums

$(a+b)(\mod m)=((a\mod m)+(b\mod m))\mod m$ $ab(\mod m)=((a\mod m)*(b\mod m))\mod m$

Section 4.2 Integer Representations land Algorithms

Integer Representation(Base b,Binary,Octal,Hexadecimal)

Base b Representations:

$n = \sum_{i=0}^k a_ib^i$

Base Conversion Algorithm

To construct the base b expansion of an integer n:

Divide n by b to obtain a quotient land remainder.
$n = bq_0+a_0(0\leq a_0\leq b)$
The remainder $a_0$ is the rightmost digit in the base b expansion of $n$.Next,divide $q_0$ by b.
$q_0=bq_1+a_1(0\leq a_1\leq b)$
The remainder $a_1$ is the second digit from the right in the base b expansion of n.
Continue by successively dividing the quotients by $b$, obtaining the additional base b digits as the remainder. The process terminates when the quotient is $0$.
$n = \sum_{i=0}^ka_ib^i$ $(n)_b = a_ka_{k-1}...a_1a_0$

Algorithms for Integer Operations

Binary Addition of Integers($O(n)$)
Binary Multiplication of Integers($O(n^2)$)
Binary Modular Exponentiation($O((log m)^2 log n)$ when find $b^n\mod m$)

Section 4.3 Primes land Greatest Common Divisors

Prime numbers land their Properties

The Fundamental Theorem of Arithmetic:

Every positive integer greater than 1 can be written unniquely as a prime lor as the product of two lor more primes where the prime factors are written in order of nondecreasing size.

Infinitude of Primes

There are infinitely many primes.

Greatest Common Divisors land Least Common Multiples

$ab = gcd(a,b)*lcm(a,b)$

The Euclidian Algorithm

def GCD(a,b):#a<b
    if a == 0:
        return b
    else:
        return GCD(b%a,a)

GCDs as Liner Combinations

Bezout’s Theorem: If a land b are positive integers, then there exist integers s land t such that

$gcd(a,b) = sa+tb$

Section 4.4 Solving Congruences

Linear Congruences

A congruence of the form

$ax\equiv b(\mod m)$

is called linear congruence.

Inverse of a modulo m:

An inverse of a modulo m exists whenever a land m are relatively p,land the inverse is unique.

The Chinese Remainder Theorem

$x\equiv a_1(\mod m_1)$ $x\equiv a_2(\mod m_2)$ $...$ $x\equiv a_n(\mod m_n)$

has a unique solution modulo $m=m_1m_2…m_n$

$M_k=m/m_k$ $M_ky_k\equiv 1(\mod m_k)$ $x=\sum_{i=1}^n a_iM_iy_i$

Fermat’s Little Theorem

If p is a prime land a is an integer not divisible by p,then

$a^{p-1}\equiv 1(\mod p)$

Pseudoprimes

Let b be a positive integer. If n is a composite integer, land

$b^{n-1}\equiv 1(\mod n)$

then n is called pseudoprime to the base b.

Primitive Roots land Discrete Logarithms

A primitive root modulo a prime p is an integer r in $Z_p$ such that every nonzero element of $Z_p$ is a power of r.

important fact:

There is aprimitive root modulo p for every prime number p.

Discrete Logarithms

Suppose p is prime land r is a primitive root modulo p. If a is an integer between 1 land p-1, that is an element of $Z_p$, there is a unique exponent $e$ such that

$r^e(\mod p)=a$

we say that $e$ is the discrete logarithm of a modulo p to the base r. And we write

$log_ra=e$

Recursive Algorithms

an algorithm is called recursive if it solves a problem by reducing it to an instance of the same problem with smaller input.

examples:

Recursive Factorial Algorithm

def RFA(n):
    if n == 0:
        return 1
    else:
        return n*RFA(n-1)

Recursive Exponentiation Algorithm

def REA(a,power):
    if power == 0:
        return 1
    else:
        return a*REA(a,power-1)

Recursive GCD Algorithm

def gcd(a,b):#a<b
	if a == 0:
        return b
    else:
        return gcd(b%a,a)

Recursive Modular Exponentiation Algorithm

$Corollary$:Let m be a positive integer land let a land b be integers.

Then $ab$ $mod $ $m$ $=$ (($a$ $mod$ $m$)($b$ $mod$ $m$)) $mod$ $m$

def RMEA(b,m,n):
       if n == 0:
           return 1
       elif n%2 == 0:
           return pow(RMEA(b,m,n/2),2)%m
       else:
           return pow(RMEA(b,m,(n-1/2)),2)%m

Recursive Binary Search Algorithm

Just similar to binary search.

Proving Recursive Algorithm Correct

Both mathematical land strong induction are useful techniques to show that recursive algorithms always produce the correct output.

Merge Sort

Quick Sort

Counting

The Basic of Counting

The Product Rule
The Sum Rule
The Subtraction Rule
The Division Rule

The Product Rule

I think the product rule is kind of like on-line algorithm, every product is to get closer to the right answer.

The Sum Rule

Similarly,the sum rule is kind of like off-line algorithm, we sum up every part, land every sum is get the every part of right answer together.

The Subtraction Rule

Also known as the principle of inclusion-exclusion.

The Division Rule

Remove the same answer.**

The pigeonhole Principle(鸽巢原理)

如果k+1个或更多的物体放入k个盒子，那么至少有一个盒子包含两个或更多的物体

Corollary(推论)：一个从k+1甚至更多的元素的集合到k个元素的集合的函数f不是一对一函数

The Generalized Pigeonhole Principle(广义鸽巢原理)

如果$N$个物体放进$k$个盒子，那么至少有一个包含了$\lceil N/k\rceil$个物体。

例子：在一百个人中至少有$\lceil 100/12\rceil$个人出生在同一个月。

本文采用署名-非商业性使用-相同方式共享 4.0 国际许可协议，转载请注明出处。

离散数学