CS202: Discrete Structures « Saylor.org – Free Online Courses Built by Professors

Discrete Structures

Purpose of Course show close

This course has been designed to provide you with a clear, accessible introduction to discrete mathematics. Discrete mathematics describes processes that consist of a sequence of individual steps (as compared to calculus, which describes processes that change in a continuous manner). The principal topics presented in this course are logic and proof, induction and recursion, discrete probability, and finite state machines. As you progress through the units of this course, you will develop the mathematical foundations necessary for more specialized subjects in Computer Science, including data structures, algorithms, and compiler design. Upon completion of this course, you will have the mathematical know-how required for an in-depth study of the science and technology of the computer age.

Learning Outcomes show close

Upon successful completion of this course, the student will be able to:

Create compound statements, expressed in mathematical symbols or in English, to determine the truth or falseness of compound statements and to use the rules of inference to prove a conclusion statement from hypothesis statements by applying the rules of propositional and predicate calculus logic.
Prove mathematical statements involving numbers by applying various proof methods, which are based on the rules of inference from logic.
Prove the validity of sequences and series and the correctness or repeated processes by applying mathematical induction.
Define and identify the terms, rules, and properties of set theory and use these as tools to support problem solving and reasoning in applications of logic, functions, number theory, sequences, counting, probability, trees and graphs, and automata.
Calculate probabilities and apply counting rules.
Solve recursive problems by applying knowledge of recursive sequences.
Create graphs and trees to represent and help prove or disprove statements, make decisions or select from alternative choices to calculate probabilities, to document derivation steps, or to solve problems.
Construct and analyze finite state automata, formal languages, and regular expressions.

Course Requirements show close

In order to take this course, you must:

√ Have access to a computer.

√ Have continuous broadband internet access.

√ Have the ability/permission to install plug-ins or software (e.g. Adobe Reader of Flash).

√ Have the ability to download and save files and documents to a computer.

√ Have the ability to open Microsoft files and documents (.doc, .ppt, .xls, etc.).

√ Be competent in the English language.

√ Have read the Saylor Student Handbook.

√ Have completed the following prerequisite courses from “The Core Program” of the Computer Science discipline, including CS101 and/or CS102 for use of functions and procedures, conditional statements, loops, recursion, data types, and evaluation of expressions.

√ Have completed the following required mathematics courses in the Computer Science discipline, including CS103/MA101, CS104/MA102, and CS105/MA211. Skills in basic algebra and calculus are necessary for this course.

Unit Outline show close

1 The Logic of Compound Statements
1.1 Compound Statements
1.1.1 The NOT, AND, OR, and XOR Symbols
1.1.2 Translating from English to Symbols
1.1.3 Truth Tables for Negation
1.1.4 Truth Tables for Conjunction
1.1.5 Truth Tables for Disjunction
1.1.6 Truth Tables for Exclusive OR
1.1.7 Double Negative Property
1.1.8 Negations of AND and OR: De Morgan’s Law
1.1.9 Tautologies and Contradictions
1.2 Conditional Statements
1.2.1 Logical Equivalences Using Conditional Statements
1.2.2 Negation of a Conditional Statement
1.2.3 Contrapositive of a Conditional Statement
1.2.4 Converse and Inverse of a Conditional Statement
1.2.5 If and Only If, Sufficient and Necessary Conditions
1.2.6 Proving Validity or Invalidity of an Argument Using Truth Tables
1.3 Modus Ponens and Modus Tollens
1.3.1 Rules of Inference

2 The Logic of Quantified Statements
2.1 Quantified Statements
2.1.1 The Universal Quantifier
2.1.2 The Existential Quantifier
2.1.3 Translating from Formal to Informal Language
2.1.4 Translating from Informal to Informal Language
2.2 Operating on Quantified Statements
2.2.1 Negations of Quantified Statements
2.2.2 Contrapositive of a Universal Statement
2.2.3 Converse of a Universal Statement
2.2.4 Inverse of a Universal Statement
2.3 Statements Containing Multiple Quantifiers
2.3.1 Translating Statements with Multiple Quantifiers from Formal to Informal Language
2.3.2 Translating Statements with Multiple Quantifiers from Informal to Formal Language
2.3.3 The Definition of a Limit

3 Introduction to Number Theory and Proof Methods
3.1 Direct Proofs and Indirect Proofs
3.1.1 Odd and Even Numbers
3.1.2 Prime Numbers
3.1.3 Proving and Disproving Universal Statements
3.1.4 Proving and Disproving an Existential Statement
3.2 Numbers: Direct Proofs and Counterexamples
3.2.1 Rational Numbers
3.2.2 Irrational Numbers
3.2.3 Proving Properties of Rational Numbers
3.3 Divisibility: Direct Proofs and Counterexamples
3.3.1 Divisibility
3.3.2 Proving Properties of Divisibility

4 Mathematical Induction and Introduction to Sequences
4.1 Sequences
4.1.1 Finding Terms of Sequences Given by Explicit Formula
4.1.2 An Alternating Sequence
4.1.3 Finding an Explicit Formula to Fit Given Initial Terms
4.2 Summation
4.2.1 Computing Summations
4.2.2 Converting Summation Notation to Expanded Form
4.2.3 Converting Expanded Form to Summation Notation
4.2.4 Properties of Summation
4.3 Product Notation
4.3.1 The Notation
4.3.2 Computing Products
4.3.3 Properties of Products
4.4 Factorial Notation
4.4.1 The First Ten Factorials
4.4.2 Computing with Factorials
4.5 Mathematical Induction
4.5.1 Principle of Mathematical Induction
4.5.2 Proof by Induction of the Sum of First n Integers
4.5.3 Proof by Induction of the Sum of a Geometric Sequence
4.5.4 Proving Divisibility by Induction
4.5.5 Proving an Inequality by Induction
4.6 Loop Invariants
4.6.1 Basis Property
4.6.2 Inductive Property
4.6.3 Eventual Falsity of Guard
4.6.4 Correctness of the Post-Condition

6 Introduction to Counting and Probability
6.1 Definitions and Basic Counting
6.1.1 What Is a Sample Space?
6.1.2 What Is an Event?
6.1.3 Equally Likely Probability Formula
6.1.4 Counting Elements of Lists and Sublists
6.1.5 Counting Elements of a One-Dimensional Array
6.2 Possibility Trees and Advanced Counting
6.2.1 Possibility Trees and the Multiplication Rule
6.2.2 Permutation
6.2.3 Counting Elements of Disjoint Sets: The Addition Rule
6.2.4 The Difference Rule
6.2.5 Combinations
6.2.6 r-Combinations with Repetition Allowed
6.2.7 The Algebra of Combinations
6.3 Probability Axioms
6.3.1 Applying Probability Axioms
6.3.2 The Probability of the Complement of an Event
6.3.3 The Probability of a General Union of Two Events
6.4 Conditional Probability and Independent Events
6.4.1 Computing a Conditional Probability
6.4.2 Bayes’ Theorem
6.4.3 Computing the Probability of Independent Events

7 Recursion
7.1 Recursively Defined Sequences
7.1.1 Computing Terms of a Recursively Defined Sequence
7.1.2 Sequences that Satisfy the Same Recurrence Relation
7.1.3 Converting Sequences with Explicit Formulas to Recurrence (Recursive) Relation
7.1.4 The Tower of Hanoi and the Fibonacci Numbers
7.2 Solving Recurrence Relations
7.2.1 Using the Method of Iteration
7.2.2 Using Mathematical Induction
7.3 Recursive Functions
7.3.1 McCarthy’s 91 Function
7.3.2 The Ackermann Function

8 Graphs and Trees
8.1 Introduction to Graph Theory
8.1.1 Terminology
8.1.2 Directed Graph
8.1.3 Special Graphs
8.2 The Concept of Graph Degrees
8.2.1 Degree of a Vertex
8.2.2 Total Degrees of a Graph
8.2.3 The Handshake Theorem
8.3 Isomorphism of Graphs
8.3.1 Showing that Two Graphs are Isomorphic
8.3.2 Showing that Two Graphs Are Not Isomorphic
8.4 Trees
8.4.1 Determining if a Graph is a Tree or Not
8.4.2 Tree Types

9 Regular Expressions and Finite-State Automata
9.1 Formal Languages
9.1.1 Polish Notation
9.1.2 Languages Defined by Regular Expressions
9.2 Finite State Automata
9.2.1 A Simple Example: a Vending Machine
9.2.2 Finite State Automaton Given by a Transition Diagram
9.2.3 Generating Finite State Automaton from Next-State Tables
9.2.4 Automaton and Accepted Language
9.2.5 Showing that a Language Is Not Regular
9.2.6 Simplifying Finite State Automata

10 Final Exam

Expand All Resources Collapse All Resources

Unit 1: The Logic of Compound Statements

Great thinkers have studied logic since the time of the Greek philosopher Aristotle; its rules serve as the basis for the study of every branch of knowledge—including (and perhaps especially) computer science. Logic is an abstraction and formalization of reasoning we use every day, in mathematics, in science, and, in particular, computer science. Logic deals with logical systems that consist of symbols that represent statements that are either true or false, definitions of operations for combining statements (for example, addition is an operation in arithmetic for combining numbers), rules for manipulating statement and operator symbols, and rules for inferring new statements from given statements. In Unit 1 and Unit 2, we will study two logical systems: the Propositional Calculus and the First Order Predicate Calculus.

The following guidance will help you get started in our study of logic in Discrete Structures. The definitions and rules are called axioms or postulates (we use these terms synonymously). We use axioms and known true statements to prove the truth or falseness of theorems. A theorem is a statement that has a hypothesis (assumptions) and a conclusion. Much of our work will involve proving theorems. You may notice that several different notations are used in logic, depending on the author, text, or reference. In this course we use several different notations so that you are introduced to these differences.

Logic is an extensive field of study and selected topics are included in Discrete Structures. These topics vary depending on the institution or school, course, the instructor, and the text. To expose you to some of the variation, we use two main resources, as well as include supplementary resources and our own original content. In this unit, we will examine various rules of logic (i.e. negations, conjunctions, and disjunctions) in order to determine how they can create conditional statements, arguments, and rules but also prove the truthfulness or falseness of any argument, whether presented in mathematical terms or in everyday language.

Unit 1 Time Advisory show close

Unit 1 Learning Outcomes show close

1.1 Compound Statements

1.1.1 The NOT, AND, OR, and XOR Symbols

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic" (PDF)

Also Available in:
EPUB

Instructions: Please read Section 1 through the end of Section 1.1.1 (pages 1-3). This reading discusses logical symbols or operators that apply to propositions (the operands) to form a compound statement. A proposition is a statement that is either True (T) or False (F). Propositions are often denoted by single letters, for example, P or Q. The resulting truth or falseness of the compound statement is determined either using a truth table based on the truth or falseness of the operands or, as we will see later, by applying inference rules to prove that the compound statement is inferred from true statements. Please note that Section 1.1.1 of this reading also covers topics for subunits 1.1.3, 1.1.4, and 1.1.5.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit BF: Boolean Functions and Computer Arithmetic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit BF: Binary Functions and Computer Arithmetic" (PDF)

Also Available in:
EPUB

Instructions: This reading also covers the topic for subunit 1.1.6. Read Section 1 Boolean Functions up to Example 6 (pages BF-1 to BF-4). This reading presents material similar to Devadas and Lehman, but uses the language of Boolean Functions. Exclusive OR is defined in Example 4. Example 5 discusses the relation of Boolean Functions and Logic.

XOR is the exclusive OR symbol. It differs from OR in that the resulting value is True if and only if exactly one of the operands is True. Thus, the result value in the truth table for XOR is False (F) for the row where each operand has the value True (T).

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

1.1.2 Translating from English to Symbols

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic" (PDF)

Also Available in:
EPUB

Instructions: Read the beginning paragraphs in the “Logic” section up to Section 1, and then read Sections 1.2 and 1.3 (pages 3-6).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, Sand Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic, and Numbers, Unit Lo: Logic"
Link: University of California, Sand Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers: Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Read the beginning of Logic, Section 1: Propositional Calculus, from pages Lo-1 into page Lo-3, up to the "Implication" paragraph. This reading also applies to subunit 1.1.7 of this course.

These brief readings introduce the use of logic in representing English or natural language statements, as well as for statements in mathematics. The translation discussion is continued in section 1.1.9 below.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!
Reading: The Saylor Foundation’s “Translating from English to Logic Symbols”
Link: The Saylor Foundation’s “Translating from English to Logic Symbols” (PDF)

Instructions: Please download this reading for a brief summary and review of translating English to logic symbols.
See a broken link? Please let us know!

1.1.3 Truth Tables for Negation

1.1.4 Truth Tables for Conjunction

1.1.5 Truth Tables for Disjunction

1.1.6 Truth Tables for Exclusive OR

1.1.7 Double Negative Property

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit BF: Boolean Functions and Computer Arithmetic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit BF: Binary Functions and Computer Arithmetic" (PDF)

Also Available in:
EPUB

Instructions: Read example 3 on page BF-2 in Section 1 Boolean Functions of the Bender and Williamson reading.

NOT is a unary operator, meaning it has one operand. The other operators AND, OR, and XOR are binary operators, meaning they have two operands. "NOT P," also written as NOT (P), or ~P, is defined by the truth table referenced in subunit 1.1.1, above. This truth table can also be used to evaluate the truth or falseness of NOT (NOT (P)), which is T when P is T and F when P is F. Thus, it has the same values as P. We say that NOT (NOT (P)) and P are equivalent.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

1.1.8 Negations of AND and OR: De Morgan’s Law

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit BF: Boolean Functions and Computer Arithmetic and Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit BF: Boolean Functions and Computer Arithmetic" (PDF) and "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB (Logic)
EPUB (Boolean Functions)

Instructions: Study Theorem 2 (Algebraic Rules for Boolean Functions) on pages 6-7. In the article on Logic,study Theorem 1 (Algebraic Rules for Statement Forms) on page 3. De Morgan's law is very useful and widely used in communication, mathematics, engineering, and the sciences. Please make sure to familiarize yourself with De Morgan’s law before moving on to other sections of this course.

Terms of Use: Please respect the copyright and terms of use displayed on the web pages above.
See a broken link? Please let us know!

1.1.9 Tautologies and Contradictions

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Study Definition 1 (Tautology, Contradiction) in Section 1 (pages 2-3). In subunit 1.1.2 of this course, we introduced translation between English statements and logic. This reading, in addition to Tautology and Contradiction, adds to the translation story by discussing the relationship with set theory. Thus, you can translate from and to English, logic, and set symbols. The discussion of translation will continue when you study Implication in the subunit 1.2.1.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

1.2 Conditional Statements

1.2.1 Logical Equivalences Using Conditional Statements

Reading: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic" (PDF)

Also Available in:
EPUB

Instructions: Read Sections 1.1.2 and 1.1.3 (pages 4 and 5). Section 1.1.3 of this reading also applies to subunit 1.2.5 of this course.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Read the Section titled "Implication" up to the Exercises (pages 4-9). For the English translation discussion, see Example 3 (page 6) and subunit 1.1.2 of this course. Example 3 also applies to 1.2.2, 1.2.3, and 1.2.4 below.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

1.2.2 Negation of a Conditional Statement

1.2.3 Contrapositive of a Conditional Statement

1.2.4 Converse and Inverse of a Conditional Statement

1.2.5 If and Only If, Sufficient and Necessary Conditions

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Read Example 5 (pages 7-8). Note that in A if and only if (abbreviated iff) B, A is the necessary part and B the sufficient part.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

1.2.6 Proving Validity or Invalidity of an Argument Using Truth Tables

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic" (PDF)

Also Available in:
EPUB

Instructions: Read Sections 1.2 (pages 5 and 6) and 1.4 (pages 6-8).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit BF: Boolean Functions and Computer Arithmetic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logicand Numbers, Unit BF: Binary Functions and Computer Arithmetic" (PDF)

Also Available in:
EPUB

Instructions: Read Example 7 on pages 7 and 8.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!
Reading: The Saylor Foundation’s “Validity and Arguments”
Link: The Saylor Foundation’s “Validity and Arguments” (PDF)

Instructions: Please read through the entire text linked here.
See a broken link? Please let us know!

1.3 Modus Ponens and Modus Tollens

1.3.1 Rules of Inference

Reading: Wikipedia: "List of Rules of Inference, Table: Rules of Inference—A Short Summary"

Link: Wikipedia: "List of Rules of Inference, Table: Rules of Inference—A Short Summary" (PDF)

Instructions: Read over the text from Wikipedia on rules of inference. The summary table is located before the 'truth table' and the Examples. The Rules of Inference are referred to by names in the 3rd column in the table. In this course, alternate names are also used. Those that have corresponding alternate names are listed in the following table:

Wikipedia Name	Alternate Name
Disjunction	Generalization
Conjunction	Specialization
Elimination	Generalization
Modus Ponens
Modus Tollens
Hypothetical Syllogism	Transitivity
Disjunctive Syllogism	Disjunctive Elimination
Resolution	Elimination

Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).

See a broken link? Please let us know!

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Proofs"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Proofs" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1 “The Axiomatic Method” up to Section 3 (pages 3-7). Please note that reading Section 3 (pages 7-9) is optional.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Review Example 4 (Right Triangles and the Pythagorean Theorem) on pages 6-7.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!
Reading: The Saylor Foundation’s “Modus Ponens and Other Types of Reasoning”
Link: The Saylor Foundation’s “Modus Ponens and Other Types of Reasoning” (PDF)

Instructions: Please download each file linked here for a summary on Modus Ponens and other types of reasoning.
See a broken link? Please let us know!

1.3.1.1 Generalization

1.3.1.2 Specialization

1.3.1.3 Elimination

1.3.1.4 Transitivity

Assessment: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 1"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 1" (PDF)

Instructions: Do problem #1. You can check your answers on the solutions guide here. (PDF)

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Discrete Mathematics Course: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”

Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: This assessment has two parts:

1. Given that a set P is a subset of set Q, let 'a' be an element that is not in Q. Prove using the propositional calculus that 'a' is not in set P. Hint: Translate the statements to the predicate calculus and use rules of inference. For background reading for this problem, select the hyperlink “Lo PDF” to download the file for the Logic Unit. In this Logic Unit, you may want to reread the material from Example 1 up to Example 3 as a review. Keep in mind the difference between implication, which is a Binary Function, or logic operator for combining two statements, and a rule of inference, such as Modus Ponens, with which we form proofs or arguments.

Answer: Assume, without loss of generality, that sets P and Q consist of members from a Universal set U. Let y be any member of U, and a be a specific member of U.
Then, we have to prove that NOT (a in P) logically follows from
[(y in P) --> (y in Q)] / [NOT (a in Q)].
The truth table for this follows. SINCE it holds for any y, it HOLDS for y = a, and we REPLACE y with a in the table.
[(a in P) (a in Q) -->] [NOT (a in Q)] ^

F	F	T	F	F
F	F	T	T	T
F	T	T	F	F
F	T	T	T	T
T	F	F	F	F
T	F	F	T	F
T	T	T	F	F
T	T	T	T	T

Note the row marked with "<--" on the right side of the table. This is the only row for which the hypothesis applies (the hypothesis is that (a in Q) is False and (a in P) implies (a in Q)). Therefore, it follows that a in P is False.

Of course we could have proved this assessment using set theory, but because this is a unit on Logic, we wanted to demonstrate the translation from sets to logic.

2. Complete questions 1-8 of the Multiple Choice Questions for Review on pages Lo23-Lo25.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.

See a broken link? Please let us know!

Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Discrete Mathematics Course: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Do the Review Questions 1-8 on page Lo23.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

Unit 2: The Logic of Quantified Statements

In the previous unit, we discussed the logical analysis of compound statements, including those comprised of simple statements joined by OR, AND, NOT operators. This analysis provides us with a better understanding of human reasoning, but cannot be used to determine the validity of the majority of mathematical situations. In some cases, it becomes necessary to separate statements into parts, just as we parse sentences in order to facilitate comprehension.

In this unit, we will learn to analyze and understand the special roles that keywords and predicates (i.e. “for all” and “some) play—exercises that constitute the foundation of predicate calculus.

Unit 2 Time Advisory show close

Unit 2 Learning Outcomes show close

2.1 Quantified Statements

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic" (PDF)

Also Available in:
EPUB

Instructions: Read Section 3 through 3.1 (pages 11 and 12).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"(PDF)

Also Available in:
EPUB

Instructions: Please read Section 2 Predicate Logic up to and including Definition 4 (pages 12 and 13). These readings also apply to the topics in subunits 2.1.1 and 2.1.2. As you read this text, consider that statements in the First Order Predicate Calculus, or for us, simply, the Predicate Calculus, involve variables that can take on values from a set in a reference domain. We interpret the statement by introducing a domain of discourse or reference domain that the symbols (statements and operators), the rules, and variables represent or refer to. Just keep in mind, that the variables in a predicate calculus statement take on the values from a particular set, for example, the set of all boys in Chicago or the set of positive integers.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

2.1.1 The Universal Quantifier

2.1.2 The Existential Quantifier

2.1.3 Translating from Formal to Informal Language

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic" (PDF)

Also Available in:
EPUB

Instructions: Read Sections 3.2 (page 12) and 3.6 (pages 14 and 15). This reading also pertains to the topic in subunit 2.1.4.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Please read Definition 5 up to and including Example 8 (pages 13 and 14). This reading also applies to the topic for subunit 2.1.4 of this course. As you read this text, please keep in mind that normal language includes logic, binary functions, sets, programming languages. Informal language includes English and other natural languages. Please note that translating from informal to informal language for subtopic 2.1.4 involves rewriting an informal statement into a different but equivalent statement.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

2.1.4 Translating from Informal to Informal Language

2.2 Operating on Quantified Statements

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic”
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic” (PDF)

Also Available in:
EPUB

Instructions: Read Sections 3.3 and 3.4 on page 13.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Read Example 15 on page 19.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

2.2.1 Negations of Quantified Statements

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Logic" (PDF)

Also Available in:
EPUB

Instructions: Read Section 3.5 on page 14.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Please read Example 9 up to and including Example 10 (pages 14 and 15). These readings apply to the topics in 2.2.1.1, 2.2.1.2, and 2.2.2 through 2.2.4.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

2.2.1.1 Negating a Universal Statement

2.2.1.2 Negating an Existential Statement

2.2.2 Contrapositive of a Universal Statement

2.2.3 Converse of a Universal Statement

2.2.4 Inverse of a Universal Statement

2.3 Statements Containing Multiple Quantifiers

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Please read from Example 11 up to the Section 2 Exercises (pages 16-19). These readings also apply to topics in subunits 2.3.1 and 2.3.2. The examples work with multiple quantifiers.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

2.3.1 Translating Statements with Multiple Quantifiers from Formal to Informal Language

2.3.2 Translating Statements with Multiple Quantifiers from Informal to Formal Language

2.3.3 The Definition of a Limit

Reading: The Saylor Foundation’s “Definition of a Limit”
Link: The Saylor Foundation’s “Definition of a Limit” (PDF)

Instructions: Please read this text in its entirety to better understand the definition of a limit and primarily to illustrate the use of the notation from this unit.
See a broken link? Please let us know!
Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 1"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 1" (PDF)

Instructions: Do problems #2 and 3. You can check your answers on the solutions guide here. (PDF)

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Discrete Mathematics Course: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit Lo: Logic" (PDF)

Also Available in:
EPUB

Instructions: Do the Review Questions 9-11 on page Lo25.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

Unit 3: Introduction to Number Theory and Proof Methods

In this unit, we will learn the properties of integers, real numbers, rational numbers, irrational numbers, and operations on all of these types of numbers. Our goal will be to learn how to determine the validity or falsity of a mathematical statement via a number of methods, including counterexample and exhaustion. We will apply these methods to not only prove the validity of the properties of the number types we are studying in this unit, but provide a practical approach to them so that future mathematical arguments can be proved or disproved using these methods.

Unit 3 Time Advisory show close

Unit 3 Learning Outcomes show close

3.1 Direct Proofs and Indirect Proofs

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Proofs"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Proofs" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1 “The Axiomatic Method,” and Sections 4-6, inclusive.

Consider the following comparison of direct and indirect proofs. A direct proof is an argument which shows that the conclusion logically follows from the premises or assumptions by applying rules of inference in a sequence of steps. Method 1 in Devadas and Lehman, Proofs Section 2 Proving an Implication, 2.1 and 2.2 is a direct proof method. In a logic system, a statement P is equivalent to an implication, where P logically follows from the axioms and valid statements of the logic system.

An indirect proof, in contrast, is a proof in which the theorem to be proved is assumed False, and from this assumption, it is shown that a contradiction follows. Because the logic system is consistent, i.e. there are no contradictions, the theorem must be True. (Two statements are contradictions when they cannot both be True and they cannot both be False.)

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Examples 1-4 (pages 3-6), inclusive, which discuss proofs for sets.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

3.1.1 Odd and Even Numbers

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1 through Example 1 (pages 1 and 2).

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

3.1.2 Prime Numbers

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic, and Numbers, Unit NT: Number Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic,and Numbers, Unit NT: Number Theory" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1 beginning at Prime Numbers and Factorization on page 3 and continue up to Example 3 on page 4. Example 3 also applies to 3.1.4 and 3.2.2 below.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

3.1.3 Proving and Disproving Universal Statements

3.1.3.1 Proof by Using the Method of Exhaustion

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory" (PDF)

Also Available in:
EPUB

Instructions: Read Example 2 on page 2. This material also applies to the topic in section 3.3.1.1 of this course.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!
Reading: The Saylor Foundation’s “Proof by Exhaustion”
Link: The Saylor Foundation’s “Proof by Exhaustion” (PDF)

Instructions: Please download this reading for comments on proof by exhaustion.
See a broken link? Please let us know!

3.1.3.2 Disproof by Counterexample

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory" (PDF)

Also Available in:
EPUB

Instructions: Read over the Exercises for Section 1 (pages 10-13). Note the use of Counterexamples. A universally quantified statement may be False. It can be proven False by showing that there exists an instance of the universally bound variable for which the statement is False. The instance is called a counter example. Exercises often have useful information, also applicable outside of the Exercise.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

3.1.4 Proving and Disproving an Existential Statement

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory" (PDF)

Also Available in:
EPUB

Instructions: Read Example 5 on pages 5 and 6. An Existential Statement can be proved directly by specifying the instance of the existentially bound variable that makes the statement True. To disprove an Existential statement, transform its negation to an equivalent Universal statement, by using the property where the negation of an existential quantifier becomes a universal quantifier, (negating 'there exists an x such that P(x)' becomes 'for all x not P(x)'.) Then, prove the Universal statement.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

3.2 Numbers: Direct Proofs and Counterexamples

3.2.1 Rational Numbers

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1: Basic Facts about Numbers Example 4 on page 5. This reading also applies to the topic in subunit 3.2.3 of this course.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

3.2.2 Irrational Numbers

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1: Basic Facts about Numbers, Example 5 (pages 5 and 6) and Example 6 (pages 7-9). This reading also applies to the topics in subunits 3.2.3 and 3.3.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

3.2.3 Proving Properties of Rational Numbers

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course Recitations: "Case Analysis"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course Recitations: "CaseAnalysis" (PDF)

Instructions: Read the recitation, pages 1 through 5.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

3.3 Divisibility: Direct Proofs and Counterexamples

3.3.1 Divisibility

3.3.1.1 Divisibility Definition

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Number Theory I"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Number T h eory I" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1 Divisibility (pages 1-4) and Section 4 Greatest Common Divisor (pages 7-12).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory" (PDF)

Also Available in:
EPUB

Instructions: Read “Prime Numbers and Factorization Remainders and Modular Arithmetic, pages NT-6 to the top of NT-9. Sections 2 and 3 are motivational and you should at a minimum scan over them. Note that these discussions in the readings pertain to integers. They also apply to the following subsections: 3.3.1.2 and 3.3.1.3. In considering divisors of zero for subunit 3.3.1.2 as you read through these sections, remember that every integer a divides 0, since a · 0 = 0. This also holds for rational, irrational, and real numbers, since w · 0 = 0 for any real number w.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

3.3.1.2 Divisors of Zero

3.3.1.3 The Positive Divisors of a Positive Number

3.3.1.4 Divisibility of Algebraic Expressions

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Induction I”
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Induc t ion I” (PDF)

Instructions: Read Section 3 “A Divisibility Theorem.” This reading also applies to the topics in sections 3.3.2: 3.3.2.1, 3.3.2.2, and 3.3.2.3 of this course.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: The Saylor Foundation’s “General Theorem: Divisibility of Algebraic Expressions”
Link: The Saylor Foundation’s “General Theorem: Divisibility of Algebraic Expressions” (PDF)

Instructions: Please read the text in its entirety.
See a broken link? Please let us know!

3.3.2 Proving Properties of Divisibility

3.3.2.1 Transitivity of Divisibility

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Number Theory I”
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Number Theory I” (PDF)

Also Available in:
EPUB

Instructions: Please review Lemma 1 in Section 1.1 on page 2 of Devadas and Lehman’s “Number Theory I”.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

3.3.2.2 Divisibility by a Prime

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Number Theory I”
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Number Theory I” (PDF)

Also Available in:
EPUB

Instructions: In Devadas and Lehman’s “Number Theory 1,” read Section 5, titled Fundamental Theorem of Arithmetic, in its entirety (pages 12-15).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

3.3.2.3 The Quotient-Remainder Theorem

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Number Theory I”
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Number Theory I” (PDF)

Also Available in:
EPUB

Instructions: In Devadas and Lehman’s “Number Theory 1,” read Section 1.2, which presents the Division Theorem, in its entirety (pages 2-5).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Assessment: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 3"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 3" (PDF)

Instructions: Do problems #4-7. You can check your answers on the solutions guide here. (PDF)

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Assessment: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory and Cryptography"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit NT: Number Theory and Cryptography" (PDF)

Also Available in:
EPUB

Instructions: Do the Review Questions at the end of the chapter on pages NT26 - NT28.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

Unit 4: Mathematical Induction and Introduction to Sequences

In the field of Computer Science, we are often required to prove the correctness of an algorithm. We have developed a number of methods in order to do just that, one of which is known as mathematical induction. In this unit, we will learn to use induction in order to determine whether mathematical sequences are valid or invalid. This lesson is extremely important, because mathematical sequences are the basis for the study of repeated processes.

This unit will present induction first in an abstract form and then through specialized proofs of sequences. We will examine mechanisms for finding the general formula for a sequence and apply mathematical induction to prove a given formula’s validity.

Unit 4 Time Advisory show close

Unit 4 Learning Outcomes show close

4.1 Sequences

4.1.1 Finding Terms of Sequences Given by Explicit Formula

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequences, and Series"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequences, and Series" (PDF)

Also Available in:
EPUB

Instructions: Read Section 2 Sequences (pages 11-19). This reading also applies to subunits 4.1.2 and 4.1.3 in this course. See the definition of alternating sequence, immediately before Example 14. Please pay particular attention to Examples 7, 14, and 17 for information specific to the topics in subunits 4.1.2 and 4.1.3. Given a sequence, f(k), f(k + 1), f(k + 2), f(k + 3), ..., where k is a fixed integer, we may be able to determine a general expression for each term of this sequence. The general expression will have the form f(n), where n is a variable that takes on values from the set {n, n > k}. If we can determine the form for f, we writef(n)_{n >= k}. See the exercises for Section 2 for examples.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

4.1.2 An Alternating Sequence

4.1.3 Finding an Explicit Formula to Fit Given Initial Terms

4.2 Summation

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Summations”
Link: MIT: Srini Devadas and Eric Lehman’s Mathematics for Computer Science Course: “Summations” (PDF)

Also Available in:
EPUB

Instructions: Read this entire lecture. It is excellent and includes useful insights. Take your time to understand the transition from one step to the next in the proofs. This can be time consuming, but rewarding. This reading applies to sections 4.2.1, 4.2.2, 4.2.3, 4.2.4, and 4.3.2 below.

The reading mentions induction as a way of proving some of the expressions and then continues to give insight into the source or the expression. We will cover induction in section 4.5 of this course.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

4.2.1 Computing Summations

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence, and Series"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence, and Series " (PDF)

Also Available in:
EPUB

Instructions: Read Section 3 (pages 20-30). This reading also applies to subunits 4.2.2 and 4.2.3 in this course.

For sequences, given a summation ∑_{n > = k}(f(n), we can expand it to the series, f(k), f(k) + f(k + 1), f(k) + f(k + 1) + f(k + 2), .... Given the series, f(k), f(k) + f(k + 1), f(k) + f(k + 1) + f(k + 2), f(k) + f(k + 1) + f(k + 2) + f(k + 3), ..., we can write it as ∑_{n >= k}f(n).

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

4.2.2 Converting Summation Notation to Expanded Form

4.2.3 Converting Expanded Form to Summation Notation

4.2.4 Properties of Summation

Reading: The Saylor Foundation’s “Summation Properties”
Link: The Saylor Foundation’s “Summation Properties” (PDF)

Instructions: Please read this brief note on summation.
See a broken link? Please let us know!

4.3 Product Notation

4.3.1 The Notation

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence and Series"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence and Series" (PDF)

Also Available in:
EPUB

Instructions: Then, read Section 1 pages 1-11. ∏is the symbol for product. If p₁ , p_{2 ,}... , p_{k ...}is a sequence, the series p₁, p₁ p₂, p₁ p₂p₃ , p₁ p_{2 ,}... , p_k is written ∏ p₁ p₂... p_k. If you look over the Exercises for Section 1, you will see that this reading applies to ∏examples as well as ∑ examples. This reading also applies to topics in subunits 4.3.2 and 4.3.3.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

4.3.2 Computing Products

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Summations”
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: “Summations” (PDF)

Also Available in:
EPUB

Instructions: You have already read this lecture for subunit 4.2. Here, pay particular attention to and re-read section 3.4 Approximating 1 + x.

Consider the following information, which addresses the topics in subunits 4.3.2 and 4.3.3. Product computation is similar to the evaluation of the product of numbers in arithmetic. Product or multiplication is a binary operation that is commutative [i.e. a times b = a b = b a]; associative [i.e. (a b) c = a ( b c )]; and has an identity (i.e. a times 1 = 1). In addition, there are some tricks that can be used.

Some simple properties of products are: 1) a ∏ p_i= ∏ a p_i,where the ∏ ranges over a set of positive integers i 2) ∏ p_i ∏ q_{ij =} ∏ p_iq_j, where the product symbols varies over ranges for i and j.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

4.3.3 Properties of Products

4.4 Factorial Notation

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Sums, Approximations, and Asymptotics II"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Sums, Approximations ,and Asy m ptotics II" (PDF)

Also Available in:
EPUB

Instructions: Please read Section 2 “The Factorial Function.” The reading also applies to the subsections 4.4.1 and 4.4.2. In subunit 4.4.2, see the Binomial Theorem and its generalization to the Multinomial Theorem. The ten factorials correspond to a term of the z's and k's.

Note the first ten factorials: 10! 9! 8! 7! 6! 5! 4! 3! 2! 1! = 10¹ x 9²x 8³x 7⁴x 6⁵x 5⁶x 4⁷x 3⁸x 2⁹x 1¹⁰.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

4.4.1 The First Ten Factorials

4.4.2 Computing with Factorials

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting II and Counting III"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting II" "Counting III" (PDF)

Also Available in:
EPUB (Counting II)
EPUB (Counting III)

Instructions: In Counting II, read Section 1.3 “Permutations.” In Counting III, read Section 1.3 “Combinations” and Section 2 “Binomial Theorem.”

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

4.5 Mathematical Induction

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Induction I"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Induction I" (PDF)

Instructions: Read Sections 1 and 2 (pages 1-4). This reading also applies to subunits 4.5.1, 4.5.2, and 4.5.4 in this course. As you read about induction in the references note that induction has a relationship to recursion.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Induction III"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Induction III" (PDF)

Also Available in:
EPUB

Instructions: Read Section 2 (pages 2 - 5) and Section 4 (pages 8 - 12). These readings give helpful guidance in correct use of induction.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

4.5.1 Principle of Mathematical Induction

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence, and Series"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence and Series" (PDF)

Also Available in:
EPUB

Instructions: Click on “IS PDF” to download the chapter on “Induction, Sequence, and Series.” Please read and reread Section 1 and Section 2 up to 2.2 and Section 4.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

4.5.2 Proof by Induction of the Sum of First n Integers

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence, and Series"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, UnitIS: Induction, Sequence, and Series" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1 Example 2 on page IS-2.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

4.5.3 Proof by Induction of the Sum of a Geometric Sequence

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence and Series"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence and Series" (PDF)

Also Available in:
EPUB

Instructions: Please read Example 11, Example 12, and Theorem 2 (pages 5-7, 22, and 23). Some of the examples are more difficult, but hard examples push our understanding and expand our skill.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

4.5.4 Proving Divisibility by Induction

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Induction I"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Induction I" (PDF)

Instructions: Please read Sections 3 and 4 (pages 5-7).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

4.5.5 Proving an Inequality by Induction

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence, and Series"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic and Numbers, Unit IS: Induction, Sequence, and Series" (PDF)

Also Available in:
EPUB

Instructions: Please read Example 4 on pages 3 and 4.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

4.6 Loop Invariants

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Induction III"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Induction III” (PDF)

Also Available in:
EPUB

Instructions: Read Section 3.2. The reading presents a proof that an initial configuration of the 9 puzzle cannot be transformed into its inverse. The proof uses the fact that after each move the number of inversions remains even; this is an invariant. Invariants are used in proofs and in proving the correctness of programs.

Invariants are only introduced in this course; they are covered in detail in programming language courses.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Reading: The Saylor Foundation’s “Loop Invariants”
Link: The Saylor Foundation’s “Loop Invariants” (PDF)

Instructions: Please review the attached text for more information on invariants. This text applies to subunits 4.6.1-4.6.4 of this course.
See a broken link? Please let us know!

4.6.1 Basis Property

4.6.2 Inductive Property

4.6.3 Eventual Falsity of Guard

4.6.4 Correctness of the Post-Condition

Assessment: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 2 and Problem Set 3"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 2" and "Problem set 3" (PDF)

Instructions: Do problems 1-4 in Problem Set 2; do problems 1 and 3 in Problem Set 3. You can check your solutions for Problem Set 2 here and for Problem Set 3 here. (PDF)

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Assessment: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic, and Numbers, Unit IS: Induction, Sequence, and Series"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Arithmetic, Logic, and Numbers, Unit IS: Induction, Sequence, and Series" (PDF)

Also Available in:
EPUB

Instructions: Complete the multiple choice review questions are at the end of the Unit on pages IS31- IS33.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

Unit 5: Set Theory

Computer scientists often find themselves working with sets of homogeneous or heterogeneous values. Scientists have devised set theory in order to respond to these situations. In this unit, we will learn the basics of set theory, taking a look at definitions and notations and using the proof methods and counterexample means we introduced earlier to establish set properties.

Set Theory is a fundamental tool of mathematics and often used as the starting point for its study and used to define basic concepts, such as functions, numbers, limits, etc.

Unit 5 Time Advisory show close

Unit 5 Learning Outcomes show close

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: This reading covers all subunits 5.1-5.3. Key comments are included in the Instructions for each subunit.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.1 Definition of Set Theory

5.1.1 Set Notation

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1, pages SF-1 to SF-2. This reading also applies to Section 5.1.2 below and Sections 5.2.1-5.2.5 of this course.

A set is a collection of elements, called members of the set. Sets are denoted using capital letters; elements are denoted using small letters. We write a ? A for a an element of A; and a ? A, for a not an element of A.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.1.2 Set Equality

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence ,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 1 on page SF-1. NOTE: If A and B are sets, and if a ? A, implies a ? B, then we say A is a subset of B, denoted A ⊂ B.

A = B, if and only if, A ⊂ B and B ⊂ A. A and B are assumed to be subsets of a universal set E. Ø is the empty set or the set that has no members.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.2 Set Operations

5.2.1 The Union Operator

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 1 on page SF-2. Note that A U B = {x : x ? A or x ? B}.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.2.2 The Difference Operator

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 1 on page SF-2. A-B = { x : x ? A and x ? B}, called the complement of B with respect to A.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.2.3 The Intersection Operator

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 1 on page SF-2. NOTE: A ∩ B = {x : x ? A and x ? B}.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.2.4 The Complement of a Set

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 1 on page SF-2. NOTE: A' = {x : x ? A} = {x : x ? E and x ? A}, where E is the universal, containing all the sets. A' is called the complement of A.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.2.5 Cartesian Products

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 1 on page SF-2. The Cartesian Product, A x B = { (a, b) : a ? A and b ? B}, is referred to as the set of ordered pairs of A and B.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.2.6 Binary Relation

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Example 10 on page SF-16.

Given a set A, a binary relation, R on A, is a subset of A x A.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.2.6.2 Reflexive

NOTE:A binary relation on A is reflexive, if (a, a) ? R.

5.2.6.3 Symmetric

NOTE: A binary relation is symmetric if (a, b) ? R, then (b , a) ? R.

5.3 Set Identities and Proof of Set Identities

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read “Set Properties and Proofs” page SF-2 through top of SF-6. This reading applies to 5.3.1-5.3.3, 5.3.7, 5.3.9, and 5.3.10.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.1 Commutative Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Theorem 1 on SF-2 and SF-3. The Commutative laws are: A U B = B U A, A ∩ B = B∩ A.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.2 Associative Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Theorem 1 on SF-2 and SF-3. The Associative Laws are: (A U B) U C = A U (B U C) = A U B U C. Note that we can write the rightmost expression, which has no parenthesis, because U is associative. Replacing U by the intersection operations, gives the Associative Law for intersection.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.3 Distributive Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Click on the “SF PDF” hyperlink to download the “Sets and Functions” chapter. Read Theorem 1 on SF-2 and SF-3. The Distributive Laws are: A U (B ∩ C) = (A U B) ∩ (A U C); A ∩ (B U C) = (A ∩ B) U (A ∩ C).

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.4 Identity Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 1 on pages SF-1 and SF-2. It follows from the definition of the empty set that A U Ø = A, A ∩ Ø = Ø.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.5 Complement Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 1 on pages SF-1 and SF-2. For universal set E, E' = Ø= A ∩ A'; A - A = Ø.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.6 Double Complement Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Theorem 1 on pages SF-2 and SF-3. Double Complement is also referred to as Double Negative: (A') ' = A.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.7 Idempotent Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence ,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Theorem 1 on pages SF-2 and SF-3. The Idempotent Laws for union and intersection are: A U A = A, A ∩ A = A.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.8 Universal Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence ,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Click on the “SF PDF” hyperlink to download the “Sets and Functions” chapter. Read Definition 1 on pages SF-1 and SF-2. Note that it follows that A U A' = E, E ∩ A = A.

Terms of Use: Please respect the copyright and terms of use displayed on the web pages above.
See a broken link? Please let us know!

5.3.9 De Morgan’s Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence ,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Theorem 1 on page SF-2 and SF-3. The De Morgan's Laws are: (A U B) ' = A' ∩ B'; (A ∩ B)' = A' U B'.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.10 Absorption Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Click on the “SF PDF” hyperlink to download the “Sets and Functions” chapter. Read Theorem 1 on pages SF-2 and SF-3. The Absorption Laws are: If A ⊂ B,then A U B = B, A ∩ B = A; or more generally, P U (P ∩ Q), = P, P ∩ (P U Q) = P.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

5.3.11 Set Difference Laws

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 1 on pages SF-1 and SF-2 and Theorem 1 on pages SF-2 and SF-3. The Set Difference Laws: A - (B U C) = (A - B) ∩ (A - C); A - (B ∩ C) = (A - B) U (A - C) follow from the definition of set difference and De Morgan's Laws (use the fact the A - B = A ∩ B').

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!
Assessment: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 1"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 1" (PDF)

Instructions: Do problems 5 and 6. You can check your answers on the solutions guide here. (PDF)

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Assessment: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence, and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence,and Order, Unit SF: Sets and Functions" (PDF)

Also Available in:
EPUB

Instructions: Click on the “SF PDF” hyperlink to download the “Sets and Functions” chapter. Work on the Review Questions at the end of the chapter, pages SF29 - SF32.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

Unit 6: Introduction to Counting and Probability

Counting is not always as easy as it sounds. Say, for example, you are asked to arrange three balls of three different colors. What are the possibilities? What if two of them have the same color? This is an example of a set of problems known as “counting problems.” In this unit, we will learn different types of counting using possibility trees and general counting theorems. Once we understand the concepts of counting, we will discuss the probability of event occurrence, which refers to the likelihood that a certain outcome for a given problem set will occur. Events can be dependent or independent, making them subject to different sets of rules. Throughout the unit, we will relate counting and probability to computer science topics such as counting list and array elements, password computation, and brute force attacks.

In this unit, we are going to rely on the Devadas and Lehman reference as primary. Use the Bender and Williamson reference as a supplement.

Unit 6 Time Advisory show close

Unit 6 Learning Outcomes show close

6.1 Definitions and Basic Counting

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability" (PDF)

Also Available in:
EPUB

Instructions: In Devadas and Lehman, read the Introduction to Probability. Read up to Section 6.1.2.

This also applies to the subsections 6.1.1, 6.1.2, 6.1.3, 6.2.1: see these sections below for the specific pages that apply.

The reading also applies to 6.3: see the axioms on the top of page 8, and the top and middle of page 9.

Pertaining to Section 6.2.1 below, look at the line drawings; these are possibility trees. Realize that they are just representations of functions. For Section 6.4 below, focus on the modeling advice and Steps 1 - 4, on pages 1 - 9.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.1.1 What Is a Sample Space?

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability" (PDF)

Also Available in:
EPUB

Instructions: . Please read through Section 1.3 only (pages 3-5).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.1.2 What Is an Event?

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability" (PDF)

Also Available in:
EPUB

Instructions: Please read through Section 1.4 only (pages 5-6).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.1.3 Equally Likely Probability Formula

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability" (PDF)

Also Available in:
EPUB

Instructions: Please read through Section 1.5 only (pages 6-9).

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.1.4 Counting Elements of Lists and Sublists

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting I"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting I" (PDF)

Also Available in:
EPUB

Instructions: Click on the “PDF” hyperlink after the title “Counting I” to download Lecture 13. Read the Lecture on Counting I. This reading also applies to 6.1.5, 6.2.1, and 6.2.3 below. Section 1.3 applies to 6.1.5 and Section 2.2 applies to 6.2.1. Section 2 applies to 6.2.3.

Note, regarding 6.1.5, see Section 1.4 on page 5 and 6. The elements of a list can be mapped via a bijection to a one dimensional array. Thus, because we can count the elements of a list, we can count the elements of such an array.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.1.5 Counting Elements of a One-Dimensional Array

Reading: 6.1.5 Counting Elements of a One-Dimensional Array
NOTE: The elements of a list can be mapped via a bijection to a one dimensional array. Thus, because we can count the elements of a list, we can count the elements of such an array.
See a broken link? Please let us know!

6.2 Possibility Trees and Advanced Counting

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting II"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting II" (PDF)

Also Available in:
EPUB

Instructions: Specific parts of this reading apply to subsections 6.2.1, 6.2.2, 6.2.4, and are identified in the respective sections below.

Effective practice requires techniques and tools. These require thorough understanding of the reading. This in turn requires thinking about the reading and integrating it into your familiar knowledge.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.2.1 Possibility Trees and the Multiplication Rule

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability" (PDF)

Also Available in:
EPUB

Instructions: Look at the line drawings; these are possibility trees. Realize that they are just representations of functions used in modeling a problem. Note the modeling advice and Steps 1 - 4, on pages 1 - 9.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.2.2 Permutation

6.2.3 Counting Elements of Disjoint Sets: The Addition Rule

6.2.4 The Difference Rule

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting III"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting III" (PDF)

Also Available in:
EPUB

Instructions: See Section 1.2 and Section 5 on pages 13-15. This reading also applies to 6.2.7.2 of this course.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.2.5 Combinations

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting III"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting III" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1 on pages 1- 3. This reading also applies to 6.2.6 below - see Rule 1.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.2.6 r-Combinations with Repetition Allowed

6.2.7 The Algebra of Combinations

Reading: The Saylor Foundation’s “Combinations”
Link: The Saylor Foundation’s “Combinations” (PDF)

Instructions: Please review the attached text for more information on the algebra of combinations. This text applies to subunits 6.2.7.1 and 6.2.7.2 as well.
See a broken link? Please let us know!

6.2.7.1 Values to Remember

6.2.7.2 Pascal’s Triangle

6.2.7.3 The Binomial Theorem

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting III"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Counting III" (PDF)

Also Available in:
EPUB

Instructions: Read Section 2.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.3 Probability Axioms

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Introduction to Probability"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Probability" (PDF)

Also Available in:
EPUB

Instructions: Read Section 2.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.3.1 Applying Probability Axioms

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Sets, Equivalence and Order, Unit SF: Sets and Functions"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Unit CL: Basic Counting and Listing" (PDF)

Instructions: Click on the “CL PDF” hyperlink to download the “Basic Counting and Listing” chapter. Read Section 4, pages CL-28 up to and including CL-30.
Some useful results are summarized here:
1) ∑_x_{ε S}P(x) = 1, where S is the sample space, also written P(S) = 1.
2) P(x) >=0, for x in the sample space.
3) Let E be an event, defined as a subset of S. P(E) = ∑_x_{ε E}P(x).
4) If E and D are events such that E is contained in D, then P(E) <= P(D).
5) P(E U D) = P(E) + P(D) for E, D disjoint.
From the above the following can be proved: Let E be an event. E' = S -E. P(E U E') = P(E) + P(E'), P(S= E U E') = 1; thus, 1 = P(E) + P(E') and P(E') = 1 - P(E).

Terms of Use: Please respect the copyright and terms of use displayed on the web pages above.
See a broken link? Please let us know!

6.3.2 The Probability of the Complement of an Event

6.3.3 The Probability of a General Union of Two Events

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Conditional Probability"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Conditional Probabi lity" (PDF)

Also Available in:
EPUB

Instructions: Click on the “PDF” hyperlink after the title “Conditional Probability” to download Lecture 18. Read Theorems 2 and 3 on page 12.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.4 Conditional Probability and Independent Events

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Conditional Probability"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Conditional Probability" (PDF)

Also Available in:
EPUB

Instructions: Read this lecture in its entirety.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.4.1 Computing a Conditional Probability

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Conditional Probability"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Conditional Probability" (PDF)

Also Available in:
EPUB

Instructions: Work through the following examples in this lecture: Section 1 The Halting Problem (this is the fictitious name of a hockey team) on page 2, Section 2.1 A Coin Problem on page 6, Section 2.2 A Variant of the Two Coins Problem on page 8, Section 3 Medical Testing on page 9, Section 4.1 Carnival Dice on page 11, Section 4.3 Discrimination Lawsuit on page 14, and Section 4.4 On-Time Airlines on page 15.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

6.4.2 Bayes’ Theorem

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions, and Graphs, Unit DT: Decision Trees and Recursion"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions,and Graphs, Unit DT: Decision Trees and Recursion"(PDF)

Also Available in:
EPUB

Instructions: Read Section 3, pages DT-28 through DT-35.

Bayes’ Theorem is a famous theorem for computing conditional probabilities. Assume E_iare mutually exclusive events for i = 1, ..., n and U _iE_i= D, for arbitrary event D, P(E_i| D) = P(D | E_i ) P(E_i) / [P(D|E₁)P( E₁) + ....+ P(D|E_n) P(E_n)].

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

6.4.3 Computing the Probability of Independent Events

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Independence"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Independence" (PDF)

Also Available in:

EPUB

Instructions: Read this lecture in its entirety.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Assessment: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 3, Problem Set 7, and Problem Set 8"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 3" "Problem Set 7" "Problem Set 8" (PDF)

Instructions: Work through problem 2 in Problem Set 3, problems 2-5 in Problem Set 7, and problem 3 in Problem Set 8. You can check your answers on the solutions guide for Problem Set 3 here, Problem Set 7 here, and Problem Set 8 here. (PDF)

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Assessment: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit CL: Counting and Listing" and "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit CL: Counting and Listing" (PDF) and "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion"(PDF)

Also Available in:
EPUB (Counting and Listing)
EPUB (Decision Trees and Recursion)

Instructions: Complete the multiple choice Review Questions are at the end of the Unit on pages CL41 - CL44in the Counting and Listing document. Then, do the Review Questions 17-23 on pages DT55-DT57 in the Decision Trees and Recursion document.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

Unit 7: Recursion

In previous sections, we learned about sequences in a general sense. In this unit, we will take a look at a specific type known as a recursive sequence. The unit will first present a number of examples that demonstrate how one computes the terms of a recursive sequence and analyzes certain kinds of problems recursively in order to generate a general recursive sequence. We will then learn to use the proof method of induction to prove the validity or falsity of a recursive sequence.

In this unit, we are going to rely on the Bender and Williamson reference as primary. Use the Devadas and Lehman reference as supplementary. Switching primary references exposes us to some differences in notation and perspective.

Unit 7 Time Advisory show close

Unit 7 Learning Outcomes show close

7.1 Recursively Defined Sequences

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion" (PDF)

Also Available in:
EPUB

Instructions: Read Section 4, Recursion Equations, up to Example 27. This reading also applies to subsections: 7.1.1 - 7.1.4.

Given a recursive relation, the terms of its recursively defined sequence (7.1.1 below) are computed by evaluating the relation for the base value, say n = 1; then evaluating it for successive values of n.

Theorem 7 applies to 7.1.2. Given a recursive equation, also called a recursive relation, Theorem 7 tells us how to verify a solution for it.

Note regarding 7.1.3, let f(n) be an explicit formula for the nth term, A_n, of a sequence and assume that f(n) = A bⁿ + K = A bⁿ + K + Kb - Kb = A bⁿ + Kb + K - Kb = b (A b^n-1 + K) + K ( 1 - b) = b f(n - 1) + K(1 - b). Thus, f(n) = b f(n - 1) + C, a recursive equation, i.e. relation.

Notice that the definition of induction, in the Unit IS: Induction, Sequences and Series, is in terms of A(n), an assertion dependent on n. The A(n), n = 1, ..., n, ... is a sequence. In induction, A(n-1) is used to prove A(n). If A(n) is defined using A(n - 1), the sequence is recursively defined. Thus, induction and recursion both exploit a relationship between A(n) and A(n-1).

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

7.1.1 Computing Terms of a Recursively Defined Sequence

7.1.2 Sequences that Satisfy the Same Recurrence Relation

7.1.3 Converting Sequences with Explicit Formulas to Recurrence (Recursive) Relation

7.1.4 The Tower of Hanoi and the Fibonacci Numbers

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions, and Graphs, Unit DT: Decision Trees and Recursion"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions ,and Graphs, Unit DT: Decision Trees and Recursion"(PDF)

Also Available in:
EPUB

Instructions: These examples illustrate 7.1.3 and are examples of recursion. For the Fibonacci Numbers see Theorem 9 and Example 29 in the above Bender and Williamson reading, on pages DT-480DT49. For the Tower of Hanoi problem see Example 11, also in the above reading. Example 29 starts with the sequence, F₀ = F₁= 1, F_k= F_{k -1}+ F_{k -2}, and develops a formula for F_n which does not utilize an earlier F in the sequence.

Example 11 solves a famous puzzle with a recursive solution, namely a solution for n discs in terms of a solution for n-1 and 1 discs.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!
Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Recurrences"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Recurrences" (PDF)

Also Available in:

EPUB

Instructions: Read this Section 1, pages 1 - 5.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

7.2 Solving Recurrence Relations

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion" (PDF)

Also Available in:
EPUB

Instructions: Read from Example 27 to the end of the chapter. This reading also applies to subunits 7.2.1 and 7.2.2 in this course.

A solution to a recursive equation is a formula that computes A(n) without having to compute A(k), for k < n. Review the Section on Recursive Equations, on page DT-44 up to Example 26 on DT-46.

1. A solution to a recursive equation can be found by inspection of the terms of a given sequence (example 27 in the above reading); OR
2. Apply Theorems 8 if A(n) depends on A(n - 1); Theorem 9, if A(n) depends on A(n - 1) and A(n - 2).

By Theorem 8 on page DT-48, if an = ban−1 +c , then iterating,an = b( ban−2+c) + c = b(b ( b an−3+ c ) + c ) + c= ....= a₀bⁿ + c b^n-1 + c b^n-2 + .... + c. This is an example of 7.2.1.1, using the method of iteration for finding a formula for a recurrence relation for an arithmetic sequence.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

7.2.1 Using the Method of Iteration

7.2.1.1 Finding a Formula for a Recurrence Relation for an Arithmetic Sequence

7.2.1.2 Finding a Formula for an Iterative Relation for a Geometric Sequence

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion" (PDF)

Also Available in:
EPUB

Instructions: A simple example of going from an iterative relation to a formula is as follows: given the iterative relation, a_n= arⁿ, ar^n,= r a r ^n-1= r a _{n - 1}, . Continuing in this manner, we get the formula,a_n= rⁿ a₀. For another example, read over the Exercise 4.7 in the Bender and Williamson resource for a discussion of going from an iterative sequence to a recursive solution/equation, and, vice versa, from the recursive equation to an iterative sequence.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!
Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Summations"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Summations" (PDF)

Also Available in:

EPUB

Instructions: Please note that you have already read this lecture in section 4.2 above. Here, please focus on re-reading Section 1.2, which finds a formula for, not the terms of the sequence, but for the sum of the terms of the sequence.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

7.2.2 Using Mathematical Induction

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion" (PDF)

Also Available in:
EPUB

Instructions: Read Section 4, pages DT-42 to DT-44 up to Recursion Equations. Remember recursion and induction are closely related.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

7.3 Recursive Functions

7.3.1 McCarthy’s 91 Function

Reading: Wikipedia: "McCarthy 91 Function"
Link: Wikipedia: “McCarthy 91 Function” (PDF)

Instructions: Please read the entire Wikipedia article for a description of the McCarthy 91 Function, an example of a recursive function used in Computer Science as a test case for the performance of formal verification techniques and methods.

Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).
See a broken link? Please let us know!

7.3.2 The Ackermann Function

Reading: Wikipedia: "Ackermann Function"
Link: Wikipedia: “Ackermann Function” (PDF)

Instructions: Please read the entire Wikipedia article for a description of the Ackermann Function, an example of a recursive function that grows extremely rapidly.

Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).
See a broken link? Please let us know!
Assessment: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 6"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 6" (PDF)

Instructions: Try to work through problems 1, 5, 6, and 8. You can check your answers on the solutions guide here. (PDF)

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Assessment: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit DT: Decision Trees and Recursion" (PDF)

Also Available in:
EPUB

Instructions: Complete the Review Questions at the end of the chapter, numbers 1-16, on pages DT-53 and DT-54.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

Unit 8: Graphs and Trees

Graphs serve innumerable functions: they can represent communications systems, chart knowledge, and even solve problems. In this unit, we will acquaint ourselves with special kinds of mathematical graphs while discussing graph concepts from degree and vertex to isomorphism. We will then turn to trees, which comprise a special category of graphs, as they serve special purposes and have different structures. We will conclude with an examination of tree properties, discussing how trees can be applied to the study of artificial intelligence, scheduling problems, and transportation systems.

Unit 8 Time Advisory show close

Unit 8 Learning Outcomes show close

8.1 Introduction to Graph Theory

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Graph Theory"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Graph Theory" (PDF)

Also Available in:
EPUB

Instructions: This reading applies to 8.1 and its subsections: 8.1.1 - 8.1.3. In the reading, Sections 1 Introduction, 1.1, 1.3, and 1.5 apply to 8.1.1, 8.1.2, and 8.1.3 below. A graph is simple if there is at most one arc associated with a pair of vertices. A graph that is not simple is called a multigraph.

The reading, Section 1.1, also applies to 8.2 below. Think of graphs as models for representing the elements and relations of a problem that we wish to solve.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

8.1.1 Terminology

8.1.2 Directed Graph

8.1.3 Special Graphs

8.1.3.1 Simple Graph

8.1.3.2 Complete Graph

8.1.3.3 Subgraphs

8.2 The Concept of Graph Degrees

8.2.1 Degree of a Vertex

8.2.2 Total Degrees of a Graph

Reading: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs: Basic Concepts in Graph Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions, and Graphs: Basic Concepts in Graph Theory" (PDF)

Also Available in:
EPUB

Instructions: Read Definition 3 on pages GT-4 and GT-5.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.
See a broken link? Please let us know!

8.2.3 The Handshake Theorem

Reading: Wikipedia: "Handshaking Lemma"
Link: Wikipedia: “Handshaking Lemma” (PDF)

Instructions: Please read the entire article for a description of the Handshaking Lemma and the degree sum formula.

Terms of Use: The article above is released under a Creative Commons Attribution-Share-Alike License 3.0 (HTML). You can find the original Wikipedia version of this article here (HTML).
See a broken link? Please let us know!

8.3 Isomorphism of Graphs

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Graph Theory"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Graph Theory" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1.6. This reading also applies to 8.3.1 and 8.3.2.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011).. License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

8.3.1 Showing that Two Graphs are Isomorphic

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Graph Theory"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Graph Theory" (PDF)

Also Available in:
EPUB

Instructions: Read Section 1.6 on page 7. This reading is also applicable to Section 8.3.2 below.

Let G and H be two graphs. To show G and H are isomorphic, construct a bijection from the vertices of G to the vertices of H that preserves adjacency. The adjacency matrix, defined in Section 4 in Devadas and Lehman Lecture Graphs I, is helpful in supping the construction of an isomorphic mapping.
Let G and H be two graphs. G and H are not isomorphic if:
- there is no bijection from the vertices of G to H.
- there is no bijection that preserves adjacency of vertices.
- G and H have different properties, e.g. vertices have different degrees
Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

8.3.2 Showing that Two Graphs Are Not Isomorphic

8.4 Trees

Reading: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Graph Theory"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "GraphTheory" (PDF)

Also Available in:
EPUB

Instructions: Read Section 5 on Trees, pages 15-18. This reading also applies to 8.4.1 - 8.4.2, including the subsections: 8.4.2.1 - 8.4.2.3. Please note that the definition of Tree or the properties of trees (Theorem 8) can beused to determine if a Graph is a Tree or not.

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!

8.4.1 Determining if a Graph is a Tree or Not

8.4.2 Tree Types

Reading: The Saylor Foundation’s “Types of Tree”
Link: The Saylor Foundation’s “Types of Tree” (PDF)

Instructions: Please download the file linked here for a discussion of types of trees. This discussion applies to 8.4.2.1 - 8.4.2.3.
See a broken link? Please let us know!

8.4.2.1 Parse Trees

8.4.2.2 Decision Trees

8.4.2.3 Binary Trees

Assessment: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 5"
Link: MIT: Srini Devadas and Eric Lehman's Mathematics for Computer Science Course: "Assessments: Problem Set 5" (PDF)

Instructions: Do problems 1-6. You can check your answers on the solutions guide here. (PDF)

Terms of Use: Srini Devadas and Eric Lehman, Mathematics for Computer Science, Spring 2005. (Massachusetts Institute of Technology: MIT OpenCourseWare), http://ocw.mit.edu (Accessed September 8, 2011). License: Creative Commons BY-NC-SA 3.0.
See a broken link? Please let us know!
Assessment: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Lists, Decisions and Graphs, Unit GT: Basic Concepts in Graph Theory"
Link: University of California, San Diego: Edward Bender and S. Williamson's Discrete Mathematics Course: "Basic Concepts in Graph Theory" (PDF)

Also Available in:
EPUB

Instructions: Complete the Review Questions on pages GT52-GT55.

Terms of Use: The linked material above has been reposted by the kind permission of Edward Bender and S. Williamson. Please note that this material is under copyright and cannot be reproduced in any capacity without explicit permission from the copyright holder.

See a broken link? Please let us know!

Unit 9: Regular Expressions and Finite-State Automata

Computer language compilers frequently use regular languages (which feature regular expressions) to match patterns within text or perform lexical analysis. This unit will introduce formal languages and state automata to prove the correctness or falsity of a language. We will see that some languages might not be valid for a state automaton, but that we can also define and create state automata for languages defined using regular expressions.

The definition of regular expressions is recursive. This definition and difference between regular sets and regular expressions requires careful contemplation on your part.
The topic of Formal Languages and the related topic of Finite State Automata are not directly addressed in our two references. Our study of Discrete Structures has given us the background to develop these topics in Instruction paragraphs.

We begin with notation, terminology, and definitions and expressions for formal languages. Then we introduce finite automata and their relationship with regular expressions, and use them to solve problems.

Unit 9 Time Advisory show close

Unit 9 Learning Outcomes show close

9.1 Formal Languages

Reading: The Saylor Foundation’s “Formal Languages”
Link: The Saylor Foundation’s “Formal Languages” (PDF)

Instructions: Please download the file linked here for a discussion of grammars and formal languages. This discussion also applies to section 9.1.2.2 of this course.
See a broken link? Please let us know!

9.1.1 Polish Notation

Reading: The Saylor Foundation’s “Polish Notation”
Link: The Saylor Foundation’s “Polish Notation” (PDF)

Instructions: Please download the file linked here for a discussion of Polish Notation for describing expressions.
See a broken link? Please let us know!

9.1.2 Languages Defined by Regular Expressions

Reading: The Saylor Foundation’s “Languages Defined by Regular Expressions”
Link: The Saylor Foundation’s “Languages Defined by Regular Expressions” (PDF)

Instructions: Please download the file linked here for a discussion of languages defined by regular expressions.
See a broken link? Please let us know!

9.1.2.1 Order of Precedence Rules

Reading: The Saylor Foundation’s “Order of Precedence Rules”
Link: The Saylor Foundation’s “Order of Precedence Rules” (PDF)

Instructions: Please download the file linked here for a discussion of operator precedence.
See a broken link? Please let us know!

9.1.2.2 Set Notations and Language Descriptions

9.1.2.3 Deciding Whether Regular Expressions Define the Same Language

Reading: The Saylor Foundation’s “Deciding Whether Regular Expressions Define the Same Language”
Link: The Saylor Foundation’s “Deciding Whether Regular Expressions Define the Same Language” (PDF)

Instructions: Please download the file linked here for a discussion of operator precedence.
See a broken link? Please let us know!

9.2 Finite State Automata

Reading: The Saylor Foundation’s “Finite State Automata”
Link: The Saylor Foundation’s “Finite State Automata” (PDF)

Instructions: Please download the file linked here for a discussion of finite state automata. This reading also applies to 9.2.1-9.2.3 and is useful in solving assignment questions 5 and 6 for this unit.
See a broken link? Please let us know!

9.2.1 A Simple Example: a Vending Machine

9.2.2 Finite State Automaton Given by a Transition Diagram

9.2.3 Generating Finite State Automaton from Next-State Tables

9.2.4 Automaton and Accepted Language

Reading: The Saylor Foundation’s “Automata and Accepted Language”
Link: The Saylor Foundation’s “Automata and Accepted Language” (PDF)

Instructions: Please download the file linked here for a discussion of regular sets and their acceptance by finite state automata. This reading also applies to section 9.2.4.1 of this course.
See a broken link? Please let us know!

9.2.4.1 Finding the Language Accepted by an Automaton

9.2.4.2 Designing a Finite State Automaton

Reading: The Saylor Foundation’s “Designing a Finite State Automaton”
Link: The Saylor Foundation’s “Designing a Finite State Automaton” (PDF)

Instructions: Please download the file linked here for a discussion of hints on designing a finite state automaton to recognize a given regular set.
See a broken link? Please let us know!

9.2.5 Showing that a Language Is Not Regular

NOTE: Not all languages are regular. Because a finite state machine has a finite number of states, it can only 'remember' a finite number of inputs. Consider the set {oⁿ1ⁿfor all n >= 0}. Because this set requires a recognizing machine to remember n 0's for any n (so that it can then look for n 1's), the number of states is infinite, i.e. not a finite state machine. Thus, the language is not regular. Hence, one way to show that a language is not regular is to show that the automaton that recognizes it has an infinite number of states.

9.2.6 Simplifying Finite State Automata

Reading: The Saylor Foundation’s “Simplifying Finite State Automata”
Link: The Saylor Foundation’s “Simplifying Finite State Automata” (PDF)

Instructions: Please download the file linked here for a discussion ways to simplify a finite state automata.
See a broken link? Please let us know!
Assignment: The Saylor Foundation's "Unit 9 Assignment"
Link: The Saylor Foundation’s "Unit 9 Assignment" (PDF)

Instruction: Please download the file linked here for the assignment for Unit 9. Then, check your answers against the answer key.
See a broken link? Please let us know!
Assessment: The Saylor Foundation’s "Unit 9 Assessment"
Link: The Saylor Foundation’s “Unit 9 Assessment" (PDF)

Instructions: Please download the file linked here for the assessment for Unit 9. Then, check your answers against the answer key.
See a broken link? Please let us know!

Final Exam

Final Exam: The Saylor Foundation's CS202 Final Exam
Link: The Saylor Foundation's CS202 Final Exam

Instructions: You must be logged into your Saylor Foundation School account in order to access this exam. If you do not yet have an account, you will be able to create one, free of charge, after clicking the link.
See a broken link? Please let us know!

« Previous Unit Next Unit » Back to Top

Saylor.org

Resource Center

Legend

Discuss CS202 with other Saylor Students here!

Discrete Structures

Purpose of Course show close

Learning Outcomes show close

Course Requirements show close

Unit Outline show close

Saylor.org

Resource Center

Legend

Discuss CS202 with other Saylor Students here!

Discrete Structures

Purpose of Course showclose

Learning Outcomes showclose

Course Requirements showclose

Unit Outline show close

Purpose of Course show close

Learning Outcomes show close

Course Requirements show close