Exercises for first-order logic  (Page 8/5)

Consider the binary relation $\mathrm{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?

How would you define $\mathrm{addsTo}$ as a ternary relation?

1. Give a prose definition of $\mathrm{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\}$ .

Generalize the previous problem to describe how you can represent any $k$ -ary function as a $\left(k+1\right)$ -ary relation.

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, $\mathrm{atLeastAsWiseAs}(a, b)\lor \mathrm{atLeastAsWiseAs}(b, a)$
• For arbitrary $a$ in the domain, $\mathrm{prime}(a)\implies \left(\mathrm{odd}(a)\implies \mathrm{prime}(a)\right)$
• For arbitrary $a$ and $b$ in the domain, $\mathrm{betterThan}(a, b)\implies \neg \mathrm{betterThan}(b, a)$

[Practice problem $—$ solution provided.]

Suppose we wanted to represent the count of neighboring pirates with a binary relation, such that when location $A$ has two neighboring pirates, $\mathrm{piratesNextTo}(A, 2)$ will be true. Of course, $\mathrm{piratesNextTo}(A, 1)$ would not be true in this situation. These would be analogous with the propositional WaterWorld propositions $\mathrm{A-has-2}$ and $\mathrm{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 $\mathrm{piratesNextTo}$ ?

2. If we further introduced another relation, $\mathrm{isNumber?}$ , what is a formula that would help distinguishintended interpretations from unintended interpretations? That is, give a formula that is true under all our intendedinterpretations of $\mathrm{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 .)