<< Chapter < Page Chapter >> Page >
Relations are subsets. Binary relations might be reflexive, symmetric, antisymmetric, or transitive.

When using relations in logic formulas, there are two things going on:

  • relations themselves, as mathematical entities, and
  • formulas involving symbols, which must be interpreted as specific relations.
First things first: we'll just discuss relations for now, and later tackle using relations in logic formulas.

We'll start with a couple of equivalent ways of defining relations, and then discuss a common subclass of relations: binary relations.

Relations as subsets

Consider the set of WaterWorld locations Loc A B Z . For this domain (also known as a universe ), we'll say a binary relation is a set of (ordered) pairs of the domain.

For instance, the nhbr relation of the previous section is the set A B A G B A B C Y X Y Z Z Y .

That is, x is related to y if x y is in the set nhbr .

Got questions? Get instant answers now!

For the domain D Object String MutableString , the relation subclass-of might be String Object MutableString Object MutableString String .

In general, a binary relation over the domain D is a subset of D D . Note that these are ordered pairs; just because x is related to y doesn't mean y has the same relation to x . For example, while MutableString Object is in the relation subclass-of , the pair Object MutableString most certainly is not.

Got questions? Get instant answers now!

You can consider the relation hasStarredWith , over the domain of Hollywood actors. We won't list all the elements ofthe relation, but some related pairs are:

  • hasStarredWith Ewan McGregor Cameron Diaz , as witnessed by the movie A Life Less Ordinary , 1997.
  • hasStarredWith Cameron Diaz John Cusack , as witnessed by the movie Being John Malkovich , 1999.

Got questions? Get instant answers now!

If binary relations are subsets of pairs of the domain, what might a unary relation be? Simply, subsets of the domain.

For the domain of vegetables, Ian defines the relation yummy? as tomatoes okra cucumbers carrots potatoes and nothing else.

Got questions? Get instant answers now!

In one particular game of WaterWorld, the relation hasPirate turned out to be K T R U E .

Got questions? Get instant answers now!

If unary and binary relations make sense, what about ternary, etc. , relations? Sure! In general, a k -ary relation (or,

relation of arity k
) over the domain D is a subset of D k . However, any given relation has a fixed arity.That is, a relation may be binary or ternary, but not both.

As with propositions, rather than writing

R x y is true
, we'll simply write
R x y
. In fact, notice that once you choose some particular pair of x and y , then R x y can be treated as a single true/false proposition.(We'll soon extend the idea of propositions to include such relation symbols,and then allow formulas to include these terms .)

prime 18
is a proposition that's false, assuming the standard interpretation of prime .

Got questions? Get instant answers now!

safe A
is a proposition that is true on some boards and not others.

Got questions? Get instant answers now!

Relations as functions

The relation nhbr , which we're defining as a set (of pairs), could also be thought of being a function.We say that the indicator function of a set is a Boolean function indicating whether its inputis in the set or not. So instead of being given the set nhbr , you would have been equally happy withits indicator function f nhbr , where (for example) f nhbr B C and f nhbr B Q . Similarly, if you know that f hasPirate K and that f hasPirate L , then this is enough information to conclude that K hasPirate and L hasPirate . The set and the function are equivalent ways of modeling the same underlying relation.

Get Jobilize Job Search Mobile App in your pocket Now!

Get it on Google Play Download on the App Store Now




Source:  OpenStax, Intro to logic. OpenStax CNX. Jan 29, 2008 Download for free at http://cnx.org/content/col10154/1.20
Google Play and the Google Play logo are trademarks of Google Inc.

Notification Switch

Would you like to follow the 'Intro to logic' conversation and receive update notifications?

Ask