Exercises for first-order logic

Some binary relations can be viewed as the encoding of a unary function, where the first element of the ordered pair representsthe function's value. For instance, in a previous exercise we encoded the binary function addition as a ternary relation $\mathrm{addsTo}$ .

1. Give one example of a binary relation which does not correspond to the encoding of a function.

2. Write a first-order formula describing the properties that a binary relation $R$ must have to correspond to a unary function.

Alternation of quantifiers: Determine the truth of each of the following sentencesin each of the indicated domains.

Four sentences:

1. $\forall x\colon \forall y\colon \exists z\colon \mathrm{likes}(x, y)\land \left((z\neq y)\implies \neg \mathrm{likes}(y, z)\right)$
2. $\exists x\colon \forall y\colon \forall z\colon \mathrm{likes}(x, y)\land \left((z\neq y)\implies \neg \mathrm{likes}(y, z)\right)$
3. $\exists x\colon \exists y\colon \forall z\colon \mathrm{likes}(x, y)\land \left((z\neq y)\implies \neg \mathrm{likes}(y, z)\right)$
4. $\forall x\colon \exists y\colon \forall z\colon \mathrm{likes}(x, y)\land \left((z\neq y)\implies \neg \mathrm{likes}(y, z)\right)$

Four domains:

1. The empty domain.
2. A world with one person, who likes herself.
3. A world with Yorick and Zelda, where Yorick likes Zelda, Zelda likes herself, and that's all.
4. A world with many people, including CJ (Catherine Zeta-Jones), JC (John Cusack), andJR (Julia Roberts). Everybody likes themselves;everybody likes JC; everybody likes CJ except JR;everybody likes JR except CJ and IB. Any others may or may not like each other, as you choose,subject to the preceding. (You may wish to sketch a graph of this $\mathrm{likes}$ relation, similar to Rosen Section 9.1 Figure 8.)

Determine the truth of all sixteen combinations of the four statements and four domains.

Translate the following into first-order logic:

Raspberry sherbet with hot fudge ( $\mathrm{rshf}$ ) is the tastiest dessert.

What is the intended domain for your formula? What is a relation which makes this statement true?One which makes it false?

Even allowing for ellision, the list of WaterWorld domain axioms is incomplete, in a sense. The game reports how many pirates exist in total, butthat global information is not reflected in the propositions or axioms. We had the same problem with the propositional logic domain axioms

1. First, assume we only use the default WaterWorld board size and number of pirates, i.e. , five. What additional axiom or axioms do we need?
2. Next, generalize your answer to model the program's ability to play the game with a different number of pirates.What problem do you encounter?

The puzzle game of Sudoku is played on a $9\times 9$ grid, where each square holds a number between 1 and 9.The positions of the numbers must obey constraints. Each row and each column has each of the 9 numbers.Each of the 9 non-overlapping $3\times 3$ square sub-grids has each of the 9 numbers.

Like WaterWorld, throughout the game, some of the values have not been discovered, although they are determined.You start with some numbers revealed, enough to guarantee that the rest of the board is uniquely determined by the constraints.Thus, like in WaterWorld, when deducing the value of another location, what has been revealed so far would serve aspremises in a proof.

Fortunately, there are the same number of rows, columns, subgrids, and values.So, our domain is $\{1, 2, 3, 4, 5, 6, 7, 8, 9\}$ .

To model the game, we will use the following relations:

• $\mathrm{value}(r, c, v)$ indicates that at row $r$ , column $c$ is the value $v$ .
• $v=w$ is the standard equality relation.
• $\mathrm{subgrid}(g, r, c)$ indicates that subgrid $g$ includes the location at row $r$ , column $c$ .

Provide domain axioms for Sudoku, and briefly explain them. These will model the row, column, and subgrid constraints.In addition, you should include constraints on our above relations, such as that each location holds one value.

Some of the first-order equivalences are redundant. For each of the following, prove the equivalence using the other equivalences.

1. $\forall x\colon \varphi \implies \theta \equiv \exists x\colon \varphi \implies \theta$

2. Assuming a non-empty domain, $\exists x\colon \theta \implies \varphi \equiv \theta \implies \exists x\colon \varphi$ .

We can characterize a prime number as a number $n$ satisfying $\forall q\colon \forall r\colon (qr=n)\implies (q=1)\lor (r=1)$ . Using the equivalences for first-order logic, show step-by-step that this is equivalent to the formula $\neg \exists q\colon \exists r\colon (qr=n)\land (q\neq 1)\land (r\neq 1)$ . Do not use any arithmetic equivalences.

A student claims that $\forall x\colon (A(x)\land B(x))\implies C(z)\equiv (\forall x\colon A(x)\land \forall x\colon B(x))\implies C(z)$ by the

distribution of quantifiers

Simplify the formula $\forall x\colon \forall y\colon \exists z\colon (A(x)\land B(y))\implies C(z)$ , so that the body of each quantifier contains only a single atomic formula involving that quantified variable. Provide reasoning for each step of your simplification.

[Practice problem $—$ solution provided.]

Prove that syllogisms are valid inferences. In other words, show that $\forall x\colon R(x)\implies S(x)\text{,}R(c)⊢S(c)$ .

What is wrong with the following

proof

Using the inference rules, formally prove the last part of the previous problem about ducks and such .

Give an inference rule proof of $\forall x\colon \mathrm{Fruit}(x)\implies \mathrm{hasMethod}(\text{tasty}, x)\text{,}\forall y\colon \mathrm{Apple}(y)\implies \mathrm{Fruit}(y)⊢\forall z\colon \mathrm{Apple}(z)\implies \mathrm{hasMethod}(\text{tasty}, z)$ .

1. Prove the following: $\exists x\colon P(x)\text{,}\forall y\colon P(y)\implies Q(y)⊢\exists z\colon Q(z)$
2. Your proof above used ∃Intro. Why can't we replace that step with the formula $\forall z\colon Q(z)$ with the justification

   ∀Intro

   ?
3. Describe an interpretation which satisfies the proof's premises, but does not satisfy $\forall z\colon Q(z)$ .