Logique de 1er ordre
Déjà en 1879, le mathématicien allemand Gottlob Frege avait bouleversé la logique qui semblait immuable depuis Aristote. Mais à partir de 1884, année de parution des Fondements de l’arithmétique, suivi des deux volumes des Lois fondamentales de l’arithmétique, il montra que l’ensemble des mathématiques ne pouvait reposer que sur la logique et non sur la géométrie comme on le pensait à la suite d’Euclide. Révolutionnaire.
Si les règles de logique sont aujourd’hui enseignées, c’est souvent pour conduire à l’algèbre de Boole puis à ses applications en informatique (voir les portes logiques).
Pour vous initier, c’est par ici…
Logique mathématique du premier ordre
La logique du premier ordre, ou logique des prédicats, comprend les connecteurs classiques tels que la négation, le caractère conjonctif (et), le disjonctif (ou), l’implication (si… alors) et l’équivalence (si et seulement si).
Une proposition mathématique est soit vraie soit fausse. Par exemple, \(2 + 5 = 7\) est une proposition vraie.
Symboles
Une proposition est notée avec une lettre majuscule : \(A,\) \(B,\)
| Non | \(\neg\) |
| Implique | \(\to\) |
| Équivalent à | \(\leftrightarrow\) |
| Et | \(\wedge\) |
| Ou | \(\lor\) |
Tables de vérité
La plus simple : si une proposition \(A\) est vraie, alors « non \(A\) » est fausse et inversement.
| \(A\) | \(\neg A\) |
| V | F |
| F | V |
Désormais, non utiliserons 1 pour « vrai » et 0 pour « faux ».
| \(A\) | \(B\) | \(A \wedge B\) |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 0 |
Vous constatez ci-dessous que OU est inclusif. L’exclusif (XOR) ne sera pas vu ici.
| \(A\) | \(B\) | \(A \lor B\) |
| 1 | 1 | 1 |
| 1 | 0 | 1 |
| 0 | 1 | 1 |
| 0 | 0 | 0 |
Jusqu’ici les choses sont très simples. Elles doivent vous rappeler votre découverte des probabilités (voir la page d'initiation aux probabilités).
| \(A\) | \(B\) | \(A \to B\) |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 1 |
| 0 | 0 | 1 |
| \(A\) | \(B\) | \(A \leftrightarrow B\) |
| 1 | 1 | 1 |
| 1 | 0 | 0 |
| 0 | 1 | 0 |
| 0 | 0 | 1 |
Nous n’irons pas plus loin dans la théorie. Démontrons que si \(A\) implique \(B\) et \(B\) implique \(A\) alors \(A\) est équivalent à \(B.\) En d’autres termes, \(A\) est une condition nécessaire et suffisante pour \(B.\)
| \(A\) | \(B\) | \(A \to B\) | \(B \to A\) | \((A \to B) \wedge (B \to A)\) | \(A \leftrightarrow B\) |
| 1 | 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 0 | 1 | 1 | 0 | 0 | 0 |
| 0 | 0 | 1 | 1 | 1 | 1 |
Les deux dernières colonnes sont identiques. La démonstration est terminée.
Exercices
- Démontrer que \((A \to B) \iff (\neg A \lor B)\)
- Donner la table de vérité de l’implication \([A \wedge (A \to B)] \to B.\)
Corrigés
1- Table de vérité
| \(A\) | \(B\) | \(A \to B\) | \(\neg A\) | \(\neg A \lor B\) |
| 1 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 1 | 1 |
| 0 | 0 | 1 | 1 | 1 |
Les colonnes 3 et 5 sont identiques. La démonstration est faite (on peut aussi ajouter une sixième colonne avec pour intitulé l’équivalence de l’énoncé et ne comportant que des 1).
2- Table de vérité
| \(A\) | \(B\) | \(A \to B\) | \(A \wedge (A \to B)\) | \([A \wedge (A \to B)] \to B\) |
| 1 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 0 | 0 | 1 | 0 | 1 |
Fonction propositionnelle
Et voici l’occasion de retrouver les quantificateurs !
\(P(x)\) est une fonction propositionnelle, avec \(x\) appartenant à un ensemble \(E.\)
- \(\forall x, x \in A, P(x)\) est vraie si \(P(x)\) est vraie pour toutes les valeurs de \(X\) et fausse pour au moins une valeur de \(x.\)
- \(\exists x, x \in A, P(x)\) est vraie s’il existe au moins une valeur de \(x\) pour laquelle \(P(x)\) est vraie et fausse si \(P(x)\) est fausse pour toutes les valeurs de \(x.\)
