Transcript finalreviewpart1

• Homework 7
– Average: 70
Median: 75
– http://www.cs.virginia.edu/~cmt5n/cs202/hw7/
• Homework 8
– Average: 74
Median: 79
– http://www.cs.virginia.edu/~cmt5n/cs202/hw8/
– #36 was commonly missed
• The solution key presents a rather tedious, straightforward
application of the counting techniques we discussed in class.
• There is a more clever way to solve this problem but it takes a
bit of creative insight beyond what we discussed in class. I
did not present this more clever solution in the key because I
want you to see how it can be solved without this insight.
• Emmanuel’s last OH is this Thursday, April 24th
Review for Final Exam (Part 1)
• Propositional Logic
• Know the rules and connectives
• Be able to translate statements into propositional logic
• Be able to produce logical equivalences
• Solve Logic Puzzles (Who’s Lying?, Knights/Knaves, etc.)
• Predicate Logic
• Know the rules, quantifies, and format for predicate logic
• Be able to translate statements into predicate logic
• Know how to form common statements (such as at least two, etc)
• Methods of Proof
• Know how to apply the different proof techniques
• When can you use a counter-example, when do you need UG?
• Be able to prove given statements by applying the proper method
• Know how to spot invalid use of a proof technique
• Sets
• Know the definition of commonly used sets: N, Z, Z+, R, Q, etc.
• Be able to work with set operations: , , , , , P(S), etc.
• Have facility with set specifiers: =, , , , , |S|, etc.
• Know set terminology: empty, disjoint, etc.
• Understand the bit string representation of a subset of a given set
• Review things that gave you trouble on TEST1
• Functions
• KNOW THE DEFINITION OF MAP AND FUNCTION!
• Be able to tell whether a function is 1-1 or onto and show it
• Understand function operations such as composition and inverse
• What is a 1-1 correspondence? How does it relate to counting?
• The Integers and Division
• Know the definitions: a | b, even, odd, rational, irrational, prime,
composite, mod, relatively prime, pairwise relatively prime
• Review the theorems in this section regarding divisibility, mod,
primes, fundamental theorem of arithmetic, division algorithm, etc.
• Be able to find the prime factorization, gcd, lcm, mod, etc.
• Prove results concerning divisibility, rational, irrational, prime,
composite, mod, etc.
• Proof Strategy
• The main goal is to be able to prove theorems. Strategies
presented include working backwards from the desired result, using
existing proofs, looking for counter-examples, making conjectures
• Sequences and Summations
• Review sequences, summations, summation notation, cardinality
• Know the definition of countability, uncountability, etc.
• How do sequences relate to countability?
• Be able to determine whether a set is countable or uncountable.
• Prove results concerning countability/uncountability.
• Understand the technique of diagonalization and how it is used to
prove that a set is uncountable.
• Other methods of proving a set is uncountable?
Ex: Show that the set of irrational numbers is uncountable.
We can not use the technique of diagonalization here because we
don’t have a rigorous representation for irrational numbers.
Proof: Assume, to the contrary, that the set of irrational numbers is
countable. Use I to represent the set of irrational numbers.
We know that R = Q  I. We also know that Q is countable.
Hence R is countable as the union of two countable sets [we proved it].
But we know that R is uncountable [we proved this as well].
This is a contradiction: a set can’t be both countable and uncountable,
so the set of irrational numbers must be uncountable, after all.
Take specific note here that diagonalization is not the only means by
which to prove a set is countable. Also note that just because we may
not be able to diagonalize a set doesn’t mean it isn’t uncountable.
• Mathematical Induction
• Know the principle of mathematical induction
• When can we use mathematical induction
• Be able to prove results using mathematical induction
• Recursive Definitions and Structural Induction
• KNOW HOW A RECURSIVE SET DEFINITION WORKS!
• Be able to determine the elements of a recursively defined set
• Understand the technique of structural induction and how to use it
to prove results about recursively defined sets and sequences.
• Review things that gave you trouble on TEST2
• Pay specific attention to understanding countability/uncountability
• Also the workings of recursive set definition gave a lot of trouble.