Version sans JavaScript, en lecture seule : les ateliers, les quiz et l’exécution du code n’y sont pas. Version complète · Catalogue · Se connecter
Support de cours · chapitre 1
Le langage des propositions
Ce qu'est une formule, comment on la lit, et comment on l'écrit avec le moins de parenthèses possible sans changer son sens.
Pourquoi une logique pour l'informatique
Un programme passe son temps à décider : if (x > 0 && !fini), une requête WHERE age >= 18 OR parent, une règle de pare-feu, une spécification qui dit ce qu'une fonction doit garantir. Chaque fois, une condition est construite à partir de conditions plus simples, avec « et », « ou », « non », « si… alors ».
La logique étudie ces constructions pour elles-mêmes. Elle répond à des questions qu'un informaticien se pose tous les jours : deux conditions disent-elles la même chose ? Cette condition peut-elle être vraie ? Est-elle toujours vraie, et donc inutile ? Cette propriété découle-t-elle de celles que je connais déjà ?
Ce chapitre fixe le langage : ce qu'on a le droit d'écrire, et comment on le lit. Le chapitre suivant dira ce que ça signifie.
Propositions et connecteurs
Les variables propositionnelles
Une proposition est un énoncé qui est vrai ou faux : « il pleut », « $x$ est pair », « le fichier existe ». On ne s'intéresse pas à son contenu, seulement à sa valeur de vérité. On la représente donc par une lettre, une variable propositionnelle : $p$, $q$, $r$, $p_1$, $p_2$…
On ajoute deux constantes : $\top$ (toujours vrai) et $\bot$ (toujours faux).
Les connecteurs
On combine les propositions avec des connecteurs :
| Symbole | Nom | Se lit |
|---|---|---|
| $\lnot p$ | négation | non $p$ |
| $p \land q$ | conjonction | $p$ et $q$ |
| $p \lor q$ | disjonction | $p$ ou $q$ (ou les deux) |
| $p \to q$ | implication | si $p$ alors $q$ |
| $p \leftrightarrow q$ | équivalence | $p$ si et seulement si $q$ |
| $p \oplus q$ | ou exclusif | soit $p$, soit $q$, pas les deux |
La négation est unaire : elle porte sur une seule formule. Les autres sont binaires : elles relient deux formules. Le « ou » de la logique est inclusif ; le « ou » exclusif du français (« fromage ou dessert ») s'écrit $\oplus$.
La syntaxe
Les formules, définies par induction
On ne peut pas écrire n'importe quelle suite de symboles. Les formules sont définies par trois règles :
- une variable propositionnelle, $\top$ et $\bot$ sont des formules ;
- si $A$ est une formule, $(\lnot A)$ est une formule ;
- si $A$ et $B$ sont des formules, $(A \land B)$, $(A \lor B)$, $(A \to B)$ et $(A \leftrightarrow B)$ sont des formules.
Rien d'autre n'est une formule. Ainsi $((\lnot p) \to (q \lor r))$ est une formule : $p$, $q$ et $r$ en sont (règle 1), donc $(\lnot p)$ et $(q \lor r)$ aussi (règles 2 et 3), donc l'ensemble (règle 3). En revanche, $p \lor \land q$ n'en est pas une : aucune règle ne la produit.
Les lettres $A$, $B$, $C$ ne sont pas des variables propositionnelles : elles désignent n'importe quelle formule. On s'en sert pour énoncer des règles générales.
L'arbre de syntaxe
Une formule a une structure d'arbre. Sa racine est le connecteur principal, le dernier appliqué par les règles ; ses feuilles sont les variables.
flowchart TD A["→"] --> B["¬"] A --> C["∨"] B --> D["p"] C --> E["q"] C --> F["r"]
C'est l'arbre de $((\lnot p) \to (q \lor r))$. Son connecteur principal est $\to$. Chaque nœud de l'arbre est la racine d'une sous-formule : ici $((\lnot p) \to (q \lor r))$, $(\lnot p)$, $(q \lor r)$, $p$, $q$ et $r$.
C'est l'arbre qui donne le sens de la formule. Deux écritures qui ont le même arbre disent la même chose ; deux écritures qui ont des arbres différents ne le disent pas.
Écrire moins de parenthèses
Les priorités
Les parenthèses de la définition rendent chaque formule lisible sans ambiguïté, mais lourde. On en retire en fixant des priorités, comme en arithmétique où $2 + 3 \times 4$ se lit $2 + (3 \times 4)$ :
Le connecteur le plus prioritaire s'applique d'abord : $\lnot p \land q$ se lit $((\lnot p) \land q)$, et $p \lor q \to r$ se lit $((p \lor q) \to r)$.
L'associativité
Quand le même connecteur se répète :
- $\land$ et $\lor$ : on écrit $p \land q \land r$ sans parenthèses. Les deux groupements donnent le même résultat (on le montrera au chapitre suivant).
- $\to$ : à droite. $p \to q \to r$ se lit $(p \to (q \to r))$. Ce n'est pas la même formule que $((p \to q) \to r)$ : les parenthèses sont alors obligatoires.
Retirer les parenthèses sans changer le sens
On retire une paire de parenthèses quand les priorités et l'associativité la rétablissent d'elles-mêmes. Méthode : dessiner l'arbre, puis pour chaque nœud, se demander si le connecteur du fils est plus prioritaire que celui du père.
La langue et le métalangage
Deux sortes de symboles vont cohabiter dans ce cours, et il ne faut pas les confondre.
- Les connecteurs $\lnot, \land, \lor, \to, \leftrightarrow$ font partie du langage : ils servent à écrire des formules. $p \to q$ est une formule.
- Les symboles $\vDash$ (« a pour conséquence ») et $\equiv$ (« est équivalente à ») font partie du métalangage : ils servent à dire quelque chose sur des formules. $p \vDash p \lor q$ n'est pas une formule, c'est une affirmation à propos de deux formules, vraie ou fausse.
On ne peut donc pas demander si « $p \equiv q$ » est satisfiable : ce n'est pas une formule. On peut le demander de $p \leftrightarrow q$. Le chapitre suivant précise le lien entre les deux.