Course Goals:
(1) An introduction to mathematical logic and proof techniques
and mathematical relations.
(2) An introduction to topics in discrete
mathematics, including counting problems and graph theory.
This is preparation for 4000 level math courses.
Course outline:
Logic: chapter 1
Proof: chapters 1,2,3,4
Counting: chapters 5,6,7
Relations: chapter 8
Graph theory: chapter 9, 10
Class 1
At the beginning of the class, students were introduced to the
TA and grader for this course, Bir Kafle.
Bir Kafle's office hours:
MW: 8:30 - 9am
TTh: 11am -12pm
Office: 327
The class covered:
Went over handout (the material at the top of this page)
Introduction to the class and to discrete mathematcs
Started section 1.1., defined propositions, propositional variables,
logical operators. Next class we will go over several logical operators.
Class 2, Wednesday August 26, 2009
The class covered:
The definitions and truth tables
for the logical operators not, and, or, xor, implies, if and only if
We defined a set and operations union and intersection
and the empty set (see chapter 2 for more on sets, we'll come back to this)
Defined Venn diagrams (we'll come back to this in chapter 2)
We gave the truth tables of each of the logical operators
not, and, or, xor, implies and if and only if.
You should learn the symbols and the tables
Class 3, Friday August 28, 2009
The class covered:
Quiz on the logical operator "or"
Venn diagrams corresponding to the operators and, or, xor, implies, iff
Example of truth tables
examples of equivalent propositions
example of turning logical expressions into English sentences
Definition of converse and contrapositive and
started section 1.2
Definitions of tautology, contradiction, contingency
Definition of when two propositions are logically equivalent
Examples of logical equivalences
Question: how can you write the logical operators or, xor, implies, iff
in terms of only "not" and "and"?
Class 4, Monday August 31, 2009
The class covered:
Using truth tables to prove two propositions are equivalent.
We gave two examples.
Proof by contradiction to prove two propositions are equivalent, a more
verbal style of reasoning.
Gave examples of how to write or, xor, impies, iff, in terms of not and and
Mentioned disjunctive normal form
Handout
with homework and preparation for quiz on Friday
Class 5, Wednesday September 2
Went over the solutions to the sample quiz
Finished section 1.2 on examples of equivalences
Started 1.3: defined a predicate
Class 6, Wednesday September 2
Quiz. Went over solutions in class.
Solutions are: d,e,b,c,a,2,5,5.
section 1.3. More on predicates and quantifiers. Examples of both
Defined the universe (or universe of discourse), which is the domain of
the predicate as a function.
Defined the notation R, Q, Z, N for reals, rationals, integers,
natural numbers (voted not to include 1), which are common examples of
universes we might take; could also have examples like U ={1,2,3}
Discussed the logical equivalences known as "de Morgan's laws for
quantifiers" - see page 41
Discussion of predicates with more than one variable, and
multiple quantifiers. (section 4.1, page 51)
Examples of when you can and can't change the order of quantifiers
(this is section 4.1, page 51-53
Note: homework due September 9 is:
section 1.2 ex: 2,4,6,10,40
section 1.3 ex: 2,8,20,12,32
Note: homework due September 16 is:
section 1.4 ex: 6,8,10,20,26,28,30,40
There will be a quiz on Friday September 11, similar to the following:
Let U=set of all birds
P(x)= x has feathers
Q(x)= x can fly
Match up
(1)&forall x P(x)
(2)&forall x Q(x)-> P(x)
(3)¬ &exist x ¬ P(x)
(4)&exist x ¬ Q(x)
with
(a)There is no bird which does not have feathers
(b)All birds which can fly have feathers
(c)Some birds can not fly
(d)All birds have feathers
Which pair of (1)-(4) are equivalent?
Class 7, Wednesday September 9
Went over sample quiz above
More examples from 1.3 and 1.4 of predicates, quantifiers,
going from English to logic and logic to English, and examples with truth
tables and equivalences of different ways of saying things.
Class 8, Friday September 11
Quiz in class, and going over solutions
Example of nested quantifiers: example 6, section 1.4, page 58
Section 1.5, Rules of inference: covered rules in tables on pages 66 and 70
Class 9 and 10, Monday September 14, Wednesday September 15
Going over examples of proofs as in section 1.6 and 1.7
Including direct proof, proof by contradition, proof by contraposition
Class 12, Friday September 17
Test 1
Class 13-15,
Monday - Friday September 20 - 24
More examples of proofs from 1.6 and 1.7
includes exhaustive proofs;
case by case proofs; proofs where "without loss of generality"
(WLOG) is used; examples of constructive and non constructive existance
proofs
.
homework, due Wednesday Septmber 30:
1.7 ex 2,4, 6, 8, 10
Class 16
Monday September 28
Some hints for homework on proofs.
Tiling problems - tiling 8 by 8 boards with some squares removed with
dominoes. Pages 97-101 in book.
Class 17
Wednesday September 30
More examples of domino tilings and proofs
homework, due Wednesday October 7:
1.7 ex 14, 28, 32, 40, 42
Class 18
Monday October 5
Sets: section 2.1 and some of 2.2.
handout with quiz for Wednesday and Friday
and next homework: 2.1:
2, 8, 18, 20, 32; 2.2: 2, 4, 6, 8, 14
Class 19
Wednesday October 7
Quiz, and went through preparation for Friday's quiz - more complicated
sets.
Discussion of Russel's paradox and paradox of barber - see ex 38, page 121
Cartesian products of sets.
Class 20
Friday October 9
Went over prepration for todays quiz, which was postponed until Monday.
Discussion of empty set and difference between sets like the empty set and
the set containing the empty set, and the difference between x being a subset
of y and an element of y. Etc.
The homework that was due today will now be due on Friday
We discussed the quiz for Friday, on countable and uncountable sets.
Class 28
Friday October 30
Quiz on countable and uncountable sets
Proof of uncountability of the reals
Proof of uncountability of the power set of the natural numbers
Proof of countability of product of countable sets
notes on countability of rationals, in particular, note about
Stern's diatomic sequence, which leads to a recursive formula for listing all positive rationals with x0=1, and xn = f(x(n-1)) with
f(x)=1/(floor(x) + 1 -fractionalpart(x))
Next week we start on Chapter 3, section 3.4
Class 29
Monday November 2
Started section 3.4 on Integers and division
Definied quotient, remainder, div, mod, congruence modulo m
Homework due Wednesday November 11: 2.4: 36, 38
and 3.4 2,6,8,10
Quiz on Friday Nov 6: similar to: does 97 divide 304?
Find the quotient and remainder when 304 is divided by 97
Note on test: There is a test on
Friday Nov 13. Topics covered will be from sections 2.3, 2.4, including
how to prove the rationals are countable and the reals uncountable,
and sections 3.4 and 3.5
Handout , telling you the next
Homework: 3.4 ex 26, 28, 32(a), 34. 3.5 ex
2(a)-(c), 4(a)-(c), 10, 12, 20(a)-(c), 22(a)-(c)
And that there is a review for the test in Locket 235 Tuesday Nov 10
5-6pm
Test will be this Friday
Covered section 3.5 on primes and greatest common divisors
Proved there are infinitely many primes (see page 212).
We will not cover sections 3.1, 3.2, 3.3, 3.6, 3.7, 3.8.
Started chapter 4 on induction. Stated the first principle of induction,
and described the domino and ladder analogies for understanding induction.
See text book for these and another analogy.
Started to prove that the sum of i from i=1 to i=n is n(n+1)/2
Class 33
Wednesday November 9
Went over solutions to test guide
Class 34
Friday November 13
Test 3
Class 35
Monday November 16
Chapter 4, proof by induction
(section 4.1) Described proof by induction
Proved the formulas for sum of integers and sums of squares of
integers up to n.
Proved a formula for number of regions n lines can divide a circle into
Defined the Fibonacci sequence (see section 4.3)
Homework: 4.2 ex 4, 6, 10, 14, 20, 32.
Due Wednesday Dec 2.
Class 36
Wednesday November 18
Fibonacci sequence, (see 4.3, page 297)
Proofs by induction relating to Fibonacci sequence:
4.3 ex 14 (pg 308); proof that sum of first n fibonacci numbers is 1 less
than the n+2 Fibonacci number.
Discussion of Fibonacci numbers in nature - pine cones, spirals,
golden ratio. There are many web sites on this!
Fibonacci numbers and rabbit population problem
Fibonacci numbers and trains of length n with carriages of length 1 or 2
See e.g.,
Illuminations web site
for more on this and other Fibonacci problems.
Class 37
Friday November 20
More examples of proof by induction
Chapter 5: Counting.
Defined P(n,r) and C(n,r), and proved formulas for these, and gave some
examples.
See section 5.3 and 5.4.
Class 38
Friday November 23
Chapter 5: Counting.
Proved binomial theorem
Defined Pascal's triangle and proved Pascal's identity
Gave some examples of problems with binomials, e.g., number of lines
when you join together n points on a circle with lines from each point to
each other point.
There will be a quiz on Monday November 30 on finding P(n,r) or
C(n,r) for some small n and r.
Homework: 5.3 ex 2, 4, 8, 22, 24.
Due last day of class, December 4.