Exercices corrigés : logique booléenne et mathématique (201-N11)

a) $\lnot q$ inverse la colonne de $q$, puis on applique le ET, qui ne vaut 1 que si les deux colonnes valent 1. Lignes dans l'ordre $(p,q)=(1,1),(1,0),(0,1),(0,0)$ : $\lnot q$ vaut $0,1,0,1$ et $p\land\lnot q$ vaut $0,1,0,0$. L'expression n'est donc vraie que sur la ligne $p=1$, $q=0$. C'est exactement la ligne où $p\Rightarrow q$ est fausse, ce qui n'est pas un hasard : $p\land\lnot q$ est la négation de $p\Rightarrow q$.

b) Une seule ligne : $p=1$ et $q=0$. Une implication n'est fausse que lorsque la prémisse est vraie et la conclusion fausse. Sur l'exemple : la promesse « si le fichier existe, alors la lecture réussit » n'est trahie que dans le cas où le fichier existe bel et bien et où la lecture échoue quand même. Si le fichier n'existe pas, la promesse n'est pas testée, et on la déclare tenue : les deux dernières lignes valent 1. C'est le point que les étudiants refusent le plus longtemps, parce que le « si » du français porte une idée de cause que le $\Rightarrow$ de la logique n'a pas.

c) $p\oplus q$ vaut 1 quand les deux valeurs diffèrent : $0,1,1,0$ sur les quatre lignes. $p\Leftrightarrow q$ vaut 1 quand elles sont égales, soit $1,0,0,1$, donc sa négation vaut $0,1,1,0$. Les deux colonnes sont identiques : $p\oplus q$ et $\lnot(p\Leftrightarrow q)$ sont la même fonction booléenne. Deux expressions sont équivalentes exactement quand leurs tables coïncident ligne à ligne, et c'est la seule preuve d'équivalence qui ne demande aucune astuce.

d) Avec $n$ propositions, chaque proposition prend 2 valeurs indépendamment des autres : la table compte $2^{n}$ lignes, donc $2^{5}=32$ lignes pour cinq propositions. Pour compter les fonctions de deux variables, on remarque qu'une fonction est entièrement déterminée par la colonne de résultats qu'elle produit, soit 4 cases à remplir par 0 ou 1 : il y a $2^{4}=16$ fonctions booléennes de deux variables. Elles ont toutes un nom : ET, OU, XOR, NAND, NOR, l'implication, les deux constantes, et ainsi de suite. Piège classique : répondre 4 en confondant le nombre de lignes et le nombre de fonctions.

a) $A + AB = A(1+B) = A \cdot 1 = A$, car $1+B=1$ : un OU avec 1 vaut toujours 1. C'est la loi d'absorption. Lecture : si $A$ suffit déjà à rendre l'expression vraie, ajouter un cas plus exigeant ($A$ ET $B$) n'ajoute rien. Piège : écrire $A+AB = A+B$ en « simplifiant » comme en algèbre ordinaire.

b) On développe : $(A+B)(A+\overline{B}) = AA + A\overline{B} + BA + B\overline{B}$. Or $AA=A$ (idempotence), $B\overline{B}=0$ (une variable et sa négation ne sont jamais vraies ensemble), donc il reste $A + A\overline{B} + AB = A(1+\overline{B}+B) = A$. On peut aussi appliquer directement la distributivité du OU sur le ET : $(A+B)(A+\overline{B}) = A + B\overline{B} = A+0 = A$. Cette seconde distributivité, $X+YZ = (X+Y)(X+Z)$, n'a pas d'équivalent avec les nombres réels : c'est elle qu'on oublie.

c) De Morgan donne $\overline{AB} = \overline{A}+\overline{B}$, donc $\overline{AB}+\overline{A} = \overline{A}+\overline{B}+\overline{A} = \overline{A}+\overline{B}$ par idempotence, soit encore $\overline{AB}$. L'expression valait déjà $\overline{AB}$ dès le départ : le terme $\overline{A}$ était absorbé.

d) De Morgan sur le premier facteur : $\overline{\overline{A}+\overline{B}} = \overline{\overline{A}} \cdot \overline{\overline{B}} = AB$. L'expression devient $AB(A+B) = ABA + ABB = AB + AB = AB$. Résultat : $AB$. La barre longue se lève d'un seul coup et change le connecteur ; la barre courte sur chaque lettre, elle, reste.

e) $A \oplus A = 0$ : deux valeurs identiques donnent 0. $A \oplus \overline{A} = 1$ : elles diffèrent toujours. $A \oplus 0 = A$ : le XOR avec 0 laisse passer. Ces trois identités sont la base du chiffrement par XOR et de l'échange de deux variables sans variable auxiliaire.

f) Table de $(A+B)(A+\overline{B})$ sur les lignes $(A,B)=(1,1),(1,0),(0,1),(0,0)$ : $A+B$ vaut $1,1,1,0$ ; $A+\overline{B}$ vaut $1,1,0,1$ ; leur produit vaut $1,1,0,0$. C'est exactement la colonne de $A$. La table confirme la simplification, et c'est le seul contrôle qui ne se discute pas.

a) Contraposée : $s \Rightarrow \lnot c$, soit « si le programme contient une erreur de syntaxe, alors il ne compile pas ». La contraposée échange ET nie les deux membres. Elle a toujours la même valeur de vérité que l'implication de départ : les deux ont la même table. C'est ce qui autorise le raisonnement par contraposition en démonstration.

b) Réciproque : $\lnot s \Rightarrow c$, soit « si le programme ne contient pas d'erreur de syntaxe, alors il compile ». Elle est fausse : un programme syntaxiquement correct peut échouer à la compilation pour une erreur de type, une bibliothèque manquante ou un fichier introuvable. C'est un contre-exemple, et un seul suffit. La réciproque n'a aucune raison de partager la valeur de vérité de l'implication : les confondre est l'erreur de raisonnement la plus fréquente du cours.

c) Nier une implication, c'est affirmer la prémisse et nier la conclusion : $\lnot P = c \land s$, soit « le programme compile ET il contient une erreur de syntaxe ». La négation d'une implication n'est jamais une implication, et surtout pas $c \Rightarrow s$. Le repère : une promesse ne se réfute qu'en exhibant le cas où elle est trahie.

d) Table sur les lignes $(p,q)=(1,1),(1,0),(0,1),(0,0)$. $p \Rightarrow q$ vaut $1,0,1,1$. Pour $\lnot p \lor q$ : $\lnot p$ vaut $0,0,1,1$, donc $\lnot p \lor q$ vaut $1,0,1,1$. Les deux colonnes coïncident sur les quatre lignes, donc les expressions sont équivalentes. Cette identité est la porte d'entrée de toute la logique dans les circuits : une implication se câble avec un NON et un OU.

e) $\lnot(p \Rightarrow q) = \lnot(\lnot p \lor q) = p \land \lnot q$ par De Morgan. On retrouve la réponse de la question c) par le calcul, ce qui la confirme.

f) Exemple : dans une boucle qui parcourt un tableau vide, l'énoncé « pour tout tour effectué, le compteur augmente » est vrai à vide, puisqu'aucun tour n'est effectué. Un test unitaire portant sur un tableau vide passe donc toujours si sa condition porte sur les éléments : il ne prouve rien. C'est pourquoi une spécification de la forme « si le tableau contient un doublon, alors la fonction renvoie vrai » doit être testée sur un cas où la prémisse est effectivement vraie.

a) $\forall i \in \{0,\dots,n-1\},\ T[i] > 0$. On quantifie sur les indices, pas sur les valeurs : c'est la forme qui se traduit directement en boucle.

b) La négation échange le quantificateur et nie la propriété : $\exists i \in \{0,\dots,n-1\},\ T[i] \le 0$, soit « il existe au moins un élément de $T$ qui est négatif ou nul ». En français, la négation de « tous » n'est pas « aucun » mais « au moins un ne l'est pas ». Confondre les deux est l'erreur la plus coûteuse du chapitre, parce qu'elle passe inaperçue à la relecture.

c) « $T$ contient au moins un doublon » s'écrit $\exists i,\ \exists j,\ (i \neq j) \land (T[i]=T[j])$. Sa négation est $\forall i,\ \forall j,\ (i \neq j) \Rightarrow (T[i] \neq T[j])$ : tous les éléments sont deux à deux distincts. Notez que la négation d'un $\exists$ suivi d'un ET donne un $\forall$ suivi d'une implication, et non d'un ET.

d) Le premier est vrai : pour chaque $x$, on choisit $y=-x$, et ce choix a le droit de dépendre de $x$ puisque $y$ est quantifié après. Le second est faux : il faudrait un unique $y$ qui annule tous les $x$ à la fois, or $y$ conviendrait pour $x=-y$ et échouerait pour $x=-y+1$. La comparaison montre que l'ordre des quantificateurs n'est pas décoratif : $\forall\exists$ et $\exists\forall$ sont deux énoncés différents, et l'un peut être vrai quand l'autre est faux.

e) Il est vrai. Sur un tableau vide il n'y a aucun indice $i$, donc aucune occasion de trouver un contre-exemple : l'énoncé est vrai à vide. Une fonction qui parcourt le tableau et renvoie vrai si aucune violation n'a été trouvée renvoie donc bien vrai sur le tableau vide, ce qui est le comportement correct et non un bogue.

f) Pour vérifier l'énoncé, il faut aller au bout : $n$ comparaisons au pire, et exactement $n$ quand l'énoncé est vrai. Pour le réfuter, un seul contre-exemple suffit, donc 1 comparaison au mieux, $n$ au pire si le seul élément fautif est le dernier. Cette asymétrie est celle du $\forall$ : coûteux à confirmer, parfois immédiat à infirmer. Pour un $\exists$, c'est l'inverse.

a) Les lignes où $f=1$ sont $(0,1,1)$, $(1,0,1)$, $(1,1,0)$ et $(1,1,1)$. Chaque ligne donne un produit : $\overline{A}BC$, $A\overline{B}C$, $AB\overline{C}$ et $ABC$. D'où $f = \overline{A}BC + A\overline{B}C + AB\overline{C} + ABC$. La règle : une variable qui vaut 1 sur la ligne entre telle quelle, une variable qui vaut 0 entre barrée. Chaque produit vaut 1 sur sa ligne et sur elle seule, donc la somme vaut 1 exactement sur les quatre lignes voulues.

b) Chaque produit de trois variables demande 2 portes ET à deux entrées, soit 8 portes ET, plus 3 portes NON (une par variable barrée, ici $\overline{A}$, $\overline{B}$, $\overline{C}$), plus 3 portes OU pour relier les 4 termes. Total : 14 portes. C'est précisément ce coût qui motive la simplification.

c) On développe la forme proposée. $AB$ vaut 1 sur les lignes $(1,1,0)$ et $(1,1,1)$ ; $BC$ vaut 1 sur $(0,1,1)$ et $(1,1,1)$ ; $AC$ vaut 1 sur $(1,0,1)$ et $(1,1,1)$. La réunion de ces lignes est $\{(0,1,1),(1,0,1),(1,1,0),(1,1,1)\}$, exactement l'ensemble des lignes où $f=1$, et aucune autre ligne n'est atteinte. Les tables coïncident, donc $f = AB+BC+AC$. Par le calcul : $ABC$ apparaît dans les trois termes et se laisse dupliquer par idempotence, ce qui permet de recoller $\overline{A}BC + ABC = BC$, $A\overline{B}C+ABC = AC$ et $AB\overline{C}+ABC = AB$. On passe de 14 portes à 5.

d) $f$ vaut 1 exactement quand au moins deux des trois variables valent 1 : c'est la fonction majorité. Elle sert au vote à trois modules dans les systèmes redondants, où l'on accepte la panne d'un capteur sur trois.

e) $\overline{f}$ vaut 1 sur les quatre lignes restantes : $(0,0,0)$, $(0,0,1)$, $(0,1,0)$ et $(1,0,0)$. D'où $\overline{f} = \overline{A}\,\overline{B}\,\overline{C} + \overline{A}\,\overline{B}C + \overline{A}B\overline{C} + A\overline{B}\,\overline{C}$, soit bien 4 termes. Les 8 lignes se répartissent entre $f$ et $\overline{f}$ sans reste : c'est un contrôle gratuit à faire systématiquement.

a) La ligne $AB=01$ signifie $A=0$ et $B=1$ ; la colonne $CD=11$ signifie $C=1$ et $D=1$. Le numéro vaut $8(0)+4(1)+2(1)+1 = 7$, qui figure bien dans la liste. Le contrôle vaut la peine d'être fait sur deux ou trois cases avant de grouper quoi que ce soit : un tableau mal rempli produit une simplification impeccable de la mauvaise fonction.

b) On teste la colonne $CD=11$, qui est entièrement à 1. Ses quatre numéros sont $3$ (ligne 00), $7$ (ligne 01), $15$ (ligne 11) et $11$ (ligne 10). Or $3$ et $11$ ne figurent pas dans la liste $\{0,2,5,7,8,10,13,15\}$. Les cases fautives sont donc celles des lignes $AB=00$ et $AB=10$ dans la colonne $CD=11$ : elles valent 0. En les corrigeant, le tableau devient : ligne $00$ : $1,0,0,1$ ; ligne $01$ : $0,1,1,0$ ; ligne $11$ : $0,1,1,0$ ; ligne $10$ : $1,0,0,1$. On compte alors 8 cases à 1, ce qui correspond aux 8 minterms annoncés. Ce décompte est le contrôle à ne pas sauter.

c) Premier groupe : les quatre coins du tableau, cases $(AB,CD) = (00,00), (00,10), (10,00), (10,10)$, soit les numéros $0, 2, 8, 10$. Les bords opposés étant voisins, ces quatre coins forment bien un rectangle de 4. Sur ce groupe $A$ change, $C$ change, mais $B=0$ et $D=0$ partout : il donne $\overline{B}\,\overline{D}$. Deuxième groupe : le bloc central des lignes $01$ et $11$ sur les colonnes $01$ et $11$, soit les numéros $5, 7, 13, 15$. $A$ change, $C$ change, mais $B=1$ et $D=1$ : il donne $BD$. Les 8 cases sont couvertes, donc $f = \overline{B}\,\overline{D} + BD$. Les variables $A$ et $C$ ont disparu : la fonction ne dépend pas d'elles.

d) $f$ vaut 1 exactement quand $B$ et $D$ ont la même valeur : c'est le NON-OU-exclusif, $f = \overline{B \oplus D}$, appelé comparateur d'égalité. C'est la brique de base d'un comparateur de mots binaires : on teste l'égalité bit à bit puis on relie les résultats par des ET.

e) Forme canonique : 8 minterms de 4 variables, soit 24 portes ET à deux entrées, 7 portes OU et 4 portes NON, environ 35 portes. Forme simplifiée : 2 portes NON, 2 portes ET, 1 porte OU, soit 5 portes, ou une seule porte XNOR si le catalogue en propose une. Le rapport est de l'ordre de 7 pour 1, et il se paie en surface de silicium, en consommation et en délai de propagation.

a) $A$ et $B$ entrent tous deux dans la porte XOR du haut et dans la porte ET du bas. Donc $S = A \oplus B$ et $R = AB$. Les points sur les fils marquent les dérivations : un même signal alimente deux portes, ce qui est permis et ne coûte rien de plus qu'une piste.

b) Lignes $(A,B) = (0,0), (0,1), (1,0), (1,1)$. $S$ vaut $0, 1, 1, 0$ et $R$ vaut $0, 0, 0, 1$. En lisant $R$ comme le bit de poids fort et $S$ comme le bit de poids faible, le couple $(R,S)$ vaut $00, 01, 01, 10$ en binaire, soit $0, 1, 1, 2$ en décimal : c'est exactement $A+B$. Le circuit additionne. Le cas $1+1$ est celui qui justifie la retenue : la somme vaut 2, qui ne tient pas sur un bit.

c) $S = A \oplus B \oplus R_e$ : la somme vaut 1 quand un nombre impair d'entrées vaut 1. $R_s = AB + R_e(A \oplus B)$ : il y a retenue soit parce que $A$ et $B$ valent tous deux 1, soit parce qu'exactement un des deux vaut 1 et que la retenue entrante s'y ajoute. Contrôle numérique : pour toute combinaison, $2R_s + S = A+B+R_e$, ce qui vaut 0, 1, 2 ou 3. On câble ce bloc $n$ fois en chaîne pour additionner deux mots de $n$ bits.

d) NON : $\overline{A} = A \uparrow A$, une seule NAND, en reliant les deux entrées ensemble. ET : $AB = \overline{\overline{AB}} = (A \uparrow B) \uparrow (A \uparrow B)$, soit 2 NAND. OU : par De Morgan, $A+B = \overline{\overline{A} \cdot \overline{B}} = \overline{A} \uparrow \overline{B} = (A \uparrow A) \uparrow (B \uparrow B)$, soit 3 NAND. Comme tout circuit se décrit avec NON, ET et OU, tout circuit se décrit avec des NAND seules : la porte est dite universelle. La porte NOR l'est également.

e) Parce qu'une usine qui ne grave qu'un seul motif de transistors le grave mieux, le teste avec un seul banc et le remplace partout par la même cellule de bibliothèque. En technologie CMOS, la NAND est en outre la porte la moins chère : 4 transistors, contre 6 pour un ET, qui n'est qu'une NAND suivie d'un inverseur. Un circuit entièrement en NAND est donc souvent plus petit que le même circuit écrit avec des ET et des OU, même s'il compte davantage de portes sur le schéma.

1) FAUX. Une implication et sa réciproque sont deux énoncés indépendants. « Si $x=2$ alors $x^{2}=4$ » est vraie, mais sa réciproque « si $x^{2}=4$ alors $x=2$ » est fausse pour $x=-2$. Énoncé correct : une implication a toujours la même valeur de vérité que sa CONTRAPOSÉE, jamais nécessairement que sa réciproque.

2) FAUX. C'est la loi de De Morgan mal appliquée : la barre qui se lève change aussi le connecteur. Contre-exemple avec $A=1$, $B=0$ : $\overline{AB} = \overline{0} = 1$, tandis que $\overline{A} \cdot \overline{B} = 0 \cdot 1 = 0$. Énoncé correct : $\overline{AB} = \overline{A} + \overline{B}$, et symétriquement $\overline{A+B} = \overline{A} \cdot \overline{B}$.

3) FAUX. Chaque proposition double le nombre de lignes : il y en a $2^{n}$, donc $2^{4} = 16$ pour quatre propositions. Huit lignes correspondent à trois propositions. Énoncé correct : une table à $n$ propositions compte $2^{n}$ lignes, et le nombre de fonctions booléennes de $n$ variables vaut $2^{2^{n}}$.

4) FAUX. Le OU se distribue sur le ET en dédoublant le terme : contre-exemple avec $A=1$, $B=0$, $C=0$ : à gauche $1 + 0 = 1$, à droite $(1+0) \cdot 0 = 0$. Énoncé correct : $A + BC = (A+B)(A+C)$.

5) FAUX. Le OU logique est inclusif : $1+1 = 1$. Il est vrai dès qu'au moins une entrée vaut 1, y compris quand les deux valent 1. Énoncé correct : le connecteur qui vaut 0 lorsque les deux entrées valent 1 est le OU exclusif, noté $A \oplus B$, et il vérifie $A \oplus B = A\overline{B} + \overline{A}B$.

a) Le cahier des charges se traduit terme à terme : $A = BCH + BCD$. Chaque « ET » devient un produit, le « également » devient un OU.

b) $BCH + BCD = BC(H+D)$ par mise en facteur, c'est-à-dire la distributivité du ET sur le OU lue de droite à gauche. Lecture métier : il faut le badge ET le code, plus au moins une des deux justifications d'horaire. Cette forme dit mieux le cahier des charges que la première, parce qu'elle sépare l'identification de l'autorisation temporelle.

c) Avant : chaque produit de trois variables demande 2 portes ET, soit 4 portes ET, plus 1 porte OU : 5 portes. Après : 1 porte OU pour $H+D$, puis 2 portes ET pour $B \cdot C \cdot (H+D)$ : 3 portes. On économise 2 portes sur 5, et surtout un niveau de logique, donc du délai.

d) $A$ vaut 1 quand $B=1$, $C=1$ et $H+D=1$. $B$ et $C$ sont fixés, il reste les 4 combinaisons de $(H,D)$, dont 3 vérifient $H+D=1$ : $(1,0)$, $(0,1)$ et $(1,1)$. Donc 3 combinaisons sur 16 ouvrent la porte. La proportion est un contrôle utile : un système de sécurité qui ouvrirait sur la moitié des combinaisons serait suspect par construction.

e) $\overline{A} = \overline{BC(H+D)} = \overline{BC} + \overline{H+D} = \overline{B} + \overline{C} + \overline{H}\,\overline{D}$, par De Morgan appliqué deux fois. Trois causes de refus, et elles sont bien distinctes : badge invalide, ou code faux, ou bien hors horaire ET sans dérogation. Notez que la troisième cause est un produit, pas une somme : être hors horaire ne suffit pas à refuser si une dérogation existe.

f) Prenons $B=0$, $C=0$, $H=1$, $D=0$ : le vrai système donne $A = 0 \cdot 0 \cdot 1 = 0$, la porte reste fermée. La version du stagiaire donne $A' = 0 + 1 + 0 = 1$ : la porte s'ouvre pour n'importe qui, sans badge ni code, du seul fait qu'on est dans l'horaire ouvré. L'erreur vient de la priorité des opérateurs : il a écrit un OU là où le cahier des charges impose que $BC$ soit un facteur commun obligatoire. En logique de sécurité, une condition nécessaire se met en facteur, jamais en somme.