Version sans JavaScript, en lecture seule : les ateliers, les quiz et l’exécution du code n’y sont pas. Version complète · Catalogue · Se connecter

Feuille d'exercices 8

Premier ordre : sémantique et modélisation

Évaluer une formule dans une structure, construire des contre-modèles, traduire le français sans ambiguïté, et juger des syllogismes. Chapitre 8.

Corrigé
  1. Vraie : 1 a 2, 2 a 3, 3 a 1.
  2. Fausse : aucun $y$ n'est l'image de tous. Même structure, même relation, autre ordre des quantificateurs, autre valeur.
  3. Pour $x = 1$ : $y = 2$, avec $\lnot P(2)$, convient. Pour $x = 3$ : le seul $y$ est 1, et $P(1)$ est vraie. Fausse.
  4. Fausse : $R$ ne contient aucun couple $(x, x)$.
Corrigé
  1. Fausse. $D = \{1, 2\}$, $P = \{1\}$, $Q = \{2\}$ : chaque élément est $P$ ou $Q$, mais ni tous $P$, ni tous $Q$.
  2. Fausse. Même structure : il y a un $P$ et un $Q$, mais aucun élément n'est les deux.
  3. Vraie : si un même $x_0$ est en relation avec tous les $y$, alors chaque $y$ a un $x$ qui lui est relié, $x_0$.
  4. Fausse. $D = \{1, 2\}$, $R = \{(1, 1), (2, 2)\}$ : chaque $y$ a un $x$ (lui-même), mais aucun $x$ n'est relié aux deux.
  5. Vraie : $\lnot \forall x\, A \equiv \exists x\, \lnot A$, et $\lnot(P(x) \to Q(x)) \equiv P(x) \land \lnot Q(x)$.
Corrigé
  1. $\forall x\, (\mathit{Etud}(x) \to \mathit{Aime}(x, \mathit{log}))$. Pas $\forall x\, (\mathit{Etud}(x) \land \ldots)$, qui dirait que tout le monde est étudiant.
  2. Lecture la plus naturelle : chaque étudiant a une matière qu'il n'aime pas, $\forall x\, (\mathit{Etud}(x) \to \exists y\, (\mathit{Mat}(y) \land \lnot \mathit{Aime}(x, y)))$.
  3. Trois lectures, et c'est l'intérêt de la question : (a) la même que la phrase 2, $\forall x\, \exists y$ ; (b) il existe une matière qu'aucun étudiant n'aime : $\exists y\, (\mathit{Mat}(y) \land \forall x\, (\mathit{Etud}(x) \to \lnot \mathit{Aime}(x, y)))$ ; (c) il existe une matière que tous les étudiants n'aiment pas, au sens « pas aimée de tous » : $\exists y\, (\mathit{Mat}(y) \land \lnot \forall x\, (\mathit{Etud}(x) \to \mathit{Aime}(x, y)))$. On accepte toute lecture annoncée et correctement formalisée ; la phrase montre que l'ordre des quantificateurs et la portée de la négation doivent être choisis.
  4. Lecture retenue : ils sont meilleurs que les étudiants qui n'ont pas de bonne note en logique, $\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))$. La lecture « meilleurs que tous les autres étudiants » pose problème dès que deux étudiants ont une bonne note : chacun devrait être meilleur que l'autre.
Corrigé
  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))$ : correct. Si $d$ est Catarrhinien, il est Apodiforme par la seconde hypothèse, donc Amniote par la première. Remarque : la seconde hypothèse est fausse en biologie (les Catarrhiniens sont des primates, les Apodiformes des oiseaux), et la conclusion est vraie quand même. Un raisonnement correct garantit la conclusion si les hypothèses sont vraies ; il ne dit rien sinon.
  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))$ ? Incorrect au premier ordre. Contre-modèle : $D = \{1\}$, $C$, $G$ et $\mathit{Car}$ vides. Les deux hypothèses sont vraies (il n'y a aucun chat), la conclusion est fausse.
  3. Qu'il existe au moins un chat : $\exists x\, C(x)$. Si $c$ est un chat, il a des griffes et il est carnivore. La feuille 10 le démontre par résolution.