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

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

L'algèbre de Boole

Cette section est vide, insuffisamment détaillée ou incomplète. Votre aide est la bienvenue ! Comment faire ?

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é

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

Associativité

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é

L'ordre est sans importance :

a + b = b + a

a·b = b·a

Distributivité

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

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

Idempotence

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

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

Élément neutre

a+0=a

a·1 = a

Élément nul

0·a = 0

1+a=1

Complémentarité

a = ¬(¬a)

a+ a = 1

a· a = 0

Priorité

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

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

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é

• 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