ITEC 122 2007fall ibarland

home—info—lectures—hws—exams

hw04-redo
proofs revisited

See some sample problems.

Although you are welcome to typeset your work nicely (using Microsoft Word or LaTeX or whatever to get nice logic symbols), it's probably much easier to write formulas by hand.

Remember that to prove a ∀ requires showing that something holds for all possible value. Disproving a ∀ is easier; you simply show one counterexample. Conversely, to disprove a ∃ requires showing that something never holds, and proving an ∃ is easier; you simply show a witness making the statement true.

1. Rosen p.85 #10: Prove that Q is “closed under multiplication” (that is: the product of two rational numbers is rational).
   You'll of course need to use the definition of Q = { x | ∃p,q such that x=p/q, p ∈ Z, q ∈ Z-{0} }.
2. Rosen p.85 #30 (an equivalent variant): Show that a<b if and only if a is less than the average of a and b.
   Hint: your answer should be a series of inequalities, joined by "is equivalent to".
3. Prove that Q is “dense”: that is, between any two (different) rational numbers there exists another rational number.
   (Does this problem relate to the previous one?)
4. Is the function stringLength: Σ^* → N …
   1. one-to-one?
   2. onto?
   You may abbreviate stringLength as “L”. In each case, prove your answer (whether “yes” or “no”). (You'll of course need to use the exact definition of one-to-one and onto from the book.)
5. Rosen p.103 #18: uniqueness of floor.

If you see a few other problems in Rosen which catch your eye, and you'd like to do them for extra credit, you are welcome to (though you can ask me for how much; extra-credit is harder to earn point-per-point than regular credit).

If you write your own html, you might be interested in this page of useful html math (and other) entities

home—info—lectures—hws—exams

©2007, Ian Barland, Radford University Last modified 2007.Oct.13 (Sat)

Please mail any suggestions (incl. typos, broken links) to iba�rlandrad�ford.edu