DOC PREVIEW
Berkeley COMPSCI 70 - Homework

This preview shows page 1 out of 2 pages.

Save
View full document
View full document
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience
Premium Document
Do you want full access? Go Premium and unlock all 2 pages.
Access to all documents
Download any document
Ad free experience

Unformatted text preview:

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

Berkeley COMPSCI 70 - Homework

Documents in this Course
Notes 1

Notes 1

12 pages

Note 2

Note 2

6 pages

Notes

Notes

6 pages

Notes

Notes

7 pages

Note 10

Note 10

8 pages

n20

n20

10 pages

n19

n19

10 pages

n18

n18

10 pages

n17

n17

6 pages

n16

n16

9 pages

n15

n15

10 pages

n14

n14

9 pages

n13

n13

6 pages

n12

n12

7 pages

n11

n11

6 pages

n10

n10

8 pages

n9

n9

5 pages

n8

n8

7 pages

n7

n7

8 pages

n6

n6

5 pages

n5

n5

8 pages

n4

n4

7 pages

n3

n3

10 pages

n2

n2

7 pages

n1

n1

5 pages

Load more
Download Homework
Our administrator received your request to download this document. We will send you the file to your email shortly.
Loading Unlocking...
Login

Join to view Homework and access 3M+ class-specific study document.

or
We will never post anything without your permission.
Don't have an account?
Sign Up

Join to view Homework 2 2 and access 3M+ class-specific study document.

or

By creating an account you agree to our Privacy Policy and Terms Of Use

Already a member?