OBJECTIFS D’APPRENTISSAGE :
À la fin de ce cours, l’étudiant sera capable de :

1. Comprendre le concept d’induction sur la complexité des expressions.
2. Appliquer l’induction mathématique sur la complexité des formules en logique propositionnelle.
3. Comprendre la démonstration par induction sur la complexité et comment elle est appliquée en logique propositionnelle.

CONTENU
INDUCTION SUR LA COMPLEXITÉ
UN EXEMPLE SIMPLE : LE THÉORÈME DE SUBSTITUTION

Induction sur la complexité

Supposons que nous voulions prouver qu’une propriété \mathcal{P} s’applique à toute expression F. Une manière de le démontrer consiste à utiliser la variante de l’induction mathématique appelée « induction sur la complexité des expressions ». Cela se fait à travers les étapes suivantes :

• Premièrement, nous montrons que toutes les expressions atomiques satisfont cette propriété (cela correspond au cas n=1 d’une induction traditionnelle).
• Ensuite, en supposant que cette propriété est vraie pour des expressions quelconques F et G, nous prouvons qu’elle est également vraie pour des expressions de la forme F\downarrow G; ou équivalemment, pour \neg F et l’une des suivantes : F\wedge G, F\vee G, F\rightarrow G.

Si nous réussissons cela, alors nous concluons que la propriété \mathcal{P} s’applique à toutes les expressions de la logique propositionnelle. C’est ce qu’on appelle « l’induction mathématique sur la complexité des expressions ».

Un exemple simple : le théorème de substitution

Pour mieux comprendre comment fonctionne l’induction sur la complexité des formules, nous allons examiner le (méta)théorème de substitution.

Supposons que F\equiv G. Soit H une expression contenant F comme sous-expression, et soit H^\prime l’expression obtenue en remplaçant toutes les occurrences de F par G, alors H\equiv H^\prime.

Démonstration par induction sur la complexité des formules

La démonstration par induction sur la complexité consiste à montrer deux choses : 1) un cas initial (pour les formules atomiques) et 2) le pas inductif (si cela fonctionne pour des expressions quelconques F et G, alors cela fonctionne pour F\downarrow G, ou plus simplement : cela fonctionne pour \neg F et pour au moins une des suivantes : F\vee G, F\wedge G, F\rightarrow G ou F\leftrightarrow G).

Supposons que H soit une expression atomique, F est une sous-expression de H et F\equiv G. Si H^\prime est le résultat du remplacement de toutes les sous-expressions F de H, alors puisque H est atomique, nous avons H^\prime \equiv G. D’autre part, comme H est atomique et F est une sous-expression de H, alors H\equiv F. Enfin, nous obtenons :

H\equiv F \equiv G \equiv H^\prime

Ainsi, le cas initial pour les expressions atomiques est démontré.

Passons maintenant au pas inductif.

L’hypothèse d’induction

Supposons que le théorème fonctionne pour deux expressions quelconques H_1 et H_2, chacune contenant F comme sous-expression et F \equiv G. Alors si H_1^\prime est ce que nous obtenons en remplaçant toutes les F par G dans H_1 et que H_2^\prime est ce que nous obtenons en remplaçant toutes les F par G dans H_2, alors nous avons H_1\equiv H_1^\prime et H_2\equiv H_2^\prime.

Le pas inductif

Ici, nous allons vérifier si, en conséquence de l’hypothèse d’induction, le théorème s’applique également à \neg H_1 (ou \neg H_2, l’une ou l’autre) et pour au moins une des suivantes : H_1 \wedge H_2, H_1 \vee H_2, H_1 \rightarrow H_2.

Si H:= \neg H_1, alors, selon l’hypothèse d’induction, H\equiv \neg H_1^\prime=: H^\prime , où H^\prime est le résultat du remplacement de toutes les occurrences de F dans H par G. Par conséquent, H\equiv H^\prime.

De même, si H:= H_1 \wedge H_2, alors, selon l’hypothèse d’induction, H\equiv H_1^\prime \wedge H_2 \equiv H_1^\prime \wedge H_2^\prime =: H^\prime , où H^\prime est le résultat du remplacement de toutes les occurrences de F dans H par G. Par conséquent, H\equiv H^\prime.

Ainsi, l’induction est complète et le théorème de substitution est valable pour toutes les expressions de la logique propositionnelle.

En appliquant cette forme d’induction, il est possible de garantir qu’une propriété s’applique à toutes les expressions d’un système logique, ce qui est particulièrement utile en logique propositionnelle pour structurer des démonstrations rigoureuses. De plus, son utilité s’étend à des domaines tels que l’intelligence artificielle et le développement de logiciels, où la vérification des systèmes logiques est essentielle. Grâce à cette technique, il est possible d’automatiser les démonstrations et d’assurer la cohérence des expressions complexes, ce qui réduit le risque d’erreurs et améliore la précision dans les environnements dépendant de la validité mathématique et logique.