Skip to content Skip to navigation Skip to collection information

OpenStax-CNX

You are here: Home » Content » Intro to Logic » modeling with relations

Navigation

Lenses

What is a lens?

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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.

This content is ...

Affiliated with (What does "Affiliated with" mean?)

This content is either by members of the organizations listed or about topics related to the organizations listed. Click each link to see a list of all content affiliated with the organization.
  • Rice Digital Scholarship

    This collection is included in aLens by: Digital Scholarship at Rice University

    Click the "Rice Digital Scholarship" link to see all content affiliated with them.

Recently Viewed

This feature requires Javascript to be enabled.
 

modeling with relations

Module by: Ian Barland, John Greiner, Phokion Kolaitis, Moshe Vardi, Matthias Felleisen. E-mail the authors

Summary: (Blank Abstract)

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-3xnhbrxy¬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 hasStarredWithabhasStarredWithbchasStarredWithca 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

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

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 )((Rating4)(genre=Classical)) genreRock Rating4 genreClassical .

Exercise 7

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

Solution

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

However, for (genre=Rock )((Rating4)(genre=Classical)) genreRock Rating4 genreClassical there is no equivalent one-term-per-clause DNF or CNF formula! 2

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 GoodOrClassicalGoodOrClassical for (Rating4)(genre=Classical) Rating4 genreClassical , then another (genre=Rock )GoodOrClassical genreRock GoodOrClassical for the desired result.

The upshot is that iTunes came up with a query language which is as expressive as propositional3 logic. For some queries, it can be awkward to use, but the GUI designers who came up with smart playlists might have figured that few users would want such queries.

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?

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.

Collection Navigation

Content actions

Download:

Collection as:

PDF | EPUB (?)

What is an EPUB file?

EPUB is an electronic book format that can be read on a variety of mobile devices.

Downloading to a reading device

For detailed instructions on how to download this content's EPUB to your specific device, click the "(?)" link.

| More downloads ...

Module as:

PDF | More downloads ...

Add:

Collection to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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

Module to:

My Favorites (?)

'My Favorites' is a special kind of lens which you can use to bookmark modules and collections. 'My Favorites' can only be seen by you, and collections saved in 'My Favorites' can remember the last module you were on. You need an account to use 'My Favorites'.

| A lens I own (?)

Definition of a lens

Lenses

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

What is in a lens?

Lens makers point to 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 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