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

[Practice problem $—$ solution provided.]

Find two fundamentally different interpretations that satisfy the statement

There exists one person who is liked by two people

For the four

Musketeer

Depict each of these interpretations as a graph . Draw three circles ( nodes ) representing the three people, and an arrow ( edge ) from a person to each person they like.(You can glance at Rosen Section 9.1, Figure 8 for an example.)

Translate the following statements into first-order logic. The domain is the set of natural numbers, and the binary relation $\mathrm{kth}(k, n)$ indicates whether or not the $k$ th number of the sequence is $n$ . For example, the sequence $\left(5,7,5\right)$ , isrepresented by the relation $\mathrm{kth}=\{\left(0,5\right), \left(1,7\right), \left(2,5\right)\}$ . You can also use the binary relations $$ , $$ , and $$ , but no others.

You may assume that $\mathrm{kth}$ models a sequence. No index $k$ is occurs multiple times, thus excluding $\mathrm{kth}=\{\left(0,5\right), \left(1,7\right), \left(0,9\right)\}$ . Thus, $\mathrm{kth}$ is a function, as in a previous example representing an array as a function . Also, no higher index $k$ occurs without all lower-numbered indices being present, thus excluding $\mathrm{kth}=\{\left(0,5\right), \left(1,7\right), \left(3,9\right)\}$ .

1. The sequence is finite.
2. The sequence contains at least three distinct numbers , e.g. , $\left(5,6,5,6,7,8\right)$ , but not $\left(5,6,5,6\right)$ .

3. The sequence is sorted in non-decreasing order, e.g. , $\left(3,5,5,6,8,10,10,12\right)$ .

4. The sequence is sorted in non-decreasing order,except for exactly one out-of-order element, e.g. , $\left(20,30,4,50,60\right)$ .