Relations and Logic: modeling

Modeling with Relations 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 represented! How shall we encode concepts such as location A has 3 dangerous neighbors , using relations? 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 . 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 >. 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). 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 , and yummy carrots . 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! 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. 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.) ) We can use the binary relation thinksIsYummy: In particular, thinksIsYummy Ian anchovies but thinksIsYummy Phokion anchovies 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. 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. 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. 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 Bullwinkle, 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 nullified, in the future? How might we make a model which does capture this? What is the domain? What relations do you want? 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, 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 infinite 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. 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.

A Case Study: iTunes Consider iTunes' smart playlists: you can create a playlist consisting of (say) All songs I've rated 3-stars or better, and whose genre is not Classical . This is smart because its a program which is re-run every time your music library changes: For example, if you change a song's genre, it may be immediately added or deleted from the playlist. We realize actually have a simple formula (which we can express in propositional logic with relations). The structure (instance) for a single is the interpretation. This formula is true when interpreted on (my library's representation of) Brian Eno's Here Come the Warm Jets, but false for Bonnie Tyler's '80's epic Holding Out for a Hero and for Bach's Little Fugue in Gm . We now have one formula, and want to determine its truth-value in many different particular interpretations. In fact, we want to return all interpretations which make the formula (playlist) true. Look at the GUI box for defining these queries. Compared to propositional logic, what sort of formulas can you define? DNF or CNF: Each line corresponds to a single predicate, and at the top of the box you can ask for songs which mach any (disjunction) or all (conjunction) of the predicates. Are there queries which can't be directly transliterated into the GUI box? Transliterate meaning a word-for-word substitution, while translate preserves meanings and idioms. So while the German Übung macht den Meister transliterates to Drill makes the master, it translates to Practice makes perfect. Yes. Two examples are genreClassical genreHoliday , and genreRock Rating4 genreClassical . Can you find formulas equivalent to each of the preceding two, which can be expressed? Yes and no. For genreClassical genreHoliday , we can clearly use DeMorgan's law and make the query genreClassical genreHoliday . However, there is no possible CNF or DNF equivalent to the second formula! Budding logicians might wonder how you actually prove this claim! The upshot is that iTunes came up with a query language which is not as expressive as propositional Technically, this is a relational calculus formula, since we are using relations instead of flat propositions. logic. More fundamentally, the programmers and GUI designers who came up with smart playlists may have only thought they were coding up a style of GUI lists and menus, and never thought to compare themselves to the well-known query language of propositional logic. How might you create a GUI widget which can specify any propositional formula, and yet still look nice and be intuitive enough for my mother to use? Is there a better usability/expressibility trade-off than what iTunes has done, or are they optimal? (Or, are the only queries which iTunes can express too obscure or weird to worry about?)