Disjonctive (forme normale)

Imaginez deux interrupteurs, notés p et q, dont un seul doit être activé. La lampe s’allume dans deux situations visibles : p est activé et q ne l’est pas, ou bien q est activé et p ne l’est pas.

Une forme normale disjonctive rassemble précisément ce type de scénarios. Chaque scénario relie des conditions par « et » ; les scénarios possibles sont ensuite reliés par « ou ». La formule est vraie dès qu’au moins un scénario complet est réalisé.

Une forme normale disjonctive, abrégée FND, est une formule propositionnelle formée par un « ou » de termes, chaque terme étant un « et » de littéraux. Un littéral est une proposition atomique, comme p, ou la négation d’une proposition atomique, comme « non p ». Les termes peuvent contenir un seul littéral.

Avec les propositions p, q et r, l’expression suivante possède cette structure :Les parenthèses délimitent deux conjonctions ; leur disjonction forme la FND. Toute formule propositionnelle admet une FND équivalente, c’est-à-dire vraie pour exactement les mêmes affectations de valeurs de vérité. Cette écriture n’est généralement pas unique.

La FND dite canonique associe un terme à chaque ligne vraie de la table de vérité. Dans chacun de ces termes, chaque proposition apparaît une fois, affirmée ou niée selon la ligne. Si aucune ligne n’est vraie, elle est la constante fausse ⊥, qui représente par convention la disjonction vide. En algèbre de Boole, « ou », « et » et « non » deviennent les opérations booléennes correspondantes. Pour des ensembles, la même structure se lit comme une union d’intersections, avec des compléments lorsque des littéraux sont niés.

On veut décrire le cas où une seule des deux propositions p et q est vraie. Données : p et q prennent chacune la valeur vrai ou faux ; la sortie est vraie pour les couples (vrai, faux) et (faux, vrai), et fausse dans les deux autres cas. Les quatre affectations et les deux cas retenus rendent le contrôle visuel immédiat.

1. Pour le couple (vrai, faux), on écrit le terme « p et non q ». Il n’est vrai que dans ce premier cas retenu.

2. Pour le couple (faux, vrai), on écrit « non p et q ». Il n’est vrai que dans le second cas retenu.

3. On relie les deux termes par « ou » :Cette expression est une FND canonique.

Contrôle. Si p et q sont toutes deux vraies, chaque terme contient une négation fausse : la sortie est donc fausse. Si une seule est vraie, un terme complet devient vrai.

À partir d’une table de vérité, la FND canonique se construit en relevant les lignes où la sortie vaut vrai. Elle est préférable à une lecture informelle lorsque chaque cas doit être vérifié sans ambiguïté.

Pour évaluer une formule, on teste séparément ses conjonctions. Dès qu’un terme est entièrement vrai, toute la FND est vraie ; si aucun ne l’est, elle est fausse. Une table complète reste plus adaptée lorsqu’il faut comparer toutes les affectations d’un seul regard.

Dans un circuit logique, une FND suggère une organisation en portes ET suivies d’une porte OU. Une autre écriture équivalente peut toutefois employer moins de portes : le nombre de termes et de littéraux sert alors de critère de choix.

Forme normale conjonctive. Elle inverse les deux niveaux : c’est un « et » de clauses construites avec « ou ». Le critère est la connexion principale entre les groupes. Ainsi, « (p ou q) et non p » est conjonctive, pas disjonctive.

Simple disjonction. Une formule contenant « ou » n’est pas nécessairement une FND. Dans « p ou (q et (r ou s)) », un « ou » reste imbriqué dans une conjonction : la structure exigée n’est pas obtenue.

Ou exclusif. Le « ou » qui relie les termes d’une FND est inclusif : plusieurs termes peuvent être vrais simultanément. Dans l’exemple conducteur, la fonction décrite est exclusive seulement parce que les deux termes imposent des cas incompatibles.

Une écriture correcte peut être redondante. Ajouter un terme déjà couvert ne change pas la fonction. Le symptôme est un scénario dont toutes les affectations vraies le sont déjà par un autre terme ; il faut alors comparer les lignes couvertes avant de conclure que la formule est simplifiée.

La forme canonique peut devenir volumineuse. Avec n propositions, une table possède $2^{n}2^n$ affectations. Une fonction vraie sur beaucoup de lignes produit donc beaucoup de termes canoniques ; il faut rechercher ensuite une FND équivalente plus courte si la taille importe.

Un terme contradictoire ne réalise aucun cas. Une conjonction contenant à la fois p et « non p » est toujours fausse. Elle peut être supprimée, mais sa présence ne rend pas fausse toute la FND si un autre terme peut devenir vrai.

La conversion ne garantit pas la simplification. Développer mécaniquement une formule peut multiplier les termes. Pour un circuit, il faut vérifier l’équivalence puis comparer réellement le nombre de portes ou de littéraux, au lieu de prendre l’étiquette « normale » pour « minimale ».

L’algèbre de Boole replace la FND parmi les opérations et les identités qui justifient les transformations de formules.

La table de vérité donne la procédure exhaustive qui construit la FND canonique à partir des lignes vraies.

La fonction booléenne montre quel objet reste inchangé lorsque deux FND différentes ont exactement les mêmes valeurs.