Exemple 2.4.3. Un premier circuit combiné: dynamique.
On considère le circuit de la figure 2.4.4. Si \(X=1,Y=0,Z=1\text{,}\) quelle est la sortie du circuit?
Section 2.4 Circuits logiques
Pour la première fois, on évoque spécifiquement le fonctionnement d’un ordinateur. Les composantes d’un ordinateur sont presque toutes composées de petits circuits électroniques qui sont fait pour accepter deux intensité de courant électrique. Un circuit qui reçoit le niveau élevé de courant sera représenté par un \(1\) alors qu’un circuit qui reçoit un faible niveau sera représenté par un \(0\text{.}\) Cette dualité n’est pas sans rappeler les sections précédentes où les propositions étaient vraie ou fausse.
Un ordinateur combine l’information de tous ses circuits pour effectuer ses tâches. Pour cela, il combine ces informations à l’aide de ce qu’on appelle des portes, qui sont analogues aux connecteurs logiques. Les éléments de la présente section sont d’une certaine façon une manière graphique de visualiser les notions de la section 2.1.
Dans cette section, on définit les portes logiques élémentaires, les circuits logiques et leur construction,
Sous-section 2.4.1 Portes logiques
Une porte logique est un dispositif agissant sur un certain nombre d’entrée et produisant à partir de ceux-ci une sortie. Typiquement dans un ordinateur, le niveau de tension de composantes est fourni en entrée afin de produire un résultat ou une information. On peut aussi voir les entrées comme des Vrai ou Faux, des Ouvert ou Fermé ou des \(1\) ou \(0\text{.}\) Une partie d’un circuit peut être illustré comme sur la figure 2.4.1. À gauche, on retrouve les entrées (il peut y en avoir une ou plusieurs) et à droite la sortie (encore une fois, une ou plusieurs). Au centre, on retrouve une porte, une espèce de boite noire qui accomplit des opérations logiques pour produire la sortie.
On définit maintenant les trois portes principales d’un circuit logique. Elles les équivalents des opérateurs logiques \(\neg,\wedge,\vee\text{.}\) Les portes NON, ET et OU sont illustrées ci-dessous.
En plus des portes élémentaires, on peut aussi définir des portes pour des opérations comme le ou exclusif. On peut même définir ses propres opérations logiques et leur créer une porte. Concrètement, la porte NON va changer le signal de l’entrée pour l’inverser. Ainsi si une composante avait une tension élevée, envoyer son signal dans une porte NON convertira la tension en basse. Une porte ET regarde les deux entrées et retourne un signal à tension élevée si les deux signaux d’entrée étaient aussi à tension élevée. Finalement la porte OU envoie un signal à tension élevée dès que l’une de ses entrée l’était. Pour se coller à la tradition informatique, on parlera désormais en termes de \(1\) et de \(0\) pour parler de l’entrée et de la sortie d’un circuit.
Évidemment, ces portes à elles seules ne sont pas très intéressante, mais c’est en les combinant qu’on peut faire des choses complexes et utiles. Il y a toutefois quelques règles à respecter. Sous ces conditions, la sortie d’un circuit sera entièrement déterminée par la valeur de ces entrées au moment de la lecture de celles-ci. On regarde un exemple de circuit plus complexe avant d’établir les règles pour combiner les portes.
Quelles sont donc les règles pour avoir un circuit logique valide? Il y en a quatre. La dernière, si elle n’est pas respectée, peut donner lieu à des circuits appelés séquentiels. On ne considère pas ce type de circuits.
-
On ne combine pas deux fils d’entrée.
-
Une entrée peut se séparer comme l’entrée \(Y\) dans le circuit de la figure 2.4.4 afin d’être utilisée par plus d’une porte.
-
Une sortie peut être utilisée comme entrée.
-
Par contre, aucune sortie ne retourne dans la porte d’où elle provient, que ce soit immédiatement ou éventuellement.
Sous-section 2.4.2 Parallèle avec la logique propositionnelle
On sait que pour chaque possibilité des entrées d’un circuit, on obtiendra une valeur de sortie. Lorsque le nombre de possibilités est raisonnable, on peut faire une table des possibilités. C’est l’équivalent de la table de vérité de la logique propositionnelle. Ci-dessous, la table du circuit de l’exemple 2.4.3. On peut vérifier avec la figure interactive 2.4.5 que les valeurs sont exactes.
| \(X\) | \(Y\) | \(Z\) | Sortie |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 0 |
| 0 | 1 | 1 | 0 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 1 |
| 0 | 0 | 0 | 0 |
S’il est possible d’associer à un circuit logique une table de vérité, il est également possible de lui associer une expression logique. La sortie du circuit de l’exemple 2.4.3 se lisait d’ailleurs \((X\wedge Y)\vee(\neg Y\wedge Z)\text{.}\)
Digression: En passant.
Exemple 2.4.7. D’autres exemples de circuits logiques.
On considère les circuits de la figure ci-dessous. On cherche à déterminer la table de vérité et une expression de logique propositionnelle pour chacun.
Solution 1.
On débute par la table de vérité de ce circuit.
On commence avec la paire d’entrées \(1\)-\(1\text{.}\) La porte OU les combinant retournent \(1\text{.}\) La valeur de \(Y\) est inversée par la porte non et se combine ensuite avec le résultat précédent dans la porte ET. Comme la valeur du Y a été inversée et est maintenant \(0\text{,}\) la porte ET retourne \(0\) comme sortie du circuit.
Pour la paire d’entrée \(1\)-\(0\text{,}\) la porte OU les combinant retournent \(1\text{.}\) La valeur de \(Y\) est inversée par la porte non et se combine ensuite avec le résultat précédent dans la porte ET. Comme la valeur du Y a été inversée et est maintenant \(1\text{,}\) la porte ET retourne \(1\) comme sortie du circuit.
Pour la paire d’entrée \(0\)-\(1\text{,}\) la porte OU les combinant retournent \(1\text{.}\) La valeur de \(Y\) est inversée par la porte non et se combine ensuite avec le résultat précédent dans la porte ET. Comme la valeur du Y a été inversée et est maintenant \(0\text{,}\) la porte ET retourne \(0\) comme sortie du circuit.
Pour la paire d’entrée \(0\)-\(0\text{,}\) la porte OU les combinant retournent \(1\text{.}\) La valeur de \(Y\) est inversée par la porte non et se combine ensuite avec le résultat précédent dans la porte ET. La valeur du Y a été inversée et est maintenant \(1\text{,}\) mais la porte OU a retourné \(0\text{.}\) La porte ET finale retourne \(0\) comme sortie du circuit.
Le résumé de ces calculs se trouve dans la table ci-dessous.
| \(X\) | \(Y\) | \(X\vee Y\) | \((X\vee Y)\wedge \neg Y\) |
| 1 | 1 | 1 | 0 |
| 1 | 0 | 1 | 1 |
| 0 | 1 | 1 | 0 |
| 0 | 0 | 0 | 0 |
Pour ce qui est de l’expression logique, en suivant le raisonnement des calculs précédents, on arrive à \((X\vee Y)\wedge (\neg Y)\text{.}\)
Solution 2.
Souvent, il est plus simple de déterminer d’abord l’expression logique et à partir de celle-ci, écrire la table de vérité. C’est l’approche préconisée ici.
On peut procéder comme dans le circuit à deux entrées. On peut aussi procéder de la sortie vers les entrées. La porte finale est une porte ET. On sait donc qu’on aura une conjonction de deux propositions. La première partie de la conjonction correspond à la sortie de la porte OU, qui combine le \(X\) et le \(Y\text{.}\) La seconde partie de la porte finale est la sortie d’une inversion. On aura donc une négation. Ce qui est inversé, c’est le résultat de la porte ET, qui combine le \(Y\) et le \(Z\text{.}\) En combinant ces informations, on obtient \((X\vee Y)\wedge \neg(Y\wedge Z)\text{.}\)
On peut ensuite trouver la table de vérité ci-dessous.
| \(X\) | \(Y\) | \(Z\) | \(X\vee Y\) | \(\neg(Y\wedge Z)\) | \((X\vee Y)\wedge \neg(Y\wedge Z)\) |
| 1 | 1 | 1 | 1 | 0 | 0 |
| 1 | 1 | 0 | 1 | 1 | 1 |
| 1 | 0 | 1 | 1 | 1 | 1 |
| 1 | 0 | 0 | 1 | 1 | 1 |
| 0 | 1 | 1 | 1 | 0 | 0 |
| 0 | 1 | 0 | 1 | 1 | 1 |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 | 1 | 0 |
Si on peut trouver une expression logique et une table de vérité à partir d’un circuit logique, on peut probablement trouver une circuit logique à partir d’une expression ou d’une table de vérité. Pour cette dernière option, la forme normale disjonctive sera particulièrement utile.
Exemple 2.4.11. Des circuits à partir d’une expression logique ou d’une table de vérité.
On considère l’expression logique \((X\vee \neg Z)\wedge (\neg Y\vee Z) \) et la table de vérité suivante.
| \(X\) | \(Y\) | \(Z\) | \(f(X,Y,Z)\) |
| 1 | 1 | 1 | 1 |
| 1 | 1 | 0 | 1 |
| 1 | 0 | 1 | 1 |
| 1 | 0 | 0 | 1 |
| 0 | 1 | 1 | 1 |
| 0 | 1 | 0 | 0 |
| 0 | 0 | 1 | 0 |
| 0 | 0 | 0 | 0 |
On veut dessiner des circuits logiques équivalents à ceux-ci.
Solution 1.
On débute avec l’expression logique. On voit que la sortie sera obtenue après une porte ET qui combine les deux paires de parenthèses. Dans la première paire, le \(X\) est combiné à la négation de \(Z\) par une porte OU et dans la seconde, c’est la négation de \(Y\) qui est combinée à \(Z\text{,}\) aussi par une porte OU.
Comme \(Z\) apparait dans les deux paires de parenthèses, il faudra séparer l’entrée en deux. Une solution possible est donner ci-dessous.
Solution 2.
Le plus simple pour construire le circuit associé à une table de vérité est de construire la forme normale disjonctive de l’expression. Comme toutes les sorties tels que \(X\) est \(1\) donnent \(1\text{,}\)en combinant \(X\) à la cinquième ligne, on obtient \(X\vee (\neg X\wedge Y\wedge Z)\text{.}\) Il faudra donc combiner l’inverse de \(X\) avec \(Y\) et ensuite combiner ce résultat avec \(Z\) dans des portes ET. Ensuite, on combine cette sortie avec \(X\) dans une porte OU. À noter qu’à l’exercice 2.4.4.1, on verra qu’on peut combiner plus de deux entrées dans une porte ET grâce à l’associativité.
Le circuit associé à cette table de vérité est illustré ci-dessous.
En plus de déterminer des circuits équivalents à des expressions ou des tables de vérité, on peut aussi déterminer l’équivalence de circuits entre eux. Grâce aux règles de la logique, on peut simplifier les circuits. Si on réussit à réduire le nombre de portes utilisées, on aura potentiellement sauvé des coûts de construction du circuit et peut-être aussi en maintenance ou alimentation.
Questions de compréhension de la lecture 2.4.3 Questions de compréhension de la lecture
Ces questions sont à faire avant de venir en classe et à remettre au début du cours.
1.
Déterminer la valeur de la sortie si:
(a)
\(X=1,Y=0,Z=0\text{;}\)
(b)
\(X=0,Y=1,Z=0\text{;}\)
(c)
\(X=0,Y=0,Z=1\text{.}\)
2.
Déterminer la table de vérité du circuit illustré à la figure 2.4.16. Par quelle porte plus simple aurait-on pu le remplacer?
3.
En plus des portes NON,ET et OU, on peut aussi créer d’autres portes à l’aide d’expressions fréquemment utilisées. Dans cet exercice, on s’intéresse au circuit du ou exclusif. Une porte associée à cette opération s’appelle une porte XOR. Elle est illustrée à la figure 2.4.17.
Déterminer une circuit équivalent à une simple porte XOR en termes de porte NON, ET et OU.
4.
Quel serait un circuit associé à l’expression \(p\rightarrow q\text{?}\)
5.
Un circuit peut avoir plus d’une sortie. C’est particulièrement utile quand un circuit est en fait une partie d’un système plus complexe. Le circuit illustré à la figure 2.4.18 est une partie d’un circuit utilisé pour qu’un ordinateur effectue des additions. On reviendra sur ce type de circuit dans le chapitre 3.
Déterminer la table de vérité de ce circuit.
6.
Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
7.
Noter toute question qui demeure suite à la lecture de la section et la résolution des exercices ci-dessus ou toute précision/clarification à apporter. Note: cette question est facultative.
Exercices 2.4.4 Exercices
À faire en classe
Ces exercices sont faits pour travailler en classe. Ils servent à approfondir les notions de la section et à atteindre les objectifs d’apprentissage plus avancés.
1.
Dans cet exercice, on constate qu’il est parfois possible de combiner deux portes en une seule de même nature.
(a)
Vérifier que les deux circuits suivants sont équivalents.
Réponse.
Une première méthode est de construire la table de vérité des deux circuits, et comparer la valeur des sorties. Ceci revient à faire la démonstration de l’associativité du \(\wedge \text{.}\)
Une autre méthode est d’utiliser les propositions logiques associées aux circuits. On utilise cette méthode.
La proposition logique associée au premier circuit est \((X\wedge Y)\wedge Z \text{,}\) alors que la proposition associée au deuxième circuit est \(X\wedge (Y\wedge Z) \text{.}\) En utilisant l’associativité du \(\wedge\text{,}\) on sait que \((X\wedge Y)\wedge Z \equiv X\wedge (Y\wedge Z) \text{.}\)
Puisque les deux propositions associées sont équivalentes, les circuits le sont également
(b)
Vérifier que le résultat est le même si on remplace les portes ET par des portes OU.
Réponse.
Comme à la partie précédente, une première méthode est de construire la table de vérité des deux circuits, et comparer la valeur des sorties. Ceci revient à faire la démonstration de l’associativité du \(\vee \text{.}\)
Une autre méthode est d’utiliser les propositions logiques associées aux circuits. On utilise encore une fois cette méthode.
La proposition logique associée au premier circuit est \((X\vee Y)\vee Z \text{,}\) alors que la proposition associée au deuxième circuit est \(X\vee (Y\vee Z) \text{.}\) En utilisant l’associativité du \(\vee\text{,}\) on sait que \((X\vee Y)\vee Z \equiv X\vee (Y\vee Z) \text{.}\)
Puisque les deux propositions associées sont équivalentes, les circuits le sont également
Puisque les circuits sont équivalents, on utilisera parfois une porte ET ou une porte OU à plus de deux entrées pour alléger les diagrammes. Un exemple d’une porte ET à trois entrées est illustré ci-dessous.
2.
Si la porte XOR, associé au ou exclusif, retourne \(1\) lorsque les entrées sont différentes et \(0\) lorsqu’elle sont égales, on peut aussi définir une porte qui fait le contraire, c’est-à-dire une porte qui retournera \(1\) en cas d’égalité et \(0\) sinon. En termes de propositions logiques, on veut alors le complément du ou exclusif. On parlera d’une porte ÉGAL, qui est illustrée à la figure 2.4.22. On note que c’est la même porte que le XOR, mais avec le point de l’inversion à la sortie. Lorsqu’une porte quelconque possède ce point à sa sortie, on comprendra que c’est l’inversion de la porte sans le point qui est donnée.
Déterminer un circuit équivalent à une porte ÉGAL qui n’utilise que des portes NON,ET et OU.
Indice.
Une possibilité est d’ajouter tout simplement une porte NON à la fin du circuit pour la porte XOR. Ceci devrait normalement donner les cinq portes du XOR et la porte NON. Il est toutefois possible de le faire à l’aide de cinq portes au total si on utilise les lois de la logique pour simplifier le complément du ou exclusif.
3.
À l’exercice 2.4.4.2, il a été mentionné qu’une porte avec un point ouvert à la sortie représente l’inversion de cette porte. On peut ainsi définir les portes NET et NOU, illustrées ci-dessous.
En particulier, dans l’exercice sur la barre de Sheffer, il a été question de l’opérateur logique NAND (anglais pour NET). Pour chaque question ci-dessous, l’exercice équivalent sur la barre de Sheffer pourrait être utile.
(a)
Trouver un circuit logique ne possédant que des portes NET équivalent à l’inversion.
(b)
Trouver un circuit logique ne possédant que des portes NET équivalent à une porte ET.
(c)
Trouver un circuit logique ne possédant que des portes NET équivalent à une porte OU.
4.
Déterminer quel est le résultat du circuit ci-dessous pour les entrées demandées. Attention aux portes avec des inversions \(\circ\text{.}\)
(a)
\(X=0,Y=0,Z=0\)
Réponse.
(b)
\(X=1,Y=0,Z=0\)
Réponse.
(c)
\(X=0,Y=1,Z=0\)
Réponse.
(d)
\(X=0,Y=0,Z=1\)
Réponse.
(e)
\(X=1,Y=1,Z=1\)
Réponse.
5.
Construire un circuit à trois entrées qui retourne \(1\) si et seulement si \(X=Y\) et \(Y\neq Z\) en n’utilisant que les trois portes de base
6.
Construire un circuit à trois entrées qui retourne \(1\) si au moins deux entrées valent 1, et \(0\) sinon. Utiliser n’importe quelle(s) porte(s) vues jusqu’ici.
7.
Construire un circuit à trois entrées qui retourne \(1\) si au moins deux entrées valent 0, et \(0\) sinon. Utiliser n’importe quelle(s) porte(s) vues jusqu’ici.
Exercices supplémentaires
8.
Un pont de la région de Vancouver possède trois voies qui s’utilisent dans les deux sens, selon la direction du trafic (vers l’île ou vers l’extérieur). Afin d’orienter les usagers, des symboles lumineux vert ou rouge indique si une voie est accessible. L’affichage de ces symboles est contrôlé par deux interrupteurs \(X,Y\text{.}\)
Lorsque les deux interrupteurs sont fermés (\(0\)), les trois voies affichent rouge. Lorsque \(X\) seulement est ouvert, la voie la plus à droite des trois est au vert et les deux autres sont au rouge. Lorsque \(Y\) seulement est ouvert, ce sont les deux voies de droites qui sont au vert, la troisième est au rouge. Finalement, si les deux interrupteurs sont ouverts, les trois voies sont au vert.
Donner un circuit à deux entrées et trois sorties illustrant cette situation.
1
Image tirée de Wikipedia, libre de droits
9.
(a)
Trouver un circuit logique ne possédant que des portes NOU équivalent à l’inversion.
(b)
Trouver un circuit logique ne possédant que des portes NOU équivalent à une porte ET.
(c)
Trouver un circuit logique ne possédant que des portes NOU équivalent à une porte OU.
L’opérateur logique équivalent à la porte NOU est appelé la flèche de Peirce. On note l’opération \(p\downarrow q\text{.}\)
