Énoncé:
Une table de vérité binaire à $k$ entrées est une correspondance entre $k$ bits d'entrée (chiffres binaires, $0$ [faux] ou $1$ [vrai]) et $1$ bit de sortie. Par exemple, les tables de vérité binaires à $2$ entrées pour les fonctions logiques ET et XOR sont les suivantes :
$x$ | $y$ | $x \ \text{ET} \ y$ |
---|---|---|
$0$ | $0$ | $0$ |
$0$ | $1$ | $0$ |
$1$ | $0$ | $0$ |
$1$ | $1$ | $1$ |
$x$ | $y$ | $x \ \text{XOR} \ y$ |
---|---|---|
$0$ | $0$ | $0$ |
$0$ | $1$ | $1$ |
$1$ | $0$ | $1$ |
$1$ | $1$ | $0$ |
Combien de tables de vérité binaires à $6$ entrées, $τ$, satisfont à la formule
$τ(a, b, c, d, e, f) \ \text{ET} \ τ(b, c, d, e, f, a \ \text{XOR} \ (b \ \text{ET} \ c)) = 0$
pour toutes les entrées de $6$ bits $(a, b, c, d, e, f)$ ?
Lien du problème originel