Logique et démonstrations : les règles selon lesquelles on raisonne en IA

Propositions, connecteurs et tables de vérité, le piège de l’implication, quantificateurs et types de démonstrations — et pourquoi XOR a arrêté les premiers réseaux de neurones.

14 minutes Matěj Žalmánek 2026-10-15

Série Bases de l’IA Partie 7 sur 52

1. Carte de l’intelligence artificielle : qu’est-ce qui est quoi et comment tout s’emboîte
2. Brève histoire de l’intelligence artificielle : de Turing aux modèles de langage
3. Données, modèle, entraînement, inférence : les notions de base sur un seul exemple
4. Lire la notation mathématique : symboles, indices, sommes et quantificateurs
5. Ensembles et relations : les briques dont sont faites les définitions en IA
6. Fonctions et applications : pourquoi tout modèle d’IA est une fonction
7. Logique et démonstrations : les règles selon lesquelles on raisonne en IA
8. Graphes et arbres : la structure sur laquelle reposent la recherche et les réseaux de neurones
9. Algèbre linéaire pour l’apprentissage automatique : vecteurs, matrices et pourquoi l’IA multiplie surtout
10. Dérivées, gradient et règle de dérivation en chaîne : comment un modèle sait dans quelle direction apprendre
11. Descente de gradient : comment un modèle apprend
12. Qu’est-ce que la probabilité : du lancer de dé aux axiomes de Kolmogorov
13. Probabilité conditionnelle et théorème de Bayes : comment réviser une estimation quand on apprend du nouveau
14. Variable aléatoire et fonction de répartition : une seule fonction qui dit tout de la loi
15. Fonction de densité et fonction de masse : pourquoi une variable continue a une probabilité nulle en chaque point
16. Espérance, variance et covariance : où se situe une loi, quelle est sa largeur et ce qui varie avec quoi
17. Panorama des lois de probabilité : Bernoulli, binomiale, Poisson, uniforme, normale et exponentielle
18. Loi des grands nombres et théorème central limite : pourquoi les moyennes sont si prévisibles
19. Statistique et estimation de paramètres : maximum de vraisemblance, MAP et intervalles de confiance
20. Théorie de l’information : entropie, entropie croisée et divergence KL — d’où viennent les fonctions de perte
21. Recherche dans l’espace d’états : BFS, DFS, UCS et A* en animations
22. Jeux et adversaires : minimax, élagage alpha-bêta et Monte Carlo tree search
23. Satisfaction de contraintes : backtracking, propagation de contraintes et AC-3 sur un sudoku et une carte des régions tchèques
24. Logique et systèmes à base de connaissances : chaînage avant et arrière, résolution et systèmes experts
25. Planification : STRIPS, monde des blocs, heuristiques par relaxation et planification dans les agents IA
26. Recherche locale et recuit simulé : un voyageur de commerce à travers les chefs-lieux de région tchèques
27. Algorithmes génétiques : population, croisement, mutation et sélection sur un sac à dos de randonnée
28. Stratégies d’évolution et programmation génétique : de la règle du cinquième à la loi de Kepler
29. Optimisation par colonies de fourmis : comment une piste de phéromone trouve un chemin court
30. Optimisation par essaim de particules : inertie, expérience propre et expérience de l’essaim
31. Neuroévolution : faire évoluer les poids et la forme des réseaux de neurones, et l’algorithme NEAT
32. Ensembles flous et fonctions d’appartenance : comment écrire « un peu chaud »
33. Logique floue et probabilité : pourquoi « un peu chaud » ne veut pas dire « probablement chaud »
34. Logique floue : t-normes, implications et règles SI–ALORS
35. Commande floue : Mamdani et Sugeno, du ventilateur au pendule inversé sur un chariot
36. Clustering flou : l’algorithme fuzzy c-means et les points entre les clusters
37. Systèmes neuro-flous (ANFIS) : des règles floues qui apprennent à partir des données
38. Chaînes de Markov : matrice de transition, distribution stationnaire et PageRank
39. Modèles de Markov cachés : l’algorithme de Viterbi et le casino malhonnête
40. Réseaux bayésiens : pourquoi l’herbe est mouillée et ce que cela implique pour l’arroseur
41. Le filtre de Kalman : comment estimer, à partir de mesures imprécises, où se trouve une voiture et à quelle vitesse elle roule
42. Types d’apprentissage automatique : supervisé, non supervisé, semi-supervisé et plus
43. Prompts, contexte et RAG : comment donner au modèle les bonnes informations
44. Autoencodeurs variationnels (VAE) : de nouvelles images à partir d’un espace latent continu
45. Réseaux antagonistes génératifs (GAN) : le faussaire contre le détective
46. Modèles de diffusion : comment une image naît du bruit pur
47. Processus de décision markoviens : états, actions, récompenses et équations de Bellman
48. Q-learning et DQN : apprendre la valeur des actions, du tableau au réseau de neurones
49. Policy gradient et PPO : apprendre directement la politique
50. Comment fonctionne un agent IA : un modèle de langage en boucle avec des outils
51. Programmer avec des agents IA : consigne, tests et vérification
52. Évaluation et sécurité des systèmes d’IA : comment mesurer et comment surveiller

Programme complet de la série 52 sur 83 sujets publiés

Chaque définition de cette série est une proposition logique, et chaque « donc » qui la suit est un morceau de démonstration. La logique, ce sont les règles du jeu : elle dit quand une affirmation est vraie et comment déduire correctement d’autres affirmations à partir d’affirmations vraies. Et en intelligence artificielle, elle apparaît deux fois — comme langage dans lequel on parle des algorithmes, et comme discipline à part entière d’où sont nés les premiers programmes « pensants ».

Nous avons rencontré les symboles ¬, ∧, ∨, ⇒, ∀ et ∃ pour la première fois dans la partie sur la notation mathématique. Ici, nous verrons comment ils fonctionnent exactement, où l’on se trompe le plus souvent et comment on en compose une démonstration.

1. Propositions et valeurs de vérité

Définition — proposition

Une proposition est une affirmation dont il a un sens de dire si elle est vraie ou fausse. Sa valeur de vérité est 1 (vrai) ou 0 (faux).

À partir de propositions simples P, Q, … on forme, à l’aide de connecteurs logiques, des propositions composées. La vérité d’une proposition composée ne dépend que de la vérité de ses parties.

2. Connecteurs et tables de vérité

Le mieux pour montrer comment fonctionne un connecteur, c’est une table de vérité : une ligne pour chaque combinaison de valeurs de P et Q. Deux variables donnent 2 · 2 = 4 combinaisons, n variables 2ⁿ.

• La négation ¬P inverse la valeur.
• La conjonction P ∧ Q (« et ») n’est vraie que si les deux parties sont vraies.
• La disjonction P ∨ Q (« ou ») est vraie si au moins une partie est vraie — y compris les deux.
• L’implication P ⇒ Q (« si…, alors ») n’est fausse que dans un seul cas : P est vraie et Q ne l’est pas.
• L’équivalence P ⇔ Q est vraie quand les deux parties ont la même valeur.
• Le ou exclusif P ⊕ Q (XOR) est vrai quand exactement une des deux est vraie.

3. L’implication : le piège le plus fréquent

Définition — réciproque et contraposée

Pour l’implication P ⇒ Q, la réciproque est Q ⇒ P et la contraposée est ¬Q ⇒ ¬P.

Théorème. Une implication est équivalente à sa contraposée, mais pas à sa réciproque.

La table le montre sans discussion : les colonnes de l’implication et de la contraposée sont identiques, la réciproque diffère sur deux lignes.

Le deuxième piège, ce sont les lignes avec P = 0 : quand l’hypothèse est fausse, l’implication est vraie, quelle que soit Q. « Si 7 est pair, je suis le pape » est une proposition vraie. Cela sonne bizarre, mais c’est logique — l’implication ne promet quelque chose que pour la situation où P est vraie, et cette promesse ne peut pas être rompue quand P est fausse.

4. Tautologies et propositions équivalentes

Définition — tautologie, contradiction, équivalence

Une tautologie est une proposition composée vraie pour toute affectation des variables (p. ex. P ∨ ¬P). Une contradiction est toujours fausse (P ∧ ¬P).

Les propositions A et B sont logiquement équivalentes, A ≡ B, si A ⇔ B est une tautologie — elles ont la même colonne dans la table de vérité.

C’est ainsi qu’on peut vérifier les lois de De Morgan de la partie sur les ensembles : ¬(P ∧ Q) ≡ ¬P ∨ ¬Q. Les colonnes sont identiques :

Vérifier une tautologie avec une table est fiable, mais pour n variables cela fait 2ⁿ lignes. Pour 300 variables, c’est plus de lignes qu’il n’y a d’atomes dans l’univers. La question de savoir si une proposition peut seulement être satisfaite (le problème SAT) est l’un des problèmes difficiles les plus célèbres de l’informatique.

5. Pourquoi XOR a arrêté les premiers réseaux de neurones

Dessinons les quatre combinaisons de P et Q comme des points dans le plan et colorions-les selon le résultat. Pour « et » comme pour « ou », on peut séparer les points verts des points orange par une seule droite. Pour XOR, c’est impossible — les points verts sont sur une diagonale et les orange sur l’autre :

P ∧ Q

P ∨ Q

P ⊕ Q

Le perceptron, le réseau de neurones le plus simple, ne sait séparer des points que par une droite. En 1969, Minsky et Papert ont montré qu’il ne peut donc pas apprendre une fonction aussi simple que XOR, et l’intérêt pour les réseaux de neurones est retombé pour des années. La solution consiste à ajouter une couche : XOR se compose de fonctions plus simples, (P ∨ Q) ∧ ¬(P ∧ Q), et un réseau à deux couches en est capable. C’est là que commence l’histoire de l’apprentissage profond.

6. Prédicats et quantificateurs

Définition — prédicat et quantificateurs

Un prédicat P(x) est une proposition avec une variable : pour chaque x d’un ensemble donné, il devient une proposition (« x est pair »).

∀x ∈ M : P(x) est vraie si P(x) est vraie pour tous les x ∈ M. ∃x ∈ M : P(x) est vraie si elle est vraie pour au moins un.

L’ordre de quantificateurs différents compte : ∀x ∃y : P(x, y) ne signifie en général pas la même chose que ∃y ∀x : P(x, y).

Les définitions en IA sont pleines de quantificateurs. L’heuristique admissible de la partie sur la recherche s’écrit « ∀n : h(n) ≤ h*(n) » — et pour la réfuter, il suffit d’un seul état où l’estimation dépasse.

7. Qu’est-ce qu’une démonstration

Définition — démonstration et modus ponens

Une démonstration d’une affirmation T est une suite finie de propositions qui se termine par T et dans laquelle chaque proposition est soit une hypothèse (axiome, théorème déjà démontré), soit découle des précédentes selon une règle d’inférence.

La règle d’inférence de base est le modus ponens : de P et P ⇒ Q on déduit Q. La règle est correcte, car (P ∧ (P ⇒ Q)) ⇒ Q est une tautologie.

8. Types de démonstrations

Démonstration directe

À partir des hypothèses, on arrive pas à pas à l’affirmation. Affirmation : la somme de deux nombres pairs est paire. Démonstration : les nombres pairs sont 2a et 2b pour des entiers a, b. Leur somme vaut 2a + 2b = 2(a + b), soit le double d’un entier — un nombre pair. ∎

Démonstration par contraposée et par l’absurde

Au lieu de P ⇒ Q, on démontre l’équivalente ¬Q ⇒ ¬P — ou on suppose que l’affirmation est fausse et on aboutit à une absurdité. Affirmation : il existe une infinité de nombres premiers. Démonstration par l’absurde (Euclide) : s’il y en avait un nombre fini, p₁, …, p_k, on prendrait N = p₁ · … · p_k + 1. Aucun p_i ne divise N — il reste toujours 1. N a donc un diviseur premier qui manque dans la liste. Contradiction. ∎

Contre-exemple

Une affirmation « pour tout » se réfute par un seul exemple. « Tout nombre impair supérieur à 1 est premier » est vrai pour 3, 5 et 7 — et tombe sur 9 = 3 · 3. Trois exemples ne démontrent rien, un seul contre-exemple réfute.

Récurrence

Définition — principe de récurrence

Si P(1) est vraie (initialisation) et si pour tout n ≥ 1 on a P(n) ⇒ P(n + 1) (hérédité), alors P(n) est vraie pour tout n ∈ ℕ.

Affirmation : 1 + 2 + … + n = n(n + 1)/2. Initialisation : pour n = 1, on a 1 à gauche et 1 · 2/2 = 1 à droite. Hérédité : si la formule est vraie pour n, alors 1 + … + n + (n + 1) = n(n + 1)/2 + (n + 1) = (n + 1)(n + 2)/2, ce qui est la formule pour n + 1. ∎ L’image montre le même résultat : deux escaliers de points forment ensemble un rectangle n × (n + 1).

En informatique, on démontre par récurrence la correction des algorithmes : « après k itérations de la boucle, on a… ». C’est ainsi qu’on démontre par exemple qu’UCS développe les états dans l’ordre croissant du coût — et trouve donc le chemin le moins cher.

9. La logique en intelligence artificielle

• IA symbolique — les premiers systèmes d’intelligence artificielle étaient logiques : des connaissances écrites sous forme de règles « si–alors » et une déduction par modus ponens. C’est sur cela que reposaient les systèmes experts des années quatre-vingt.
• Les solveurs SAT répondent à la question « cette proposition peut-elle être satisfaite ? » pour des millions de variables — ils planifient, vérifient du matériel et cherchent des erreurs dans les programmes.
• Vérification de l’IA — la logique sert à démontrer des propriétés des systèmes : qu’un pilote automatique ne donne jamais deux ordres contradictoires, ou qu’un réseau de neurones ne change pas sa décision à cause d’un bruit invisible.
• Modèles de langage et démonstrations — les modèles actuels savent écrire des démonstrations, qui sont ensuite contrôlées par des outils formels vérifiant chaque étape mécaniquement.

10. Résumé

• Une proposition est vraie ou fausse ; les connecteurs ¬ ∧ ∨ ⇒ ⇔ ⊕ sont définis précisément par une table de vérité.
• Une implication est équivalente à sa contraposée, pas à sa réciproque — et avec une hypothèse fausse, elle est toujours vraie.
• XOR ne peut pas être séparé par une seule droite, c’est pourquoi un réseau de neurones a besoin de plusieurs couches.
• L’ordre des quantificateurs compte ; une affirmation « pour tout » est réfutée par un seul contre-exemple.
• Une démonstration est une chaîne d’étapes vérifiables : directe, par contraposée, par l’absurde ou par récurrence.

Vous voyez les choses autrement ? Écrivez à support@coden-app.com.