Topic Name Description
Course Introduction Course Syllabus
1.1.1: The NOT, AND, OR, and XOR Symbols Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Logic"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Boolean Functions and Computer Arithmetic"

Read Section 1: "Boolean Functions and Computer Arithmetic" up to example 6 on pages BF-1 to BF-4. 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.

1.1.2: Translating from English to Symbols Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Logic"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic, and Numbers: Logic"

Read the beginning of Logic, "Section 1: Propositional Calculus," from pages Lo-1 to page Lo-3, 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.

Translating from English to Logic Symbols

Read this article for a brief summary and review of translating English to logic symbols.

1.1.3: Double Negative Property University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Boolean Functions and Computer Arithmetic"

Read example 3 on page BF-2 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.

1.1.4: Negations of AND and OR: DeMorgan's Law University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Boolean Functions and Computer Arithmetic"

Study Theorem 2 (Algebraic rules for Boolean Functions) on pages BF-6 and BF-7.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic, and Numbers: Logic"

Study Theorem 1 (Algebraic rules for statement forms) on page Lo-3.

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.

1.1.5: Tautologies and Contradictions University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic, and Numbers: Logic"

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

1.2.1: Logical Equivalences Using Conditional Statements Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Logic"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic, and Numbers: Logic"

Read the section titled "Implication" up to the exercises on pages Lo-4 - Lo-9. For the English translation discussion, see example 3 on page Lo-6 and Subunit 1.1.2 of this course. Example 3 also covers the Negation of a Conditional Statement, the Contrapositive of a Conditional Statement, and the Converse and Inverse of a Conditional Statement.

1.2.2: If and Only If, Necessary and Sufficient Conditions University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic, and Numbers: Logic"

Read example 5 on pages Lo-7 - Lo-8. 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.

1.2.3: Proving Validity or Invalidity of an Argument Using Truth Tables Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Logic"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Boolean Functions and Computer Arithmetic"

Read example 7 on pages BF-7 and BF-8. 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.

Validity and Arguments

1.3: Modus Ponens and Modus Tollens Wikipedia: "List of Rules of Inference"

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
Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Proofs"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic, and Numbers: Logic"

Review example 4 (Right Triangles and the Pythagorean theorem) on pages Lo-6 - Lo-7. It illustrates some of the rules of inference.

Modus Ponens and Other Types of Reasoning

Read this summary of Modus Ponens and other types of reasoning.

2.1: Quantified Statements Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Logic"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Logic"

Read Section 2: "Predicate Logic" up to and including Definition 4 on pages Lo-12 and Lo-13. 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 Lo-12, 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.

Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Logic"

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).

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Logic"

Read Definition 5 up to and including example 8 on pages Lo-13 and Lo-14. 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.

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 Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Logic"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Logic"

Read example 15 on page Lo-19. 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.

Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Logic"

Read Section 3.5 on page 14 on the use of quantifiers with negation.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Logic"

Please read example 9 and example 10 on pages Lo-14 and Lo-15. 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 self-learning 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.

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.3: Statements Containing Multiple Quantifiers University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Logic"

Read from example 11 up to Exercises for Section 2 on pages Lo-16 - Lo-19. 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.

The direction of the translation 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.

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.

Definition of a Limit

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.

3.1: Direct Proofs and Indirect Proofs Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Proofs"

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.)

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Sets and Functions"

Read example 1 through example 4 on pages SF-3 to SF-6. It discusses proofs for sets.

3.1.1: Odd and Even Numbers University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Number Theory"

Read Section 1 through example 1 on pages NT-1 and NT-2. 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.

3.1.2: Prime Numbers University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Number Theory"

Read Section 1 beginning at "Prime Numbers and Factorization" on page NT-3, and continue up to example 3 on page NT-4. 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.

3.1.3.1: Proof by Using the Method of Exhaustion University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Number Theory"

Reread example 2 on page NT-2, with special attention to the proof method, called proof by induction (an exhaustive proof method). This reading discusses a universal statement, which is just a statement that involves universal quantification.

A statement may be provable by evaluating it or by manipulating the symbols using definitions, rules, and theorems to transform the statement to an equivalent statement. Use of truth tables to evaluate a statement is an example of the former. This is also an example of the Method of Exhaustion. If a Universal statement has a finite set for its bound variable (a variable that is quantified is bound and the set of values that it can take is its range or domain), then it can be proven by proving it for each value in the range of the bound variable. If the set is countable, a proof by induction may be applicable. Induction is studied in Unit 4 of this course. Equivalently, the Universal statement can be proved by showing that it is true for an arbitrary value.

3.1.3.2: Disproof by Counterexample University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Number Theory"

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

3.1.4: Proving and Disproving an Existential Statement University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Number Theory"

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

3.2.1: Rational Numbers University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Number Theory"

Read Section 1: "Basic Facts about Numbers," example 4 on page NT-5. 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.

3.2.2: Irrational Numbers University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Number Theory"

Read Section 1: "Basic Facts about Numbers," example 5 on pages NT-5 and NT-6 and example 6 on pages NT-7 - NT-9. Example 5 proves a property of real numbers using counterexamples. Example 6 applies to integer, rational, and real numbers.

3.2.3: Proving Properties of Rational Numbers Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Notes for Recitation 2"

Read the recitation on pages 1 - 5. These give more examples of proof techniques for numbers.

3.3.1.1: Divisibility Definition Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Number Theory I"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Number Theory"

Read "Remainders and Modular Arithmetic," page NT-6 to the top of NT-9. 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. In considering divisors of zero 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.

We say that division by zero is undefined. Why do we say that? Consider the following line of reasoning: suppose x is a non-zero 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.

Theorem 1 on page NT-3 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.2: Divisibility of Algebraic Expressions Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Induction I"

Read Section 3, "A Divisibility Theorem."

3.3.2: Proving Properties of Divisibility Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Number Theory I"

Review Lemma 1 in Section 1.1 on page 2. Then Read Section 5, "The Fundamental Theorem of Arithmetic," on pages 12 - 15. Finally, Read Section 1.2, which presents the Division theorem in its entirety on pages 2 - 5.

4.1: Sequences University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Induction, Sequences, and Series"

Read Section 2, "Sequences" on pages IS-12 - IS-19. 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.

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 IS-24 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.

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 n-1 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 n-1 term to obtain the nth term), or a geometric sequence (where a fixed number is used to multiply the n-1 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 n-1 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.

An example for the third situation above is that of the Fibonacci series - f(n) = n + (n-1) and f(0) = 0, f(1) = 1.

4.2: Summation Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Sums and Approximations"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Induction, Sequences, and Series"

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).

Summation Properties

Read this brief note on summation.

4.3.1: Product Notation University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Induction, Sequences, and Series"

Read Section 1 on pages 1 - 11. ∏ is the symbol for product. If p1 , p2, ... , pk ... is a sequence, the series p1 , p1 p2 , p1 p2 p3 , p1 p2 , ... , pk is written ∏ p1 p2 ... pk. 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.

4.3.2: Computing Products Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Sums and Approximations"

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.

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Induction, Sequences, and Series"

Read Theorem 11 and example 17 on pages IS-27 through IS-30. 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.

4.4: Factorial Notation Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Sums, Approximations, and Asymptotics II"

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.

Note the first ten factorials: 10! 9! 8! 7! 6! 5! 4! 3! 2! 1! = 101 x 92 x 83 x 74 x 65 x 56 x 47 x 38 x 29 x 110.

Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Counting II" and "Counting III"

In "Counting II", read Section 1.3, "Permutations." In "Counting III", read Section 1.3, "Combinations" and Section 2, "Binomial Theorem."

4.5: Mathematical Induction Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Induction I"

You have encountered mathematical induction in some of the previous readings in this course. Read Sections 1 and 2 on pages 1 - 4. As you read about induction in the references, note that induction has a relationship to recursion. Then, read Section 3 and Section 4 on pages 5 - 7.

Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Induction III"

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

University of California, San Diego: Edward Bender and S. Williamson's "Arithmetic, Logic and Numbers: Induction, Sequences, and Series"

Study the applications of induction in Section 1 on pages IS-1 through IS-8. Then, read Section 1, example 2 on page IS-2. Finally, 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. Afterwards, read example 4 on pages 3 and 4.

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.

4.6: Loop Invariants Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Induction III"

Read Section 3.2. The reading presents a proof that an initial configuration of the 9-number 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.

5.1.1: Set Notation University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study the notation used for sets in Section 1 on pages SF-1 to SF-2.

A set is a collection of elements, called members of the set. Sets are denoted using capital letters; elements are denoted using small letters. We write a ∈ A for a an element of A; and a $\notin$ 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 comprise 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.

5.1.2: Set Equality University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study Definition 1 on page SF-1. 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 $\subset$ 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 $\subset$ B and B $\subset$ 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.

5.2.1: The Union Operator University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study set operations and the property of set operations Section 1 on pages SF-2 - SF-3. Set Union is defined on page SF-2.

Set Union is defined on page SF-2. Note that A $\cup$ 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.

5.2.2: The Difference Operator University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

This reading is the same as that for the previous section. For this section, study the definitions of complement and set difference on page SF-2.

A-B = {x : x ∈A and x $\notin$ B}, is called set difference, or the complement of B with respect to A.

5.2.3: The Intersection Operator University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study the reading on set intersection, defined on page SF-2. Note: A ∩ B = {x : x ∈ A and x ∈ B}.

5.2.4: The Complement of a Set University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

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.

5.2.5: Cartesian Products University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

One last time, look over the above reading. Now study the product of sets defined on page SF-2, 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.

5.2.6: Binary Relation University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

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.

A binary relation on A is reflexive, if (a, a) ∈ R.

A binary relation is symmetric if (a, b) ∈ R, then (b, a) ∈ R.

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 University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Read "Set Properties and Proofs" on pages SF-2 - SF-6.

5.3.1: Commutative Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study Theorem 1, on pages SF-2 and SF-3, on the commutative laws: A $\cap$ B = B $\cap$ A, A $\cup$ B = B $\cup$ A. Prove the commutative laws.

5.3.2: Associative Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study Theorem 1 on pages SF-2 and SF-3 on the associative laws: (A $\cap$ B) $\cap$ C = A $\cap$ (B $\cap$ C) = A $\cap$ B $\cap$ C. Note that we can write the rightmost expression, which has no parenthesis, because $\cap$ is associative. Replacing $\cap$ by the intersection operations, gives the associative law for intersection. Prove the associative laws.

5.3.3: Distributive Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study Theorem 1 on pages SF-2 and SF-3 on the distributive laws: A $\cap$ (B $\cup$ C) = (A $\cap$ B) $\cup$ (A $\cap$ C); A $\cup$ (B $\cap$ C) = (A $\cup$ B) $\cap$ (A $\cup$ C). The former shows union distributes over intersection; and the latter shows intersection distributes over union. Prove the distributive laws.

5.3.4: Identity Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study the identities (equality of two set expressions) on pages SF-3 and SF-4 (the top of SF-3 and examples 2, 3, and 4). It follows from the definition of the empty set that A $\cup$ Ø = A, A $\cap$ Ø = Ø. Prove these identities.

5.3.5: Complement Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study the identities involving complement on pages SF-3 and SF-4. For universal set E, E' = Ø= A ∩ A'; A - A = Ø. Study example 1 on SF-4; 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.

5.3.6: Double Complement Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study Theorem 1 on pages SF-2 and SF-3. 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.

5.3.7: Idempotent Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study the idempotent identities of Theorem 1 on pages SF-2 and SF-3. An idempotent is an object A such that (A operation A) = A. The idempotent laws for union and intersection are: A $\cup$ A = A, A $\cap$ A = A. Prove several of the idempotent identities.

5.3.8: Universal Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study the identities involving the universal set in Theorem 1 and in examples 1 and 2 on pages SF-2 to SF-4. Prove some of the identities involving the universal set.

5.3.9: DeMorgan's Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study Theorem 1 on pages SF-2 and SF-3 on DeMorgan's laws: (A $\cup$ B) ' = A' $\cap$ B'; (A $\cap$ B)' = A' $\cup$ 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.

5.3.10: Absorption Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

Study Theorem 1 on pages SF-2 and SF-3 on absorption laws. These are called absorption identities because one of the sets is absorbed by the other(s). Prove the absorption laws.

5.3.11: Set Difference Laws University of California, San Diego: Edward Bender and S. Williamson's "Sets, Equivalence and Order: Sets and Functions"

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

6.1: Definitions and Basic Counting Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Introduction to Probability"

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.

6.1.1: What Is a Sample Space? Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Introduction to Probability"

Read Section 1.3 on pages 3 - 5. The previous reading introduced a four-step process for building a probabilistic model to analyze and solve problems using probability. This reading discusses the first step.

6.1.2: What Is an Event? Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Introduction to Probability"

Read Section 1.4 on pages 5 - 6. This reading discusses the second step of the four-step process for building a probabilistic model for solving probability problems.

6.1.3: Equally Likely Probability Formula Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Introduction to Probability"

Read Section 1.5 and Section 1.6 on pages 6 - 9. This reading discusses the third and fourth steps of the four-step 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.

6.1.4: Counting Elements of Lists and Sublists Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Counting I"

Read through Section 1.4. This work presents some strategies and rules that aid us in counting members of sets arising in the analysis of probability problems.

Section 1.3 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 one-dimensional 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 Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Counting I"

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.

6.2.1: Possibility Trees and the Multiplication Rule Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Introduction to Probability"

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.

Multiplication often 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.

6.2.2: Permutation Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Introduction to Probability"

Read Section 1.3 for the definition of a permutation, how to count permutations, and a reminder of Stirling's formula, which approximates n!

6.2.3: Counting Elements of Sets: Addition, Product, and Division Rules Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Counting I"

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."

Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Counting II"

Read 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, non-disjoint sets.

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 $\cap$ A).

6.2.4: Combinations Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Counting III"

Read Section 1 on pages 1 - 3. Section 1.1 and Section 1.2 discuss counting sequences; Section 1.3 discusses counting combinations.

6.2.5: The Algebra of Combinations Combinations

Pascal's triangle is a simple, manual way to calculate binomial coefficients.

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.

Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Counting III"

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.

6.3: Probability Process Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Introduction to Probability"

Read Section 2, which presents a four-step process for solving probability problems. This process incorporates basic probability axioms, albeit indirectly, as part of the process steps.

6.3.1: Probability Axioms University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions, and Graphs: Counting and Listing"

Read Section 4 on pages CL-28 through CL-30.

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ε EP(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.

From the above the following can be proved: Let E be an event. E' = S -E. P(E È E') = P(E) + P(E'), P(S= E È E') = 1; thus, 1 = P(E) + P(E') and P(E') = 1 - P(E).

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.2: The Probability of a General Union of Two Events Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Conditional Probability"

Read Section 4, "Conditional Probability Pitfalls," in particular, "Conditional Probability Theorem 2" and "Theorem 3" on page 12. This will serve as a lead-in to conditional probability, which is covered in the next section.

6.4: Conditional Probability and Independent Events Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Introduction to Probability"

Focus on the modeling advice and steps 1 - 4 on pages 1 - 9.

Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Conditional Probability"

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.

6.4.1: Computing a Conditional Probability Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Conditional Probability"

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, "On-Time Airlines" on page 15.

Understanding the examples is critical to really understanding conditional probability.

6.4.2: Bayes's Theorem University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions, and Graphs: Decision Trees and Recursion"

Read Section 3 on pages DT-28 through DT-35.

Bayes' theorem is a famous theorem for computing conditional probabilities. Assume Ei are mutually exclusive events for i = 1,..., n and Ui Ei = D, for arbitrary event D, P(Ei | D) = P(D | Ei ) P(Ei) / [P(D|E1)P( E1) + ....+ P(D|En) P(En)]. Statements of Bayes' theorem are given on pages DT-28 and DT-32. Like the binomial theorem, Bayes' theorem is very useful in calculating probabilities for many applications, for example, in diagnosis and in decision theory.

6.4.3: Computing the Probability of Independent Events Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Independence"

Read this lecture for practice with the probability of independent events.

7.1: Recursively Defined Sequences University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions and Graphs: Decision Trees and Recursion"

Read Section 4, "Recursion Equations," up to example 27 on pages DT-42 - DT-46.

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(n-1) is used to prove A(n). If A(n) is defined using A(n - 1), the sequence is recursively defined. Thus, induction and recursion both exploit a relationship between A(n) and A(n-1).

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.

Given a recursive equation, also called a recursive relation, Theorem 7 on page DT-43 of the reading in Subunit 7.1 tells us how to verify a solution for it.

Let f(n) be an explicit formula for the nth term, An, of a sequence and assume that f(n) = A bn + K = A bn + K + Kb - Kb = A bn + Kb + K - Kb = b (A bn-1 + K) + K ( 1 - b) = b f(n - 1) + K(1 - b). Thus, f(n) = b f(n - 1) + C, a recursive equation, i.e. relation.

For the Fibonacci numbers, see theorem 9 and example 29 on pages DT-48 - DT-49. Example 29 starts with the sequence, F0 = F1 = 1, Fk = Fk -1 + Fk -2, and develops a formula for Fn which does not utilize an earlier F in the sequence.

For the Towers of Hanoi problem, see example 11 on pages DT-18 - DT-19.

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

Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Recurrences"

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.

7.2: Solving Recurrence Relations University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions and Graphs: Decision Trees and Recursion"

Read from example 27 to the end of the chapter on pages DT-46 - DT-50

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

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).

Regarding Theorem 8 on page DT-48, if an = ban - 1 +c , then iterating, an = b( ban - 2+c) + c = b(b (b an - 3+ c ) + c ) + c= ....= a0 bn + c bn-1 + c bn-2 + .... + c. This is an example of using the method of iteration for finding a formula for a recurrence relation for an arithmetic sequence.

7.2.1: Finding a Formula for an Iterative Relation for a Geometric Sequence University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions and Graphs: Decision Trees and Recursion"

A simple example of going from an iterative relation to a formula is as follows: given the iterative relation, an = arn , arn, = r a r n-1 = r a n - 1, . Continuing in this manner, we get the formula, an = rn a0.

For another example, read over Exercise 4.7 on page DT-51. It discusses going from an iterative sequence to a recursive solution/equation, and vice versa, from the recursive equation to an iterative sequence.

Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Sums and Approximations"

Note that you have already read this lecture in Subunit 4.2. Focus on re-reading 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.

7.2.2: Using Mathematical Induction University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions and Graphs: Decision Trees and Recursion"

Read Section 4 on pages DT-42 to DT-44 up to "Recursion Equations." Note that mathematical induction and recursion are closely related concepts.

7.3.1: McCarthy's 91 Function Wikipedia: "McCarthy 91 Function"

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.

7.3.2: The Ackermann Function Wikipedia: "Ackermann Function"

Read the Wikipedia article for a description of the Ackermann function, an example of a recursive function that grows very rapidly.

8.1: Introduction to Graph Theory Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Graph Theory"

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.

8.2.1: Total Degrees of a Graph University of California, San Diego: Edward Bender and S. Williamson's "Lists, Decisions, and Graphs: Basic Concepts in Graph Theory"

Read Definition 3 on pages GT-4 to GT-5.

8.2.2: The Handshake Theorem Wikipedia: "Handshaking Lemma"

Read the article for a description of the handshaking lemma and the degree sum formula.

8.3: Isomorphism of Graphs Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Graph Theory"

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.

8.4: Trees Massachusetts Institute of Technology: Srini Devadas and Eric Lehman's "Graph Theory"

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.

Types of Trees

Read this article for a discussion of types of trees.

9.1: Formal Languages Formal Languages

Read this discussion of grammar and formal languages.

9.1.1: Polish Notation Polish Notation
Read this discussion of Polish notation for describing expressions.
9.1.2: Languages Defined by Regular Expressions Languages Defined by Regular Expressions

Read this discussion of languages defined by regular expressions.

9.1.3: Order of Precedence Rules Order of Precedence Rules

Read this discussion of operator precedence.

9.1.4: Deciding Whether Regular Expressions Define the Same Language Deciding Whether Regular Expressions Define the Same Language

Download the linked file for a discussion of operator precedence.

9.2: Finite State Automata Finite State Automata

Read this discussion on finite state automata.

9.2.1: Automaton and Accepted Language Automaton and Accepted Language

Read this discussion of regular sets and their acceptance by finite state automata.

9.2.2: Designing a Finite State Automaton Designing a Finite State Automaton

Read this discussion of hints on designing a finite state automaton to recognize a given regular set.

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 {on 1n 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.3: Simplifying Finite State Automata Simplifying Finite State Automata

Read this discussion of ways to simplify finite state automata.

Unit 9 Assessment Unit 9 Assignment