Transcript mar09x

CMSC250 SECTIONS 0303 & 0304
MIDTERM REVIEW
Sri Kankanahalli
Discussion 10: 9 March 2016
Office Hrs: Mon. and Wed. 4-6PM
AVW 1112
Topics for Today
• Midterm 1 is March 21st ! ! !
• Review:
• Propositional logic
• Binary arithmetic
(1.1, 1.2, 1.4)
(Feb 3. slides 18-21)
• Two’s complement
• Proof techniques
• Set theory
• Functions
(1.7, a bit of 1.8)
(2.1, 2.2)
(2.3)
• Floor and ceiling functions
• Number theory
(4.1)
Propositional Logic
• Know:
• Logical connectives (including implication and biimplication)
• Quantifiers (∀, ∃)
• Translating from English to propositional logic, in
both directions
• A(X): X is a cow.
• B(X): X is blue.
• “All cows are blue.”
• ∀ x [A(x) → B(x)]
• ∃ x ¬A(x) ∧ B(x)
• “There exists a thing that is not a cow and is blue.”
Propositional Logic
• Don’t need to know (for this test):
• System specifications
• Circuits
Propositional Logic
• Slides:
• Feb. 1, everything
• Feb. 8, material on quantifiers
• Feb. 10, everything
• Practice problems:
• Translating from English to propositional logic
• Chapter 1.1, #10-12
• Working with quantifiers
• Chapter 1.4, #10, 32, 33
Binary Arithmetic
• Know:
• How to convert numbers from base 10 to
binary
• Two’s complement arithmetic
• Don’t need to know
• How to convert to other bases (octal,
hexadecimal, etc.)
• Though this is still a good skill to have in life!
Binary Arithmetic
• Slides:
• Feb. 3, material on binary arithmetic
• Practice problems:
• Convert 59 to an 8-bit two’s complement
binary number.
• Convert -63 to an 8-bit two’s complement
binary number.
• Express (21 – 95) as an 8-bit two’s
complement binary number.
Proof Techniques
• Know:
• All our basic methods of proof
• Direct proof
• Proof by contraposition
• Proof by contradiction
• General proof techniques
• Constructing a counterexample
• Proof by cases
Proof Techniques
• Slides:
• Feb. 17, everything
• Practice problems:
• Basic proof methods
• Chapter 1.7, #1-5, 6, 13
• Proof by counterexample and/or cases
• Chapter 1.8, #3, 6
Set Theory
• Know:
• Set operations (union, intersection, difference)
• Definition of subset and proper subset
• Proving properties of sets
• Proof by “element chasing”
• Proof by derivation
• Don’t need to know (for this test):
• Set identities (you’ll get a sheet, like the one
you had on the HW)
Set Theory
• Slides:
• Feb. 22, everything
• Practice problems:
• “Element chasing” proofs
• Chapter 2.2, #16, 19
• Derivational proofs
• Chapter 2.2, #17, 18
• Prove (A – B) ∩ (B – A) = ∅, both ways.
Functions
• Know:
• Finding the domain and codomain of a function
• Injectivity, surjectivity, bijectivity – and how to
prove them
• How to take the inverse of a function, and
verify it
• Floor and ceiling functions
• Don’t need to know (for this test):
• Partial functions
• Binary relations
Functions
• Slides:
• Feb. 24, everything
• Feb. 29, material on floor/ceiling functions
• Practice problems:
• Finding domain and codomain
• Chapter 2.3, #7
• Determining injectivity/surjectivity/bijectivity
• Chapter 2.3, #12-15, 22, 23
• Taking inverses of functions
• Find the inverse of f(x) = 3x + 4 + 5/x
• Floor and ceiling functions
• Chapter 2.3, #8, 9
Number Theory
• Know:
• Proving things about even/odd numbers
• Divisibility
• Modular arithmetic
• Proving statements like:
• “If n is odd, n2 ≡ 1 (mod 8).”
• “If n is odd and m ≡ 3 (mod 4), then (n2 + m) is
divisible by 4.” (More complicated than midterm.)
• Proving small roots are irrational
• Using modular arithmetic
• Using the Unique Factorization Theorem (slides later!)
Number Theory
• Don’t need to know (for this test):
• The division algorithm
• Modular exponentiation
• Proofs about primes
Number Theory
• Slides:
• Feb. 29, number theory and divisibility
• Mar. 7, everything
• Practice problems:
• Proving things about even/odd numbers
• Chapter 1.7, #1-5, 6, 13
• Divisibility
• Chapter 4.1, #5-8
• Modular arithmetic
• Chapter 4.1, #38-40
• Proving irrationality
• Prove √3 is irrational, once with modular arithmetic,
and once with the Unique Factorization Theorem.
Unique Factorization Theorem
• Also called the “Fundamental Theorem of
Arithmetic”
• Theorem: “Every integer can be expressed
as a product of unique prime numbers.”
• 24
• 160
• x
=3*2*2*2
= 3 * 23
=5*4*4*2
= 5 * 42 * 2
= p1a1 * p2a2 * … * pnan
Unique Factorization Theorem
• Proof: √2 is irrational.
• A proof by contradiction (like usual): Assume
√2 is rational. Then √2 = a / b, for a and b with
no common factors.
• So 2 = a2 / b2.
• So a2 = 2b2.
• We’ve done this many times before. Only the
next part differs.
Unique Factorization Theorem
• Proof: √2 is irrational.
• So a2 = 2b2.
• By the UFT, we can write a and b as a unique
product of prime factors.
• a = p1x1 * p2x2 * … * pnxn
• b = q1y1 * q2y2 * … * qnyn
• So, we can write a2 and b2 as:
• a2 = p12x1 * p22x2 * … * pn2xn
• b2 = q12y1 * q22y2 * … * qn2yn
Unique Factorization Theorem
• Proof: √2 is irrational.
• a2 = 2b2.
• So, we can write a2 and b2 as:
• a2 = p12x1 * p22x2 * … * pn2xn
• b2 = q12y1 * q22y2 * … * qn2yn
• We see a2 and b2 have all even powers, for each
prime in their factorizations.
• So, a2 and b2 would both have an even number of
2s in their factorizations.
• So, 2b2 would have an odd number of 2s.
• Since 2b2 has an odd number of 2s in its
factorization, and a2 has an even number of 2s, by
the UFT they can’t be equal! Contradiction.
Unique Factorization Theorem
• Proof: √2 is irrational.
• a2 = 2b2.
• Since 2b2 has an odd number of 2s in its
factorization, and a2 has an even number of 2s,
by the UFT they can’t be equal! Contradiction.
• Because assuming that √2 is rational leads to a
contradiction, √2 must be irrational. QED