La logique combinatoire
La logique combinatoire est une branche essentielle de l'électronique numérique qui repose sur des circuits dont la sortie dépend uniquement des valeurs actuelles des entrées, sans tenir compte des valeurs précédentes. Ces circuits, sans mémoire, sont entièrement déterminés par les entrées à un instant donné et peuvent être modélisés par des fonctions logiques, des tables de vérité et des tables de Karnaugh. Contrairement à la logique séquentielle, où la sortie dépend aussi de l'état précédent, la logique combinatoire se concentre sur l'instantanéité des entrées/sorties. L'algèbre de Boole, fondée par George Boole en 1854, formalise des opérations logiques pour résoudre des raisonnements à deux valeurs (vrai et faux), et est cruciale pour la conception des circuits numériques et les systèmes électroniques modernes.
Le schéma ci-dessous résume la modélisation de ce système numérique :
Historique de l'algèbre de Boole
L'algèbre de Boole introduit en effet une nouvelle méthode de raisonnement logique proposée par ce logicien et publiée dans son ouvrage intitulé "The Laws of Thought". Ce modèle logique repose sur le principe des variables booléennes qui ne prennent que deux valeurs : 0 (faux) et 1 (vrai) ; appelées aussi variables binaires, et ne fournit que deux réponses possibles : 0 (faux) et 1 (vrai). Il s'appuie également sur quelques opérateurs logiques permettant de les manipuler.
Définitions de base
Pour commencer avec la logique combinatoire, il est recommandé de connaître les définitions suivantes :
- L'algèbre de Boole : il s'agit d'un système algébrique dans lequel les éléments sont des variables à deux états ; soit un "0" logique ou un "1" logique, et les opérations logiques de base sont NON, ET, et OU. Ces opérations sont utilisées pour manipuler des fonctions logiques et créer des circuits combinatoires.
- Une variable logique : une variable est une quantité numérique pouvant prendre les valeurs 0 ou 1, ce qui représente tout simplement l'une des deux formes possibles pour un interrupteur électrique ; soit fermé, soit ouvert. En électronique numérique, les niveaux logiques ; 0 et 1, sont codés par des niveaux de tension continue de 5V (1.5V ou 12V ou autre valeur), ou de 0V. Cette quantité est représentée par un identificateur, comme une lettre ou un nom.
- Une fonction logique de $n$ variables binaires, appelée aussi équation logique, est une expression dans laquelle plusieurs variables binaires sont reliées par des opérateurs logiques (NON, ET, OU). La sortie de la fonction dépend des valeurs de ces variables à un moment donné.
- Une table de vérité : c'est la représentation de l’évolution du comportement de notre système combinatoire en fonction des variations à ses entrées. Ce tableau énumère les différentes combinaisons possibles à l'entrée de notre système et la valeur de sortie correspondante. L'image ci-dessous vous détaille les différents éléments constituant une table de vérité :
Les opérateurs logiques fondamentaux
Les opérateurs logiques sont des outils de base qui permettent de manipuler les variables binaires. Les plus utilisés sont :
- Opérateur "NON" (NOT) : la valeur de la sortie est l'inverse de la valeur à l'entrée de la fonction : si la variable est à 0, la sortie sera 1, et vice versa. La table de vérité se résume comme suit:
| E = Entrée | S = Sortie |
| 0 | 1 |
| 1 | 0 |
- Opérateur "ET" (AND) : la sortie est à 1 si toutes les entrées de la fonction sont à 1, sinon la sortie reste à 0. La table de vérité se résume comme suit:
| A | B | S = A.B (sortie) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Dans la pratique, une fonction ET correspond à un circuit composé d'une lampe et de plusieurs interrupteurs montés en série. Elle s'allume uniquement lorsque tous les interrupteurs sont fermés simultanément.
- Opérateur "OU" (OR) : la sortie est à 1 si au moins une des variables est à 1. La table de vérité se résume comme suit :
| A | B | S = A+B (sortie) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Dans la pratique, une fonction OU correspond à un circuit composé d'une lampe et de plusieurs interrupteurs montés en dérivation (dit aussi en parallèle). Ce qui correspond à une lampe qui s'allume uniquement si un interrupteur est fermé.
Propriétés et opérations élémentaires
Dans la logique combinatoire, les opérateurs logiques ET et OU possèdent certaines propriétés fondamentales qui nous facilitent la manipulation et la simplification d'une fonction logique telles que :
La commutativité :
- ET : $A⋅B=B⋅A$
- OU : $A+B=B+A$
Cela signifie que l'ordre des entrées n'affecte pas la sortie de la fonction.
L'associativité :
- ET : $(A⋅B)⋅C=A⋅(B⋅C)$
- OU : $(A+B)+C=A+(B+C)$
Cela signifie que le regroupement des entrées n'affecte pas la sortie de la fonction.
La distributivité :
- ET par rapport à OU : $A⋅(B+C)=(A⋅B)+(A⋅C)$
- OU par rapport à ET : $A+(B⋅C)=(A+B)⋅(A+C)$
La complémentarité :
- ET : $A \cdot \bar{A} = 0$
- OU : $A + \bar{A} = 1$
L'idempotence :
L'idempotence signifie qu'une variable combinée à elle-même par l'opérateur ET ou OU conserve sa valeur initiale tel que :
- ET : $A \cdot A = A$
- OU : $A+A = A$
L'élément neutre :
Tout élément ou mot binaire est neutre devant la fonction ET et la fonction OU tel que :
- ET : $A \cdot 1=A$
- OU : $A+0=A$
L'élément absorbant :
L'élément absorbant est un élément qui force la valeur de la sortie de la fonction logique à 0 ou 1 suivant la fonction logique appliquée ET ou OU tel que :
- ET : $A \cdot 0=0$
- OU : $A+1=1$
L'absorption :
En logique binaire, l’absorption est une loi qui nous permet de réduire une expression si une variable A est additionnée à un produit où A est présente. Cette formule reste valable pour la fonction OU également telle que :
- ET : $A \cdot (A +B)=A$, soit une absorption sous forme de produit.
- OU : $A+ A \cdot B =A$, soit une absorption sous forme de somme.
L'involution :
Une involution est une fonction binaire qui, si nous l'appliquons deux fois, nous retrouvons le mot initial telle que :
- $\overline{\overline{A}} = A$ : le complément du complément de A est égal à A
- $\overline{\overline{\overline{A}}} = \overline{A}$ : le complément du complément du complément de A est égal au complément de A
Loi d'adjacence :
En algèbre de Boole, deux termes sont dits adjacents lorsqu'ils sont identiques à l'exception d'une seule variable. Cette loi permet d'éliminer la variable qui change d'état telle que :
- Produit des sommes (ET) : $(A+B) \cdot (A+\overline{B}) = A$ : on applique la distributivité du OU sur le ET, puis $B \cdot \overline{B} = 0$.
- Sommes des produits (OU) : $A \cdot B + A \cdot \overline{B} = A$ : on met $A$ en facteur commun, puis $B + \overline{B} = 1$.
Autres opérateurs logiques
- Opérateur "NON ET" (NAND) : la sortie est à 0 seulement si toutes les entrées sont à 1. Il s'agit de l'inverse de l'opérateur ET. La table de vérité se résume comme suit :
| A | B | S = A NAND B (sortie) |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
- Opérateur "NON OU" (NOR) : la sortie est à 1 seulement si toutes les entrées sont à 0. Il s'agit de l'inverse de l'opérateur OU. La table de vérité se résume comme suit :
| A | B | S = A NOR B (sortie) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
- Opérateur "OU Exclusif" (XOR) : la sortie est à 1 si une seule des entrées est égale à 1 (mais pas les deux). La table de vérité se résume comme suit :
| A | B | S = A XOR B (sortie) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
- Opérateur "NON OU Exclusif" (XNOR) : la sortie est à 1 si les entrées sont identiques (c'est-à-dire soit les deux sont à 0, soit les deux sont à 1). La table de vérité se résume comme suit :
| A | B | S = A XNOR B (sortie) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Lois de De Morgan
Les lois de De Morgan sont des règles fondamentales en logique booléenne qui permettent de simplifier les expressions logiques en modifiant l'opérateur logique. Elles concernent les opérateurs logiques NON, ET et OU, et sont particulièrement utiles pour simplifier les formules logiques et les expressions complexes dans l'algèbre de Boole.
Ainsi, les deux lois proposées par De Morgan sont les suivantes :
- La première stipule que la négation de la disjonction de deux variables est équivalente à la conjonction des négations de ces variables :
$$¬(A∨B)=¬A∧¬B$$
Autrement dit, la négation d'une opération OU entre A et B est égale à la combinaison de deux négations de A et B reliées par une opération ET. Si nous transposons cela dans notre écriture binaire simple, nous pouvons écrire :
$$\overline{(A + B)} = \overline{A} \cdot \overline{B}$$
- La deuxième stipule que la négation de la conjonction de deux variables est équivalente à la disjonction des négations de ces variables :
$$¬(A∧B)=¬A∨¬B$$
Cela signifie que la négation d'une opération ET entre A et B est égale à la disjonction réalisée par l'opérateur OU des deux négations de A et B. Si nous transposons cela dans notre écriture binaire simple, nous pouvons écrire :
$$\overline{(A \cdot B)} = \overline{A} + \overline{B}$$
Ces lois sont importantes car elles permettent de transformer une expression logique dans un format qui peut être plus facile à manipuler ou à implémenter dans des circuits logiques. Elles sont souvent utilisées dans la conception de circuits électroniques pour minimiser le nombre de portes logiques nécessaires ou pour simplifier les équations dans des systèmes plus complexes.
Dans le contexte de l'algèbre de Boole, ces lois permettent de manipuler des fonctions logiques de plusieurs variables binaires, qui sont souvent utilisées pour représenter des circuits combinatoires. Par exemple, dans une situation où une fonction logique implique des opérateurs ET et OU, les lois de De Morgan permettent de réécrire l'expression de manière à réduire la complexité ou à la rendre plus compatible avec une implémentation pratique, comme dans les circuits à portes NAND ou NOR. En utilisant ces lois, les concepteurs peuvent simplifier des expressions booléennes complexes en d'autres formes équivalentes qui sont plus faciles à traiter, que ce soit pour les calculs théoriques ou pour la conception matérielle de circuits.
Présentation d'une fonction logique
Pour présenter une fonction logique, nous aurons besoin de définir au minimum :
- Une ou plusieurs variables
- Le résultat attendu, ce qui indique que nous définissons une table de vérité puis une équation logique de la fonction.
Variable logique
Une variable logique est tout simplement un vecteur d'information numérique. Comme expliqué ci-dessus, une variable est une information électrique ne pouvant prendre que l'une des deux valeurs suivantes ; soit 0 (tension basse, ex. 0 V), soit 1 (tension haute, ex. 5 V). Ce qui représente aussi les deux formes d'un interrupteur ; soit ouvert, soit fermé.
La table de vérité
Une table de vérité est un outil qui regroupe toutes les combinaisons d'états logiques possibles des entrées exprimées en 0 et 1 ainsi que l'état correspondant à la sortie. Elle permet de définir la valeur à la sortie de notre fonction logique en fonction des différentes valeurs à son entrée.
Par exemple, pour une fonction logique à deux variables, la table de vérité ressemble à ceci :
| A | B | S = Sortie |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
Ainsi, cette table décrit le comportement d'une fonction logique (par exemple, cette table présente le tableau de vérité d'une fonction logique OU) en fonction des différentes valeurs reçues à son entrée.
L'équation logique
Une équation logique est une expression qui relie la variable de sortie en fonction d'une ou plusieurs variables d'entrées à l'aide d'opérations logiques de sommes (soit la fonction OU logique) et de produits logiques (soit la fonction ET logique).
Par exemple, l'équation logique de la fonction ET est la suivante : $S = A \cdot B$.
Pour la fonction logique OU, son équation est la suivante : $S = A + B$.
Le logigramme
Le logigramme, appelé aussi le diagramme logique, est une représentation symbolique que nous pouvons aussi appeler schéma logique qui regroupe les fonctions de base requises interconnectées entre elles pour réaliser la fonction logique demandée. L'image ci-dessous représente le logigramme de la fonction logique : $S=\overline{A} \enspace XOR \enspace B$
Le chronogramme
Le chronogramme est une représentation graphique qui visualise l'évolution de la sortie de notre fonction logique en fonction des différentes combinaisons possibles des entrées de notre système combinatoire. Dans certains cas, principalement pour les systèmes de type logique séquentielle, ce chronogramme prend en considération un ou plusieurs états précédents. L'image ci-dessous représente le chronogramme du logigramme proposé ci-dessous (dont la fonction logique est $S = \overline{A} \enspace XOR \enspace B$ )
Simplification des fonctions logiques
Comme nous l'avons indiqué précédemment, tout système combinatoire dispose d'une fonction logique, simple ou complexe. De ce fait, il est recommandé de simplifier l'équation logique le plus possible afin de simplifier son implémentation électrique. Pour cela, il est possible de simplifier toute équation logique par les deux méthodes de simplification suivantes :
- Application des formules d'algèbre : cette technique utilise les principes fondamentaux de l'algèbre de Boole, les règles des opérateurs logiques, des théorèmes de De Morgan, etc.
- Application graphique de la table de Karnaugh : cette méthode plus simple utilise la table de Karnaugh pour simplifier des équations et des fonctions logiques.
Exercices d'application avec correction
 |
Une fois que vous avez bien assimilé cette première partie de ce cours, nous pouvons avancer ensemble pour vous expliquer comment simplifier une équation booléenne en utilisant la table de Karnaugh.
La Table de Karnaugh
La table de Karnaugh, appelée aussi tableau de Karnaugh, d'une fonction logique est une représentation de sa table de vérité sous forme d'une table contractée à 2 dimensions. Soit une écriture de la table de vérité sous forme d'une matrice à 2 dimensions : des lignes et des colonnes. Nous notons que cette représentation est déconseillée pour les fonctions logiques ayant plus de 6 variables. Au-delà de 6 variables, la simplification par la table de Karnaugh demande 128, 256, ... cases; ce qui devient compliqué à traiter manuellement.
Pour transformer une table de vérité en une table de Karnaugh, nous devons suivre la procédure ci-dessous à la lettre (simple et non pas compliquée) :
- Chaque ligne de la table de vérité correspond à une case de la table de Karnaugh.
- On dit que deux cases sont adjacentes si et seulement si une seule variable à l'entrée de notre système logique diffère.
- Pour passer d'une case à une autre dans la table de Karnaugh, une seule variable à l'entrée de notre système logique ne peut changer à la fois (ce passage respecte le code de Gray).
Pour mieux comprendre cela, vous trouverez ci-dessous les différents formats d'une table de Karnaugh pour 2 à 4 variables :
|
|
|
|
| Table de Karnaugh à 2 variables | Table de Karnaugh à 3 variables | Table de Karnaugh à 4 variables |
Afin de mieux vous expliquer comment utiliser une table de Karnaugh pour simplifier une équation logique, prenons comme exemple la table de vérité ci-dessous (la même que nous avons présentée au début de notre cours) :
À partir de cette table de vérité, remplissons maintenant la table de Karnaugh et regroupons les 1 en appliquant les règles citées ci-dessus :
Ainsi, nous pouvons écrire l'équation logique simplifiée de notre table de vérité telle que : $S = B \cdot \overline{C} +\overline{A} \cdot C$.
 |