Solutions to Exercises in Chapter 3

Available under Creative Commons-ShareAlike 4.0 International License. Download for free at http://cnx.org/contents/383d4b87-2d7b-454e-99fe-2eaa43eae8ff@20.20

Solution to Exercise 3.1.1

We'll use a unary (one-input) relation: safe(A) is true if and only if ("if") location A is safe.

Solution to Exercise 3.2.1

{(0,0), (1; 1) ; (2; 4) ; (3; 9) , …, (i, i²), …} In set-builder notation, this is {(x; y) ( y = x²}

In general, for an indicator function f, the corresponding set would be {(x, y) | f (x, y) } (Note that we don't need to write " ... f (x, y) = true "; as computer scientists comfortable with Booleans as values, we see this is redundant.)

Solution to Exercise 3.2.2

$f_{hasPirate\left ( x \right )}=\left\{\begin{matrix} true\ if\ x=K\\ true\ if\ x=T\\ true\ if\ x=R\\ true\ if\ x=U\\ true\ if\ x=E\\ false\ otherwise \end{matrix}\right. .$

In general, for a (unary) relation R, $f_{R}\left ( x \right )=\left\{\begin{matrix} true\ if\ x \in R \\ false\ if\ x \notin R \end{matrix}\right. .$

Solution to Exercise 3.3.1

For all w, x, y, and z of the domain,

$S\left ( w,x,y \right )\wedge S\left ( w,x,z \right )\Rightarrow\left ( y=z \right )$

Solution to Exercise 3.5.1

A good first guess might be to say we have a function which returns the number of pirates next to a given location. That is, " piratesNear(A)=3 ". However, "piratesNear" doesn't qualify as a relation. Why not?

To work around this, we could propose a binary relation along the lines of " piratesNear (A, 3) = true ". This is better, but it requires our domain to be not only board locations, but also numbers. And to be able to talk about numbers, we'd need more axioms, as well as numeric relations such as >.

ASIDE: Hmmm, what is the arity of ">"?

While this approach is feasible, and ultimately might be what we want, for now, let's stick with relations involving only locations, not numbers.

Okay, the third time's the charm: we'll implement the concept "A neighbors three pirates" as a relation has − 3(A) being true. To cover the cases when there are exactly two neighboring pirates, we'll use a whole new separate relation, "has − 2"; has − 2(A) would be false on any board where has − 3(A) is true (at least, in our standard interpretation).

Solution to Exercise 3.5.2

We can use the binary relation thinksIsYummy: In particular, thinksIsYummy (Ian, anchovies) = false but thinksIsYummy (Phokion, anchovies) = true What set are we using, as the domain for this? Really, the domain is the union of people and pizza-toppings. So thinksIsYummy (radishes, brusselsSprouts) is a valid thing to write down; it would be false. Note that if working with such a domain, having unary predicates isVegetable and isPerson would be useful.

Solution to Exercise 3.5.3

The proposed formula asserts that each pair has been in some movie together, but they each could have been different movies without being in the same one simultaneously. As a counterexample, it is true that hasStarredWith (Charlie Chaplin, Norman Lloyd) (as witnessed by Limelight, 1952), hasStarredWith (Norman Lloyd, Janeane Garofolo) (as witnessed by The Adventures of Rocky and Bullwin kle, 2000), and if we generously include archive footage, hasStarredWith (Charlie Chaplin, Janeane Garofolo) (as witnessed by Outlaw Comic: The Censoring of Bill Hicks, 2003); however, they have not all been in a movie together. Might the counterexample you chose become nullifed, in the future?

Solution to Exercise 3.5.4

As always, there are several ways of modeling this problem. We'll outline three.

First, we could augment the hasStarredWith to be a ternary (3-input) relation to include the movie. Like in the yummy extension (Exercise 3.5.2), the domain would then include both actors and movies, and we'd also want relations to know which is which.

Second, we could use a bunch of relations. Starting with the familiar binary hasStarredWith, we'd add the ternary hasStarredWith3, the quaternary hasStarredWith4, .... Our domain would just be actors. However, we'd either need an infnite number of such relations, which we normally don't allow, or we'd need an arbitrary cap on the number of people we're interested in at a time.

Third, we could use sets of actors, instead of individuals. We'd need only one relation, haveStarredtogether, that states a set of actors have starred together in a single movie. Solution to Exercise 3.5.5 (p. 84)

This is effectively Disjunctive or Conjunctive Normal Form, limited to clauses of one term each.

Solution to Exercise 3.5.6

Yes. Two examples are ¬ ((genre = Classical) ∨ (genre = Holiday)), and (genre = Rock) ∧ ((Rating ≥ 4) ∨ (genre = Classical)).

Solution to Exercise 3.5.7

For the first example, ¬ ((genre = Classical) ∨ (genre = Holiday)), we can clearly use DeMorgan's law and make the query ¬ (genre = Classical) ∧¬ (genre = Holiday).

However, for (genre = Rock) ∧ ((Rating ≥ 4) ∨ (genre = Classical)) there is no equivalent one-termper-clause DNF or CNF formula!¹⁶

Fortunately, iTunes has a way around this. Playlist membership or non-membership is itself an available predicate, allowing you to nest playlists. Thus, you can build a playlist GoodOrClassical for (Rating ≥ 4) ∨ (genre = Classical), then another (genre = Rock) ∧ GoodOrClassical for the desired result.

3628 reads

You are here

Solutions to Exercises in Chapter 3