CS 70 SPRING 2008 — DISCUSSION #1LUQMAN HODGKINSON, AARON KLEINMAN, MIN XU1. Administrivia(1) Course Information• The first homework is due Thursday January 31st at 5:00PM. You are encouraged to workon the homework in groups of 3-4, but write up your submission on your own. Cite any externalsources you use.(2) Discussion Information• If you have a clash, it is ok to attend a section different to your enrolled/wait-listed one if youcan get the permission of the new section’s GSI. Just be sure to show up so that we can ‘assign’you somewhere based on the rolls taken in sections in the first few weeks.• Section notes like these will be posted on the course website.• Feel free to contact the GSI’s via e-mail, or the class staff and students through the newsgroup,ucb.class.cs70, if you have a question.2. Warm-up ExerciseExercise 1. Write down the truth table for ¬A ⇒ B. What else is this operation on A and B known as?Exercise 2. Use a truth table to show that the negation of P ⇒ Q is P ∧ ¬Q, in another words, ¬(P ⇒ Q)is logically equivalent to P ∧ ¬Q. Keeping in mind that DeMorgan’s rule says that ¬(P ∧ Q) ≡ ¬P ∨ ¬Q,what is the negation of P ⇔ Q?3. Quantifier PracticeExercise 3. Consider the false statement “For each x in R. x2≥ x” (consider 0 < x < 1). What is thenegation of this statement? Is it “For each x in R. x2< x”? Why not? Let P (x) be the proposition“x2≥ x” with x taken from the universe of real numbers R. Then our original statement is succinctlywritten as ∀x.P (x). How do we negate this with DeMorgan’s Law?We can chain together quantifiers in any manner we please: ∀x.∃y.∀z.P (x, y, z) and negate it using thesame rules discussed above. By applying the rules in sequence, we get that¬(∀x.∃y.∀z.P (x, y, z))∃x.¬(∃y.∀z.P (x, y, z))∃x.∀y.¬(∀z.P (x, y, z))∃x.∀y.∃z, ¬P (x, y, z)The ¬ “bubbles down”, flipping quantifiers as it goes.The following problem comes from Question 14 inthe Mathematics Subject GRE Sample Test:Exercise 4. Let R be the set of real numbers and let f and g be functions from R to R. The negation ofthe statement“For each s in R, there exists an r in R such that if f(r) > 0, then g(s) > 0.”is which of the following?(A) For each s in R, there exists an r in R such that f (r) ≤ 0 and g(s) > 0.(B) There exists an s in R such that for each r in R, f (r) ≤ 0 and g(s) ≤ 0.Date: February 1, 2008.The authors gratefully acknowledge the TA’s of CS70 Past for the use of their previous notes: Assane Gueye, VahabPournaghshband, Alex Fabrikant, Chris Crutchfield, Amir Kamil, David Garmire, Lorenzo Orecchia, and Ben Rubinstein.Their notes form the basis for this handout.1(C) There exists an s in R such that for each r in R, f (r) ≤ 0 and g(s) > 0.(D) There exists an s in R such that for each r in R, f (r) > 0 and g(s) ≤ 0.(E) For each s in R, there exists an r in R such that f (r) ≤ 0 and g(s) ≤ 0.Use the tools covered above. (hint: what happens when you negate an implication? Try rewriting thestatements in propositional logic, e.g. replacing f (r) > 0 with P (r) and g(s) > 0 with Q(s)). 4. We Hold These Truth To Be Self-Evident That ∀x, y ∈ MEN.x = yExercise 5. Suppose we’re considering the domain of just 2 numbers S = {0, 1}. Try to re-state the followingpropositions without using any quantifiers. For example, ∀x.P (x) can be re-formulated as P (0) ∧ P (1).(1) ∃x.P (x)(2) ¬∃x.P (x)(3) ∀x.∃y.P (x, y)(4) ∃x.P (x) ∨ (∀y.Q(x, y))(5) ¬(∀x.∃y.P (x) ⇒ Q(y))Exercise 6. Louis Reasoner, upon finishing CS61A, decided to take CS70. After the first lecture, he imme-diately made the conjecture that ∀x.∃y.P (x, y) is logically equivalent to ∃y.∀x.P (x, y). Use a counterexamplefrom either basic mathematics or the everyday world to prove him wrong. What about ∀x.∀y.P (x, y) vs.∀y.∀x.P (x, y)? Or what about ∃x.∃y.P (x, y) vs. ∃y∃x.P (x,
View Full Document
Unlocking...