CSE 472/572, Spring 2002 ------------------------------------------------------------------------- HW #8 Answers & Grading ========================================================================= 1. R&N, Ch. 8, p. 262, #8.8: * Omitting universal quantifiers, the answers are: Before(i,j) <=> Ek[Meet(i,k) ^ Meet(k,j)] After(i,j) <=> Before(j,i) During(i,j) <=> EkEm[Meet(Start(j),k) ^ Meet(k,i) ^ Meet(i,m) ^ Meet(m,End(j))] Overlap(i,j) <=> Ek[During(k,i) ^ During(k,j)] * 4 defs @ 0246 each = 24 pts. total ------------------------------------------------------------------------- 2. For each problem: translation into FOL: 0123 syntax & semantics: 0123 Total = 24 points. a) Ey[Ice_cream_cone(y) ^ Gave(mary, michael, y)] or: Gave(mary, michael, ice-cream-cone-3) syntax semantics ------ --------- Gave(x,y,z) x gave z to y Ice_cream_cone(x) x is an ice cream cone mary Mary michael Michael ice-cream-cone-3 an ice cream cone b) NB: In FOL, must make a decision about the (implicit) quantifier. Thus, either "all bb players are tall" or "some bb players are tall" Ax[BBP(x) => Tall(x)] or: Ex[BBP(x) ^ Tall(x)] syntax semantics ------ --------- BBP(x) x is a basketball player Tall(x) x is tall c) Ex[Tree(x) ^ Ay[Tree(y) {^ In_the_vicinity(y)} => y=x] ^ Ez[Axe(z) ^ Cut_down(robert, x, z)]] or any Skolemization thereof, with or without the Ay[] clause, and with or without the optional "In_the_vicinity" clause syntax semantics ------ --------- Tree(x) x is a tree In_the_vicinity(x) x is in the nearby vicinity NB: The idea behind this is to make sense out of "the tree"; clearly, there isn't a single, unique tree. Rather, there is one salient tree in the nearby vicinity. The braces are being used here to show that this clause is optional. Axe(x) x is an axe Cut_down(x,y,z) x cut down y using z robert Robert d) Here's one possibility: Ey[Bowl(y) ^ Ax[Ingredient(x) => (In(x,y) ^ Mixed_thoroughly(x))] i.e., there is a bowl (y), and, for each ingredient x, x is in the bowl and x is mixed thoroughly. But this doesn't quite work, because it's not that *each* ingredient is mixed thoroughly; rather, all of them are thoroughly mixed together! So, here's another possibility, now using the braces as they are used in set theory (note that set-brace notation is a "variable-binding" operator, like the quantifiers!): Ex[x = {y | Ingredient(y)} ^ Ez[Bowl(z) ^ In(x,z)] ^ Mixed_thoroughly(x)] i.e., there is a set (x) of ingredients and there is a bowl that the set is in and the set is mixed thoroughly. syntax semantics ------ --------- Bowl(x) x is a bowl Ingredient(x) x is an ingredient (in the recipe) In(x,y) x is located in y Mixed_thoroughly x is mixed thoroughly {y | P} the set of all y such that P (note that this is a term-forming operator) ========================================================================= Total = 48 points Letter CS 472 both CS 572 ------------------------------ A 46-48 A- 44-45 B+ 41-43 B 38-40 B- 35-37 C+ 33-34 C 28-32 17-32 C- 22-27 D+ 17-21 D 9-16 F 0- 8