NSI 1ère

Logique et applications

Introduction

Les valeurs logiques, ou booléennes, ainsi que les opérateurs logiques (and, or, not) qui s'y appliquent, ont déjà été mentionnées en programmation Python,

Toutefois leur rôle en Informatique dépasse largement leur utilisation en programmation.
Les deux valeurs logiques possibles (Vrai et Faux) peuvent être utilisées pour modéliser les deux valeurs numériques 0 et 1 permettant de coder toute forme d'information. Elles peuvent aussi être représentées concrètement par deux états différents dans un circuit électronique logique : relié au pôle + de l'alimentation (état haut) , ou à son pôle - (état bas).
Les circuits électroniques logiques permettent de réaliser concrètement des opérations logiques, qui seront elles-mêmes utilisées pour effectuer des calculs ou pour gérer les mémoires.
Ce triple aspect (logique, numérique et électrique) est résumé sur la figure ci-dessous. les trois aspects des valeurs logiques

Les valeurs et expressions logiques (booléennes) sont à la base du fonctionnement des machines programmables.

Variables et fonctions logiques

Les variables logiques

On rappelle qu'une variable logique est une variable qui ne peut prendre que deux valeurs différentes, en principe Vrai ou Faux.
Les propositions, comme par exemple "J'ai les yeux bleus" ou "Il fait jour", sont des variables logiques.
Une variable logique n'est cependant pas nécessairement une proposition : par la suite on représentera simplement une variable logique par une lettre comme A, B, S..., ne pouvant prendre que deux valeurs.
Ces deux valeurs, ou états, possibles sont Vrai et Faux, mais on pourra aussi les représenter sous une forme numérique:
classiquement, on utilise la valeur numérique 1 comme équivalent de la valeur logique Vrai, et la valeur numérique 0 comme équivalent de la valeur logique Faux .
Cette convention sera souvent utilisée par la suite, notamment dans les tables de vérité.

Fonctions logiques

Une fonction logique fait correspondre une ou plusieurs variables logiques (souvent appelées "entrées") avec une variable logique ("sortie").
La valeur de la sortie est déterminée par les valeurs des entrées.

La correspondance entre la ou les valeurs de la ou des entrées, et celle de la sortie, est souvent donnée sous la forme d'un tableau appelé table de vérité de la fonction.

Fonctions usuelles

Fonction not (inverseur)

La fonction not (inverseur) est une fonction à une seule entrée, et dont la sortie a l'état opposé de celui de l'entrée.
Si S=not A alors S est Vrai si A est Faux, et Faux si A est Vrai.

Sous forme de table de vérité, on écrira
S=not A
AS
FauxVrai
VraiFaux
qu'on peut aussi écrire,en codant l'état Vrai par le chiffre 1 et l'état faux par le chiffre 0 :
S=not A
AS
01
10
On a not not A = A
Il existe plusieurs façons de noter la fonction not:
S=not A comme ci-dessus (expression valide en Python), ou
S=A,
ou S=¬A .
Nous utiliserons plutôt les deux premières.

Fonction and (et)

Cette fonction prend au moins deux entrées.
La sortie de la fonction and est Vraie si et seulement si toutes ses entrées sont Vraies.

Pour une fonction and à deux entrées A et B la table de vérité est :
S=A and B
ABS
FauxFauxFaux
FauxVraiFaux
VraiFauxFaux
VraiVraiVrai
qu'on peut aussi écrire :
S=A and B
ABS
000
010
100
111
La fonction S=A and B peut aussi être notée
S=A · B
ou S = A ∧ B.

Fonction or (ou inclusif)

Cette fonction prend au moins deux entrées.
La sortie de la fonction or est Vraie si et seuiement si au moins une de ses entrées est Vraie.

Pour une fonction or à deux entrées A et B la table de vérité est :
S=A or B
ABS
FauxFauxFaux
FauxVraiVrai
VraiFauxVrai
VraiVraiVrai
qu'on peut aussi écrire
S=A or B
ABS
000
011
101
111
La fonction S=A or B peut aussi être notée
S=A + B
ou S = A ∨ B

Fonction xor (ou exclusif)

Cette fonction prend au moins deux entrées.
La sortie de la fonction xor est Vraie si et seulement si une et une seule de ses entrées est vraie.

Pour une fonction xor à deux entrées A et B la table de vérité est :
S=A xor B
ABS
FauxFauxFaux
FauxVraiVrai
VraiFauxVrai
VraiVraiFaux
c'est à dire
S=A xor B
ABS
000
011
101
110
La fonction S=A xor B peut aussi être notée
S=A ⊕ B.

Fonctions composées

On peut obtenir une nouvelle fonction logique par composition de fonctions logiques.
Par exemple en composant la fonction not et la fonction and on obtient une nouvelle fonction S=not(A and B)= A · B = ¬(A ∧ B) de table de vérité
S=not(A and B)
AB A and B (étape intermé-diaire)S
0001
0101
1001
1110
Les fonctions not, and, or sont appelées fonctions logiques élémentaires car elles permettent d'obtenir n'importe quelle fonction logique par combinaison.

Par exemple chacune des combinaisons suivantes est équivalente à la fonction à deux entrées (A,B)→ Vrai:

  • (A and B) or not(A and B)
  • A or B or (not A and not B)
  • not A or not B or(A and B)
Deux fonctions ou combinaisons de fonctions qui ont la même table de vérité sont équivalentes

L'exercice ci-dessus a permis de mettre en évidence deux équivalences fondamentales :
  • not (A or B) = (not A) and (not B)
  • not (A and B) = (not A) or (not B)
qu'on peut écrire aussi en utilisant la notation xymbolique :
  • A · B =A + B
  • A + B = A·B
Ces équivalences sont appelées Lois de De Morgan.

Electronique logique

Premier exemple et principe du codage des états.

Les portes logiques sont des composants électroniques permettant de réaliser des opérations logiques. Le schéma suivant montre par exemple comment on peut observer le comportement d'une porte logique ET (AND).
montage testeur porte ET
La porte logique ET peut être représentée par un des deux symboles normalisés ci-dessous.
symboles portes ET
Dans le montage représenté, les entrées de la porte logique peuvent être reliées, grâce à des interrupteurs, soit à la borne + d'une source de tension continue, soit à sa borne -.
Une entrée reliée à la borne + est dite "à l'état haut". Elle a la valeur logique Vrai (1).
Une entrée reliée à la borne - est dite "à l'état bas". Elle a la valeur logique Faux (0).
De même, si la tension entre la sortie de la porte logique et la borne - est nulle, la sortie est dite " à l'état bas" : elle a la valeur logique Faux (0) . Si au contraire elle est élevée, la sortie est dite "à l'état haut" et a la valeur logique Vrai (1).
Cliquer ici pour pouvoir simuler le fonctionnement de ce circuit Dans la simulation, actionner les interrupteurs pour agir sur l'état des entrées et observer comment l'état de la sortie change en conséquence.

On peut remplacer l'ensemble "source de tension continue + interrupteurs" par les "entrées logiques" proposées par le simulateur : une entrée logique représente un point pouvant être mis à l'état haut (H) ou bas (Low) d'un clic de souris. De même le voltmètre mesurant l'état de la sortie peut être remplacé par une "sortie logique" affichant H ou L. on peut aussi se contenter d'observer la couleur prise par la sortie puisque le simulateur fait apparaître en vert vif les parties du circuit qui sont à l'état haut.

Effacer la simulation précédente (voir ci-après Prise en main du simulateur) et construire le schéma ci-dessous, utilisant une porte ET et des entrées et sorties logiques (qu'on trouve dans le menu Dessiner/Portes logiques). Utiliser l'option "Editer" des entrées et sorties logiques pour remplacer l'affichage "H/L" de leur état par un affichage numérique "1/0".
porte ET
Prise en main rapide du simulateur :
    Construire un circuit
  • Utiiser le menu Dessiner pour trouver des composants, dans le sous-meenu Portes logiques notamment.
  • Utiliser la souris pour tracer un composant à l'emplacement et avec l'orientation voulus.
  • On peut annuler/refaire à l'aide des combinaisons de touches Ctrl-Z et Ctrl-Y
  • Pour connecter les composants entre eux, sélectionner Dessiner/Ajouter fils (ou utiliser la touche raccouci w) et tracer un fil entre les bornes à connecter. Une connection correcte apparaît sous forme d'un rond blanc, un rond rouge signale une mauvaise connection (on ne peut connecter un fil que par ses extrémités).
  • Pour effacer un composant, placer le curseur de la souris dessus (il apparaît alors en bleu clair) et utiliser la touche Suppr
  • Pour déplacer un composant, maintenir la touche Majuscule appuyée et déplacer le composant avec la souris.
  • Pour faire pivoter un composant, maintenir la touche Ctrl appuyée et déplacer le composant avec la souris.
  • Pour modifier les propriétés d'un composant, faire un clic-droit sur le composant puis choisir l'option "Editer".
  • Pour déplacer tout le circuit, maintenir la touche Alt appuyée et déplacer le circuit avec la souris.
  • Pour effacer tout le circuit, le sélectionner par Ctrl-A et utiliser la touche Suppr, ou bien utiliser la dernière ligne du menu "Circuits", "circuit vide".
  • Pour obtenir des informations sur un composant ou une partie d'un circuit il suffit de placer le curseur de la souris dessus.
    Simulation
  • La simulation est active lorsque le bouton RUN/Stop apparaît grisé et que le compteur de temps tourne.
  • On peut modifier l'état de certains composants (ex : interrupteur, entrée logique) en mode conception comme en mode simulation, mais il faut être en mode simulation pour visualiser les conséquences.

Autres portes logiques

Les portes logiques sont réalisées à l'aide de transistors, qui sont les composants de base de l'électronique. On les trouve sous forme de circuits intégrés ("puces") contenant généralement plusieurs portes du même type.
puces
Puces électroniques: deux des "pattes" sont à relier à l'alimentation électrique, les autres sont, si la puce contient des portes logiques, soit des entrées soit des sorties logiques. Exemples d'une famille de "puces" logiques
On retrouve dans ces circuits intégrés les portes logiques correspondant aux fonctions logiques élémentaires (non,and,or, xor) ainsi qu'à la fonction xor.
De haut en bas : symboles normalisés d'une porte NON, d'une porte OU , porte OU-EXclusif (XOR)
La combinaison d'une porte avec un non est représentée en accolant un petit rond au symbole de la porte de base (exemple ci-dessous)
:Symboles normalisés du non-ou (nor)
Ces portes élémentaires permettent de construire des circuits logiques plus élaborés comme ceux vus ci-après.

Circuits de calcul

Demi-additionneur

Un demi-additionneur est un circuit logique permettant d'obtenir le résultat (en binaire) de l'addition de deux nombres codés sur un bit. Le résultat doit donc s'écrire sur deux bits.
  1. A et B étant les deux variables d'entrée du demi-additionneur et S1 et S0 ses deux sorties, les valeurs (0 ou 1) des sorties sont les bits composant le résultat de l'addition de A et de B en base deux, dans l'ordre S1S0. Compléter la table de vérité du demi-additionneur ci-dessous:
      A     B  Résultat de l'addition en base deux
    S1
    (bit de poids fort)     		S0
    (bit de poids faible)
    00  
    01  
    10  
    11  
  2. En déduire quelles sont les fonctions logiques qui permettent d'obtenir respectivement S1 et S0 à partir de A et B.
  3. A l'aide du simulateur, réaliser le demi-additionneur avec des portes logiques et vérifier son fonctionnement (penser à mettre les entrées et sorties en format numérique).

Additionneur complet

Pour additionner deux nombres binaires de plus d'un bit, il faut pouvoir effectuer la somme de trois nombres d'un bit, à cause de la retenue éventuelle (par exemple pour additionner 11 et 11 on devra pouvoir effectuer 1+1+1 en base deux).
Un circuit logique capable d'additionner trois nombres d'un bit aura trois entrées A,B et R, et deux sorties S1 et S0 (S1 étant le bit de poids fort du résultat, et S0 son bit de poids faible). Compléter la table de vérité de l'additionneur complet ci-dessous.
  A     B     R  Résultat de l'addition en base deux
S1
(bit de poids fort) 		S0
(bit de poids faible)
000  
010  
100  
110  
001  
011  
101  
111  

Les expressions logiques utilisant le plus petit nombre de fonctions différentes pour obtenir S0 et S1 sont :

S1 = (A and B) or (R and ( A xor B))

S0 = (A xor B) xor R.

Dans le menu "circuits/logique combinatoire" du simulateur, choisir "additionneur complet". Identifier la sortie S1 et la sortie S0, ainsi que les entrées A, B et R. Vérifier que le circuit donne bien le résultat de l'addition A+B+R , en base deux sur S1 et S0.
Ce montage peut être intégré sous la forme d'un circuit additionneur à 3 entrées et 2 sorties. Le simulateur propose un tel circuit dans le menu "Dessiner/Circuits intégrés numériques" , ainsi qu'un demi-additionneur à deux entrées et deux sorties. demiadditionneur
Demi-additionneur : S est le bit de poids faible du résultat (S0 pour nous), C son bit de poids fort (S1 pour nous).
La lettre C est pour "carry", anglais pour "retenue".
additionneur
Additionneur complet : L'entrée "Cin" est destinée à recevoir la retenue entrante (R pour nous), S est le bit de poids faible du résultat, C son bit de poids fort.

Addition sur plusieurs bits

Pour additionner des nombres à plusieurs bits, on utilise plusieurs additionneurs étagés, la sortie C de l'un étant l'entrée Cin du suivant.
On peut voir ci-dessous un exemple d'additionneur 4 bits. additionneur 4 bits

Cet additionneur est constitué de quatre additionneurs complets, en cascade. La retenue entrante du premier additionneur est mise à 0 : on aurait pu le remplacer par un demi-additionneur. Dans la pratique toutefois, il est préférable de laisser la possibilité pour un additionneur N bits d'avoir une retenue entrante : cela permet de l'associer en cascade avec d'autres additionneurs pour en faire un plus grand (cliquer sur l'image pour ouvrir et tester cer additionneur dans le simulateur)

Opposé d'un nombre

Un circuit additionneur peut aussi être utilisé pour faire des soustrations : pour effectuer A-B, il suffit de faire A+(-B). Il faut donc pouvoir déterminer l'opposé d'un entier. Dans le chapitre sur le codage des données, on a vu comment écrire en base deux l'opposé d'un nombre, en binaire : il faut inverser tous les digits, puis ajouter 1.
Cliquer pour compléter le schéma dans le simulateur d'un montage permettant d'obtenir l'opposé d'un entier, codé complément à deux.
La partie du montage déjà réalisée à l'aide de demi-additionneurs est un incrémenteur : il ajoute 1 au nombre binaire écrit sur les entrées A0 à A3, le résultat s'écrivant sur les sorties S0 à S3.
L'objectif est de compléter le montage en ajoutant des portes logiques et des connexions, de sorte que les 4 bits écrits dans le cadre marqué "sortie", à droite, forment l'opposé de l'entier écrit sur 4 bits dans le cadre marqué "entrée", à gauche (en complément à deux sur 4 bits)

Logique séquentielle

Les portes logiques permettent aussi de construire des circuits dont la réponse est séquentielle, c'est à dire que l'état du circuit à un moment donné dépend non seulement de l'état de ses entrées à ce moment là, mais aussi de l'état précédent du circuit. Leurs transitions entre états peuvent souvent être synchronisées à l'aide d'un signal d'horloge

Des circuits séquentiels sont par exemple utilisés pour écrire les données binaires en mémoire.

Quelques exemples de circuits séquentiels

Bascule RS

Ouvrir le simulateur .

Dans le menu Circuits/Logique séquentielle/Bascule, choisir Bascule SR.

Ce circuit comporte deux entrées, appelées usuellement S (pour "set", ici notée Affecter) et R (pour "reset), d'où le nom du circuit.
Le circuit possède aussi deux sorties, qui sont en principe dans deux états complémentaires : si l'une est à 1, l'autre est à 0, et inversement. Ces deux sorties complémentaires, qui changent donc d'état en même temps, sont caractéristiques des circuits de type bascule.
Les deux entrées sont ici paramétrées en bouton poussoir à partir de l'état haut : quand on les actionne, elles passent brièvement à l'état bas, avant de revenir à l'état haut.
A l'aide du simulateur, vérifier qu'une impulsion à l'entrée "Affecter" (set) fait passer la sortie Q à l'état haut si elle était à l'état bas, et n'a aucun effet si Q est à l'état haut.
Symétriquement, vérifier qu'une impulsion à l'entrée "reset" fait passer la sortie Q à l'état bas si elle était à l'état haut, et n'a aucun effet si elle est à l'état bas.
Vérifier aussi que les deux sorties changent bien d'état simultanément, comportement caractéristique d'une "bascule".

Verrou D

Cette bascule dérive de la bascule RS précédente. Utiliser le simulateur pour vérifier que le circuit permet de transférer sur la sortie Q la valeur de l'entrée D (et sur la sortie Q la valeur de D, à la condition que l'entrée T soit à l'état haut. Si l'entrée T est à l'état bas, les sorties sont verrouillées: elles ne changeront pas d'état, quoi qu'il se passe sur l'entrée D.

On a donc ici un circuit pouvant servir de mémoire réinscriptible: on peut écrire la donnée D dans la mémoire Q en mettant l'entrée de contrôle T à l'état haut, et verrouiller la mémoire en mettant ensuite T à l'état bas.

Bascule synchronisée sur un signal d'horloge

Dans le menu Circuits/Logique séquentielle/Bascule du simulateur, choisir Bascule Maître-Esclave.

Ce montage combine deux verrous D vu précédemments.

Un signal d'horloge (clk) est appliqué à leurs entrées T. On appelle signal d'horloge un signal périodique de forme carrée, passant alternativement de l'état haut à l'état bas ( courbe visible tout en bas de l'écran dans le simulateur). Comme le précédent, ce circuit recopie sur la sortie Q l'état de l'entrée D, mais seulement au moment où le signal d'horloge passe de l'état haut à l'état bas (bascule sur front descendant).
Utiliser le simulateur pour vérifier ce fonctionnement: changer l'état de l'entrée D et regarder à quel moment ce changement est répercuté sur les sorties, en observant les trois courbes en bas de l'écran, qui montrent de haut en bas l'état de D, l'état de Q, et celui de l'horloge.

Les opérateurs logiques bit à bit

Puisque les données sont stockées en mémoire sous forme de nombres binaires, on peut considérer chacun de leurs bits comme une variable logique.

On peut ainsi envisager d'effectuer des opérations logiques bit par bit sur ces données.

Python propose ainsi des opérateurs logiques bit à bit pouvant être appliqués à des nombres entiers.

    Les opérateurs bit à bit sont représentés en Python par les symboles suivants:
  • & : opérateur binaire ET : il effectue un ET logique entre les bits de même rang des deux données. Par exemple, (1011)2 & (1000)2 = (1000)2
  • | (alt-gr 6) : opérateur binaire OU-INCLUSIF : il effectue un OU INCLUSIF logique entre les bits de même rang des deux données. Par exemple, (1011)2 | (1000)2 = (1011)2
  • ^ (alt-gr 9) : opérateur binaire OU-EXCLUSIF : il effectue un OU EXCLUSIF logique entre les bits de même rang des deux données. Par exemple, (1011)2 ^ (1000)2 = (0011)2
  • ~ (alt-gr 2, puis barre d'espace) : opérateur NON (inverseur), il inverse tous les bits. Appliqué à une valeur entière a, il donnera l'entier ~a tel que a & ~a vaut toujours 0 quelle que soit la valeur de a.
L'exercice ci-dessus met en évidence une application importante des opérateurs bit à bit, le masquage logique , qui permet de ne conserver en l'état qu'une partie des bits d'une donnée.