Aller au contenu

Valeurs booléennes1⚓︎

1. 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é.

img

2. Portes logiques⚓︎

2.1 Le transistor porte logique de base⚓︎

Transistor

Un transistor est un composant électronique possèdant 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).

transistor

Fonction logique

Une fonction logique prend un ou plusieurs bits en entrée et retourne un ou plusieurs bits en sortie.

Porte logique

Une porte logique est un circuit électronique représentant une fonction logique.

Transistor / Fonction logique / Table logique

Un transistor est une porte logique implémentant la fonction de NON logique ou Inverseur.

A (entrée) B = NON(A) (sortie)
0 1
1 0

transistor

2.2 D’autres portes logiques: Transistors en série ou en parallèle⚓︎

Deux portes importantes

C'est en combinant les transistors qu'on peut implémenter d'autres portes importantes :

  • La porte AND constituée de deux transistors en série
  • La porte OR constituée de deux transistors en parallèle

3. Fonctions booléennes⚓︎

3.1 Fonctions booléennes⚓︎

Définitions

  • Un booléen est un type de données pouvant prendre deux valeurs True (Vrai) ou False (Faux) qu'on représente numériquement par un bit de valeur \(1\) pour True ou \(0\) pour False. Electroniquement, les valeurs 1 et 0 se traduisent respectivement par des tensions haute ou basse.
  • Une fonction booléenne \(f\) associe un booléen à un ou plusieurs booléens.
  • Une porte logique est la représentation sous forme de circuit d'une fonction booléenne et sa table logique est la table de vérité de cette fonction.

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

3 fonctions booléennes à connaitre

  • La négation de \(x\) est une fonction à 1 bit d'entrée (unaire) notée \(\neg x\) ou \(\overline{x}\) Si x est un booléen, sa négation est not x en Python.
\(x\) \(\overline{x}\)
0 1
1 0
  • La conjonction de \(x\) et \(y\) est une fonction à 2 bits d'entrée (binaire) notée \(x \wedge y\) ou \(x . y\) Si x et y sont des booléens, leur conjonction est x and y en Python.
\(x\) \(y\) \(x.y\)
0 0 0
0 1 0
1 0 0
1 1 1
  • La disconjonction de \(x\) et \(y\) est une fonction à 2 bits d'entrée (binaire) notée \(x \vee y\) ou \(x + y\) Si x et y sont des booléens, leur disjonction est x or y en Python.
\(x\) \(y\) \(x+y\)
0 0 0
0 1 1
1 0 1
1 1 1

Propriétés des fonctions booléennes

  1. Les fonctions booléennes élémentaires respectent un certain nombre de règles qui permettent de simplifier les expressions booléennes complexes :
  • opérateur involutif : \(\overline{\overline{x}}=x\)
  • élément neutre : \(1 . x =x\) ou \(0 + x =x\)
  • élément absorbant : \(0 . x =0\) ou \(1 + x =1\)
  • idempotence : \(x . x =x\) ou \(x + x =x\)
  • complément : \(x . (\overline{x}) =0\) ou \(x + \overline{x} =1\)
  • commutativité : \(x . y = y . x\) ou \(x + y = y + x\)
  • associativité : \(x . (y . z) = (x . y) . z\) ou \(x + (y + z) = (x + y) + z\)
  • distributivité : \(x . (y + z) = x . y + x . z\) ou \(x + (y . z) = (x + y) . (x + z)\)
  • loi de Morgan : \(\overline{x . y} = \overline{x} + \overline{y}\) ou \(\overline{x + y} = \overline{x} . \overline{y}\)
  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.

Parenthèses

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.

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

Pour prouver une égalité de deux expressions booléennes

Pour démontrer l'égalité d'expressions booléennes, on utilise les deux méthodes suivantes :

  • Méthode 1 : en comparant les tables de vérité des deux expressions booléennes ;
  • Méthode 2 : en utilisant les règles de simplification de la propriété 1. (hors programme)

Exemple

Démontrer que \(x + \overline{x} . y= x + y\)

Résolution (avec la méthode 1)

\(x\) \(y\) \(\overline{x}\) \(\overline{x}.y\) \(x+\overline{x}.y\) \(x+y\)
0 0 1 0 0 0
0 1 1 1 1 1
1 0 0 0 1 1
1 1 0 0 1 1

Les deux colonnes de droite sont bien identiques: ceci montre l'égalité \(x + \overline{x} . y= x + y\)

  1. Cours tiré très largement du manuel NSI 1re Spécialité - Ed. 2021 Hachette et de https://frederic-junier.gitlab.io/parc-nsi ↩