Skip to content Skip to navigation

Connexions

You are here: Home » Content » Relations and Logic: modeling

Navigation

Content Actions
  • Download module PDF
  • Add to ...
    Add the module to:
    • My Favorites
    • A lens
    • An external social bookmarking service
    • My Favorites (What is 'My Favorites'?)
      'My Favorites' is a special kind of lens which you can use to bookmark modules and collections directly in Connexions. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need a Connexions account to use 'My Favorites'.
    • A lens (What is a lens?)

      Definition of a lens

      Lenses

      A lens is a custom view of Connexions content. You can think of it as a fancy kind of list that will let you see Connexions through the eyes of organizations and people you trust.

      What is in a lens?

      Lens makers point to Connexions materials (modules and collections), creating a guide that includes their own comments and descriptive tags about the content.

      Who can create a lens?

      Any individual Connexions member, a community, or a respected organization.

      What are tags? tag icon

      Tags are descriptors added by lens makers to help label content, attaching a vocabulary that is meaningful in the context of the lens.

    • External bookmarks
  • E-mail the authors
  • Rate this module (How does the rating system work?)

    Rating system

    Ratings

    Ratings allow you to judge the quality of modules. If other users have ranked the module then its average rating is displayed below. Ratings are calculated on a scale from one star (Poor) to five stars (Excellent).

    How to rate a module

    Hover over the star that corresponds to the rating you wish to assign. Click on the star to add your rating. Your rating should be based on the quality of the content. You must have an account and be logged in to rate content.

    		(0 ratings)

Recently Viewed

This feature requires Javascript to be enabled.

Relations and Logic: modeling

Module by: Ian Barland, John Greiner, Phokion Kolaitis, Moshe Vardi, Matthias Felleisen

Summary: (Blank Abstract)

Note: Your browser may not currently support MathML. See our browser support page for additional details. You can always view the correct math in the PDF version.

Modeling with Relations

Aside:

Note that the nhbrnhbr 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 nhbrnhbr relation need not be symmetric). Actually, any graph can be represented!

Exercise 1

How shall we encode concepts such as “ location AA has 3 dangerous neighbors ”, using relations?

Solution

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, “ piratesNearA=3 piratesNear A 3 ”. However, “piratesNearpiratesNear” doesn't qualify as a relation. Why not?

To work around this, we could propose a binary relation along the lines of “ piratesNearA3=true 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 >.

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 “AA neighbors three pirates” as a relation has-3A 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-2has-2”; has-2A has-2 A would be false on any board where has-3A 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 xx and yy, we have the following axiom: has-3x∧nhbrxy⇒¬safey has-3 x nhbr x y safe y ”. Really, note that there's something else going on here: xx and yy 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 yummyyummy is a useful one to know, when cooking. In case you weren't sure, yummyBrussels sprouts=false yummy Brussels sprouts , and yummycarrots=true yummy carrots .

Suppose we had a second relation, yuckyyucky. 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 2

You might have objected to the idea of the unary relation yummyyummy, since different people have different tastes. How could you model individuals' tastes? (Hint: Use a binary relation.) )

Solution

We can use the binary relation thinksIsYummythinksIsYummy: In particular, thinksIsYummyIananchovies=false thinksIsYummy Ian anchovies but thinksIsYummyPhokionanchovies=true 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 thinksIsYummyradishesbrusselsSprouts 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 isVegetableisVegetable and isPersonisPerson 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.

Exercise 3

Why doesn't hasStarredWithab∧hasStarredWithbc∧hasStarredWithca hasStarredWith a b hasStarredWith b c hasStarredWith c a capture the notion of aa, bb, and cc all being in the same movie? Prove your answer by giving a counterexample.

Solution

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 hasStarredWithCharlie ChaplinNorman Lloyd hasStarredWith Charlie Chaplin Norman Lloyd (as witnessed by Limelight, 1952), hasStarredWithNorman LloydJaneane Garofolo hasStarredWith Norman Lloyd Janeane Garofolo (as witnessed by The Adventures of Rocky and Bullwinkle, 2000), and if we generously include archive footage, hasStarredWithCharlie ChaplinJaneane Garofolo 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?

Exercise 4

How might we make a model which does capture this? What is the domain? What relations do you want?

Solution

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

First, we could augment the hasStarredWithhasStarredWith to be a ternary (3-input) relation to include the movie. Like in the yummyyummy 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 hasStarredWithhasStarredWith, we'd add the ternary hasStarredWith3hasStarredWith3, the quaternary hasStarredWith4hasStarredWith4, …. 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, haveStarredtogetherhaveStarredtogether, 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 isChildOfBartHomerMarge isChildOf Bart Homer Marge . Would the triple Bart Marge Homer Bart Marge Homer be in the relation as well as Bart Homer Marge Bart Homer Marge ?

As long as all the writers and users of formulas involving isChildOfisChildOf 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.

Exercise 5

Look at the GUI box for defining these queries. Compared to propositional logic, what sort of formulas can you define?

Solution

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.

Exercise 6

Are there queries which can't be directly transliterated into the GUI box? 1

Solution

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

Exercise 7

Can you find formulas equivalent to each of the preceding two, which can be expressed?

Solution

Yes and no. For ¬genre=Classical∨genre=Holiday genreClassical genreHoliday , we can clearly use DeMorgan's law and make the query ¬genre=Classical∧¬genre=Holiday genreClassical genreHoliday . However, there is no possible CNF or DNF equivalent to the second formula! 2

The upshot is that iTunes came up with a query language which is not as expressive as propositional3 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.

Note:

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?)

Footnotes

  1. “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”.
  2. Budding logicians might wonder how you actually prove this claim!
  3. Technically, this is a “relational calculus” formula, since we are using relations instead of flat propositions.

Comments, questions, feedback, criticisms?

Send feedback