Hors programme. Écrire table(f, n) qui produit la table de vérité…

def table(f, n):
    """Toutes les lignes de la table de verite de f, a n entrees.

    Precondition : f accepte n arguments valant 0 ou 1. La ligne k est
    l'ecriture binaire de k sur n bits : on n'oublie ainsi aucun cas.
    """
    lignes = []
    for k in range(2 ** n):
        bits = [(k >> (n - 1 - i)) & 1 for i in range(n)]
        lignes.append((bits, f(*bits)))
    return lignes

>>> table(lambda a, b, c: (a & b) | c, 3)
[([0, 0, 0], 0), ([0, 0, 1], 1), ([0, 1, 0], 0),
 ([0, 1, 1], 1), ([1, 0, 0], 0), ([1, 0, 1], 1),
 ([1, 1, 0], 1), ([1, 1, 1], 1)]

Le décalage (k >> (n - 1 - i)) & 1 extrait le $i$-ème bit de $k$ en partant de la gauche. C'est le procédé du chapitre 1 : le comptage binaire énumère exactement une fois chaque combinaison.

Les deux dénombrements. La table a $2^n$ lignes. Une fonction booléenne, c'est le choix d'un $0$ ou d'un $1$ sur chacune de ces lignes : il y a donc $2^{2^n}$ fonctions distinctes à $n$ variables.

La conclusion, et elle est brutale. Pour $n=2$ : $4$ lignes, $16$ fonctions — on peut toutes les écrire. Pour $n=5$ : $32$ lignes, mais $2^{32}\approx 4$ milliards de fonctions. Pour $n=6$ : $2^{64}$, soit plus de $10^{19}$. Vérifier une équivalence reste faisable ($2^n$ lignes) bien plus longtemps que parcourir les fonctions ($2^{2^n}$) — et même la première tâche devient impraticable vers $n=40$.

Prolongement : décider si une formule booléenne peut être rendue vraie s'appelle le problème SAT. Aucun algorithme connu ne le résout en temps raisonnable dans le pire cas, et savoir s'il en existe un est le problème « P contre NP », l'une des grandes questions ouvertes des mathématiques.