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
Support de cours · chapitre 8
Premier ordre : sémantique et modélisation
Donner un sens aux formules dans une structure, montrer qu'une formule n'en entraîne pas une autre par un contre-exemple, et traduire le français sans se tromper de quantificateur.
Les structures
Définition
Au calcul propositionnel, il suffisait de donner une valeur à chaque variable. Ici, il faut dire de quoi on parle. Une structure $\mathcal{M}$ pour une signature donne :
- un domaine $D$, ensemble non vide d'objets ;
- pour chaque constante $c$, un objet $c^{\mathcal{M}}$ de $D$ ;
- pour chaque symbole de fonction $f$ d'arité $n$, une fonction $f^{\mathcal{M}} : D^n \to D$ ;
- pour chaque symbole de prédicat $P$ d'arité $n$, l'ensemble $P^{\mathcal{M}} \subseteq D^n$ des $n$-uplets pour lesquels $P$ est vrai.
La valeur d'une formule
Pour évaluer une formule qui a des variables libres, on fixe aussi une affectation $\sigma$ : un objet de $D$ pour chaque variable. Les termes se calculent alors de bas en haut, et l'on définit « $A$ est vraie dans $\mathcal{M}$ pour $\sigma$ », noté $\mathcal{M}, \sigma \vDash A$ :
- $P(t_1, \ldots, t_n)$ est vraie si le $n$-uplet des valeurs des $t_i$ est dans $P^{\mathcal{M}}$ ;
- les connecteurs suivent leurs tables, comme au chapitre 2 ;
- $\forall x\, A$ est vraie si $A$ est vraie pour toute valeur de $x$ dans $D$ (les autres variables gardant leur valeur) ;
- $\exists x\, A$ est vraie si $A$ est vraie pour au moins une valeur de $x$ dans $D$.
Une formule close ne dépend pas de $\sigma$ : elle est vraie ou fausse dans $\mathcal{M}$, et l'on écrit $\mathcal{M} \vDash A$.
Les mêmes mots qu'au chapitre 2
On reprend les définitions en remplaçant « interprétation » par « structure » :
- $\mathcal{M}$ est un modèle d'une formule close $A$ si $\mathcal{M} \vDash A$ ;
- $A$ est valide si elle est vraie dans toute structure, satisfiable si elle a un modèle, insatisfiable sinon ;
- $\Sigma \vDash A$ si tout modèle de $\Sigma$ est un modèle de $A$.
Une différence de taille : il y a une infinité de structures, et des domaines infinis. Plus de table de vérité pour tout vérifier. Pour montrer que $\Sigma \not\vDash A$, on exhibe une structure (un contre-modèle) qui rend $\Sigma$ vraie et $A$ fausse, souvent sur un petit domaine. Pour montrer que $\Sigma \vDash A$, on raisonne sur une structure quelconque, ou l'on prouve (chapitres 6 et 10).
Quantificateurs et connecteurs
Les équivalences utiles
| Nom | Équivalence |
|---|---|
| Négation | $\lnot \forall x\, A \equiv \exists x\, \lnot A$ et $\lnot \exists x\, A \equiv \forall x\, \lnot A$ |
| Distribution | $\forall x\, (A \land B) \equiv \forall x\, A \land \forall x\, B$ et $\exists x\, (A \lor B) \equiv \exists x\, A \lor \exists x\, B$ |
| Même quantificateur | $\forall x\, \forall y\, A \equiv \forall y\, \forall x\, A$ et $\exists x\, \exists y\, A \equiv \exists y\, \exists x\, A$ |
« Ce n'est pas vrai que tous les cygnes sont blancs » veut bien dire « il existe un cygne qui n'est pas blanc ».
Ce qui ne marche pas
- $\forall x\, (A \lor B) \not\equiv \forall x\, A \lor \forall x\, B$. Tout entier est pair ou impair ; mais il n'est pas vrai que tout entier est pair, ni que tout entier est impair.
- $\exists x\, (A \land B) \not\equiv \exists x\, A \land \exists x\, B$. Il existe un entier pair et il existe un entier impair ; il n'existe pas d'entier pair et impair.
- $\forall x\, \exists y\, A \not\equiv \exists y\, \forall x\, A$. « Toute personne a une mère » n'est pas « quelqu'un est la mère de tout le monde ». On a seulement $\exists y\, \forall x\, A \vDash \forall x\, \exists y\, A$ : si un même $y$ convient à tous, alors chacun a un $y$ qui lui convient.
Traduire le français
Les quatre phrases types
| En français | En formule |
|---|---|
| Tous les A sont B | $\forall x\, (A(x) \to B(x))$ |
| Certains A sont B | $\exists x\, (A(x) \land B(x))$ |
| Aucun A n'est B | $\forall x\, (A(x) \to \lnot B(x))$, soit $\lnot \exists x\, (A(x) \land B(x))$ |
| Certains A ne sont pas B | $\exists x\, (A(x) \land \lnot B(x))$ |
L'ordre des quantificateurs et la portée de la négation
Le français laisse souvent l'ordre des quantificateurs implicite, et la négation flotter. « Tous les étudiants n'ont pas réussi » peut vouloir dire « aucun n'a réussi » ou « pas tous ont réussi ». La formule, elle, doit choisir. Quand une phrase est ambiguë, on écrit les lectures possibles, et l'on dit laquelle on retient.
Syllogismes et domaine non vide
« Tous les A sont B ; tous les C sont A ; donc tous les C sont B » est un raisonnement valide :
Soit $\mathcal{M}$ un modèle des deux hypothèses et $d$ un objet de $D$ tel que $C(d)$. Par la seconde, $A(d)$ ; par la première, $B(d)$.
Un raisonnement valide ne dit pas que ses conclusions sont vraies, seulement qu'elles le sont si les hypothèses le sont. Et certains syllogismes de la logique d'Aristote ne sont plus valides au premier ordre : ceux qui concluent « il existe » à partir de phrases « tous ». « Tous les A sont B » n'affirme pas qu'il existe des A : $\forall x\, (A(x) \to B(x))$ est vraie dans une structure où aucun objet n'est A.