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.

L'électricité en quelques lignes : 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.

L'électricité en quelques lignes : 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 ?

L'électricité en quelques lignes : 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

Du coup, 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)
L'électricité en quelques lignes : 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 = 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

Voilà le composant principal de tout ordinateur, que ce soit dans le processeur ou dans la mémoire.

En première approximation, on peut voir le transistor comme un interrupteur. Mais pas un interrupteur commandé par une action mécanique. Non, un interrupteur commandé par une action électrique.

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".

Première possibilité : une commande de 5V (à gauche) :

  • le transistor est équivalent à un interrupteur fermé.
  • on récupère 0V en sortie puisque le point de sortie est directement relié à la masse (en bas, le point qu'on prend comme référence du 0V).
5V True 0V False 0V False 5V True Vcc = 5V 0V

Deuxième possibilité : une commande de 0V (à gauche) :

  • le transistor est équivalent à un interrupteur ouvert.
  • pas de courant dans le résistor du haut : I = 0
  • du coup, tension U de 0V aux bornes du résistor U = R.I = R.0 = 0 : il se comporte comme un simple fil conducteur
  • on récupère 5V en sortie !

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

Et bien, nous venons de créer un NOT ou NON en français.

Première chose à comprendre, le 1 n'est qu'une façon de décrire l'état HAUT. On prendra par exemple toute tension supérieure à 2,5 V pour l'état HAUT.

Deuxième chose : le 0 décrit simplement l'autre état : l'état BAS. Ou 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)

Nous venons donc de voir comment l'ordinateur parvient à exécuter un not logique, comme dans Python :

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

Du coup, si on reprend les deux possibilités de commandes mais en plaçant les états 0 et 1, on obtient ceci :

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 Chine.

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

3 - Table de vérité du NON

Table de vérité avec True et False

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
Equation mathématique avec 1 et 0

Mathématiquement, cela revient à écrire : s = a.

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

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

Entrée a Sortie s 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 a ou a/ ou encore ¬a

On notera aussi que NON(NON(a)) redonne simplement 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 ?

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

Dernière chose : le symbole d'un NON dans un shéma :

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

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 Sortie s a ou ¬a
1 0 1 donne 0
0 1 0 donne 1

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 ! En Python, une fonction NAND maison, ça pourrait petre ceci :

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)
VRAI VRAI VRAI FAUX
FAUX VRAI ? ?
VRAI FAUX ? ?
FAUX FAUX ? ?

...CORRECTION...

Valeur de a Valeur de b a ET b NON(a ET b)
VRAI VRAI VRAI FAUX
FAUX VRAI FAUX VRAI
VRAI FAUX FAUX VRAI
FAUX FAUX FAUX VRAI

Et 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 NON-ET (NAND en anglais) à partir de deux transisors :

Le cas avec les deux entrées à VRAI :

La sortie est donc à 0V puisqu'on relie la masse et la sortie avec un fil conducteur.

Le cas avec une seule entrée à VRAI :

On rappelle qu'on remplace ici le résistor par un fil car U = R.I : aucun courant ne passe donc I = 0 donc U = 0 aux bornes du résistor. C'est comme un fil.

La sortie est donc à 5V puisqu'on relie la sortie au 5V par un fil.

Table de vérité de NAND / NON-ET
Valeur de a Valeur de b a AND b a NAND b
VRAI VRAI VRAI FAUX
FAUX VRAI FAUX VRAI
VRAI FAUX FAUX VRAI
FAUX FAUX FAUX VRAI
Equation mathématique

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 ainsi : a . b

En effet, 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.

Du coup; le NAND est le complément de cela : a . b

Valeur de a Valeur de b a . b
VRAI VRAI FAUX
FAUX VRAI VRAI
VRAI FAUX VRAI
FAUX FAUX VRAI

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

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.

Les UAL sont des circuits composés en majorité 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 a AND b.

La variable a à 70% d'être False et b à 30% d'être False. Vaut-il mieux utiliser a AND b ou b AND a ?

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 changer le temps d'évaluation de l'expression !

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 à 70% d'être False et b à 30% d'être False. 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.