Relations and Interpretations

Exercise 4.4.1

Consider the binary relation is − a − factor − of on the domain {1, 2, 3, 4, 5, 6}.

1. List all the ordered pairs in the relation.
2. Display the relation as a directed graph.
3. Display the relation in tabular form.
4. Is the relation reflexive? symmetric? transitive?

Exercise 4.4.2

How would you define addsTo as a ternary relation?

1. Give a prose defnition of addsTo (x, y, z) in terms of the addition function.
2. List the set of triples in the relation on the domain {1, 2, 3, 4}.

Exercise 4.4.3

Generalize the previous problem (Exercise 4.4.2) to describe how you can represent any k-ary function as a (k + 1)-ary relation.

Exercise 4.4.4

Are each of the following formulas valid, i.e., true for all interpretations? (Remember that the relation names are just names in the formula; don't assume the name has to have any bearing on their interpretation.)

• For arbitrary a and b in the domain, atLeastAsWiseAs (a, b) ∨ atLeastAsWiseAs (b, a)
• For arbitrary a in the domain, prime (a) ⇒ (odd(a) ⇒ prime (a))
• For arbitrary a and b in the domain, betterThan (a, b) ⇒¬betterThan (b, a)

For each, if it is true or false under all interpretations, prove that. For these small examples, a truth table will probably be easier than using Boolean algebra or inference rules. Otherwise, give an interpretation in which it is true, and one in which it is false.

Exercise 4.4.5

Suppose we wanted to represent the count of neighboring pirates with a binary relation, such that when location A has two neighboring pirates, piratesNextTo (A, 2) will be true. Of course, piratesNextTo (A, 1) would not be true in this situation. These would be analogous with the propositional WaterWorld propositions A − has − 2 and A − has − 1, respectively.

1. If we only allow binary relations to be subsets of a domain crossed with itself, then what must the domain be for this new relation piratesNextTo?
2. If we further introduced another relation, isNumber?, what is a formula that would help distinguish intended interpretations from unintended interpretations? That is, give a formula that is true under all our intended interpretations of piratesNextTo but is not true for some "nonsense" interpretations we want to exclude. (This will be a formula without an analog in the WaterWorld domain axioms (Propositional axioms for WaterWorld).)

Exercise 4.4.6

Determine whether the relation R on the set of all people is reflexive, antireflexive, symmetric, antisymmetric, andjor transitive, where (a, b) ∈ R if and only if ...

1. a is older than b.
2. a is at least as old as b.
3. a and b are exactly the same age.
4. a and b have a common grandparent.
5. a and b have a common grandchild.

Exercise 4.4.7

For each of the following, if the statement is true, explain why, and if the statement is false, give a counter-example relation.

1. If R is reflexive, then R is symmetric.
2. If R is reflexive, then R is antisymmetric.
3. If R is reflexive, then R is not symmetric.
4. If R is reflexive, then R is not antisymmetric.
5. If R is symmetric, then R is reflexive.
6. If R is symmetric, then R is antireflexive.
7. If R is symmetric, then R is not antireflexive.