Mood

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

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 math.stackexchange.com.

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

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?!)

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.

Recursion

Collected stuff...

Recurrence Relations

Collected stuff...

Relations

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