$24
ROB 501 - Mathematics for Robotics HW #2
Preliminaries:
Review logic symbols here: http://en.wikipedia.org/wiki/List_of_logic_symbols
Read about truth tables here:
http://sites.millersville.edu/bikenaga/math-proof/truth-tables/truth-tables.html
1. Negate the following statements. For each one, construct a truth table to prove that your negation is correct. Note that "or" in logic is always non-exclusive!
(a) (P^Q)
(b) (P_Q)
2. Negate the following statements. No truth table is required. You do not have to provide your steps. It is enough to just give an answer.
(a) For every integer n, 2n + 1 is odd.
(b) For some integer n, 2n + 1 is prime.
(c) Let A be an n n real matrix and 2 R . Statement: 9 v 2 Rn; v 6= 0; such that Av = v.
(d) Let f : R ! R be a function. Statement: 8 > 0; 9 > 0 such that jxj =) jf(x)j jxj
3. Prove that p7 is irrational. In your proof, you may use as true the following statement: “Let m be an integer. If 7 divides m2, then 7 also divides m.”
4. Let A be a square matrix. Prove: If det(A) = 0, then A is not invertible. Remark:
(a) As part of your solution, look up the definition of an inverse of a matrix and write it down carefully.
(b) You may use as known: det(AB) = det(A) det(B) for square matrices of the same size.
5. Prove that, for all integers n 1,
n
k(k+1)
= n+1 .
kP
1
n
=1
6. These use strong induction:
(a) Prove that, for all integers n 12, there exist non-negative integers k1 and k2 such that n = k14 + k25. Is the same statement true for n 8?
(b) Prove that, for all even integers n 6, there exist non-negative integers k1 and k2 such that n = k13 + k25.
1
7. More Lagrange Multipliers: Let M be an n n real symmetric matrix. Use the method of Lagrange multipliers to do the following
(a) For x 2 Rn, solve max x>M x, subject to the constraint, x>x = 1. Find both the maximum value and an x that solves the problem.
(b) For x 2 Rn, solve min x>M x, subject to the constraint, x>x = 1. Find both the minimum value and an x that solves the problem.
2
Hints
Hints: Prob. 2 For (c) and (d), you may find it easier to replace the symbols 8 and 9 by appropriate words in English BEFORE you negate the statement. Once you have negated the statement expressed in English, reinsert the symbolic expression as appropriate. With practice, you can skip this intermediate step.
In (d), there is an implied quantifier. Here is an equivalent statement that I will call (d’) Let f : R ! R
be a function. Statement: (d’) 8 > 0; 9 > 0 such that 8x 2 R satisfying jxj it is true that jf(x)j jxj
Another way to think about the statement: Let A := fx 2 R j jxj g.
(d”) 8 > 0; 9 > 0 such that x 2 A implies jf(x)j jxj
Hints: Prob. 3 Definition: An integer m divides an integer n if there exists an integer k such that n = mk.
Hints: Prob. 5 Write down carefully P (n), followed by the base case, the induction step, and what is to be shown. Then the problem becomes easy.
Hints: Prob. 6 (a) is worked in the handout, except for the part about n 8. For (b), you should really try to do it without any further help.
Hints: Prob. 7
• No additional hints given in Office Hours! This can be a hard problem. If you get it, great! If not, no big deal, study the solution and remember the answer. We will use the result later in the term. This could have been part of HW 1, but I wanted to keep the initial HW set as short as possible.
• x is a column vector and thus x>M x is a scalar.
• When you form your Lagrange function, write it as x>M x + (1 x>x).
• Eigenvalues of real symmetric matrices are real; the eigenvectors are real too. You can easily find proofs of this on the web.
• Because the eigenvalues are real and finite in number, there exists a largest eigenvalue, denoted max, and a smallest eigenvalue, denoted min.
• For a symmetric matrix M, @x@ (x>M x) = 2M x, where we are writing the gradient as a column vector, with i-th entry @x@i (x>M x). Though we are not doing so here, it is often more convenient to write it as a row vector, in which case @x@ (x>M x) = 2x>M (recall that M is symmetric).
3
