Mathematics for Computer Science

References

• Mathematics for Computer Science, by Eric Lehman, F Thomas Leighton, and Albert R Meyer

Symbols:

Proofs

• A proof is a method of establishing truth.
• A mathematical proof of a proposition is a chain of logical deductions leading to the proposition form a base set of axioms.

What Is A Proof

• A proposition is a statement (communication) that is either true or false.
• • Examples:
  • • : true proposition
    • : false proposition
• A prime number is an integer greater than 1 that is not divisible by any other integers greater than 1.
• For a computer scientist, one of the most important things to prove are the correctness or programs and systems - whether a program or system does what it's supposed to do.
• A predicate can be understood as a proposition whose truth depends on the values of one or more variables.
• Predicate notation:

• axioms are propositions that are accepted as true, like assumptions.
• A proof is a sequence of logical deductions from axioms and previously proved statements that concludes with the proposition in question.
• Important true propositions are called theorems.
• A lemma is a preliminary proposition useful for proving later propositions.
• A corollary is a proposition that follows in just a few logical steps from a theorem.
• Logical Deductions or inference rules are used to prove new propositions using previously proved ones.
• In general, a proof can be any sequence of logical deductions from axioms previously proved statements that concludes with the proposition in question.

The Well Ordering Principle

Every nonempty set of nonnegative integers has a smallest element.

• This provides one of the most important proof rules in discrete mathematics.
• Prime Factorization Theorem states that every integer greater than one has a unique expression as a product of prime numbers.
• A set of real numbers is well ordered when each of its nonempty subsets has a minimum element.
• Well ordering commonly comes up in computer science as a method for proving that computations won't run forever. The idea is to assign a value to each successive step of a computation so that the values get smaller at each step. If the values are all from a well ordered set, then the computation can't run forever, because if it did, the values assigned to it successive steps would define a subset with no minimum element.

Logical Formulas

• Propositional variables can only take on the values true and false. Propositional variables are also called Boolean variables.
• Mathematicians use the words NOT, AND, and OR for operations that change or combine propositions. The precise mathematical meaning of these special words can be specified by truth tables.
• IFF = if and only if, i.e. P IFF Q = P if and only if Q
• A truth table for implications can be summarized: An implication is true exactly when the if-part is false or the then-part is true

• A valid formula is one that is always true, no matter what truth vales its variables may have: P OR NOT(P).
• A satisfiable formula is one which can sometimes be true - that is, there is some assignment of truth values to its variables that makes it true.

Mathematical Data Types

Sets

• • Informally, a set is a bunch or object, which are called the elements of the set. the elements of a set can be just about anything: numbers, points in space, or even other sets.
  • The order of elements is not significant in a set. Mathematicians have devised special symbols to represent some common sets:

• The expression indicates that set S is a subset of set T, which means that every element of S is also an element of T. means that S is a strict subset of T, and that the sets are not equal.
• The union of sets A and B, denoted , includes exactly the elements appearing in A or B or both:

• The intersection of sets A and B, denoted , consists of all elements that appear in both A and B.
• The set difference of A and B, denoted , consists of all elements that are in A, but not in B.
• The set of all the subsets of set A is called the power set of A.
• Two sets are defined to be equal if they have exactly the same elements. That is, means that if and only if for all elements Z.

Sequences

• sequences are lists of objects called components, members, or elements. Short sequences are commonly described by listing the elements between the parentheses: .
• Differences between sets and sequences:
• • The elements of a set are required to be distinct, but elements in a sequence can be the same.
  • The elements in a sequence have a specified order, but the elements of a set do not.
  • Texts differ on notation for the empty sequence, this book uses .
  • A Cartesian product of sets is a new set consisting of all sequences where the first component is drawn from , the second from , and so forth. Length two sequences are called pairs.

Functions

• A function assigns an element of one set, called the domain, to an element of another set, called the codomain. The notation: indicates that is a function with domain A and codomain B. The familiar notation "" indicates that assigns the element to a. Here, b would be called the value of at argument a.
• A function might also be defined by a procedure for computing its value at any element of its domain.
• Functions may be partial functions, meaning that there may be domain elements for which the function is not defined. The set of domain elements for which the function is defined is called the support of the function. If a function assigns a value to every element of its domain, that is, its support equals its domain, it is called a total function.
• The set of values that arise from applying to all possible arguments is called the range of .
• Composing functions: .

Binary Relations

• Binary relations define relations between two objects. For example: .
• Binary Relation diagram:

Finite Cardinality

• A finite set is one that has only a finite number of elements. The number of elements is the size or cardinality of the set: is the cardinality of set A, or the number of elements in set A.

Induction

Induction is a powerful method for showing a property is true for all nonnegative integers. Induction plays a central role in discrete mathematics and computer science. Induction plays a central role in discrete mathematics and computer science. In fact, its use is a defining characteristics of discrete - as opposed to continuous - mathematics.

The Induction Principle

• Let P be a predicate on nonnegative integers. If
• • is true, and
  • IMPLIES for all nonnegative integers
• then
• • is true for all nonnegative integers,
• A useful variant of induction is called strong induction. Strong induction and ordinary induction are used for exactly the same thing: proving that a predicate is true for all nonnegative integers. Strong indication is useful when a simple proof that the predicate holds for does not follow from the fact that it holds at , but from the fact that it holds for other values .

Principle of Strong Induction

• Let P be a predicate on nonnegative integers. If
• • is true, and
  • for all together imply ,
• then is true for all .

State Machines

State Machines are a simple, abstract model of step-by-step processes. Since computer programs can be understood as defining step-by-step computational processes, it's not surprising that state machines come up regularly in computer science. They also come up in many other settings such as designing digital circuits and modeling probabilistic processes.

• A property that is preserved through a series of operations or steps is known as a preserved invariant.
• Formally, a state machine is nothing more than a binary relation on a set, except that the elements of the set are called states, the relation is called the transition relation, and an arrow in the graph of the transition relation is called a transition. A transition from state q to stater will be written . The transition relation is also called the state graph of the machine. A state machine also comes equipped with a designated start state.
• A state machine execution describes a possible sequence of steps a machine might take.

The Invariant Principle

• If a preserved invariant of a state machine is true for the start state, then it is true for all reachable states.
• Partial correctness is the property that the final results, if any, f the process must satisfy system requirements. The second correctness property, called termination, is that the process does always produce some final value.

Recursive Data Types

Recursive data types play a central role in programming, and induction is really all about them. Recursive data types are specified by recursive definitions, which say how to construct new data elements from previous ones.

• Definitions of recursive data types have two parts:
• • Base case(s) specifying that some known mathematical elements are in the data type
  • Constructor case(s) that specify how to construct new data elements from previously constructed elements or from base elements.

Structures

Number Theory

• Number theory is the study of integers. Number theory underlies modern cryptography.
• Divisibility
• • a divides b (notation | IFF there is an integer k such that .

• Number theory is the study of integers. Number theory underlies modern cryptography.
• Divisibility
• • a divides b (notation | IFF there is an integer k such that .
  • Facts about divisibility:
  • • If a | b and b | c, then a | c.
    • If a | b and a | c, then a | sb + tc for all s and t.
    • For all , a | b if and only if ca | cb.
  • Let n and d be integers such that d 0. Then there exists a unique pair of integers q and r such that AND .The number q is called the quotient and the number r is called the remained of n divided by r.

Directed Graphs and Partial Orders

• Directed graphs, called digraphs, provide a handy way to represent how things are connected together and how together from one thing to another by following those connections. The dots are called nodes or vertices and the lines are called directed edges or arrows.

• A directed graph G consists of a nonempty set called the vertices of G, and a set called the edges of G. An element is called a vertex. A vertex is also called a node; the words vertex and node are used interchangeably. An element is called a directed edge. A directed edge is also called an arrow or simply an edge. A directed edge starts at some vertex u called the tail of the edge and ends at some vertex v called the head of the edge. Such an edge can be represented by the ordered pair . The notation denotes this edge.
• The in-degree of a vertex in a digraph is the number of arrows coming into it, and similarly its out-degree is the number of arrows coming out of it.
• Sequence of edges is a walk. A path is a walk that never visits a vertex more than once.

A walk in a digraph is an alternating sequence of vertices and edges that begins with a vertex, ends with a vertex, and such that that for every edge in the walk, vertex u is the element just before the edge, and vertex v is the next element after the edge.

• A closed walk is a walk that begins and ends at the same vertex. A cycle is a positive length closed walk whose vertices are distinct except for the beginning and end vertices.
• If a graph G has n vertices a useful way to represent it is with an matrix of zeros and ones called its adjacency matrix . The ijth entry of the adjacency matrix is 1 if there is an edge from vertex to vertex and 0 otherwise.
• Adjacency Matrix for Graph Above:

• When there is a walk from vertex v to vertex w, we say that w is reachable from v.
• A directed acyclic graph (DAG) is a directed graph with no cycles.
• A topological sort or topological ordering of a directed graph is a linear ordering of its vertices such that for every directed edge  from vertex u to vertex v, u comes before v in the ordering.

Simple Graphs

• Simple Graphs model relationships that are symmetric, meaning that the relationship is mutual. Simple graphs are defined in almost the same way as digraphs, except that edges are undirected - they connect two vertices without pointing in either direction between the vertices. So instead of a directed edge which starts at vertex v and ends at vertex w., a simple graph only has an undirected edge that connects v and w.

• Two vertices are connected in a graph when there is a path that begins at one and ends at the other. By convention, every vertex is connected to itself by a path of length zero. A graph is connected when every pair of vertices are connected.

Counting

Sums and Asymptotics

• We can convert any product into a sum by taking a logarithm:

Conclusion

• I might come back to this later when I have more time to look at things that are too theoretical for me to look at right now.