algebre de bool

« Mars 2010 ALGEBRE DE BOOLE BTS IG2 INTRODUCTION. 1.

Exemple: A •-----⁄--------------⁄ a ----------- \----------•B Soit a l'interrupteur. ◊ Si a est fermé le courant passe, on dit que a = 1. ◊ Si a est ouvert le courant ne passe pas, on dit que a = 0. a est une variable de Boole qui ne peut prendre que les valeurs 0 ou 1. 2..

Généralisation pour deux interrupteurs.

on a donc deux variables de Boole a , b . •• Premier type de montage: ( En série .

) A •-----⁄--------------⁄ a ----------- \------------⁄--------------⁄ b ----------- \--------•B ◊ Si ( a = 0 et b = 1 ) ou (a = 1 et b = 0 ) ou (a = 0 et b = 0 ) , c.-à-d.

si l'un des interrupteurs au moins est ouvert, alors le courant ne passe pas. On dit que a .

b = 0 ◊ Si ( a = 1 et b = 1 ) , c.-à-d.

les deux interrupteurs sont fermés alors le courant passe. On dit: o a.

b = 1 La multiplication des deux variables ( booléennes ) s'apparente au connecteur logique " et " . •• Second type de montage: (En parallèle ) --------------⁄ a ----------\-----------\ /-----⁄ \-----⁄--------------⁄ b ----------- \-----------// ◊ Si ( a = 0 et b = 1 ) ou (a = 1 et b = 0 ) ou (a = 1 et b = 1 ) , c.-à-d.

si l'un des interrupteurs au moins est fermé, alors le courant passe. On dit : a + b =1 ◊ Si ( a = 0 et b = 0 ) , c.-à-d.

les deux interrupteurs sont ouverts alors le courant ne passe pas. On dit : a+b=0 La somme des deux variables (booléennes) s'apparente au connecteur " ou " 1.

ASPECT THEORIQUE. Une algèbre de Boole est un ensemble E (non vide), dont les éléments sont des variables notées a, b, c, d , e , f , g ....

etc.

" dites booléennes" qui ne peuvent prendre que deux valeurs 0 ou 1, muni de trois opérations. + " la somme booléenne" définie par : a b a+b 0 0 0 0 1 1 1 0 1 1 1 1 • le "produit booléen" défini par: a b a•b 0 0 0 0 1 1 0 0 0 1 1 1 • la "complémentation" définie par: a a 0 1 1 0 et qui ont des particularités. + est Associative. ( a + b) + c = a + (b + c ) = a + b +c + admet 0 comme élément Neutre. a + 0 = 0 + a = a + est commutative. a + b = a + b + est Distributive par rapport à • a + (b • c ) = ( a + b ) • ( a + c ) • est Associative. (a • b) • c = a • ( b • c ) = a • b • c • admet 1 comme élément Neutre. a • 1 = 1 • a = a • est Commutative. • est Distributive par rapport à + a • b = a • b a • ( b + c ) = ( a • b )+ ( a • c ) Existence d'un complémentaire a pour tout a dans E a+ a =1 a • a= 0 pour tout a dans E 2.

EXEMPLE. L'ensemble des propositions mathématiques avec les opérations "ou " "et " "NON" . 3.

PROPRIETES DE L'ALGEBRE DE BOOLE E ( + , • , ¯ ) Soit a , b , c trois variables booléennes c.-à-d.

trois éléments de E. ◊ Pour tout a dans E (Idempotence) a+a=a Aucun multiple TRES IMPORTANT a •a =a Aucune puissance TRES IMPORTANT ◊ Pour tout a et tout b dans E a + (a • b) = a (Absorption) TRES IMPORTANT a • (a + b) = a ◊ Pour tout a et tout b dans E (Lois de Morgan) La complémentation de a + b est a • b La complémentation de a • b est a + b TRES IMPORTANT TRES IMPORTANT ◊ Pour tout a et tout b dans E a+1=1 TRES IMPORTANT a• 0=0 TRES IMPORTANT a + ( a • b) = a + b (TRES IMPORTANT pour les exercices.

) a • (a + b ) = a • b 4.

Remarque: a + ( a • b) est interprété même sans parenthèse comme a + b. Par contre pour a • ( a + b) il faut mettre les parenthèses pour éviter les confusions. 5.

Mintermes- maxtermes Un « minterme » de n variables booléennes est un produit comportant n facteurs, chaque facteur correspondant à une variable donnée ou à son complémentaire Un « maxterme » de n variables booléennes est une somme comportant n termes , chaque terme correspondant à une variable donnée ou à son complémentaire ♥ Les Minterms de deux variables a et b sont les expressions suivantes : a•b ; a• b ; a •b ; a • b On peut les faire apparaitre dans un tableau: TRES IMPORTANT a\b 0 1 0 a • b a •b 1 a• b a•b Quand une expression A ne comporte que deux variables a et b On peut toujours la présenter comme somme de certains des minterms a•b ; a• b ; a •b ; a • b Dans le tableau précédent on met des 1 à la place des minterms dont elle est la somme. Par exemple; Soit A = a • b + a • b va se traduire par le tableau (De Karnaugh) suivant.

: a\b 0 0 1 1 1 1 Ici on trouve A = b à l'aide visuelle du tableau de Karnaugh de A. ♥ Les Minterms de trois variables a, b, c sont les expressions suivantes : a• b • ; a • b•c ; a •b•c ; a •b• c ; a• b • c ; a• b•c ; a•b•c a•b• c ; On les met en évidence dans le tableau ci-dessous. a\ bc 00 01 11 0 a • b •c a • b •c a •b•c a • b •c 1 a• b • c a• b •c a•b•c a•b• c Quand une expression A 10 ne comporte que trois variables a , b , c on peut toujours la présenter comme somme de certains des minterms précédents. Dans le tableau précédent on met des 1 à la place des minterms dont elle est la somme. Par exemple; Soit A = a • b • c + a • b • c + a • b • c va se traduire par le tableau a\ bc 0 1 00 1 01 11 1 10 1 C'est le tableau de Karnaugh de A.

Il permet de simplifier l'expression de A. A =a•b+ a • b • c Ici on peut dire : Comment obtenir une expression simplifiée : On obtient l’expression simplifiée d’un diagramme de Karnaugh en regroupant les « 1 » adjacents d’abord 8 par 8 si l’on peut, puis, après, 4 par 4, puis, après 2 par 2. Remarques :  Deux « 1 » sont adjacents lorsque leurs cases ont un côté commun .On considère que le bord droit et le bord gauche du diagramme sont un côté unique.  Pour a , on aurait pu regrouper autrement les « 1 » adjacents. a\ bc 00 0 1 01 11 1 1 10 1 1 On aurait pu obtenir :  a= a c +a c C’est la disposition 00, 01,11,10 qui rend possible les regroupements.  Exemple : a\ bc 00 0 01 11 1 1 1 1 1 Est celui de l’expression simplifiée : 10 1 1 b + ac + a b c Exercices : EX.

1 Soit les variables booléennes a , b ,c . Indication correction Soit A l'expression booléenne dont le tableau de Karnaugh est a\b c 00 0 1 1 1 01 11 10 1 1 Donner l'expression de A. 1 1 EX.

2 Soit les variables booléennes a , b ,c . 1.

Soit A = Indication correction a b + a b + b.

Simplifier A. 2.

Soit B = a b + abc + a b .

Simplifier B. 3.

Soit C = a b c + a b c + a b + a b c .

Simplifier C. 4.

Soit D = ( a + b ) ( b + c ) ( c +a ) .

Simplifier D. EX.

3 1.

Donner l'expression de A dont le tableau de Karnaugh est : Indication a\b c correction 00 01 0 1 1 1 1 11 10 1 1 2.

Simplifier l'expression de A à l'aide du tableau. A= ab + a c+ 3.

Trouver par le calcul que : EX.

4 Simplifier par le calcul A = ( a + b +.... »