OBJECTIFS D’APPRENTISSAGE :
À la fin de cette leçon, l’étudiant sera capable de :

1. Appliquer l’algorithme FND/FNC à des expressions concrètes pour trouver leurs formes normales conjonctive et disjonctive.
2. Comprendre l’utilisation des interrupteurs simples et composés dans la logique propositionnelle.
3. Identifier la structure des interrupteurs composés et des boîtes noires.
4. Utiliser le tableau de vérité pour résumer les informations sur un dispositif.
5. Extraire la FND et la FNC d’un dispositif à partir de son tableau de vérité.
6. Concevoir un interrupteur composé ayant le même fonctionnement qu’un dispositif donné.

TABLE DES MATIÈRES
L’ALGORITHME FND/FNC
ALGORITHME POUR OBTENIR LA FORME NORMALE À PARTIR DES TABLES DE VÉRITÉ : BOÎTES NOIRES ET INTERRUPTEURS COMPOSÉS
EXERCICES D’EXEMPLE

Bien que nous ayons prouvé que toutes les expressions de la logique propositionnelle sont équivalentes à une forme normale, nous n’avons rien dit sur la manière de trouver ces formes normales. Pour y parvenir, nous examinerons un algorithme dont le but est de générer des expressions en forme normale, et enfin, nous examinerons les applications qui émergent de ces sujets.

L’Algorithme FND/FNC

L’algorithme FND/FNC est une série d’étapes qui vous permettra de trouver, à partir de toute expression de la logique propositionnelle, son expression équivalente en FND ou FNC (selon le cas). Il est effectué de la manière suivante :

• ÉTAPE 1 : Remplacez toutes les sous-expressions de la forme (F\rightarrow G) par (\neg F\vee G), de même pour (F\leftrightarrow G). Répétez cette étape jusqu’à ce que toutes les implications et doubles implications soient éliminées de l’expression.
• ÉTAPE 2 : Éliminez les doubles négations et appliquez les lois de De Morgan là où c’est possible. Les remplacements suivants doivent être appliqués
  • \neg\neg G \longmapsto G
  • \neg(G\wedge H) \longmapsto (\neg G \vee \neg H)
  • \neg(G\vee H) \longmapsto (\neg G \wedge \neg H)

    Lorsqu’il n’y a plus de sous-expressions de la forme \neg\neg G, \neg(G \wedge H) ou \neg(G \vee H), continuez avec l’étape 3.

• ÉTAPE 3 : Cette étape est divisée en deux parties selon si vous souhaitez arriver à une FND ou à une FNC
  • Si vous voulez arriver à une FNC :

    Utilisez la distribution \vee là où c’est possible. C’est-à-dire, appliquez les remplacements suivants :

    \left.\begin{matrix}G\vee(H\wedge K) \\ \\ (H\wedge K)\vee G \end{matrix} \right\} \longmapsto (G\vee H)\wedge (G\vee K)

    Lorsqu’il n’y a plus d’expressions de la forme G\vee(H\wedge K) ou (H\wedge K)\vee G, vous aurez atteint une FNC.

  • Si vous voulez arriver à une FND :

    Utilisez la distribution \wedge là où c’est possible. C’est-à-dire, appliquez les remplacements suivants :

    \left.\begin{matrix}G\wedge(H\vee K) \\ \\ (H\vee K)\wedge G \end{matrix} \right\} \longmapsto (G\wedge H)\vee (G\vee K)

    Lorsqu’il n’y a plus d’expressions de la forme G\wedge(H\vee K) ou (H\vee K)\wedge G, vous aurez atteint une FND.

Exemples

Utilisez l’algorithme FND/FNC pour les expressions suivantes dans leurs formes normales conjonctive et disjonctive.

1. (A\rightarrow (B\rightarrow A)) [SOLUTION]
2. ((A\vee B)\rightarrow(\neg B \wedge A)) [SOLUTION]

Algorithme pour Obtenir la Forme Normale à partir des Tables de Vérité: Boîtes Noires et Interrupteurs Composés

L’algorithme FND/FNC nous permet de trouver, pour toute expression de la logique propositionnelle, son expression équivalente en forme normale. Mais il existe des situations où nous n’avons pas d’expression initiale sur laquelle travailler. C’est le cas lorsque nous avons le résultat d’une table de vérité d’une expression F dont nous ne connaissons pas la structure propositionnelle. Expliquer cela en mots est un processus long ; cependant, la technique est beaucoup mieux comprise en montrant des exemples de la manière dont elle se développe, donc je laisserai quelques exemples que je développerai en vidéo, mais d’abord, vous devez revoir les concepts suivants :

• Câble : Moyen par lequel un signal circule
• Nœud : Point où 3 ou plus de câbles se rejoignent.
• Interrupteur simple : Dispositif qui admet les états de marche (1) et d’arrêt (0), étant toujours dans un, et un seul, de ces états. L’état de marche permet le passage d’un signal et l’état d’arrêt l’empêche.
• Interrupteur composé : C’est un dispositif composé d’interrupteurs simples et de câbles.
• Boîte Noire : C’est tout dispositif dont la structure interne ne peut être observée.

Les interrupteurs simples sont modélisés à travers des variables propositionnelles, et les composés à travers des expressions de la logique propositionnelle. Les cas les plus simples sont ceux obtenus à partir des connecteurs de disjonction et de conjonction illustrés ci-dessous

Schéma de la Conjonction

Schéma de la Disjonction

Exercices d’Exemple

1. Un dispositif est formé par une boîte noire et 4 interrupteurs ordonnés. L’activation du dispositif se produit dans les conditions suivantes
   • Condition 1 : Il est activé s’il y a deux interrupteurs consécutifs allumés. Cette condition cesse de fonctionner s’il y a trois interrupteurs consécutifs allumés.
   • Condition 2 : Il est activé si tous les interrupteurs sont éteints.
   • Exception : Si les conditions précédentes ne sont pas remplies, l’appareil s’éteint.

   a) Résumez cette information dans un tableau de vérité [SOLUTION]

   b) À partir du tableau de vérité, extrayez la FND et la FNC qui reproduisent le fonctionnement de la machine. [SOLUTION]

   c) Utilisez la FNC ou la FND obtenue à l’étape précédente (la plus simple) pour concevoir un interrupteur composé ayant le même fonctionnement que le dispositif. [SOLUTION]

2. La même chose que dans l’exercice précédent, sauf que maintenant le dispositif a 5 interrupteurs. [DÉFI POUR LE LECTEUR]