Description

Sundry
Before you start writing your final homework submission, state briefly how you worked on it. Who else did you work with? List names and email addresses. (In case of homework party, you can just describe the group.)
1 Calculus Review
(a) Compute a closed-form expression for the value of following summation:
∞ 9

k∑=1 2k
(b) Use summation notion to write an expression equivalent to the following statement:
The sum of the first n consecutive odd integers, starting from 1
(c) Compute the following integral:
t
dt
(d) Find the maximum value of the following function and determine where it occurs:
f(x) = −x·lnx
2 Propositional Practice
In parts (a)-(c), convert the English sentences into propositional logic. In parts (d)-(f), convert the propositions into English. In part (f), let P(a) represent the proposition that a is prime.
(a) There is one and only one real solution to the equation x2 = 0.
(b) Between any two distinct rational numbers, there is another rational number.
(c) If the square of an integer is greater than 4, that integer is greater than 2 or it is less than -2. (d) (∀x ∈ R) (x ∈ C)
(e) (∀x,y ∈ Z)(x2 −y2 6= 10)
(f) (∀x ∈ N) [ (x > 1) =⇒ (∃a,b ∈ N) ((a+b = 2x)∧P(a)∧P(b)) ]
3 Tautologies and Contradictions
Classify each statement as being one of the following, where P and Q are arbitrary propositions:
• True for all combinations of P and Q (Tautology)
• False for all combinations of P and Q (Contradiction)
• Neither
Justify your answers with a truth table.
(a) P =⇒ (Q∧P)∨(¬Q∧P)
(b) (P∨Q)∨(P∨¬Q)
(c) P∧(P =⇒ ¬Q)∧(Q)
(d) (¬P =⇒ Q) =⇒ (¬Q =⇒ P)
(e) (¬P =⇒ ¬Q)∧(P =⇒ ¬Q)∧(Q)
(f) (¬(P∧Q))∧(P∨Q)
4 Prove or Disprove
For each of the following, either prove the statement, or disprove by finding a counterexample.
(a) (∀n ∈ N) if n is odd then n2 +4n is odd.
(b) (∀a,b ∈ R) if a+b ≤ 15 then a ≤ 11 or b ≤ 4.
(c) (∀r ∈ R) if r2 is irrational, then r is irrational.
(d) (∀n ∈ Z+) 5n3 > n!. (Note: Z+ is the set of positive integers)
5 Twin Primes
(a) Let p > 3 be a prime. Prove that p is of the form 3k+1 or 3k−1 for some integer k.
(b) Twin primes are pairs of prime numbers p and q that have a difference of 2. Use part (a) to prove that 5 is the only prime number that takes part in two different twin prime pairs.
6 Social Network
Consider the same setup as Q2 on the vitamin, where there are n people at a party, and every two people are either friends or strangers. Prove or provide a counterexample for the following statements.
(a) For all cases with n = 5 people, there exists a group of 3 people that are either all friends or all strangers.
(b) For all cases with n = 6 people, there exists a group of 3 people that are either all friends or all strangers.
7 Preserving Set Operations
For a function f, define the image of a set X to be the set f(X) = {y | y = f(x) for some x ∈ X}. Define the inverse image or preimage of a set Y to be the set f−1(Y) = {x | f(x) ∈ Y}. Prove the following statements, in which A and B are sets. By doing so, you will show that inverse images preserve set operations, but images typically do not.
Hint: For sets X and Y, X =Y if and only if X ⊆Y and Y ⊆ X. To prove that X ⊆Y, it is sufficient to show that (∀x) ((x ∈ X) =⇒ (x ∈Y)).
(a) f−1(A∪B) = f−1(A)∪ f−1(B). (b) f−1(A∩B) = f−1(A)∩ f−1(B).
(c) f−1(AB) = f−1(A) f−1(B).
(d) f(A∪B) = f(A)∪ f(B).
(e) f(A∩B) ⊆ f(A)∩ f(B), and give an example where equality does not hold.
(f) f(AB) ⊇ f(A) f(B), and give an example where equality does not hold.