|
|
Math 22Discrete Mathematics
Math 22
MTWThF: 9:30am - 10:20am
Elements of discrete mathematics with applications to computer science.
Topics include methods of proof, mathematical induction, logic, sets,
relations, graphs, combinatorics, and Boolean Algebra.
Textbook for Winter Quarter 2006:
Discrete Mathematics (Sixth Edition) by Johnsonbaugh
Prerequisite: Math 49A PreCalculus or equivalent
If you passes Math 49A or higher at De Anza, you are automatically cleared for Math 22. If you did not pass Math 49A or higher at
De Anza, you will need to clear your pre-requisites or else the system will block you from registering. GO to the placement office the Student services Building with your transcript showing that you have passes pre-calculus or higher. If you have questions about whether you need to take a placement exam, they can also help you. If you do
not have a transcript acceptable to them, you need to get your prerequisites
approved by the Dean of Physical Sciences, Mathematics, and Engineering (PSME). Call the division office at 864-8774 or 864-8800 to get
information concerning the process and the documentation you need;
you will need to visit the office.I am sorry, but I can not approve your
pre-requisites myself - they must be processed through the Dean's office.
Math 22 Update
Week 10 Quiz 7 THURSDAY March 16
Week 11 Exam 3 TUESDAY March 21
Week 12 Final Exam WEDNESDAY March 29 9:15 am to 11:15 am
22 Assignments W06:
http://faculty.deanza.edu/bloomroberta/stories/storyReader$61
Math 22 Solutions:
http://faculty.deanza.edu/bloomroberta/stories/storyReader$56
Useful Resources
Many discrete math problems can be approached from the perspective of serious mathematical study at the college level, and as "brain-teasers" or mathematical
puzzles or activities at high school, middle school, and even
elementary school level.
Resources for the work for Math 22 are listed below, by topic
in blue titles.
Some links are to interactive websites, math "toys", puzzles, problems of the week, and lesson plans to teach the material in K-12. Look for the orange Discrete Math Fun items.
Historical and multicultural links are posted for some topics with
green titles.
Using Pascal's Triangle to expand (a + b)^n
http://www.davidscudder.com/resource/pascal/binomial.html
Discrete Math Fun
Pascal's Triangle and
"The 12 Days of Christmas"
http://www.aip.org/isns/reports/2002/058.html
http://dimacs.rutgers.edu/~judyann/LP/lessons/12.days.pascal.html
History of this arithmetical triangle often attributed to Pascal but with earlier roots in other cultures
http://mathforum.org/workshops/usi/pascal/pascal_intro.html
Laws of Logical Equivalence - in conjunction with
Section 1.1
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/LogicalEquivalenceLaws.doc
Section 1.3 Quantified Statements - Lecture Notes
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/QuantifiedStmtW06.doc
Sections 1.1 through 1.4:
Additional practice problems in logic, and answers to problems:
Distributed as pink handout in class
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/M22Practice1.doc
Section 1.5 Proof
Answers to problems for finding conclusions using
logical arguments
See problems on the first purple worksheet, which we did in class
and as HW and went over in class, early in section 1.5.
A second purple worksheet, distributed the day before the exam, has additional practice examples.
ClassWork Examples: Solutions to Purple Worksheet #1
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/LogicalArguExSol.doc
Exam Practice Problems: Solutions to Purple Worksheet #2
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/LogicalArguPractSol.doc
Axioms for Arithmetic with Real Numbers
and copies of the proofs done in class for the theorems stated in the text.
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/AxiomsForArithmetic.doc
Which type of proof is appropriate in what situations?
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/TypesofProofs.htm
Existence Proof Examples:
Constructive Proof of
Existence and Non-Constructive Proof of
Existence
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/ExistenceProofExamples.htm
Discrete Math Fun
One of the proofs at the link above was about prime numbers.
Play with Eratosthenes' sieve to find prime numbers (interactive)
http://www.faust.fr.bw.schule.de/mhb/eratosiv.htm
Another Non-Constructive Proof of Existence:
The equation x^3 - e^x =0 has a solution
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/x3ex.pdf
Biconditional Theorems: "If and only if"
Here is a familiar theorem in biconditional form
Suppose you are given a triangle with sides having lengths a, b, c,
where c is
the length of the longest side.
a^2 + b^2 = c^2 if and only if the triangle is a right triangle
The converse of the Pythagorean Theorem can be proved, so that the Pythagorean Thereom can be stated in biconditional form.
Link below to a direct proof
of the converse of the Pythagorean Theorem
and other pertinent resources relating to the proof of Pythagorean Theorem and
the Law of Cosines.
http://nebula.deanza.fhda.edu/math/FT/bloom/ConversePythagorean.htm
Indirect Proof - Notes
http://facultyfiles.deanza.edu/gems/bloomroberta/IndirectProofNotes.doc
Examples of Indirect Proof :
"Odd integers are not divisible by 10"
Proof by contraposition and by contradiction
http://nebula.deanza.fhda.edu/math/FT/bloom/Oddintegers10.htm
Proof by Contradiction that the Square Root of 2 is Irrational
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/SquareRootof2isIrrational.pdf
(Optional) In case you are curious,
but only if you have taken or are taking Math 1C:
Proof by contradiction that e is irrational
http://mathforum.org/isaac/problems/eproof.html
This proof relies on the series expansion of e that you learn about in Math 1C.
This is not required for Math 22;
I am making it available in case you are interested.
It is beyond the scope of this class for Math 22,
but if you have had Math 1C you can understand it.
SECTION 1.7 Proof by Mathematical Induction
Template for the format of doing a proof by induction for the sum of a sequence
.
This outline is the "training wheels" my math 49B classes use when they start to
learn proof by mathematical induction. You may find it helpful for getting started until you've had some practice.
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/ProofByInductionFormat.doc
SECTION 11.1 CIRCUITS AND GATES
And, Or, Not Circuits with Batteries, Bulbs and Switches
http://nebula.deanza.fhda.edu/math/FT/bloom/22circuits1.gif
Discrete Math Fun
Interactive On-Line Boolean Circuit Simplifier
at the University of Northern Colorado
http://hopper.unco.edu/KARNAUGH1.1/Function.html
You can use it to check your homework problems
This is a diagram of the circuit for a 7 segment display.
The Boolean statements were handed out in class.
http://www.physics.udel.edu/wwwusers/watson/phys345/class/17-decoder-full.html
7 Segment Display for Binary Calculator, as discussed in class
http://nebula.deanza.fhda.edu/math/FT/bloom/22binarydisplay.gif
On this handout the input is "p" rather than "x" as we did in class.
The "~" symbol means NOT, instead of using the bar above the input, as we did in class. I am unable to fix the graphic to use our current class notation.
NOT IN OUR SYLLABUS, but maybe some of you might be curious
KARNOUGH MAPS are used to simplify the expressions for electronic circuits.
This site has a good explanation of Karnough Maps
http://www.ee.surrey.ac.uk/Projects/Labview/minimisation/karnaugh.html
This technique can be used to simplify the complicated Boolean statements in
disjunctive normal form that we looked at for the 7 segment display.
Cardinality of Infinite Sets
How Big is Infinity?
http://www.jcu.edu/math/vignettes/infinity.htm
Countable Infinity
http://pirate.shu.edu/projects/reals/infinity/countble.html
Uncountable Infinity
http://pirate.shu.edu/projects/reals/infinity/uncntble.html
More on Cardinality: above and beyond in depth compared to the other links
http://www.earlham.edu/~peters/writing/infapp.htm
Chapter 2.1: SETS
Practice Problems for Inclusion/Exclusion Rule:
http://nebula.deanza.fhda.edu/math/FT/bloom/InclusionExclusionPractice.htm
Hint
for practice problems:
Some problems for the Inclusion/Exclusion rule give you size of the OR set and not the size
of the AND set
If you have all the other set sizes, then you will have 3 of
the 4 items in the equation for 2 sets, or 7 of the 8 items in the equation for
3 sets, and you can solve to find the missing variable in the equation.
Binary, Octal, Decimal, and Hexadecimal Numbers
The theory, and algorithms for conversion
Decimal:
http://www.danbbs.dk/~erikoest/decimal.htm#top
http://www.hal-pc.org/~clyndes/computer-arithmetic/decimal.html
Binary:
http://www.danbbs.dk/~erikoest/binary.htm#top
http://www.hal-pc.org/~clyndes/computer-arithmetic/binary.html
Octal:
http://www.danbbs.dk/~erikoest/octal.htm#top
http://www.hal-pc.org/~clyndes/computer-arithmetic/octal.html
Hexadecimal:
http://www.danbbs.dk/~erikoest/hex.htm
http://www.hal-pc.org/~clyndes/computer-arithmetic/hex.html
Pigeon Hole Principle
Practice problems for the pigeon hole principle
Easier than most of the problems in the textbook section 6.8.
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/PigeonHolePractice.doc
Recurrence Relations and Sequences
List of some of the interesting, famous, classic, or useful recurrence
relations we are examining in this class
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/RecurrenceRelationList.doc
Discrete Math Fun
Tower of Hanoi Sites
Game: http://www.mazeworks.com/hanoi/
Game: http://www.lhs.berkeley.edu/Java/Tower/tower.html
History: http://www.lhs.berkeley.edu/Java/Tower/towerhistory.html
Discrete Math Fun
Fibonacci Sequence in nature
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fibnat.html
Fibonacci Sequence and the Golden Ratio (Phi and phi)
http://www.mcs.surrey.ac.uk/Personal/R.Knott/Fibonacci/fib.html
The mathematics of the Fibonacci Sequence
http://mathworld.wolfram.com/FibonacciNumber.html
Visual representations of Fibonacci Numbers
http://mathforum.org/advanced/robertd/fibboard.html
Discrete Math Fun
Visual representations of Catalan Numbers
http://mathforum.org/advanced/robertd/catalan.html
Discrete Math Fun
Visual representations of Stirling Numbers
of the first kind: http://mathforum.org/advanced/robertd/stirling1.html
of the second kind: http://mathforum.org/advanced/robertd/stirling2.html
Graph Theory Chapter 8
Definitions in our textbook:
|
Start & End
Vertices |
Repeated
Edges? |
Repeated
Vertices? |
Contains
Every Edge? |
Contains
Every Vertex? |
| Path |
Different | ? | . | . | . |
| Simple Path |
Different | No | No | . | . |
| Cycle |
Same | No | . | . | . |
| Simple Cycle |
Same | No | No | . | . |
Euler
Cycle |
Same | No | . | Yes ONCE | Yes
(may repeat) |
Hamiltonian
Cycle |
Same | No | No | . | Yes ONCE |
For any empty box in the table, the property is permitted but not required.
I consider it to be ambiguous in our text whether a path may contain repeated
edges.
Graph theory is a relatively new field of mathematics. The terminology such as path
and cycle (and walk and circuit) is not standard for all texts. When looked up in other textbooks or various
on-line sources, the definition of path is not consistent. Also the definition
of simple may differ in other textbooks. When
reading other sources on graph theory, check the definitions carefully to see
how they are used by that author
Math 22 Chapter 8 Graph Theory Notes
Copy of table above and definitions and theorems handed out in class
http://nebula.deanza.fhda.edu/math/FT/bloom/Math22/M22GraphNotes.doc
Discrete Math Fun
Animation of n hypercube
http://www.keypress.com/sketchpad/javasketchpad/gallery/pages/hypercube.php
Web resources for graph theory for chapter 8 of Johnsonbaugh
http://cwx.prenhall.com/bookbind/pubbooks/johnsonbaugh4/chapter6/deluxe.html
Section 8.4 Djikstra's Shortest Path Algorithm
Optional section: We may skip this due to time constraints as the quarter is almost over
Djikstra's Algorithm explained and applets and other interactive websites:
http://renaud.waldura.com/doc/java/dijkstra/
http://www-b2.is.tokushima-u.ac.jp/~ikeda/suuri/dijkstra/Dijkstra.shtml
http://www.dgp.toronto.edu/people/JamesStewart/270/9798s/Laffra/DijkstraApplet.html
http://carbon.cudenver.edu/~hgreenbe/sessions/dijkstra/DijkstraApplet.html
http://www.ifors.ms.unimelb.edu.au/tutorial/dijkstra/
Infix, Prefix, Postfix, and polish and reverse polish notation:
http://www.cs.man.ac.uk/~pjj/cs2121/fix.html
This is covered in the text, but this is site gives you another resource if you want one.
THE REMAINDER OF THIS PAGE IS NOT YET UPDATED FOR
WINTER QUARTER 2006 AND MAY OR MAY NOT BE APPROPRIATE OR OF INTEREST THIS QUARTER
Combination Lock:
Combination lock as finite state automaton:
http://nebula.deanza.fhda.edu/math/FT/bloom/22ch7-2lock.gif
How a combination lock works: Inside a combination lock
http://home.howstuffworks.com/inside-lock.htm
Relations
The reflexive closure of a relation R is the smallest reflexive relation that contains the given relation R as a subset. To form the reflexive closure, start with the given relation R and add only those ordered pairs that are necessary to make the relation reflexive. This means that the reflexive closure will be the original relation, enlarged as necessary to contain all possible ordered pairs of the form
(x,x).
The symmetric closure of a relation R is the smallest symmetric relation that contains the given relation R as a subset. To form the symmetric closure, start with the given relation R and add only those ordered pairs that are necessary to
make the relation symmetric. This means that the symmetric closure will be the
original relation enlarged as necessary so that if (x,y) is in R, then (y,x) is in R.
The transitive closure of a relation R is the smallest transitive
relation that contains the given relation R. To form the transitive closure,
start with the given relation R and add only those ordered pairs that are
necessary to make the relation transitive. This means that the transitive
closure will be the original relation enlarged as necessary so that if
(x,y)and (y,z) are in R, then (x,z)
is in R.
Finding the transitive closure is more difficult than finding the reflexive and symmetric closures.
Interactive transitive closure calculator
At the website of Matthew E. Coppenbarger at the Rochester Institute of Techonology
http://cs.engr.uky.edu/~inna/cs650/Problem23/
Follow instructions to enter the relation as the adjacency matrix of its
directed graph.
The algorithm will find the transitive closure for the relation.
Although we studied transitive closures in the chapter on relations
before we studied graph theory,
this is a nice application of graph theory,
algorithms, and computer programming, all put together.
Another interactive transitive closure site: http://www.ifors.ms.unimelb.edu.au/tutorial/transitive/index.html
|
|
|
