ISN Opérations booléennes

Les opérations booléennes

Savoirs :	Présentation des opérations booléennes de base (et, ou, non, ou-exclusif).
Capacités :	Exprimer des opérations logiques simples par combinaison d'opérateurs de base.
Observation :	On découvre les opérations logiques de base à l'aide d'exercices simples et on met en évidence ces opérations dans les mécanismes de recherche. En parallèle avec les séances d'algorithmique, on peut expliquer le principe d'addition de deux octets.

Logique à deux états

On appelle « logique à deux états », ou logique booléenne, un système d'opérations qu'on peut faire sur des objets qui ne peuvent prendre que deux valeurs, appelées faux/vrai ou 0/1.

Schéma de brochage du compteur asynchrone décimal TTL 7490.

Les circuits logiques à deux états sont nombreux dans un ordinateur, il en existe plusieurs normes. Par exemple, selon le standard TTL, la valeur 0 est définie par un tension électrique comprise entre 0 et 0,5 V, la valeur 1 est définie par une tension comprise entre 2,4 et 5 V. On arrive à garantir que ces valeurs de tensions soient respectées en concevant correctement les montages logiques :

• en contrôlant le courant maximal demandé à chaque porte logique ;
• en utilisant une horloge pour déterminer à quel moment les valeurs logiques sont bien établies.

Circuits logiques CMOS

Le standard CMOS est plus récent que le standard TTL. Il est basé sur l'utilisation de transistors Complémentaires utilisant une technologie Metal-Oxyde-Semiconducteur (d'ou l'acronyme CMOS).

Coupe schématique d'un transistor à effet de champ MOS à canal dopé N.

Un transistor MOS peut être considéré comme un petit barreau de semi-conducteur (en silicium dopé), avec deux extrémités nommées drain (D) et source (S), dont la conductivité électrique est contrôlée par une électrode nommée la porte ou la grille (G) : cette électrode métallique est placée très près du barreau, elle n'en est séparée que par film isolant en oxyde de silicium très fin (quelques nm).

Pour le standard CMOS, la valeur FAUSSE (0) est définie par une tension comprise entre 0 V et la moitié de la tension d'alimentation, la valeur VRAIE (1) est définie par une tension coprise entre la 0,5 fois et une fois la tension d'alimentation. La tension d'alimentation peut varier entre 3 et 18 V, ce qui facilite l'emploi de ces circuits électroniques dans divers montages.

Autres circuits logiques

Il existe d'autres circuits logiques que les circuits logiques à deux états, par exemple des circuits dont la sortie peut être « fausse », « vraie » ou en haute impédance (ils se comporte alors comme s'ils étaient débranchés du circuit).

Opération booléenne NON

L'opération NON est ue opération unaire, c'est à dire à un seul opérande.

(NON a) est VRAI si A est FAUX; (NON a) est FAUX si a est VRAI.

(NON a) se note ${\overline {a}}$

Table de vérité du NON

$a$	${\overline {a}}$
0	1
1	0

Réalisation d'une porte NON avec un transistor MOS à effet de champ

Le barreau semi-conducteur entre drain et source peut changer de conductivité électrique :

• quand la tension électrique entre grille et source $U_{GS}$ est faible (valeur logique 0 ou FAUX), le "barreau" entre drain et source est isolant, on peut le considérer comme non existant dans le circuit électrique ;
• quand la tension électrique entre grille et source $U_{GS}$ est importante (valeur logique 1 ou VRAI), le "barreau" entre drain et source est conducteur, on peut le considérer comme un fil électrique.

Il est donc possible de réaliser un simple porte NON à l'aide d'un transistor et d'une résistance électrique. Voici un schéma qui montre comment, avec un signal logique 0 à l'entrée d'un tel montage, on obtient en sortie un signal de valeur logique 1 :

la tension $U_{GS}$ est nulle, le transistor est isolant	tout se passe comme si le transistor n'était pas là, la sortie est reliée au pôle positif à travers la résistance

Le schéma suivant montre qu'avec un signal logique 1 à l'entrée du montage, on obtient en sortie un signal de valeur logique 0 :

la tension $U_{GS}$ est égale à $U_{DS}$, le transistor est conducteur	on peut le remplacer par un fil électrique, la résistance n'intervient plus

Remarque : dans les circuits logiques CMOS, la résistance est remplacée par un autre transistor MOS dont le comportement est complémentaire : ça symétrise mieux le comportement des portes logiques.

Opération booléenne OU

le résultat de (a OU b) est VRAI si et seulement si plus d'une valeur boolénnes a et b sont VRAIES (une seule VRAIE, ou les deux VRAIES en même temps).

(a OU b) se note : $a\lor b$

Table de vérité du OU

$a$	$b$	$a\lor b$
0	0	0
0	1	1
1	0	1
1	1	1

Réalisation d'une porte OU avec des transistors MOS

Le circuit ci-dessus fabrique à partir des signaux d'entrée $a$ et $b$ un signal intermédiaire $c$ (à l'intérieur du circuit), puis un signal de sortie $d$, par action d'un transistor monté en porte NON.

On peut montrer que $c={\mbox{NON}}(a\ {\mbox{OU}}\ b)$, ou, noté autrement, $c={\overline {a\lor b}}$. Comme $d$ est la négation de $c$ et que la double négation revient à une copie en logique binaire, $d={\overline {c}}={\overline {\overline {a\lor b}}}=a\lor b$.

Exercice : dessiner le schéma d'une porte "OU NON", réalisée à l'aide de transistors MOS canal N et de résistances. La table de vérité du "OU NON" est la suivante :

$a$	$b$	$a\ {\mbox{OU NON}}\ b$
0	0	1
0	1	0
1	0	0
1	1	0

Opération booléenne ET

le résultat de (a ET b) est VRAI si et seulement si les deux valeurs boolénnes de a et b sont VRAIES en même temps.

(a ET b) se note : $a\cdot b$ ou encore $a\land b$

La table de vérité faux/vrai de l'opérateur booléen ET est exactement identique à la la table de multiplication de deux chiffres binaires.

Table de vérité du ET

$a$	$b$	$a\land b$
0	0	0
0	1	0
1	0	0
1	1	1

autre présentation : table à deux entrées.

$\land$	F	V
F	F	F
V	F	V

la table à deux entrées correspond point par point à la table de multiplication en binaire :

$\times$	0	1
0	0	0
1	0	1

Exercice : trouver un schéma d'une porte ET réalisée à l'aide de transistors MOS canal N et de résistances.

Opération booléenne OU EXCLUSIF

la valeur de $a\ {\mbox{OU EXCLUSIF}}\ b$ est VRAIE si et seulement si une seule des valeurs $a$ ou $b$ est VRAIE (donc l'autre est fausse, en même temps).

Table de vérité du OU EXCLUSIF

$a$	$b$	$a\ {\mbox{OU EXCLUSIF}}\ b$
0	0	0
0	1	1
1	0	1
1	1	0

Équation logique du OU EXCLUSIF

Cette opération peut se formuler comme : « a est VRAI ET b est FAUX, ou a est FAUX et B est VRAI ».

• On peut traduire « a est VRAI ET b est FAUX » par $a\land {\overline {b}}$ :
• on peut traduire « a est FAUX et B est VRAI » par ${\overline {a}}\land b$.

Donc l'équation logique de a OU EXCLUSIF b est : $(a\land {\overline {b}})\lor ({\overline {a}}\land b)$

Exercices sur les opérateurs logiques

N.B. : le symbole $\oplus$ est celui de l'opération OU EXCLUSIF.

Exercice 1 :

Remplissez les cases de ce tableau de vérité :

$a$	$b$	${\overline {a}}$	${\overline {b}}$	$a\land {\overline {b}}$	${\overline {a}}\land b$	$(a\land {\overline {b}})\lor ({\overline {a}}\land b)$	$a\oplus b$
0	0	1	1
0	1	1	0
1	0
1	1

Exercice 2 :

Montrez que ${\overline {(a\land b)\lor ({\overline {a}}\land {\overline {b}})}}$ est une autre expression possible pour $a$ OU EXCLUSIF $b$.

Exercice 3 :

Donnez une expression logique pour l'opération "TRUC" dont la table de vérité est ci-dessous :

$a$	$b$	$a\ {\mbox{TRUC}}\ b$
0	0	1
0	1	0
1	0	1
1	1	1

Montrer que l'opération "TRUC" peut aussi s'interpréter comme "a IMPLIQUE b", ou "si a est VRAI, alors b est VRAI".

Combinaisons de portes logiques

On peut schématiser les portes logiques comme des rectangles branchés à des fils électriques. Par convention, on place les fils de sorties des portes logiques du même côté, en général à droite quand c'est possible. Une inscription sur le rectangle rappelle la fonction de la porte logique.

On peut se procurer une « boîte à outils » contenant des portes logiques, par exemple en achetant des circuits intégrés logiques de la série CMOS, ou TTL. Les schémas de portes logiques ne contiennent pas les fils d'alimentation électrique qui permettent aux portes de fonctionne. Bien évidemment, quand on réalise un montage réel avec les portes logiques, il convient de bien brancher les fils d'alimentation.

Notre boîte à outils « de départ »

Notre boîte à outil de départ contient les portes ET, OU et NON. La sortie de chaque porte est du côté arrondi du rectangle.

porte ET	porte OU	porte NON

Exercices avec des portes logiques : quatre pour une

Trouvez la table de vérité de la porte logique obtenue par des combinaisons ci-dessous :

Cette table de vérité permet-elle de créer une nouvelle porte pour notre « boîte à outils » ?

Exercices avec des portes logiques : OU EXCLUSIF

Rappeler une formule logique utilisant les opérateurs ET, OU, NON, qui permet d'obtenir l'opération OU EXCLUSIF.

Câbler cette formule logique en utilisant des portes ET, OU, NON. À partir de là, on peut considérer qu'on a rajouté une porte OU EXCLUSIF à notre boîte à outils. On l'étiquettera "OUEX".

Exercices avec des portes logiques : demi-additionneur à 1 bit

Voici une table d'addition pour le système binaire :

0	1
0	0	1
1	1	0$^{*}$

L'étoile en exposant, dans la case en bas à droite de la table, signifie qu'il y a une retenue : « un et un fait zéro et je retiens un ».

Voici un schéma de montage qui additionne deux bits $a$ et $b$ (les chiffres binaires sont des Binary digITs), calcule le bit de somme et le bit de retenue :

Peut-on associer des montages de ce genre pour faire un additionneur qui traite les deux fois 8 bits de deux octes à additionner, d'un seul coup ? Justifier le nom "demi-additionneur" de ce circuit.

Exercices avec des portes logiques : additionneur complet

On trouve, publié dans Wikipedia, un schéma d'additionneur ; celui-ci se schématise comme ceci, avec notre convention de représentation des portes logiques :

Complétez la table de vérité de cette porte à trois entrées et deux sorties :

a	b	retenue entrante	somme	retenue sortante
0	0	0
0	0	1
0	1	0
0	1	1
1	0	0
1	0	1
1	1	0
1	1	1

Vérifier que cette porte est effectivement utilisable pour additionner des mots de plusieurs bits, en en associant autant que nécessaire.

Exercices de programmation

Recherche d'entiers pairs non divisibles par trois

On veut la liste de tous les nombres pairs et non divisibles par trois compris entre 1 et 100. On utilisera l'opération "modulo", qui permet d'obtenir le reste de la division d'un nombre par un autre.

Soit $a$ la proposition "le nombre $x$ est pair". Cette proposition peut se transcrire par l'expression $x{\bmod {2}}=0$.

x "modulo 2" est nul, signifie que le reste de la division de x par 2 est nul.

Soit $b$ la proposition "le nombre $x$ n'est pas divisible par 3". On peut la transcrire par l'expression $x{\bmod {3}}\neq 0$

On peut donc utiliser l'algorithme suivant pour trouver la liste des nombres pairs non divisibles par trois :

debut
  entier i
  liste l := []
  booleen a
  booleen b
  pour i dans intervalle [1,100]
    a := (x mod 2 = 0)
    b := (x mod 3 = 0)
    si a et non b alors
      l := ajout(l, x)
    fin si
  fin pour
  resultat := l
fin

Programmer cet algorithme dans un ou plusieurs langages et tester les programmes.

Recherche de nombres premiers

Problème facile

La liste des nombres premiers inférieurs à 10 est : 2, 3, 5 et 7

Écrire un algorithme qui permet de trouver la liste des nombres premiers (c'est à dire divisibles seulement par eux-même et par 1) entre 11 et 49. Programmer l'algorithme et le tester.

Problème difficile

On donne un nombre, trouver la liste des nombres premiers plus petits que celui-ci.

Écrire un algorithme, programmer, tester.