Algèbre propositionnelle
Formule
Une formule est une expression mathématique pouvant être lue comme une phrase avec un verbe.
| Formule mathématique | Lecture |
|---|---|
| 8 + 8 = 16 |
Huit et huit font seize(Jacques Prévert, Page d’écriture) |
Le symbole = décrit une relation que l’on peut lire comme le verbe « égaler » ou « valoir ».
- inégalités de comparaison (<, >, ≤, ≥, ≠),
- appartenance (∈) et inclusion (⊂)
- parallélisme (//) et orthogonalité (⊥) …
Certaines relations n’ont pas de symbole d’usage courant et il est tout à fait possible d’écrire une formule sous la forme d’une phrase en français.
Une formule n’est pas nécessairement toujours vraie.
| Formule vraie | 2 + 2 = 4 | Victor Hugo est né en 1802. |
|---|---|---|
| Formule fausse | 1 = 2 | Victor Hugo est né en 1800. |
| Expression valable | 32 + 42 | Naissance en 1802 |
| Expression impossible | 1 / 0 | Il a né |
Une assertion est une formule que l’on déclare comme étant vraie.
Connecteurs binaires
En pratique, une phrase en français peut contenir plusieurs propositions séparées par des conjonctions de coordination.
Ce soir, Bernadet l’insaisissable couchera en cabane, ou je ne m’appelle plus Nestor Burma…
De même, plusieurs formules peuvent être assemblées avec les connecteurs (ou opérateurs) booléens suivants.
| Symbole | Prononciation | Résultat |
|---|---|---|
| ∧ | « et » | conjonction |
| ∨ | « ou » | disjonction |
| ⇒ | « implique » | implication |
| ⇔ | « si et seulement si » | équivalence |
| et | F | V |
|---|---|---|
| F | F | F |
| V | F | V |
| ou | F | V |
|---|---|---|
| F | F | V |
| V | V | V |
| ⇒ | F | V |
|---|---|---|
| F | V | V |
| V | F | V |
| ⇔ | F | V |
|---|---|---|
| F | V | F |
| V | F | V |
Les formules notées à gauche et à droite du symbole sont appelés les clauses du résultat.
La conjonction ne traduit pas tous les usages du mot « et » en français. La phrase « l’éclipse de soleil n’a lieu qu’en journée et en période de nouvelle lune » est bien une conjonction car les deux conditions doivent être réunies simultanément. Au contraire, la phrase « l’équinoxe n’a lieu qu’au printemps et à l’automne » est une disjonction, car les deux conditions ne sont pas simultanées.
Le connecteur « ou » est inclusif, c’est-à-dire qu’il autorise la conjonction. Ainsi, à la question « Fromage ou dessert ? », un mathématicien peut répondre « Les deux ! » Il existe aussi un connecteur « ou exclusif », mais il est d’usage moindre en mathématiques.
Le connecteur d’implication est le seul des quatre qui n’est pas symétrique. Si A et B sont deux formules, l’assertion A ⇒ B signifie que si A est vrai alors B aussi. On dit aussi que A est une condition suffisante pour B ou encore que B est une condition nécessaire pour A. Mais sans information supplémentaire, cela ne signifie pas que B soit vrai (et A non plus d’ailleurs).
Si le monde était à l’envers,
Je marcherais les pieds en l’air
L’implication A ⇒ B a pour implication réciproque B ⇒ A. L’une peut être vraie sans que l’autre le soit comme dans la définition du Hitzefrei en Allemagne : « S’il fait trop chaud, les élèves sont dispensés de cours ». Une dispense de cours n’implique pas nécessairement une température élevée.
Le symbole ⇒ ne signifie pas « donc » même s’il est souvent employé en ce sens en prise de notes. Il ne représente ni une déduction ni une relation causale.
L’équivalence A ⇔ B est une conjonction d’implications (A ⇒ B) et (B ⇒ A).
Négation
À côté de ces opérateurs binaires, on trouve l’opérateur unaire de négation, qui traduit le fait de passer d’une phrase affirmative à une phrase négative (et vice versa). La négation d’une formule A peut se noter ¬A ou ¯(A).
- Lois de De Morgan
- ¯(A et B) ⇔ ¯(A) ou ¯(B)
- ¯(A ou B) ⇔ ¯(A) et ¯(B)
La négation permet de définir la contraposée d’une implication A ⇒ B par ¯(B) ⇒ ¯(A). La contraposée a même valeur de vérité que l’implication directe.
Variables et quantificateurs
En français le pronom « qui » peut être employé nominalement pour représenter n’importe quel être humain sans désigner personne en particulier, notamment dans beaucoup de proverbes (« Qui dort dine »). En mathématiques, cette notion se retrouve dans l’usage de variables. Il s’agit généralement de lettres isolées, le plus souvent en italique, apparaissant dans des phrases en français ou dans des formules et pouvant être remplacées par différentes valeurs.
Il est préférable de préciser systématiquement l’ensemble des valeurs possibles pour chaque variable. On a tendance à l’omettre si toutes les variables sont réelles quelconques, mais certaines peuvent représenter des fonctions, des suites, des ensembles, des matrices, des formules… En outre, les domaines de définition des fonctions ou les conditions d’application des théorèmes peuvent restreindre le domaine des variables.
Le fait de préciser le domaine des variables dans une formule ne signifie pas
que cette formule est toujours vraie.
Par exemple, l’égalité √(x2) = x
a un sens pour n’importe quel réel x
mais elle n’est vraie que si x est positif.
De même, on peut considérer l’équation de droite
y = 2x + 1
avec deux variables réelles x et y
représentant les coordonnées de n’importe quel point du plan,
mais l’équation n’est satisfaite que lorsque le point est sur la droite.
Pour formuler une assertion, on introduit donc chaque variable avec un quantificateur qui apporte une information sur les cas de validation de la formule. On en utilise principalement deux :
- le quantificateur universel ∀ (« pour tout ») qui signifie que la formule reste vraie quand on remplace la variable par n’importe quelle valeur du domaine considéré,
- le quantificateur existentiel ∃ (« il existe ») qui signifie qu’il y a au moins une valeur de la variable qui permet de valider la formule.
Le quantificateur universel peut sembler plus exigeant que l’existentiel (« si c’est vrai tout le temps, c’est vrai au moins une fois »). En réalité, il y a un cas où l’universel est vrai et l’existentiel faux : lorsque le domaine de la variable est vide.
« Sur une île qui n’existe pas, tout peut exister. »
L’ordre d’énonciation des quantificateurs est crucial en français comme en mathématiques.
- « Tous les jours, il y a un élève qui arrive en retard. »
- « Il y a un élève qui arrive en retard tous les jours. »
- « Pour tout entier n, il y a un entier M strictement plus grand. »
- « Il y a un entier M strictement plus grand que tout entier n. »
Formes d’inférence
Déduction
Le raisonnement mathématique consiste à produire une succession d’assertions justifiées par les précédentes ou par des axiomes (propositions admises à partir desquelles découle tout le corpus des mathématiques), suivant des règles dérivées du modus ponens. Cette règle est une formalisation du syllogisme aristotélicien :
Tous les hommes sont mortels
Or Socrate est un homme
Donc Socrate est mortel.
Les logiciens l’écrivent sous la forme A ⇒ B, A ⊢ B dans laquelle le symbole ⊢ est beaucoup plus proche du sens du mot « donc » que ne l’est le symbole d’implication ⇒.
Induction
L’induction consiste à faire émerger une règle générale à partir de cas particuliers.
Socrate est un homme
Or Socrate est mortel
Donc tous les hommes sont mortels.
Même si la conclusion est correcte, ce procédé ne constitue pas une démonstration. En effet, l’accumulation d’exemples ne permet pas d’exclure qu’un contre-exemple puisse survenir, sauf si on s’assure d’avoir examiné tous les cas possibles. Ainsi, les Européens ont longtemps cru qu’il n’existait pas de cygne noir avant d’en trouver en Australie.
En mathématiques, de nombreux résultats traitent précisément de l’existence ou non de contre-exemples à des propriétés qui semblent vraies pour les premiers entiers ou pour les fonctions usuelles. Certaines de ces propriétés restent d’ailleurs encore à l’état de conjecture, c’est-à-dire qu’on ignore pour l’instant si elles admettent ou non un contre-exemple. L’induction est donc surtout un moyen de formuler des conjectures.
Abduction
L’abduction prend une implication à rebours.
Socrate est mortel
Or tous les hommes sont mortels
Donc Socrate est un homme.
Là encore, il ne s’agit pas d’une démonstration. Socrate pourrait aussi être le prénom d’un chien et valider ainsi seulement les deux prémisses du raisonnement. Certes, l’abduction est un mécanisme intellectuel courant (« si ça ressemble à un chien, c’est un chien » ou bien « la rue est mouillée, donc il a plu »). Mais elle mène régulièrement à des raccourcis contestables : « Cet homme a une fiche S, or tous les terroristes ont une fiche S, donc cet homme est un terroriste. »
En mathématiques, l’abduction se réalise dans l’étude de la vraisemblance en statistique inférentielle. Elle permet d’éventuellement infirmer une hypothèse d’indépendance, par exemple, mais jamais de la justifier.