Leçons de niveau 12

Informatique au lycée/Algèbre booléenne et circuits logiques

Une page de Wikiversité.
Sauter à la navigation Sauter à la recherche
Début de la boite de navigation du chapitre
Algèbre booléenne et circuits logiques
Icône de la faculté
Chapitre no 5
Leçon : Informatique au lycée
Chap. préc. :Codage de l'information
Chap. suiv. :Programmation et langages
fin de la boite de navigation du chapitre
Icon falscher Titel.svg
En raison de limitations techniques, la typographie souhaitable du titre, « Informatique au lycée : Algèbre booléenne et circuits logiques
Informatique au lycée/Algèbre booléenne et circuits logiques
 », n'a pu être restituée correctement ci-dessus.

L'algèbre de Boole[modifier | modifier le wikicode]

Wikipédia possède un article à propos de « Algèbre de Boole ».

L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques qui s'intéresse aux opérations et aux fonctions sur les variables logiques. Elle fut inventée par le mathématicien britannique George Boole. Aujourd'hui, l'algèbre de Boole trouve de nombreuses applications en informatique et dans la conception des circuits électroniques.

On appelle B l’ensemble constitué de deux éléments appelés valeurs de vérité {FAUX, VRAI}. Cet ensemble est aussi noté B = {0, 1}, notation que l’on utilisera désormais.

Sur cet ensemble on peut définir les lois ET et OU et une transformation appelée « complémentaire » (parfois « inversion » ou « contraire »).

ET

Elle est définie de la manière suivante : a ET b est VRAI si et seulement si a est VRAI et b est VRAI.

OU

Elle est définie de la manière suivante : a OU b est VRAI si et seulement si a est VRAI ou b est VRAI, ou si a et b sont vrais.

NON

Le contraire de « a » est VRAI si et seulement si a est FAUX.

Fonctions logiques et tables de vérité[modifier | modifier le wikicode]

Wikipédia possède un article à propos de « Table de vérité ».

Une table de vérité est un tableau qui représente des entrées (en colonne) et des états binaires (0 et 1). Le résultat, exprimé lui aussi sous forme binaire, se lit dans la dernière colonne.

Symbole de la porte logique Opération booléenne Table de vérité
ET (AND) TODO : image A·B
Entrées Sortie
A B A AND B
0 0 0
0 1 0
1 0 0
1 1 1
OU TODO A+B
Entrées Sortie
A B A AND B
0 0 0
0 1 1
1 0 1
1 1 1
NON TODO
Entrées Sortie
A NOT A
0 1
1 0
NON-ET TODO
Entrées Sortie
A B A NAND B
0 0 1
0 1 1
1 0 1
1 1 0
NON-OU TODO
Entrées Sortie
A B A NOR B
0 0 1
0 1 0
1 0 0
1 1 0
OU exclusif TODO
Entrées Sortie
A B A XOR B
0 0 0
0 1 1
1 0 1
1 1 0

Quelques propriétés utiles[modifier | modifier le wikicode]

Associativité[modifier | modifier le wikicode]

Comme avec les opérations habituelles, certaines parenthèses sont inutiles :

(a + b) + c = a + (b + c) = a + b + c

(a·b)·c = a·(b·c) = a·b·c

Commutativité[modifier | modifier le wikicode]

L'ordre est sans importance :

a + b = b + a

a·b = b·a

Distributivité[modifier | modifier le wikicode]

Comme avec les opérations mathématiques habituelles, il est possible de distribuer :

a·(b+c) = a·b + a·c

Idempotence[modifier | modifier le wikicode]

a + a + a + [...] + a = a

a·a·a·[...]·a = a

Élément neutre[modifier | modifier le wikicode]

a+0=a

a·1 = a

Élément nul[modifier | modifier le wikicode]

0·a = 0

1+a=1

Complémentarité[modifier | modifier le wikicode]

a = ¬(¬a)

a+ a = 1

a· a = 0

Théorème de De Morgan[modifier | modifier le wikicode]

Priorité[modifier | modifier le wikicode]

Pour faciliter leur compréhension, il a été décidé que ces opérations seraient soumises aux mêmes règles que les opérations mathématiques. La fonction ET (multiplication logique) est ainsi prioritaire par rapport à la fonction OU (somme logique) ; on peut, pour s'aider, placer des parenthèses dans les opérations.

Tables de Karnaugh[modifier | modifier le wikicode]

Une table de Karnaugh est une méthode inventée par Maurice Karnaugh en 1954 et qui sert à simplifier des équations logiques ou à trouver l'équation logique correspondant à une table de vérité. La méthode utilisée est graphique. Elle fonctionne très bien avec 3 ou 4 variables, beaucoup moins bien avec 5 ou 6 variables, et plus du tout au-delà !

Principe[modifier | modifier le wikicode]

Soit la table de vérité de S suivante avec les variables A, B, C et D :

A B C D S
0 0 0 0 1
0 0 0 1 0
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 1
0 1 1 0 1
0 1 1 1 1
1 0 0 0 1
1 0 0 1 0
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 1
1 1 1 0 1
1 1 1 1 1

La table de Karnaugh correspondante se présente ainsi :

AB\CD 00 01 11 10
00 1 0 1 1
01 0 1 1 1
11 0 1 1 1
10 1 0 1 1

Méthode de recherche de l'équation de la table de vérité[modifier | modifier le wikicode]

  • Pour trouver une équation logique, il faut regrouper les valeurs de S égales à 1 dans des rectangles ayant comme nombre de cases une puissance de 2 (16, 8, 4, 2 ou 1 cases).
  • Les groupes formés doivent être les moins nombreux possibles, mais ils doivent englober tous les 1. On peut faire des chevauchements.
  • On a intérêt à dessiner des rectangles les plus grands possibles.
  • On peut considérer cette table comme un tore : la dernière ligne est adjacente à la première et la première colonne est adjacente à la dernière. On peut ainsi regrouper des 1 se trouvant à ces emplacements.

Pour les tables à 4 variables, il faut de préférence procéder dans l’ordre suivant :

  1. les rectangles 8 cases, puis
  2. les rectangles 4 cases, puis
  3. les rectangles 2 cases, et enfin
  4. les cases uniques.

Dans l'exemple : on peut former un rectangle de 8 cases (en bleu), puis un carré de 4 (en vert) et enfin on peut regrouper les deux 1 restants (en rouge).

AB\CD 00 01 11 10
00 1 0 1 1
01 0 1 11 1
11 0 1 11 1
10 1 0 1 1

Mise en équation[modifier | modifier le wikicode]

Circuits logiques[modifier | modifier le wikicode]