A note on "Discrete Mathematics and Its Applications 4ed" (Kenneth H. Rosen)
The Foundations: Logic, Sets, and Functions
Boolean and bit operations
bit comes from binary digits (by John Tukey)
Data.Bits provides bitwise operations for integers.
For small cases, a truth table can be used to determine two propositions are equivalent or not.
-
universal quantifier
- "for all x P(x)"
- "for every x P(x)"
-
existential quantifier
- "there is an x such that P(x)"
- "there is at least one x such that P(x)"
- "for some x P(x)"
Cantor's naive set theory
-
A function f injective iff (f(x) = f(y) ==> x = y).
-
A function f:A->B is surjective iff B=f(A).
- Example 17 (Cantor's diagonal argument)
-
Big-O Notation f is O(g) iff there exists a constants C and k such that for any x>k, |f(x)| <= C*|g(x)|.
- O(1)
- O(log n)
- O(n)
- O(n * log n)
- O(n^2)
- O(n!)
-
Big-Omega and Big-Theta notation f is Omega(g) iff there exists a constants C and k such that for any x>k, C*|g(x)| <= |f(x)|.
f is Theta(g) iff f is O(g) and f is Omega(g). We say that f is of order g.
The Fundamentals: Algorithms, the Integers, and Matrices
-
An algorithm is a finite set of (precise) instructions ("how to") for performing a computation.
-
Pseudocode = an intermediate step between an English description and an actual programming language.
- procedure statements
- assignments
- block
- comments
- conditional constructions (if, then, else)
- loop constructions (for, while)
-
tractable problems: A problem is called tractable iff there is an algorithm with polynomial (O(n^b) of some b) worst-case complexity. (There is no guarantee that a tractable problem can be solved in a reasonable time.)
-
unsolvable problems: A problem is unsolvable iff no algorithm exists for solving them. The first instance is the famous halting problem (Alan Turing). (See also 4.2 of Haskell road to logic.)
-
class NP: Many solvable problems are believed to have the property that no algorithm with polynomial worst-case time complexity solves them, but a solution, if exists, can be checked in polynomial time. Such a class of problems form the class NP.
-
NP-complete problems: If any of NP-complete problems can be solved by a polynomial worst-case time algorithm, then all the problems can be solved by polynomial worst-case time algorithms. So far no-proof or no-counterexample have been found, it is generally accepted that no NP-complete problem can be solved in polynomial time.
- division
- gcd
- Euclidean algorithm
- Representations of integers
- binary expansion
- binary addition
- binary multiplication
- Extended Euclidean algorithm
- Chinese Remainder Theorem
-
Libraries:
-
Tutorials, Examples, etc
- An introduction: http://dis.um.es/~alberto/hmatrix/hmatrix.html
-
For Bitwise operation, https://hackage.haskell.org/package/base-4.14.0.0/docs/Data-Bits.html My question is how we combine some matrix library (in particular matrix operation with addition and multiplication) and that of boolean (i.e., bitwise).
Mathematical Reasoning
- Rules of inference (infer: to derive as a conclusion from facts or premises)
| Rules | Tautology |
|---|---|
| Addition | p -> (p || q) |
| Simplification | (p && q) -> p |
| Conjunction | ((p) && (q)) -> (p && q) |
| Modus ponens | ( p && (p->q)) |
| Modus tollens | ((not p) && (p->q)) -> (not p) |
| Hypothetical syllogism | ((p->q) && (q->r)) -> (p->r) |
| Disjunctive syllogism | ((p || q) && (not p)) -> q |
-
Methods of proving theorems
- direct proof
- indirect proof
- vacuous proof
False -> q - trivial proof
p -> True - proof by contradiction
- vacuous proof
-
The Halting Problem
- The well-ordering property
Every non-empty set of non-negative integers (i.e., natural numbers) has a least element.
- Mathematical Induction
- Base case: the proposition
p(0)(orp(1)) is shown to be true. - Induction step: the implication
p(n) -> p(n+1)is shown to be true for every positive integer (i.e., a natural number) n.
- Base case: the proposition
Here, the statement P(n) for a fixed n is called the inductive hypothesis.
- The Second Princple of Mathematical Induction
- Base case: the proposition
p(0)(orp(1)) is shown to be true. - Induction step:
(p(0) && .. && p(n)) -> p(n+1)is shown to be true for any n.
- Base case: the proposition
A naive factorial would be
factorial 0 = 1
factorial n = n * factorial (n-1)There exist more efficient and fast algorithms: *FFF of FastFactorialFunctions *A Haskel implementation by konn-san: https://github.com/konn/factorials
- Ulam numbers https://oeis.org/A002858
http://www.rosettacode.org/wiki/Ulam_numbers
My implementation is based on a lazy list. It can give first few hundreds within few second (i.e., extremely slow).
Counting
Adcanced Counting Techniques
We consider a class of recurrence relation in which the recurrence relation is written as a linear combination of previous terms.
- Linear homogeneous recurrence relations A linear homogeneous recurrence relation of degree k with const. coeff. is a recurrence relation of the form:
a(n) = c1*a(n-1) + .. + ck*a(n-k)
where ck /= 0 holds, with given k initial conditions: a(0) .. a(k-1)
A systematic approach is based on the characteristic equation.
Consider an algorithm that splits a problem size n into a sub-problem of the size n/b = n `div` b.
Suppose that a total g(n) additional operations are required in this division procedure:
f(n) = a*f(n/b) + g(n)
This relation is called divide-and-conquer.
Formal power series (we ignore the convergence problem).
Relations
A binary relation from a set A to another set B is a subset of the product set A×B. A binary relation on A is a binary relation from A to A itself.
- A relation R on A is reflexive iff for any element a of A, aRa.
- A relation R on A is symmetric iff if aRb then bRa.
- A relation R on A is antisymmetric iff if aRb and bRa then a=b.
- A relation R on A is transitive iff if aRb and bRc then aRc.
A model of computer databases (the relational data model).
For a finite set, labeling elements (i.e., converting a set into a list), we can express a relation as a zero-one matrix (or boolean matrix). One gain of this method is composition-preserving property (in other words, the zero-one representation forms a functor). Another choice would be digraphs (directed graphs); a digraph consists of a set of vertices and an ordered pair of vertices (edges).
So far skipped.
An equivalence relation is a relation which is reflexive, symmetric, and transitive.
An equivalence relation on a set splits the set into disjoint subsets: equivalence classes.
A partial order is a relation which is reflexive, antisymmetric, and transitive.
A lattice is a poset in which every pair of elements has both a least upper bound and a greatest lower bound.
Topological Sorting (based on the following fact)
Every finite non-empty poset has a minimal; choose one element a0, if a0 is minimal then nothing has to be proven. If a0 is not a minimal, then there exists a1 such that a1 < a0; is a1 is minimal, done. Since the set is assumed to be finite, this procedure will terminate in a finite step.
Graphs
*Libraries *https://hackage.haskell.org/package/graphviz GraphViz for haskellers.
*Examples *https://stackoverflow.com/a/20860364
*https://qiita.com/lotz/items/4443a3ccb35780fa0c00
As an attempt to automate the drawing graphs, I'd use Turtle. My first attempt is ugly, though.
Tree
Boolean Algebra