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 ;
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.
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 - VB où VA 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).
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.
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.
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
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
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 ::
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 ¬ mais il possède également un code raccourci : ¬. Vous voyez le rapprochement ?
3.5 - NON dans Python
Il suffit d'utiliser le mot-clé not.
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 :
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 |
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 bCela 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 cCela 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 :
- (len(t) >= 6) AND (t[5] > 10)
- (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 :
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 )
- En commençant par b ET c : ( a ) . ( b . c )
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.
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 bCela 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 cCela 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 :
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 )
- En commençant par b OU c : ( 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.
Mathématiquement, cela donne s = a + b = b + a
Activité publiée le 01 03 2020
Dernière modification : 01 03 2020
Auteur : ows. h.