Fonction booléenne, mintermes et forme canonique

Une fonction booléenne associe 0 ou 1 à chaque combinaison de valeurs de ses variables ; on la donne par une table de vérité ou par une expression. La forme canonique disjonctive est l'expression qu'on lit directement sur la table : la somme des mintermes des lignes où la fonction vaut 1. Ce chapitre montre comment passer d'une table à une expression et inversement, puis d'une situation décrite en français à une expression simplifiée, comme le demandent les sujets.

Fonction booléenne

Une fonction booléenne de n variables associe à chaque n-uplet de 0 et de 1 une valeur 0 ou 1. Elle est entièrement décrite par sa table de vérité, qui a 2ⁿ lignes.

Une même fonction a une seule table, mais une infinité d'expressions : ab + ab̅, a(b + b̅), a + ab et a désignent toutes la même fonction. Simplifier, c'est choisir la plus courte de ces expressions.

Les mintermes

Un minterme (ou monôme canonique) de n variables est un produit qui contient chaque variable exactement une fois, avec ou sans barre. Avec a, b, c : abc, ab̅c, a̅b̅c̅… Il y en a 2ⁿ, un par ligne de la table.

Un minterme vaut 1 sur une seule ligne de la table : celle où chaque variable sans barre vaut 1 et chaque variable barrée vaut 0. Par exemple, ab̅c vaut 1 seulement pour a = 1, b = 0, c = 1.

De la table à l'expression : la forme canonique disjonctive

Une fonction vaut 1 sur certaines lignes. Elle est égale à la somme des mintermes de ces lignes : chaque minterme « allume » sa ligne, et la somme vaut 1 dès qu'une de ces lignes est atteinte. Cette écriture s'appelle la forme canonique disjonctive (ou forme normale disjonctive, ou somme de mintermes). Elle est unique, à l'ordre des termes près.

Exemple. Soit f définie par la table :

f vaut 1 sur les lignes 001, 011 et 111. Sa forme canonique est :

f = a̅b̅c + a̅bc + abc

On simplifie ensuite, par le calcul ou par Karnaugh : a̅b̅c + a̅bc = a̅c, et a̅bc + abc = bc (en dupliquant a̅bc). Donc f = a̅c + bc = c(a̅ + b).

De l'expression à la table

Dans l'autre sens, chaque produit d'une somme de produits fixe certaines variables et laisse les autres libres. Il vaut 1 sur toutes les lignes compatibles.

• abc vaut 1 sur une ligne : 111.
• ab̅ (c est libre) vaut 1 sur deux lignes : 100 et 101.
• c (a et b sont libres) vaut 1 sur quatre lignes : 001, 011, 101, 111.

Exemple. g = ab̅ + bc. Le terme ab̅ donne les lignes 100 et 101 ; le terme bc donne les lignes 011 et 111. g vaut 1 sur 011, 100, 101, 111, et 0 ailleurs.

Pour obtenir la forme canonique à partir d'une expression, on peut aussi compléter chaque produit avec les variables qui lui manquent, en le multipliant par (x + x̅) = 1 :

• ab̅ = ab̅(c + c̅) = ab̅c + ab̅c̅ ;
• bc = (a + a̅)bc = abc + a̅bc ;
• donc g = a̅bc + ab̅c̅ + ab̅c + abc.

La forme canonique conjonctive (complément)

On peut aussi partir des lignes où la fonction vaut 0. Un maxterme est une somme qui contient chaque variable une fois, et qui vaut 0 sur une seule ligne. Pour l'écrire, la règle est inversée : la variable vaut 0 → telle quelle, elle vaut 1 → barrée. La ligne 101 donne le maxterme a̅ + b + c̅.

La fonction est alors le produit des maxtermes des lignes à 0 : c'est la forme canonique conjonctive. Pour la fonction f de l'exemple, qui vaut 0 sur 000, 010, 100, 101 et 110 :

f = (a + b + c)(a + b̅ + c)(a̅ + b + c)(a̅ + b + c̅)(a̅ + b̅ + c)

Cette forme est utile quand la table a beaucoup de 1 et peu de 0. Les sujets du BTS demandent surtout la forme disjonctive ; une autre façon de profiter d'une table pleine de 1 est d'écrire la somme des mintermes du complément f̅ (les lignes à 0), de la simplifier, puis d'appliquer De Morgan.

D'une situation à une expression

C'est la compétence que le programme formule ainsi : « passer d'une situation donnée à une expression booléenne correspondante et inversement ». La méthode :

1. Définir les variables : une variable par condition élémentaire, avec sa signification exacte (« a = 1 si… »).
2. Écrire l'expression directement à partir du texte, ou remplir la table ligne par ligne si la règle s'exprime mieux cas par cas.
3. Simplifier, par le calcul ou par Karnaugh.
4. Traduire le résultat en français, en une phrase simple : c'est souvent la dernière question, et elle montre que tu as compris.

Exemple. Un comité de trois personnes valide les projets informatiques : la directrice (a), le responsable financier (b) et la responsable technique (c). Chaque variable vaut 1 si la personne vote pour. Un projet est validé (V = 1) s'il obtient au moins deux voix, mais la directrice a un droit de veto : si elle vote contre, le projet est refusé.

On remplit la table cas par cas :

Forme canonique : V = ab̅c + abc̅ + abc.

Simplification, en dupliquant abc : (ab̅c + abc) + (abc̅ + abc) = ac + ab. Donc V = ab + ac = a(b + c).

En français : un projet est validé si la directrice vote pour et qu'au moins un des deux autres membres vote pour.

Exercices

Exercice 1 sur 5 De la table à l'expression Réussi À revoir

Une fonction h de trois variables vaut 1 exactement sur les lignes 010, 011, 110 et 111.

1. Écris h sous forme canonique disjonctive.
2. Simplifie h.

Voir la réponseMasquer la réponse de l'exercice 1

1. h = a̅bc̅ + a̅bc + abc̅ + abc.
2. h = a̅b(c̅ + c) + ab(c̅ + c) = a̅b + ab = b(a̅ + a) = b. Les quatre lignes sont exactement celles où b = 1.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 2 sur 5 De l'expression à la table Réussi À revoir

Dresse la table de vérité de k = a̅ + bc̅ sans calculer colonne par colonne, en raisonnant sur les termes. Écris ensuite k sous forme canonique disjonctive.

Voir la réponseMasquer la réponse de l'exercice 2

a̅ vaut 1 sur les quatre lignes où a = 0 : 000, 001, 010, 011. bc̅ vaut 1 sur 010 et 110. k vaut donc 1 sur 000, 001, 010, 011 et 110.

a	b	c	k
0	0	0	1
0	0	1	1
0	1	0	1
0	1	1	1
1	0	0	0
1	0	1	0
1	1	0	1
1	1	1	0

Forme canonique : k = a̅b̅c̅ + a̅b̅c + a̅bc̅ + a̅bc + abc̅.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 3 sur 5 Une prime d'équipe Réussi À revoir

Une entreprise de services numériques verse une prime à un technicien selon trois critères : a = 1 s'il a résolu plus de 50 tickets dans le mois ; b = 1 si la satisfaction des utilisateurs dépasse 90 % ; c = 1 s'il a assuré au moins une astreinte. La prime est versée dans les cas suivants, et seulement dans ces cas :

• plus de 50 tickets et satisfaction au-dessus de 90 %, avec ou sans astreinte ;

• satisfaction au-dessus de 90 %, au moins une astreinte, mais au plus 50 tickets ;

• plus de 50 tickets et au moins une astreinte, mais satisfaction d'au plus 90 %.

1. Écris l'expression P de la prime, puis sa forme canonique.
2. Simplifie P.
3. Traduis le résultat par une phrase.

Voir la réponseMasquer la réponse de l'exercice 3

1. P = ab + a̅bc + ab̅c. En complétant ab : ab = abc + abc̅. Forme canonique : P = abc + abc̅ + a̅bc + ab̅c.
2. On duplique abc pour l'associer à chacun des trois autres termes : (abc + abc̅) + (abc + a̅bc) + (abc + ab̅c) = ab + bc + ac. P = ab + ac + bc.
3. La prime est versée quand le technicien remplit au moins deux des trois critères.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 4 sur 5 De l'expression à la situation Réussi À revoir

Dans une salle serveur, la ventilation de secours se déclenche (D = 1) selon la formule D = t + p̅c, où t = 1 si la température dépasse 30 °C, p = 1 si la climatisation principale fonctionne, c = 1 si la salle est occupée par un technicien.

1. Traduis D par une phrase.
2. La ventilation se déclenche-t-elle quand la climatisation est en panne, la salle vide et la température à 25 °C ?
3. Écris le complément D̅ sous forme de somme de produits et traduis-le.

Voir la réponseMasquer la réponse de l'exercice 4

1. La ventilation de secours se déclenche si la température dépasse 30 °C, ou si la climatisation principale est en panne alors qu'un technicien est dans la salle.
2. t = 0, p = 0, c = 0 : D = 0 + 1 · 0 = 0. Elle ne se déclenche pas.
3. D̅ = non(t + p̅c) = t̅ · non(p̅c) = t̅(p + c̅) = t̅p + t̅c̅. La ventilation reste arrêtée si la température ne dépasse pas 30 °C et que la climatisation fonctionne, ou si la température ne dépasse pas 30 °C et que la salle est vide.

Tu avais trouvé ?

Oui, j'avais bonPas encore

Exercice 5 sur 5 Forme conjonctive Réussi À revoir

Une fonction m de deux variables vaut 0 seulement sur la ligne a = 1, b = 1. Écris m sous forme canonique conjonctive. Reconnais-tu cette fonction ?

Voir la réponseMasquer la réponse de l'exercice 5

m n'a qu'une ligne à 0 : sa forme conjonctive est un seul maxterme, celui de la ligne 11, où les deux variables valent 1 et sont donc barrées. m = a̅ + b̅. Par De Morgan, m = non(ab) : c'est la fonction NAND (non-et), qui vaut 0 seulement quand les deux entrées valent 1.

Tu avais trouvé ?

Oui, j'avais bonPas encore