Discrete Maths
Discrete maths is the foundation of computer science. It is particularly important for algorithm and compiler design.Mathematical Induction
Principal of mathematical induction
Where P(n) is a function taking a natural number and returning a boolean result:
Base case If P(1) is true and
Induction step Whenever P(n) is true, P(n+1) is true
Conclusion P(n) is true for every natural number n.
For example, 1 + 3 + 5 + ... + (2n-1) = n2:
Base case 2x1 1 = 12
Induction step [ 1 + 3 + 5 + ... + (2n-1) ]+ (2(n+1) -1) = [n2 ] 2n +1 = (n+1)2
Conclusion 1 + 3 + 5 + ... + (2n-1) = n2
Proof of mathematical induction
This is done by showing the smallest x such that not P(x) is proved by P(x-1)
-which is to small to be not P(x) and proves it as P(x) ? P(x + 1)
1 Assume P(0)
2 Assume for all n = 0, P(n) ? P(n + 1)
3 Assume for all m = 0 (natural numbers), P(m) is false
ie There exists an m such that not P(m)
We now prove that if 1 and 2 are true, then 3 is false, hence P(m) is true for all natural numbers
Let x be the smallest value such that not P(x)
By rule one, x can't be zero
As x is the smallest not P, P(x-1), but by 2 this gives a contradiction as P(x) ? P(x + 1)
Course of values induction
Induction step Whenever P(k) can be inferred from the truth of P(j) for all j < k
Conclusion P(n) is true for every natural number n
Note the lack of base case
Relations
A relation R on A is defined to be R A x A
|
|
|---|---|
|
Note that 'antisymmetric' is not the logical negative of 'symmetric' (whereby aRb implies bRa). |
|
|
|
|
|
|
Partial order:
A partial order is a binary relation R over a set P which is reflexive, antisymmetric, and transitive
Examples:
The set of natural numbers equipped with the lesser than or equal to relation, or with the divisibility relation is a partial order. Under divisibility there is a lower (lcm) and upperbound (gcd)
If (A, <A) and (B,<B) are partially ordered sets, then the product order is
(a1 <A a2) ^ (b1 <A b2) <-> (a1, b1) < (a2, b2)
ie Its just the Cartesian (normal multiplication) product of the two orders.
You can prove AxB is a partial order as follows:
reflexive as (a,b) < (a,b)
A and B are antisymmetric, so a1< a2 and a2< a1 so a1=a2 (same with b's) so
(a1,b1)=(a2,b2)
a1<Aa2<Aa3 so a1<Aa3 because <A is transitive, same with b's
(a1,b1)
Divisibility is a partial order:
reflexive a|a
antisymmetric a|b => b
|atransitive a|b and b|c => a|c
To prove something is a least upper bound, assume there is a lower upper bound, then it divides the elements and either divides the LUB or is the LUB: contradiction. Simliar argument for greatest lower bound.
is a partial order:
reflexive AA
anti symmetric A B B A=> B=A
transitive A B B C => A C
Given A,B X the greatest lower bound is A B and the lowest upper bound is A n B.
This is proved by letting C be g|b, C X and by entailment show either CAB or A n BC
The greatest lower bound of AxB = ( glb(a1,a2) ,glb(b1,b2) )
Subsets including of 0 dont have an upper bound, as 0 doesn't divide natural numbers (when using the divide operator as the PO).
N has no least upper bound (as there is no number bigger than the largest in N), but a greatest lower bound. Its subsets have both.
Lattices:
A lattice is a partially ordered set where every pair of elements has both a least upper bound and a greatest lower bound.
Well founded relation
A well founded relation on a set A is a relation A x A such that there are no infinitely descending chains.
Any non-empty subset S of a well-founded (relation) set A has a minimal element: Pick an element a0, if it is minimal then stop. Otherwise pick a1 a0. If minimal stop, if not then pick a2 a1. This can't continue for ever as is well founded, therefore there must be a minimal element.
If two relations <A on A and <B on B are well founded show that the relation and product relation on AxB are both well founded:
Consider projection of product order into A -> find minimum.
Consider proection into B-> find minimum.
Show minimal
Observe <L <P
Total order
A total order on a set X is any binary relation on X that is antisymmetric, transitive, and total. This means that if we denote one such relation by = then the following statements hold for all a, b and c in X:
if a = b and b = a then a = b (antisymmetry)
if a = b and b = c then a = c (transitivity)
a = b or b = a (totality)
A relation's property of "totality" can be described this way: that any pair of elements in the set are mutually comparable under the relation.
Notice that the totality condition implies reflexivity, that is a = a. Thus a total order is also a partial order, that is, a binary relation which is reflexive, antisymmetric and transitive.
The lexicographical order on the product of a set of totally ordered sets indexed by an ordinal (indexing number, eg first, second etc.) is itself a total order.
For example, any set of words ordered alphabetically is a total order, viewed as a subset of a product of a countable number of copies of a set formed by adding the space symbol to the alphabet (and defining a space to be less than any letter).
A totally ordered set is said to be complete if every subset that has an upper bound, has a least upper bound.
Equivalence relation
An equivalence relation on a set X is a binary relation on X that is reflexive, symmetric, and transitive. That is, if the relation is denoted by the symbol "~", it holds for all a, b, and c in X that
(Reflexivity) a ~ a
(Symmetry) if a ~ b then b ~ a
(Transitivity) if a ~ b and b ~ c then a ~ c
If two equivalence relations over the set X are given, then their intersection (viewed as subsets of X×X) is also an equivalence relation.
An introduction to Discrete Mathematics
Introduction
Discrete maths is the foundation of computer science. It is particularly important for algorithm and compiler design.Sets
|
N0 = {0, 1, 2, } |
Natural numbers with 0 |
|
Z = { , 2, 1, 0, 1, 2, } |
Integers |
|
Q |
(Rational) Fractions |
|
R |
Real numbers |
|
Ψ = {} |
The empty set |
|
x ? X |
x is an element of the set X |
|
X ? Y N ? N0 ? Z ? Q ? R.
|
One set, X, is a subset of another set, Y, if every element of X is also an element of Y. We write this with a rounded less-than-or-equal sign |
|
N = {x ? Z | x > 0} |
The set of integers that satisfy the predicate x>0 |
Key types of relations:
Injective: Each y, y=f(x), can only come from one unique x. Eg; f(x)=2+1 is, x2 is not.
Surjective: Each y in the codomain is defined by at least one x. Eg; x2 for R isn't (x2=-1)
Bijective: One-one: injective and bijective. Eg; Identity function,g(x) = x2 isn't: not injective
Relations: A relation R on A is defined to be R ? A x A. Note (a,b) ?R can be written aRb
Reflexive:A relation where ?a?A (a,a)?R,ie where ?x, x->x (all x relate to x) Eg;=,<,?,| Antisymmetric: If a relates to b,and b relates to a then a=b Eg; a1< a2,a2< a1 so a1=a2 Symmetric: If f(x)=y, then f(y)=x, eg; equals, ... is married to ... Transitive: If aRb and bRc then aRc Eg; Divisibility: a|b and b|c => a|c
Preorder - a transitive relation that is also reflexive.
Partial order - a preorder that is antisymmetric.
Equivalence relation - a relation that is a preorder and symmetric.
Well ordering
This uses the fact that with N
there is always a smallest element.Fundamental theorem of Arithmetic, by Well Ordering
Proof, by contradiction:
S = {n ? N | n
Let s ? S be its smallest element. s can not be prime, since it is in S, so:
s = ab for some a, b ? N with 1 < a, b < s.
a and b are smaller than the least element of S, and so can not be in S
So a and b can be written as products of primes, but combining a and b gives s from primes
Contradiction
Proof, by mathematical induction:
1 P(n) is the statement there is no element of N smaller than n
2 Base case: P(0) is true, as there are no natural numbers smaller than 0
3 Assume P(n) is true
If P(n+1) were false, then theres a smaller element than (n+1) but it must be bigger than n as P(n) is true. So there is a minimal element n
By induction, if P(n) implies P(n+1) for all n, then P(n) is true for all n