Discrete Structures
Purpose of Course showclose
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 knowhow required for an indepth study of the science and technology of the computer age.
Course Information showclose
Course Designer: J. M. Perry
Primary Resources: This course comprises a range of different free, online materials. However, the course makes primary use of the following materials:
 Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”
 University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic
 Saylor content
Requirements for Completion: In order to complete this course, you will need to work through each unit and all of its assigned materials.
Note that you will only receive an official grade on your final exam. However, in order to adequately prepare for this exam, you will need to work through the assigned materials in each unit.
In order to pass this course, you will need to earn a score of 70% or higher on the final exam. Your score on the exam will be tabulated as soon as you complete it. If you do not pass the exam, you may take it again.
Time Commitment: This course should take you about 105.5 hours to complete. Each unit includes a time advisory that lists the amount of time you are expected to spend on each subunit. These should help you plan your time accordingly. It may be useful to take a look at these time advisories and to determine how much time you have over the next few weeks to complete each unit, and then to set goals for yourself. For example, Unit 1 should take you approximately 9 hours to complete. Perhaps you can sit down with your calendar and decide to complete subunit 1.1 (a total of 3.5 hours) on Monday night; subunits 1.2 (a total of 2.75 hours) on Tuesday night; subunit 1.3 (a total of 2 hours) on Wednesday night; etc.
Tips/Suggestions: When completing the assigned readings, it may be helpful to take notes, so you can go back to study the concepts discussed.
Learning Outcomes showclose
 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 of 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 finite state machines;
 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, to make decisions or select from alternative choices, to calculate probabilities, to document derivation steps, or to solve problems; and
 construct and analyze finite state automata (another name for machines), formal languages, and regular expressions.
Course Requirements showclose
√ Have access to a computer;
√ Have continuous broadband Internet access;
√ Have the ability/permission to install plugins or software (e.g. Adobe Reader or 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.);
√ Have competency 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 skills in basic algebra and calculus.
Unit Outline show close

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, science, and, in particular, computer science. Logic deals with logical systems consisting 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.
Unit 1 Time Advisory show close
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, instructor, and 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.
Note: Discrete structures is the term used for discrete mathematics for computer science. Discrete mathematics is often referred to as finite mathematics.
Unit 1 Learning Outcomes show close

1.1 Compound Statements
Note: In logic, we define operations on statements, which result in new statements, i.e. compound statements, much like in arithmetic where we have operations on numbers that result in a new number. We will see some of these logic operations in the next subunit.

1.1.1 The NOT, AND, OR, and XOR Symbols
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1 through the end of Section 1.1.1 on 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.
Truth tables for operations  negation, conjunction, and disjunction are derived from the definition of the operation, as seen in this reading.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1: “Boolean Functions and Computer Arithmetic” up to example 6 on pages BF1 to BF4. Example 4 includes XOR. This reading presents material similar to Devadas and Lehman, but uses the language of Boolean functions. Throughout our study, we will see the relationship of English statements, logic, Boolean functions, and sets, and will learn how to translate between them to represent the same meaning. Exclusive OR is defined in example 4. Example5 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).
Truth tables for operations, such as exclusive OR, are derived from the definition of the operation, as seen in this reading.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”

1.1.2 Translating from English to Symbols
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic” (PDF)
Also Available in:
EPUB
Instructions: Read the beginning paragraphs in the Logic section up to Section 1, and then read Section 1.2 and Section 1.3 on pages 3  6.
This reading (and the following readings for this section) shows the relationship of natural language, in our case English, to the language of logic. Logic deals with simple statements, called propositions, that are either true or false, and operators  for example, NOT, AND, and OR  that combine propositions to form compound statements. Translating from English to logic involves analyzing English statements, i.e. parsing them, into elementary statements that can be expressed as propositions, connected by conjunctions, which usually can be expressed as logic operations. However, since natural languages are not always precise, we have to be careful to understand the semantics, or meaning, of an English statement and then express that same meaning using logic.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Read the beginning of Logic, “Section 1: Propositional Calculus,” from pages Lo1 to page Lo3, up to the “Implication” paragraph. This reading also applies to Subunit 1.1.3 of this course.
These brief readings further 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.5 below.
Reading this selection and taking notes should take approximately 15 minutes.
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.  Reading: The Saylor Foundation’s “Translating from English to Logic Symbols”
Link: The Saylor Foundation’s “Translating from English to Logic Symbols” (PDF)
Instructions: Download this reading for a brief summary and review of translating English to logic symbols.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”

1.1.3 Double Negative Property
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic” (PDF)
Also Available in:
EPUB
Instructions: Read example 3 on page BF2 in Section 1: “Boolean Functions and Computer Arithmetic” of the Bender and Williamson reading.
We have seen that some statements in English can be translated to logic. We have also seen in the Bender and Williamson reading in 1.1.1, the equivalence of logic and Boolean functions. The term “equivalence” is used here in the context of equivalence of representations. The term “equivalence” in logic is used to mean that two propositions have the same truth value. Thus, the same word has two similar, yet different, meanings depending on the context in which it is used. Assignment of true to a proposition corresponds to a Boolean function that maps the proposition to 1. Assignment of false to a proposition corresponds to a Boolean function that maps the proposition to 0. The logic operators are translated to operations on Boolean functions.
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,” as a Boolean function is written as, NOT (P), or ~P, where P is in the set {0,1}. As a unary logic operator, it is defined by the truth table referenced in subunit 1.1.1, and as a Boolean function it is defined in example 3 in Devadas and Lehman.
The truth table for NOT P, can 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 as logic operators. Using Boolean functions, NOT (NOT (P)) is evaluated as follows: P is either 0 or 1. When P is 1, NOT (NOT (1)) = 1. When P is 0, NOT (NOT (0)) = 0. Thus, NOT (NOT) (P) = identity function.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic”

1.1.4 Negations of AND and OR: DeMorgan’s Law
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic” and “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “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 BF6 and BF7. In the article on Logic, study Theorem 1 (Algebraic rules for statement forms) on page Lo3.
A similar argument could be used to prove DeMorgan’s law, which is very useful and widely used in communication, mathematics, engineering, and the sciences. Please make sure to familiarize yourself with DeMorgan’s law before moving on to other sections of this course.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: Please respect the copyright and terms of use displayed on the webpages above.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic” and “Arithmetic, Logic and Numbers: Unit Lo: Logic”

1.1.5 Tautologies and Contradictions
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Study definition 1 (Tautology, contradiction) in Section 1 on pages Lo2 and Lo3. 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.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”

1.2 Conditional Statements
Note: As you have likely noticed there is a similarity between the language of logic and a natural language, such as English. In fact, there is a similarity between implication in logic and the conditional statement in English, i.e. an if statement. In the follow subsections, we will study the application of operations to the logical if statement.

1.2.1 Logical Equivalences Using Conditional Statements
 Reading: Massachusetts Institute of Technology: Reading: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1.1.2 and Section 1.1.3 on pages 4 and 5. Section 1.1.3 of this reading also applies to Subunit 1.2.5.
The conditional statement in English can be translated to implication in logic.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Read the section titled “Implication” up to the exercises on pages Lo4  Lo9. For the English translation discussion, see example 3 on page Lo6 and Subunit 1.1.2 of this course. Example 3 also applies to Subunits 1.2.2, 1.2.3, and 1.2.4.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: Massachusetts Institute of Technology: Reading: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”

1.2.2 Negation of a Conditional Statement
Note: Conditional English sentences can be difficult to interpret, particularly when they are negated. Logic helps us to correctly interpret such statements. This topic, negation of a conditional statement, is addressed in the reading on implication in Subunit 1.2.1.

1.2.3 Contrapositive of a Conditional Statement
Note: Given a conditional statement, we can derive several new statements from it by inserting negation and/or inverting the antecedent and consequent. For example, from P implies Q, we can derive NOT Q implies NOT P. These two statements, namely the implication, P implies Q, and the derived statement are logically equivalent. This derivation is called the contrapositive of the implication. Contrapositive is discussed in the Bender and Williamson reading in Subunit 1.2.1.

1.2.4 Converse and Inverse of a Conditional Statement
Note: In addition to negation of a conditional statement and contrapositive, two other common derivations from a conditional statement are the converse and inverse. These are discussed in the readings for Subunit 1.2.1.

1.2.5 If and Only If, Necessary and Sufficient Conditions
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Read example 5 on pages Lo7  Lo8. Note that in the statement A if and only if B, abbreviated A iff B, A is called the necessary part and B the sufficient part.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”

1.2.6 Proving Validity or Invalidity of an Argument Using Truth Tables
 Reading: Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1.2 on pages 5 and 6 and 1.4 on pages 6  8 to learn about logical equivalence of statements. The term validity refers to an argument or proof. We say an argument is valid if its conclusion logically follows from its premises. We can do this by showing that a statement is logically equivalent to a premise, or by showing that a statement logically follows from a premise. Logically follows from, or is a consequence of, means that the conclusion is true if the premise is true.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit BF: Boolean Functions and Computer Arithmetic” (PDF)
Also Available in:
EPUB
Instructions: Read example 7 on pages BF7 and BF8. This is an example where a given expression is transformed into a logically equivalent expression, which, in turn, is translated into another equivalent express, and so on.
Reading this selection and taking notes should take approximately 30 minutes.
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.  Reading: The Saylor Foundation’s “Validity and Arguments”
Link: The Saylor Foundation’s “Validity and Arguments” (PDF)
Instructions: Read through the entire text linked here.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”

1.3 Modus Ponens and Modus Tollens
Note: A proof, or an argument, is a series of statements where each statement logically follows from the previous one(s). Logically follows means that there is a logic rule of inference that derives it from the previous statement(s). One famous rule of inference is modus ponens, which we will study in the next subunits.

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. Rules of inference are used to show that one statement is a consequence of another statement and, thus, are used for constructing proofs. 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
Reading this selection and taking notes should take approximately 45 minutes.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0You can find the original Wikipedia version of this article here.  Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Proofs”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Proofs” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1, “The Axiomatic Method,” up to Section 3 on pages 3  7. Please note that reading Section 3 on pages 7  9 is optional.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Review example 4 (Right Triangles and the Pythagorean theorem) on pages Lo6  Lo7. It illustrates some of the rules of inference.
Reading this selection and taking notes should take approximately 30 minutes.
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.  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: This is a summary of Modus Ponens and other types of reasoning.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: Wikipedia: “List of Rules of Inference, Table: Rules of Inference  A Short Summary”

Unit 1: Assesment 1
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 1”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 1” (PDF)
Instructions: Complete problem #1. You can check your answers on the solutions guide here. (PDF)
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 1”

Unit 1: Assesment 2
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: 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.
1 y in P y in Q y in P
>
y in Qa in Q NOT (a in Q) [(y in P) >
(y in Q)] /
(NOT (a in Q))2 F F T F T T 3 F F T T F F 4 F T T F T T 5 F T T T F F 6 T F F F T T 7 T F F T F F 8 T T T F T T 9 T T T T F F
SINCE y is a variable, it HOLDS for a specific value, y = a, and we can REPLACE y with a in the table. This yields a table for [(a in P) > (a in Q)] / [NOT (a in Q)].
The hypothesis included that a is not in Q. This occurs for the rows: 2, 4, 6, and 8. Rows 4 and 8 are not applicable because they state (a in Q) and (a not in Q), which can’t occur, at least not in our reality. Look at row 6; it states that the implication, (a in P) > (a in Q) is false; our hypothesis states otherwise, namely we assume it’s true. Therefore, only row 2 is applicable; row 2 states a in P is false, which is what we wanted to prove, i.e. a is not in P.
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, and then use logic to prove the hypothesis.
Completing this assessment should take approximately 30 minutes.
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.
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”

Unit 1: Assesment 3
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Do review Questions 1  6 on page Lo23.
Completing this assessment should take approximately 30 minutes.
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.
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”

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, etc. 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.
Unit 2 Time Advisory show close
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 Learning Outcomes show close

2.1 Quantified Statements
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic” (PDF)
Also Available in:
EPUB
Instructions: Read Section 3 through 3.1 on pages 11 and 12. This reading introduces the universal quantifier and the existential quantifier. Logic without quantifiers is called propositional calculus; logic with quantifiers is called the (first order) predicate calculus.
Reading this selection and taking notes should take approximately 45 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics</em>: “Arithmetic, Logic and Numbers: Unit Lo: Logic”(PDF)
Also Available in:
EPUB
Instructions: Read Section 2: “Predicate Logic” up to and including Definition 4 on pages Lo12 and Lo13. 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. This is essentially what we do when we translate from English to logic. In other words, translation is using one domain, e.g. logic, to represent another domain, and setting up an association between symbols in one to those of the other. 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.
For an understanding of the universal quantifier, study Definition 4, on page Lo12, which is critically important for the study of logic, science and mathematics. This definition also defines the existential quantifier. These two quantifiers are often used together, as the examples in the next subunits will show.
Reading this selection and taking notes should take approximately 1 hour.
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.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”

2.1.1 Translating between Formal and Informal Languages
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer ScienceM: “Logic”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic” (PDF)
Also Available in:
EPUB
Instructions: Read Sections 3.2 on page 12 and 3.6 on pages 14 and 15. This reading also pertains to the topic in subunit 2.1.2. This reading shows how logic (a formal language) can be used to describe sets (another formal language).
Reading this selection and taking notes should take approximately 45 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Read Definition 5 up to and including example 8 on pages Lo13 and Lo14. This reading also applies to the topic for Subunit 2.1.2 of this course. This reading gives important examples of using logic to represent statements in mathematics. As you read this text, please keep in mind that formal language includes logic, binary functions, sets, and programming languages. Informal language includes English and other natural languages. Please note that translating from informal to informal language for subunit 2.1.2 involves rewriting an informal statement into a different but equivalent statement.
Reading this selection and taking notes should take approximately 1 hour.
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.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer ScienceM: “Logic”

2.1.2 Translating from Informal to Informal Language
Note: The Bender and Williamson reading for 2.1.1 addresses translating from informal to informal language(s). In our study of logic, our primary interest is translating between logic and English (or natural languages). In addition, you will find it useful to translate between informal (that is, natural) languages. For example, suppose you have an English statement that you find difficult to translate to logic. Rewriting or translating the statement to an equivalent English statement usually makes the translation to logic easy. Translating between informal or natural languages also occurs when we translate from one natural language to another, for example, from English to Spanish.

2.2 Operating on Quantified Statements
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic” (PDF)
Also Available in:
EPUB
Instructions: Read Sections 3.3 and 3.4 on page 13. We have seen the use of quantifiers in representing statements in other languages, e.g. English, mathematics, and programming. The next step is to see how statements with quantifiers can be combined and transformed using logic rules. This reading looks at statements that have both types of quantifiers, i.e. universal and existential, used together; it also looks at the order in which the quantifiers appear.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Read example 15 on page Lo19. Here you read about the use of quantifiers together with the use of logic operations, such as AND, OR.
As you study and read, you should THINK about the material, both on what it means in relation to what you already know and how it relates to other topics you have studied. To help you think about the material, you should look at the exercises, even if the instructions don’t explicitly state this.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”

2.2.1 Negations of Quantified Statements
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic” (PDF)
Also Available in:
EPUB
Instructions: Read Section 3.5 on page 14 on the use of quantifiers with negation.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Please read example 9 and example 10 on pages Lo14 and Lo15. These readings apply to the topics in 2.2.1.1, 2.2.1.2, and 2.2.2 through 2.2.4. Here is where you will have to apply some of your selflearning skills: you should review what a contrapositive, converse, and inverse are, and use what you have learned about how quantifiers and negation affect one another.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Logic”

2.2.1.1 Negating a Universal Statement
Note: The reading for 2.2.1 includes negation of statements having quantifiers. Given a statement in logic, as you have seen with the propositional logic, we can negate it. We can do the same for a statement in predicate logic. Then, once we negate it, how can we rewrite the negated statement as a logically equivalent statement, so that the negation applies to the parts of the statement, rather than the entire statement? Why do we care? Because by doing so, we often simplify the statement or put it into a more convenient form for a particular purpose. In effect, we can study ways to translate from logic to logic in order to obtain a statement that is more convenient for what we might need.

2.2.1.2 Negating an Existential Statement
Note: The reading for 2.2.1 also includes the negation of an existential quantifier.

2.2.2 Contrapositive of a Statement Having a Universal or Existential Quantifier
Note: The reading for 2.2.1 also includes other “transformations,” in addition to negation, of a logic statement that uses quantifiers. In particular, that reading addresses the contrapositive of a statement having a quantifier.

2.2.3 Converse of a Statement Having a Universal or Existential Quantifier
Note: Just as with negation and contrapositive, the reading for 2.2.1 covers the converse of a statement having a quantifier.

2.2.4 Inverse of a Statement Having a Universal or Existential Quantifier
Note: Just as with negation and contrapositive, the reading for 2.2.1 covers the converse of a statement having a quantifier.

2.3 Statements Containing Multiple Quantifiers
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Read from example 11 up to Exercises for Section 2 on pages Lo16  Lo19. These readings also apply to topics in subunits 2.3.1 and 2.3.2. The examples work with multiple quantifiers and pertain to translation between logic and math and English domains.
Reading this selection and taking notes should take approximately 45 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic”

2.3.1 Translating Statements with Multiple Quantifiers from Formal to Informal Language
Note: This topic is covered by the reading in subunit 2.3. The direction of the translation in this topic, from formal to informal language, is typically done to communicate a result obtained from logic, back to the language in which the problem was specified.

2.3.2 Translating Statements with Multiple Quantifiers from Informal to Formal Language
Note: This topic is covered by the reading in subunit 2.3. The “direction” of this translation, from a natural language to logic, is done to apply logic to a problem in some other discipline or everyday task (e.g. history, science; making a decision, debating). Furthermore, in applying logic, we also find it useful to translate from logic to logic (to transform a statement into a more convenient form), and to translate from a natural language to a natural language to simplify translation to logic.

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: 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.
Limits are studied in continuous mathematics, such as the differential and integral calculus, and in analysis. Discrete mathematics (which is studied in discrete structures) provides the concepts that are used in defining topics in continuous mathematics. This is illustrated with the reading for this topic.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: The Saylor Foundation’s “Definition of a Limit”

Unit 2: Assessment 1
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 1”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 1” (PDF)
Instructions: Solve problems 2 and 3. You can check your answers in the solutions guide here. (PDF)
Completing this assessment should take approximately 1 hour.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 1”

Unit 2: Assessment 2
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit Lo: Logic” (PDF)
Also Available in:
EPUB
Instructions: Complete review questions 7  11 on page Lo24  Lo25.
Completing this assessment should take approximately 1 hour.
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.
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit Lo: Logic”

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: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Proofs”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Proofs” (PDF)
Also Available in:
EPUB
Instructions: Read the opening discussion, “Proofs,” Section 1, “The Axiomatic Method,” and Sections 2  6, inclusive. In Unit 3, you will get a chance to apply a lot of what you have thought about and mastered in Units 1 and 2. Our domain of discourse is number theory, in particular proofs in elementary number theory.
Consider the following comparison of direct and indirect proofs. A direct proof is an argument that shows that the conclusion logically follows from the premises or assumptions by applying rules of inference in a sequence of steps.
Sections 1, 2, 4, and 5 deal with direct proofs. Section 2, “Proving an Implication,” refers to statement such as P implies Q, and proving that Q is a consequence of P. In a logic system, P logically follows from the axioms and valid statements of the logic system, is another way of saying that P is a consequence of the axioms and valid statements or P is implied by them. This is what is meant by proving an implication.
Section 3 is related to indirect proof. Section 6 discusses indirect proof, also known as proof by contradiction, directly. 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.)
Reading this selection and taking notes should take approximately 1 hour.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Read example 1  example 4 on pages SF3  SF6. It discusses proofs for sets.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Proofs”

3.1.1 Odd and Even Numbers
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1 through example 1 on pages NT1 and NT2. There are several commonly used sets of numbers that will be introduced to you; the first is the set of odd and even integers, i.e. the set of integers.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”

3.1.2 Prime Numbers
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit NT: Number Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “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 NT3, and continue up to example 3 on page NT4. Example 3 also applies to 3.1.4 and 3.2.2 below. Prime numbers are the next set of commonly used numbers to be introduced. The introduction of prime numbers leads to the discussion of factoring an integer.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit NT: Number Theory”

3.1.3 Proving and Disproving Universal Statements
Note: Statements often involve universal quantifiers. The following subunits examine ways used to prove or disprove such statements.

3.1.3.1 Proof by Using the Method of Exhaustion
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory” (PDF)
Also Available in:
EPUB
Instructions: Reread example 2 on page NT2, with special attention to the proof method, called proof by induction (an exhaustive proof method). This material also applies to the topic in subunit 3.3.1.1 of this course. This reading discusses a universal statement, which is just a statement that involves universal quantification.
Reading this selection and taking notes should take approximately 15 minutes.
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.  Reading: The Saylor Foundation’s “Proof by Exhaustion”
Link: The Saylor Foundation’s “Proof by Exhaustion” (PDF)
Instructions: This reading comments on proof by exhaustion.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”

3.1.3.2 Disproof by Counterexample
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory” (PDF)
Also Available in:
EPUB
Instructions: Read over the Exercises for Section 1 on pages NT10  NT13. 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.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”

3.1.4 Proving and Disproving an Existential Statement
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory” (PDF)
Also Available in:
EPUB
Instructions: Read example 5 on pages NT5 and NT6. 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.
Reading this selection and taking notes should take approximately 30 minutes.
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
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”

3.2 Numbers: Direct Proofs and Counterexamples
Note: Logic has application to other parts of mathematics, not just to reasoning about the world. The following subunits apply logic to statements about numbers.

3.2.1 Rational Numbers
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “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 NT5. This example proves an important property of rational numbers using a constructive proof technique. This reading also applies to the topic in subunit 3.2.3 of this course.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”

3.2.2 Irrational Numbers
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1: “Basic Facts about Numbers,” example 5 on pages NT5 and NT6 and example 6 on pages NT7  NT9. Example 5 proves a property of real numbers using counterexamples. Example 6 applies to integer, rational, and real numbers. This reading also applies to the topics in Subunits 3.2.3 and Subunit 3.3.
Reading this selection and taking notes should take approximately 45 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”

3.2.3 Proving Properties of Rational Numbers
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Notes for Recitation 2”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Notes for Recitation 2” (PDF)
Instructions: Read the recitation on pages 1  5. These give more examples of proof techniques for numbers.
Reading this selection and taking notes should take approximately 45 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Notes for Recitation 2”

3.3 Divisibility: Direct Proofs and Counterexamples
Note: The following subunits continue the appliction of logic to number theory.

3.3.1 Divisibility
Note: The following subunits examine important properties of divisibility.

3.3.1.1 Divisibility Definition
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1, “Divisibility” on pages 1  4 and Section 4, “The Greatest Common Divisor” on pages 7  12. This reading overlaps that of Bender and Williamson.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory” (PDF)
Also Available in:
EPUB
Instructions: Read “Remainders and Modular Arithmetic,” page NT6 to the top of NT9. Section 2 and Section 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 Subunits: 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.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I”

3.3.1.2 Divisors of Zero and Division by Zero
Note: Division by zero is covered in the Bender and Williamson above.
We say that division by zero is undefined. Why do we say that? Consider the following line of reasoning: suppose x is a nonzero number, and when it is divided by zero, the result is the specific number y. It can be proved that, if x / 0 = y, then x = 0 multiplied by y (i.e. x = 0 * y). But, then, x = 0 * y = 0, because any number multiplied by 0 is 0. However, we assumed that x was non zero, a contradiction.
If x were 0, then x / 0 = 0 / 0 = y. Again, this implies that 0 = 0 * y. This, in turn, implies that y could be any number. This is, again, a contradiction, because we assumed that y was a specific number.
Mathematical definitions and proofs are specified to adhere to certain rules. One of those rules is that results do not lead to contradictions. Therefore, we say that division by 0 is not defined. 
3.3.1.3 The Positive Divisors of a Positive Number
Note: This topic is also covered by the Bender and Williamson in Subunit 3.3.1.1. Theorem 1 on page NT3 states that for any given integer, > or = 2, can be written as the product of prime numbers. Each of these primes will be a divisor of the given integer.

3.3.1.4 Divisibility of Algebraic Expressions
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction I”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction I” (PDF)
Instructions: Read Section 3, “A Divisibility Theorem.” This reading also applies to the topics in subunits 3.3.2, 3.3.2.1, 3.3.2.2, and 3.3.2.3 of this course.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: The Saylor Foundation’s “General Theorem: Divisibility of Algebraic Expression”
Link: The Saylor Foundation’s “General Theorem: Divisibility of Algebraic Expression” (PDF)
Instructions: Read the text in its entirety.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction I”

3.3.2 Proving Properties of Divisibility
Note: The readings for the following subunits prove some properties of divisibility (in particular, the fundamental theorem of arithmetic), which we typically use often in arithmetic.

3.3.2.1 Transitivity of Divisibility
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I” (PDF)
Also Available in:
EPUB
Instructions: Review Lemma 1 in Section 1.1 on page 2.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I”

3.3.2.2 Divisibility by a Prime
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I” (PDF)
Also Available in:
EPUB
Instructions: Read Section 5, “The Fundamental Theorem of Arithmetic,” on pages 12  15.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I”

3.3.2.3 The QuotientRemainder Theorem
 Reading: Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1.2, which presents the Division theorem in its entirety on pages 2  5.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Number Theory I”

Unit 3: Assessment 1
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 3”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 3” (PDF)
Instructions: Solve problems 4  7. You can check your answers on the solutions guide here. (PDF)
Reading this selection and taking notes should take approximately 1 hour.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 3”

Unit 3: Assessment 2
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory and Cryptography”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory and Cryptography” (PDF)
Also Available in:
EPUB
Instructions: Complete the review questions at the end of the chapter on pages NT26  NT28.
Reading this selection and taking notes should take approximately 1 hour.
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.
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit NT: Number Theory and Cryptography”

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. Mathematics has a variety 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.
Unit 4 Time Advisory show close
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 Learning Outcomes show close

4.1 Sequences
Note: Sequences of numbers often arise in the applications of mathematics. Sometimes a sequence is defined using a formula; sometimes a sequence is defined by just listing the terms of the sequence in order.

4.1.1 Finding Terms of Sequences Given by Explicit Formula
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequences, and Series”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequences, and Series” (PDF)
Also Available in:
EPUB
Instructions: Read Section 2, “Sequences” on pages IS12  IS19. In addition, read the examples mentioned below. This reading also applies to subunits 4.1.2 and 4.1.3.
See the definition of alternating sequence, immediately before example 14. Please pay particular attention to examples 7, 14 (optional), 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 write f(n)n >= k. See the exercises for section 2 for examples.
Reading this selection and taking notes should take approximately 3 hours.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequences, and Series”

4.1.2 An Alternating Sequence
Note: This topic is covered by the reading in Subunit 4.1.1. If one takes the first term of a sequence, then the sum of the first two terms, then the sum of the first three terms, and so on, the result is a new sequence, called a series. Alternating series are defined on page IS24 of the Bender and Williamson reading above. An alternating sequence is defined just like an alternating series; namely, the signs of the adjacent terms of the sequence alternate in their signs.

4.1.3 Finding an Explicit Formula to Fit Given Initial Terms
Note: The problem of finding an explicit formula for a sequence or series is, in general, a hard problem. In some cases, there might not even exist such a formula.
Finding an explicit formula pertains to three situations:
1. Given a sequence of numbers, find a general formula for the nth term of the sequence that depends on the n1 term.
2. Given a sequence of numbers, find a general formula for the nth term of the sequence that depends on n.
3. Given a sequence of numbers, find a general formula for the nth term of the sequence that depends on one or more of the preceding terms.
If the sequence has certain properties  such as the ability of each term to be calculated from the preceding term  as in an arithmetic sequence (where a fixed number is added to the n1 term to obtain the nth term), or a geometric sequence (where a fixed number is used to multiply the n1 term, to obtain the nth term), then one could use that information to deduce a formula for each term. Thus, one makes assumptions about the relationship of the n1 term and the nth term. Or, if one is given a formula for each term that depends on that term, one could deduce a formula for the nth term.
Examples 7 and 17 of the reading in Subunit 4.1.1 touch on this topic.
An example for the third situation above is that of the Fibonacci series  f(n) = n + (n1) and f(0) = 0, f(1) = 1. (Note: Fibonacci numbers also appear in Section 7.1.4 below).Chapter 1, Section 2 and Chapter 2, Section 2 in the reading in Subunit 4.2 below touch on this topic for series. 
4.2 Summation
 Reading: MIT: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums and Approximations”
Link: MIT: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums and Approximations” (PDF)
Also Available in:
EPUB
Instructions: Read this lecture. Take your time to understand the transition from one step to the next in the proofs. This can be time consuming, but it is rewarding. Don’t let the topic of the examples  annuities, for example  distract you. The domains (e.g. annuities, Taylor series, etc.) are important, but so is the method they illustrate. The method is more general than the specific domain of the example.
The reading mentions induction as a way of proving some of the expressions and then continues to give insight into the source of the expression. We will cover induction in Subunit 4.5 of this course.
Reading this selection and taking notes should take approximately 3 hours.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: MIT OpenCourseWare. The original version can be found here.
Note: This reading applies to Sections 4.2.1, 4.2.2, and 4.3.2 below.
 Reading: MIT: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums and Approximations”

4.2.1 Computing Summations
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series” (PDF)
Also Available in:
EPUB
Instructions: Read Section 3 on pages 20  30.
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).
Reading this selection and taking notes should take approximately 2 hours.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series”

4.2.2 Properties of Summation
 Reading: The Saylor Foundation’s “Summation Properties”
Link: The Saylor Foundation’s “Summation Properties” (PDF)
Instructions: Read this brief note on summation.
Reading this selection and taking notes should take approximately 30 minutes.
 Reading: The Saylor Foundation’s “Summation Properties”

4.3 Products
Note: As for summation, we will now look at products, calculating them and their properties.

4.3.1 Product Notation
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence and Series”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence and Series” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1 on pages 1  11. ∏ is the symbol for product. If p_{1} , p_{2, }... , p_{k ... }is a sequence, the series p_{1 }, p_{1} p_{2 }, p_{1} p_{2 }p_{3} , p_{1} p_{2 , }... , p_{k }is written ∏ p_{1} p_{2 }... 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 Subunit 4.3.2.
Reading this selection and taking notes should take approximately 1 hour.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence and Series”

4.3.2 Computing Products
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums and Approximations”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums and Approximations” (PDF)
Also Available in:
EPUB
Instructions: Study Section 3.4 “Approximating 1 + x.”
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 ∏ pi = ∏ a pi, where the ∏ ranges over a set of positive integers i.
2. ∏ pi ∏ qij = ∏ pi qj, where the product symbols varies over ranges for i and j.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence and Series”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence and Series” (PDF)
Also Available in:
EPUB
Instructions: Read Theorem 11 and example 17 on pages IS27 through IS30. In doing calculation involving series, we work with sums (since a series is the sum of the succeeding terms of a sequence). In working these calculations, we also encounter the product of terms, for example when determining whether a series is bounded.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums and Approximations”

4.4 Factorial Notation
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums, Approximations, and Asymptotics II”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums, Approximations, and Asymptotics II” (PDF)
Also Available in:
EPUB
Instructions: Read Section 2 “The Factorial Function.” The reading also applies to the Subunit 4.4.1 and Subunit 4.4.2. In reading for Subunit 4.4.2, below, see the binomial theorem and its generalization to the multinomial theorem.
Reading this selection and taking notes should take approximately 1 hour.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums, Approximations, and Asymptotics II”

4.4.1 The First Ten Factorials
Note the first ten factorials: 10! 9! 8! 7! 6! 5! 4! 3! 2! 1! = 10^{1} x 9^{2 }x 8^{3 }x 7^{4 }x 6^{5 }x 5^{6 }x 4^{7 }x 3^{8 }x 2^{9 }x 1^{10}.

4.4.2 Computing with Factorials
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting II” and “Counting III”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting II” (PDF) and “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.”
Reading this selection and taking notes should take approximately 1 hour.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting II” and “Counting III”

4.5 Mathematical Induction
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction I”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction I” (PDF)
Instructions: You have encountered mathematical induction in some of the previous readings in this course. Read Sections 1 and 2 on pages 1  4. This reading also applies to Subunits 4.5.1, 4.5.2, and 4.5.4 below. As you read about induction in the references, note that induction has a relationship to recursion.
Reading this selection and taking notes should take approximately 1 hour.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: MIT OpenCourseWare. The original version can be found here.  Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction III”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction III” (PDF)
Also Available in:
EPUB
Instructions: Read Section 2 on pages 2  5 and Section 4 on pages 8  12. These readings give helpful guidance in correct use of induction.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction I”

4.5.1 Application of Principle of Mathematical Induction
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence and Series” (PDF)
Also Available in:
EPUB
Instructions: Study the applications of induction in Section 1 on pages IS1 through IS8.
This reading is a good formal review. Again, the presentation relies on a lot of examples. Don’t forget to look over the exercises at the end of the section. Some of these examples will be utilized in following subunits.
Reading this selection and taking notes should take approximately 1 hour.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series”

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 Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1, example 2 on page IS2.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series”

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 Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence and Series”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence and Series” (PDF)
Also Available in:
EPUB
Instructions: Read Theorem 2 on pages 5  7, example 11 on page 22, and example 12 on page 23. Some of the examples are more difficult, but hard examples push our understanding and expand our skill.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence and Series”

4.5.4 Proving Divisibility by Induction
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction I”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction I” (PDF)
Instructions: Read Section 3 and Section 4 on pages 5  7.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction I”

4.5.5 Proving an Inequality by Induction
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series” (PDF)
Also Available in:
EPUB
Instructions: Read example 4 on pages 3 and 4.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic and Numbers: Unit IS: Induction, Sequence, and Series”

4.6 Loop Invariants
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction III”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction III” (PDF)
Also Available in:
EPUB
Instructions: Read Section 3.2. The reading presents a proof that an initial configuration of the 9number 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.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: The Saylor Foundation’s “Loop Invariants”
Link: The Saylor Foundation’s “Loop Invariants” (PDF)
Instructions: Review this article for more information on invariants. This reading also applies to Subunits 4.6.1  4.6.4, where more detail is given about the four components of a loop invariant.
Reading this selection and taking notes should take approximately 30 minutes.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Induction III”

4.6.1 Basis Property
Note: The reading “Loop Invariants” in subunit 4.6defines the four components of a loop invariant. The first of these is the basis property, which is the start condition for performing the statements of the loop. The basis property is the value of an expression that is true before performing the statements of a loop.

4.6.2 Inductive Property
Note: The inductive property is the key property of a loop invariant. If the statements of the loop are performed, the basis property is still true after performing the statements of the loop.

4.6.3 Eventual Falsity of Guard
Note: The eventual falsity of the guard is necessary to stop the loop so that it is not performed continuously, i.e. an infinite loop.

4.6.4 Correctness of the PostCondition
Note: The fourth property of a loop invariant is the correctness of the postcondition − the value of the base expression when the guard is false, i.e. when the loop terminates.

Unit 4: Assessment 1
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 2” and “Problem Set 3”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 2” and “Problem Set 3” (PDF)
Instructions: Solve problems 1  4 in “Problem Set 2”; complete problems 1 and 3 in “Problem Set 3.” You can check your solutions for “Problem Set 2” here and for “Problem Set 3” here.
Completing this assessment should take approximately 3 hours.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of TechnologyOpenCourseWare. The original version can be found here.
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 2” and “Problem Set 3”

Unit 4: Assessment 2
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit IS: Induction, Sequence, and Series”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit IS: Induction, Sequence, and Series” (PDF)
Also Available in:
EPUB
Instructions: Complete the multiplechoice review questions are at the end of the unit on pages IS31  IS33.
Completing this assessment should take approximately 2 hours.
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.
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Arithmetic, Logic, and Numbers: Unit IS: Induction, Sequence, and Series”

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.
Unit 5 Time Advisory show close
Set theory is a fundamental tool of mathematics and often used as the starting point for its study and to define basic concepts, such as functions, numbers, and limits.
Unit 5 Learning Outcomes show close

5.1 Definition of Set Theory
Note: Set theory may seem strange until you get used to it. Then, it’s so natural that you will often think in terms of sets but this comes with familiarity. So think carefully about the following material, because it is VERY important.

5.1.1 Set Notation
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study the notation used for sets in Section 1 on pages SF1 to SF2. This reading also applies to Subunits 5.1.2 and 5.2.1  5.2.5.
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 an element of A; and a ÏA, for a not an element of A. Examples of sets can be found everywhere. All the units in this course comprise a set. The collection of people related to you comprises a set. Sets can be described using English descriptions, predicates in logic, or mathematical functions, in particular Boolean functions. A set can also be defined by listing the members of the set. A set can be finite, having a finite number of members; a set can be infinite. The number of elements of a set is one obvious property of a set.
The members, or elements, of a set can be anything, even sets themselves. For example, {a, b, {a, b}} is a set of 3 members, and one of the members is a set.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.1.2 Set Equality
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study Definition 1 on page SF1. Typically, when an object is defined in mathematics, we next define when two of those objects are equal. Then we define operations on those objects. Now, for the objects are sets. When are two sets equal?
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. The number of subsets of a set A, is denoted 2A (the reason for this notation will become clear when you study functions.)
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.
Note that the order of the elements in a set does not change the set. Work sufficient examples to ensure that you completely understand the concept of set equality.
Reading this selection and taking notes should take approximately 1 hour.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”

5.2 Set Operations
Note: Recall that in logic, operations for building compound statements were defined. We do the same for sets, i.e. define operations for building new sets from old sets.

5.2.1 The Union Operator
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study set operations and the property of set operations Section 1 on pages SF2  SF3. Set Union is defined on page SF2. Note that A È B = {x : x ∈A or x ∈B}. You will read and reread this section several times, each time focusing on a basic set operation. These basic operations are so fundamental and ubiquitous (i.e. occur so frequently in mathematics, computer science, and their applications) that they deserve more than a quick reading. Work a lot of examples.
Reading this selection and taking notes should take approximately 1 hour.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”

5.2.2 The Difference Operator
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: This reading is the same as that for the previous section. For this section, study the definitions of complement and set difference on page SF2. AB = {x : x ∈A and x Ï B}, is called set difference, or the complement of B with respect to A.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”

5.2.3 The Intersection Operator
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study the reading on set intersection, defined on page SF2. Note: A ∩ B = {x : x ∈A and x ∈B}.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”

5.2.4 The Complement of a Set
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: This time, focus on complement of a set. Complement is set difference with respect to the largest set, called the universal set, namely, E  A is the complement of A. E is the universal set, the set of all elements; when sets are defined, the type of the elements is specified. For example, in a set of all red cars, the type of the members in this example, is car. We also say that the domain of the elements is the (universal) set of all cars. The complement is also written A’. Note: A’ = {x : x Ï A} = {x : x Î E and x Ï A}, where E is the universal, containing all theelements.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”

5.2.5 Cartesian Products
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: One last time, look over the above reading. Now study the product of sets defined on page SF2, just before the section titled “Set Properties and Proofs.” 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. Clearly, it is analogous to multiplication of numbers.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”

5.2.6 Binary Relation
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Read example 10 on page SF16.
Given a set A, a binary relation, R on A, is a subset of A x A. Note that a binary relation is a set of order pairs (x, y) where x and y are in A. The next subunits define properties of a binary relation, reflexive and symmetric. A third property is transitivity.
Relations are another critically important concept in set theory, functions, science, and every other subject. Work a lot of examples.
Reading this selection and taking notes should take approximately 1 hour.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”

5.2.6.1 Reflexive
Note: A binary relation on A is reflexive, if (a, a) ∈R.

5.2.6.2 Symmetric
Note: A binary relation is symmetric if (a, b) ∈R, then (b, a) ∈R.

5.2.6.3 Transitive
Note: A binary relation is transitive if (a, b) ∈ R, (b, c) ∈ R, then (a, c ) ∈ R. There is an important consequence of a binary relation being reflexive, symmetric, and transitive. A binary relation that has all 3 properties is called an equivalence relation. If a binary relation on A is an equivalence relation, it determines a partition of A. A partition of A is a set of subsets of A, which are mutually disjoint, and whose union is A.

5.3 Set Identities and Proof of Set Identities
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Read “Set Properties and Proofs” on pages SF2  SF6. This reading applies to 5.3.1  5.3.3, 5.3.7, 5.3.9, and 5.3.10.
Reading this selection and taking notes should take approximately 1 hour.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.1 Commutative Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study Theorem 1, on pages SF2 and SF3, on the commutative laws: A È B = B È A, A Ç B = B Ç A. Prove the commutative laws.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.2 Associative Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study Theorem 1 on pages SF2 and SF3 on the associative laws: (A È B) È C = A È (B È C) = A È B È C. Note that we can write the rightmost expression, which has no parenthesis, because È is associative. Replacing È by the intersection operations, gives the associative law for intersection. Prove the associative laws.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.3 Distributive Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study Theorem 1 on pages SF2 and SF3 on the distributive laws: A È (B Ç C) = (A È B) Ç (A È C); A Ç (B È C) = (A Ç B) È (A Ç C). The former shows union distributes over intersection; and the latter shows intersection distributes over union. Prove the distributive laws.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.4 Identity Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study the identities (equality of two set expressions) on pages SF3 and SF4 (the top of SF3 and examples 2, 3, and 4). It follows from the definition of the empty set that A È Ø = A, A Ç Ø = Ø. Prove these identities.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.5 Complement Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study the identities involving complement on pages SF3 and SF4. For universal set E, E’ = Ø= A ∩ A’; A  A = Ø. Study example 1 on SF4; VENN diagrams are a visual representation of sets, which are useful for depicting set membership of complements as well as other sets resulting from set operations. Use a VENN diagram to prove one of the identities involving complement.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.6 Double Complement Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study Theorem 1 on pages SF2 and SF3. Double complement is also referred to as double negative: (A’) ‘ = A. Take the identities in the theorem involving set difference or complement. Insert a second difference or complement operator, thus creating some new set equations, and check whether the new set equations are still identities. Prove or disprove several of the equations you created by adding a second difference or complement operation.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.7 Idempotent Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study the idempotent identities of Theorem 1 on pages SF2 and SF3. An idempotent is an object A such that (A operation A) = A. The idempotent laws for union and intersection are: A È A = A, A Ç A = A. Prove several of the idempotent identities.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.8 Universal Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study the identities involving the universal set in Theorem 1 and in examples 1 and 2 on pages SF2 to SF4. Note that it follows that A È A’ = E, E Ç A = A. Prove some of the identities involving the universal set.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.9 DeMorgan’s Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study Theorem 1 on pages SF2 and SF3 on DeMorgan’s laws: (A È B) ‘ = A’ Ç B’; (A Ç B)’ = A’ È B’. In English, the complement of A union B is the intersection of A complement and B complement; and the complement of A intersect B is the complement of A union the complement of B. DeMorgan’s laws are famous and appear in many places in mathematics, engineering, and computer science. Prove DeMorgan’s Laws.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.10 Absorption Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study Theorem 1 on pages SF2 and SF3 on absorption laws: If A ⊂ B, then A È B = B, A Ç B = A; or more generally, P È (P Ç Q), = P, P Ç (P È Q) = P. These are called absorption identities because one of the sets is absorbed by the other(s). Prove the absorption laws.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

5.3.11 Set Difference Laws
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Study pages SF1 and SF2, and Theorem 1 on pages SF2 and SF3. The set difference laws: A  (B È C) = (A  B) Ç (A  C); A  (B Ç C) = (A  B) È (A  C) follow from the definition of set difference and DeMorgan’s laws. Prove these identities using the fact the A  B = A Ç B’.
Reading this selection and taking notes should take approximately 30 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

Unit 5: Assessment 1
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 1”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 1” (PDF)
Instructions: Solve problems 5 and 6. You can check your answers on the solutions guide here (PDF).
Completing this assessment should take approximately 1 hour and 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 1”

Unit 5: Assessment 2
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions” (PDF)
Also Available in:
EPUB
Instructions: Work on the review questions at the end of the chapter on pages SF29  SF32.
Completing this assessment should take approximately 1 hour and 30 minutes.
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.
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence, and Order: Unit SF: Sets and Functions”

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.
Unit 6 Time Advisory show close
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 Learning Outcomes show close

6.1 Definitions and Basic Counting
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability” (PDF)
Also Available in:
EPUB
Instructions: Read from the Introduction to Probability through Section 1.2. This reading motivates our study of probability and also counting  because counting often comes up in the analysis of problems that we solve using probability.
Reading this selection and taking notes should take approximately 15 minutes to complete.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”

6.1.1 What Is a Sample Space?
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1.3 on pages 3  5. The previous reading introduced a fourstep process for building a probabilistic model to analyze and solve problems using probability. This reading discusses the first step.
Reading this selection and taking notes should take approximately 15 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”

6.1.2 What Is an Event?
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1.4 on pages 5  6. This reading discusses the second step of the fourstep process for building a probabilistic model for solving probability problems.
Reading this selection and taking notes should take approximately 15 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”

6.1.3 Equally Likely Probability Formula
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1.5 and Section 1.6 on pages 6  9. This reading discusses the third and fourth steps of the fourstep process for building a probabilistic model for solving probability problems. In the third step, probabilities are assigned using the possibility tree drawn during steps one and two. In step three, probabilities are assigned to the edges of the tree. At each level of the tree, the branches of a node represent possible outcomes for that node. If the outcomes of a node are assigned the same probability (the outcomes of a node add to 1), we say that they represent equally likely outcomes.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”

6.1.4 Counting Elements of Lists and Sublists
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting I”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting I” (PDF)
Also Available in:
EPUB
Instructions: Read “Counting I” through Section 1.4. It presents some strategies and rules that aid us in counting members of sets arising in the analysis of probability problems.
This reading also applies to Subunit 6.1.5 below.
Reading this selection and taking notes should take approximately 1 hour.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting I”

6.1.5 Counting Elements of a OneDimensional Array
Note: Section 1.3 of the reading for Subunit 6.1.4 illustrates the bijection rule for arrays and lists. The bijection rule can be applied to counting the elements of an array. The elements of a list can be mapped via a bijection to a onedimensional array. Thus, because we can count the elements of a list, we can count the elements of such an array. (We count the elements of a list, by walking down the list and incrementing a tally, initialized to zero, by one for each item of the list.)

6.2 Possibility Trees and Advanced Counting
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting I”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting I” (PDF)
Also Available in:
EPUB
Instructions: You have read this selection in Subunit 6.1.4 above. Each of the analyses discussed in “Counting I” can be illustrated by drawing a tree. Take another look at Section 2.1 and Section 2.2 of the readings on the sum rule and the product rule. These will be covered in a subunit below but are mentioned here to explain what a possibility tree is. If you illustrate these rules by drawing a tree, it will depict all the elements of a union of disjoint sets (sum rule) and of the product of sets (multiplication rule). If these sets represent outcomes for events, then the tree is called a possibility tree.
Reading this selection and taking notes should take approximately 15 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting I”

6.2.1 Possibility Trees and the Multiplication Rule
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability” (PDF)
Also Available in:
EPUB
Instructions: Read up to Section 1.3. Look at the line drawings beginning in Section 1.3 and in following sections; 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.
Multiplicationoften applies to each level of the tree, i.e. each node at level 1 is expanded (multiplied) by the same number of branches at level 2, and so on, for each level. If the outcomes of an event for a probability problem are modeled using a tree is called a possibility tree.
Reading this selection and taking notes should take approximately 45 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”

6.2.2 Permutation
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”
Link: Massachusetts Institute of Technology : Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1.3 for the definition of a permutation, how to count permutations, and a reminder of Stirling’s formula, which approximates n!
Reading this selection and taking notes should take approximately 15 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”

6.2.3 Counting Elements of Sets: Addition, Product, and Division Rules
 Reading: Massachusetts Institute of Technology : Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting I”
Link: Massachusetts Institute of Technology : Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting I” (PDF)
Also Available in:
EPUB
Instructions: This topic was covered in Subunit 6.1. Revisit Section 2, “Two Basic Counting Rules,” of the reading to reinforce your understanding of the counting rules, focusing on 2.1: “The Sum Rule” and 2.2: “The Product Rule.”
Reading this selection and taking notes should take approximately 15 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting II”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting II” (PDF)
Also Available in:
EPUB
Instructions: Study “Counting II” from the beginning through Section 1.2; then study the division rule covered in Section 2. Lastly, study Section 3, which discusses counting elements of the union of sets, extending the addition rule: disjoint sets and, then, nondisjoint sets.
Reading this selection and taking notes should take approximately 45 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology : Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting I”

6.2.4 The Difference Rule
Note: The difference rule is as follows: the number of elements in B  A equals (the number of elements in B) minus (the number of elements in B intersect A). In symbols # (B  A) = # (B)  # (B Ç A).

6.2.5 Combinations
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting III”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting III” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1 on pages 1  3. Section 1.1 and Section 1.2 discuss counting sequences; Section 1.3 discusses counting combinations.
Reading this selection and taking notes should take approximately 15 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting III”

6.2.6 The Algebra of Combinations
 Reading: The Saylor Foundation’s “Combinations”
Link: The Saylor Foundation’s “Combinations” (PDF)
Instructions: Read this article for more information on the algebra of combinations.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: The Saylor Foundation’s “Combinations”

6.2.6.1 Pascal’s Triangle
Pascal’s triangle is a simple, manual way to calculate binomial coefficients.
Note: In the previous Saylor reading, look at the table at the bottom of the reading. The first column, (0,1,2,3,4,5), contains the numbers of the rows  the 0th row, 1st row, 2nd row, etc.  and corresponds to the exponent ‘n’ in (x + y)n .
Ignore the first column for the moment. Take the nth row and shift it n spaces to the left, i.e. the 0th row is not shifted, the 1st row is shifted 1 space to the left, the 2nd row is shifted 2 spaces to the left, the 3rd row is shifted 3 spaces to the left, etc. This shifting results in a shape of a triangle  ‘1’ is at the top of the triangle in the 0th row, ‘1 1’ is next in the 1st row offset by one space (so that the ‘1’ at the top is above the space in ‘1 1’), etc. This triangle for n from 0 to 5 generalizes to any n and is called Pascal’s triangle. These numbers are the coefficients for the binomial equation presented in the following subunit. 
6.2.6.2 The Binomial Theorem
 Reading: Massachusetts Institute of Technology : Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting III”
Link: Massachusetts Institute of Technology : Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting III” (PDF)
Also Available in:
EPUB
Instructions: Read Section 2, which defines the binomial expansion expressed in the binomial theorem, that is, the expansion of (a + b)^{n}. The binomial expansion is very important because it is used to make approximations in many domains, including the sciences, engineering, weather forecasting, economics, and polling.
The expansion of (a + b)n is a polynomial whose coefficients are the integers in the nth row of Pascal’s Triangle (see Subunit 6.2.6.1 above).
Reading this selection and taking notes should take approximately 15 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology : Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Counting III”

6.3 Probability Process
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability” (PDF)
Also Available in:
EPUB
Instructions: Read Section 2, which presents a fourstep process for solving probability problems. This process incorporates basic probability axioms, albeit indirectly, as part of the process steps.
Reading this selection and taking notes should take approximately 1 hour.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”

6.3.1 Probability Axioms
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions, and Graphs: Unit CL: Counting and Listing” (PDF)
Instructions: Read Section 4 on pages CL28 through CL30.
Some useful results are summarized here:
∑_{xε S }P(x) = 1, where S is the sample space, also written P(S) = 1;

P(x) >=0, for x in the sample space;

Let E be an event, defined as a subset of S. P(E) = ∑_{xε E}P(x);

If E and D are events such that E is contained in D, then P(E) <= P(D); and
 P(E È D) = P(E) + P(D) for E, D disjoint.
Reading this selection and taking notes should take approximately 30 minutes.
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. 
∑_{xε S }P(x) = 1, where S is the sample space, also written P(S) = 1;
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Sets, Equivalence and Order: Unit SF: Sets and Functions”

6.3.2 The Probability of the Complement of an Event
Note the probability of the complement of an event E is 1  (probability of E). This result is often very useful, because for some problems the probability of E may be difficult to calculate, but the probability of the complement of E may be easy to calculate.

6.3.3 The Probability of a General Union of Two Events
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Conditional Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Conditional Probability” (PDF)
Also Available in:
EPUB
Instructions: Read Section 4, “Conditional Probability Pitfalls,” in particular, “Conditional Probability Theorem 2” and “Theorem 3” on page 12. This will serve as a leadin to conditional probability, which is covered in the next section.
Reading this selection and taking notes should take approximately 45 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Conditional Probability”

6.4 Conditional Probability and Independent Events
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability” (PDF)
Also Available in:
EPUB
Instructions: Focus on the modeling advice and steps 1  4 on pages 1  9.
Reading this selection and taking notes should take approximately 45 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Conditional Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Conditional Probability” (PDF)
Also Available in:
EPUB
Instructions: Read this lecture. Try to understand the concepts of conditional probability, and just scan the examples. We’ll take a closer look at the problems in the next section.
Reading this selection and taking notes should take approximately 1 hour.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Introduction to Probability”

6.4.1 Computing a Conditional Probability
 Activity: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Conditional Probability”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Mathematics for Computer Science: “Conditional Probability” (PDF)
Also Available in:
EPUB
Instructions: Work through the following examples in this lecture:
Section 1, “The Halting Problem” (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, “OnTime Airlines” on page 15.
Completing this activity should take approximately 1 hour and 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here. 
Section 1, “The Halting Problem” (fictitious name of a hockey team) on page 2;
 Activity: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Conditional Probability”

6.4.2 Bayes’s Theorem
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions, and Graphs: Unit DT: Decision Trees and Recursion”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions, and Graphs: Unit DT: Decision Trees and Recursion” (PDF)
Also Available in:
EPUB
Instructions: Read Section 3 on pages DT28 through DT35.
Bayes’ theorem is a famous theorem for computing conditional probabilities. Assume E_{i }are mutually exclusive events for i = 1,..., n and U_{i }E_{i }= D, for arbitrary event D, P(E_{i } D) = P(D  E_{i} ) P(E_{i}) / [P(DE_{1})P( E_{1}) + ....+ P(DE_{n}) P(E_{n})]. Statements of Bayes’ theorem are given on pages DT28 and DT32. Like the binomial theorem, Bayes’ theorem is very useful in calculating probabilities for many applications, for example, in diagnosis and in decision theory.
Reading this selection and taking notes should take approximately 45 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions, and Graphs: Unit DT: Decision Trees and Recursion”

6.4.3 Computing the Probability of Independent Events
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Independence”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Independence” (PDF)
Also Available in:
EPUB
Instructions: Read this lecture for practice with the probability of independent events.
Reading this selection and taking notes should take approximately 1 hour and 15 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Independence”

Unit 6: Assessment 1
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 3,” “Problem Set 7,” and “Problem Set 8”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 3”, “Problem Set 7”, and “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.
Completing this assessment should take approximately 1 hour and 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 3,” “Problem Set 7,” and “Problem Set 8”

6.6 Unit 6: Assessment 2
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit CL: Counting and Listing” and “Unit DT: Decision Trees and Recursion”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit CL: Counting and Listing” (PDF) and “Unit DT: Decision Trees and Recursion” (PDF)
Also Available in:
EPUB (Counting and Listing)
EPUB (Decision Trees and Recursion)
Instructions: Complete the multiplechoice review questions are at the end of the unit on pages CL41  CL44 in the “Counting and Listing” document. Then, complete review questions 17  23 on pages DT55  DT57 in the “Decision Trees and Recursion” document.
Completing this assessment should take approximately 1 hour and 30 minutes.
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.
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit CL: Counting and Listing” and “Unit DT: Decision Trees and Recursion”

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.
Unit 7 Time Advisory show close
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 Learning Outcomes show close

7.1 Recursively Defined Sequences
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit DT: Decision Trees and Recursion”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “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 on pages DT42  DT46.
Notice that the definition of induction, in “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(n1) 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(n1).
Reading this selection and taking notes should take approximately 30 minutes.
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.
Note: This reading also applies to subunits 7.1.1  7.1.4.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit DT: Decision Trees and Recursion”

7.1.1 Computing Terms of a Recursively Defined Sequence
Note: Given a recursive relation, the terms of its recursively defined sequence are computed by evaluating the relation for the base value, say n = 1, then evaluating it for successive values of n.

7.1.2 Sequences that Satisfy the Same Recurrence Relation
Note: Given a recursive equation, also called a recursive relation, Theorem 7 on page DT43 of the reading in Subunit 7.1 tells us how to verify a solution for it.

7.1.3 Converting Sequences with Explicit Formulas to Recurrence (Recursive) Relation
Note: Let f(n) be an explicit formula for the nth term, A_{n}, of a sequence and assume that f(n) = A b^{n} + K = A b^{n} + K + Kb  Kb = A b^{n} + Kb + K  Kb = b (A b^{n1 }+ 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.

7.1.4 The Towers of Hanoi and the Fibonacci Numbers
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions, and Graphs: Unit DT: Decision Trees and Recursion”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions, and Graphs: Unit DT: Decision Trees and Recursions” (PDF)
Also Available in:
EPUB
Instructions: The examples listed here illustrate the concepts in Subunit 7.1.3 and are examples of recursion. For the Fibonacci numbers, see theorem 9 and example 29 on pages DT48  DT49. Example 29 starts with the sequence, F_{0} = F_{1 }= 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.
For the Towers of Hanoi problem, see example 11 on pages DT18  DT19.
This example solves a famous puzzle with a recursive solution, namely a solution for n discs in terms of a solution for n1 and 1 discs.
Reading this selection and taking notes should take approximately 1 hour and 15 minutes.
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.  Optional Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Recurrences”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Recurrences” (PDF)
Also Available in:
EPUB
Instructions: This reading presents an alternative illustration of the use of a recursive equation to solve the Tower of Hanoi problem. Read Section 1 on pages 1  5.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions, and Graphs: Unit DT: Decision Trees and Recursion”

7.2 Solving Recurrence Relations
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit DT: Decision Trees and Recursion”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “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 on pages DT46  DT50
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 DT44 up to example 26 on page DT46.
1. A solution to a recursive equation can be found by inspection of the terms of a given sequence (example 27); OR
2. Apply theorem 8 if A(n) depends on A(n  1) and theorem 9, if A(n) depends on A(n  1) and A(n  2).
Reading this selection and taking notes should take approximately 1 hour and 15 minutes.
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.
Note: This reading also applies to Subunits 7.2.1 and 7.2.2.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit DT: Decision Trees and Recursion”

7.2.1 Using the Method of Iteration
Note: We have seen in subunit 4.5 that mathematical induction and recursion are related. Likewise, recursion is related to iteration, as you will notice in Subunits 7.2.1.1 and 7.2.1.2.

7.2.1.1 Finding a Formula for a Recurrence Relation for an Arithmetic Sequence
Regarding Theorem 8 on page DT48 of the reading in Subunit 7.2, if a^{n} = ba^{n  1} +c , then iterating, a^{n} = b( ba^{n  2}+c) + c = b(b (b a^{n  3}+ c ) + c ) + c= ....= a_{0 }b^{n} + c b^{n1} + c b^{n2} + .... + 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.

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 Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit DT: Decision Trees and Recursion”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “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^{n }, ar^{n, }= r a r ^{n1 }= r a _{n  1}, . Continuing in this manner, we get the formula, a_{n }= r^{n} a_{0}.
For another example, read over Exercise 4.7 on page DT51. It discusses going from an iterative sequence to a recursive solution/equation, and vice versa, from the recursive equation to an iterative sequence.
Reading this selection and taking notes should take approximately 30 minutes.
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.  Reading: Massachusetts Institute of Technology: : Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums and Approximations”
Link: Massachusetts Institute of Technology: : Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Sums and Approximations” (PDF)
Also Available in:
EPUB
Instructions: Note that you have already read this lecture in Subunit 4.2. Focus on rereading Section 1.2 on page 3, which finds a formula not for the terms of the sequence, but for the sum of the terms of the sequence.
Reading this selection and taking notes should take approximately 15 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology: OpenCourseWare. The original version can be found here.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit DT: Decision Trees and Recursion”

7.2.2 Using Mathematical Induction
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: Lists, Decisions and Graphs: “Unit DT: Decision Trees and Recursion”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit DT: Decision Trees and Recursion” (PDF)
Also Available in:
EPUB
Instructions: Read Section 4 on pages DT42 to DT44 up to “Recursion Equations.” Note that mathematical induction and recursion are closely related concepts.
Reading this selection and taking notes should take approximately 45 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: Lists, Decisions and Graphs: “Unit DT: Decision Trees and Recursion”

7.3 Recursive Functions
Note: Many wellknow functions are defined recursively. Several such functions are presented in the next few subunits.

7.3.1 McCarthy’s 91 Function
 Reading: Wikipedia: “McCarthy 91 Function”
Link: Wikipedia: “McCarthy 91 Function” (PDF)
Instructions: Read the 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.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia: “McCarthy 91 Function”

7.3.2 The Ackermann Function
 Reading: Wikipedia: “Ackermann Function”
Link: Wikipedia: “Ackermann Function” (PDF)
Instructions: Read the Wikipedia article for a description of the Ackermann function, an example of a recursive function that grows very rapidly.
Reading this selection and taking notes should take approximately 1 hour.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia: “Ackermann Function”

Unit 7: Assessment 1
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 6”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “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.
Completing this assessment should take approximately 1 hour and 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 6”

Unit 7: Assessment 2
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit DT: Decision Trees and Recursion”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “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 DT53 and DT54.
Completing this assessment should take approximately 1 hour and 30 minutes.
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.
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit DT: Decision Trees and Recursion”

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 a study of tree and graph properties. Trees and graphs have application to 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: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Graph Theory”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Graph Theory” (PDF)
Also Available in:
EPUB
Instructions: Read this article.
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.
Think of graphs as models for representing the elements and relations of a problem that we wish to solve.
Reading this selection and taking notes should take approximately 2 hours.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Graph Theory”

8.2 The Concept of Graph Degrees
Note: Think about a graph and imagine some properties that a graph might have that are characteristic of a graph  essential properties, i.e. not superficial properties like the labels for the nodes. Think some more about how we might define quantitative properties, i.e. those properties that take on numeric values. The following subunits present some thinking on these matters.

8.2.1 Total Degrees of a Graph
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Basic Concepts in Graph Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions, and Graphs: Basic Concepts in Graph Theory” (PDF)
Also Available in:
EPUB
Instructions: Read Definition 3 on pages GT4 to GT5.
Reading this selection and taking notes should take approximately 15 minutes.
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.
 Reading: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Basic Concepts in Graph Theory”

8.2.2 The Handshake Theorem
 Reading: Wikipedia: “Handshaking Lemma”
Link: Wikipedia: “Handshaking Lemma” (PDF)
Instructions: Read the article for a description of the handshaking lemma and the degree sum formula.
Reading this selection and taking notes should take approximately 15 minutes.
Terms of Use: The article above is released under a Creative Commons AttributionShareAlike License 3.0. You can find the original Wikipedia version of this article here.
 Reading: Wikipedia: “Handshaking Lemma”

8.3 Isomorphism of Graphs
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Graph Theory”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Graph Theory” (PDF)
Also Available in:
EPUB
Instructions: Read Section 1.6. Isomorphism of two graphs is a formal way of saying that two graphs are essentially the same. Essentially the same means that they are the same with respect to specified properties that characterize a graph.
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, is helpful in supping the construction of an isomorphic mapping.
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; and
 G and H have different properties, e.g. vertices have different degrees.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here. 
there is no bijection from the vertices of G to H;
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Graph Theory”

8.4 Trees
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: Graph Theory
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Graph Theory” (PDF)
Also Available in:
EPUB
Instructions: Read Section 5 on trees on pages 15  18. Please note that the definition of tree or the properties of trees (Theorem 8) can be used to determine if a graph is a tree.
Reading this selection and taking notes should take approximately 30 minutes.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.  Reading: The Saylor Foundation’s “Types of Trees”
Link: The Saylor Foundation’s “Types of Trees” (PDF)
Instructions: Read this article for a discussion of types of trees.
Reading this selection and taking notes should take approximately 30 minutes.
 Reading: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: Graph Theory

Unit 8: Assessment 1
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 5”
Link: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 5” (PDF)
Instructions: Solve problems 1  6. You can check your answers on the solutions guide here.
Completing this assessment should take approximately 2 hours.
Terms of Use: This resource is licensed under a Creative Commons AttributionNonCommercialShareAlike 3.0 Unported License. It is attributed to Srini Devadas, Eric Lehman and Massachusetts Institute of Technology: Massachusetts Institute of Technology OpenCourseWare. The original version can be found here.
 Assessment: Massachusetts Institute of Technology: Srini Devadas and Eric Lehman’s Mathematics for Computer Science: “Problem Set 5”

Unit 8: Assessment 2
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit GT: Basic Concepts in Graph Theory”
Link: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit GT: Basic Concepts in Graph Theory” (PDF)
Also Available in:
EPUB
Instructions: Complete the review questions on pages GT52  GT55.
Completing this assessment should take approximately 2 hours.
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.
 Assessment: University of California, San Diego: Edward Bender and S. Williamson’s Lectures in Discrete Mathematics: “Lists, Decisions and Graphs: Unit GT: Basic Concepts in Graph Theory”

Unit 9: Regular Expressions and FiniteState 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.
Unit 9 Time Advisory show close
The definition of regular expressions is recursive. This definition and that of 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 Learning Outcomes show close

9.1 Formal Languages
 Reading: The Saylor Foundation’s “Formal Languages”
Link: The Saylor Foundation’s “Formal Languages” (PDF)
Instructions: Read this discussion of grammar and formal languages.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: The Saylor Foundation’s “Formal Languages”

9.1.1 Polish Notation
 Reading: The Saylor Foundation’s “Polish Notation”
Link: The Saylor Foundation’s “Polish Notation” (PDF)
Instructions: Read this discussion of Polish notation for describing expressions.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: The Saylor Foundation’s “Polish Notation”

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: Read this discussion of languages defined by regular expressions.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: The Saylor Foundation’s “Languages Defined by Regular Expressions”

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: Read this discussion of operator precedence.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: The Saylor Foundation’s “Order of Precedence Rules”

9.1.2.2 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: Download the linked file for a discussion of operator precedence.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: The Saylor Foundation’s “Deciding Whether Regular Expressions Define the Same Language”

9.2 Finite State Automata
 Reading: The Saylor Foundation’s “Finite State Automata”
Link: The Saylor Foundation’s “Finite State Automata” (PDF)
Instructions: Read this discussion on finite state automata.
Reading this selection and taking notes should take approximately 30 minutes.
 Reading: The Saylor Foundation’s “Finite State Automata”

9.2.1 Automaton and Accepted Language
 Reading: The Saylor Foundation’s “Automaton and Accepted Language”
Link: The Saylor Foundation’s “Automaton and Accepted Language” (PDF)
Instructions: Read this discussion of regular sets and their acceptance by finite state automata.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: The Saylor Foundation’s “Automaton and Accepted Language”

9.2.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: Read this discussion of hints on designing a finite state automaton to recognize a given regular set.
Reading this selection and taking notes should take approximately 15 minutes.
 Reading: The Saylor Foundation’s “Designing a Finite State Automaton”

9.2.3 Showing that a Language Is Not Regular
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^{n }1^{n }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.4 Simplifying Finite State Automata
 Reading: The Saylor Foundation’s “Simplifying Finite State Automata”
Link: The Saylor Foundation’s “Simplifying Finite State Automata” (PDF)
Instructions: Read this discussion of ways to simplify finite state automata.
Reading this selection and taking notes should take approximately 30 minutes.
 Reading: The Saylor Foundation’s “Simplifying Finite State Automata”

Unit 9: Assignment 1
 Assignment: The Saylor Foundation’s “Unit 9 Assignment”
Link: The Saylor Foundation’s “Unit 9 Assignment” (PDF)
Instruction: Please complete this assignment. Then, check your answers against the answer key.
Completing this assignment should take approximately 3 hours.
 Assignment: The Saylor Foundation’s “Unit 9 Assignment”

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.
 Final Exam: The Saylor Foundation’s “CS202 Final Exam”