Logique des prédicats, théorie des ensembles

Introduction

La logique des prédicats prolonge le raisonnement introduit en logique propositionnelle en permettant d’exprimer des propriétés paramétrées : les prédicats. Elle apparaît non seulement en mathématiques et en informatique, mais également en intelligence artificielle, en philosophie et en linguistique. À l'instar de la logique propositionnelle, c'est un langage doté de sa propre syntaxe, qui enrichit celui de la logique propositionnelle qui en devient un sous-langage, et la sémantique s’y greffe dans un second temps. La théorie ZF, quant à elle, fournit les objets sur lesquels ces propriétés peuvent opérer : les ensembles. Elle joue ainsi un rôle fondamental en informatique, où elle fournit les outils nécessaires pour représenter et raisonner rigoureusement sur des données structurées.

Dans cette perspective, la théorie ZF adjoint au langage prédicatif l'unique symbole non logique \(\in\), dont des axiomes régissent l'usage : c'est cette combinaison qui constitue la théorie des ensembles^♯ La théorie des ensembles élaborée par Zermelo et Fraenkel présentée ici n'a rien de canonique, d'autres théories des ensembles sont possibles.. Cette théorie n'explique pas ce que sont les ensembles – des sacs de billes sont bien plus explicites pour cela – mais en propose un codage systématique.

Autrement dit, la logique des prédicats fournit les mécanismes généraux permettant d’énoncer et d’articuler des propriétés : les objets mathématiques informels y sont reconstruits sous forme de structures manipulables. Les axiomes de la théorie des ensembles jouent le rôle de règles de construction qui déterminent ce qu'il est permis de construire, en excluant notamment les constructions à l'origine des paradoxes classiques. Cette analogie avec les langages de programmation n’est pas seulement heuristique, elle éclaire le fait que ce cadre fournit un support formel dans lequel l’activité mathématique peut s’exprimer, se développer et se vérifier, en permettant d’écrire, de transformer et de contrôler des expressions symboliques selon des règles précises.

La médiathèque

Vous devez développer un moteur de recherche pour une médiathèque numérique. Un usager souhaite trouver tous les documents de la médiathèque qui parlent de robot(s) ou de chat(s), mais qui ne mentionnent pas l'intelligence artificielle. Le corpus* Ce corpus n'est pas réaliste. Il a été réduit ici à une poignée d'entrées afin de pouvoir être analysé à la main et de comprendre les mécanismes que nous mettrons en œuvre pour répondre à cette question. La réalité pour ce type de recherche serait plus proche de dizaines de milliers voire de millions de documents. de cette médiathèque est le suivant :

• \( d_1 \) : Le chat mécanique
• \( d_2 \) : Robots et intelligence artificielle
• \( d_3 \) : Chats et robots en bande dessinée
• \( d_4 \) : Intelligence artificielle et animaux
• \( d_5 \) : Robots domestiques
• \( d_6 \) : L’intelligence artificielle expliquée aux enfants

Avant même de concevoir un algorithme capable de répondre automatiquement à cette requête, et plus généralement à toute requête de ce type, une question se pose.

Question :

Nous y reviendrons à la fin du chapitre en proposant une formalisation rigoureuse et complète de ce problème une fois étudiés les nouveaux concepts introduits : prédicats et ensembles.

Théorie mathématique

Axiomes et démonstrations

Une théorie ma­thé­ma­ti­que est un ensemble d'affirmations, les assertions ou propositions vraies. Une assertion peut être admise, auquel cas on parle d'axiome ou de postulat – c'est in­con­tour­na­ble, on ne peut pas créer une théorie ex nihilo, – ou être obtenue à partir d'assertions préétablies, dont les axiomes, et d'un ensemble de règles de déduction logique (comme le modus ponens par exemple).

Une fois fixés les axiomes et les règles déductives, une théorie mathématique est parfaitement déterminée, faire des mathématiques ne consiste qu'à explorer l'arbre des déductions possibles dans cette théorie si l'on caricature la discipline en un simple jeu formel d'assemblage, comme un jeu lego^® ou une partie d'échecs. Cependant, la pratique humaine ne se limite pas à explorer mécaniquement tous les assemblages/coups possibles, elle fait appel à l'intuition, à la créativité et à la stratégie. La communauté mathématique ne se contente pas d'appliquer des règles, elle invente de nouvelles méthodes, formule des conjectures et choisit des pistes prometteuses dans l'arbre des possibles. Mais plus fondamentalement encore, elle n'est pas confinée dans un champ clôturé par un système fixé une fois pour toutes – comme la théorie ZF introduite ici –, elle s'interroge également sur ses propres structures logiques et la nature de ses fondements.

La logique des prédicats enrichit la logique pro­po­si­tion­nel­le en fournissant de nouveaux mécanismes – variables, prédicats, quantificateurs – pour construire des énoncés plus expressifs. Ce pouvoir d'expression n'est pas circonscrit à un cadre purement syntaxique : il permet d'appréhender plus fidèlement le monde qui nous entoure, chaque fois qu'il s'agit de décrire des objets, leurs propriétés et les relations qui les lient. Ce langage n'entre donc pas en concurrence avec celui de la logique propositionnelle, il l'englobe. Une théorie particulière, comme celle des ensembles que nous étudierons plus loin, viendra compléter ce langage logique de ses propres symboles.

Cette approche formelle, voire kafkaïenne, des mathématiques ne doit pas faire perdre de vue qu'elles seraient im­pra­ti­ca­bles ou pour le moins considérablement entravées si l'on s'in­ter­di­sait l'usage de la langue naturelle pour s'exprimer. Répétons-le, faire des mathématiques ne peut pas se résumer à la construction d'énoncés formels qui respectent une syntaxe stricte, à la manière d'un langage de programmation. Parler d'un entier naturel \(n\) pair n'est pas moins rigoureux que d'écrire, pour un entier \(n\) fixé :

La proposition \(\exists k\ (k\in\N) \land (n=2k)\) est en revanche bien plus efficace que sa version en langue naturelle^☆Cette proposition mobilise des ingrédients que le lecteur a certainement déjà croisés dans d'autres cours, sans nécessairement savoir à quelle strate du langage chacun appartenait : un prédicat, une quantification, et le symbole \(\in\) qui, on le verra, n'appartient pas à la logique elle-même mais au langage particulier de la théorie des ensembles. C'est un avant-goût typique de l'articulation entre prédicats et ensembles que ce chapitre se propose de rendre moins nébuleux. s'il faut démontrer que le carré d'un entier pair est pair : en supposant \(n\) pair, d'après \((\ref{eq:entierpair})\), on dispose d'un entier naturel \(k\) tel que \(n=2k\), et on démontre successivement que les trois implications suivantes sont vraies grâce aux propriétés des opérations arithmétiques :

Et la transitivité de l'implication nous donne

L'égalité \(n=2k\) étant vraie par choix de \(k\), la règle du modus ponens appliquée à l'implication \((\ref{eq:endproof})\) nous donne \(n^2=2{\color{#48F}K}\) avec \({\color{#48F}K}:={\color{#48F}2k^2}\in\N\) : la proposition \(\exists K\ (K\in\N)\land(n^2=2K)\) est vraie, autrement dit \(n^2\) est pair. Et comme l'entier pair \(n\) a été choisi quelconque, le résultat vaut pour tout entier pair : le carré d'un entier pair est pair.

On rappelle la définition introduite au chapitre précédent :

Une nouvelle assertion obtenue par déduction est appelée théorème, ou lemme si le résultat est une étape importante pour l'obtention d'un théorème, ou parfois pro­po­si­tion­ (au sens informel donc), ou encore corollaire lorsqu'il s'agit d'une con­sé­quen­ce directe d'un théorème. Stricto sensu, chaque proposition intermédiaire obtenue dans une démonstration constitue un théorème, mais nous ne mettons en évidence que celles qui nous pa­rais­sent importantes, les autres restent dans l'anonymat.

Explication ou preuve ?

Le rôle premier d'une démonstration est de valider une proposition. Elle agit comme un processus de certification qui n'explique pas nécessairement pourquoi elle est vraie, mais comment. En général, on débute par la compréhension du résultat, même parcellaire, puis on tente de le valider formellement, rarement l'inverse. Parfois l'explication est transposable en preuve, en particulier quand il s'agit d'un processus constructif.

Ce processus formel de certification d'un résultat peut être particulièrement abscons. Il est donc essentiel de trouver des arguments, même informels, pour comprendre pourquoi une proposition est vraie. C'est ce qui fait polémique (au dernier trimestre 2026) entre le travail des mathématiciens sur les preuves et celui des llm auxquels on demande d'inférer des certificats comestibles pour des assistants de preuve… De la même manière, un algorithme s'adresse à un être humain et explicite comment obtenir un résultat, alors que le code exécutable qui le réalise n'est plus qu'une suc­ces­sion d'instructions parfaitement obscures. Le lecteur pourra s'en convaincre en lisant celui de n'importe quel programme une fois compilé.

Illustrons ça avec le célèbre théorème de Pythagore qui admet une explication parfaitement convaincante :

Les deux grands carrés à gauche et à droite dans la figure ci-dessus ont des côtés de même longueur \(a+b\). On recompose le premier carré en déplaçant les \(4\) triangles rouges qu'il contient de manière à former les deux rectangles de côtés de mesure \(a\) et \(b\) qui apparaissent dans le second carré. On en déduit que les aires bleues à gauche et à droite sont égales :

La dé­mons­tra­tion géométrique dans la figure ci-dessus est informelle mais justifie de manière compréhensible le résultat. Une preuve formelle utiliserait, par exemple, les outils de la géométrie cartésienne comme les vecteurs et le produit scalaire pour établir le résultat de manière algébrique (déplier la preuve sous le théorème).

Nous avons déjà mentionné trois méthodes communes qui sont utilisées pour faire une dé­mons­tra­tion :

1. Par modus ponens. Si \(P\) et \(Q\) sont deux propositions telles que \(P\) est vraie et \(P\Rightarrow Q\) est vraie, on en déduit que la proposition \(Q\) est vraie ;
2. Par modus tollens (contraposition). Si \(P\) et \(Q\) sont deux propositions telles que \(P\Rightarrow Q\) est vraie et que \(\neg Q\) est vraie, on en déduit que la proposition \(\neg P\) est vraie ;
3. Par l'absurde. Pour démontrer qu'une proposition \(P\) est vraie, on suppose que la proposition \(\neg P\) est vraie, i.e. \(\neg P\) est un nouvel axiome de la théorie, puis on cherche une proposition \(Q\) telle que la proposition \(Q\land \neg Q\) est vraie, prouvant ainsi que cette théorie est contradictoire d'après le tiers exclu ce qui invalide la nouvelle théorie et disqualifie cet axiome.

Nous verrons plus loin dans ce chapitre, puis au chapitre Combinatoire, deux autres méthodes de dé­mons­tra­tion :

4. Par disjonction de cas.
5. Par ré­cur­ren­ce.

Logique des prédicats

Un canevas pour des langages

Le mot prédicat n'est pas une invention de logiciens : c'est, depuis 2016, un terme officiel du programme scolaire français, enseigné dès le CM1 : une phrase s'y décompose en un sujet – ce dont on parle – et un prédicat – ce que l'on en dit^*Le prédicat grammatical se compose le plus souvent d'un verbe et de ses compléments..

Ce que la logique en retient est très proche, à un détail près : en grammaire, le sujet et le complément sont fixés, si bien qu'une phrase complète est d'emblée vraie ou fausse, c'est donc une proposition au sens de la logique propositionnelle^†Manifestement les grammairiens communiquent peu avec les logiciens.. En logique des prédicats, on va au contraire dépouiller l'articulation elle-même de tous les termes qu'elle relie : le prédicat n'est plus que la relation nue et chacun des termes qu'elle relie, sujet comme complément, reste à l'extérieur, comme autant de places vides. Par exemple :

•    a réalisé Pulp Fiction
  vrai pour Quentin Tarantino, faux pour Steven Spielberg ;
• Tarantino a réalisé   
  vrai pour Pulp Fiction, faux pour E.T. ;
•    est journaliste
  vrai pour Tintin, faux pour Obélix^‡On pourrait tout aussi bien voir ici le prédicat unaire est journaliste. Le découpage entre ce qui relève du prédicat et ce qui relève des places est un choix de modélisation, pas une donnée de la phrase. ;
•    joue de la guitare dans   
  vrai pour le couple (Wolfgang Van Halen, Mammoth), faux pour le couple (Wolfgang Amadeus Mozart, La flûte enchantée).

Quel que soit le nombre de places laissées ouvertes, tant qu'elles ne sont pas toutes remplies, on ne peut pas attribuer une valeur de vérité à ces phrases : c'est précisément ce mécanisme – une relation dépouillée des termes qu'elle articule, qui ne devient une proposition qu'une fois tous ces termes fournis – que la logique des prédicats va formaliser.

Comme pour la logique propositionnelle, il faut se donner un lexique de symboles avant de pouvoir composer des prédicats. On hérite sans changement des constantes \(\top\) et \(\bot\), des connecteurs logiques \(\neg,\land,\lor,\Rightarrow,\Leftrightarrow,\ldots\) et des parenthèses. Les variables propositionnelles, en revanche, ne sont pas reconduites telles quelles : on verra plus loin qu'elles reviennent sous la forme d'un cas particulier d'une nouvelle catégorie de symboles. À ce lexique s'ajoutent donc quatre nouvelles catégories :

1. Des variables individuelles : des symboles désignant un individu quelconque – un objet –, à ne pas confondre avec une variable propositionnelle, qui désigne directement une proposition. On les prend généralement dans les dernières lettres de l'alphabet latin, \(x\), \(y\), \(z\ldots\)
2. Des symboles prédicatifs : des symboles arbitraires, généralement pris dans les premières lettres de l'alphabet latin en majuscule, \(P\), \(Q\), \(R\ldots\), chacun muni d'une arité fixée.
3. Le symbole d'égalité \(=\).
4. Les quantificateurs \(\forall\) et \(\exists\), dont on précisera le sens plus loin.

Ce lexique, comme celui de la logique propositionnelle, ne dépend d'aucune théorie : aucun de ces symboles ne présuppose un domaine particulier d'objets ni une théorie mathématique donnée. C'est précisément ce qui permettra, plus loin, à une théorie particulière comme la théorie ZF, de l'enrichir de son propre vo­ca­bu­lai­re.

Nous sommes à présent en mesure de donner une définition formelle d'un prédicat, à partir du lexique qu'on vient de fixer. La notion d'arité nous est déjà familière : de même qu'un con­nec­teur \(q\)-aire relie \(q\) propositions, un symbole prédicatif d'arité \(q\) est relié à \(q\) variables individuelles entre parenthèses, généralement notées de manière préfixe : \(P(x,y)\) pour un symbole \(P\) d'arité \(2\), \(R(x,y,z)\) pour un symbole \(R\) d'arité \(3\), et ainsi de suite – on parle alors de prédicat \(q\)-aire.

L'égalité a, parmi les symboles prédicatifs, un statut particulier : contrairement à \(P,Q,R,\ldots\), dont le sens reste à la charge de chaque théorie particulière, elle a une interprétation fixée une fois pour toutes, commune à toute théorie du premier ordre : la proposition \(x\) est égal à \(y\), codée \begin{equation} x=y \end{equation} exprime que les expressions \(x\) et \(y\) désignent le même objet.

Si \(x\) et \(y\) satisfont \(x=y\), cela entraîne qu'ils sont synonymes, ou, pour reprendre un vocabulaire familier à l'informaticien, des alias l'un de l'autre : deux étiquettes différentes désignant le même objet. On peut donc les substituer dans n'importe quelle expression ma­thé­ma­ti­que sans modifier son interprétation logique.

Les quantificateurs universels et existentiels

Précisons à présent le sens des deux quantificateurs annoncés dans notre lexique, qui permettent de construire des propositions à l'aide d'un prédicat \(P(x)\) et des règles syntaxiques pour les composer :

1. Le quantificateur universel \(\forall\), qui se lit quel que soit ou pour tout, et s'utilise dans l'ex­pres­sion \begin{equation} \label{eq:universel0} \forall x\ {\color{#08F}P(x)} \end{equation} qui code la proposition Pour tout \(x\), la proposition \(P(x)\) est vraie.
2. Le quan­ti­fi­ca­teur existentiel \(\exists\) qui se lit il existe, et s'utilise dans l'expression \begin{equation} \label{eq:existentiel0} \exists x\ {\color{#F80}P(x)} \end{equation} qui code la proposition Il existe \(x\) tel que la proposition \(P(x)\) est vraie. Notons qu'un tel élément n'est pas nécessairement unique.

Quand un quan­ti­fi­ca­teur précède une variable \(x\), on dit qu'elle est quantifiée ou qu'il s'agit d'une variable liée (sous-entendu à un quantificateur). On dit également va­ria­ble muette ou anonyme : elle peut être remplacée partout dans l'expression par n'im­por­te quelle autre variable qui n'y est pas présente sans en chan­ger le sens. On peut s'en convaincre en remplaçant \(x\) par \(y\) dans les deux expressions \((\ref{eq:universel0})\) et \((\ref{eq:existentiel0})\) : ces deux expressions sont donc bien des propositions et non des prédicats. Quand une variable n'est pas quantifiée elle est dite libre. Quand toutes les variables d'une formule de la logique des prédicats sont quantifiées, la formule est dite close.

Théorie ZF

La théorie des ensembles de Cantor

La théorie ma­thé­ma­ti­que dans laquelle nous discourons, tout au moins dans ce cours, est une axiomatisation de la théorie des ensembles. Cette théorie a été développée par G. Cantor^*Mathématicien allemand de la fin du 19ème siècle. à la fin du 19ème siècle, puis axiomatisée par les mathématiciens allemands E. Zermelo et A. Fraenkel pour en éliminer les paradoxes. Elle est l'aboutissement de ques­tion­ne­ments philosophiques sur la nature du rai­son­ne­ment et de la construction des ensembles qui ont culminé à la charnière du xix-ème et du xx-ème siècle. Bien entendu, les mathématiciens n'ont pas attendu le xx-ème siècle et cette théorie pour faire des démonstrations. L'apparition de con­tra­dic­tions et de paradoxes, conséquence de manipulations sans contraintes des ensembles infinis, a mis en péril l'édifice mathématique et a nécessité d'en fixer les règles. Pour faire une métaphore routière, conduire sur les routes sans fixer quelques règles de circulation peut générer des accidents.

Cette théorie identifie tous les objets manipulés à des ensembles, nombres, fonctions, relations, vecteurs, etc. Elle fournit un nombre limité d'axiomes et de règles pour justifier leur existence ou pour les construire. Elle n'est pas la théorie des ensembles, au sens défini singulier, bien que nous employions souvent cette expression, mais plutôt un codage (au sens informatique du terme) particulier et cohérent des objets qui étaient déjà utilisés en ma­thé­ma­ti­ques. La plupart des axiomes expriment des propriétés qui semblent évidentes pour les ensembles tels que nous les concevons naïvement. Ils précisent dans quel cadre nous pouvons construire de nouveaux ensembles à partir de ceux que nous connaissons déjà.

La raison de cette théorie n'est pas d'expliquer ce qu'est un ensemble, mais d'établir des règles de cons­truc­tion afin d'éviter des paradoxes. Nous ne ferons qu'effleurer ces questions délicates dans ce cours de li­cen­ce, elles seront à nouveau abordées dans un cours de calculabilité de mas­ter d'in­for­ma­ti­que. Dans la suite nous ne présenterons que les axiomes que nous utilisons in­ten­si­ve­ment, ils il­lus­trent la démarche qui sous-tend cette théorie et dont la dimension systématique est proche de la théorie des langages en informatique.

Plus prosaïquement, nous concevons un en­sem­ble comme une collection d'objets, comme un re­grou­pe­ment, à la manière d'un sac de billes. Cette vision informelle est non seulement légitime mais in­dis­pen­sa­ble pour élaborer nos rai­son­ne­ments, il est donc exclu de la sacrifier sur l'autel du formalisme, elle est suffisante pour la licence. C'est celle de Georg Cantor :

Les deux mots clés dans cette définition sont les mots définis et discernables. Le premier signifie que l'on doit être en mesure de dire pour tout objet s'il est un élément ou non de l'ensemble \(X\). Le second signifie que l'on doit être en mesure de distinguer les éléments d'un ensemble. Ces deux conditions expriment qu'un ensemble est entièrement caractérisé par les éléments qu'il contient.

La condition définis fait émerger un symbole propre au langage de la théorie des ensembles : la relation d'appartenance \(\in\). La proposition \(x\) est un élément de \(X\) est codée par l'expression \begin{equation} x\in X. \end{equation} Quant à la condition discernables, elle s'appuie sur l'égalité \(=\), dont on a déjà vu qu'il s'agit d'un symbole logique, indépendant de toute théorie particulière.

Rien n'empêche un ensemble d'être lui-même l'élément d'un autre ensemble.

D'autres notations sont spécifiques à la théorie des ensembles, en particulier l'accolade ouv­ran­te { et l'accolade fermante }. Quand le nombre d'éléments qui caractérisent un ensemble \(X\) est fini – la définition formelle de la finitude dans le cadre de cette théorie sera définie plus tard –, on peut représenter cet ensemble par la liste de ses éléments délimitée par ces deux sym­boles respectivement. Par exemple : \begin{align} \label{eq:ens4} X=\{1,f,3,x\}. \end{align} dont les éléments sont : \(1\), \(f\), \(3\) et \(x\). Cette écriture de l'ensemble \(X\) est dite en extension.

Nous utiliserons deux notations pour l'égalité, le symbole simple \(=\) et le symbole composé \(:=\). Ils désignent la même relation d'égalité : les deux points qui précèdent l'égalité ont un simple rôle sémantique dans le métalangage mathématique. Ils signalent au lecteur que le terme à gauche est défini par celui de droite, généralement au moyen d'une construction mathématique. L'égalité qui en découle est alors une conséquence de cette définition. Ainsi, on distinguera l'assertion \(3=1+2\) de la définition \(X:=\{a,b,c\}\). Cette dernière signifie que \(X\) est l'ensemble constitué des trois objets \(a\), \(b\) et \(c\), et permet alors de former la nouvelle assertion \(X=\{a,b,c\}\). Cette notation est particulièrement commode et a également été popularisée en informatique par des langages comme le Pascal, qui utilisent \(:=\) pour distinguer l'affectation de l'égalité.

Prédicats et ensembles

Une formule du calcul des prédicats, comme \(\forall x\ \exists y\ P(x,y)\), n'est jusqu'ici qu'un gabarit : de la syntaxe pure, doublement vide de sens. Elle comporte d'une part des symboles prédicatifs \(P,Q,R\ldots\) anonymes, dont on ignore quelle relation ils désignent, et d'autre part des places – ses variables – dont on ignore quels objets viendront les occuper. Dans les exemples du début de la section précédente, le prédicat (a réalisé) était fixé et seules les places étaient vides ; ici, même le prédicat est anonyme. La théorie ZF comble le premier vide : elle substitue aux symboles anonymes son unique symbole \(\in\), et le gabarit \(\forall x\ \exists y\ P(x,y)\) devient la formule \(\forall x\ \exists y\ x\in y\), qui parle désormais d'appartenance. Les places, elles, restent ouvertes : ce sont des ensembles qui viendront les occuper.

Le prédicat \(x\in\{1,2\}\), par exemple, ressemble à une instance de la règle \(2\) : le symbole \(\in\), en notation infixe, appliqué à \(x\) et à \(\{1,2\}\). Ce n'en est pas tout à fait une, car \(\{1,2\}\) n'est pas une variable mais une abréviation. Il en va de même de \(\varnothing\), \(1\), \(2\), \(\subseteq\), \(\cup\), \(\leqslant\) et de la plupart des écritures mathématiques usuelles : chacune pourrait en principe être dépliée en une formule n'utilisant que \(\in\) et \(=\), comme un programme se compile en code machine. Le résultat serait parfaitement illisible et nous ne le ferons jamais : il suffit de savoir que c'est possible.

On conserve la même terminologie que pour la logique propositionnelle quand on fixe la valeur d'une ou plusieurs variables d'un prédicat, il s'agit encore d'une interprétation. Notons que si une seule variable a été interprétée dans un prédicat à \(q\) variables, la nouvelle expression est un prédicat à \(q-1\) variables.

Cette définition peut sembler déroutante car naïvement nous envisageons toujours une collection d'objets comme un ensemble, que ces objets vérifient ou non un prédicat. Elle a pour objet de distinguer les prédicats qui définissent des ensembles des autres, cette fois formellement.

Les axiomes de la théorie des ensembles élaborée par Zermelo et Fraenkel fournissent une famille de prédicats col­lec­ti­vi­sants suf­fi­sam­ment riche pour pouvoir coder tous les objets dont les ma­thé­ma­ti­ciens ont besoin, mais contrôlent la construction de nouveaux ensembles afin de ne pas créer de mons­tres gé­né­rant des paradoxes.

De manière imagée, les axiomes et le langage de cette théorie s'apparentent à un jeu de construction dont les pièces détachées et les règles d'assemblage permettent de construire de nouveaux objets dont on peut étudier les propriétés. Pour valider cette boite de jeu, il fallait être capable de reconstruire*plus précisément coder au sens informatique du terme les objets utilisés depuis des lustres par les mathématiciens et montrer que le prix à payer pour cette restriction de mouvement constituait un gage de sécurité.

A contrario, la théorie ne fournit pas explicitement de prédicats non-collectivisants. Devraient être disqualifiés tous ceux dont les en­sem­bles associés, s'ils existaient, permettraient d'en déduire une contradiction. Cantor ne faisait pas ce distinguo et son principe d'abstraction affirmait que tout prédicat définissait un ensemble, ce que l'on traduirait dans le langage de la théorie ZF, par tout prédicat est collectivisant.

L'application du principe de Cantor, écarté dans la théorie ZF, génère des pa­ra­do­xes. Le plus célèbre d'entre eux est probablement le paradoxe de Russell * Bertrand Russell était un phi­lo­so­phe et ma­thé­ma­ti­cien ang­lais et l'un des fon­da­teurs de la lo­gi­que con­tem­po­rai­ne. Il a dé­cou­vert ce pa­ra­do­xe en 1901. : considérons le prédicat \(P(x)\) suivant :

Supposons que \(P(x)\) soit collectivisant en \(x\). Alors l'ensemble en compréhension de \(P\) existe :

D'après la définition \((\ref{eq:Russell})\) de l'ensemble \(X\), il est clair que si \(X\in X\) alors \(X\) satisfait \(\neg(X\in X)\). En notant \(A\) la proposition \(X\in X\), on vient donc de montrer que \[(A\then\neg A)\equiv (\neg A\lor \neg A)\equiv \neg A.\] Bien sûr, si \(\neg(X \in X)\), alors l'ensemble \(X\) satisfait le prédicat \((\ref{eq:predicatRussell})\) et doit donc appartenir à \(X\), on a donc montré que \[(\neg A\then A)\equiv (A\lor A)\equiv A.\] On a donc prouvé que \(A\land \neg A\) ce qui est contradictoire.

Quantificateurs et ensembles

En pratique, la variable \(x\) décrit généralement des éléments d'un ensemble fixé \(X\), on utilise alors très souvent les quantifications bornées suivantes : \begin{align} \label{eq:universel} \forall x\in X\ \ &Q(x)\ \ \equiv\ \ \forall x\ {\color{#08F}(x\in X)\then Q(x)},\\ \label{eq:existentiel} \exists x\in X\ \ &Q(x)\ \ \equiv\ \ \exists x\ {\color{#F80}(x\in X)\land Q(x)}. \end{align}

La première expression a été construite sur la base de l'expression \((\ref{eq:universel0})\) avec le prédicat \({\color{#08F}(x\in X)\then Q(x)}\), la seconde sur la base de l'expression \((\ref{eq:existentiel0})\) avec le prédicat \({\color{#F80}(x\in X)\land Q(x)}\). Comme leurs homologues non bornées, ce sont bien des propositions et non des prédicats : la variable \(x\) y reste muette, au sens déjà précisé.

Par exemple la proposition \(\color{#08F}\forall x\in\{a,b,c\}\ P(x)\) résume bien la conjonction des trois propositions \[ {\color{#08F}\forall x\in\{a,b,c\}\ P(x)}\;\equiv\; {\color{#08F}P(a)\land P(b)\land P(c)}. \] et la proposition \(\color{#F80}\exists x\in\{1,2,3,4\}\ Q(x)\) résume la disjonction des quatre propositions \[ {\color{#F80}\exists x\in\{1,2,3,4\}\ Q(x)}\;\equiv\; {\color{#F80} Q(1)\lor Q(2)\lor Q(3)\lor Q(4)}. \] Mais la puissance de ces quantificateurs ne se limite pas à résumer un nombre fini de propositions, elles permettent surtout de s'affranchir de la finitude de \(X\) comme dans l'expression \(\forall x\in\R\).

Pour démontrer une proposition du type \(\forall x\in X\ \ P(x)\), on se donne un élément \(x\) quelconque de l'en­sem­ble \(X\) et on montre que \(P(x)\) est vraie. Comme \(x\) est quelconque, il incarne n'importe quel élé­ment de \(X\). Ainsi si la proposition \(P(x)\) est vraie, elle l'est aussi pour tout autre élément de \(X\).

Pour démontrer une proposition du type \(\exists x\in X\ \ P(x)\), il faut exhiber un élément particulier \(x\) de l'en­sem­ble \(X\) tel que \(P(x)\) soit vraie, il peut d'ailleurs en exister plusieurs.

Il arrive souvent que l'on ait besoin d'exprimer l'existence d'un objet et que celui-ci est unique. On rajoute alors un point d'exclamation à la suite du quantificateur existentiel pour le signifier. La proposition \(\exists!\, x\in X\ P(x)\) est logiquement équivalente à la proposition \begin{equation} \underbrace{(\exists x\in X\ \ P(x))}_{\text{existence}}\;\land\;\underbrace{\Big(\forall x\in X\ \forall y\in X\ \ \big((P(x)\land P(y))\Rightarrow (x=y)\big)\Big)}_{\text{unicité}}. \end{equation} Le terme gauche de cette conjonction code l'existence de \(x\) et le terme droit son unicité en exprimant sous forme contraposée que deux éléments distincts \(x\) et \(y\) de l'ensemble \(X\) ne peu­vent simultanément satisfaire le prédicat : \[(x\neq y)\then \neg(P(x)\land P(y)).\]

La négation des deux expressions \((\ref{eq:universel0})\) et \((\ref{eq:existentiel0})\) est conforme à celle des énoncés cor­res­pon­dan­ts en langue na­tu­rel­le :

Interprétations des formules prédicatives

Les langages mathématiques étant des supports pour objectiver la pensée, il est important de savoir interpréter ces nouvelles expressions et de réaliser que les manipulations logiques sont cohérentes par rapport à ces interprétations.

Illustrons l'équivalence logique \((\ref{eq:negA})\) en langue naturelle en supposant que \(X\) désigne l'ensemble des étudiants qui suivent ce cours de mathématiques et \(P(x)\) le prédicat dont l'interprétation est L'étudiant \(x\) comprend le cours. La proposition \({\color{orange}\forall x\in X\ P(x)}\) dans le membre gauche de l'équivalence logique \((\ref{eq:negA})\) s'interprète donc :

Et sa négation pourrait être interprétée par Il existe un étudiant qui suit ce cours et ne le comprend pas plutôt que Tous les étudiants qui suivent ce cours ne le comprennent pas qui peut prêter à interprétation, veut-on signifier qu'aucun étudiant ne comprend le cours ou que certains étudiants ne le comprennent pas ? Et l'ambiguïté des langues na­tu­rel­les ne s'arrête pas là, le mot un induit souvent l'unicité, il est donc préférable d'exprimer la négation par

Ainsi, quand on veut démontrer qu'une pro­po­si­tion du type \(\color{orange}\forall x\in X\ \ P(x)\) est fausse, autrement dit que sa négation est vraie, il suffit d'exhiber un élément \(\color{green}x\in X\) tel que \(\color{green}\neg P(x)\), qu'on appelle un contre-exemple.

Étudions à présent l'équivalence logique \((\ref{eq:negE})\). En supposant que \(X\) désigne cette fois l'ensemble des éléphants, et que le prédicat \(P(x)\) soit L'éléphant \(x\) est rose, alors la proposition \({\color{#F6B}\exists x\in X\ P(x)}\) qui apparaît dans le membre gauche de l'équivalence logique \((\ref{eq:negE})\) s'interprète :

Et sa négation pourrait être la proposition il n'existe pas d'éléphants roses ou encore tous les éléphants ne sont pas roses, mais cette dernière laisse entendre que certains peuvent l'être mais pas tous ! Ma­thé­ma­ti­quement, on dirait quel que soit l'éléphant, celui-ci n'est pas rose ce qui s'exprime plus élégamment sous la forme

Ordre des quantificateurs

Les difficultés commencent quand on manipule des prédicats de plu­sieurs variables et que l'on quantifie tout ou partie de leurs variables. Par exemple, un prédicat \(P(x,y)\) dont la variable \(x\) a été quantifiée est un prédicat de la variable \(y\). Considérons le prédicat \(P(x,y)\) suivant défini sur deux variables réelles \(x\) et \(y\) : \[x^2-y= 1\] On peut définir le prédicat \(Q(x)\) de la variable \(x\) suivant \[\exists y\in\R\quad x^2-y= 1\] et la proposition \(\forall x\in\R\ Q(x)\), soit \[\forall x\in\R\ (\exists y\in\R\quad x^2-y = 1)\] que l'on écrit souvent en omettant les parenthèses : \begin{equation}\label{eq:AE} \forall x\in\R\ \exists y\in\R\quad x^2-y = 1. \end{equation} Cette proposition est vraie. En effet, quelle que soit la valeur du nombre réel \(x\), le nombre réel \(y\) défini par \(y:=x^2-1\) satisfait l'équation de la proposition \((\ref{eq:AE})\). Échangeons à présent les deux quantificateurs et étudions la signification de cette nouvelle proposition : \[\exists y\in\R\ \forall x\in\R\quad x^2-y = 1.\] Replaçons tout d'abord les parenthèses (ce n'est qu'une fois que ces écritures seront familières que l'on pourra s'en dispenser) : \begin{equation}\label{eq:EA} \exists y\in\R\ (\forall x\in\R\quad x^2-y = 1). \end{equation} Montrons que cette nouvelle proposition est fausse. Notons \(y_0\) un nombre réel \(y\) tel que tout nombre réel \(x\) satisfait l'égalité de la proposition \((\ref{eq:EA})\). Si tous les nombres réels \(x\) satisfont l'égalité \((\ref{eq:EA})\) pour \(y:=y_0\), c'est le cas en particulier des nombres réels \(0\) et \(1\). On peut donc affirmer que : \begin{align*} 0^2-y_0&=1^2-y_0 \end{align*} proposition équivalente à la proposition (prouvez le) : \begin{align*} 0=1 \end{align*} qui est fausse. Nous avons exhibé là un contre-exemple.

Il faut donc prendre garde à l'ordre des quantificateurs et en particulier replacer les parenthèses absentes si l'on doit pro­pager une négation comme \((\ref{eq:negA})\) ou \((\ref{eq:negE})\) pour des prédicats à plu­sieurs variables.

Poursuivons nos investigations sur l'ordre des quantificateurs en considérant l'énoncé suivant : \(f\) est une application constante de l'ensemble des réels dans lui-même*Nous ne verrons la définition d'une application qu'au chapitre Relations, applications, mais l'étudiant a déjà été familiarisé avec cet outil ma­thé­ma­ti­que en cours d'analyse. Notons simplement que l'ensemble des applications d'un ensemble \(X\) dans un ensemble \(Y\) est noté \(Y^X\).. On peut traduire la constance de l'application en logique des prédicats et reformuler cet énoncé :

L'application \(f\in\R^{\R}\) vérifie la proposition \begin{equation} \label{eq:marmite0} \forall (x_1,x_2)\in\R\times\R\ \ f(x_1)=f(x_2) \end{equation}

On peut écrire une proposition équivalente à la proposition \((\ref{eq:marmite0})\) : \begin{equation} \label{eq:marmite} {\color{#88F}\exists c\in\R}\ \ {\color{orange}\forall x\in\R}\quad f(x)=c \end{equation}

qui n'est pas logiquement équivalente à la proposition \begin{equation} \label{eq:marmite2} {\color{orange}\forall x\in\R}\ \ {\color{#88F}\exists c\in\R}\quad f(x)=c \end{equation}

Cette dernière proposition exprime que tout nombre réel \(x\) admet une image \(c\) dans \(\R\) par \(f\) qui dépend donc de \(x\). Elle est toujours vraie puisque c'est précisément celle qui caractérise une application. La différence est de taille, \((\ref{eq:marmite})\) exprime que l'application \(f\) est constante, alors que \((\ref{eq:marmite2})\) répète qu'il s'agit d'une application…

La métaphore suivante devrait aider à comprendre l'impact d'une permutation des deux quantificateurs. Considérons l'expression fran­çai­se Toute marmite a son couvercle. En notant \(M\) l'ensemble des marmites, \(C\) l'ensemble des cou­ver­cles et \(P(m,c)\) le prédicat à deux variables dont l'interprétation est \(P(m,c)\) est vrai si et seulement si le couvercle \(c\) est adapté à la marmite \(m\), la proposition suivante a exactement la même structure que celle de la proposition \((\ref{eq:marmite2})\) : \begin{equation*} {\color{orange}\forall m\in M}\ \ {\color{#88F}\exists c\in C}\quad P(m,c) \end{equation*}

Il est évident que le couvercle \(c\) dépend de la mar­mi­te \(m\) considérée. En permutant les quantificateurs, la pro­po­si­tion \begin{equation*} {\color{#88F}\exists c\in C}\ \ {\color{orange}\forall m\in M}\quad P(m,c) \end{equation*} exprime qu'il existe un couvercle qui convient à toutes les marmites, ce qui n'est bien sûr pas la même chose.

Axiomes de la théorie ZF

Nous allons à présent introduire la terminologie de base de la théorie des ensembles et définir pas-à-pas les opérations élémentaires sur les ensembles. On commence par l'inclusion.

Axiome d'extension

En théorie des ensembles, le symbole d’égalité = est un symbole logique primitif dont le rôle est d’exprimer la possibilité de remplacer un terme par un autre dans toute formule sans modifier sa valeur de vérité, mais il ne dit rien sur ce que signifie, pour des ensembles, d'être égaux. Nous devons donc préciser ce que cette égalité logique représente.

Attention aux confusions possibles à cause des différences d'acception d'un mot en langue naturelle et en mathématiques. En français, l'inclusion est synonyme d'appartenance, alors que l'inclusion \(\subseteq\) et l'appartenance \(\in\) ne signifient pas la même chose en théorie des ensembles.

On note commodément \(X\not\subseteq Y\) plutôt que \(\neg(X\subseteq Y)\). Dans la proposition \(X\) est une partie de \(Y\), il n'y a plus mention de la variable \(x\) présente dans son homologue formalisée \(\forall x\ \ x\in X\then x\in Y\), elle est donc bien muette.

L'axiome d'extension exprime que deux en­semb­les sont égaux si et seulement s'ils ont exactement les mêmes éléments. Il relie la notion logique d’égalité (pure substitution) à la conception mathématique de l’égalité entre ensembles (égalité des contenus). Il permet ainsi d’interpréter correctement le symbole = dans le cadre de la théorie ZF.

C'est cet axiome que l'on applique quand on veut démontrer que deux ensembles \(X\) et \(Y\) sont égaux, on parle souvent de la double inclusion. Cela consiste à se donner un élément quelconque \(x\in X\) et à démontrer qu'il appartient à l'ensemble \(Y\), puis à démontrer la réciproque.

Axiome de la paire

Si l'on dispose de deux objets \(a\) et \(b\), l'axiome de la paire assure l'existence de l'ensemble constitué de ces deux objets.

Dans le cas où \(a=b\), la paire \(\{a,b\}\) est réduite à \(\{a\}\), on l'appelle singleton \(a\). L'axiome de la paire nous permet de considérer un ensemble avec deux objets et c'est grâce à cet axiome et à l'axiome de la réunion plus loin, que l'on peut définir l'écriture en extension d'un ensemble.

Axiome de sélection

L'axiome de sélection (ou axiome de compréhension ou encore axiome de séparation) est déjà bien connu du lecteur après le cours de mathématiques générales, il est utilisé en permanence. C'est la restriction du principe d'abstraction de Cantor, tout prédicat \(P(x)\) définit un ensemble, à condition que les objets \(x\) qui vérifient \(P(x)\) soient sélectionnés dans un ensemble pré­exis­tant :

On peut donc collecter les éléments d'un ensemble \(X\) qui satisfont un prédicat quelconque \(P(x)\). Il est clair qu'il s'agit d'un sous-ensemble de \(X\). Ainsi, cet axiome est inoffensif, il ne permet pas de créer un ensemble trop gros. L'écriture \((\ref{eq:compr})\) d'un ensemble est dite écriture en comp­ré­hen­sion, ses éléments sont décrits via un prédicat qu'ils satisfont. De manière imagée, on peut interpréter \((\ref{eq:compr})\) comme le résultat d'une pêche au filet, \(X\) désigne la zone de pêche et le prédicat \(P(x)\) les caractéristiques du poisson à retenir dans le filet.

Axiome de la réunion

Cet axiome exprime simplement que si l'on dispose de plusieurs ensembles, on peut considérer l'ensemble qui contient tous leurs éléments.

Quand l'ensemble \(Y=\{A,B\}\) est une paire d'ensembles, sa réunion est notée \(A\cup B\). C'est grâce à l'axiome de la réunion et à l'axiome de la paire que l'on a pu construire l'ensemble \((\ref{eq:ens4})\), c'est la réunion des paires \(\{1,f\}\) et \(\{3,x\}\). La réunion de l'ensemble \(\{\{a\},\{a,b,d\},\{a,c\},\{b,d\}\}\) est l'en­sem­ble \(\{a,b,c,d\}\).

Soit \(P(x)\) un prédicat quelconque. En se souvenant de \((\ref{eq:universel})\) et \((\ref{eq:existentiel})\), on comprend pourquoi la proposition \(\forall x\in\varnothing\ P(x)\), qui affirme que tout élément de l'ensemble vide satisfait le prédicat \(P(x)\), est toujours vraie : elle s'écrit \(\forall x\ (x\in\varnothing)\then P(x)\) et, \(x\in\varnothing\) étant faux pour tout \(x\), chaque implication est vraie (on rappelle que \(\bot\then A\) est toujours vrai). Symétriquement, la proposition \(\exists x\in\varnothing\ P(x)\), qui s'écrit \(\exists x\ (x\in\varnothing)\land P(x)\), est toujours fausse. Ce ne sont pourtant ni une tautologie ni une antilogie : chaque instance \(x\in\varnothing\then P(x)\) a la forme \(A\then B\), qui n'est pas une tautologie, et \((x\in\varnothing)\land P(x)\) la forme \(A\land B\), qui n'est pas une antilogie. Leur valeur de vérité ne tient pas à leur forme, mais au fait que \(x\in\varnothing\) est faux pour tout \(x\), ce que nous avons établi dans la preuve précédente à partir de la définition même de l'ensemble vide.

On note parfois \(\complement_XY\) le complémentaire de \(Y\) dans \(X\) ou encore \(\overline{Y}\) si le contexte discursif établit clairement quel est l'ensemble de référence \(X\).

Deux ensembles \(X\) et \(Y\) dont l'intersection \(X\cap Y=\varnothing\) est vide sont dits disjoints. En particulier l'ensemble vide est disjoint de tout ensemble \(X\). L'intersection d'un ensemble d'ensembles à la manière de la réunion d'un ensemble sera définie au chapitre prochain. La différence symétrique entre deux en­sem­bles \(X\) et \(Y\) est l'ensemble \((X\cup Y)\setminus(X\cap Y)\), on le note \(X\;\Delta\;Y\).

Pour aider à la compréhension, on représente parfois les opérations ensemblistes à l'aide d'un dia­gram­me de Venn.* John Venn était un ma­thé­ma­ti­cien ang­lais du début du 20-ème siècle Les ensembles sont représentés sous forme de cercles ou de patates qui se che­vau­chent. Vous pouvez visualiser le résultat des différentes opérations ensemblistes en les sur­vo­lant ci-dessous :

Axiome des parties

L'axiome des parties* nettement moins inoffensif que l'axiome de sélection permet de considérer l'ensemble dont les éléments sont tous les sous-ensembles de \(X\). Nous verrons au chapitre Combinatoire qu'il est considérablement plus grand que \(X\).

L'ensemble vide est une partie de tout ensemble \(X\) puisque \(x\in\varnothing\then x\in X\) est une proposition vraie puisque \(x\in\varnothing\) est fausse. Un ensemble est bien sûr inclus dans lui-même, par conséquent l'ensemble des parties d'un ensemble \(X\) contient toujours la partie vide \(\varnothing\) et l'ensemble \(X\). Par exemple si \(X=\{a,b,c\}\), on a \[\parts{X}=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},X\}.\] D'autre part, l'ensemble des par­ties de l'ensemble vide \(\parts{\varnothing}=\{\varnothing\}\) qui n'est pas l'en­semb­le vide puisqu'il contient l'élément \(\varnothing\).

L'ordre dans lequel nous écrivons les éléments d'un ensemble en extension n'a pas d'importance, la paire \(\{x,y\}\) est donc égale à la paire \(\{y,x\}\). Comment définir un nouvel objet ma­thé­ma­ti­que similaire à une paire mais pour lequel l'ordre dans lequel on écrit les deux objets a une importance ? On admettra le résultat suivant.

On peut vérifier que deux couples sont égaux si et seulement si leurs projections respectives sont égales (cf. exercice suivant). Par conséquent on dispose d'un objet mathématique \((x,y)\) qui répond à notre besoin : il contient deux objets \(x\) et \(y\) et l'ordre dans lequel ils apparaissent est important, i.e. \((x,y)\neq(y,x)\). On peut bien sûr imaginer d'autres constructions ensemblistes pour définir un objet similaire. Il faut être conscient qu'il ne s'agit que d'un simple codage et que maintenant que ce nouvel objet élémentaire a intégré notre arsenal, on peut oublier l'échafaudage qui a permis sa cons­truc­tion.

On généralise facilement la notion de couple à la notion de \(n\)-uplet \((x_1,x_2,\ldots,x_n)\) en posant \begin{equation} (x_1,\ldots,x_n):=((x_1,\ldots,x_{n-1}),x_n) \end{equation} et en utilisant inductivement l'axiome de la paire et l'axiome de la réunion puis en définissant le produit cartésien de \(n\) ensembles \(X_1, X_2,\ldots,X_n\) par \begin{equation} X_1\times X_2\times\cdots\times X_n:=\{(x_1,x_2,\ldots,x_n)\such \forall i\in\{1,\ldots,n\}\ x_i\in X_i\}. \end{equation} On définit alors la \(i\)-ème projection \(\text{pr}_i\) pour tout \(i\in\{1,\ldots,n\}\) et un ensemble \(G\) de \(n\)-uplets est qualifié de \(n\)-graphe.

Axiome du choix

Un dernier axiome, et nous achèverons là cette introduction à la théorie des ensembles, l'axiome du choix. Il fait intervenir deux notions étudiées plus loin dans ce cours, la notion de fonction et la notion de famille d'éléments d'un ensemble, mais que l'étudiant connaît déjà. Cet axiome nous autorise à extraire un élément de notre choix de chaque ensemble d'une famille d'ensembles pour en faire un ensemble, une sorte de menu à la carte. Cet axiome peut être intégré ou non dans la théorie des ensembles, si c'est le cas elle est appelée théorie zfc.

Remarques finales

La liste d'axiomes présentée dans ce chapitre est volontairement incomplète. La théorie des ensembles moderne, dite ZF en hommage à Zermelo et Fraenkel, comprend deux axiomes supplémentaires – le schéma de remplacement et l'axiome de fondation – plus délicats, et dont l'usage courant des mathématiques peut se passer : tous les objets construits dans ce cours ne réclament que les axiomes présentés ici. Ces deux axiomes sont étudiés dans le cours de calculabilité de master, qui revient en détail sur les fondements de la théorie des ensembles.

Comme évoqué au chapitre précédent, le texte mathématique suit une structure fondamentale faite de définitions et de théorèmes, alternant avec des exemples, des remarques et des commentaires qui en éclairent le sens. Ce cours respecte cette organisation, tout en intégrant des explications pour en comprendre les motivations et les enjeux. À ce stade, il est essentiel de maîtriser la structure type d'une définition et d'un théorème :

Pour une définition d'un nouvel objet mathématique :

• On liste les objets (les ingrédients) qui le composent,
• On précise les conditions que doit satisfaire cette construction.

Pour un théorème :

• On liste toutes les hypothèses : les propositions supposées vraies,
• On énonce la conclusion : la nouvelle proposition qui en découle.

Formalisation

Réponse au problème de la médiathèque

On rappelle qu'il s'agit d'étudier comment automatiser la recherche de documents qui satisfont la requête suivante dans une médiathèque : trouver tous les documents qui parlent de robot(s) ou de chat(s)*l’extraction des termes a permis de regrouper les variantes lexicales robot / robots ou encore chat / chats sous un même descripteur normalisé., mais qui ne mentionnent pas l'intelligence artificielle.

Le corpus \(\mathscr D\) de cette médiathèque est le suivant :

• \( d_1 \) : Le chat mécanique
• \( d_2 \) : Robots et intelligence artificielle
• \( d_3 \) : Chats et robots en bande dessinée
• \( d_4 \) : Intelligence artificielle et animaux
• \( d_5 \) : Robots domestiques
• \( d_6 \) : L’intelligence artificielle expliquée aux enfants

Définition des prédicats

On définit trois prédicats d'une variable \(d\) représentant un document avec les interprétations suivantes :

• \( R(d) \) : le document \(d\) contient le mot robot
• \( C(d) \) : le document \(d\) contient le mot chat
• \( I(d) \) : le document \(d\) contient les termes intelligence artificielle

La requête exprimée par l’usager se traduit par le prédicat \(P(d)\) suivant sur le corpus \({\mathscr D}\) de documents de la médiathèque :

Calcul

Le travail à fournir se traduit à présent par de simples opérations ensemblistes

Trois documents correspondent finalement à la requête \(P\) : \[ {\mathscr D}(P)=\{d_1,d_3,d_5\} \]

Perspectives d'automatisation du processus

Bien sûr, on est encore loin de pouvoir réaliser toutes ces opérations automatiquement. Comment sont indexés les termes clefs des documents ? Peut-on traduire automatiquement une requête en langue naturelle sous forme prédicative ? etc.

L’évaluation du prédicat \(P(d)\) sur le corpus \(\mathscr{D}\) repose sur un traitement algorithmique qui peut être schématiquement décomposé en plusieurs étapes :

1. Indexation du corpus : Cette phase est réalisée au préalable pour tous les documents du corpus qui sont enrichis de descripteurs (les tag) sur lesquels les requêtes vont réellement opérer. Cette opération peut être réalisée manuellement par un professionnel à chaque nouveau document abondant le corpus. Pour des raisons évidentes, ce travail est désormais réalisé automatiquement, en particulier par des algorithmes de traitement des langues naturelles.
2. Traduction de la requête : Lorsqu’une requête est soumise par l’utilisateur (sous forme textuelle), elle est tout d’abord transformée en une formule logique sur les prédicats correspondant aux descripteurs indexés (par exemple ici : \(P(d) \equiv (R(d) \lor C(d)) \land \neg I(d)\)). Cette traduction peut être réalisée manuellement pour des requêtes simples, ou bien automatiquement grâce à un analyseur syntaxique ou un parseur de requêtes, qui identifie les opérateurs logiques (et, ou, non) et les entités lexicales à relier aux tags du système.
3. Filtrage du corpus : La requête logique ainsi obtenue est ensuite évaluée sur les descripteurs associés à chaque document. Cette étape consiste à appliquer la combinaison booléenne aux tags présents, sans nécessiter de lire à nouveau le contenu complet des documents. Les documents satisfaisant la requête sont alors extraits et restitués à l’utilisateur.

D’un point de vue calculatoire, cette procédure peut s’exprimer de façon élémentaire en Python sous la forme suivante :

  # 1. Indexation du corpus
  index = {
  "d1": {"chat"},
  "d2": {"robot", "ia"},
  "d3": {"robot", "chat"},
  "d4": {"ia"},
  "d5": {"robot"},
  "d6": {"ia"}
  }

  # 2. Traduction de la requête
  def P(d):
  tags = index[d]
  return ("robot" in tags or "chat" in tags) and ("ia" not in tags)

  # 3. Filtrage du corpus
  resultats = [d for d in index if P(d)]

  print(resultats)

Le résultat produit ici est :

  ['d1', 'd3', 'd5']

Ce qui correspond exactement à l’ensemble \({\mathscr D}(P)\).

Le retour du Sudoku

Le calcul des prédicats permet de modéliser certains problèmes de manière beaucoup plus concise et expressive que le calcul propositionnel, notamment en évitant la prolifération des variables lorsque les domaines de valeurs sont importants. Revenons sur le jeu du Sudoku introduit dans le chapitre précédent. On rappelle qu'il faut comp­lé­ter les cases vierges d'une grille de \(9\times 9\) cases avec des valeurs comprises entre 1 et 9 de manière à ce que chacun des \(27\) blocs de \(9\) cases contienne exactement ces \(9\) valeurs, c'est-à-dire :

1. 1 : Chaque ligne doit contenir exactement chacune des 9 valeurs 1 à 9 ;
2. 2 : Chaque colonne doit contenir exactement chacune des 9 valeurs 1 à 9 ;
3. 3 : Chaque région \(3 \times 3\) doit contenir exactement chacune des 9 valeurs 1 à 9.

Les valeurs déjà présentes dans la grille, ont été choisies de manière à ce qu'il n'existe qu'une seule façon de compléter la grille, et le jeu consiste à les trouver. La grille ci-dessous est un exemple de grille à résoudre.

La formalisation du problème du Sudoku se fait avec un langage adapté. Les constantes sont les \(9\) valeurs de l'ensemble \({\mathscr C}:=\{1,2,3,\ldots,9\}\) et on considère des prédicats \(S(l,c,n)\) à \(3\) variables dans l'ensemble \(\def\CC{{\mathscr C}}\CC\) avec l'interprétation suivante :

C'est bien plus économique que la logique propositionnelle avec laquelle il fallait définir une variable propositionnelle pour chaque valeur possible dans chaque case, soit \(9\times 9\times 9=729\) va­riab­les.

On traduit le fait que chaque case contient exactement une valeur par les deux propositions sui­van­tes (la première pour exprimer au moins une valeur, la seconde pour au plus une valeur) :

La partie des règles R1 et R2 disant que chaque nombre apparaît une seule fois par ligne et par colonne s'exprime respectivement par les deux propositions suivantes :

Pour la partie de la règle R3 disant que chaque nombre apparaît au plus une fois par région, c'est un peu plus complexe car les sous-grilles \(3\times 3\) ne sont pas aisément adressables par des indices séparés. On peut régler ce problème de bien des manières. Par exemple en introduisant une fonction auxiliaire \(r:\CC^2\rightarrow\CC\) qui à chaque couple \((l,c)\) associe le numéro de la région où se trouve la case à la ligne \(l\) et à la colonne \(c\), en numérotant les régions de \(1\) à \(9\) dans l'ordre de lecture par exemple. On aurait alors

Chacun des \(24\) indices fournis dans la grille au départ se traduit par une instanciation \(S(l,c,n) = V\) pour la valeur \(n\) affectée à la ligne \(l\) et la colonne \(c\), par exemple ici \(S(2,5,2)=V\) ou encore \(S(3,7,5)=V\).

          def LireFichier(nom_du_fichier_physique):
          fichier_logique = open(nom_du_fichier_physique,"r")
          liste_des_lignes = fichier_logique.readlines()
          fichier_logique.close()
          return liste_des_lignes

          nomfichier = input("Fichier à lire ? ")
          lignes = LireFichier(nomfichier)
          print(lignes)
        

            ['une premiere ligne\n', 'une deuxieme ligne\n', 'et enfin une troisieme\n']       
          

            for ligne in lignes:
            print(ligne.rstrip())
          

          une premiere ligne
          une deuxieme ligne
          et enfin une troisieme
        

            chaine = "maths:en:folie"
            print(chaine.split(":"))
          

            ["maths","en","folie"]
          

          def LireGrille(nom_fichier_grille):
          fichier_grille = open(nom_fichier_grille,"r")
          grille = [(ligne.rstrip()).split() for ligne in fichier_grille.readlines()]
          fichier_grille.close()
          return grille
        

          def AfficherGrille(grille):
          for l in range(9):
          if (l > 0) and ((l% 3) == 0):
          print(" ------+-------+------")
          for c in range(9):
          if (c > 0) and ((c % 3)  == 0):
          print(" |", end="")
          print((grille[l][c]).rjust(2), end="")
          print()
        

            9 . . | . 7 . | 3 . .
            . 1 5 | . 2 . | . 4 6
            . . 8 | 6 . . | 2 5 .
            ------+-------+------
            4 6 ? | 1 8 2 | . . .
            . 7 9 | . . . | 8 3 .
            . . . | 9 3 7 | . 6 2
            ------+-------+------
            . 3 7 | . . 1 | 5 . .
            1 8 . | . 5 . | 6 9 .
            . . 4 | . 6 . | . . 3

          cinema = {"Alice", "Benoît", "Claire", "David"}
          sport = {"Benoît", "Bob", "Claire", "Emma", "Farid"}
          musique = {"Alice", "Farid", "Tom", "Claire"}
        

          . 2 . | . 7 . | 3 . .
          . . . | . 3 8 | 9 1 .
          . . . | . 5 . | . . .
          ------+-------+------
          . . . | . . . | . . .
          . 3 4 | 5 6 . | . . .
          . . . | . . . | . . .
          ------+-------+------
          . 9 2 | . . . | . . .
          . . . | . 9 7 | 1 . .
          . . . | . . . | . . 3