ASIDE: Note that the nhbr relation can actually represent an arbitrarily weird board, such as locations that look adjacent on the map but actually aren't, boards which wrap around a cylinder or toroid, or a location with a tunnel connecting it to a location far across the board (like the secret passages in the game Clue, or the harrowing sub trip through Naboo in Star Wars: The Phantom Menace.) One-way passages can be encoded as well (meaning the nhbr relation need not be symmetric). Actually, any graph can be representedl
Exercise 3.5.1
How shall we encode concepts such as " location A has 3 dangerous neighbors ", using relations? Proofs otherwise unchanged. Note that we might express our rules as " for any
locations x and y, we have the following axiom: has − 3(x) ∧ nhbr (x, y) ⇒¬safe (y) ".
Really, note that there's something else going on here: x and y are symbols which can represent any location: they are variables, whose value can be any
element of the domain.
For the domain of types-of-vegetables, the relation yummy is a useful one to know, when cooking. In case you weren't sure, yummy
(Brussels sprouts) = false, and yummy (carrots) = true.
Suppose we had a second relation, yucky. Is it conceivable that we could model a vegetable that's neither yucky nor yummy, using these relations? Sure! (Iceberg
lettuce, perhaps.) In fact, we could even have a vegetable which is both yummy and yucky radishes!
ASIDE: A quick digression on a philosophical nuance: the domain for the above problem is not vegetables; it's types-of-vegetables. That is, we talk about whether or not carrots are yummy; this is different than talking the yumminess of the carrot I dropped under the couch yesterday, or the carrot underneath the chocolate sauce. In computer science, this often manifests itself as the difference between values, and types of values. As examples, we distinguish between 3 and the set of all integers, and we distinguish between particular carrots and the abstract idea of carrots. (Some languages even include types as values.) Philosophers enjoy debating how particular instances define the abstract generalization, but for our purposes we'll take each both vegetables and types of-vegetables as given.
Exercise 3.5.2
You might have objected to the idea of the unary relation yummy, since different people have different tastes. How could you model individuals' tastes? (Hint: Use a
binary relation.) )
Modeling actors and the has-starred-with relation didn't include information about specific movies. For instance, it was impossible to write any formula which could capture the notion of
three actors all being in the same movie.
Exercise 3.5.3
Why doesn't hasStarredWith (a, b) ∧ hasStarredWith (b, c) ∧ hasStarredWith (c, a) capture the notion of a, b, and c all being in the same movie? Prove your answer by giving a counterexample.
Exercise 3.5.4
How might we make a model which does capture this? What is the domain? What relations do you want?
Of course, the notion of interpretations are still with us, though usually everybody wants to be thinking of one standard interpretation. Consider a relation with elements such as
isChildOf (Bart, Homer, Marge). Would the triple (Bart, Marge, Homer) be in the relation as well as (Bart, Homer, Marge)?
As long as all the writers and users of formulas involving isChildOf all agree on what the intended interpretation is, either convention can be used.
- 1801 reads
