Exercice 8 / 8Moyen
Du circuit logique à l'expression
À toi
Un circuit a trois entrées a, b, c et une sortie S. Il est câblé ainsi :
- une porte ET reçoit a et b ;
- une porte NON reçoit c ;
- une porte OU reçoit les sorties de ces deux portes ;
- une dernière porte NON inverse la sortie de la porte OU et donne S.
- Quelle expression donne S ?
- Quelle est sa forme simplifiée en somme de produits ?
- Que vaut S pour a = 1, b = 0 et c = 1 ?
Logique et algèbre de Boole
Les connecteurs et leurs notations
| Connecteur | Logique | Algèbre de Boole | Code (C#, Java, JavaScript) |
|---|---|---|---|
| non | ¬P | a̅ | !a |
| et | P ∧ Q | ab ou a · b | a && b |
| ou (inclusif) | P ∨ Q | a + b | a || b |
| ou exclusif | P ⊕ Q | a ⊕ b | a ^ b |
Le et ne vaut vrai (1) que si les deux le sont ; le ou ne vaut faux (0) que si les deux le sont ; le ou exclusif vaut vrai quand exactement un des deux l'est. L'implication P ⇒ Q n'est fausse que dans un cas : P vraie et Q fausse. En algèbre de Boole, + veut dire « ou » : 1 + 1 = 1.
Construire une table de vérité
Avec n variables, il y a 2ⁿ lignes, rangées comme un comptage en binaire (000, 001, 010… 111). On ajoute une colonne par sous-expression, de l'intérieur vers l'extérieur. Exemple, a ⊕ b = a̅b + ab̅ :
| a | b | a̅b | ab̅ | a̅b + ab̅ |
|---|---|---|---|---|
| 0 | 0 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 | 1 |
| 1 | 1 | 0 | 0 | 0 |
Les règles de calcul
| Règle | Forme « produit » | Forme « somme » |
|---|---|---|
| Complémentarité | aa̅ = 0 | a + a̅ = 1 |
| Neutre et absorbant | a · 1 = a ; a · 0 = 0 | a + 0 = a ; a + 1 = 1 |
| Idempotence | aa = a | a + a = a |
| Absorption | a(a + b) = a | a + ab = a |
| Absorption du complément | a(a̅ + b) = ab | a + a̅b = a + b |
| Distributivité | a(b + c) = ab + ac | a + bc = (a + b)(a + c) |
La mise en facteur donne la règle clé des simplifications : xy + xy̅ = x(y + y̅) = x.
Les lois de De Morgan
non(a + b) = a̅ b̅ et non(ab) = a̅ + b̅ : quand la barre se casse, le signe change. On les applique de l'extérieur vers l'intérieur : non(ab̅ + c) = non(ab̅) · c̅ = (a̅ + b)c̅. En code, !(x && y) équivaut à !x || !y, et en SQL NOT (p OR q) à NOT p AND NOT q.
De la table à l'expression
Un minterme est un produit des trois variables, chacune barrée si elle vaut 0 sur la ligne : la ligne a = 1, b = 0, c = 1 donne ab̅c. La forme canonique d'une fonction est la somme des mintermes des lignes où elle vaut 1.
Le tableau de Karnaugh à trois variables
a en ligne, bc en colonne dans l'ordre de Gray 00, 01, 11, 10 : deux cases voisines ne diffèrent que d'un bit, et les colonnes 00 et 10 sont voisines elles aussi (le tableau se referme en cylindre).
- On regroupe des 1 voisins par rectangles de 1, 2, 4 ou 8 cases, les plus grands possible, le moins de groupes possible ; une case peut servir deux fois.
- Un groupe donne le produit des variables qui gardent la même valeur dans toutes ses cases (barrée si elle vaut 0). Les autres disparaissent.
| a \ bc | 00 | 01 | 11 | 10 |
|---|---|---|---|---|
| 0 | 1 | 1 | 0 | 0 |
| 1 | 1 | 1 | 0 | 0 |
Ici, un seul groupe de 4 (colonnes 00 et 01) : a et c changent, b vaut 0 partout. La fonction vaut b̅.
Du circuit à l'expression
On écrit la sortie de chaque porte, de l'entrée vers la sortie : ET donne un produit, OU une somme, NON une barre. Une porte OU sur a et b suivie d'une porte NON donne non(a + b) = a̅b̅.
Tu es bloqué ?
Ouvre les indices un par un, le corrigé en dernier.
Indice 1
Écris la sortie de chaque porte, de l'entrée vers la sortie : la porte ET donne ab, la première porte NON donne c̅.
Indice 2
La porte NON finale met une barre sur toute la sortie du OU.
Indice 3
De Morgan : non(x + y) = x̅ y̅, puis non(ab) = a̅ + b̅.
Voir le corrigé
Connecte-toi pour voir le corrigé
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données
Pour revoir la notion : chapitre 6 du cours Algèbre de Boole, Algèbre de Boole : définition, règles et propriétés.
Tes réponses
Connecte-toi pour faire cet exercice
C'est gratuit, avec ton compte Google : un clic, et tu reviens ici. Ta progression te suit ensuite sur tous tes appareils.
Le site garde ton nom et ton email, rien d'autre. Tes données