ISN Opérations booléennes

Un livre de Wikilivres.
Sauter à la navigation Sauter à la recherche

Les opérations booléennes[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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

Table de vérité du NON[modifier | modifier le wikicode]

0 1
1 0

Réalisation d'une porte NON avec un transistor MOS à effet de champ[modifier | modifier le wikicode]

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

  • quand la tension électrique entre grille et source 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 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 :

FET-g0V.svg FET-g0V-equiv.svg
la tension 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 :

FET-g5V.svg FET-g5V-equiv.svg
la tension est égale à , 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[modifier | modifier le wikicode]

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 :

Table de vérité du OU[modifier | modifier le wikicode]

0 0 0
0 1 1
1 0 1
1 1 1

Réalisation d'une porte OU avec des transistors MOS[modifier | modifier le wikicode]

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

On peut montrer que , ou, noté autrement, . Comme est la négation de et que la double négation revient à une copie en logique binaire, .

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 :

0 0 1
0 1 0
1 0 0
1 1 0

Opération booléenne ET[modifier | modifier le wikicode]

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 : ou encore

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[modifier | modifier le wikicode]

0 0 0
0 1 0
1 0 0
1 1 1

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

F V
F F F
V F V

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

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[modifier | modifier le wikicode]

la valeur de est VRAIE si et seulement si une seule des valeurs ou est VRAIE (donc l'autre est fausse, en même temps).

Table de vérité du OU EXCLUSIF[modifier | modifier le wikicode]

0 0 0
0 1 1
1 0 1
1 1 0

Équation logique du OU EXCLUSIF[modifier | modifier le wikicode]

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  :
  • on peut traduire « a est FAUX et B est VRAI » par .

Donc l'équation logique de a OU EXCLUSIF b est :

Exercices sur les opérateurs logiques[modifier | modifier le wikicode]

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

Exercice 1 :

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

0 0 1 1
0 1 1 0
1 0
1 1

Exercice 2 :

Montrez que est une autre expression possible pour OU EXCLUSIF .

Exercice 3 :

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

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[modifier | modifier le wikicode]

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 »[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

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 et (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[modifier | modifier le wikicode]

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[modifier | modifier le wikicode]

Recherche d'entiers pairs non divisibles par trois[modifier | modifier le wikicode]

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 la proposition "le nombre est pair". Cette proposition peut se transcrire par l'expression .

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

Soit la proposition "le nombre n'est pas divisible par 3". On peut la transcrire par l'expression

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[modifier | modifier le wikicode]

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.