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

1. Se rappeler la définition de littéral et des formes normales conjonctives et disjonctives.
2. Identifier les structures d’une expression en FNC et FND.
3. Utiliser FNC ou FND pour simplifier les expressions de la logique propositionnelle.

INDEX
DÉFINITION DU LITTÉRAL
DÉFINITION DES FORMES NORMALES
THÉORÈME DES FORMES NORMALES

Un résultat intéressant et utile de la logique propositionnelle est lié aux formes normales. Pour aborder ces sujets en détail, il est nécessaire de revoir d’abord certains concepts.

Définition du Littéral

Un littéral est toute expression atomique ou la négation d’une expression atomique. En fonction de cela, on parle de littéraux négatifs ou positifs selon que les expressions atomiques sont précédées ou non d’une négation. Par exemple : A serait un littéral positif et \neg A serait un littéral négatif.

Définition des Formes Normales

Une expression F est en forme normale conjonctive (FNC) lorsqu’elle peut être écrite comme une conjonction de disjonctions de littéraux, c’est-à-dire :

\displaystyle F=\bigwedge_{i=1}^n \left( \bigvee_{j=1}^m L_{ij}\right)

De même, on a une forme normale disjonctive (FND) si elle est écrite comme une disjonction de conjonctions de littéraux :

\displaystyle F=\bigvee_{i=1}^n \left(\bigwedge_{j=1}^m L_{ij}\right)

Théorème des Formes Normales

Toutes les expressions de la logique propositionnelle sont équivalentes à une expression en FND et une autre en FNC.

DÉMONSTRATION :

Cela peut être démontré par induction sur la complexité des formules F.

• Cas de base : Si F est une expression atomique, elle peut être écrite à la fois en FNC et en FND, car : F\equiv F_D \equiv F_C, où F_C:=((F\vee F)\wedge (F\vee F)) et F_D:=((F\wedge F)\vee (F\wedge F))
• Étape d’induction : Soient G et H deux expressions quelconques pour lesquelles le résultat du théorème est valable ; c’est-à-dire qu’il existe H_C et G_C en FNC, et H_D et G_D en FND, tels que :

  G\equiv G_D \equiv G_D

  H\equiv H_D \equiv H_D

  Ainsi, nous pouvons écrire :

  \displaystyle G_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} ; \displaystyle G_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC}

  \displaystyle H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{HD} ; \displaystyle H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{HC}

  Sans perte de généralité, si F:= \neg G, alors en utilisant le théorème de substitution et les lois généralisées de De Morgan, on obtient :

  \displaystyle F:= \neg G \equiv \left\{ \begin{matrix} \neg G_D := \neg \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \equiv\bigwedge_{i=1}^n \neg \bigwedge_{j=1}^m L_{ij}^{GD} \equiv \bigwedge_{i=1}^n \bigvee_{j=1}^m \neg L_{ij}^{GD} \\ \\ \neg G_C := \neg \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \neg \bigvee_{j=1}^m L_{ij}^{GC} \equiv \bigvee_{i=1}^n \bigwedge_{j=1}^m \neg L_{ij}^{GC} \end{matrix}\right.

  D’autre part, si F:=G\wedge H, alors selon le théorème de substitution :

  \displaystyle F:=G\wedge H \equiv G_C \wedge H_C := \bigwedge_{i=1}^n \bigvee_{j=1}^m L_{ij}^{GC} \wedge \bigwedge_{i=1}^{n^\prime} \bigvee_{j=1}^{m^\prime} L_{ij}^{HC}

  ce qui est une forme normale conjonctive. Et de même, si F:=H\vee G, alors :

  \displaystyle F:=G\wedge H \equiv G_D \vee H_D := \bigvee_{i=1}^n \bigwedge_{j=1}^m L_{ij}^{GD} \vee \bigvee_{i=1}^{\overline{n}} \bigwedge_{j=1}^{\overline{m}} L_{ij}^{HD}

  c’est-à-dire une forme normale disjonctive.

  Par conséquent, l’induction est complète et toutes les expressions de la logique propositionnelle peuvent être écrites en FND et FNC.

L’étude des formes normales conjonctive (FNC) et disjonctive (FND) de la logique propositionnelle est essentielle pour simplifier et résoudre des problèmes complexes en mathématiques et en informatique. Le théorème qui stipule que toute expression logique peut être écrite à la fois en FND et en FNC est d’une grande importance, car il permet de structurer les propositions de manière plus gérable et standardisée, facilitant ainsi leur analyse et manipulation. L’importance de ce résultat réside dans le fait qu’il fournit une base solide pour la conception d’algorithmes, l’optimisation des expressions logiques et la résolution efficace de problèmes dans divers domaines de la connaissance, tels que l’intelligence artificielle et la vérification des logiciels. De plus, la technique de preuve par induction utilisée pour démontrer ce théorème renforce la compréhension des propriétés fondamentales des expressions logiques et de leur applicabilité dans d’autres contextes mathématiques.