**Exercise 4.4.1**

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

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

**Exercise 4.4.2**

How would you define **addsTo** as a ternary relation?

- Give a prose defnition of addsTo (
*x*,*y*,*z*) in terms of the addition function. - 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 (**will be true. Of course,

*A*, 2)**piratesNextTo (**would not be true in this situation. These would be analogous with the propositional WaterWorld propositions

*A*, 1)**A − has − 2**and

**A − has − 1**, respectively.

- 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**? - 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*)**∈**

*if and only if ...*

**R**-
is older than**a***b*. -
is at least as old as**a***b*. -
and*a*are exactly the same age.**b** -
and**a**have a common grandparent.**b** -
and**a**have a common grandchild.**b**

**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.

- If
is reflexive, then**R**is symmetric.**R** - If
is reflexive, then**R**is antisymmetric.**R** - If
is reflexive, then**R**is not symmetric.**R** - If
is reflexive, then**R**is not antisymmetric.**R** - If
is symmetric, then**R**is reflexive.**R** - If
is symmetric, then**R**is antireflexive.**R** - If
is symmetric, then**R**is not antireflexive.**R**

- 1523 reads