skip to content

Search

离散数学

13 min read

这篇文章介绍了离散数学的基本概念和逻辑推理方法,包括命题逻辑、谓词逻辑、证明方法等内容。

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,蕴含关系只有当条件为真,结论为假时才为假,蕴含关系的等价表达式是pq=¬pqp\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:

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:

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:

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

De Morgan`s Laws

¬(pq)=¬p¬q\neg (p\lor q) = \neg p\lor \neg q

¬(pq)=¬pq\neg(p\land q) = \neg p\lor q

Equivalence Proofs

example:

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

Show that (pq)()pq(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:

A compound proposition is in Conjunctive Normal Form (CNF) if it is a conjunction of disjunctions.
Propositional Satisfiability
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

A Sudoku puzzle is represented by a 9*9 grid made up of nine 3*3 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)p(i,j,n), when the cell in row ii land column jj has the given value.
  • Assert that every row contains every number.
i=19n=19j=19p(i,j,n)\bigwedge_{i=1}^9\bigwedge_{n=1}^9\bigvee_{j=1}^9p(i,j,n)
  • Assert that every column contains every number.

    j=19n=19i=19p(i,j,n)\bigwedge_{j=1}^9\bigwedge_{n=1}^9\bigvee_{i=1}^9p(i,j,n)
  • Assert that each of the 333*3 blocks contain every number.

    r=02s=02n=19i=13j=13p(3r+i,3s+j,n)\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 nn,nn^*,ii,jj, where each variable ranges from 1 to 9 land nnn\neq n^*,of

    p(i,j,n)¬p(i,j,n)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,zx,y,z
  • Predicates:P(x),M(x)P(x),M(x)
  • Quantifiers:,\exists ,\forall

Propositional Functions

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

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

P(x)\exists P(x) asserts P(x)P(x) is true for some xx 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 (xJ(x))(\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 (x(S(x)J(x)))(\forall x (S(x) \rightarrow J(x))).

(x(S(x)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 xJ(x)\exists x J(x)

Solution 1: But if U is all people, then translate as x(S(x)J(x))\exists x (S(x) \land J(x)) x(S(x)J(x))\exists x (S(x) \rightarrow J(x)) is not correct. In this proposition, if xx such thatJ(x)J(x) is true, then for anyone in the U, the proposition is correct.

De Morgan’s Laws for Quantifiers

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

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

Nested Quantifiers

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

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

section 1.3 Proofs

Rules of Inference

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

Modus Tollens:((pq)¬p)¬q((p\rightarrow q)\land \neg p)\rightarrow \neg q

Hypothetical Syllogism: ((pq)(qr))(pr)((p\rightarrow q)\land (q\rightarrow r))\rightarrow(p\rightarrow r)

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

Resolution:((¬pq)(pr))qr((\neg p\lor q)\land(p\lor r))\rightarrow q\lor r

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

Existential Instantiation(EI):xP(x)P(c)\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={xP(x)}S = \{x|P(x)\}

Interval Notation:

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

Set Equality:

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

(AB)(BA)(A\subset B) \land (B\subset A)

Sub Set:

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

Power Set:

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

Cartesian Product:

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

  • Set Operations

Union:ABA\cup B

Intersection:ABA\cap B

Complementation:UAU-A

Difference:BAB-A

Symmetric Difference:ABA\oplus B

{x((xA)(xB))(x(AB))}\{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: AA

Cdomain: BB

image: yy

preimage: xx

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

Surjection(onto):yB,xA,f(x)=y\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)),ABCf(g(x)),A\rightarrow B\rightarrow C

  • Types of Functions
  • Operation on Functions
  • Computability

Sequences

Definition:

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

Geometric Progression:

an=arna_n = ar^n

Arithmetic Progression:

an=a+nda_n = a+nd
  • Type of Sequences
  • Summation Formula

Set Cardinality

  • Cardinality
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:

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

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

  1. 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.
  2. Then qiqq_i \leq q , where qiq_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.
  3. Similarly, by Lemma 1, the two algorithms must have the same number of dimes, nickels, land quarters.

Halting Problem

  • Growth of Functions

OO land ΩΩ

OO:f(x)Cg(x)|f(x)|\leq C|g(x)|

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

  • Complexity of Algorithms

Chapter 4 Number Theory

section 4.1 Divisibility land Modular

  • Division

Definition:(denoted as aba|b)

aa divides bb if there exists an integer cc such that b=acb=ac.(all integers)

  • Division Algorithm

Definition of Functions divdiv land modmod:

q=a÷dq = a \div d r=amoddr = a\mod d
  • Modular Arithmetic

Congruence Relation:

aa is congruent to b mod m if mm divides aba - b

notation:

a(bmodm)amodm=bmodmcacb(modm)(c+a)(c+b)(modm)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:

If

ab(modm)cd(modm)a\equiv b(\mod m)\land c\equiv d(\mod m)

then

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

Computing the mod m Function of Products land Sums

(a+b)(modm)=((amodm)+(bmodm))modm(a+b)(\mod m)=((a\mod m)+(b\mod m))\mod m ab(modm)=((amodm)(bmodm))modmab(\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=i=0kaibin = \sum_{i=0}^k a_ib^i
  • Base Conversion Algorithm

To construct the base b expansion of an integer n:

  1. Divide n by b to obtain a quotient land remainder.

    n=bq0+a0(0a0b)n = bq_0+a_0(0\leq a_0\leq b)
  2. The remainder a0a_0 is the rightmost digit in the base b expansion of nn.Next,divide q0q_0 by b.

    q0=bq1+a1(0a1b)q_0=bq_1+a_1(0\leq a_1\leq b)
  3. The remainder a1a_1 is the second digit from the right in the base b expansion of n.

  4. Continue by successively dividing the quotients by bb, obtaining the additional base b digits as the remainder. The process terminates when the quotient is 00.

    n=i=0kaibin = \sum_{i=0}^ka_ib^i (n)b=akak1...a1a0(n)_b = a_ka_{k-1}...a_1a_0
  • Algorithms for Integer Operations
  1. Binary Addition of Integers(O(n)O(n))
  2. Binary Multiplication of Integers(O(n2)O(n^2))
  3. Binary Modular Exponentiation(O((logm)2logn)O((log m)^2 log n) when find bnmodmb^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)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+tbgcd(a,b) = sa+tb

Section 4.4 Solving Congruences

  • Linear Congruences

A congruence of the form

axb(modm)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
xa1(modm1)x\equiv a_1(\mod m_1) xa2(modm2)x\equiv a_2(\mod m_2) ...... xan(modmn)x\equiv a_n(\mod m_n)

has a unique solution modulo m=m1m2...mnm=m_1m_2...m_n

Mk=m/mkM_k=m/m_k Mkyk1(modmk)M_ky_k\equiv 1(\mod m_k) x=i=1naiMiyix=\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

ap11(modp)a^{p-1}\equiv 1(\mod p)
  • Pseudoprimes

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

bn11(modn)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 ZpZ_p such that every nonzero element of ZpZ_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 ZpZ_p, there is a unique exponent ee such that

re(modp)=ar^e(\mod p)=a

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

logra=elog_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

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

Then abab modmod mm == ((aa modmod mm)(bb modmod mm)) modmod mm

 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(广义鸽巢原理)

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

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