Version without JavaScript, read-only: workshops, quizzes and running code are not available here. Full version · Catalogue · Sign in

Exercise sheet 8

First-order logic: semantics and modelling

Evaluate a formula in a structure, build countermodels, translate natural language without ambiguity, and assess syllogisms. Chapter 8.

Solution
  1. True: 1 has 2, 2 has 3, 3 has 1.
  2. False: no $y$ is the image of every element. Same structure, same relation, different order of quantifiers, different value.
  3. For $x = 1$: $y = 2$, with $\lnot P(2)$, works. For $x = 3$: the only $y$ is 1, and $P(1)$ is true. False.
  4. False: $R$ contains no pair $(x, x)$.
Solution
  1. False. $D = \{1, 2\}$, $P = \{1\}$, $Q = \{2\}$: every element is $P$ or $Q$, but they are neither all $P$ nor all $Q$.
  2. False. Same structure: there is a $P$ and a $Q$, but no element is both.
  3. True: if a single $x_0$ is related to every $y$, then each $y$ has an $x$ related to it, namely $x_0$.
  4. False. $D = \{1, 2\}$, $R = \{(1, 1), (2, 2)\}$: each $y$ has an $x$ (itself), but no $x$ is related to both.
  5. True: $\lnot \forall x\, A \equiv \exists x\, \lnot A$, and $\lnot(P(x) \to Q(x)) \equiv P(x) \land \lnot Q(x)$.
Solution
  1. $\forall x\, (\mathit{Etud}(x) \to \mathit{Aime}(x, \mathit{log}))$. Not $\forall x\, (\mathit{Etud}(x) \land \ldots)$, which would say that everyone is a student.
  2. Most natural reading: each student has a subject they do not like, $\forall x\, (\mathit{Etud}(x) \to \exists y\, (\mathit{Mat}(y) \land \lnot \mathit{Aime}(x, y)))$.
  3. Three readings, and that is the point of the question: (a) the same as sentence 2, $\forall x\, \exists y$; (b) there is a subject that no student likes: $\exists y\, (\mathit{Mat}(y) \land \forall x\, (\mathit{Etud}(x) \to \lnot \mathit{Aime}(x, y)))$; (c) there is a subject that not all students like, in the sense of “not liked by everyone”: $\exists y\, (\mathit{Mat}(y) \land \lnot \forall x\, (\mathit{Etud}(x) \to \mathit{Aime}(x, y)))$. Any reading that is stated and correctly formalised is accepted; the sentence shows that the order of the quantifiers and the scope of the negation must be chosen.
  4. Chosen reading: they are better than the students who do not have a good mark in logic, $\forall x\, \forall y\, (\mathit{Etud}(x) \land \mathit{BN}(x, \mathit{log}) \land \mathit{Etud}(y) \land \lnot \mathit{BN}(y, \mathit{log}) \to \mathit{Meilleur}(x, y))$. The reading “better than all the other students” is a problem as soon as two students have a good mark: each would have to be better than the other.
Solution
  1. $\{\forall x\, (\mathit{Ap}(x) \to \mathit{Am}(x)),\; \forall x\, (\mathit{Ca}(x) \to \mathit{Ap}(x))\} \vDash \forall x\, (\mathit{Ca}(x) \to \mathit{Am}(x))$: valid. If $d$ is a Catarrhine, it is an Apodiform by the second hypothesis, hence an Amniote by the first. Note: the second hypothesis is false in biology (Catarrhini are primates, Apodiformes are birds), and the conclusion is true all the same. A valid argument guarantees the conclusion if the hypotheses are true; it says nothing otherwise.
  2. $\{\forall x\, (C(x) \to G(x)),\; \forall x\, (C(x) \to \mathit{Car}(x))\} \vDash \exists x\, (\mathit{Car}(x) \land G(x))$? Invalid in first-order logic. Countermodel: $D = \{1\}$, $C$, $G$ and $\mathit{Car}$ empty. Both hypotheses are true (there are no cats), the conclusion is false.
  3. That there is at least one cat: $\exists x\, C(x)$. If $c$ is a cat, it has claws and it is a carnivore. Sheet 10 proves it by resolution.