Combien de fonctions logiques différentes peut-on construire avec n entrées, et peut-on toutes les réaliser avec ET, OU, NON ?

Pourquoi cette question : un modèle d'introduction

Le jury attend que vous expliquiez pourquoi vous avez choisi la question. Inspirez-vous de ce modèle, mais racontez votre propre parcours.

En NSI, nous avons rempli des tables de vérité pour ET, OU et OU exclusif. Je me suis demandé combien de fonctions différentes on pourrait inventer avec deux entrées, puis avec plus. Le dénombrement donne des nombres vertigineux, et pourtant trois opérations suffisent à toutes les construire : c'est ce qui permet de fabriquer un processeur avec quelques types de portes.

L'enjeu et les notions du programme

Dénombrer des fonctions par le principe multiplicatif appliqué deux fois, et démontrer qu'un petit ensemble d'opérations suffit à toutes les exprimer.

Le plan de l'exposé en 9,5 min

1. 1. Introduction

   1 min

   Une fonction booléenne associe à chaque combinaison de $n$n entrées (0 ou 1) une sortie (0 ou 1). Problématique : combien en existe-t-il, et faut-il une porte différente pour chacune ?

2. 2. Mathématiques : un double dénombrement

   4 min

   Les entrées forment un mot de $n$n bits : il y a $2^n$2ⁿ combinaisons, donc $2^n$2ⁿ lignes dans la table de vérité. Une fonction est déterminée par sa colonne de sortie : un choix de 0 ou 1 pour chacune des $2^n$2ⁿ lignes. Par le principe multiplicatif, il y a $2^{2^n}$2^(2ⁿ) fonctions.

   Pour $n=1$n=1 : 4 fonctions (constante 0, constante 1, identité, NON). Pour $n=2$n=2 : $2^4=16$2⁴=16 (dont ET, OU, OU exclusif, NON-ET…). Pour $n=3$n=3 : $2^8=256$2⁸=256. Pour $n=6$n=6 : $2^{64}\approx 1,8\times 10^{19}$2⁶⁴≈1,8×10¹⁹. La croissance est « doublement exponentielle ».

   Pourtant, toute fonction s'écrit avec ET, OU, NON. Pour chaque ligne où la fonction vaut 1, on écrit le ET des entrées (ou de leurs négations) qui reconnaît exactement cette ligne ; puis on fait le OU de ces termes. Exemple : le OU exclusif vaut 1 sur les lignes $(1;0)$(1;0) et $(0;1)$(0;1) : $a\oplus b=(a\wedge \neg b)\vee (\neg a\wedge b)$a⊕ b=(awedgeneg b)vee(neg awedge b).

3. 3. NSI : des portes aux processeurs

   3 min

   Cette méthode, appelée forme normale disjonctive, garantit qu'on peut réaliser n'importe quelle fonction avec trois types de portes. On peut même se contenter d'une seule : la porte NON-ET, car $\neg a=a\text{NAND}a$neg a=a NAND a, et ET, OU s'en déduisent. Les usines de puces fabriquent ainsi des milliards de portes identiques.

   La forme normale peut être très longue (jusqu'à $2^n$2ⁿ termes) : simplifier un circuit, c'est trouver une écriture plus courte de la même fonction. En Python, on vérifie l'égalité de deux expressions en comparant leurs sorties sur les $2^n$2ⁿ lignes.

4. 4. Conclusion

   1,5 min

   Il existe $2^{2^n}$2^(2ⁿ) fonctions booléennes à $n$n entrées, un nombre gigantesque, mais toutes se construisent avec ET, OU, NON, et même avec la seule porte NON-ET. C'est ce qui rend possible la fabrication des processeurs. J'ouvre sur le problème de trouver le plus petit circuit pour une fonction donnée, très difficile en général.

Ce que j'écris au tableau

Pas de calculatrice ni de support numérique : un calcul clé écrit au tableau rend l'exposé concret et montre la solidité des connaissances.

Conclusion : la réponse à la question

Les questions probables du jury

Pendant les 10 minutesd'échange, le jury vous fait préciser et approfondir, sur tout le programme de vos spécialités en lien avec la question.

Les pièges qui coûtent des points

• Confondre 2^(2ⁿ) et (2²)ⁿ = 4ⁿ.
• Oublier les fonctions constantes dans le décompte.
• Croire qu'il faut une porte différente par fonction.

Revoir les notions

• Combinatoire et dénombrement (Terminale spé maths) →
• Nombres et calculs (Seconde) →

Autres questions : logique et calculabilité

• Peut-on écrire un programme qui détecte tous les programmes qui tournent en boucle infinie ?
• Existe-t-il des nombres qu'aucun programme ne pourra jamais calculer ?
• Pourquoi « non (a et b) » ne veut-il pas dire « non a et non b », et pourquoi cette erreur cause-t-elle tant de bugs ?
• Comment démontrer qu'un algorithme avec une boucle donne toujours le bon résultat ?

Toutes les questions maths-nsi →