Mathématiques pour l'informatique - Raisonnement et logique propositionnelle

OA Mathématiques pour l'informatique - Raisonnement et logique propositionnelle

Raisonnement et logique propositionnelle

Introduction

Trois robots, xam, arg et bax travaillent pour un constructeur automobile et sont dotés d'un module de synthèse vocale 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 faux et quand il fonctionne, son diagnostic est toujours vrai. On sait qu'il y a au moins un robot défectueux et au moins un robot en bon état. Quel(s) robot(s) 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 :

La construction d'objets abstraits qui servent de modèles descriptifs pour la compréhension et l'étude de phénomènes physiques.
La recherche de propriétés de ces objets abstraits qui permettent, d'une part de s'assurer de leur adéquation avec la réalité physique et d'autre part d'anticiper des résultats concrets. Les modèles sont alors des modèles prédictifs.
La validation de ces propriétés par des démonstrations.
La résolution de problèmes grâce aux propriétés des objets qui ont permis de les modéliser.

Le mathématicien pur contestera peut-être 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 très grande majorité des théories mathématiques a pour origine des problèmes bien réels engendrant de nouveaux questionnements qui parfois s'épanouissent au sein de théories autonomes. La dichotomie entre mathématiques pures et appliquées n'a donc pas de raison d'être et si distinction il y a, les deux vivent depuis longtemps en parfaite symbiose.

Selon la théorie de l'évolution de Lamarck, la fonction créant l'organe, le langage mathématique s'est progressivement structuré pour que cette science puisse se développer suivant ces quatre axes. Les mathématiques s'imposent naturellement en informatique dès que l'on cherche à analyser un problème, à élaborer des méthodes de résolution et à valider les résultats 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 langages informatiques, la langue naturelle reste indispensable pour animer la partition. Ce métalangage est totalement formaté par et pour le raisonnement.

Que ce soit en informatique ou en mathématiques, l'écrit est par essence le principal vecteur de communication. La conséquence de ce fait indiscutable est qu'aucune méthode d'apprentissage, aussi innovante soit-elle, ne pourra remplacer une pratique intensive de la lecture et de l'écriture pour progresser dans ces deux disciplines.

Les règles de construction des mots, des phrases et plus généralement des langues naturelles qui occupent les grammairiens ont leur pendant en mathématiques et en informatique. Les mathématiciens se sont intéressés à la théorie de la démonstration dès le début du xx^ème siècle et les informaticiens à la théorie des langages dans les années 1950. Les questions sur la nature du calcul ont largement contribué aux interactions entre les deux disciplines dans le cadre de la théorie de la calculabilité et l'isomorphisme de Curry-Howard établit des liens formels entre une démonstration dans un système logique et un programme dans un modèle de calcul, autrement dit

prouver\(\ \iff\ \)programmer

Ce résultat ne sera probablement 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 mathématique concerne les ambiguïtés et la justesse des propos. Les ambiguïtés sont inhérentes aux langues naturelles et sont d'ailleurs largement exploitées dans la rhétorique (allusions, sous-entendus, jeux de mots, sophismes, etc.) alors qu'elles sont bannies du langage mathématique et des langages de programmation. Il est indispensable de les lever dès qu'un énoncé peut être interpré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 mathématiques qui emploient des tournures de phrases rarement utilisées dans le langage commun, comme si et seulement si, deux-à-deux disjoints, un et un seul, non-vide, etc. La logique naturelle n'est pas tout à fait celle de la logique classique des mathématiques, il existe d'ailleurs des logiques mathématiques (dites non-classiques par opposition) dont certaines ont précisément pour objet d'être plus proches de celle que nous pratiquons au quotidien. Là aussi, il est nécessaire de clarifier certaines situations. Notons que les problèmes d'interprétation de la logique ne concernent pas que les mathématiques, mais parfois les tribunaux.

Pour baptiser les objets que l'informaticien/mathématicien construit, les mots sont choisis avec beaucoup de précaution et sont censés être en adéquation avec l'acception qu'ils ont communément. Pourtant certaines distorsions existent parfois entre le sens que nous donnons à un mot et celui qu'il a en mathématiques, ce qui peut être une source d'erreurs ou de confusion. D'autre part, certains mots désignent des objets mathématiques différents selon le contexte où ils sont employés. Il faut en être conscient et comprendre le rôle réellement capital des définitions qui précisent leur sens dans un environnement particulier. Ceci explique la structuration litanique des textes mathématiques 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'informatique. 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éfinies formellement mais qui sont bien connues du lecteur, ou qui sont censées l'être. Ce n'est pas contraire à ce qui se fait dans tout apprentissage, la pratique de la conduite d'un véhicule est un atout pour en comprendre le fonctionnement. Dans la suite, si certains objets mathématiques sont construits à l'aide d'outils qui auraient dû ê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 propositionnel

Nécessité d'un cadre formel

L'étymologie du mot logique dévoile les mots raison et langage. La logique est à la base de l'articulation du discours mathématique et du fonctionnement atomique d'un ordinateur, il n'y a rien de surprenant à ce qu'elle se soit épanouie sur le formidable terrain de jeu qu'est l'informatique où elle est omniprésente. Les combinaisons de propositions à l'aide de connecteurs logiques constituent la première strate du raisonnement mathématique et de la construction des circuits électroniques. Il s'agit d'un langage à part entière, c'est le langage du calcul propositionnel dont nous allons fixer les règles de composition. Nous aborderons d'abord les aspects mathématiques, le chapitre Calcul booléen en donnera une vision plus proche de l'informatique et de l'électronique avec l'algèbre de Boole, les fonctions booléennes et les circuits logiques.

De manière analogue aux langues naturelles, un énoncé mathématique ou un programme informatique doit respecter :

Des règles lexicales. Elles régissent l'usage des signes et symboles (l'orthographe) pour constituer des lexèmes ou unités lexicales (nombres, fonctions, identifiants, variables, opérateurs, etc.) ;
Des règles syntaxiques. Elles régissent la composition des phrases (la grammaire) à partir des lexèmes (expressions arithmétiques, logiques, structures de contrôle, etc.) ;
Des règles sémantiques. Tout énoncé doit être interprété, avoir une signification (un sens).

Pour commencer, nous allons mettre en évidence les problèmes liés à la sémantique de la logique en langue naturelle et qui vont nous amener à la reconsidérer dans le cadre du langage du calcul propositionnel.

Une proposition est un énoncé auquel on peut attribuer une valeur de vérité vrai ou faux.

Il est important de noter dans cette définition informelle qu'il est possible d'attribuer une valeur de vérité à une proposition. 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 consubstantielle à la proposition. Certains auteurs parlent d'assertion pour une proposition, mais nous préférons ici réserver ce terme pour désigner une proposition énoncée comme vraie. Une assertion est donc une affirmation, ce qui rend son usage conforme à l'acception de ce terme en français.

À titre d'exemples voici quelques énoncés dont certains sont des propositions, d'autres non pour cette définition :

Il pleut,
Pourquoi le poulet a-t-il traversé la route ?
Ce chapitre est trop long à lire,
\(\def\then{{\;\Rightarrow\;}}\def\iff{{\;\Leftrightarrow\;}}1+2=3\),
Ce cours sera en ligne le 24 février 3016,
L'ensemble des nombres algébriques est dénombrable,
Si les poules avaient des dents, alors j'irais sur la lune,
À la montagne, on est plus vite en haut qu'à pied.
Je mens,
\(0\,(\,4=-1\),
Cette phrase n'a pas de valeur de vérité,
\(1+\sqrt{x} > 4\)
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 syntaxiquement. 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 proposition, on utilise dans ce cas le terme de prédicat ou d'énoncé contingent, qui est le centre d'étude du prochain chapitre.

Tous les autres énoncés sont des propositions, mais il n'est pas toujours possible de leur affecter une valeur de vérité sans autres considérations. En effet, la valeur de vérité de la proposition #1 dépend implicitement du contexte, le lieu et le moment, tout comme celle de la proposition #3 qui dépend du lecteur. Il est donc délicat de les considérer comme des propositions mathématiques stricto sensu. La proposition #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 proposition #5 est illusoire (ce qui ruine au passage mes espoirs de postérité). La proposition #6 demande une certaine connaissance de l'arithmétique pour établir qu'elle est vraie. La proposition #7 est vraie du point de vue du logicien, mais peut sembler absurde, voire fausse pour le lecteur lambda. Les propositions #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 proposition Je suis un menteur ne peut être vraie ou fausse sans aboutir à une contradiction. mais cela n'a rien de systématique, par exemple la proposition #13 est fausse.

Il apparaît que l'interprétation d'une proposition en langue naturelle n'est pas un exercice trivial, loin s'en faut. Toujours dans ce cadre, nous allons voir qu'il est également délicat d'analyser les énoncés contenant des connecteurs logiques pourtant omniprésents dans nos langues naturelles. Considérons les phrases suivantes :

Le cassis ou le poivre sont des baies.
Je travaille ou je me repose.
Apprenez votre cours ou vous aurez une mauvaise note.
Alice et Bob sont mariés.
Les étudiants dont la note en maths est supérieure à 7 et inférieure à 12.
Je suis déçu du résultat du contrôle continu et je jette toutes les copies.
Le facteur dépose le courrier donc le chien aboie.
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 certitude, il est donc difficile de lui attribuer une valeur de vérité. Le connecteur et de l'énoncé #5 code une énumération et pas une simple conjonction. De même, la conjonction de l'énoncé #6 induit une conséquence et celle de l'énoncé #8 induit une obligation.

Un connecteur logique est dit vérifonctionnel si la valeur de vérité de la proposition dans laquelle il apparaît dépend exclusivement des valeurs de vérité des propositions qu'il connecte.

En général les connecteurs logiques des langues naturelles ne sont pas vérifonctionnels. Supposons par exemple que la proposition Le facteur dépose le courrier et la proposition le chien aboie soient toutes deux vraies. Si la proposition Le facteur dépose le courrier donc le chien aboie est très certainement vraie, la proposition Le chien aboie donc le facteur dépose le courrier est probablement fausse. Ainsi, en logique naturelle, d'autres éléments que la valeur de vérité des propositions connectées interviennent pour fixer la valeur de vérité de leur composition. Dans le langage mathématique, les connecteurs doivent être vérifonctionnels. Cette exigence élémentaire peut créer une césure entre la logique naturelle et la logique mathématique.

En anticipant un peu sur l'étude des connecteurs logiques, la valeur de vérité d'une proposition contenant le connecteur logique d'implication peut suprendre, ainsi la proposition \[({\color{#EEF}1+2=3})\ \then\ {(\color{#EEF}\text{la Terre est ronde}})\] est vraie, alors qu'il n'y a aucun lien de cause à effet entre les deux propositions connectées qui sont toutes les deux vraies. Pire, la proposition \[ ({\color{#EEF}1+2=0})\ \then\ {(\color{#EEF}\text{la Terre est ronde}}) \] est également vraie, alors que l'expression \(1+2=0\) est fausse (si on considère l'addition des entiers naturels) !

Nous avons déjà constaté que la valeur de vérité d'une proposition n'est pas consubstantielle à sa structure 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 proposition, 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 permanence en mathématiques. Même pour un simple calcul 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, seule l'application correcte de l'addition et de l'a multiplication dans l'expression abstraite importe. Le distinguo entre la syntaxe et la sémantique de l'expression \(196\) est peut-être difficile à percevoir pour le lecteur car la confusion a été volontairement entrenue 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'égrener les chiffres un, neuf, six. On encapsule ainsi forme et fond. C'est la raison exacte de l'apprentissage de la lecture des mots et des nombres, 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 leur écriture en chiffres romains, on fait ressurgir la séparation entre syntaxe et sémantique  :

\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 percevons sans peine sous la forme décimale \(196\), et pourtant les deux représentations codent exactement le même nombre.

Trouvez des exemples de propositions contenant un ou inclusif en langue naturelle.

En voilà quelques-unes :

J'aime me promener en forêt ou à la montagne.
Le néon ou le radon sont des gaz.
\(12\) est un multiple de \(3\) ou \(4\).
On peut trouver cet article en grande surface ou sur le net.
Demain il y aura du vent ou du soleil.

La conclusion de cette section est qu'une proposition logique n'est pas aisée à appréhender dans le cadre de la langue naturelle.

Syntaxe du calcul propositionnel

Concentrons-nous pour le moment sur les aspects lexicaux et syntaxiques du langage, nous reviendrons sur l'aspect sémantique un peu plus loin. Il faut tout d'abord disposer d'un lexique de symboles — un alphabet — ces symboles sont répartis en quatre catégories :

Les constantes \(\top\) et \({\bot}\).
Les variables propositionnelles ou propositions atomiques que l'on décrit généralement à l'aide de lettres de l'alphabet latin. Elles sont en nombre fini et ne peuvent prendre que les deux valeurs \(\top\) ou \({\bot}\).
Les parenthèses \((\) et \()\).
Les connecteurs logiques \(\neg\), \(\vee\), \(\wedge\), \(\Rightarrow\), \(\Leftrightarrow\), \(\oplus\), \(\uparrow\), \(\downarrow\).

Voilà pour le lexique, passons à la syntaxe. À partir des variables propositionnelles, on peut créer de nouvelles expressions 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 propositions qu'il permet de connecter, on parle aussi de connecteur \(q\)-aire.

Si \(q=1\), le connecteur est dit unaire, si \(q=2\), binaire, si \(q=3\) ternaire, 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 propositionnelles qu'elle contient. Les variables propositionnelles ne pouvant prendre qu'un nombre fini de valeurs (\(\top\) ou \({\bot}\)), un connecteur logique est entièrement caractérisé par les différentes valeurs possibles de l'expression suivant les valeurs des variables qu'il connecte. Notons que l'on ne peut pas caractériser les opérateurs arithmétiques de cette manière, l'addition dans \(\def\Z{{\Bbb Z}}\Z\) par exemple, car l'ensemble des valeurs possibles des variables est infini.

Il n'est pas nécessaire d'étudier l'analyse combinatoire, pour vérifier qu'il y a \(2^q\) combinaisons possibles pour les valeurs des \(q\) variables propositionnelles d'un connecteur \(q\)-aire, et donc \(2^{2^q}\) façons différentes de définir un connecteur \(q\)-aire. En effet pour chacune des \(2^q\) valeurs possibles du \(q\)-uplet constitué des \(q\) variables, l'expression peut prendre \(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\)

\(\top\)

\(\bot\)

\(\top\)

\(\bot\)

\(\top\)

\(\bot\)

\(\top\)

\(\bot\)

\(\top\)

\(\bot\)

\(\top\)

\(\bot\)

\(\top\)

\(\bot\)

\(\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 l'expression \(\star_2\; P\) prend exactement les mêmes valeurs que \(P\), le connecteur \(\star_2\) est ainsi l'identité. Le seul connecteur qui ne soit pas trivial est donc \(\star_3\), c'est la négation logique.

Les deux connecteurs binaires \(\diamond_{1}\) et \(\diamond_{16}\) sont constants, les connecteurs \(\diamond_{4}\) et \(\diamond_{13}\) ne dépendent que de la valeur du premier opérande \(P\) et les connecteurs \(\diamond_{6}\) et \(\diamond_{11}\) ne dépendent que de la valeur du deuxième opérande \(Q\). Ces \(6\) opérateurs ont donc peu d'intérêt, mais il en reste malgré tout 10. Sept d'entre eux sont baptisés car ils sont communément utilisés en Mathématiques et/ou en Informatique et/ou en Électronique. On a finalement huit connecteurs usuels et selon le contexte ou la discipline, on en utilise tout ou partie :

Connecteur	Nom	Symbole	Lecture	Usage
\(\star_3\)	négation	\(\neg\)	non	M\|I\|É
\(\diamond_2\)	conjonction	\(\wedge\)	et	M\|I\|É
\(\diamond_8\)	disjonction	\(\vee\)	ou	M\|I\|É
\(\diamond_{14}\)	implication	\(\Rightarrow\)	implique	M\|I
\(\diamond_{10}\)	équivalence	\(\Leftrightarrow\)	équivalent	M\|I
\(\diamond_{7}\)	disjonction exclusive	\(\oplus\)	ou exclusif	I\|É
\(\diamond_{15}\)	non conjonction	\(\uparrow\)	non et	I\|É
\(\diamond_{9}\)	non disjonction	\(\downarrow\)	non ou	I\|É

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 certains ouvrages.

Quand un connecteur est placé avant ses opérandes, on dit qu'il est en notation préfixe, c'est le cas de l'opérateur unaire de négation \(\neg\). Quand un connecteur est placé après ses opérandes, 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 propositionnelle, on écrit donc plus volontiers \(P\Rightarrow Q\) que \(P\ Q\ \Rightarrow\), bien que la notation postfixe soit très utilisée en informatique, elle permet en effet de se passer des parenthèses et d'évaluer très facilement une expression (ce point sera étudié en cours d'algorithmique de deuxième année).

Une formule ou expression bien formée, est définie inductivement par les règles de réécriture suivantes :

On appelle formule atomique ou atome toute formule \(P\) réduite à une simple variable propositionnelle.

On appelle littéral tout atome \(P\) ou sa négation \(\neg P\). Dans le premier cas il est dit positif, dans le second cas négatif.

On appelle clause conjonctive (resp. clause disjonctive) toute formule qui est une conjonction (resp. disjonction) de littéraux. Une clause désigne soit une clause conjonctive soit une clause disjonctive.

Soit \(P\), \(Q\) et \(R\) trois variables propositionnelles. La formule \(Q\) est une formule atomique, la formule \((P\vee(\neg Q\wedge (R\wedge\neg P)))\) contient les littéraux positifs \(P\) et \(R\) et les littéraux négatifs \(\neg Q\) et \(\neg P\). La formule \(((P\vee Q)\vee\neg R)\) est une clause disjonctive alors que la formule \(P\wedge\neg Q\) est une clause conjonctive. Notons qu'une clause qui ne contient qu'un littéral est à la fois conjonctive et disjonctive.

Analyse d'une formule

Une expression comme \begin{equation} \label{eq:ex1} ((P\Rightarrow Q) \wedge (P\vee \neg R)) \end{equation} est suffisamment courte pour qu'une simple lecture suffise à nous convaincre qu'il s'agit bien d'une formule de la logique propositionnelle. Les exercices que l'on peut traiter à la main en mathématiques dans ce domaine se préoccupent rarement de ce type de question, c'est le calcul littéral qui est privilégié. C'est une tout autre histoire en informatique, c'est une machine qui doit analyser de telles expressions et elles ne se limitent pas à une poignée de symboles.

Avant même d'automatiser le processus, problème qui sera abordé en théorie des langages, il faut savoir démontrer qu'une expression est bien formée. Il faut être en mesure de décrire comment elle a été construite à partir des \(5\) règles fournies dans la définition d'une formule. On peut partir du bas avec les atomes et les constantes en construisant successivement de nouvelles formules (analyse ascendante) jusqu'à obtenir la formule souhaitée, ou du haut, en décomposant la formule et en recommençant sur chaque sous-formule (analyse descendante).

Voici une séquence de règles possible en analyse ascendante. À chaque étape, on définit une nouvelle formule qui sera exploitée dans la construction des formules suivantes. La règle appliquée est indiquée au-dessus de l'affectation : \begin{align*} f_1&\ {\color{#FF8}\overset{R_1}{\leftarrow}}\ P\\ f_2&\ {\color{#FF8}\overset{R_1}{\leftarrow}}\ Q\\ f_3&\ {\color{#FF8}\overset{R_5}{\leftarrow}}\ (f_1\then f_2)\\ f_4&\ {\color{#FF8}\overset{R_1}{\leftarrow}}\ R\\ f_5&\ {\color{#FF8}\overset{R_4}{\leftarrow}}\ \neg f_4\\ f_6&\ {\color{#FF8}\overset{R_5}{\leftarrow}}\ (f_1\vee f_5)\\ f_7&\ {\color{#FF8}\overset{R_5}{\leftarrow}}\ (f_3\wedge f_6)\\ \end{align*}

Voici une séquence de règles possible en analyse descendante. À chaque étape, un cadre numéroté indique la règle qui décompose la sous-formule : \begin{align*} &\boxed{{\color{#FFF}formule}}_{\;5}\\ (\boxed{{\color{#FFF}formule}}_{\;5}&\wedge{\color{#FFF}formule})\\ (({\boxed{{\color{#FFF}formule}}}_{\;1} \Rightarrow{\color{#FFF}formule})&\wedge{\color{#FFF}formule})\\ ((P \Rightarrow {\boxed{{\color{#FFF}formule}}_{\;1}})&\wedge {\color{#FFF}formule})\\ ((P \Rightarrow Q)&\wedge {\boxed{{\color{#FFF}formule}}_{\;5}})\\ ((P \Rightarrow Q)&\wedge ({\boxed{{\color{#FFF}formule}}_{\;1}}\vee{\color{#FFF}formule}))\\ ((P \Rightarrow Q)&\wedge (P\vee {\boxed{{\color{#FFF}formule}}_{\;4}}))\\ ((P \Rightarrow Q)&\wedge (P\vee \neg {\boxed{{\color{#FFF}formule}}_{\;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. Une formule avec un connecteur \(q\)-aire est représentée à l'aide de \(q+1\) nœuds dans cet arbre, le connecteur est placé à la racine de l'arbre qui est reliée à chacun des \(q\) opérandes dans l'ordre de leur apparition dans la formule.

Les deux arbres suivants représentent respectivement une formule avec un connecteur unaire et son opérande et une formule avec 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 \(\square\) reliant des formules.

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.

Quand les opérandes d'un connecteur sont eux-mêmes 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érivation l'arbre ci-dessous :

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

Si une formule peut admettre plusieurs dérivations, elle n'a qu'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 priorités pour simplifier les écritures. 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érable d'écrire toutes les parenthèses, l'expérience prouve qu'elles facilitent beaucoup plus souvent la lecture qu'elles ne la compliquent. 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 (P\vee \neg R).\)

Un étudiant s'étonnait de ne pas avoir eu le point attribué à une question dans laquelle il fallait représenter l'arbre de dérivation de la formule \(\neg P\Rightarrow Q\) (à droite ci-dessous) qu'il avait représenté comme à gauche ci-dessous en arguant qu'ils étaient égaux :

au lieu de

Effectivement, dans ces deux graphes, les relations entre éléments matérialisées par des arcs sont strictement égales (vous pourrez en faire la preuve à titre d'exercice en définissant l'ensemble sur lequel sont définis les graphes de ces deux relations une fois cette partie du cours étudiée)^*(*) ils le sont également du point de vue topologique.. Néanmoins, il s'agit ici d'une représentation avec une sémantique, elle met en particulier en évidence la position des opérandes gauche et droit de part et d'autre d'un opérateur binaire comme l'implication \(\Rightarrow\). Autrement dit, la représentation à gauche ne fournit pas la même information que celle de droite compte tenu des conventions de représentation des arbres de dérivation. Je doute échapper à une contravention pour conduite à contresens en prétextant que les deux panneaux à sens unique ⬆ et ⬇ sont égaux…

Analogie avec un langage de programmation

Comme nous l'avons précisé en introduction, les mathématiques s'expriment grâce à un empilement de langages, celui de la logique propositionnelle étant le premier et le plus simple d'entre eux. On retrouve cette hiérarchie dans les langages de programmation eux même empilement de plusieurs langages et la logique propositionnelle en fait généralement partie, comme c'est le cas en Python.

Bien sûr, l'écriture des programmes informatiques passant par l'usage d'un clavier avec un alphabet restreint, le lexique du langage de la logique propositionnelle est nécessairement différent de celui des mathématiques et les symboles représentant les connecteurs logiques sont remplacés par leurs noms en toutes lettres, or pour \(\vee\), and pour \(\wedge\), etc. Mais, au même titre que le langage de la logique propositionnelle est un sous-langage du langage mathématique, le langage de la logique propositionnelle est un sous-langage du Python.

Par exemple dans la formule \(P\vee (Q\wedge R)\), les variables propositionnelles \(P\), \(Q\) et \(R\) sont codées en Python par les trois objets de type booléen P, Q et R et la formule homologue est P or (Q and P).

Ce n'est pas le seul sous-langage mathématique qui a été transposé en Python, celui de l'arithmétique l'a été également avec quelques bouleversements mineurs sur le lexique et la syntaxe pour les mêmes raisons de limitation du clavier. La multiplication \(\times\) est codée par le symbole * en Python par exemple.

Sémantique du calcul propositionnel

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 interprétation est donc une fonction \(I:{\mathscr F}\rightarrow \{vrai,\;faux\}\) de l'ensemble des formules propositionnelles \(\mathscr F\) dans l'ensemble*(*) Les termes ensemble et fonction ne sont pas définis formellement à ce stade mais la vision naïve est suffisante ici. \(\{vrai,\;faux\}.\)

Les règles qui permettent d'attribuer un sens aux formules doivent être cohérentes avec les règles de construction syntaxique. La fonction d'interprétation \(I\) est définie en fixant arbitrairement une valeur de vérité \(vrai\) ou \(faux\) à chacune des variables propositionnelles. 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 respectivement comme les valeurs logiques \(vrai\) et \(faux\) (objets sémantiques), c'est-à-dire \(I(\top):=vrai\) et \(I(\bot):=faux\) et que la fonction d'interprétation d'une formule se conforme aux tables des connecteurs logiques. Ainsi pour respecter la cohérence entre syntaxe et sémantique, l'interprétation des différentes variables propositionnelles qui sont impliquées dans une formule fixe l'interprétation de la formule.

On appelle interprétation d'une formule toute fonction de l'ensemble des variables propositionnelles qu'elle contient dans l'ensemble \(\{vrai,\;faux\}.\)

À présent, une formule de la logique propositionnelle est bien une proposition au sens de la première définition (informelle). Nous pouvons donc employer le terme proposition pour désigner une formule de la logique propositionnelle.

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

F V

V F

\(P\) \(Q\) \(\ P\wedge Q\ \) \(\ P\vee Q\ \) \(\ P\Rightarrow Q\ \) \(\ P\Leftrightarrow Q\ \) \(\ P\oplus Q\ \) \(\ P\uparrow Q\ \) \(\ P\downarrow Q\ \)

F F F F V V F V V

F V F V V F V V F

V F F V F F V V F

V V V V V V F F F

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 propositionnelles qu'elle contient. La table de vérité de la formule \((\ref{eq:ex1})\) est présentée ci-dessous et pour faciliter la compréhension, les deux sous-formules de la conjonction sont présentes également :

	\(P\)	\(Q\)	\(R\)	\(\ P\Rightarrow Q\ \)	\(\ P\vee\neg R\ \)	\(\ (P\Rightarrow Q)\wedge( P\vee\neg R\ )\)
	F	F	F	V	V	V
	F	F	V	V	F	F
Interprétation \(\color{#AA88FF}{I}\quad \)	F	V	F	V	V	V
	F	V	V	V	F	F
	V	F	F	F	V	F
	V	F	V	F	V	F
	V	V	F	V	V	V
	V	V	V	V	V	V

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 interprétation \(\color{#AA88FF}{I}\) pour remplacer chaque variable propositionnelle \(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 applique inductivement les deux opérations suivantes sur l'arbre de dérivation :

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,
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{#FF8}F\), \(I(Q)=\color{#FF8}V\) et \(I(R)=\color{#FF8}F\), on obtient 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 \(F_1\) et \(F_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 \(F_1\equiv F_2\). Le symbole \(\equiv\) est appelé équivalence logique.

En anticipant sur le chapitre Relations, applications, l'équivalence logique est une relation d'équivalence définie sur l'ensemble des formules propositionnelles. Un énoncé du type \(F_1\equiv F_2\) n'est donc pas une formule propositionnelle, mais constitue une proposition au sens informel.

On montre aisément que pour toute proposition \(P\), on a \begin{equation}\label{eq:neg} \neg(\neg P)\ \equiv\ P \end{equation} et que deux propositions \(P\) et \(Q\) peuvent être échangées sans rien changer aux tables de vérités des formules \(P \vee Q\) et \(P\wedge Q\), autrement dit que les connecteurs logiques de disjonction et de conjonction sont commutatifs : \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 mathématiques pour définir les connecteurs d'implication et d'équivalence à partir des trois connecteurs de négation, 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 commutativité du connecteur \(\wedge\) entraîne celle du connecteur \(\Leftrightarrow\) d'équivalence.

On peut se demander pourquoi nous n'avons pas étudié d'autres opérateurs que les opérateurs unaires et binaires ? Le théorème 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 les connecteurs \(\neg\), \(\vee\) et \(\wedge\).

On désigne par \(\Omega\) ce connecteur \(q\)-aire en notation préfixe, et par \(P_1,P_2,\ldots,P_q\) les \(q\) variables propositionnelles qu'il connecte. On définit les deux opérateurs \((q-1)\)-aires suivants : \begin{align*} T(P_1,\ldots,P_{q-1})&:=\Omega(P_1,\ldots,P_{q-1},\top)\\ F(P_1,\ldots,P_{q-1})&:=\Omega(P_1,\ldots,P_{q-1},\bot) \end{align*} et on vérifie aisément que \begin{equation} \label{eq:conbinenough} \Omega(P_1,\ldots,P_q) \equiv \big(P_q\;{\color{orange}\wedge}\;T(P_1,\ldots,P_{q-1})\big)\;\;{\color{orange}\vee}\;\;\big(\neg P_q\;{\color{orange}\wedge}\; F(P_1,\ldots,P_{q-1})\big). \end{equation} en s'assurant que l'égalité est satisfaite quand \(P=\bot\) et \(P=\top\).

Toute formule est logiquement équivalente à une formule ne contenant que les connecteurs \(\neg\), \(\vee\) et \(\wedge\).

Il suffit de répéter le théorème aux connecteurs nouvellement impliqués dans la formule \((\ref{eq:conbinenough})\).

Nous verrons au chapitre sur le calcul booléen que l'on peut obtenir un résultat plus fort encore et que l'on peut se contenter d'un unique opérateur binaire. Mais le mathématicien savait déjà que l'on pouvait se contenter des trois connecteurs \(\neg\), \(\wedge\) et \(\vee\) pour tout exprimer.

Mentionnons la structure conditionnelle Si \(P\) alors \(Q\) sinon \(R\), bien connue des informaticiens, qui dans sa version logique est un connecteur ternaire utilisé couramment. Si \(P=\top\), l'expression 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.\)

Déduction et connecteur d'implication

Nous allons étudier de plus près le connecteur logique d'implication (\(\then\)) et expliciter son rôle dans les mécanismes déductifs en mathématiques.

Lorsqu'une proposition \(P\then Q\) est vraie, on dit que \(Q\) est une condition nécessaire de \(P\) ou que \(P\) est une condition suffisante de \(Q\).

Observons d'un peu plus près sa table de vérité :

\(P\)	\(Q\)	\(\ P\Rightarrow Q\ \)
F	F	V
F	V	V
V	F	F
V	V	V

Tables de vérité de l'implication.

Pour s'assurer que la proposition \(\color{#FF8}P\then Q\) est vraie, il suffit de vérifier que si \(P\) est vraie alors \(Q\) n'est pas fausse pour éliminer la troisième interprétation de la table. Dans les \(3\) autres cas, il n'y a rien à faire, cette proposition est toujours vraie. Si la proposition \(\color{#FF8}P\then Q\) est vraie, cela ne nous donne pas d'information sur la valeur de vérité de la proposition \(P\) ni de la proposition \(Q\). En effet \(\color{#FF8}P\then Q\) peut être vraie, que \(P\) (resp. \(Q\)) soit vraie ou fausse. On ne déduit rien de la seule véracité d'une implication.

Plus troublant, la proposition \((0=1)\Rightarrow (3\ \text{est pair})\) est vraie (cependant, si l'on se souvient que \((P\then Q)\equiv(\neg P\vee Q)\), la proposition \((0=1)\Rightarrow (3\ \text{est pair})\) est logiquement équivalente à la proposition \((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 pas l'assertion \(P\Rightarrow Q\). Les connecteurs logiques établissent des liens de corrélation entre les propositions \(P\) et \(Q\) et non des liens de causalité. Il y donc de bonnes raisons de ne pas interpréter le symbole \(\Rightarrow\) comme le mot donc en français.

Ceci nous amène à nous interroger légitimement sur le choix du mot implication pour qualifier ce connecteur logique, puisqu'il a sans conteste un sens déductif en français. Continuons nos investigations.

On peut se convaincre que le connecteur d'implication tel qu'il est défini en logique propositionnelle est le meilleur choix parmi les 16 connecteurs logiques binaires pour approximer son homologue en langue naturelle. En effet, la valeur de vérité de l'implication \(P\then Q\) ne peut pas dépendre exclusivement de \(P\), ni exclusivement de \(Q\) et le connecteur n'est manifestement pas commutatif, il ne reste alors que les connecteurs \(\diamond_3\), \(\diamond_5\), \(\diamond_{12}\) ou \(\diamond_{14}\) et il ne reste finalement que \(\diamond_{14}\) si l'on admet que si \(P\) est vrai \(P\then Q\) doit avoir la valeur de \(Q.\)

Revenons à la table de vérité de l'implication. On observe que si \(P\then Q\) est vraie et que \(P\) l'est également, alors nécessairement la proposition \(Q\) est vraie. La règle du Modus Ponens ci-dessous décrit le rôle de la proposition \(P\Rightarrow Q\) dans le processus déductif et donne un sens précis aux mots donc ou alors dans le discours mathématique. La déduction logique est symbolisée par le signe \(\vdash\) (ou \(\therefore\)) séparant les prémisses (ou hypothèses) \(P\) et \(P\Rightarrow Q\), du conséquent (ou conclusion) \(Q\).

Soit \(P\) et \(Q\) deux propositions. Si \(P\Rightarrow Q\) est vraie et \(P\) est vraie, alors la proposition \(Q\) est vraie. On résume ce résultat en écrivant \begin{equation} \label{eq:modusponens} 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\).

Ces notations sont largement utilisées dans l'étude des systèmes de décision, des logiques non classiques, en théorie de la démonstration, en intelligence artificielle, etc. On vérifie facilement l'équivalence logique entre les deux propositions suivantes en construisant leurs tables de vérité : \begin{equation} \label{eq:modustollens} P\Rightarrow Q\ \equiv\ \neg Q\Rightarrow \neg P \end{equation} La proposition \(\neg Q\Rightarrow \neg P\) est appelée contraposée de la proposition \(P\Rightarrow Q\).

Vérifier l'équivalence \((\ref{eq:modustollens})\) sans construire les tables de vérités des deux propositions.

On a \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*}

Soit \(P\) et \(Q\) deux propositions. Si \(P\Rightarrow Q\) est vraie et \(\neg Q\) est vraie, alors la proposition \(\neg P\) est vraie. On résume ce résultat en écrivant \begin{equation} \neg Q,\ P\then Q\ \vdash\ \neg P\qquad\text{ou}\qquad \frac{\neg Q,\ P\Rightarrow Q}{\neg P} \end{equation} et que l'on peut lire si \(\neg Q\) et \((P\Rightarrow Q)\) alors \(\neg P\).

Une séquence de déductions logiques permettant d'établir de nouvelles assertions à partir d'assertions déjà acquises — initialement les axiomes — s'appelle une démonstration ou une preuve.

Pour vérifier une équivalence, d'après la définition \((\ref{eq:eq})\) il faut démontrer les deux implications \(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 vérifier 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 mathématicien britannique qui vécut au 19^ème siècle.

Soit \(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 en construisant les tables de vérité.

Soit \(P\), \(Q\) et \(R\) trois propositions. Démontrez que \begin{equation} \big(\Rrightarrow(P,Q,R)\big)\equiv \big((P\wedge Q)\vee(\neg P \wedge R)\big) \end{equation}

La proposition \(Q\Rightarrow P\) est appelée implication réciproque de l'implication \(P\Rightarrow Q\). Ce n'est pas sa négation, 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 propositions peuvent être toujours vraies (resp. fausses) quelles que soient les interprétations des variables propositionnelles 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 :

La non contradiction : \(\neg(P\wedge \neg P)\)
Le tiers exclu : \(P\vee \neg P,\)
L'analyse de cas : \((P\then Q)\wedge(\neg P\then Q)\iff Q,\)

La première exprime qu'une proposition et sa négation ne peuvent être vraies toutes les deux, on ne veut pas de paradoxes. Elle permet d'élaborer une stratégie de démonstration dite démonstration par l'absurde : plutôt que de montrer qu'une proposition \(P\) est vraie, on suppose qu'elle est fausse pour en déduire la contradiction \(P\wedge \neg P\) invalidant l'hypothèse et permettant de conclure que \(P\) est vraie grâce au tiers exclu. Ainsi un inspecteur qui suppose qu'un cambrioleur est passé par une fenêtre et après investigation, ne trouve aucune trace d'effraction sur cette fenêtre, conclura que son hypothèse était absurde et en déduira que le cambrioleur est entré par un autre moyen.

La seconde exprime qu'une proposition ou sa négation doit être vraie, autrement dit que l'on exclut une troisième possibilité*.(*) La logique intuitionniste rejette le tiers exclu et par conséquent le raisonnement par l'absurde. Notons que la non contradiction et le tiers exclu 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 2024, à la cour suprême des États-Unis d'Amérique, un procès tout à fait sérieux a opposé un revendeur de drogue au gouvernement au sujet de l'interprétation d'une loi sur les remises de peine. Voici une traduction simplifiée de l'introduction du document fourni en lien à la fin de cette note et expliquant les tenants et les aboutissants du procès :

Après avoir plaidé coupable pour avoir vendu plus de 50g de méthamphétamine, le requérant était confronté à une peine minimale obligatoire de 15 ans de prison. Lors du procès, il a cherché à bénéficier d'une disposition de remise de peine inscrite dans la loi fédérale et qui permet à un tribunal d'ignorer le minimum statutaire si l'accusé remplit certains critères. Parmi ces critères, figure l'exigence que l'accusé n'a pas :

plus de 4 points d'antécédents criminels, excluant tout point d'antécédents criminels résultant d'une infraction d'un point, et
une infraction antérieure de 3 points, et
une infraction violente antérieure de 2 points.

Le gouvernement a soutenu que le requérant ne satisfaisait pas cette exigence car il avait deux infractions antérieures de trois points totalisant six points d'antécédents criminels. Selon le gouvernement, chacune de ces infractions antérieures le disqualifiait en vertu de la condition B et les six points au total le disqualifiaient en vertu de la condition A. Mais le requérant affirmait qu'il restait éligible en soulignant que son casier judiciaire ne comportait pas d'infraction violente de deux points, comme spécifié en C. Et selon lui, seule la combinaison des conditions du texte choisie par le gouvernement l'empêchait d'obtenir cette dispense de peine.

Autrement dit, dans le langage de la logique propositionnelle, le requérant affirmait que l'interprétation du texte de loi par le gouvernement, à savoir la formule \begin{equation}\label{eq:pulsifier} (\neg A)\;{\color{orange}\wedge}\;(\neg B)\;{\color{orange}\wedge}\;(\neg C), \end{equation} l'empêchait de bénéficier de la remise de peine et qu'il fallait en fait l'interpréter par la formule \[ \neg(A\;{\color{orange}\wedge}\;B\;{\color{orange}\wedge}\;C) \] logiquement équivalente d'après les lois de De Morgan à \[ (\neg A)\;{\color{orange}\vee}\;(\neg B)\;{\color{orange}\vee}\;{\color{lightblue}(\neg C)} \] qu'il satisfaisait puisqu'il n'avait pas fait d'infraction violente de 2 points. Le gouvernement américain (qui a gagné malgré tout) a dû argumenter pour établir que le texte ne pouvait être interprété que par la conjonction \((\ref{eq:pulsifier})\) des trois négations des conditions. Voir Pulsifier v. United States.

Propriétés des connecteurs logiques

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

Commutativité de \(\wedge\) et \(\vee\). \begin{align*} (P\wedge Q)&\equiv (Q\wedge P) & (P\vee Q)&\equiv (Q\vee P). \end{align*}
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*}
Idempotence de \(\wedge\) et \(\vee\). \begin{align*} (P\wedge P)&\equiv P, & (P\vee P)&\equiv P. \end{align*}
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*}
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*}
Absorption. \begin{align*} (P\wedge(P\vee Q))&\equiv P & (P\vee(P\wedge Q))&\equiv P \end{align*}
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*}
Transitivité de l'implication. \begin{align*} ((P\then Q)\wedge(Q\then R))\then(P\then R). \end{align*}

Un mathématicien discute avec un ami logicien qui lui annonce que sa femme vient d'accoucher. 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.

Démontrez que le connecteur \(\oplus\) est commutatif et associatif. Parmi les autres connecteurs binaires, lesquels sont commutatifs ?

Soit \(P\), \(Q\) et \(R\) des propositions. Démontrez la transitivité de l'implication à l'aide d'une table de vérité : \begin{equation} \big((P\Rightarrow Q)\wedge(Q\Rightarrow R)\big)\ \Rightarrow (P\Rightarrow R) \end{equation}

Soit \(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 propositions \(P\), \(Q\) et \(R\) on a \[(P\,\diamond\, Q)\,\diamond\, R\ \equiv\ P\,\diamond\, (Q\,\diamond\, R).\] Démontrez que la conjonction, la disjonction et l'équivalence sont des connecteurs logiques associatifs mais que l'implication n'est pas associative.

Soit \(P\), \(Q\) et \(R\) trois propositions. Démontrez que \[(P\wedge Q)\Rightarrow R\ \equiv\ P\Rightarrow (Q\Rightarrow R)\]

Soit \(P\) et \(Q\) deux propositions. Démontrez que \[(P\iff Q) \equiv\ (P\wedge Q)\vee (\neg P\wedge\neg Q)\]

Formalisation des problèmes et 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 introduit les variables propositionnelles \(\color{#FF8}X\), \(\color{#F44}B\) et \(\color{#88F}A\) définies par

\(\color{#FF8}X:\) xam est en bon état (i.e. il fait un bon diagnostic),
\(\color{#F44}A:\) arg est en bon état (i.e. il fait un bon diagnostic),
\(\color{#88F}B:\) bax est en bon état (i.e. il fait un bon diagnostic).

Si l'on observe la table de vérité du connecteur d'équivalence \(\iff\), on note que \(P\iff Q\) est vrai si et seulement si les deux variables \(P\) et \(Q\) ont la même valeur de vérité, c'est-à-dire si les deux sont vraies ou si les deux sont fausses (on en déduit au passage que \((P\iff Q)\equiv(P\wedge Q)\vee (\neg P\wedge\neg Q)\)). On formalise alors les propositions de xam, arg et bax respectivement par :

\({\color{#FF8}P_X}:\) \((A\iff B)\),
\({\color{#F44}P_A}:\) \(\neg B\),
\({\color{#88F}P_B}:\) \((X\wedge A)\).

Il faut également 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. Autrement dit, les propositions \(X\) (resp. \(A\) et \(B\)) et \(P_X\) (resp. \(P_A\) et \(P_B\)) ont la même valeur de vérité, ce qui se traduit par la formule \begin{equation} \label{formrobot} {\mathscr F}:=({\color{#FF8}P_X}\iff {\color{#FF8}X})\wedge({\color{#F44}P_A}\iff {\color{#F44}A})\wedge({\color{#88F}P_B}\iff {\color{#88F}B}). \end{equation}

On construit ensuite la table de vérité des trois propositions \({\color{#FF8}P_X}\), \({\color{#F44}P_A}\) et \({\color{#88F}P_B}\) ainsi que celle de la formule \(\mathscr F\) :

				\({\color{#FF8}P_X}\)	\({\color{#F44}P_A}\)	\({\color{#88F}P_B}\)
	\(\color{#FF8}X\)	\(\color{#F44}A\)	\(\color{#88F}B\)	\({\color{#FF8}(A\iff B)}\)	\({\color{#F44}\neg B}\)	\({\color{#88F}(X\wedge A)}\)	\(\mathscr F\)
1	F	F	F	V	V	F	F
2	F	F	V	F	F	F	F
3	F	V	F	F	V	F	V
4	F	V	V	V	F	F	F
5	V	F	F	V	V	F	F
6	V	F	V	F	F	F	F
7	V	V	F	F	V	V	F
8	V	V	V	V	F	V	F

Table de vérité de la formule \(\mathscr F\).

Comme on peut le constater, seule l'interprétation #3 satisfait la formule \((\ref{formrobot})\), il faut donc réparer xam et bax.

Le logicien amoureux

Traitons un deuxième exemple. On interroge un logicien, qui dit toujours la vérité, sur sa vie sentimentale et il affirme :

(a) J'aime Marie ou j'aime Anne.
(b) Si j'aime Marie, alors j'aime Anne.

On peut traduire ces deux assertions en formules propositionnelles. Pour cela on définit les variables propositionnelles \(A\) et \(M\) qui sont interprétées de la manière suivante :

\(A:\) J'aime Anne,
\(M:\) J'aime Marie,

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\)
F	F	F	\(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 demande de confirmation de (b) était en soi inutile puisque le logicien dit toujours la vérité.

(c) Si c'est vrai, alors j'aime Marie,
(d) Si j'aime Marie, alors c'est vrai.

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\)
F	F	F	\(V\)	F
F	\(V\)	\(V\)	F	F
\(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 :

(a) Celui qui porte le tee-shirt rouge ne porte pas de lunettes et c'est le plus jeune,
(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 propositionnelles :

\(A_{\color{#F44}R}\) (resp. \(B_{\color{#F44}R}\), \(C_{\color{#F44}R}\)) code Alvin (resp. Bob, Calvin) porte un tee-shirt rouge,
\(A_{\color{#0A0}V}\) (resp. \(B_{\color{#0A0}V}\), \(C_{\color{#0A0}V}\)) code Alvin (resp. Bob, Calvin) porte un tee-shirt vert,
\(A_{\color{#FF8}J}\) (resp. \(B_{\color{#FF8}J}\), \(C_{\color{#FF8}J}\)) code Alvin (resp. Bob, Calvin) porte un tee-shirt jaune,
\(A_L\) (resp. \(B_L\), \(C_L\)) code Alvin (resp. Bob, Calvin) porte des lunettes,
\(A_A\) (resp. \(B_A\), \(C_A\)) code Alvin (resp. Bob, Calvin) est l'aîné,
\(A_B\) (resp. \(B_B\), \(C_B\)) code Alvin (resp. Bob, Calvin) est le benjamin,
\(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 formaliser un certain nombre de contraintes implicites. Chacun des trois frères doit porter un unique tee-shirt. Ceci se traduit par le fait qu'ils doivent porter un tee-shirt rouge ou vert ou jaune et qu'ils ne doivent pas en porter deux simultanément, soit respectivement les six formules suivantes :

\begin{align} &(A_{\color{#F44}R}\vee A_{\color{#0A0}V} \vee A_{\color{#FF8}J}),\\ &\neg(A_{\color{#F44}R}\wedge A_{\color{#0A0}V}) \wedge \neg(A_{\color{#F44}R}\wedge A_{\color{#FF8}J}) \wedge \neg(A_{\color{#0A0}V}\wedge A_{\color{#FF8}J}),\\ &(B_{\color{#F44}R}\vee B_{\color{#0A0}V} \vee B_{\color{#FF8}J}),\\ &\neg(B_{\color{#F44}R}\wedge B_{\color{#0A0}V}) \wedge \neg(B_{\color{#F44}R}\wedge B_{\color{#FF8}J}) \wedge \neg(B_{\color{#0A0}V}\wedge B_{\color{#FF8}J}),\\ &(C_{\color{#F44}R}\vee C_{\color{#0A0}V} \vee C_{\color{#FF8}J}),\\ &\neg(C_{\color{#F44}R}\wedge C_{\color{#0A0}V}) \wedge \neg(C_{\color{#F44}R}\wedge C_{\color{#FF8}J}) \wedge \neg(C_{\color{#0A0}V}\wedge C_{\color{#FF8}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{#FF8}J}\wedge B_{\color{#FF8}J})\wedge \neg(A_{\color{#FF8}J}\wedge C_{\color{#FF8}J})\wedge \neg(B_{\color{#FF8}J}\wedge C_{\color{#FF8}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 propositionnelles. 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 lunettes impose \(I(A_L):=V\) pour la fonction 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 propositionnelles, 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 heuristiques cependant..

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

(a) Celui qui porte le tee-shirt rouge ne porte pas de lunettes et c'est le plus jeune,
(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{#FF8}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 :

Alvin est le cadet, porte des lunettes et le tee-shirt vert,
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 une 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.

Limites de la logique propositionnelle

De manière générale, un énoncé peut très bien aboutir à la formalisation d'une proposition avec plusieurs interprétations valides (si elles le sont toutes, c'est une tautologie) ou aucune (antilogie). Ceci justifie la définition suivante :

Une formule propositionnelle est dite satisfaisable s'il existe une interprétation de cette formule qui soit vraie. Dans le cas contraire, elle est dite insatisfaisable.

On utilise la même terminologie pour un ensemble de formules mais dans ce cas il faut que leur conjonction (qui est une nouvelle formule) soit satisfaisable.

Déterminer si une formule est satisfaisable est un problème extrêmement difficile. Les scientifiques pensent, dans leur grande majorité, qu'aucun moyen efficace ne permet d'y répondre (cette question sera abordée en détail en master.) On peut, bien sûr, construire la table de vérité de la formule pour faire cette vérification, mais c'est un travail qui devient littéralement infaisable, même pour un ordinateur, dès qu'il y a plus de quelques dizaines de variables propositionnelles dans la formule.

Supposons qu'un ordinateur soit capable d'évaluer la valeur logique d'une formule propositionnelle pour une interprétation donnée en \(10^{-9}\) secondes, autrement dit qu'il est capable de remplir un milliard de lignes de la table de vérité de cette formule en une seconde. Si la formule contient \(50\) variables propositionnelles, combien de temps faut-il à la machine pour déterminer si elle est satisfaisable ou non ?

Des algorithmes efficaces en pratique existent pour vérifier qu'une formule est satisfaisable. Ce n'est pas contradictoire, la satisfaisabilité ou non-satisfaisabilité d'une formule n'est pas toujours difficile à établir, cela dépend de la formule et s'il y a peu de formules difficiles…

Les exemples de formalisation que nous venons de traiter illustrent les limites de la logique propositionnelle. Son manque d'expressivité nous a contraint à créer un grand nombre de variables pour décrire les différents cas et l'exercice ci-dessus montre que faute de stratégies, il peut être difficile d'automatiser la résolution de problèmes logiques. D'autre part, nombre d'énoncés et de raisonnements logiques en langue naturelle ne sont pas transposables en formules de la logique propositionnelle, par exemple Tout étudiant·e en licence d'informatique suit le cours de mathématiques, Alice est étudiante en licence d'informatique donc Alice suit le cours de mathématiques.

Mais, pire encore, que se passerait-il si une énigme faisait référence à des entiers naturels ? Par exemple, au lieu d'invoquer les couleurs des tee-shirts d'Alvin, Bob et Clive, on invoquait dans un énoncé un code secret qui serait un nombre (de taille arbitraire) ? Manipuler un très grand nombre de variables propositionnelle voire une infinité de variables propositionnelles 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 par exemple qu'une partie \(X=\{x_1,x_2,\ldots,x_n\}\) de \(\N\) ne contient que des entiers pairs par la phrase \[ \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}. \]

Le prochain chapitre est consacré à l'étude de la logique des prédicats dans le cadre de la théorie des ensembles de Zermelo-Fraenkel (abrégée en théorie zf).

Calculez les négations des propositions suivantes :

\(P\then(Q\then R)\),
\(\neg P\then Q\),
\((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).\]

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\).
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é.

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.
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).
Que doit-il apporter au minimum pour satisfaire le client et répondre à toutes ses hésitations ?

Soit \(P,Q,R\) des variables propositionnelles,

La proposition \(\big((P\vee Q)\wedge (\neg P \vee R)\big)\then (Q\vee R)\) est-elle une tautologie ?
On considère les trois variables propositionnelles \(E\), \(R\) et \(S\) qui modélise les évènements
- \(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 :

Bradacié : Piedplat est coupable et Nécassé est innocent,
Piedplat : Si Bradacié est coupable, alors Nécassé l'est aussi,
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 :

Est-il possible que mes trois lascars aient dit la vérité ? Mais alors qui serait coupable ?
Auraient-ils pu me mentir tous les trois ?
Il me semble que certains témoignages se déduisent des autres mais lesquels ?
Si je suppose que tous sont innocents, qui a menti ? et si je les suppose tous coupables, qui a menti ?
Est-il possible qu'il n'y ait qu'un seul faux témoignage ? Mais dans ce cas, qui aurait menti et qui serait coupable ?
Et si je suppose que l'innocent dit la vérité et que le coupable ment, qui alors est innocent et qui est coupable ?

Pouvez-vous aider l'inspecteur Lafrite à répondre à ces questions ? Indication : les variables propositionnelles \(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 une table de vérité. Répondre à toutes les questions de l'inspecteur Lafrite.

Soit \(P,Q,R\) et \(S\) des variables propositionnelles. Vérifier que

\(\neg \big(((P\wedge Q)\vee P)\vee R)\vee S\big)\equiv \big((\neg P\wedge \neg R)\wedge \neg S\big)\)
\(\neg\big(P\then (Q\then R)\big)\equiv \big((P\wedge Q)\wedge \neg R\big)\)

Formalisez les affirmations suivantes en logique propositionnelle :

(a) Bob a déchiffré le message d'Alice ou Alice est inquiète,
(b) Bob a déchiffré le message d'Alice et Alice n'est pas inquiète,
(c) Bob n'a pas déchiffré le message d'Alice et Alice est inquiète,
(d) Bob n'a pas déchiffré le message d'Alice ou Alice n'est pas inquiète,
(e) Si Bob a déchiffré le message d'Alice alors Alice n'est pas inquiète,
(f) Bob n'a pas déchiffré le message d'Alice si Alice est inquiète.

Travaux pratiques

En séance

Écrivez une fonction Inter(nbvar) qui renvoie le tuple constitué de toutes les interprétations possibles de nbvar variables propositionnelles.

Exemple : l'appel Inter(2) doit renvoyer le tuple

((False,False),(False,True),(True,False),(True,True))

Une formule propositionnelle FP de \(n\) variables est codée par une chaîne de caractères respectant la syntaxe du Python, les variables étant toujours codées V[0], V[1],… ,V[n-1]. Écrivez une fonction TV(FP,n) qui renvoie la table de vérité de la formule FP sous forme de tuple de tuples à l'aide de la fonction Inter et la fonction d'évaluation eval(chaine) du Python qui évalue une chaine de caractères si elle respecte la syntaxe du langage Python.

Exemple. Avec la chaîne de caractère FP = "V[0] and V[1]", l'appel de la fonction TV(FP,2) doit renvoyer le tuple

((False,False,False),(False,True,False),(True,False,False),(True,True,True))

Indication : la fonction Inter(nbvar) génère les \(\color{#FF8}2^\textsf{nbvar}\) interprétations possibles des variables V[i] et pour chacune d'entre elles, il suffit d'évaluer l'expression FP.

Écrivez une fonction Satisfaisable(FP,n) qui renvoie la liste des interprétations des n variables propositionnelles qui satisfont la formule passée en paramètre.

Exemple : pour la formule "V[0] and V[1]", la fonction doit renvoyer la liste

[(True,True)]