Let's set the mood for this class and these notes with a comic from xkcd.

Set Theory

Here is an alternative set of notes on introductory set theory to give you a second perspective and some extra examples.

Propositional Logic

Quantifiers and Proof

Here is a blog entry on the removal and [re]introduction of quantifiers during a proof — for those so minded to explore further.

Translating To/From English

One of the foremost authors in this field is Gary Hardegree. He has recently updated his book Symbolic Logic: A First Course and, in doing so, he's placed his previous edition online. In particular chapter 2 goes over the basic operations of propositional logic and chapter 4 talks heavily on translating to/from English (natural language). He also gets pretty deep on necessity and sufficiency in chapter 4, too.

In a higher-level text, he talks more about necessity and sufficiency, but I'll let you search his site for that since it is truly heady stuff — not for the weak at heart!

Number Theory — Modulo

Here is a nice discussion of modulo arithmetic from Dr. Math. Make sure you read the links to other discussions. The one on negatives is fairly deep, but informative and entertaining. In fact, there are entire areas of Dr. Math's site focused on Discrete Mathematics, Set Theory, and Number Theory topics. (See also the definitions, algorithms, and exponents sections for nifty bits!)

Here also is a representation of the clock-circle idea for modulo from Khan Academy. (Note that it is in their section on cryptography — just as our discussions lead us up to RSA encryption.)

For those having trouble with the quotient-remainder theorem, here is a pleasant depiction of it in terms of standard long division from grade school.

For those troubled by the Euclidean algorithm for gcd, here is the book's gcd(245,90) problem redone with slightly clearer notational conventions. It has both phase I and phase II so you see the gcd and find s & t.

If you are having trouble with solving linear congruences, here are a couple of problems worked out to follow along with.

Proof Techniques

To lighten the mood, here's a little existence proof humor. (Don't forget to hover over the image to see the Alt-Text part of the joke.)

Direct Proof

Here is a nice derivation of the sum of squares formula via direct proof.

Strong vs. Weak

First is a beautiful discussion of strong vs. weak induction on

Then a discussion of why theorems are known as strong or weak that makes one feel the induction names were inappropriate!


If you are having trouble with Mathematical Induction, here is a solution to one of the problems in the book that might help you follow along.

Algorithms and Analysis

Here are some notes about relative rates classification for functions using both algebra and calculus.

And here is an analysis of linear search (aka sequential search) with the "not found" case included. Just ignore the first rendition of the algorithm as C++ code and dive right in at the algorithm itself.

Counting Techniques

A probability problem that involves lots of counting and has two equally clever solutions. (Hint: Can you find the typo in the second technique?!)

Here is problem 13 from section 5.1.8 which includes lots of discussion of counting techniques as well.

Binomial Proofs

Here are some notes to clarify and close-out our discussion from class Tuesday regarding problem 13 from subsection 5.2.3.

Combinatorial Proofs

Here are some notes to clarify and close-out our discussion from class last Tuesday regarding problem 9a from subsection 5.2.3.


Collected stuff...

Recurrence Relations

Collected stuff...


Some notes [possibly inappropriately] posted by a professor at Winona State University describing Warshall's algorithm. The algorithm and analysis are about half-way down...

Generating Functions

Collected stuff...