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!
How shall we encode concepts such as
“
location AA has 3 dangerous neighbors
”,
using relations?
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 >.
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!
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.
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.)
)
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.
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.
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?
How might we make a model which does capture this?
What is the domain? What relations do you want?
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.
