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 et de la sortie. L'algèbre de Boole, fondée par Georges 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

Cette 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 des 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'un des deux formes possibles pour un interrupteur électrique ; soit ouvert, soit  fermé. Il peut s'agir d'une information électrique sous forme de tension continue de 5 V (1,5 V ou 12 V ou autre), ou de 0 V (ou d'une forme négative). 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é : 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 à sa sortie qui correspond. 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:

• Opérateur "ET" (AND): la sortie est à 1 si toutes les entrées de la fonctions sont à 1, sinon la sortie reste à 0. La table de vérité se résume comme suit:

Dans la pratique, une fonction ET pourrait correspondre à un circuit où une lampe qui 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 :

Dans la pratique, une fonction OU pourrait correspondre à une lampe qui s'allume si au moins 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é :

• OU par rapport à ET : \( A+(B⋅C)=(A+B)⋅(A+C) \)
• ET par rapport à OU : \( A⋅(B+C)=(A⋅B)+(A⋅C) \)

La complémentarité :

• OU : \( A \cdot \bar{A} = 0 \)
• ET : \( A + \bar{A} = 1 \)

L'idempotence :

L'idempotence d'un mot binaire se définit par la production du même résultat lorsque le même variable est soumis à la même fonction plusieurs fois :

• OU : \( A \cdot A = A \)
• ET : \( 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⋅1=A \)
• OU : \( A+0=A \)

L'élément absorbant :

L'élement absorbant est un élément qui force la valeur de la sortie de la fonction logique à sa valeur devant une fonction ET ou une fonction OU tel que :

• ET : \( A⋅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 aditionnée à un produit où A est présente. Cette formule reste valable pour la fonction OU également telle que :

• ET : \( A+(A \cdot B)=A \)
• OU : \( A \cdot (A +B)=A \)

L'involution :

Une involution est une fonction binaire qui si nous l'appliquons deux fois, nous retrouvons le mot initiale telle que :

• \(  \overline{\overline{A}} = A \) : le complément du complément de A est égale à A
• \(  \overline{\overline{\overline{A}}} = \overline{A} \) : le complément du complément du complément de A est égale au complément de A

L'inclusion :

Ce théorème stipule la formule que :

• \( A \cdot B + A \cdot \overline{B} = A \)
• \( (A+B) \cdot (A+\overline{B}) = A \)

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 :

• 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 :

• 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 :

• 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 :

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. Ceci concerne les opérations 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 \cdot B)} = \overline{A} + \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 combinaison de deux négations de A et B reliées par une opération OU. Si nous transposons cela dans notre écriture binaire simple, nous pouvons écrire :

\[ \overline{(A + B)} = \overline{A} \cdot \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 à travailler, 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-dessous, une variable est une information électrique ne pouvant prendre que l'une des deux valeurs suivantes ; soit 0 pour l'absence du passage de courant électrique, soit 1 pour son passage. 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 :

Ainsi, cette table décrit le comportement de la fonction logique (par exemple, cette table présente le tableau de vérité d'une fonction logique ET) en fonction des différentes valeurs à 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 \).

Et pour la sortie Q d'une bascule RS est la suivante : \( Q_{n+1} =S+(\overline{R} \cdot Q_{n} ) \)

Le logigramme

Le logigramme, appelé aussi 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 tient en considération un ou plusieurs état précédent. L'image ci-dessous représente le chronogramme du logigramme proposé ci-dessous (dont sa 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 maximum possible afin de simplifier son implémentation électrique. Pour cela, il est possible de simplifier toute équation logique par ces deux méthodes de simplification par :

• 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 Morgan, etc.
• Application graphique de la table de Karnaugh : cette méthode est plus simple utilise la table de Karnaugh pour simplifier des équations et des fonctions logiques.

Dans la suite de notre cours, nous allons vous expliquer comment simplifier une équation booléenne par application de 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 tableau de vérité sous forme d'une table contractée à 2 dimensions. Soit une écriture de la table de vérité sous forme d'un vecteur à 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-delas de 6 variables, la simplification par la table de Karnaugh demande 128 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 prescrite ci-dessous à la lettre (simple et qui n'est 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 dites 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 change à la fois.

Pour mieux comprendre cela, vous trouverez ci-dessous les différents formats d'une table de Karnaugh pour 2 à 4 variables :

Pour encore 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) :

A 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 \)

Nous mettons également à votre disposition un calculateur tableau de Karnaugh qui vous permet de retrouver vos équations logiques simplifiées à partir de vos tables de vérités. Vous pouvez également vous exercer à ce type de simplification en vous entraînant avec la série d’exercices suivante : Exercices - La table de Karnaugh