Tables de vérité

Identification

Infoforall

2 - Tables de verité


Nous avons vu comment l'ordinateur avait été concu et pensé au fil du temps.

Nous avons vu qu'il comporte plusieurs parties indépendantes mais communicantes :

  • Le processeur qui contient
    • Unité de Contrôle (UdC) qui gère les instructions basiques
    • Unité Arithmétique et Logique (UAL) qui gère les calculs
    • des registres : de très petites mémoires mais très rapides d'accès
  • Une mémoire centrale

Nous allons aujourd'hui nous pencher sur la délicate question de l'action de l'UAL. Comment réaliser des tests ET, OU, des additions ... Cela nous permettra de comprendre ce qui est une action basique et simple pour un ordinateur et ce qui ne l'est pas.

Nous allons notamment parler des XOR ;

Les XOr : le bleu, le rouge et le gris

Evaluation ✎ :

Documents de cours : open document ou pdf

1 - Un peu d'électricité

L'informatique est basée de nos jours sur l'électricité et plus particulièrement l'électronique.

L'un des composants matériels de base des ordinateurs est le transistor. On le trouve dans toutes les parties de ces machines.

Survolons donc rapidement les notions que vous devriez connaître, à défaut de vraiment maitriser.

1.1 - courant électrique

Un courant électrique est dû à un mouvement global d'électrons. En gros les électrons se dirigent massivement dans la même direction. C'est l'analogie du courant d'eau où les molécules d'eau se dirigent globalement dans la même direction.

1.2 - Intensité électrique I(A)

On caractérise l'importance d'un courant électrique par une grandeur algébrique

  • qu'on nomme intensité électrique
  • qu'on représente par la lettre I
  • qu'on mesure en Ampère

Pour information, 1 A correspond au transport de plus de 6 milliards de milliards d'électrons en une seconde. Plus facile de mesurer ça en Ampère non ?

1.3 - Tension électrique U(V)

Un courant électrique est constitué d'électrons. Encore faut-il leur donner envie de bouger !

C'est là qu'intervient la tension électrique entre deux points, A et B par exemple. Plus la tension électrique entre deux points est grande, plus les électrons auront tendance à se déplacer.

C'est d'ailleurs la raison physique de l'existence des éclairs lors des orages : la tension électrique entre les deux zones devient tellement grande que les électrons parviennent à se déplacer alors que l'air est normalement un isolant électrique ! Il faut dire qu'on atteint plusieurs millions de Volt.

Animation montrant un éclair qui décharge le surplus d'électrons
Eclair, animation du domaine public

Une fois les électrons déplacés, la tension repasse sous le seuil où l'air est isolant. C'est fini, jusqu'à la recharge progressive et l'arrivée du prochain éclair.

On peut donc voir la tension électrique entre deux points A et B comme une mesure de la différence de charges électriques entre le point A et le point B.

On définit pour cela la tension électrique UAB = VA - VBVA désigne le potentiel électrique du point A.

Tensions et potentiels se mesurent en VOLT.

On peut voir le potentiel électrique VA comme une mesure des charges électriques présentes au point A.

Ainsi une batterie possède bien

  • une borne + (on y trouve plus de charges électriques positives que de charges négatives) et
  • une borne - (on y trouve plus de charges électriques négatives que positives).
Symbole d'une pile
Symbole d'une pile tiré de physique-chimie-college.fr

SI on permet aux électrons de se déplacer en plaçant un conducteur entre les deux, l'intensité électrique sera d'autant plus forte que la tension électrique est forte.

Pour information : tensions limites de danger

Le danger pour un être humain est bien la différence de tension entre deux points (main - pied par exemple).

Avec un système générant une tension continue

  • Milieu mouillé : sans danger si U < 30 V
  • Milieu humide : sans danger si U < 60 V
  • Milieu sec : sans danger si U < 120 V

Avec un système générant une tension alternative

  • Milieu mouillé : sans danger si U < 12 V
  • Milieu humide : sans danger si U < 25 V
  • Milieu sec : sans danger si U < 50 V (définition de la Très Basse Tension)
1.4 - Résistance électrique R(Ω)

Un conducteur dit ohmique possède une caractéristique : il s'oppose au courant électrique sans être isolant.

On caractérise cette opposition au passage du courant continu par une grandeur algébrique

  • qu'on nomme résistance électrique
  • qu'on représente par la lettre R
  • qu'on mesure en Ohm (Ω)

Sur un tel conducteur, on peut utiliser la loi d'Ohm : $$U = R.I$$.

On peut déduire de la loi d'Ohm que pour une source de tension U constante, on a : $$I = \frac{U}{R}$$.

Cela veut donc dire que plus la résistance électrique est grande, plus l'intensité électrique est petite. Logique.

01° Calculer la tension nécessaire pour établir une intensité de 0,002 A à travers un résistor de 2000 Ω.

...CORRECTION...

U = R . I = 2000 * 0.002

U = 4 V

02° Calculer l'intensité obtenue pour une tension continue de 5V et une résistance de 40 Ω.

...CORRECTION...

U = R . I

U / R = I

I = 5 / 40

I = 0.125 A

2 - Transistor

Aucune connaissance n'est exigible sur les transistors en NSI. Toute cette partie n'est qu'un ensemble de connaissances de culture générale.

Le transitor est le composant électronique principal de tout ordinateur, que ce soit dans le processeur ou dans la mémoire.

2.1 - Description du transistor

On peut voir le transistor comme un interrupteur dans le cadre d'informatique. Mais un interrupteur commandé par une action électrique plutôt que mécanique.

Image montrant plusieurs types de transistors
Des transistors, Par ArnoldReinhold — Travail personnel, CC BY-SA 3.0,

Voyez le transistor comme un composant possédant 3 bornes :

  • une borne (à gauche) qui sert de commande. Selon la technologie du transistor, on doit y imposer un courant ou une tension.
  • deux autres bornes qui servent d' "interrupteur".
2.2 - Montage du transistor avec une entrée à 5V

La borne de gauche est placée à 5V :

  • le transistor est équivalent à un interrupteur fermé.
  • 0V en sortie puisque la sortie est alors directement reliée à la masse (en bas) par un fil conducteur.
5V True 0V False 0V False 5V True Vcc = 5V 0V
2.3 - Montage du transistor avec une entrée à 0V

La borne d'entrée (à gauche) est placée à 0V :

  • le transistor est équivalent à un interrupteur ouvert.
  • pas de courant dans le résistor du haut puisque le courant ne peut s'évacuer vers la masse. On a donc I = 0A dans le résistor
  • Puisque U = R.I, il y a U = 0V aux bornes du résistor qui se comporte donc comme un simple fil conducteur
  • la borne 5V est donc reliée à la sortie par un simple fil : 5V en sortie !

Bon, et c'est quoi le rapport avec l'informatique ?

2.4 - Porte logique NOT

Voici comme on gère les 0 et les 1 dans un ordinateur :

L'état HAUT (ou 1 ou True en Python) est encodé physiquement par une tension différente de 0V, soit 5V ici.
Techniquement, on prend plus large : toute tension supérieure à 2.5 V.

L'état BAS (ou 0 ou False en Python) est encodé physiquement par une tension de 0V.
Techniquement, on prend plus large : toute tension inférieure à 2.5 V.

Etat Nombre Python Tension
HAUT différent de 0 True U > 2.5 V (5V)
BAS égal à 0 False U < 2.5 V (0V)

Si on reprend les deux possibilités précédentes mais en plaçant les états True et False, on obtient ceci :

Nous venons de créer l'équivalent d'un NOT / NON.

C'est comme cela que l'UAL parvient à exécuter électroniquement un not de Python :

>>> a = 12 >>> a > 5 True >>> not(a > 5) False
CONCLUSION

Aujourd'hui, les transistors sont de tailles microscopiques. C'est en réduisant leurs tailles qu'on augmente leur nombre et donc la vitesse de calcul des ordinateurs.

Nous atteignons aujourd'hui la taille des atomes. Il va donc falloir trouver des nouvelles façons d'augmenter cette vitesse si on veut continuer à ne pas faire mentir la loi de Moore .

Graphique (en ordonnées logarithmiques) illustrant la loi de Moore par rapport à l'évolution réelle du nombre de transistors dans les microprocesseurs Intel; en pointillés verts au-dessus, représentation de l'hypothèse selon laquelle ce nombre doublerait tous les 18 mois :

Courbe montrant l'évolution du nombre de transisors dans un ordinateur au fil du temps
Loi de Moore, The original uploader was QcRef87 at French Wikipedia, CC BY-SA 3.0,

La réduction de la taille des transistors impose des usines de plus en plus chères. Pour les plus petits modèles, on peut monter à plus de 3 milliards. Ceci explique aussi pourquoi la plupart des constructeurs Européens ont jeté l'éponge. Ces usines ne se trouvent quasiment plus qu'en Asie.

Cela renforce bien entendu la dépendance de nos pays à ces quelques et rares usines.

Aujourd'hui, la loi empirique de Moore tend à ne plus être suivi car les transistors atteignent la taille de quelques atomes.

On commence donc à créer des microprocesseurs en 3D plutôt qu'en 2D. Mais cela provoque des problèmes d'évacuation de la chaleur. Cela devient vraiment compliqué de continuer à augmenter les capacités de calculs.

3 - Table de vérité du NON

3.1 - Table de vérité du NON

On peut donner les valeurs possibles en prenant les valeurs booléennes VRAI et FAUX.

On considère une valeur booléenne d'entrée notée a.

On considère une valeur booléenne de sortie notée s.

Voici la table de vérité du NON :

Entrée a Sortie s
VRAI FAUX
FAUX VRAI
3.2 - Créer électroniquement un NON

Nous avons vu que l'une des possibilités était de simplement utiliser un transistor associé à un résistor.

3.3 - NON dans un schéma électrique

a b s a s ET & OU ≥1 & ≥1 =1 1

Symbole dans un schéma :

Le symbole est simple : on note 1 à l'intérieur de la boîte qui ne possède qu'une entrée unique a. Pour indiquer qu'on inverse la sortie par rapport au OUI, on rajoute un rond ou une barre oblique sur la sortie.

On trouve également le symbole suivant qui correspond à la norme ANSI américaine ::

Schéma du NON ANSI : un TRIANGLE avec un point au bout
NON ANSI, image dans le domaine public, réalisée par jjbeard, récupérée sur Wikipedia
3.4 - NON dans l'algèbre de Bool (équation mathématique avec 1 et 0)

Mathématiquement, cela revient à écrire : \(s = \bar a\).

A quoi correspond la barre supérieure ? Elle indique qu'il faut inverser ( ou complémenter ) a.

On dit d'ailleurs que \(\bar a\) est le complément de \(a\) car \(\bar a + a\) donne nécessairement 1.

Entrée a Sortie s \(\bar a\)
1 0 1 donne 0
0 1 0 donne 1

Suivant la façon dont une documentation est réalisée, il est parfois difficile de placer le trait supérieur. On trouve donc d'autres manières d'indiquer la complémentarité.

La complémentarité de a peut donc se noter

  • \(\bar a\)
  • \(a/\)
  • \(\neg a\)

On notera aussi que NON(NON(a)) redonne simplement a :

  • \(\bar {\bar a} = a\)
  • \(\neg {\neg a} = a\)

D'ailleurs, sachez que ce dernier caractère ¬ possède une valeur UNICODE 172 (en base 10). On peut donc l'afficher en HTML en utilisant &#172; mais il possède également un code raccourci : &not;. Vous voyez le rapprochement ?

3.5 - NON dans Python

Il suffit d'utiliser le mot-clé not.

Le NON est donc facile à réaliser avec un transistor et est assez facile à comprendre.

Mais une table de vérité est plus visuelle.

Entrée a \(\bar a\) ou \(\neg a\)
1 0
0 0

4 - NON-ET ou NAND

Passons au second circuit très facilement réalisable : le NON-ET en français. NAND en anglais.

Sa réponse ? L'inverse du ET.

4.1 - NAND en Python

Le NAND n'existe pas naturellement en Python. Mais on peut le créer via une fonction comme celle-ci :

1 2
def nand(a,b): return not(a and b)

03° Compléter la table de vérité du NON-ET :

Valeur de a Valeur de b a ET b NON(a ET b) qu'on peut écrire a NAND b
VRAI VRAI VRAI FAUX
FAUX VRAI ? ?
VRAI FAUX ? ?
FAUX FAUX ? ?
4.2 - Table de vérité du NAND

Valeur de a Valeur de b a ET b NON(a ET b) qu'on peut écrire a NAND b
VRAI VRAI VRAI FAUX
FAUX VRAI FAUX VRAI
VRAI FAUX FAUX VRAI
FAUX FAUX FAUX VRAI
4.3 - Créer électroniquement un NAND

Pourquoi parler du NON-ET alors que nous n'avons pas encore vu la table du ET tout court !

Simplement car il est très facile de réaliser un NAND à partir de deux transisors en série :

Le cas avec les deux entrées à VRAI :

Le cas avec une seule entrée à VRAI :

4.4 - NAND dans un schéma électrique

Pour information : Symbole dans un schéma logique

On symbolise le NON-ET comme une porte logique ET en rajoutant le cercle symbolisant qu'on complémente (inverse) l'état de sortie.

On trouve également le symbole suivant qui correspond à la norme ANSI américaine :

Schéma du NAND ANSI : un AND avec un point au bout
NAND ANSI, image dans le domaine public, réalisée par jjbeard, récupérée sur Wikipedia
4.5 - NAND dans l'algèbre de Bool (équation mathématique avec 1 et 0)

Le NON-ET est l'inverse du ET. Son complément. Si on sait écrire mathématiquement un ET logique, on sait donc écrire un NON-ET.

D'un point de vue logique 0 et 1, le ET peut s'écrire à l'aide d'une multiplication : \(a.b\)

Il n'y a que dans le cas où \(a=1\) ET \(b=1\) qu'on peut avoir \(a.b = 1.1 = 1\).
Dans tous les autres cas, c'est 0.

Le NAND est le complément du AND : \(\overline{a.b}\)

Valeur de a Valeur de b \(\overline{a.b}\)
VRAI VRAI FAUX
FAUX VRAI VRAI
VRAI FAUX VRAI
FAUX FAUX VRAI

Pourquoi étudier le NAND avant le AND ?

Tout simplement car avec un ensemble de circuit NAND on peut réaliser toutes les autres fonctions logiques.

En logique, cette propriété s'appelle la complétude fonctionelle.

On pourrait ainsi créer des UAL uniquement à l'aide de portes NAND reliées les unes ou autres pour réaliser des NAND, des AND, des OR ...

Exemple avec le NOT qu'on peut construire ainsi : on relie les deux entrées d'une NAND

a a a s

On remarquera d'abord qu'en logique a . a = a

Pourquoi ?

Démonstration simple comme il n'y a que deux cas :

VRAI ET VRAI donne VRAI : a = 1 alors a.a = 1.1 = 1.

FAUX ET FAUX donne FAUX : a = 0 alors a.a = 0.0 = 0

Donc, on a bien s = a.a = a

5 - ET AND

Nous avons déjà rencontré le ET lors des activités Python. D'ailleurs, vous avez dû l'utiliser pour comprendre le NON-ET du coup.

04° Compléter la table de vérité du ET :

Valeur de a Valeur de b a ET b
VRAI VRAI ?
FAUX VRAI ?
VRAI FAUX ?
FAUX FAUX ?

Cela revient à chercher cela avec Python :

a and b

Cela revient à chercher cela avec Javascript, C, C++ :

a && b

...CORRECTION...

Valeur de a Valeur de b a ET b
VRAI VRAI VRAI
FAUX VRAI FAUX
VRAI FAUX FAUX
FAUX FAUX FAUX

05° Compléter la table de vérité du ET avec 3 entrées :

Valeur de a Valeur de b Valeur de c a ET b ET c
VRAI VRAI VRAI ?
FAUX VRAI VRAI ?
VRAI FAUX VRAI ?
FAUX FAUX VRAI ?
VRAI VRAI FAUX ?
FAUX VRAI FAUX ?
VRAI FAUX FAUX ?
FAUX FAUX FAUX ?

Cela revient à chercher cela avec Python :

a and b and c

Cela revient à chercher cela avec Javascript, C, C++ :

a && b && c

...CORRECTION...

Valeur de a Valeur de b Valeur de c a ET b ET c
VRAI VRAI VRAI VRAI
FAUX VRAI VRAI FAUX
VRAI FAUX VRAI FAUX
FAUX FAUX VRAI FAUX
VRAI VRAI FAUX FAUX
FAUX VRAI FAUX FAUX
VRAI FAUX FAUX FAUX
FAUX FAUX FAUX FAUX
Evaluation paresseuse

Dans certains langages de programmation, dont Python, on dit que l'évaluation des expressions logiques est paresseuse.

Qu'est-ce que cela veut-dire pour un ET ?

Simplement qu'on évalue l'expression de gauche à droite.

Dès qu'on rencontre un terme qui est FAUX, on arrête d'évaluer : la réponse est nécessairement FAUX !

Sur l'exemple du ET à 3 entrées, on aurait ceci :

Valeur de a Valeur de b Valeur de c a ET b ET c
VRAI VRAI VRAI VRAI
VRAI VRAI FAUX FAUX
VRAI FAUX Peu importe FAUX
VRAI FAUX Peu importe FAUX
FAUX Peu importe Peu importe FAUX
FAUX Peu importe Peu importe FAUX
FAUX Peu importe Peu importe FAUX
FAUX Peu importe Peu importe FAUX

CONCLUSION : l'ordre dans lequel on évalue les choses peut rendre l'évaluation d'un ET long ou rapide ! Provoquer une erreur ou pas.

06° On veut évaluer si la case d'indice 5 d'un tableau est supérieure à 10 en Python , sans être certain que le tableau possède bien 6 cases. Quelle proposition est adaptée :

  1. (len(t) >= 6) AND (t[5] > 10)
  2. (t[5] > 10) AND (len(t) >= 6)

...CORRECTION...

Clairement la réponse A.

Si on applique A et que la longueur n'est pas de 6 au moins, on n'évalue que la première partie. Comme elle est False, on ne regarde même pas la suite. Et donc on ne provoque pas d'erreur.

Avec la B, on provoquerait immédiatement une erreur si on tentait de lire l'indice 6 d'un tableau qui ne possède pas d'indice 6.

Equation mathématique

D'un point de vue logique 0 et 1, le ET peut s'écrire ainsi : a . b

Valeur de a Valeur de b a . b
1 1 1
0 1 0
1 0 0
0 0 0

07° Comment peut-on représenter a ET b ET c avec une équation logique ?

...CORRECTION...

s = a . b . c

Pour information : Symbole dans un schéma logique

On symbolise le ET comme un carré avec un &, sans le cercle en sortie !

On trouve également le symbole suivant qui correspond à la norme ANSI américaine :

Schéma du AND ANSI : un AND
AND ANSI, image dans le domaine public, réalisée par jjbeard, récupérée sur Wikipedia

Propriété : associativité

On notera qu'on peut vérifier facilement la propriété d'associativité du ET : on peut calculer s = a . b . c comme on le veut.

s = a . b . c = (a . b) . c = a . (b . c)

  • En commençant par a ET b : ( a . b ) . ( c )
  • a b a . b c a . b . c
  • En commençant par b ET c : ( a ) . ( b . c )
  • b c b . c a a . b . c
Commutativité

On notera d'ailleurs qu'on peut vérifier facilement la commutativité du ET.

Il s'agit de la propriété qui précise que a ET b est identique à b ET a.

a b a . b b a b . a

Mathématiquement, cela donne s = a . b = b . a

Un cas pratique avec un programme Python qui doit vérifier qu'une note est bien supérieure ou égale à 0 ET inférieure ou égale à 20 :

>>> note = 14

>>> a = note >= 0

>>> b = note <= 20

>>> print (a and b)

True

>>> print(b and a)

True

Attention néanmoins à la notion d'expression paresseuse : on peut commuter, ça ne change rien mathématiquement. Par contre, cela peut permettre de ne faire certains calculs que si la première condition est bien satisfaite !

6 - OU OR

Nous avons déjà rencontré le OU lors des activités Python.

08° Compléter la table de vérité du OU :

Valeur de a Valeur de b a OU b
VRAI VRAI ?
FAUX VRAI ?
VRAI FAUX ?
FAUX FAUX ?

Cela revient à chercher cela avec Python :

a or b

Cela revient à chercher cela avec Javascript, C, C++ :

a || b

...CORRECTION...

Valeur de a Valeur de b a OU b
VRAI VRAI VRAI
FAUX VRAI VRAI
VRAI FAUX VRAI
FAUX FAUX FAUX

09° Compléter la table de vérité du OU avec 3 entrées :

Valeur de a Valeur de b Valeur de c a OU b OU c
VRAI VRAI VRAI ?
FAUX VRAI VRAI ?
VRAI FAUX VRAI ?
FAUX FAUX VRAI ?
VRAI VRAI FAUX ?
FAUX VRAI FAUX ?
VRAI FAUX FAUX ?
FAUX FAUX FAUX ?

Cela revient à chercher cela avec Python :

a or b or c

Cela revient à chercher cela avec Javascript, C, C++ :

a || b || c

...CORRECTION...

Valeur de a Valeur de b Valeur de c a OU b OU c
VRAI VRAI VRAI VRAI
FAUX VRAI VRAI VRAI
VRAI FAUX VRAI VRAI
FAUX FAUX VRAI VRAI
VRAI VRAI FAUX VRAI
FAUX VRAI FAUX VRAI
VRAI FAUX FAUX VRAI
FAUX FAUX FAUX FAUX
Evaluation paresseuse

Qu'est-ce que cela veut-dire pour un OU ? dans Python ?

Simplement qu'on évalue l'expression de gauche à droite.

Dès qu'on rencontre un terme qui est VRAI, on arrête d'évaluer : la réponse est nécessairement VRAI !

CONCLUSION : l'ordre dans lequel on évalue les choses peut rendre l'évaluation d'un OU long ou rapide ! Provoquer une erreur ou pas.

10° On veut évaluer a OR b.

La variable a à 80% d'être True et b à 10% d'être True. Vaut-il mieux utiliser a OR b ou b OR a ?

Equation mathématique

D'un point de vue logique 0 et 1, le OU peut s'écrire ainsi : a + b

Valeur de a Valeur de b a + b
1 1 1 (VRAI ou VRAI donne VRAI, pas 2 !)
0 1 1
1 0 1
0 0 0

11° Comment peut-on représenter a OU b OU c avec une équation logique ?

...CORRECTION...

s = a + b + c

Pour information : Symbole dans un schéma logique

On symbolise le OU comme un carré avec >=1 sans le cercle en sortie !

Pourquoi >=1 : (VRAI ou VRAI donne VRAI, pas 2 !). Attention, ce n'est pas une addition binaire mais une représentation mathématique de la logique VRAI / FAUX. En réalité, on peut considérer que tout ce qui n'est pas 0 est donc VRAI !

On trouve également le symbole suivant qui correspond à la norme ANSI américaine :

Schéma du OR ANSI : un OR
OR ANSI, image dans le domaine public, réalisée par jjbeard, récupérée sur Wikipedia

Propriété : associativité

On notera qu'on peut vérifier facilement la propriété d'associativité du OU : on peut calculer s = a + b + c

  • En commençant par a OU b : ( a + b ) + ( c )
  • a b a + b c a + b + c
  • En commençant par b OU c : ( a ) + ( b + c )
  • b c b + c a a + b + c

Propriété : commutativité

On notera d'ailleurs qu'on peut vérifier facilement la commutativité du OU.

Il s'agit de la propriété qui précise que a OU b est identique à b OU a.

a b a + b b a b + a

Mathématiquement, cela donne s = a + b = b + a

J'ai un peu menti. Ce n'est pas la première fois ! Ni la dernière...

Bref, les XOR et les additions, c'est pour la fois prochaine. Pour les plus rapides, nous verrons également comment réaliser un OR, un AND ou un XOR avec des NAND.

Activité publiée le 01 03 2020
Dernière modification : 01 03 2020
Auteur : ows. h.