Exhaustivité fonctionnelle

En logique , un ensemble fonctionnellement complet de connecteurs logiques ou d'opérateurs booléens est un ensemble qui peut être utilisé pour exprimer toutes les tables de vérité possibles en combinant les membres de l' ensemble dans une expression booléenne . Un ensemble complet bien connu de connecteurs est { AND , NOT } . Chacun des ensembles singleton { NAND } et { NOR } est fonctionnellement complet. Cependant, l'ensemble {AND, OR } est incomplet, en raison de son incapacité à exprimer NOT.

Une porte (ou un ensemble de portes) fonctionnellement complète peut également être appelée porte universelle (ou ensemble universel de portes).

Dans un contexte de logique propositionnelle , les ensembles fonctionnellement complets de connecteurs sont également appelés ( expressivement ) adéquats .

Du point de vue de l'électronique numérique , la complétude fonctionnelle signifie que chaque porte logique possible peut être réalisée sous forme d'un réseau de portes des types prescrits par l'ensemble. En particulier, toutes les portes logiques peuvent être assemblées soit à partir de portes binaires NAND uniquement , soit à partir de portes binaires NOR uniquement .

Les textes modernes sur la logique prennent généralement comme primitives un sous-ensemble des connecteurs : conjonction ( ) ; disjonction ( ) ; négation ( ) ; conditionnel matériel ( ) ; et éventuellement le biconditionnel ( ). D'autres connecteurs peuvent être définis, si on le souhaite, en les définissant en termes de ces primitives. Par exemple, NOR (la négation de la disjonction, parfois notée ) peut être exprimé comme une conjonction de deux négations :

De même, la négation de la conjonction NAND (parfois désignée par ), peut être définie en termes de disjonction et de négation. Chaque connecteur binaire peut être défini en termes de , ce qui signifie que l'ensemble est fonctionnellement complet. Cependant, il contient une redondance : cet ensemble n'est pas un ensemble minimal fonctionnellement complet, car le conditionnel et le biconditionnel peuvent être définis en termes des autres connecteurs comme

Il s'ensuit que le plus petit ensemble est également fonctionnellement complet. (Sa complétude fonctionnelle est également prouvée par le théorème de la forme normale disjonctive .) Mais cela n'est toujours pas minimal, comme on peut le définir comme

Alternativement, peut être défini en termes de manière similaire, ou peut être défini en termes de :

Aucune simplification supplémentaire n'est possible. Par conséquent, tout ensemble de connecteurs à deux éléments contenant et l'un des est un sous-ensemble minimal fonctionnellement complet de .

Étant donné le domaine booléen B = {0, 1} , un ensemble F de fonctions booléennes f _i : B ^{n _i} → B est fonctionnellement complet si le clone sur B généré par les fonctions de base f _i contient toutes les fonctions f : B ⁿ → B , pour tous les entiers strictement positifs n ≥ 1 . En d'autres termes, l'ensemble est fonctionnellement complet si toute fonction booléenne qui prend au moins une variable peut être exprimée en termes des fonctions f _i . Étant donné que toute fonction booléenne d'au moins une variable peut être exprimée en termes de fonctions booléennes binaires, F est fonctionnellement complet si et seulement si toute fonction booléenne binaire peut être exprimée en termes des fonctions de F .

Une condition plus naturelle serait que le clone généré par F soit constitué de toutes les fonctions f : B ⁿ → B , pour tous les entiers n ≥ 0 . Cependant, les exemples donnés ci-dessus ne sont pas fonctionnellement complets dans ce sens plus fort car il n'est pas possible d'écrire une fonction nulle , c'est-à-dire une expression constante, en termes de F si F lui-même ne contient pas au moins une fonction nulle. Avec cette définition plus forte, les plus petits ensembles fonctionnellement complets auraient 2 éléments.

Une autre condition naturelle serait que le clone engendré par F avec les deux fonctions constantes nulles soit fonctionnellement complet ou, de manière équivalente, fonctionnellement complet au sens fort du paragraphe précédent. L'exemple de la fonction booléenne donnée par S ( x , y , z ) = z si x = y et S ( x , y , z ) = x sinon montre que cette condition est strictement plus faible que la complétude fonctionnelle.

Emil Post a prouvé qu'un ensemble de connecteurs logiques est fonctionnellement complet si et seulement s'il n'est pas un sous-ensemble de l'un des ensembles de connecteurs suivants :

• Les connecteurs monotones ; changer la valeur de vérité de toutes les variables connectées de F à T sans changer aucune de T à F ne fait jamais changer la valeur de retour de ces connecteurs de T à F , par exemple .
• Les connecteurs affines , tels que chaque variable connectée affecte toujours ou jamais la valeur de vérité que ces connecteurs renvoient, par exemple .
• Les connecteurs auto-duaux , qui sont égaux à leur propre dual de Morgan ; si les valeurs de vérité de toutes les variables sont inversées, la valeur de vérité que ces connecteurs renvoient l'est aussi, par exemple , maj ( p , q , r ) .
• Les connecteurs préservant la vérité ; ils renvoient la valeur de vérité T sous toute interprétation qui attribue T à toutes les variables, par exemple .
• Les connecteurs préservant la fausseté ; ils renvoient la valeur de vérité F sous toute interprétation qui attribue F à toutes les variables, par exemple .

Post a donné une description complète du treillis de tous les clones (ensembles d'opérations fermés sous composition et contenant toutes les projections) sur l'ensemble à deux éléments { T , F } , aujourd'hui appelé treillis de Post , ce qui implique le résultat ci-dessus comme simple corollaire : les cinq ensembles de connecteurs mentionnés sont exactement les clones non triviaux maximaux.

Lorsqu'un connecteur logique ou un opérateur booléen est fonctionnellement complet par lui-même, il est appelé fonction de Sheffer ou parfois opérateur unique suffisant . Il n'existe pas d'opérateur unaire possédant cette propriété. NAND et NOR , qui sont duaux l'un de l'autre , sont les deux seules fonctions binaires de Sheffer. Elles ont été découvertes, mais non publiées, par Charles Sanders Peirce vers 1880, et redécouvertes indépendamment et publiées par Henry M. Sheffer en 1913. Dans la terminologie de l'électronique numérique, la porte binaire NAND (↑) et la porte binaire NOR (↓) sont les seules portes logiques binaires universelles .

Voici les ensembles minimaux fonctionnellement complets de connecteurs logiques avec arité ≤ 2 :

Un élément

{↑}, {↓}.

Deux éléments

Trois éléments

Il n'existe pas d'ensemble minimal fonctionnellement complet de plus de trois connecteurs logiques binaires au maximum. Afin de garder les listes ci-dessus lisibles, les opérateurs qui ignorent une ou plusieurs entrées ont été omis. Par exemple, un opérateur qui ignore la première entrée et renvoie la négation de la seconde peut être remplacé par une négation unaire.

• Exemples d'utilisation de la NANDcomplétude (↑). Comme illustré par
  • ¬ A ≡ A ↑ A
  • A ∧ B ≡ ¬( A ↑ B ) ≡ ( A ↑ B ) ↑ ( A ↑ B )
  • A ∨ B ≡ (¬ A ) ↑ (¬ B ) ≡ ( A ↑ A ) ↑ ( B ↑ B )
• Exemples d'utilisation de l' NORexhaustivité (↓). Comme illustré par,
  • ¬ A ≡ A ↓ A
  • A ∨ B ≡ ¬( A ↓ B ) ≡ ( A ↓ B ) ↓ ( A ↓ B )
  • A ∧ B ≡ (¬ A ) ↓ (¬ B ) ≡ ( A ↓ A ) ↓ ( B ↓ B )

Il est à noter qu'un circuit électronique ou une fonction logicielle peut être optimisé par réutilisation, pour réduire le nombre de portes. Par exemple, l'opération " A ∧ B ", lorsqu'elle est exprimée par ↑ portes, est implémentée avec la réutilisation de " A ↑ B ",

X ≡ ( A ↑ B ); A ∧ B ≡ X ↑ X

Outre les connecteurs logiques (opérateurs booléens), la complétude fonctionnelle peut être introduite dans d'autres domaines. Par exemple, un ensemble de portes réversibles est dit fonctionnellement complet s'il peut exprimer tous les opérateurs réversibles.

La porte Fredkin à 3 entrées est une porte fonctionnellement réversible à part entière – un seul opérateur suffisant. Il existe de nombreuses autres portes logiques universelles à trois entrées, comme la porte Toffoli .

En informatique quantique , la porte d'Hadamard et la porte T sont universelles, bien qu'avec une définition légèrement plus restrictive que celle de la complétude fonctionnelle.

Il existe un isomorphisme entre l' algèbre des ensembles et l' algèbre de Boole , c'est-à-dire qu'elles ont la même structure . Alors, si nous transformons les opérateurs booléens en opérateurs d'ensemble, le texte "traduit" ci-dessus est également valable pour les ensembles : il existe de nombreux "ensembles complets minimaux d'opérateurs de théorie des ensembles" qui peuvent générer n'importe quelle autre relation d'ensemble. Les "ensembles complets minimaux d'opérateurs" les plus populaires sont {¬, ∩} et {¬, ∪} . Si l' ensemble universel est interdit , les opérateurs d'ensemble sont limités à la préservation de la fausseté (Ø) et ne peuvent pas être équivalents à l'algèbre de Boole fonctionnellement complète.