Logique et ensembles
\(\def\Id{{\text{Id}}}\def\rel{\,{\mathscr R}\,}\def\rg{{\rightarrow}}\def\Rg{{\Rightarrow}}\def\iff{{\;\Leftrightarrow\;}}\def\N{{\mathbb N}}\def\Z{{\mathbb Z}}\def\Q{{\mathbb Q}}\def\R{{\mathbb R}}\)

Introduction

Trois robots opérant pour un grand constructeur automobile sont dotés d'un module de synthèse vo­cale et d'un module de diagnostic. Lors de leur passage hebdomadaire à l'atelier pour une révision, ils font les affirmations suivantes :

bax et arg sont dans le même état.
bax est défectueux.
xam et arg sont en bon état.
🤖 🤖 🤖
xam arg bax

Quand un robot est défectueux, son diagnostic est toujours erroné et quand il fonctionne nor­ma­le­ment, son diagnostic est toujours bon. On sait qu'il y a au moins un robot défectueux et au moins un robot en bon état. Quels robots faut-il réparer ?

L'un des objectifs de ce chapitre est de mettre en place l'outillage nécessaire pour répondre à cette question (et beaucoup d'autres) et plus généralement d'étudier des éléments de logique qui seront indispensables dans tout votre cursus en informatique.

Les mathématiques poursuivent quatre grands objectifs :

Le mathématicien pur contestera probablement cette vision appliquée. On peut en effet étudier des objets mathématiques sans autre motivation que la pratique stimulante d'un jeu intellectuel et sans qu'ils aient le moindre rapport avec une quelconque réalité. Pourtant la grande majorité des théories ma­thé­ma­ti­ques ont pour origine des problèmes bien réels engendrant de nouveaux ques­tion­ne­ments qui parfois s'épanouissent au sein de théories autonomes. La dichotomie entre ma­thé­ma­ti­ques pures et appliquées n'a donc pas de raison d'être et si distingo il y a, les deux vivent depuis long­temps en par­fai­te symbiose.

Selon la théorie de l'évolution de Lamarck, la fonction créant l'organe, le langage ma­thé­ma­ti­que s'est progressivement structuré pour que cette science puisse se développer suivant ces axes. Les ma­thé­ma­ti­ques s'imposent naturellement en informatique dès que l'on cher­che à analyser un problème, à élaborer des méthodes de résolution et à valider les ré­sul­tats obtenus. Le langage mathématique est constitué de plusieurs langages formels imbriqués utilisant des signes et des termes qui leur sont propres et contrairement aux lan­ga­ges informatiques, la langue naturelle reste in­dis­pen­sable pour animer la partition. Ce métalangage est totalement formaté par et pour le rai­son­ne­ment.

Que ce soit en in­for­ma­ti­que ou en ma­thé­ma­ti­ques, l'écrit est par es­sen­ce le prin­ci­pal vecteur de com­mu­ni­ca­tion. La conséquence de ce fait in­dis­cu­ta­ble est qu'aucune méthode d'ap­pren­tis­sa­ge, aussi innovante soit-elle, ne pour­ra remplacer une pratique intensive de la lecture et de l'écriture pour pro­gres­ser dans ces deux disciplines.

Les règles de construction des mots, des phrases et plus généralement des langues naturelles qui oc­cu­pent les grammairiens ont leur pendant en ma­thé­ma­ti­ques et en informatique. Les ma­thé­ma­ti­ciens se sont intéressés à la théorie de la démonstration dès le début du xx-ème siècle et les in­for­ma­ti­ciens à la théorie des lan­ga­ges dans les années 1950. Les questions sur la nature du calcul ont lar­ge­ment contribué aux interactions entre les deux disciplines dans le cadre de la théorie de la cal­cu­la­bi­li­té et l'isomorphisme de Curry-Howard établit des liens formels entre une dé­mons­tra­tion dans un système logique et un programme dans un modèle de calcul, autrement dit prouver\(\iff\)programmer. Ce ré­sul­tat ne sera pro­ba­ble­ment pas de nature à rassurer l'étudiant qui espérait trouver une échappatoire à l'étude des mathématiques, mais il met en évidence les liens profonds qui existent entre ces deux disciplines.

La principale différence entre une langue naturelle et le métalangage ma­thé­ma­ti­que concerne les am­bi­guï­tés et la jus­tes­se des propos. Les ambiguïtés sont inhérentes aux langues naturelles et sont d'ail­leurs largement exploitées dans la rhétorique (allusions, sous-entendus, jeux de mots, sophismes, etc.) alors qu'elles sont bannies du langage ma­thé­ma­ti­que (tout comme des lan­ga­ges informatiques). Il est in­dis­pen­sa­ble de les lever dès qu'un énoncé peut être in­ter­pré­té de différentes façons :

Quand j'étais en Afrique, j'ai tué un éléphant en pyjama !  (Groucho Marx)

C'est ce qui explique la nature particulière des textes ma­thé­ma­ti­ques qui emploient des tour­nu­res de phrases rarement utilisées dans le langage commun, comme si et seulement si, deux-à-deux dis­joints, un et un seul, non-vide, etc. La logique naturelle n'est pas tout à fait celle de la lo­gi­que clas­si­que des ma­thé­ma­tiques, il existe d'ailleurs des logiques ma­thé­ma­ti­ques (dites non-clas­si­ques par opposition) dont certaines ont précisément pour objet d'être plus proches de celle que nous pra­ti­quons au quo­ti­dien. Là aussi, il est nécessaire de clarifier certaines situations.

Pour baptiser les objets que l'informaticien/ma­thé­ma­ti­cien construit, les mots sont choisis avec beau­coup de précaution et sont sensés être en adéquation avec l'acception qu'ils ont com­mu­né­ment. Pourtant certaines distortions existent et sont parfois sources d'erreurs ou de con­fu­sion. D'autre part, certains mots désignent des objets différents selon le contexte où ils sont emp­loyés. Il faut en être conscient et comprendre le rôle capital des définitions qui précisent leur sens dans un en­vi­ron­ne­ment particulier. Ceci explique la structuration litanique des textes ma­thé­ma­ti­ques en alternance de définitions et de théorèmes.

Pour commencer ce cours, nous allons étudier le socle logique des mathématiques et de l'in­for­ma­ti­que. Pour illustrer notre propos, nous aurons souvent besoin d'exemples qui intègrent des objets ou des notions que nous n'aurons pas encore définis formellement mais qui sont bien connus du lecteur, ou qui sont sensés l'être. Ce n'est pas contraire à ce qui se fait dans tout apprentissage. Pour faire une mé­ta­pho­re, la pratique de la conduite d'un véhicule est un atout pour en comprendre le fonc­tion­ne­ment, l'objet de ce chapitre est de découvrir certains des organes qui se cachent sous le capot. Dans la suite, si certains objets mathématiques sont construits à l'aide d'outils sensés être définis en aval, c'est pour ne pas compliquer inutilement l'exposé, cela sous-entend que ces outils ne sont pas eux mêmes définis à l'aide de ces objets ce qui créerait alors un cercle vicieux.

Calcul pro­po­si­tion­nel

Généralités

L'étymologie du mot logique dévoile les mots raison et langage. La logique est à la base de l'ar­ti­cu­la­tion du discours ma­thé­ma­ti­que et du fonc­tion­ne­ment ato­mi­que d'un ordinateur, il n'y a rien de sur­pre­nant à ce qu'elle se soit épanouie sur le for­mi­da­ble terrain de jeu qu'est l'in­for­ma­ti­que où elle est om­ni­pré­sen­te. Les combinaisons de pro­po­si­tions à l'aide de con­nec­teurs logiques constituent la première strate à la base du raisonnement et de la construction des circuits électroniques. Il s'agit d'un langage à part entière, c'est le langage du cal­cul pro­po­si­tion­nel dont nous allons fixer les règles de composition. Nous aborderons d'abord les aspects mathématiques, le chapitre Calcul booléen en don­ne­ra une vision plus proche de l'informatique et de l'électronique avec l'algèbre de Boole, les fonctions boo­lé­en­nes et les circuits logiques.

De manière analogue aux langues naturelles, un énoncé ma­thé­ma­ti­que ou un programme in­for­ma­ti­que doit respecter :

Abordons succinctement pour commencer la dimension sémantique du calcul pro­po­si­tion­nel puisqu'il s'agit de la mo­ti­va­tion première qui a abou­ti à la for­ma­li­sa­tion du raisonnement.

Une pro­po­si­tion­ est un énoncé auquel on peut attribuer une valeur de vérité vrai ou faux.

Il est important de noter dans cette définition qu'il est possible d'attribuer une valeur de vérité à une pro­po­si­tion­. Une proposition n'a pas besoin d'une valeur de vérité pour être une proposition, d'autre part si valeur de vérité il y a, elle n'est pas con­sub­stan­tiel­le à la proposition. Certains auteurs par­lent d'assertion pour une proposition, mais nous préférons ici réserver ce terme pour désigner une pro­po­si­tion­ énoncée comme vraie. Une assertion est donc une affirmation, ce qui rend son usage conforme à l'ac­cep­tion de ce terme en français.

À titre d'exemples voici quelques énoncés dont certains sont des pro­po­si­tion­s, d'autres non pour notre définition :

  1. Il pleut,
  2. Pourquoi le poulet traverse-t-il la route ?
  3. Ce chapitre est trop long à lire,
  4. \(\def\then{{\;\Rightarrow\;}}\def\iff{{\;\Leftrightarrow\;}}1+2=3\),
  5. Ce cours sera en ligne le 24 février 3016,
  6. L'ensemble des nombres algébriques est dénombrable,
  7. Si les poules avaient des dents, alors j'irais sur la lune,
  8. À la montagne, on est plus vite en haut qu'à pied.
  9. Je mens,
  10. \(0\,(\,4=-1\),
  11. Cette phrase n'a pas de valeur de vérité,
  12. \(1+\sqrt{x} > 4\)
  13. Cette phrase n'est pas une phrase.

L'énoncé #2 est une interrogation, l'énoncé #8 est absurde, l'énoncé #10 n'est pas correct syn­ta­xi­que­ment. On ne peut pas attribuer de valeur de vérité à l'énoncé #12 sans connaître la valeur de la variable numérique \(x\), il ne s'agit pas stricto sensu d'une pro­po­si­tion­, on utilise dans ce cas le terme de prédicat ou d'énoncé contingent, qui sont l'objet d'étude de la dernière section.

Tous les autres énoncés sont des pro­po­si­tion­s, mais il n'est pas toujours possible de leur affecter une valeur de vérité pour autant. Celle de la pro­po­si­tion­ #1 dépend implicitement du contexte (le lieu et le moment) tout comme la pro­po­si­tion­ #3 (le lecteur). La pro­po­si­tion­ #4 est vraie pour peu que l'on admette les règles de représentation des nombres et que l'on connaisse les rudiments du calcul. Établir une valeur de vérité de la pro­po­si­tion­ #5 est parfaitement illusoire, ce qui ruine au passage mes espoirs de postérité. La pro­po­si­tion­ #6 demande une certaine connaissance de l'arithmétique pour établir qu'elle est vraie. La pro­po­si­tion­ #7 est vraie du point de vue du logicien, mais peut sembler absurde, voire fausse pour le lecteur lambda. Les pro­po­si­tion­s #9 et #11 sont des paradoxes logiques, elles ne peuvent être vraies ou fausses sans créer une contradiction. Les paradoxes logiques émergent parfois quand il y a autoréférence, c'est-à-dire quand un énoncé fait référence à lui-même*(*) Par exemple la pro­po­si­tion Je suis un men­teur ne peut être vraie ou fausse sans abou­tir à une con­tra­dic­tion. mais cela n'a rien de systématique, par exemple la pro­po­si­tion­ #13 est fausse.

Il apparaît que l'interprétation d'une pro­po­si­tion­ en langue naturelle n'est pas un exercice trivial, loin s'en faut. Toujours dans ce cadre, nous allons voir qu'il est éga­lement délicat d'analyser les énon­cés contenant des con­nec­teurs logiques pourtant omniprésents dans nos langues naturelles. Con­si­dé­rons les phrases suivantes :

  1. Le cassis ou le poivre sont des baies.
  2. Je travaille ou je me repose.
  3. Apprenez votre cours ou vous aurez une mauvaise note.
  4. Alice et Bob sont mariés.
  5. Les étudiants dont la note en maths est supérieure à 7 et inférieure à 12.
  6. Je suis déçu du résultat du contrôle continu et je jette toutes les copies.
  7. Il fait chaud donc je transpire.
  8. Il pleut et je dois sortir les poubelles.

Certains connecteurs peuvent avoir une signification différente selon le contexte. Le connecteur ou de la première phrase est inclusif, le second est exclusif et le troisième exprime une conséquence. La quatrième phrase laisse entendre qu'Alice est mariée avec Bob mais ce n'est pas une cer­ti­tu­de, il est donc difficile de lui attribuer une valeur de vérité. Le connecteur et de l'énoncé #5 code une énu­mé­ra­tion et pas une simple conjonction. De même la conjonction de l'énoncé #6 induit une con­sé­quen­ce.

En outre, certains connecteurs ne sont pas vé­ri­fonc­tion­nels en langue naturelle, c'est-à-dire que la valeur de vérité de l'énoncé ne dépend pas uniquement de la valeur de vérité des pro­po­si­tion­s qu'ils connectent. Ainsi en remplaçant je transpire par 4 est un nombre pair dans la pro­po­si­tion­ #7, on transforme une pro­po­si­tion­ vraie en pro­po­si­tion­ ma­ni­fes­te­ment fausse alors que la valeur de vérité de la pro­po­si­tion­ 4 est un nombre pair est la même que celle de la pro­po­si­tion­ je transpire, elles sont toutes les deux vraies. Le et de l'énoncé #8 ne se contente pas d'exprimer une conjonction, il induit aussi une obligation.

Nous avons déjà constaté que la valeur de vérité d'une pro­po­si­tion n'est pas consubstantielle à sa struc­tu­re et nous venons de mettre en évidence que les connecteurs logiques dans les énoncés en langue naturelle peuvent être difficiles à interpréter ou impropres à un usage mathématique. La manière la plus efficace de se débarrasser de ces problèmes consiste à éliminer dans un premier temps toute interprétation dans une pro­po­si­tion­, elle devient une construction purement syntaxique. C'est une façon bien commode de procéder, on limite le champ d'investigation de la logique à des entités simples en les détachant de la réalité. C'est ce que nous faisons en permance en ma­thé­ma­ti­ques. Même pour une simple expression comme

\begin{equation} \label{expr:decimal} 2\times (5+93)=196, \end{equation}

on ne se préoccupe ni de sa signification, ni de savoir si \(196\) représente une quantité, le poids d'une table ou la hauteur d'un immeuble, seul l'application des règles sur l'objet abstrait importe. Le distingo entre la syntaxe et la sé­man­ti­que de l'expression \(196\) est peut-être difficile à percevoir pour le lecteur car la confusion a été volontairement en­tre­nue par les règles de lecture d'un nombre (ici cent-quatre-vingt-seize) où le chiffre le plus significatif est intégré avant les autres afin d'assurer la perception rapide d'une mesure au lieu d'égréner les chif­fres un, neuf, six. On encapsule ainsi forme et fond. C'est la raison exacte de l'apprentissage de la lecture des mots, l'objectif est précisément de ne plus avoir à les déchiffrer (toujours cette analogie avec les nombres) pour en saisir le sens. En remplaçant l'écriture des nombres en base 10 par l'écriture en chiffres ro­mains dans l'expression \((\ref{expr:decimal})\), on fait res­surgir la séparation entre syn­taxe et sémantique, au moins le temps que la lecture des nombres en chiffres romains deviennent si naturelle qu'à nouveau il y ait confusion :

\begin{equation} \label{expr:romain} \text{II}\times\text{(V}+\text{XCIII)}=\text{CXCVI} \end{equation}

La lecture des 5 chiffres romains CXCVI n'évoque pas mentalement la quantité que nous per­ce­vons sans peine sous la forme décimale \(196\), et pourtant les deux représentations codent exactement le mê­me nombre.

Syntaxe du calcul pro­po­si­tion­nel

Concentrons nous pour le moment sur ce langage et intéressons nous à ses aspects lexicaux et syn­ta­xi­ques, nous reviendrons sur l'aspect sémantique un peu plus loin. Pour construire une pro­po­si­tion­, il faut tout d'abord disposer d'un lexique de symboles — un alphabet — ces symboles sont répartis en quatre catégories :

  1. Les constantes \(\top\) et \({\bot}\).
  2. Les variables pro­po­si­tion­nelles ou pro­po­si­tion­s atomiques que l'on décrit généralement à l'aide de lettres de l'alphabet. Elles sont dénombrables.*(*) Nous verrons au cha­pi­tre Combinatoire ce que cela signifie. Elle ne peuvent prendre que les deux valeurs \(\top\) ou \({\bot}\).
  3. Les parenthèses \((\) et \()\).
  4. Les connecteurs logiques \(\neg\), \(\vee\), \(\wedge\), \(\Rightarrow\), \(\Leftrightarrow\), \(\oplus\), \(\uparrow\), \(\downarrow\).

Voilà pour le lexique, passons à la syntaxe. À partir des variables pro­po­si­tion­nelles, on peut créer de nouvelles pro­po­si­tion­s grâce aux connecteurs logiques qui les mettent en relation dans une formule (nous définirons précisément ce terme plus bas). L'arité d'un connecteur logique est le nombre \(q\) de pro­po­si­tion­s qu'il permet de connecter, on parle aussi de connecteur \(q\)-aire (unaire pour \(q=1\), binaire pour \(q=2\), ternaire pour \(q=3\), etc.).

À l'instar de l'expression arithmétique \(2(x+1)+y\) contenant deux variables \(x\) et \(y\), la valeur d'une formule est fonction#(#) dépend des valeurs des variables pro­po­si­tion­nel­les qu'elle contient. Les variables pro­po­si­tion­nelles ne pouvant prendre qu'un nombre fini de valeurs (\(\top\) ou \({\bot}\)), un connecteur logique est en­tiè­re­ment caractérisé par les différentes valeurs possibles de la formule selon les valeurs des variables qu'il connecte. Notons que l'on ne peut pas procéder de cette manière pour caractériser l'addition dans \(\def\Z{{\Bbb Z}}\Z\), l'ensemble des valeurs possibles des variables étant infini. Avant même d'étudier l'analyse combinatoire, il n'est pas difficile de montrer qu'il y a \(2^q\) com­bi­nai­sons possibles pour les valeurs des \(q\) variables pro­po­si­tion­nel­les d'un connecteur \(q\)-aire, et donc \(2^{2^q}\) façons différentes de définir un connecteur. En effet pour chacune des \(2^q\) valeurs possibles du \(q\)-uplet constitué des \(q\) variables, la formule peut pren­dre \(2\) valeurs distinctes \(\top\) ou \({\bot}\). La première table contient les 4 connecteurs unaires possibles \(\star_i\), la suivante les 16 connecteurs binaires possibles \(\diamond_j\) :

\(P\)\(\star_1\)\(\star_2\)\(\star_3\)\(\star_4\)
\(\bot\)\(\bot\)\(\bot\)\(\top\)\(\top\)
\(\top\)\(\bot\)\(\top\)\(\bot\)\(\top\)
Les 4 connecteurs unaires \(\star_i\) caractérisés par les 2 valeurs \(\star_i\; P\).

\(P\)\(Q\)\(\diamond_1\)\(\diamond_2\)\(\diamond_3\)\(\diamond_4\)\(\diamond_5\)\(\diamond_6\)\(\diamond_7\)\(\diamond_8\)\(\diamond_9\)\(\diamond_{10}\)\(\diamond_{11}\)\(\diamond_{12}\)\(\diamond_{13}\)\(\diamond_{14}\)\(\diamond_{15}\)\(\diamond_{16}\)
\(\bot\)\(\bot\) \(\bot\)\(\bot\)\(\bot\)\(\bot\)\(\bot\)\(\bot\)\(\bot\)\(\bot\)\(\top\)\(\top\)\(\top\)\(\top\)\(\top\)\(\top\)\(\top\)\(\top\)
\(\bot\)\(\top\) \(\bot\)\(\bot\)\(\bot\)\(\bot\)\(\top\)\(\top\)\(\top\)\(\top\)\(\bot\)\(\bot\)\(\bot\)\(\bot\)\(\top\)\(\top\)\(\top\)\(\top\)
\(\top\)\(\bot\) \(\bot\)\(\bot\)\(\top\)\(\top\)\(\bot\)\(\bot\)\(\top\)\(\top\)\(\bot\)\(\bot\)\(\top\)\(\top\)\(\bot\)\(\bot\)\(\top\)\(\top\)
\(\top\)\(\top\) \(\bot\)\(\top\)\(\bot\)\(\top\)\(\bot\)\(\top\)\(\bot\)\(\top\)\(\bot\)\(\top\)\(\bot\)\(\top\)\(\bot\)\(\top\)\(\bot\)\(\top\)
Les 16 connecteurs binaires \(\diamond_i\) caractérisés par les 4 valeurs \(P\;\diamond_i\; Q\).

Les connecteurs unaires \(\star_1\) et \(\star_4\) sont constants et la formule \(\star_2\; P\) prend exactement les mêmes va­leurs que \(P\), le connecteur \(\star_2\) est donc l'identité. Le seul connecteur qui ne soit pas trivial est donc \(\star_3\), c'est la négation logique.

Comme pour les connecteurs unaires, les deux connecteurs binaires \(\diamond_{1}\) et \(\diamond_{16}\) sont constants et de moindre intérêt, il en reste malgré tout 14. La moitié d'entre eux sont baptisés car ils sont com­mu­né­ment utilisés en Ma­thé­ma­ti­ques et/ou en Informatique et/ou en Électronique. On a au final huit con­nec­teurs usuels et selon le con­tex­te ou la discipline, on en utilise tout ou partie :

ConnecteurNomSymboleLectureUsage
\(\star_3\)négation\(\neg\) nonM|I|É
\(\diamond_2\)con­jonc­tion\(\wedge\)etM|I|É
\(\diamond_8\)dis­jonc­tion\(\vee\)ouM|I|É
\(\diamond_{14}\)implication\(\Rightarrow\)impliqueM|I
\(\diamond_{10}\)équivalence\(\Leftrightarrow\)équivalentM|I
\(\diamond_{7}\)disjonction exclusive\(\oplus\)ou exclusifI|É
\(\diamond_{15}\)non conjonction\(\uparrow\)non etI|É
\(\diamond_{9}\)non disjonction\(\downarrow\)non ouI|É
Les 16 connecteurs binaires \(\diamond_i\) caractérisés par les 4 valeurs \(P\;\diamond_i\; Q\). L'usage est indicatif.
Les symboles utilisés pour représenter les connecteurs logiques sont parfois différents dans cer­tains ouvrages.

Quand un connecteur est placé avant ses opérandes, on dit qu'il est en notation préfixe. Quand un connecteur est placé après ses opé­ran­des, on dit qu'il est en notation postfixe. Par exemple la transposée d'une matrice \(A\) est généralement écrite sous forme postfixe \(A^t\) bien que l'écriture préfixe \({}^t\!A\) soit également très commune. Quand l'opérateur est binaire et qu'il est placé entre les deux opérandes, on dit qu'il est en notation infixe et c'est généralement cette notation qui est employée en logique pro­po­si­tion­nel­le, on écrit donc plus volontiers \(P\Rightarrow Q\) que \(P\ Q\ \Rightarrow\), bien que la notation post­fixe soit très utilisée en informatique, elle permet en effet de se passer des pa­ren­thè­ses et d'évaluer très facilement une expression.

Une formule ou expression bien formée, est définie inductivement par l'une des règles de construction suivantes :
  1. \(formule := \color{#FF0}P\) où \(P\) est l'une des variables pro­po­si­tion­nel­les.
  2. \(formule := \color{#FF0}\top\)
  3. \(formule := \color{#FF0}\bot\)
  4. \(formule := \color{#FF0}\neg formule\)
  5. \(formule := \color{#FF0}(formule\;\diamond\; formule)\) où \(\diamond\) est l'un des connecteurs binaires.

Considérons par exemple \(P\), \(Q\) et \(R\) trois variables pro­po­si­tion­nel­les. L'expression

\begin{equation} \label{eq:ex1} ((P\Rightarrow Q) \wedge (P\vee \neg R)) \end{equation}

est une formule. Pour le montrer, il faut être en mesure de décrire comment elle a été construite à partir des règles fournies dans la définition ci-dessus. Voici une séquence de rè­gles possible (en jaune le terme sur lequel la prochaine règle est appliquée) : \begin{align*} &&\color{#FF0}for&\color{#FF0}mule\\ \text{règle}\ 5:&&(\color{#FF0}formule&\wedge formule)\\ \text{règle}\ 5:&&(({\color{#FF0}formule} \Rightarrow formule)&\wedge formule)\\ \text{règle}\ 1:&&((P \Rightarrow {\color{#FF0}formule})&\wedge formule)\\ \text{règle}\ 1:&&((P \Rightarrow Q)&\wedge {\color{#FF0}formule})\\ \text{règle}\ 5:&&((P \Rightarrow Q)&\wedge ({\color{#FF0}formule}\vee formule))\\ \text{règle}\ 1:&&((P \Rightarrow Q)&\wedge (P\vee {\color{#FF0}formule}))\\ \text{règle}\ 4:&&((P \Rightarrow Q)&\wedge (P\vee \neg {\color{#FF0}formule}))\\ \text{règle}\ 1:&&((P \Rightarrow Q)&\wedge (P\vee \neg R)) \end{align*}

Sauf cas particuliers, il existe plusieurs séquences de règles possibles pour établir une formule. Une telle séquence de règles s'appelle une dérivation de la formule. La représentation d'une formule à l'aide d'un arbre de dérivation permet de mieux comprendre sa structure. C'est un arbre schématisé dont le principe de construction est simple et inductif. Un connecteur \(q\)-aire est représenté à l'aide de \(q+1\) objets, le connecteur à la racine de l'arbre est relié à chacun de ses \(q\) opérandes qui constituent les nœuds de cet arbre.

On représente très souvent les arbres à l'envers, racine en haut et feuilles en bas, car les processus de construction des arbres abstraits commencent le plus souvent par la racine. On met ainsi en cohérence le sens de lecture et la chronologie de la construction.

Les deux arbres suivants représentent res­pec­ti­ve­ment un connecteur unaire et son opérande et un connecteur binaire et ses deux opérandes (les arbres sont dits unaire et binaire) :

          
L'arbre de dérivation d'un connecteur unaire \(\star\) et d'un connecteur binaire \(\diamond\) reliant des formules.

Quand les opérandes d'un connecteur sont eux-même des formules, on remplace chaque formule par l'arbre correspondant inductivement. Ainsi la formule \(((P\Rightarrow Q) \wedge (P\vee \neg R))\) a pour arbre de dé­ri­va­tion l'arbre

L'arbre de dérivation de \(((P\Rightarrow Q) \wedge (P\vee \neg R))\)

Une formule peut admettre plusieurs dérivations, mais un seul arbre de dérivation ce qui justifie l'emploi du singulier défini.

Comme pour les opérations arithmétiques, on décide de certaines prio­ri­tés pour simp­li­fier les écri­tu­res. La négation est prioritaire sur la conjonction qui est prioritaire sur la disjonction, elle mê­me prioritaire sur l'implication. Néanmoins, il est hautement pré­fé­ra­ble d'écrire toutes les pa­ren­thè­ses, l'expérience prouve qu'elle facilitent beaucoup plus sou­vent la lecture qu'elles ne la com­pli­quent. On simplifie malgré tout les formules en omettant les parenthèses aux extrémités, la formule simplifiée de \((\ref{eq:ex1})\) s'écrit \((P\Rightarrow Q) \wedge (\neg P\vee R).\)

On peut se demander pourquoi on n'étudie pas d'autres opérateurs que les opérateurs unaires et bi­nai­res. Le résultat suivant et son corollaire fournissent une justification.

Soit \(q\) un entier naturel tel que \(q > 2\). Tout connecteur \(q\)-aire peut être défini à l'aide de connecteurs d'arité \(q-1\) et le connecteur de négation.
Notons \(\Omega\) cet opérateur \(q\)-aire de manière préfixe et \(P_1,P_2,\ldots,P_q\) les \(q\) variables pro­po­si­tion­nel­les qu'il connecte. On vérifie aisément que \begin{equation} \Omega(P_1,P_2,\ldots,P_q)\Leftrightarrow \big(P_q\wedge \Omega(P_1,P_2,\ldots,P_{q-1},\top)\big)\vee\big(\neg P_q\wedge \Omega(P_1,P_2,\ldots,P_{q-1},\bot)\big). \end{equation}

Toute formule peut s'exprimer uniquement avec des connecteurs binaires et le connecteur unaire de négation.

Nous verrons au chapitre prochain que l'on peut obtenir des résultats plus forts encore que ce corollaire, mais le mathématicien sait déjà que l'on peut se contenter d'un seul connecteur binaire \(\wedge\) ou \(\vee\) en sus de la négation pour tout exprimer.

Mentionnons la structure conditionnelle Si \(P\) alors \(Q\) sinon \(R\), bien connue des in­for­ma­ti­ciens qui dans sa version logique est un connecteur ternaire utilisé couramment. Si \(P=\top\), l'ex­pres­sion a la valeur de \(Q\) et si \(P=\bot\), elle a la valeur de \(R\), ce que l'on peut résumer dans la table de vérité suivante en notant \(\Rrightarrow\) cet opérateur de manière préfixe \(\Rrightarrow(P,Q,R)\) :

\(P\)\(Q\)\(R\)\(\Rrightarrow\)
\(\bot\)\(\bot\)\(\bot\) \(\bot\)
\(\bot\)\(\bot\)\(\top\) \(\top\)
\(\bot\)\(\top\)\(\bot\) \(\bot\)
\(\bot\)\(\top\)\(\top\) \(\top\)
\(\top\)\(\bot\)\(\bot\) \(\bot\)
\(\top\)\(\bot\)\(\top\) \(\bot\)
\(\top\)\(\top\)\(\bot\) \(\top\)
\(\top\)\(\top\)\(\top\) \(\top\)
Le connecteur ternaire Si/Alors/Sinon \(\Rrightarrow.\)

Sémantique du calcul pro­po­si­tion­nel

Revenons à la sémantique. Il s'agit d'attribuer un sens à une formule, on veut l'interpréter. Seules deux valeurs logiques sont possibles, vrai ou faux, c'est la valeur de vérité de la formule. Une in­ter­pré­ta­tion est donc une fonction de l'en­semb­le des formules \(\mathscr F\) dans l'ensemble*(*) Les termes ensemble et fonction ne sont pas dé­fi­nis for­mel­le­ment à ce stade mais la vision naïve est suf­fi­san­te ici. \(\{vrai,\;faux\}.\)

Les règles qui permettent d'attribuer un sens aux formules sont mises en cohérence avec les règles de construction syntaxique. La fonction d'in­ter­pré­ta­tion \(I\) est définie en fixant arbi­trai­re­ment une valeur de vérité \(vrai\) ou \(faux\) à chacune des variables pro­po­si­tion­nelles. C'est la seule marge de manœuvre dont on dispose si l'on décide que les constantes \(\top\) et \(\bot\) (objets syntaxiques) sont interprétées res­pec­ti­ve­ment comme les valeurs logiques \(vrai\) et \(faux\) (objets sé­man­ti­ques), i.e. \(I(\top)=vrai\) et \(I(\bot)=faux\) et que la fonc­tion d'interprétation d'une formule se conforme aux tables des con­nec­teurs logiques.

On appelle in­ter­pré­ta­tion d'une proposition toute fonction de l'ensemble des variables propositionnelles quelle contient dans l'ensemble \(\{vrai,\;faux\}.\)

En remplaçant \(\top\) par \(vrai\) et \(\bot\) par faux dans les tables des connecteurs logiques, on obtient leurs tables de vérité. Nous avons regroupé les 7 tables de vérité des connecteurs logiques binaires dans un unique tableau et avons résumé les valeurs de vérité vrai et faux par \(V\) et \(F\) respectivement pour plus de lisibilité.

\(P\)\(\neg P\)
FV
VF
\(P\)\(Q\) \(\ P\wedge Q\ \) \(\ P\vee Q\ \) \(\ P\Rightarrow Q\ \) \(\ P\Leftrightarrow Q\ \) \(\ P\oplus Q\ \) \(\ P\uparrow Q\ \) \(\ P\downarrow Q\ \)
FF FFVVFVV
FV FVVFVVF
FF FVFFVVF
VV VVVVFFF

Tables de vérité des huit opérateurs logiques usuels unaires et binaires.

La table de vérité d'une formule contient ses valeurs de vérité pour l'intégralité des combinaisons possibles des variables pro­po­si­tion­nel­les qu'elle contient. La table de vérité de la formule \((\ref{eq:ex1})\) est pré­sen­tée ci-dessous et pour faciliter la compréhension, les deux sous-formules de la conjonction sont pré­sen­tes également :

\(P\)\(Q\)\(R\) \(\ P\Rightarrow Q\ \) \(\ P\vee\neg R\ \) \(\ (P\Rightarrow Q)\wedge( P\vee\neg R\ )\)
FFF VVV
FFV VFF
Interprétation \(\color{#AA88FF}{I}\quad \) FVF VVV
FVV VFF
VFF FVF
VFV FVF
VVF VVV
VVV VVV
Table de vérité de la formule \((P\Rightarrow Q)\wedge( P\vee\neg R)\)

Comment construit-on effectivement une table de vérité ? L'algorithme est simple, on se donne tout d'abord une in­ter­pré­ta­tion \(\color{#AA88FF}{I}\) pour remplacer chaque variable pro­po­si­tion­nelle \(P\) — donc chaque feuille de l'arbre de dérivation (sur fond gris dans les exemples) — par sa valeur de vérité \(I(P)\), puis on ap­pli­que in­duc­ti­ve­ment les deux opérations sui­vantes sur l'arbre de dérivation :

  1. on remplace chaque sous-arbre constitué d'un connecteur unaire de négation et de sa feuille par un seul nœud contenant la négation de la valeur contenue dans la feuille,
  2. on remplace chaque sous-arbre constitué d'un connecteur binaire et de ses deux feuilles par un seul nœud contenant la valeur de la sous-formule correspondante,
et ceci jusqu'à ce que l'arbre soit réduit à sa seule racine qui contient alors la valeur de vérité de la formule. Pour notre exemple, avec l'interprétation \(I(P)=\color{#FF0}F\), \(I(Q)=\color{#FF0}V\) et \(I(R)=\color{#FF0}F\), on ob­tient successivement les 5 arbres suivants (les nœuds des sous-arbres auxquels on applique une règle sont cerclés en jaune, les opérateurs sont sur fond noir, les opérandes sur fond gris) :

Évaluation de l'arbre de dérivation de la formule \((P\Rightarrow Q)\wedge( P\vee\neg R)\) pour l'interprétation \(I\).

Deux formules \(E_1\) et \(E_2\) qui ont même valeur de vérité pour toute interprétation \(I\) de leurs variables sont dites logiquement équivalentes, ce que l'on note \(E_1\equiv E_2\). Le symbole \(\equiv\) est appelé équivalence logique.

On montre aisément que pour toute assertion \(P\), on a \begin{equation}\label{eq:neg} \neg(\neg P)\ \equiv\ P \end{equation} et que \(P\) et \(Q\) peuvent être échangés sans rien changer aux tables de vérités de \(P \vee Q\) et \(P\wedge Q\), au­tre­ment dit que ces deux connecteurs sont com­mu­ta­tifs. \begin{align}\label{eq:comou} P \vee Q\ &\equiv\ Q\vee P\\ P \wedge Q\ &\equiv Q\wedge P\label{eq:comet} \end{align}

D'autre part, on a les deux équivalences logiques suivantes, qui sont souvent utilisées en ma­thé­ma­ti­ques pour définir les connecteurs d'implication et d'équivalence à partir des trois con­nec­teurs de né­ga­tion, de conjonction et de disjonction : \begin{align}\label{eq:implique} P\Rightarrow Q&\ \equiv\ \neg{P}\vee Q\\ P\Leftrightarrow Q&\ \equiv\ (P\Rightarrow Q) \wedge (Q\Rightarrow P)\label{eq:eq} \end{align}

Nous verrons plus bas que le connecteur d'implication \(\Rightarrow\) n'est pas commutatif, alors que la com­mu­ta­ti­vi­té du connecteur \(\wedge\) entraîne celle du connecteur \(\Leftrightarrow\) d'équivalence.

Lorsqu'une proposition \(P\Rightarrow Q\) est vraie, on dit que \(Q\) est une condition nécessaire de \(P\) ou que \(P\) est une condition suffisante de \(Q\).
Si l'on a \(P\then Q\) et que l'on sait que \(P\) est vraie, on peut en déduire que \(Q\) est vraie alors que sans information sur \(P\), ou si \(P\) est fausse, l'implication ne nous permet pas de déduire quoi que se soit sur \(Q\). À la lumière de la table de vérité de l'implication, si l'on doit démontrer qu'une assertion \(P\Rightarrow Q\) est vraie et que \(P\) est fausse, il n'y a rien à faire, en revanche si \(P\) est vraie il faut prouver que \(Q\) est vraie. Pour démontrer une équi­va­len­ce, d'après la définition \((\ref{eq:eq})\) il faut démontrer les deux imp­li­ca­tions \(P\Rightarrow Q\) et \(Q\Rightarrow P\), autrement dit que \(P\) est une condition nécessaire et suffisante de \(Q\) (ou réciproquement), ce que l'on énonce souvent en disant \(P\) si et seulement si \(Q\).

Il est aisé de prouver les deux équivalences logiques qui suivent en construisant les tables de vérités des assertions qui les constituent. Ces équivalences sont extrêmement utiles, ce sont les lois de De Morgan.*(*) Augustus De Morgan était un ma­thé­ma­ti­cien bri­tan­ni­que qui vé­cut au 19ème siè­cle.

Soient \(P\) et \(Q\) deux assertions, alors \begin{align}\label{eq:morganou} \neg(P\vee Q)&\ \equiv\ \neg P\wedge\neg Q\\ \label{eq:morganet} \neg(P\wedge Q)&\ \equiv\ \neg P\vee\neg Q\\ \end{align}
Démontrez les lois de De Morgan. Démontrez la transitivité de l'implication, i.e. soient \(P\), \(Q\) et \(R\) des pro­po­si­tion­s alors, \begin{equation} \big((P\Rightarrow Q)\wedge(Q\Rightarrow R)\big)\ \Rightarrow (P\Rightarrow R) \end{equation}
Soient \(P\), \(Q\) et \(R\) trois pro­po­si­tion­s. Démontrez que \begin{equation} \big(\Rrightarrow(P,Q,R)\big)\equiv \big(P\wedge Q)\vee(\neg P \wedge R)\big) \end{equation}
Une lecture attentive de la table de vérité du connecteur d'im­pli­ca­tion mon­tre que l'assertion \(P\Rightarrow Q\) n'est fausse que dans le cas où \(P\) est vraie et \(Q\) est fausse, et qu'elle est vraie dans tous les autres cas, et en particulier dès que l'assertion \(P\) est fausse. Par conséquent, l'assertion \((0=1)\Rightarrow (3\ \text{est pair})\) est vraie, ce qui paraît pour le moins déroutant. Si l'on revient à la définition du connecteur d'implication, à savoir \(\neg P\vee Q\), l'énoncé s'écrit \((0\not=1)\vee (3\ \text{est pair})\) ce qui est déjà moins troublant. Le mot implication dans la langue naturelle induit une relation de cause à effet entre \(P\) et \(Q\) que l'on interprète comme une déduction, ce que ne dit nullement l'assertion \(P\Rightarrow Q\).

Les connecteurs logiques établissent des liens de corrélation entre les assertions \(P\) et \(Q\) et non des liens de causalité. On peut aussi se convaincre que le connecteur d'implication tel qu'il est défini en logique pro­po­si­tion­nelle est le meilleur choix parmi les 16 connecteurs logiques binaires pour approximer son équivalent en langue naturelle.

Il ne faut pas écrire le symbole \(\Rightarrow\) pour signifier le mot donc. On peut légitimement se ques­tion­ner sur le choix du mot implication pour qualifier ce connecteur logique, puisqu'il a sans conteste un sens déductif en français. L'explication est fournie par la règle du Modus Ponens ci-dessous qui décrit le rôle de l'assertion \(P\Rightarrow Q\) dans le processus déductif et qui donne un sens précis aux mots donc ou alors dans le discours ma­thé­ma­ti­que. La déduction logique est symbolisée par le signe \(\vdash\) (ou \(\therefore\)) ou encore par une ligne séparant les prémisses \(P\) et \(P\Rightarrow Q\) (ou hypothèses), du conséquent \(Q\) (ou conclusion) à la manière d'une division.

Soient \(P\) et \(Q\) deux pro­po­si­tion­s. Si \(P\) est vraie et que \(P\Rightarrow Q\) est vraie, alors la pro­po­si­tion­ \(Q\) est vraie. On résume ce résultat en écrivant \begin{equation} \label{eq:modus} P,\ P\Rightarrow Q\vdash Q\qquad\text{ou}\qquad \frac{P,\ P\Rightarrow Q}{Q} \end{equation} et que l'on peut lire si \(P\) et \((P\Rightarrow Q)\) alors \(Q\).
Il suffit de lire la table de vérité du connecteur logique \(\Rightarrow\).

Ces notations sont largement utilisées dans l'étude des systèmes de décision, des logiques non clas­si­ques, en théorie de la dé­mons­tra­tion, en intelligence artificielle, etc. L'équivalence logique suivante entre deux implications dite Modus Tolens ou plus couramment contraposée est également très utilisée pour les dé­mons­tra­tions :

Soient \(P\) et \(Q\) deux pro­po­si­tion­s, alors \begin{equation}\label{eq:modustollens} P\Rightarrow Q\ \equiv\ \neg Q\Rightarrow \neg P \end{equation} La pro­po­si­tion­ \(\neg Q\Rightarrow \neg P\) est appelée contraposée de la pro­po­si­tion­ \(P\Rightarrow Q\).
En effet \begin{align*} \neg Q\Rightarrow \neg P\ &\equiv\ \neg(\neg Q)\vee \neg P\quad\text{d'après \((\ref{eq:implique})\)}\\ &\equiv\ Q\vee \neg P\quad\text{d'après \((\ref{eq:neg})\)}\\ &\equiv\ \neg P\vee Q\quad\text{d'après \((\ref{eq:comou})\)}\\ &\equiv\ P\Rightarrow Q\quad\text{d'après \((\ref{eq:implique})\)} \end{align*}

La pro­po­si­tion­ \(Q\Rightarrow P\) est appelée implication réciproque de l'implication \(P\Rightarrow Q\). Ce n'est pas sa né­ga­tion, en effet

\begin{align*} \neg(P\Rightarrow Q)\ &\equiv\ \neg(\neg P\vee Q)\quad\text{d'après \((\ref{eq:implique})\)}\\ &\equiv\ (\neg(\neg P))\wedge\neg Q\quad\text{d'après \((\ref{eq:morganou})\)}\\ &\equiv\ P\wedge\neg Q\quad\text{d'après \((\ref{eq:neg})\)}\\ \end{align*}

La proposition \(P\wedge\neg P\) est appelée contradiction ou paradoxe logique. Certaines pro­po­si­tion­s peuvent être toujours vraies (resp. fausses) quelles que soient les interprétations des variables pro­po­si­tion­nel­les qui les composent, on les appelle tautologies (resp. antilogies). Les trois tautologies suivantes sont très utilisées pour construire des démonstrations mathématiques :

  1. La non contradiction : \(\neg(P\wedge \neg P),\)
  2. Le tiers exclus : \(P\vee \neg P,\)
  3. L'analyse de cas : \((P\then Q)\wedge(\neg P\then Q)\iff Q,\)

La première exprime que l'on ne peut pas avoir si­mul­ta­né­ment une pro­po­si­tion­ et son contraire, on ne veut donc pas de paradoxes. Elle permet d'élaborer une stratégie de démonstration dite dé­mons­tra­tion par l'absurde. Plutôt que de montrer qu'une proposition \(P\) est vraie, on suppose qu'elle est fausse et on essaie de prouver la contradiction \(P\wedge \neg P)\) pour invalider l'hypothèse grâce à (1) et conclure que \(P\) est vraie grâce à (2). Ainsi un inspecteur qui suppose qu'un cambrioleur est passé par une fenêtre et ne trouve aucune trace d'effraction sur la fenêtre en conclura que son hypothèse était absurde et que le cambrioleur est entré par un autre moyen.

La seconde exprime qu'une pro­po­si­tion­ ou son contraire doit être vraie, autrement dit que l'on exclut une troisième possibilité. Notons que (1) et (2) sont la négation l'une de l'autre d'après les lois de De Morgan \((\ref{eq:morganou})\) et \((\ref{eq:morganet})\). La troisième exprime le fait que c'est l'interprétation de \(Q\) qui fixe la valeur de vérité de la conjonction, quelle que soit l'interprétation de \(P\).

En guise de référence rapide, on regroupe ici les propriétés les plus importantes des connecteurs lo­gi­ques. Soient \(P\), \(Q\) et \(R\) des propositions. Alors

  1. Commutativité de \(\wedge\) et \(\vee\). \begin{align*} (P\wedge Q)&\equiv (Q\wedge P) & (P\vee Q)&\equiv (Q\vee P). \end{align*}
  2. Associativité de \(\wedge\) et \(\vee\). \begin{align*} ((P\wedge Q)\wedge R)&\equiv (P\wedge(Q\wedge R)), & ((P\vee Q)\vee R)&\equiv (P\vee(Q\vee R)). \end{align*}
  3. Idempotence de \(\wedge\) et \(\vee\). \begin{align*} (P\wedge P)&\equiv P, & (P\vee P)&\equiv P. \end{align*}
  4. Lois de De Morgan. \begin{align*} \neg(P\wedge Q)&\equiv (\neg P\vee\neg Q) & \neg(P\vee Q)&\equiv (\neg P\wedge\neg Q) \end{align*}
  5. Distributivité de \(\wedge\) sur \(\vee\) et de \(\vee\) sur \(\wedge\). \begin{align*} (P\wedge(Q\vee R))&\equiv ((P\wedge Q)\vee (P\wedge R)) & (P\vee(Q\wedge R))&\equiv ((P\vee Q)\wedge (P\vee R)) \end{align*}
  6. Absorption. \begin{align*} (P\wedge(P\vee Q))&\equiv P & (P\vee(P\wedge Q))&\equiv P \end{align*}
  7. La conjonction et la disjonction avec les constantes \(V\) et \(F\). \begin{align*} (P\vee V)&\equiv V & (P\wedge V)&\equiv P & (P\vee F)&\equiv P & (P\wedge F)&\equiv F \end{align*}
  8. Transitivité de l'implication. \begin{align*} (P\then Q)\wedge(Q\then R))\then(P\then R). \end{align*}
Démontrez que le connecteur \(\oplus\) est commutatif et associatif. Parmi les autres connecteurs bi­nai­res, combien sont commutatifs ?
Soient \(P\) et \(Q\) deux variables propositionnelles. Démontrez que \[(P\oplus Q)\equiv(P\vee Q)\wedge\neg(P\wedge Q) \]
Un connecteur logique binaire \(\diamond\) est dit associatif si pour toutes pro­po­si­tion­s \(P\), \(Q\) et \(R\) on a \[(P\,\diamond\, Q)\,\diamond\, R\ \equiv\ P\,\diamond\, (Q\,\diamond\, R).\] Parmi les 4 connecteurs logiques binaires de conjonction, de disjonction, d'implication et d'équivalence, le­quel(s) est/sont associatif(s) ?
Soient \(P\), \(Q\) et \(R\) trois pro­po­si­tion­s. Démontrez que \[(P\wedge Q)\Rightarrow R\ \equiv\ P\Rightarrow (Q\Rightarrow R)\]
Un mathématicien discute avec un ami logicien qui lui annonce que sa femme vient d'ac­cou­cher. Le mathématicien lui demande s'il a eu un garçon ou une fille et le logicien lui répond oui. Expliquez la réponse du logicien.

Formalisation du raisonnement

Les robots

Nous pouvons à présent étudier le problème de robots que nous avons présenté en introduction. On rappelle qu'un robot en bon état (resp. défectueux), fait toujours un bon (resp. mauvais) diagnostic et que les trois robots font les affirmations suivantes :

bax et arg sont dans le même état.
bax est défectueux.
xam et arg sont en bon état.
🤖 🤖 🤖
xam arg bax

On considère les variables propositionnelles \(\color{#FF0}X\), \(\color{#F44}B\) et \(\color{#88F}A\) définies par

On formalise les propositions de xam, arg et bax respectivement par :

  1. \({\color{#FF0}P_X}:\) \((B\wedge A)\vee (\neg B\wedge\neg A)\),
  2. \({\color{#F44}P_A}:\) \(\neg B\),
  3. \({\color{#88F}P_B}:\) \((X\wedge A)\).

Mais il faut traduire l'hypothèse qui dit qu'un robot en bon état fait toujours un bon diagnostic et qu'un robot défectueux fait toujours un mauvais diagnostic. Ce sont les trois équi­va­len­ces

\begin{equation} \label{eq:eqq} {\color{#FF0}P_X}\iff {\color{#FF0}X}, \quad {\color{#F44}P_A}\iff {\color{#F44}A}, \quad {\color{#88F}P_B}\iff {\color{#88F}B}. \end{equation}

Ainsi dans la table de vérité des trois propositions \({\color{#FF0}P_X}\), \({\color{#F44}P_A}\) et \({\color{#88F}P_B}\), leurs valeurs de vérités doivent être identiques à celles de \(X\), \(A\) et \(B\) respectivement :

\(\color{#FF0}X\)\(\color{#F44}A\)\(\color{#88F}B\)\({\color{#FF0}(B\wedge A)\vee (\neg B\wedge\neg A)}\)\({\color{#F44}\neg B}\)\({\color{#88F}(X\wedge A)}\)
1FFF VVF
2FFV FFF
3FVF FVF
4FVV VFF
5VVF FVF
6VFV FFF
7VVF VVV
8VVV VFV
Table de vérité des propositions des trois robots.

Comme on peut le constater, seule l'interprétation #3 satisfait les trois équivalences \((\ref{eq:eqq})\), il faut donc réparer xam et bax. Il faut cependant réaliser que de manière générale, un énoncé peut très bien aboutir à la formalisation d'une proposition avec plusieurs in­ter­pré­ta­tions valides ou aucune (antilogie). Ceci justifie la définition suivante :

Un ensemble de propositions est dit satisfaisable s'il existe une interprétation de leur conjonction qui soit vraie. Dans le cas contraire, il est dit insatisfaisable.

Le logicien amoureux

Traitons un deuxième exemple. On interroge un logicien, qui dit toujours la vérité, sur sa vie sen­ti­men­ta­le et il affirme :

On peut traduire ces deux as­ser­tions en formules propositionnelles. Pour cela on définit les variables pro­po­si­tion­nel­les \(A\) et \(M\) qui sont interprétées de la manière suivante :

La proposition (a) se traduit par \(M\vee A\) et la proposition (b) par \(M\then A\). On construit leurs tables de vérité :

\(A\)\(M\)\(M\vee A\)\(M\then A\)
FFF \(V\)
F\(V\)\(V\) F
\(V\)F\(V\) \(V\)
\(V\)\(V\)\(V\) \(V\)
Table de vérité des propositions de l'énigme du logicien.

Les deux dernières lignes de cette table de vérité (les seules qui assurent que les assertions du logicien sont vraies) montrent que le logicien aime nécessairement Anne mais on ne sait rien de plus au sujet de la nature de sa relation avec Marie. Il nous faut donc un complément d'information pour conclure. À la question Est-il vrai que si vous aimez Marie, alors vous aimez Anne ?, le logicien répond*Notez que cette de­man­de de con­fir­ma­tion de (b) était en soi inu­ti­le puis­que le lo­gi­cien dit tou­jours la vé­ri­té.

Si on traduit ces deux dernières affirmations en propositions, on obtient \((M\then A)\then M\) pour (c) et \(M \then (M\then A)\) pour (d) et on reconnaît là l'équivalence \((M\then A)\iff M\) que l'on rajoute dans la table de vérité. Cette fois il ne reste qu'une seule interprétation propositionnelle de \(A\) et \(M\) qui assure la vérité des trois propositions, celle où le logicien aime les deux femmes :

\(A\)\(M\)\(M\vee A\) \(M\then A\)\((M\then A)\iff M\)
FFF \(V\)F
F\(V\)\(V\) FF
\(V\)F\(V\) \(V\)F
\(V\)\(V\)\(V\) \(V\)\(V\)

Les différentes affirmations du logicien ont donc été traduites sous formes de propositions et nous avons cherché les interprétations \(I\) des différentes variables assurant que leur conjonction était vraie, ici \(I(A)=V\) et \(I(M)=V\).

Les tee-shirts

Étudions le problème suivant : trois frères Alvin, Bob et Clive sont d'âges différents et portent des tee-shirts de couleurs différentes rouge, vert ou jaune. On dispose de deux indices :

  1. (a) Celui qui porte le tee-shirt rouge ne porte pas de lunettes et c'est le plus jeune,
  2. (b) Alvin porte des lunettes et Bob est plus vieux que celui qui porte le tee-shirt vert.
On cherche à déduire de ces indices le maximum d'information pour chacun des frères, à savoir sa position dans la fratrie, la couleur de son tee-shirt et s'il porte ou non des lunettes.

Phase 1. Certains éléments de l'énoncé sont des attributs (porter des lunettes, porter un tee-shirt d'une certaine couleur, être le benjamin) et sont satisfaits ou non par chaque frère, il est naturel d'en faire des variables pro­po­si­tion­nel­les :

  1. \(A_{\color{#F44}R}\) (resp. \(B_{\color{#F44}R}\), \(C_{\color{#F44}R}\)) code Alvin (resp. Bob, Calvin) porte un tee-shirt rouge,
  2. \(A_{\color{#0A0}V}\) (resp. \(B_{\color{#0A0}V}\), \(C_{\color{#0A0}V}\)) code Alvin (resp. Bob, Calvin) porte un tee-shirt vert,
  3. \(A_{\color{#FF0}J}\) (resp. \(B_{\color{#FF0}J}\), \(C_{\color{#FF0}J}\)) code Alvin (resp. Bob, Calvin) porte un tee-shirt jaune,
  4. \(A_L\) (resp. \(B_L\), \(C_L\)) code Alvin (resp. Bob, Calvin) porte des lunettes,
  5. \(A_A\) (resp. \(B_A\), \(C_A\)) code Alvin (resp. Bob, Calvin) est l'aîné,
  6. \(A_B\) (resp. \(B_B\), \(C_B\)) code Alvin (resp. Bob, Calvin) est le benjamin,
  7. \(A_C\) (resp. \(B_C\), \(B_C\)) code Alvin (resp. Bob, Calvin) est le cadet.

On dispose donc de \(21\) variables propositionnelles. Avant même d'utiliser les indices, il faut for­ma­li­ser un certain nombre de contraintes implicites. Chacun des trois frères doit porter un unique tee-shirt. Ceci se traduit par le fait qu'il doivent porter un tee-shirt rouge ou vert ou jaune et qu'il ne doivent pas en porter deux simultanément, soit res­pec­ti­ve­ment les six formules suivantes :

\begin{align} &(A_{\color{#F44}R}\vee A_{\color{#0A0}V} \vee A_{\color{#FF0}J}),\\ &\neg(A_{\color{#F44}R}\wedge A_{\color{#0A0}V}) \wedge \neg(A_{\color{#F44}R}\wedge A_{\color{#FF0}J}) \wedge \neg(A_{\color{#0A0}V}\wedge A_{\color{#FF0}J}),\\ &(B_{\color{#F44}R}\vee B_{\color{#0A0}V} \vee B_{\color{#FF0}J}),\\ &\neg(B_{\color{#F44}R}\wedge B_{\color{#0A0}V}) \wedge \neg(B_{\color{#F44}R}\wedge B_{\color{#FF0}J}) \wedge \neg(B_{\color{#0A0}V}\wedge B_{\color{#FF0}J}),\\ &(C_{\color{#F44}R}\vee C_{\color{#0A0}V} \vee C_{\color{#FF0}J}),\\ &\neg(C_{\color{#F44}R}\wedge C_{\color{#0A0}V}) \wedge \neg(C_{\color{#F44}R}\wedge C_{\color{#FF0}J}) \wedge \neg(C_{\color{#0A0}V}\wedge C_{\color{#FF0}J}).\\ \end{align}

Mais deux frères ne peuvent pas porter le même tee-shirt : \begin{align} &\neg(A_{\color{#F44}R}\wedge B_{\color{#F44}R})\wedge \neg(A_{\color{#F44}R}\wedge C_{\color{#F44}R})\wedge \neg(B_{\color{#F44}R}\wedge C_{\color{#F44}R}),\\ &\neg(A_{\color{#0A0}V}\wedge B_{\color{#0A0}V})\wedge \neg(A_{\color{#0A0}V}\wedge C_{\color{#0A0}V})\wedge \neg(B_{\color{#0A0}V}\wedge C_{\color{#0A0}V}),\\ &\neg(A_{\color{#FF0}J}\wedge B_{\color{#FF0}J})\wedge \neg(A_{\color{#FF0}J}\wedge C_{\color{#FF0}J})\wedge \neg(B_{\color{#FF0}J}\wedge C_{\color{#FF0}J}). \end{align}

Chacun des trois frères doit avoir une unique position dans la fratrie :

\begin{align} &(A_A\vee A_B\vee A_C),\\ &\neg(A_A\wedge A_B)\wedge \neg(A_A\wedge A_C)\wedge\neg(A_B\wedge A_C),\\ &(B_A\vee B_B\vee B_C),\\ &\neg(B_A\wedge B_B)\wedge \neg(B_A\wedge B_C)\wedge\neg(B_B\wedge B_C),\\ &(C_A\vee C_B\vee C_C),\\ &\neg(C_A\wedge C_B)\wedge \neg(C_A\wedge C_C)\wedge\neg(C_B\wedge C_C). \end{align}

Et deux frères ne peuvent être à la même position dans la fratrie :

\begin{align} &\neg(A_A\wedge B_A)\wedge\neg(A_A\wedge C_A)\wedge\neg(B_A\wedge C_A),\\ &\neg(A_B\wedge B_B)\wedge\neg(A_B\wedge C_B)\wedge\neg(B_B\wedge C_B),\\ &\neg(A_C\wedge B_C)\wedge\neg(A_C\wedge C_C)\wedge\neg(B_C\wedge C_C). \end{align}

Phase 2. On formalise maintenant les deux indices du problème avec des formules pro­po­si­tion­nel­les. L'indice (a) nous donne :

\begin{align} A_{\color{#F44}R}&\then (\neg A_L\wedge A_B),\\ B_{\color{#F44}R}&\then (\neg B_L\wedge B_B),\\ C_{\color{#F44}R}&\then (\neg C_L\wedge C_B). \end{align}

L'indice (b) est plus délicat à formaliser. Alvin porte des lu­net­tes impose \(I(A_L):=V\) pour la fonc­tion d'interprétation \(I\) que l'on doit précisément déterminer. C'est la seconde affirmation Bob est plus vieux que celui qui porte le tee-shirt vert. qui demande un peu de réflexion puisqu'il faut l'exprimer uniquement avec les variables dont on dispose. Si Alvin est le benjamin et qu'il porte un tee-shirt vert, alors Bob est soit le cadet soit l'aîné. Si Alvin est le cadet et porte le tee-shirt vert, Bob est nécessairement l'aîné, etc.

\begin{align} &(A_{\color{#0A0}V}\wedge A_B)\then (B_A\vee B_C),\\ &(A_{\color{#0A0}V}\wedge A_C)\then B_A,\\ &(C_{\color{#0A0}V}\wedge C_B)\then (B_A\vee B_C),\\ &(C_{\color{#0A0}V}\wedge C_C)\then B_A. \end{align}

Phase 3. Nous sommes face à un total de \(25\) propositions à satisfaire et il reste \(20\) variables à définir puisque nous savons que la variable \(A_L\) doit être vraie. Construire la table de vérité de la conjonction de ces \(25\) propositions n'est pas envisageable à la main, il y a plus d'un million de combinaisons possibles des \(20\) variables pro­po­si­tion­nel­les, mais se programme aisément. Il faut réaliser que l'augmentation du nombre de variables propositionnelles limite drastiquement la portée de la méthode consistant à construire la table de vérité. Le cours de théorie de la complexité de master montrera que chercher une interprétation qui satisfait un ensemble arbitraire de propositions logiques est un problème que l'on pense ne jamais pouvoir résoudre efficacement*On connaît d'excellentes heuristique cependant..

On peut tenter une approche moins mécanique. Notons \({\color{#F44}R},{\color{#0A0}V},{\color{#FF0}J}\) les trois couleurs, \(B,C,A\) les trois statut (Benjamin, Cadet, Aîné) dans la fratrie et \(L\) le statut de porteur de lunettes. On rappelle les deux indices :

  1. (a) Celui qui porte le tee-shirt rouge ne porte pas de lunettes et c'est le plus jeune,
  2. (b) Alvin porte des lunettes et Bob est plus vieux que celui qui porte le tee-shirt vert.
D'après (a) on a \({\color{#F44}R}\then B\), mais il n'y a qu'une couleur possible par statut, le statut de benjamin ne peut donc être associé à aucune autre couleur, d'où \({\color{#F44}R}\iff B\). Il reste donc les couleurs \({\color{#0A0}V}\) et \({\color{#FF0}J}\) pour le cadet et l'aîné. Mais Bob étant plus vieux que celui qui porte le tee-shirt vert d'après (b), il est donc l'aîné des trois frères et porte le tee-shirt jaune. D'autre part, puisqu'Alvin porte des lunettes, il ne peut porter le tee-shirt rouge (d'après (a), \({\color{#F44}R}\then \neg L\) soit par contraposition \(L\then \neg {\color{#F44}R},\) il porte donc le tee-shirt vert et c'est le cadet. Résumons :
  1. Alvin est le cadet, porte des lunettes et le tee-shirt vert,
  2. Bob est l'aîné et porte le tee-shirt jaune.

On en déduit évidemment que Calvin est le benjamin et qu'il porte le tee-shirt rouge. Il nous reste à savoir qui porte des lunettes. On sait qu'Alvin en porte et que Calvin ne peut en porter puisqu'il porte le tee-shirt rouge. Pour Bob, on ne sait pas, il peut porter des lunettes ou non. Finalement :

Calvin ¬👓 < Alvin 👓 < Bob 👓?
L'avantage décisif de cette démarche par rapport à la première approche est que l'on a développé une stratégie qui nous a évité un grand nombre de calculs inutiles, à la manière d'un joueur d'échec qui cherche son chemin dans les méandres des combinaisons de coups possibles. Cependant, il faut comprendre que ceci n'a été possible que parce que le problème est très simple et que nous avons construit un stratégie spécifique pour traiter cette instance. Il suffirait de rajouter quelques éléments à cette énigme pour rendre le problème totalement inextricable pour un être humain.

L'exemple de formalisation que nous venons de traiter illustre les limites de la logique pro­po­si­tion­nel­le. Son manque d'expressivité nous a contraint à créer un grand nombre de variables pour décrire les différents cas. Que se passerait-il si une énigme faisait référence à des entiers naturels ? Par exemple, un entier naturel est un multiple de la somme de ses chiffres et le premier chiffre est impair (dans sa re­pré­sen­ta­tion en base \(10\)) ? Manipuler une infinité de variables pro­po­si­tion­nel­les n'est envisageable ni pour humain, ni pour une machine. Il faut pouvoir décrire une infinité de situations à l'aide d'une description finie. L'apport du calcul des prédicats permet aussi de formaliser des situations finies de manière bien plus concise, on exprimera qu'une partie \(X=\{x_1,x_2,\ldots,x_n\}\) de \(\N\) ne contient que des entiers pairs par \[ \forall x\in X\ \ \exists k\in\N\ \ x=2\, k. \] plutôt que par l'ensemble des \(n\) propositions suivantes : \[ x_1\ \text{est pair},\ x_2\ \text{est pair},\ x_3\ \text{est pair},\ldots,\ x_n\ \text{est pair}. \]

Nous allons étudier la logique des prédicats dans le cadre de la théorie des ensembles de Zermello-Fraenkel (abrégée en théorie zf).

Calculez les négations des propositions suivantes :
  1. \(P\then(Q\then R)\),
  2. \(\neg P\then Q\),
  3. \((P\wedge Q)\vee R\).
Soit \(P,Q\) et \(R\) trois variables propositionnelles et \(\def\FF{{\mathscr F}}\FF\) la formule propositionnelle définie par \[\big((P\vee Q)\vee R\big)\then (P\wedge Q).\]
  1. Donner la valeur logique (valuation) de la formule \(\FF\) dans les cas suivants :
    1. Les variables \(P\) et \(Q\) prennent la valeur logique \(V\), la variable \(R\) prend la valeur logique \(F\).
    2. Les variables \(P\) et \(Q\) prennent la valeur logique \(F\), la variable \(R\) prend la valeur logique \(V\).
  2. Montrer que \(\FF\) est logiquement équivalente à \[(P\vee \neg Q) \wedge (P\vee \neg R) \wedge (Q \vee \neg P) \wedge (Q \vee \neg R).\]
Dans une brasserie vous commandez un sandwich au jambon ou un sandwich au pâté et un verre de bière. Le garçon vous écoute distraitement car il est occupé.
  1. Dans un premier temps il est sûr de la place du ou et du et mais il hésite sur la place des parenthèses.
    1. Ecrivez pour chacune des commandes possibles la formule propositionnelle correspondante.
    2. Pour être sûr de contenter le client, il doit satisfaire à la fois les deux commandes possibles. Écrivez la formule propositionnelle correspondante. Montrez à l'aide d'une table de vérité que cette dernière est logiquement équivalente à apporter (un sandwich au jambon ou un sandwich au pâté) et un verre de bière.
  2. Dans un second temps le garçon hésite aussi sur la place du et et du ou.
    1. Refaites dans ce cas le (1a), puis le (1b) en utilisant les équivalences logiques.
    2. Montrez que dans ce cas il peut se contenter d'apporter un sandwich au jambon et -un sandwich au pâté ou un verre de bière).
  3. Que doit-il apporter au minimum pour satisfaire le client et répondre à toutes ses hésitations ?
Soient \(P,Q,R\) des variables propositionnelles,
  1. La proposition \(\big((P\vee Q)\wedge (\neg P \vee R)\big)\then (Q\vee R)\) est-elle une tautologie ?
  2. On considère les trois variables propositionnelles \(E\), \(R\) et \(S\) qui modélise les évè­ne­ments
    • \(E\) : Il y a un examen,
    • \(R\) : Alexis révise ses cours,
    • \(S\) : Alexis échoue.
    On note respectivement \(P\), \(Q\) et \(R\) les trois assertions suivantes :
    • \(P:\) S'il y a un examen, alors Alexis révise ses cours,
    • \(Q:\) Si Alexis révise ses cours, alors Alexis n'échoue pas,
    • \(R:\) S'il n'y a pas d'examen, alors Alexis n'échoue pas.
    1. Écrivez \(P\), \(Q\) et \(R\) sous forme de formules propositionnelles logiques.
    2. Transformez \(P\), \(Q\) et \(R\) en propositions \(P'\), \(Q'\) et \(R'\) ne contenant que des disjonctions \(\vee\) et des négations \(\neg\),
    3. En utilisant la question (1), trouvez une proposition \(S\) telle que la proposition \((P'\wedge Q)\then S\) soit une tautologie,
    4. En utilisant la question (1), trouvez une proposition \(T\) telle que la proposition \((R'\wedge S)\then T\) soit une tautologie.
    5. Que peut-on déduire de la réussite d'Alexis à l'examen ?
L'inspecteur Lafrite interroge les suspects. Trois suspects ont été arrêtés à la suite du cambriolage de la villa de Monsieur Futay; ce sont Bradacié, Piedplat et Nécassé. Ces trois personnages sont bien connus de Lafrite pour le caractère très aléatoire de leurs affirmations :
  1. Bradacié : Piedplat est coupable et Nécassé est innocent,
  2. Piedplat : Si Bradacié est coupable, alors Nécassé l'est aussi,
  3. Nécassé : Je suis innocent mais l'un au moins des deux autres est coupable.
La réputation de l'inspecteur Lafrite serait passablement écornée s'il n'était pas en mesure de trouver la vérité. Il se doit donc d'envisager plusieurs possibilités, et c'est ce qu'il fait avant de se coucher : Pouvez-vous aider l'inspecteur Lafrite à répondre à ces questions ? Indication : les variables pro­po­si­tion­nel­les \(B\), \(P\) et \(N\) représentent les trois suspects avec la convention que la valeur de vérité V code l'innocence et F la culpabilité. Formaliser les déclarations de chacun des suspects et la validité de ces affirmations avec un table de vérité. Répondre à toutes les questions de l'inspecteur Lafrite.
Soit \(A\) et \(B\) deux variables propositionnelles. Soit le connecteur logique binaire \(\uparrow\) appelé incompatibilité ou non et et défini par : \[(A\uparrow B) \equiv \neg (A\wedge B)\] Exprimez les connecteurs \(\neg\), \(\wedge\) et \(\vee\) à l'aide du connecteur \(\uparrow\) uniquement.
Soit \(P,Q,R\) et \(S\) des variables propositionnelles. Vérifier que
  1. \(\neg \big(((P\wedge Q)\vee P)\vee R)\vee S\big)\equiv \big((\neg P\wedge \neg R)\wedge \neg S\big)\)
  2. \(\neg\big(P\then (Q\then R)\big)\equiv \big((P\wedge Q)\wedge \neg R\big)\)
Formalisez les affirmations suivantes en logique propositionnelle :
  1. (a) Bob a déchiffré le message d'Alice ou Alice est inquiète,
  2. (b) Bob a déchiffré le message d'Alice et Alice n'est pas inquiète,
  3. (c) Bob n'a pas déchiffré le message d'Alice et Alice est inquiète,
  4. (d) Bob n'a pas déchiffré le message d'Alice ou Alice n'est pas inquiète,
  5. (e) Si Bob a déchiffré le message d'Alice alors Alice n'est pas inquiète,
  6. (f) Bob n'a pas déchiffré le message d'Alice si Alice est inquiète.

Théorie des ensembles et prédicats

Introduction à la théorie des ensembles

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 à l'aide de règles de déduction logiques et d'autres assertions dont les axiomes. En complément de la logique pro­po­si­tion­nel­le, on enrichit le langage mathématique de symboles spécifiques à la théorie en précisant leur syntaxe et comment ils s'articulent avec la logique propositionnelle. Les ma­thé­ma­ti­ques seraient im­pra­ti­ca­bles si l'on s'in­ter­di­sait l'usage de la langue naturelle pour s'exprimer, mais le prix à payer pour cette liberté est d'être excessivement attentif à ce que l'on énonce.

Il est intéressant de noter que sur le terrain du langage, la ma­thé­ma­ti­que et l'informatique font en quelque sorte le chemin inverse. La nécessité de rigueur a contraint les mathématiciens à s'éloigner de la langue naturelle en développant un langage de plus en plus formel et contraint, alors que les informaticiens cherchent au contraire à développer des langages de programmation de plus en plus proches de la langue naturelle. Les langages de pro­gram­ma­tion sont en quelque sorte l'achèvement de ce qu'est censé être un langage ma­thé­ma­ti­que, tout au moins du point de vue lexical et syntaxique, les pro­gram­meurs en font la douloureuse expérience au quo­ti­dien, la moindre erreur est im­mé­dia­te­ment sanc­tion­née. Ceci explique éga­le­ment les nombreux points de convergence entre ces deux disciplines.

Une séquence de déductions logiques permettant d'établir de nouvelles assertions à partir d'as­ser­tions déjà acquises, initialement les axiomes, s'appelle une démonstration. 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 pro­po­si­tion­, ou encore corollaire lorsqu'il s'agit d'une con­sé­quen­ce directe d'un théorème. Stricto sensu, chaque résultat intermédiaire obtenu dans une démonstration constitue un théorème, mais nous ne mettons en évidence que ceux qui nous pa­rais­sent importants, les autres restent dans l'anonymat. Nous avons déjà vu plus haut trois méthodes communes sont utilisées pour faire une dé­mons­tra­tion, sans qu'elles soient ex­clu­si­ves*(*) Exemple ty­pi­que de l'ef­fort à fai­re pour le­ver les am­bi­guï­tés ou imp­ré­ci­sions de la lan­gue na­tu­rel­le. Sans cet­te pré­ci­sion, le lec­teur ne sait pas si ces trois mé­tho­des de dé­mons­tra­tion sont les seu­les pos­si­bles ou non. :

  1. Par modus ponens. Si une proposition \(P\) est vraie et que l'on a \(P\Rightarrow Q\), on en déduit que la proposition \(Q\) est vraie ;
  2. Par modus tollens (contraposition). Pour démontrer la proposition \(P\Rightarrow Q\), il peut être plus simple de démontrer la proposition \(\neg Q\Rightarrow P\) ;
  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\wedge \neg Q\) est vraie, prouvant ainsi que cette théorie est contradictoire d'après le tiers exclus ce qui invalide l'axiome.

Nous verrons au chapitre Combinatoire une autre méthode de démonstration appelée preuve par récurrence.

La théorie ma­thé­ma­ti­que dans laquelle nous discourons, tout au moins dans ce cours, est la théorie des ensembles de Zermello-Fraenkel (abrégée en théorie zf). 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és à 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 d'une trop grande liberté dans la construction des ensembles, a mis en péril l'édifice mathématique et a nécessité d'en fixer les règles.

Dans cette théorie absolument tous les objets manipulés sont identifiés à des ensembles. Nombres, fonctions, relations, vecteurs, etc. Cette théorie fournit un nombre limité d'axiomes et de règles de construction des ensembles, elle n'est pas la théorie des ensembles, mais plutôt un codage 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à.

L'objet de cette théorie n'est pas d'expliquer ce que sont les ensembles, 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é souvent proposé en master d'informatique. Dans la suite nous ne présenterons que les axiomes que nous utilisons in­ten­si­ve­ment, ils illustrent la démarche qui sous-tend cette théorie et dont la dimension systématique est très 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 exclus de la sacrifier sur l'autel du formalisme, elle est suffisante pour la licence. C'est celle du mathématicien allemand Georg Cantor qui fut l'un des pionniers sur cette ques­tion.

On appelle en­sem­ble toute collection \(X\) d'objets définis et discernables. Un tel objet est appelé élément ou membre de \(X\) et on dit aussi que l'objet appartient à \(X\).

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 décider si deux objets quelconques d'un ensemble sont égaux ou distincts. Ces deux conditions expriment le fait qu'un ensemble est totalement déterminé par ses éléments.

Les conditions définis et discernables font émerger deux relations spécifiques à la théorie des en­semb­les, respectivement l'appartenance notée \(\in\) et l'égalité notée \(=\). La phrase \(x\) est un élément de \(X\) est codée \(x\in X\) et la phrase \(x\) est égal à \(y\) est codée \(x=y\). Rien n'empêche un ensemble d'être lui-même l'élément d'un autre ensemble. On écrit souvent \(x\not\in X\) pour \(\neg (x\in X)\). Si \(x\) et \(y\) satisfont \(x=y\), cela entraîne qu'ils sont synonymes, on peut échanger leurs rôles dans n'importe quelle expression ma­thé­ma­ti­que sans rien changer à sa valeur logique. On écrit généralement \(x\not= y\) pour \(\neg(x=y)\).

D'autres symboles spécifiques à la théorie des ensembles sont utilisés, en particulier l'accolade ouv­ran­te \(\{\) et l'accolade fermante \(\}\). Quand on connaît explicitement les éléments qui définissent un ensemble \(X\), on peut le représenter par la liste de ses éléments entouré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 est appelée écriture en extension de \(X\). Les deux symboles sont chargés de sens, faire l'accolade est sy­no­ny­me d'embrasser et ceci désigne l'action qui consiste à entourer quelque chose ou quelqu'un avec ses bras \(\{\;\}\).

Comme un ensemble est entièrement déterminé par ses éléments, les répétitions éventuelles du même élément dans l'écriture en extension d'un ensemble sont redondantes, ainsi \[\{a,a,b,a,c\}=\{a,b,c\}.\] D'autre part, l'ordre dans lequel apparaissent les éléments d'un ensemble n'a aucune importance, par exemple : \[\{a,b,c\}=\{b,a,c\}=\{a,c,b\},\ \text{etc.}\]

Nous utiliserons dans ce cours deux symboles pour re­pré­sen­ter l'égalité, le symbole \(=\) et le symbole \(:=\) en deux parties. Le \(:\) qui précède l'égalité dans ce dernier a pour objectif de signifier au lecteur qu'il s'agit d'une définition d'un nouvel objet et que l'égalité entre les deux opérandes gauche et droit du symbole provient de cette définition. Ainsi on écrira \(3=1+2\) qui est une assertion et plutôt \(X:=\{a,b,c\}\) pour signifier que nous notons \(X\) l'ensemble constitué des trois objets \(a\), \(b\) et \(c\). C'est une notation bien commode héritée des concepteurs de langages de programmation comme le Pascal, qui ont eu l'idée bien inspirée de distinguer l'égalité de l'affectation.

Prédicats

Nous allons étudier la logique des prédicats ou logique du premier ordre dans le cadre du langage de la théorie des ensembles. On rajoute au lexique de la logique propositionnelle, les ensembles et les symboles spécifiques à la théorie des ensembles, à savoir \(=\), \(\in\), \(\{\), et \(\}\). Contrairement à la logique propositionnelle où les variables ne peuvent prendre leurs valeurs que dans l'ensemble \(\{\top,\bot\}\), les variables de la logique des prédicats peuvent prendre leurs valeurs dans un ensemble quelconque.

Un prédicat est un énoncé contenant des variables tel qu'en substituant chaque variable par une valeur choisie dans un ensemble, on obtient une proposition.

Un prédicat à \(q\) variables \(x_1,x_2,\ldots,x_q\) est généralement noté de manière préfixe \(P(x_1,x_2,\ldots,x_n)\). On conserve la même terminologie que pour la logique pro­po­si­tion­nel­le 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 variable a été interprétée dans un prédicat à \(q\) variables, on dispose alors d'un prédicat à \(q-1\) variables. Par exemple \(x\geq \pi\) est un prédicat \(P(x)\) à une variable \(x\) de l'ensemble des nombres réels \(\R\) et \(P(4)\) est une pro­po­si­tion­ vraie. L'énoncé \(n=2k\) est un prédicat \(P(n,k)\) à deux variables \(n\) et \(k\) dans l'en­sem­ble des entiers naturels \(\N\) et \(P(4,2)\) est une proposition vraie.

La théorie des ensembles de Zermello-Fraenkel distingue deux types de prédicats :

  1. Prédicat collectivisant : c'est un prédicat \(P(x)\) tel que les objets \(a\) qui satisfont la proposition \(P(a)\) forment un ensemble. Cet ensemble est alors noté

    \begin{equation} \{x\mid P(x)\}. \end{equation}
  2. Prédicat non-collectivisant : c'est un prédicat qui ne définit pas un ensemble.

Les axiomes de la théorie des ensembles élaborée par Zermello et Fraenkel ont pour objet de fournir une famille de prédicats col­lec­ti­vi­sants assez riche pour pouvoir recoder ce que les mathématiciens faisaient déjà mais en bridant la construction de nouveaux ensembles afin de ne pas créer de mons­tres gé­né­rant des paradoxes. A contrario, la théorie ne dit pas quels sont les prédicats qui ne sont pas collectivisants. Sont disqualifiés de fait tous les prédicats dont les en­sem­bles associés, s'ils existaient, permettraient de construire une contradiction. Cantor ne faisait pas ce distingo et avait énoncé le principe d'abstraction affirmant que tout prédicat définissait un ensemble, autrement dit que tout prédicat était collectivisant. Ce principe trop généreux engendrait justement des pa­ra­do­xes. Le plus célèbre est probablement le paradoxe de Russel : considérons \(P(x)\) le prédicat

\begin{equation} x\not\in x. \end{equation}

Supposons que \(P(x)\) soit collectivisant en \(x\). On dispose alors de l'ensemble

\[X:=\{x\mid x\not\in x\}.\]

et d'après le tiers exclus, la proposition \(X\in X\) doit être vraie ou fausse. Or si \(X\in X\) est vraie, l'ensemble \(X\) doit satisfaire le prédicat \(x\not\in x\), c'est-à-dire \(X\not\in X\) ce qui est contradictoire. Ré­ci­pro­que­ment, si \(X\not\in X\), l'ensemble \(X\) satisfait le prédicat \(x\not\in x\), il appartient donc à l'ensemble \(X\) ce qui est encore contradictoire.

La théorie des ensemble avait pour principal objectif de s'assurer que ce nouveau langage ma­thé­ma­ti­que n'aboutirait jamais plus à des contradictions. Mal­heu­reu­se­ment le logicien autrichien Kurt Gödel a mis fin à cet espoir en démontrant en 1931 que dans toute théorie ma­thé­ma­ti­que suffisamment riche pour coder l'ari­thmé­ti­que, il existe des propositions in­dé­ci­da­bles, c'est-à-dire telles que l'on ne peut pas démontrer qu'elles sont vraies ni qu'elles sont fausses. D'autre part une théorie ma­thé­ma­ti­que ne permet pas de prouver sa propre cohérence, c'est-à-dire qu'elle ne permet pas de prouver qu'elle n'engendre pas des paradoxes. Les con­sé­quen­ces des travaux de Gödel ont un impact tout aussi dé­vas­ta­teur en in­for­ma­ti­que, c'est ce que vous étudierez dans un cours de calculabilité.

Deux nouveaux symboles permettent de construire des propositions à partir d'un ensemble \(X\) et d'un prédicat \(P(x)\). 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:universel} \forall x\in X\ \ P(x) \end{equation}

qui code la proposition Pout tout élément \(x\) de l'ensemble \(X\), la proposition \(P(x)\) est vraie. Le quan­ti­fi­ca­teur existentiel \(\exists\) qui se lit il existe, et s'utilise dans l'expression

\begin{equation} \label{eq:existentiel} \exists x\in X\ \ P(x) \end{equation}

qui code la proposition il existe un élément \(x\) de l'ensemble \(X\) tel que la proposition \(P(x)\) est vraie.

Quand un quan­ti­fi­ca­teur précède une variable \(x\), on dit qu'elle est quantifiée et on parle alors de va­ria­ble muette ou anonyme au sens où elle peut être remplacée partout dans l'expression par n'im­por­te quelle autre lettre (qui ne joue pas déjà un rôle dans l'expression évidemment) sans en chan­ger le sens. On peut s'en convaincre en remplaçant \(x\) par \(y\) dans les deux expressions \((\ref{eq:universel})\) et \((\ref{eq:existentiel})\). Ces deux expressions sont donc bien des propositions et pas des prédicats.

Pour démontrer une proposition du type \(\forall x\in X\ \ P(x)\), on se donne un élément \(a\) quelconque de l'en­sem­ble \(X\) et on montre que \(P(a)\) est vraie. Comme \(a\) est quelconque il symbolise n'importe quel élé­ment de \(X\), ainsi si la proposition \(P(a)\) 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 \(a\) de l'en­sem­ble \(X\) tel que \(P(a)\) est vraie, il peut d'ailleurs en exister plus d'un.

La négation des deux expressions \((\ref{eq:universel})\) et \((\ref{eq:existentiel})\) est conforme à la négation des phrases cor­res­pon­dan­tes dans la langue naturelle. Soit \(X\) un ensemble et \(P(x)\) un prédicat de la variable \(x\) définie sur \(X\), alors \begin{align} \label{eq:negA}\neg(\forall x\in X\ \ P(x))&\ \equiv\ \exists x\in X\ \ \neg P(x)\\ \label{eq:negE}\neg(\exists x\in X\ \ P(x))&\ \equiv\ \forall x\in X\ \ \neg P(x) \end{align}

Illustrons l'équivalence logique \((\ref{eq:negA})\). La négation de la proposition tous les étudiants comprennent le cours est bien sûr il existe un étudiant qui ne comprend pas le cours plutôt que tous les étudiants ne comprennent pas le cours qui prête à interprétation, veut-on dire qu'aucun étudiant ne comprend le cours ou que certains étudiants ne comprennent par le cours ? 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 de dire il existe au moins un étudiant qui ne comprend pas le cours. Ainsi, quand on veut démontrer qu'une pro­po­si­tion \(\forall x\in X\ \ P(X)\) est fausse, autrement dit que sa négation est vraie, il suffit d'exhiber un élément \(a\) tel que \(\neg P(a)\), qu'on appelle un contre-exemple.

Passons à l'équivalence logique \((\ref{eq:negE})\). La négation de la proposition il existe un éléphant rose peut ê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 aucun éléphant n'est rose.

Ces différents énoncés montrent au passage que la variable \(x\) est bien muette, nous ne l'avons jamais mentionnée pour exprimer \((\ref{eq:negA})\) ou \((\ref{eq:negE})\). La langue française est truffée de chausse-trappes, et il est très facile de faire un raisonnement fallacieux en lui donnant l'apparence de justesse — on parle de sophisme — ce que ne manquent jamais de faire les po­li­ti­ciens. Le langage ma­thé­ma­ti­que ne peut laisser la place qu'à une unique interprétation.

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)\) défini sur deux variables réelles \(x\) et \(y\) suivant : \[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 réel \(x\), le nombre réel \(y\) défini par \(y=1-x^2\) 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 se dispenser de cette étape) : \begin{equation}\label{eq:EA} \exists y\in\R\ (\forall x\in\R\quad x^2-y = 1). \end{equation} Cette nouvelle proposition est fausse. En effet, 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 \(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 propager une négation comme \((\ref{eq:negA})\) ou \((\ref{eq:negE})\) pour des prédicats à plusieurs variables.

La continuité simple d'une fonction \(f:\R\rightarrow\R\) s'écrit \[\forall x\in X\quad\forall\varepsilon>0\quad\exists\delta>0\quad\forall y\in X\quad |x-y|<\delta\Rightarrow |f(x)-f(y)|<\varepsilon.\] Alors que la continuité uniforme s'écrit \[\forall\varepsilon>0\quad\exists\delta>0\quad\forall x\in X\quad\forall y\in X\quad |x-y|<\delta\Rightarrow |f(x)-f(y)|<\varepsilon.\] Écrivez la négation de ces deux propositions.
Soit \(X\) un ensemble et \(P(x)\) et \(Q(x)\) deux prédicats. Écrivez la négation des deux propositions suivantes : \begin{align*} \forall x\in X&\quad P(x)\Rightarrow Q(x),\\ \exists x\in X&\quad P(x)\Rightarrow Q(x). \end{align*}

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

Soient \(X\) et \(Y\) deux ensembles. On dit que \(X\) est inclus dans \(Y\) ou que \(X\) est une partie de \(Y\) ce que l'on note \(X\subseteq Y\) ou \(Y\supseteq X\) si et seulement si \begin{equation} \label{eq:inclusion} \forall x\in X\quad x\in Y. \end{equation} On dit également que \(Y\) contient \(X\) ou que \(X\) est un sous-ensemble de \(Y\).

On note \(X\not\subseteq Y\) plutôt que \(\neg(X\subseteq Y)\). Dans l'assertion \(X\) est une partie de \(Y\), il n'y a plus mention de la variable \(x\) de la proposition \((\ref{eq:inclusion})\), elle est donc bien muette. L'axiome d'extension dit que deux en­semb­les sont égaux si et seulement s'ils ont exactement les mêmes éléments :

Soient \(X\) et \(Y\) deux ensembles, alors \(X=Y\) si et seulement si \begin{equation} \label{eq:egaliteensembles} (X\subseteq Y)\wedge (Y\subseteq X). \end{equation}

C'est cet axiome que l'on applique quand on veut démontrer que deux ensembles \(X\) et \(Y\) sont égaux, on démontre 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.

Soient \(a\) et \(b\) deux objets. Le prédicat \((x=a)\vee(x=b)\) est col­lec­ti­vi­sant en \(x\). L'ensemble des éléments qui le satisfont est noté \(\{a,b\}\), \[\{a,b\}=\{x\mid (x=a)\vee(x=b)\}.\] Il est appelé paire \(\{a,b\}\).

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 réunion plus loin, que l'on peut définir l'écriture en extension d'un ensemble.

L'axiome de sélection 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 version affaiblie du principe d'abstraction de Cantor dans laquelle tout prédicat définit un ensemble du moment que les objets \(x\) sont collectés dans un ensemble pré­exis­tant :

Soit \(X\) un ensemble et \(P(x)\) un prédicat. Le prédicat \((x\in X)\wedge P(x)\) est collectivisant en \(x\). L'ensemble des éléments \(x\) de \(X\) tels que \(P(x)\) est vrai est noté \begin{equation} \label{eq:compr} \{x\in X\mid P(x)\}. \end{equation}

On peut donc collecter les éléments d'un ensemble \(X\) qui satisfont un prédicat \(P(x)\). Il est clair qu'il s'agit d'un sous-ensemble de \(X\) et que cet axiome ne permet pas donc pas de créer un ensemble trop gros si \(X\) a été construit conformément à la théorie. L'écriture \((\ref{eq:compr})\) d'un ensemble est dite écriture en comp­ré­hen­sion de l'ensemble.

Une fois étudiées les fonctions \(f:X\to Y\) au chapitre Re­la­tions, app­li­ca­tions, on écrira \[\{f(x)\mid x\in X\}\] pour l'ensemble \[\{y\in Y\mid \exists x\in X\ y=f(x)\}.\] Ainsi l'ensemble \(\{3n\mid n\in \N\}\) décrit l'ensemble des entiers naturels multiples de \(3\). Certains langages de programmation autorisent une écriture similaire à l'écriture en compréhension pour construire de nouveaux objets. Par exemple en Python la liste \(A\) ci-dessous est définie en compréhension :
A = [n for n in range(10) if n % 2 == 0]
En notant \(X=\{0,1,2,3,4,5,6,7,8,9\}\) et \(P(n)\) le prédicat \(\exists k\in\N\ n=2k\), la cons­truc­tion de la liste \(A\) des nombres entiers de \(X\) qui sont pairs correspond à celle de l'en­sem­ble \(A=\{n\in \N\mid \exists k\in\N\ n=2k\}.\)

L'axiome de la réunion permet de collecter tous les éléments des différents ensembles qui ap­par­tien­nent à un ensemble donné.

Soit \(Y\) un ensemble. Le prédicat \(\exists X\ \ ((X\in Y)\wedge(x\in X))\) est col­lec­ti­vi­sant en \(x\). Il existe donc un ensemble noté \begin{equation}\label{eq:union} \displaystyle\bigcup_{X\in Y}X \end{equation} qui contient tous les éléments appartenant aux éléments de \(Y\). Il est appelé réunion de \(Y\).

Quand l'ensemble \(X=\{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\},\varnothing\}\) est l'en­sem­ble \(\{a,b,c,d\}\). Plus généralement, l'écriture en extension est obtenue grâce à cet axiome.

Soit \(X\) un ensemble. L'ensemble \(\{x\in X\mid x\not= x\}\) existe et ne dé­pend pas de \(X\). On l'appelle l'en­sem­ble vide et on le note \(\varnothing\).
À un ensemble \(X\) on associe l'ensemble \(\varnothing_X:=\{x\in X\mid x\not=x\}\) qui formalise l'idée naïve qu'il ne contient aucun élément (aucun élément de l'ensemble \(X\) ne satisfait le prédicat \(x\not=x\)). Nous allons montrer que cet ensemble ne dépend pas de \(X\). D'après l'axiome de la paire, on peut définir la paire \(\{X,Y\}\) puis l'ensemble \(U=X\cup Y\) d'après l'axiome de réunion. Soit \(P(x)\) le prédicat \(\neg (x=x)\). L'axiome de sélection permet de construire les deux ensembles \(\{x\in X\mid P(x)\}\) et \(\{x\in Y\mid P(x)\}\). La proposition \[\forall x\in U\quad x\in X \Rightarrow x\in Y\] est vraie puisque \(x\in X\) est fausse, on a donc montré que \(X\subseteq Y\) et il suffit d'échanger le rôle de \(X\) et \(Y\) pour obtenir \(Y\subseteq X\). Nous venons donc de démontrer que ces deux ensembles sont égaux (cf. \((\ref{eq:egaliteensembles})\)).
Soient \(X\) et \(Y\) deux ensembles. La différence entre les ensembles \(X\) et \(Y\) est l'ensemble \(\{x\in A\mid x\not\in B\}\). On le note \(X\setminus Y\) ou encore \(\complement_XY\). Si de plus \(Y\subseteq X\), alors la différence \(X\setminus Y\) est appelée complémentaire de \(Y\) dans \(X\).

Exemples : \(X\setminus X=\varnothing\) et \(X\setminus\varnothing=X\) ou encore \(\{a,b\}\setminus\{a\}=\{b\}\).

Soient \(X\) et \(Y\) deux ensembles. L'in­ter­sec­tion des ensembles \(X\) et \(Y\) est l'ensemble \(\{x\in X\mid x\in Y\}\). On le note \(X\cap Y\).

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 bri­tan­ni­que 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 :

 Y
 
Diagramme de Venn et opérations ensemblistes sur deux ensembles \(X\) et \(Y\). Ensemble : aucune.

L'axiome des parties 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\).

Soit \(X\) un ensemble. Le prédicat \(Y\subseteq X\) est collectivisant en \(Y\). Il existe donc un ensemble noté \(\def\P={\mathscr P}\P(X)\) tel que \begin{equation} \P(X)=\{Y \mid Y\subseteq X\} \end{equation} Cet ensemble est appelé ensemble des parties de \(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 \(\P(X)=\{\varnothing,\{a\},\{b\},\{c\},\{a,b\},\{a,c\},\{b,c\},X\}\). D'autre part, l'ensemble des par­ties de l'ensemble vide \(\P(\varnothing)=\{\varnothing\}\) qui n'est pas l'ensemble vide puisqu'il contient l'élément \(\varnothing\).

Comme pour n'importe quel ensemble, la paire \(\{x,y\}\) est égale à la paire \(\{y,x\}\), l'ordre dans lequel nous écrivons les éléments d'un ensemble n'a pas d'importance. On souhaite 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 théorème suivant.

Soient \(x\) et \(y\) deux objets. La paire \(\{\{x\},\{x,y\}\}\) est appelé couple \(x\), \(y\) et on le note \((x,y)\). Soient \(X\) et \(Y\) deux ensembles. L'ensemble des couples \((x,y)\) tels que \(x\in X\) et \(y\in Y\) existe, on le note \(X\times Y\) et on l'appelle produit car­té­sien de \(X\) et \(Y\).

Le premier (resp. deuxième) terme d'un couple \((x,y)\) s'appelle la première projection (resp. deuxième projection) du couple \((x,y)\). On peut généraliser cette construction pour obtenir des \(n\)-uplets avec \(n\in\N\).

Démontrez que \((x,y)=(x',y')\then (x=x')\wedge(y=y').\)
À partir de l'ensemble vide \(\varnothing\), on peut construire inductivement les ensembles ci-dessous en définissant chaque nouvel ensemble à l'aide du précédent \(X\) par la réunion \(X\cup\{X\}\) : \begin{equation} \begin{matrix} \varnothing & \{\varnothing\} & \{\varnothing,\{\varnothing\}\} & \{\varnothing,\{\varnothing,\{\varnothing\}\}\} & \{\varnothing,\{\varnothing,\{\varnothing,\{\varnothing\}\}\}\} & \cdots\\ 0 & 1 & 2 & 3 & 4 &\cdots\\ & \{0\}&\{0,1\}&\{0,1,2\}&\{0,1,2,3\}&\cdots \end{matrix} \end{equation}

En identifiant \(\varnothing\) à 0 et chaque nouvel ensemble à l'entier suivant, on code les entiers naturels les uns après les autres. Cette construction des entiers naturels est due au mathématicien John Von Neumann. L'axiome de l'infini assure que l'en­sem­ble de tous ces ensembles existe. Nous le retrouverons au chapitre Combinatoire.

Un dernier axiome et nous achèverons là cette introduction à la théorie des ensembles. L'axiome du choix nous autorise à extraire un élément de son choix de chaque ensemble d'une famille d'ensembles pour en faire un ensemble. Cet axiome peut être intégré ou non dans la théorie, si c'est le cas elle est appelée théorie zfc.

Formalisation du Sudoku

Le calcul des prédicats permet de modéliser certains problèmes de manière bien plus simple que le calcul propositionnel. Considérons le problème du Sudoku. C'est un jeu solitaire qui consiste à comp­lé­ter une grille de \(9\times 9\) cases réparties en 9 régions carrées \(3\times 3\) par des nombres compris entre 1 et 9 en respectant certaines règles :

  1. chaque ligne doit contenir exactement chacun des 9 chiffres de 1 à 9;
  2. chaque colonne doit contenir exactement chacun des 9 chiffres de 1 à 9;
  3. chaque région doit contenir exactement chacun des 9 chiffres de 1 à 9.

La grille ci-dessous contient 26 indices, il faut compléter les autres cases.
74 3
38
5 6
3 4
94 1 2 3 5
6 9
5 8 7
5 3 9
4 5 8

Exemple de grille de Sudoku \(9\times 9\) à compléter

La formalisation du problème du Sudoku se fait avec un langage adapté. Les constantes sont les 9 entiers de l'ensemble \({\mathscr C}:=\{0,1,2,\ldots,9\}\) et les prédicats sont des prédicats à trois variables \(S(l,c,n)\) de l'ensemble \(\def\CC{{\mathscr C}}\CC\) auxquels on donne la signification suivante : \(S(l,c,n)\) est vrai si et seulement si la case à la ligne \(l\) et à la colonne \(c\) contient le nombre \(n\). C'est bien plus économique que la logique propositionnelle avec laquelle il aurait fallu définir une variable propositionnelle pour chaque valeur possible dans chaque case, soit \(9\times 9\times 9=243\) variables.

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) :

\begin{align*} &\forall (l,c)\in\CC^2\ \exists n\in\CC\quad S(l,c,n),\\ &\forall (l,c,n,n')\in\CC^4\quad S(l,c,n)\wedge S(l,c,n')\then n=n'. \end{align*}

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

\begin{align*} &\forall (l,c,c',n)\in\CC^4\quad S(l,c,n)\wedge S(l,c',n)\then c=c',\\ &\forall (l,l',c,n)\in\CC^4\quad S(l,c,n)\wedge S(l,c,n)\then l=l'. \end{align*}

Pour la partie de la règle (3) disant que chaque nombre apparaît au plus une fois par région, c'est un peu plus compliqué puisque les régions sont moins faciles à mettre en évidence. On peut régler ce problème de bien des manières. Par exemple en introduisant une fonction \(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 \begin{align*} &\forall (l,l',c,c',n)\in\CC^5\quad S(l,c,n)\wedge S(l,c',n)\wedge r(i,j)=r(i',j')\then (l,c)=(l',c'). \end{align*}

Chacun des 26 indices 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,3,8)=V\).

Le langage Prolog est basé sur le calcul des prédicats et permet de résoudre ce type des problèmes de cette nature de manière automatique. La théorie de la démonstration et l'intelligence ar­ti­fi­ciel­le développent des techniques pour répondre à des problèmes de cette nature en formalisant le langage du raisonnement.

On cherche à placer \(8\) reines sur un échiquier sans qu'elles ne se mettent en échec. En vous inspirant de la formalisation du Sudoku, formalisez le problème des huit reines à l'aide de la logique des prédicats.
Formalisez le problème des Tee-shirts avec la logique des prédicats.