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.
Consider the set of WaterWorld locations
Loc=AB…Z
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 nhbrnhbr relation of the previous section is the set
A BA GB AB C…Y XY ZZ Y
A B
A G
B A
B C
…
Y X
Y Z
Z Y
.
That is, xx is related to yy if
x yx y is in the set nhbrnhbr.
For the domain
D=ObjectStringMutableString
D
Object
String
MutableString
,
the relation subclass-ofsubclass-of might be
String Object MutableString Object MutableString String
String Object
MutableString Object
MutableString String
.
In general, a binary relation over the domain DD
is a subset of
D×D
D
D
.
Note that these are ordered pairs;
just because xx is related to yy doesn't mean yy has the same
relation to xx. For example, while
MutableString Object MutableString Object
is in the relation subclass-ofsubclass-of, the pair
Object MutableString Object MutableString
most certainly is not.
You can consider the relation hasStarredWithhasStarredWith,
over the domain of Hollywood actors. We won't list all the elements of
the relation, but some related pairs are:
-
hasStarredWithEwan McGregorCameron Diaz
hasStarredWith
Ewan McGregor
Cameron Diaz
,
as witnessed by the movie A Life Less Ordinary, 1997.
-
hasStarredWithCameron DiazJohn CusackhasStarredWith
Cameron Diaz
John Cusack
,
as witnessed by the movie Being John Malkovich, 1999.
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?yummy? as
tomatoesokracucumberscarrotspotatoes
tomatoes
okra
cucumbers
carrots
potatoes
and nothing else.
In one particular game of WaterWorld,
the relation hasPiratehasPirate turned out to be
KTRUE
K
T
R
U
E
.
If unary and binary relations make sense,
what about ternary, etc., relations? Sure!
In general, a kk-ary relation
(or, “relation of arity kk”)
over the domain DD is a subset of
Dk
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
“
RxyRx y is true
”,
we'll simply write
“
RxyRx y
”.
In fact, notice that once you choose some particular pair of
xx and yy, then
RxyRx 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.)
“
prime18prime18
”
is a proposition that's false,
assuming the standard
interpretation
of primeprime.
“
safeAsafe A
”
is a proposition that is true on some boards and not others.
The relation nhbrnhbr, 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 input
is in the set or not.
So instead of being given the set nhbrnhbr,
you would have been equally happy with
its indicator function
fnhbrfnhbr,
where (for example)
fnhbrBC=true
fnhbr
B C
and
fnhbrBQ=false
fnhbr
B Q
.
Similarly, if you know that
fhasPirateK=true
fhasPirate
K
and that
fhasPirateL=false
fhasPirate
L
,
then this is enough information to conclude that
K∈hasPirate
K
hasPirate
and
L∉hasPirate
L
hasPirate
.
The set and the function are equivalent ways of
modeling the same underlying relation.
The next two exercises aren't meant to be difficult,
but rather to illustrate that, while we've sketched these two
approaches and suggested they are equivalent,
we still need an exact definition.
For the indicator function
fxy={true if y=x2false otherwise
f x y
y
x
2
on the domain of (pairs of) natural numbers,
write down the set-of-pairs representation
for the corresponding binary relation.
It's insightful to give the answer both by listing the elements,
possibly with ellipses,
and also by using set-builder notation.
In general,
for a binary indicator function ff,
what, exactly, is the corresponding set?
00112439…i i2 …
00
11
24
39
…
i i2
…
In set-builder notation, this is
xy
y=x2
xy
y
x2
In general, for an indicator function ff,
the corresponding set would be
xy
fxy
xy
f xy
(Note that we don't need to write
“
…
fxy=true
f xy
”;
as computer scientists comfortable with Booleans
as values, we see this is redundant.)
For the relation
hasPirate=KTRUE
hasPirate
K T R U E
on the set of (individual) WaterWorld locations,
write down the indicator-function representation
for the corresponding unary relation.
In general, how would you write down
this translation?
fhasPiratex={true if x=Ktrue if x=Ttrue if x=Rtrue if x=Utrue if x=Efalse otherwise
f
hasPirate
x
x K
x T
x R
x U
x E
.
In general, for a (unary) relation RR,
fRx={true if x∈Rfalse if x∉R
f
R
x
x R
x R
.
Since these two formulations of a relation,
sets and indicator functions,
are so close, we'll often switch between them (a very slight abuse
of terminology).
Think about when you write a program that uses the
abstract data type Set. Its main operation is
elementOf.
When might you use an explicit enumeration to encode a set,
and when an indicator function?
Which would you use for the set of WaterWorld locations?
Which for the set of prime numbers?
Some binary relations have a special property:
each element of the domain occurs as the first item
in exactly one tuple.
For example,
isPlanet=Earth trueVenus trueSol falseCeres falseMars true
isPlanet
Earth
Venus
Sol
Ceres
Mars
is actually a (unary) function.
On the other hand,
isTheSquareOf=0 01 11 -14 24 -29 39 -3…
isTheSquareOf
0 0
1 1
1 -1
4 2
4 -2
9 3
9 -3
…
is not a function, for two reasons. First, some numbers occur
as the first element of multiple pairs.
Second, some numbers, like 33, occurs as the first element
of no pairs.
We can generalize this to relations of higher arity, also.
This is explored in
this exercise and
this one.
One subclass of relations are common enough to merit some special discussion:
binary relations. These are relations on pairs, like nhbrnhbr.
Although we introduced relations with prefix notation, e.g.,
<ij< i j,
we'll use the more common infix notation,
i<j i j,
for well-known arithmetic binary relations.
In fact, binary relations are common enough that sometimes
people use some entirely new vocabulary:
A domain with a binary relation can
be called vertices with edges between them.
Together this is known as a graph.
We won't stress these terms right now,
as we're not studying graph theory.
Binary relations (graphs) can be depicted visually,
by drawing the domain elements (vertices) as dots,
and drawing arrows (edges) between related elements.
A binary relation with a whole website devoted to it is
“has starred in a movie with”.
We'll call this relation hasStarredWithhasStarredWith
over the domain of actors. Some sample points in this relation:
-
hasStarredWithEwan McGregorCameron Diaz
hasStarredWith
Ewan McGregor
Cameron Diaz
,
as witnessed by the movie A Life Less Ordinary, 1997.
-
hasStarredWithCameron DiazJohn Cusack
hasStarredWith
Cameron Diaz
John Cusack
,
as witnessed by the movie Being John Malkovich, 1999.
You can think of each actor being a
“location”,
and two actors being
“adjacent” to each other
if they have ever starred in a movie together;
two of these locations, even if not adjacent might have a multi-step
path between them.
(There is also a shorter path; can you think of it?
The (in)famous Kevin Bacon game
asks to find a shortest path from one location to the
location Kevin Bacon.
Make a guess, as to the longest shortest path leading from
(some obscure) location to Kevin Bacon.)
Some other graphs:
-
Vertices can be tasks,
with edges meaning dependencies of what must be done first.
-
In parallel processing,
Vertices can be lines of code;
there is an edge between two lines if
they involve common variables.
Finding subsets of vertices with no lines between them
represent sets of instructions that can be
executed in parallel (and thus assigned to different processors.)
-
“Word ladders” seek to transform one word to another
by changing one letter at a time, while always remaining a word.
For example, a ladder leading from WHITE to SPINE in three steps is:
If a solution to such a puzzle corresponds to a path,
what do vertices represent?
What are edges?
Do you think there is a path from any 5-letter word to another?
