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
LL = { AA, BB, …, ZZ }.
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:
-
hasStarredWith(Ewan McGregor,Cameron Diaz)hasStarredWith(Ewan McGregor,Cameron Diaz),
as witnessed by the movie A Life Less Ordinary, 1997.
-
hasStarredWith(Cameron Diaz,John Cusack)hasStarredWith(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
“R(x,y)R(x,y) is true”,
we'll simply write
“R(x,y)R(x,y)”.
In fact, notice that once you choose some particular xx, yy, then
R(x,y)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)prime(18)”
is a proposition that's false,
(assuming the standard interpretation of primeprime
— more on interpretations later.)
“safe(A)safe(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 KhasPirate
and
L∉hasPirateLhasPirate.
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
f(x,y)=trueify=x2falseotherwise
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
(and using “…”),
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=trueifx=Ktrueifx=Ttrueifx=Rtrueifx=Utrueifx=Efalseotherwise
fhasPirate
x
x K
x T
x R
x U
x E
.
In general, for a (unary) relation RR,
fRx=trueifx∈Rfalseifx∉R
fR
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?
