Discussion problems, CS40, 04/02/2008

1. (p. 58, #1) Translate these statements into English, where the domain for each variable consists of all real numbers.

a) ∀x∃y(x<y)

b) ∀x∀y( ( (x ≥0) ∧ (y≥0) ) → (xy≥0) )

c) ∀x∀y∃z( xy = z )

2. (based on problem p. 58, #3) Let R(x,y) by the statement "x has requested that y add him/her as a Facebook™ friend", where the domain for both x and y consists of all students registered for CS40 this semester. Express each of these quantifications in English:

a) ∃x∃yR(x,y)

b) ∃x∀yR(x,y)

c) ∀x∃yR(x,y)

d) ∃y∀xR(x,y)

e) ∀y∃xR(x,y)

f) ∀x∀yR(x,y)

3. (based on p. 58 #7) Let T(x) mean that student x likes cuisine y (e.g. Mexican, Italian, Japanese, or Diner food), where the domain for x consists of all students in CS40, and the domain for y consists of all cuisines. Express each of these statements by a simple English sentence.

a) ¬T (Amos, Japanese)

b) ∃xT(x,Korean) ∧ ∀xT(x,Mexican)

c) ∃y(T(Michael, y) ∨ T(Jimmy,y))

d) ∀x∀z∃y((x ≠ z) → ¬(T(x,y) ∧ T(z,y)))

(After you state this one in logic terms, rephrase it in plain english... that is, once you understand what the statement is saying, say in a way that your roommate would understand it, even if she/he is not a math or computer science major. Then, tell me whether you think it is true or not? What would we have to do to find out? How many questions would we have to ask?)