CS 70 Discrete Mathematics for CSFall 2003 Wagner HW 1Due Thursday September 4Formatting your solution: Please use the following format for the top of the solution you turn in, withone line per item below (in the order shown below):<your username on cory.eecs><your full name>CS70, Fall 2003Homework #1Section <your section number>Partners: <your list of partners>(Remember to write your section number, not the name of your TA or the time of your section.)1. (5 pts.) Any questions?What’s the one thing you’d most like to see explained better in lecture or discussion sections? Aone-line answer would be appreciated.(Sometimes we botch the description of some concept, leaving people confused. Sometimes we omitthings people would like to hear about. Sometimes the book is very confusing on some point. Here’syour chance to tell us what those things were. All feedback is welcome.)2. (15 pts.) Getting startedCompleting parts (a)-(c) of this question is mandatory for everyone.(a) Get an EECS Instructional account, and register with our grading system. See the web page forinstructions on how to do this.(Why are we having you do this? Our grading software requires you to have an account and toregister before we can assign you grades.)(b) Make a new directory for this homework. cd to that directory and create a file README con-taining the one line “I registered!”. Now run the command submit hw1 to submit the file youjust created.(Why are we having you do this? This way we can verify that all of you have registered properly.)(c) Read the course web page. Write on your homework “I understand and will comply with theacademic integrity policy.”(d) What is David Wagner’s favorite number? The answer is found on the course newsgroup,ucb.class.cs70. Look for the post from David Wagner titled “The answer to question2(d),” and write down the answer you find there. Instructions on how to access the newsgroupmay be found on the course web page.(Why are we having you do this? The class newsgroup is your best source for recent announce-ments, clarifications on homeworks, and related matters, and we want you to be familiar withhow to read the newsgroup.)CS 70, Fall 2003, HW 1 13. (20 pts.) Inference rulesFor each of the following, define proposition symbols for each simple proposition in the argument(for example, P = “I will ace this homework”). Then write out the logical form of the argument. Ifthe argument form corresponds to a known inference rule, say which it is. If not, show that the proofis correct using truth tables.(a) I will ace this homework and I will have fun doing it. Therefore, I will ace this homework.(b) It is hotter than 100 degrees today or the pollution is dangerous. It is less than 100 degrees today.Therefore, the pollution is dangerous.(c) Tina will join a startup next year. Therefore, Tina will join a startup next year or she will beunemployed.(d) If I work all night on this homework, I will answer all the exercises. If I answer all the exercises,I will understand the material. Therefore, if I work all night on this homework, I will understandthe material.4. (20 pts.) Quantifier crazyRecall that N = {0, 1,...} denotes the set of natural numbers, and Z = {.. ., −1,0, 1,. ..} denotes theset of integers.(a) Define P(n) byP(n) = ∀m ∈ N. m < n =⇒ ¬(∃k ∈ N. n = mk ∧ k < n).Concisely, for which numbers n ∈ N is P(n) true?(b) Re-write the following in a way that removes all negations (“¬, 6=”) but remains equivalent.∀i. ¬∀ j. ¬∃k. (¬∃`. f(i, j) 6= g(k, `)).(c) Prove or disprove: ∀m ∈ Z. ∃n ∈ Z. m ≥ n.(d) Prove or disprove: ∃m ∈ Z. ∀n ∈ Z. m ≥ n.5. (20 pts.) Knights and KnavesJoan is either a knight or a knave. Knights always tell the truth, and only the truth; knaves alwaystell falsehoods, and only falsehoods. Someone asks Joan, “Are you a knight?” She replies, “If I am aknight then I’ll eat my hat.”(a) Must Joan eat her hat?(b) Let’s set this up as problem in propositional logic. Introduce the following propositions:P = “Joan is a knight”Q = “Joan will eat her hat”.Translate what we’re given into propositional logic, i.e., re-write the premises in terms of thesepropositions.(c) Using proof by enumeration, prove that your answer from part (1) follows from the premisesyou wrote in part (2). (No inference rules allowed.)6. (20 pts.) Is it true?For each claim below, prove or disprove the claim.(a) Every positive integer can be expressed as the sum of two perfect squares. (A perfect square isthe square of an integer. 0 may be used in the sum.)(b) For all rational numbers a and b, abis also rational.CS 70, Fall 2003, HW 1
View Full Document