Chapitre 13 circuits logiques et expressions booléennes

Crédits

Ce cours est largement inspiré du chapitre 22 du manuel NSI de la collection Tortue chez Ellipsen auteurs : Ballabonski, Conchon, Filliatre, N’Guyen.

Préambule

Les circuits d’un ordinateur manipulent uniquement des 0 ou des 1 représentés en interne par des tensions hautes ou basses. Les premiers ordinateurs construits dans la période 1945-1950 sont basés sur une technologie de tube à vide ou tube électrique. En 1947, aux laboratoires Bell, Shockley, Bardeen et Brattain inventent le transistor au germanium un petit composant électronique qui se comporte comme un interrupteur. Les transistors, plus petits et dissipant moins de chaleur, vont supplanter les tubes électriques : en 1954 le germanium est remplacé par le silicium, en 1955 apparaissent les premiers ordinateurs entièrement transistorisés, en 1960 le transistor à effet de champ permet l’intégration de dizaines composants dans un centimètre carré. Les transistors sont ensuite directement gravés dans une plaque de silicium constituant un cicrcuit intégré. En 1965 Gordon Moore futur directeur d’Intel énonce la loi empirique portant son nom qui fixe une feuille de route à l’industrie des mircroprocesseurs : le doublement de la densité d’intégration des transistors tous les deux ans. Cette loi s’est vérifiée jusqu’à présent avec une finesse de gravure d’environ 5 nanomètres en 2020. Le graphique ci-dessous représente l’évolution du nombre de transistors par circuit intégré.

Loi de Moore Source : Wikipedia

Portes logiques

Le transistor porte logique de base

Définition 1

Un transistor possède trois broches : la grille, la sortie (ou drain) et la source soumis à des états de tension haute ou basse qu’on peut assimiler aux valeurs binaires 1 et 0 d’un bit. Si la tension appliquée sur la grille est haute (bit à 1) alors le transitor laisse passer le courant entre la source d’énergie et la sortie et cette dernière passe à l’état de tension basse (bit à 0), sinon la sortie reste en tension haute (bit 1).

Une fonction logique prend un ou plusieurs bits en entrée et retourne un ou plusieurs bits en sortie. Une porte logique est un circuit électronique représentant une fonction logique.

Une table logique représente les sorties produites par une fonction logique pour toutes les entrées possibles.

Un transistor représente une fonction logique dont le bit d’entrée est l’état de tension de la grille et le bit de sortie, l’état de tension de la sortie. La table logique (table 1) associée est celle du NON logique ou Inverseur.

Fichier de test Logisim : transistor.circ.

Transistor

A B = NON(A)
0 1
1 0

Table logique d’une porte NON

Il existe deux conventions de représentation symbolique des portes logiques, une européenne et une américaine.

porte NOT européeenne
& porte NOT américaine

Tutoriel video Logisim : le transistor

D’autres portes logiques

Transistors en série ou en parallèle

Exercice 1

On donne ci-dessous les représentations de deux portes logiques :

Chacune de ces portes logiques comportent deux bits d’entrée : A pour la grille du transistor 1 et B pour la grille du transistor 2 et un bit de sortie.

Compléter leurs tables logiques.

Vérifier avec Logisim et les fichiers porte_NAND.circ et porte_NOR.circ.

Tutoriel video Logisim : porte NAND

Tutoriel video Logisim : porte NOR

A B NAND(A, B)
0 0  
0 1  
1 0  
1 1  
A B NOR(A, B)
0 0  
0 1  
1 0  
1 1  

Porte NAND
& Porte NOR

Voici les représentations symboliques des portes logiques NAND et NOR :

Porte NAND européenne
& Porte NAND américaine

Porte NOR européenne
& Porte NOR américaine

Portes logiques et fonctions logiques élémentaires

Exercice 2

Fichier de test Logisim : exercice2.circ.

  1. Compléter la table logique de la porte logique représentée par le circuit ci-dessous. Quelle porte logique peut-on ainsi représenter ?

Porte NOT

A B = f(A)
0  
1  
  1. Compléter la table logique de la porte logique représentée par le circuit ci-dessous. Quelle fonction logique correspond à cette porte logique ?

Porte AND

A B C = g(A, B)
0 0  
0 1  
1 0  
1 1  

Tutoriel video Logisim : exercice 2

Exercice 3

Fichier de test Logisim : exercice3.circ.

  1. Compléter la table logique de la porte logique représentée par le circuit ci-dessous. Quelle porte logique peut-on ainsi représenter ?

Porte NOT

A B = f(A)
0  
1  
  1. Compléter la table logique de la porte logique représentée par le circuit ci-dessous. Quelle fonction logique correspond à cette porte logique ?

Porte OR

A B C = g(A, B)
0 0  
0 1  
1 0  
1 1  

Tutoriel video Logisim : exercice 3

Voici les représentations symboliques des portes logiques AND et OR :

Porte AND européenne
& Porte AND américaine

Porte OR européenne
& Porte OR américaine

Exercice 4

  1. Construire un circuit représentant une porte OR uniquement avec des portes NOR.
  2. Construire un circuit représentant une porte AND uniquement avec des portes NAND.

Ainsi chacune des portes, NAND ou NOR permet de construire les portes NOT, OR, AND. Toute porte logique pouvant s’exprimer à l’aide de ces trois portes, les portes NAND et NOR sont dites universelles.

Tutoriel video Logisim : exercice 4

Fonctions booléennes

Fonctions booléennes

Définition 2

Exercice 5

  1. Compléter la fonction Python ci-dessous pour qu’elle affiche la table de vérité d’une fonction booléenne à deux entrées. Expliquer le rôle de la fonction int.
def table_verite_2bits(fonction):
    print('|{:^10}|{:^10}|{:^15}|'.format('a','b',fonction.__name__+'(a,b)'))
    for a in .............:
        for b in .............:
            print('|{:^10}|{:^10}|{:^15}|'.format(......, ......, 
            int(fonction(bool(a),bool(b)))))
  1. Vérifier que les tables de vérité affichées pour les fonctions bool.__or__, bool.__and__ et bool.__not__ sont correctes.
In [4]: table_verite_2bits(bool.__or__)                                                                                                                                           
|    a     |    b     |  __or__(a,b)  |
|    1     |    1     |       1       |
|    1     |    0     |       1       |
|    0     |    1     |       1       |
|    0     |    0     |       0       |

Tutoriel video : exercice 5

Propriété 1

On peut exprimer toute fonction booléenne à l’aide de trois fonctions booléennes élémentaires :

x \neg x
0  
1  
x y x \wedge y
0 0  
0 1  
1 0  
1 1  
x y x \vee y
0 0  
0 1  
1 0  
1 1  

Propriété 2

  1. Les fonctions booléennes élémentaires respectent un certain nombre de règles qui permettent de simplifier les expressions booléennes complexes :
  1. Les fonctions booléennes élémentaire respectent des règles de priorité : la négation est prioritaire sur la conjonction qui est prioritaire sur la disjonction.
    Il est recommandé de mettre des parenthèses plutôt que d’appliquer les règles de priorité dans l’écriture des expressions booléennes.

QCM types E3C

Exercice 6

  1. Parmi les quatre expressions suivantes, laquelle s’évalue en True ?
  1. Sachant que l’expression not(a or b) a la valeur True, quelles peuvent être les valeurs des variables booléennes a et b ?
  1. Pour quelles valeurs booléennes des variables a, b et c l’expression (a or b) and (not c) a-t-elle pour valeur True
  1. Si A et B sont des variables booléennes, laquelle de ces expressions booléennes est équivalente
    à (not A) or B ?
  1. Choisir une expression booléenne pour la variable S qui satisfait la table de vérité suivante.
A B S
0 0 1
0 1 0
1 0 1
1 1 1
  1. On considère une formule booléenne form des variables booléennes a et b dont voici la table de vérité.
a b form
True True False
False True False
True False True
False False False

Quelle est cette formule booléenne ?

Tutoriel video : exercice 6

Pour aller plus loin (hors programme de première NSI)

Dresser la table de vérité d’une fonction booléenne

Exercice 7

Démontrer dans chaque cas l’égalité des expressions booléennes en utilisant les deux méthodes suivantes :

  1. x + x . y = x
  2. x + \overline{x} . y= x + y
  3. x . z + \overline{x} . y + y . z = x . z + \overline{x} . y
  4. \overline{y . (x + \overline{y})} = \overline{x} + \overline{y}
  5. x . ( \overline{x} + \overline{y}) . (x + y) = x . \overline{y}

Exprimer une fonction booléenne à partir de sa table de vérité

Exercice 8

On considère la fonction booléenne dont la table de vérité est :

x y f(x, y)
0 0 0
0 1 1
1 0 1
1 1 0
  1. Exprimer chacune des lignes où la fonction prend la valeur 1 comme la conjonction des entrées en remplaçant chaque 1 par la variable qu’il représente et chaque 0 par la négation de la variable. Par exemple le 1 de la deuxième ligne s’écrira \overline{x} . y.
  2. On peut alors écrire f(x,y) comme la disjonction des formes conjonctives obtenues à la question précédente. En déduire une expression booléenne de f(x, y).
  3. Ouvrir le logiciel Logisim et construire une porte logique représentant cette fonction booléenne.
  4. Cette fonction s’appelle OU EXCLUSIF ou XOR. Ce nom vous paraît-il bien choisi ?

Voici les représentations symboliques de la porte logique XOR :

Porte XOR europeenne
& Porte XOR americaine

Circuits combinatoires

Définition

Définition 3

Un circuit logique combinatoire permet de réaliser une ou plusieurs fonctions booléennes : ses sorties ne dépendent que de l’état actuel de ses entrées. Les portes logiques NOT, NOR, NAND, AND, OR et XOR sont des circuits combinatoires.

Il existe d’autres circuits, dits séquentiels, dont les sorties se calculent non seulement à partir de leurs valeurs d’entrée actuelles mais aussi à partir de leurs états précédents : le facteur temps intervient. Ils utilisent des circuits de mémoire pour mémoriser leurs états antérieurs.

Exercice 9

On considère la fonction booléeenne f dont la table de vérité est donnée ci-dessous :

x y f(x, y)
0 0 1
0 1 0
1 0 0
1 1 1

  1. En utilisant la méthode exposée dans l’exercice 8, déterminer une expression booléenne de la fonction f.

  2. Ouvrir le logiciel Logisim et construire un circuit combinatoire représentant cette fonction booléenne :

    • En utilisant les portes logiques NOT, NOR, NAND, AND, OR ou XOR.
    • En n’utilisant que des portes logiques NOT, AND ou OR.
    • En n’utilisant que des portes logiques NOR.

Tutoriel video : exercice 9

Décodeur avec 2 bits d’entrées

Exercice 10

On considère un circuit combinatoire qui possède deux entrées e_{0} et e_{1} et quatre sorties s_{0}, s_{1}, s_{2} et s_{3}.

La sortie indexée par le nombre dont le bit de poids faible est e_{0} et le bit de poids fort e_{1}, est positionnée à 1 et les autres sorties à 0. Ce circuit est ainsi appelé décodeur 2 bits.

  1. Compléter la table de vérité de ce circuit combinatoire.
e_{0} e_{1} s_{0} s_{1} s_{2} s_{3}
0 0        
0 1        
1 0        
1 1        

  1. En utilisant la méthode exposée dans l’exercice 7, déterminer une expression booléenne de chacune des sorties s_{0}, s_{1}, s_{2} et s_{3}, en fonction des entrées e_{0} et e_{1}.

  2. Ouvrir le logiciel Logisim et construire un circuit combinatoire représentant un décodeur 2 bits.

Demi-additionneur et additionneur 1 bit

Exercice 11

  1. Effectuer les additions binaires : 0+0, 0+1, 1+0 et 1+1.

  2. Un demi-additionneur binaire 1 bit est un circuit combinatoire qui possède :

    • deux entrées : deux bits d’opérande e_{0} et e_{1} ;
    • deux sorties : un bit de résultat s et un bit de retenue sortante r.

La sortie s prend pour valeur le bit des unités et la sortie r le bit de retenue sortante, lorsqu’on additionne les deux bits d’entrée e_{0} et e_{1}.

  1. Compléter la table de vérité de ce circuit combinatoire :
e_{0} e_{1} s r
0 0    
0 1    
1 0    
1 1    
  1. Justifier qu’un demi-additionneur binaire 1 bit peut être représenté par le circuit ci-dessous.

Demi-additionneur binaire

  1. Ouvrir le logiciel Logisim et construire un circuit combinatoire représentant un demi-additionneur binaire 1 bit.

Tutoriel video : exercice 11

Exercice 12

Un additionneur binaire 1 bit est un circuit combinatoire qui possède :

  1. Compléter les colonnes de la table de vérité d’un additionneur binaire 1 bit pour le bit de résultat s_{2} et le bit retenue sortante r_{3}.
e_{0} e_{1} r_{0} s_{1}=\ldots \ldots r_{1}=\ldots \ldots s_{2}=\ldots \ldots r_{2}=\ldots \ldots r_{3}=\ldots \ldots
0 0 0          
0 1 0          
1 0 0          
1 1 0          
0 0 1          
0 1 1          
1 0 1          
1 1 1          

  1. Un additionneur binaire 1 bit peut être réalisé à l’aide de deux demi-additionneurs binaires 1 bit :

    • Le premier demi-additionneur binaire 1 bit prend en entrée les bits d’opérande e_{0} et e_{1} et retourne en sortie un bit de résultat intermédiaire s_{1} et un bit de retenue sortante intermédiaire r_{1}. Donner une expression booléenne de s_{1} et r_{1} en fonction de e_{0} et e_{1}.
    • Le second demi-additionneur binaire 1 bit prend en entrée le bit de résultat s_{1} et le bit de retenue entrante r_{0} et retourne en sortie le bit de résultat final s_{2} et un bit de retenue sortante intermédiaire r_{2}. Donner une expression booléenne de s_{2} et r_{2} en fonction de s_{1} et r_{0}.
    • Enfin, la retenue sortante r_{3} s’obtient à partir de la retenue sortante r_{1} du premier demi-additionneur et de la retenue sortante r_{2} du second. Donner une expression booléenne de r_{3} en fonction de r_{1} et r_{2}.

    Compléter les colonnes s_{1}, r_{1} et r_{2} puis s_{2} et r_{3} de la table de vérité de l’additionneur binaire à 1 bit.

  2. Avec le logiciel Logisim ouvrir le fichier contenant le demi-additionneur de l’exercice précédent.

    • Ajouter un nouveau circuit avec Add a circuit , le nommer additionneur1bit puis copier/coller dedans le circuit du demi-additionneur binaire 1 bit. Compléter le circuit pour obtenir un additionneur binaire 1 bit.
    • Ajouter un nouveau circuit avec Add a circuit , le nommer additionneur2bits puis copier/coller dedans le circuit de l’ additionneur binaire 1 bit. Compléter le circuit pour obtenir un additionneur binaire 2 bits.

Tutoriel video : exercice 12

Opérations bit à bit en Python (hors programme de première NSI)

Propriété 3

Les fonctions booléennes élémentaires (OR, AND, NOT, XOR) existent en Python sous la forme d’opérateurs booléens mais sont également implémentés sous la forme d’opérateurs bit à bit sur les nombres. Un opérateur bit à bit (bitwise en anglais) s’applique sur les bits de même poids des représentations binaires de ses opérandes.

Opérateur booléen Opérateur bit à bit Exemple
and , ET & >>> bin(0b101001 & 0b101010)
    '0b101000'
or , OU \| >>> bin(0b101001 \| 0b101010)
    '0b101011'
xor , OU EXCLUSIF ^ >>> bin(0b101001 ^ 0b101010)
    '0b000011'
not , NEGATION ~ >>> ~5 #~x retourne -x - 1
    -6

Exemples d’utilisation d’opérateurs bit à bit :

>>> bits_pairs = sum(2 ** k for k in range(0, 8, 2))
>>> bin(bits_pairs)
'0b1010101'
>>> bin(183)
'0b10110111'
>>> bin(183 & bits_pairs)
'0b10100010'

>>> diego = 69
>>> masque = 42
>>> zorro = diego ^ masque
>>> zorro
111
>>> zorro ^ masque
69

Exercice 13

Dans un réseau IP l’adresse IP d’une machine est constituée d’un préfixe correspondant à l’adresse du réseau (commune à toutes les machines du réseau) et à un suffixe machine, identifiant la machine sur le réseau.

Le préfixe réseau s’obtient à partir de l’adresse IP de la machine en faisant un ET bit à bit avec le masque de sous-réseau.

Par exemple si l’adresse est 192.168.11.12 de représentation binaire 11000000.10101000.00001011.00001011 et le masque de sous-réseau est 255.255.252.0 de représentation binaire

11111111.11111111.11111100.00000000 alors le préfixe réseau est 11000000.10101000.00001000.00000000 soit 192.168.8.0.

On donne ci-dessous deux fonctions outils :

def ip2liste(ip):
    "Transforme une  adresse IP V4 (type str) en liste d'entiers"
    return [int(champ) for champ in ip.split('.')]

def liste2ip(ipliste):
    "Transforme une  liste d'entiers en adresse IP V4 (type str)"
    return '.'.join(str(n) for n in ipliste)

  1. Écrire une fonction de signature prefixe_reseau(ip, masque) qui retourne le préfixe réseau sous forme d’adresse IP V4 (type str) à partir d’une adresse IP V4 et d’un masque de sous-réseau.

  2. Écrire une fonction de signature suffixe_machine(ip, masque) qui retourne le suffixe machine sous forme d’adresse IP V4 (type str) à partir d’une adresse IP V4 et d’un masque de sous-réseau.

Voici un exemple de résultat attendu :

>>> prefixe_reseau('145.245.11.254','255.255.252.0')
'145.245.8.0'
>>> suffixe_machine('145.245.11.254','255.255.252.0')
'0.0.3.254'

Propriété 4

Python définit également des opérateurs sur les bits d’un nombre, plus efficaces que les opérations mathématiques équivalentes :

Exercice 14

Dans l’algorithme de recherche dichotomique, après division en deux de la zone de recherche, l’algorithme s’appelle lui-même sur l’une des deux moitiés. C’est un algorithme de type Diviser pour régner qui peut se programmer récursivement comme nous le verrons en terminale dans le chapitre sur la récursivité.

Si on note n la taille de la liste, une autre implémentation, non récursive, est la suivante :

A la fin de de la boucle, on détermine si l’élément précédent le dernier point d’arrêt est l’élément recherché.

Compléter le code de la fonction recherche_dicho2 qui implémente cet algorithme.

def recherche_dicho2(L, e):
    x, n  = 0, len(L)
    pas = n >> 1
    while pas >= 1:
        while x + pas < n and .................:
            x = ..............
        pas = ................
    return ............