Cours de Mathématiques : calcul Booléen

Résumé du document

Treillis
Une Relation d'ordre permet de faire des calculs algébriques (...)

Extraits

[...] { = { = { 15} = { 25} = { 75} = { = { 15} = { 25} = { 75} = { 15} = { 25} = { 75} = { 25} = { 75} = { 75} = et 15 n'ont pas de complément donc D75 est un treillis non complémenté Page 5 NEUVIEME PARTIE - CALCUL BOOLEEN Algèbre de Boole Un treillis à la fois distributif et complémenté est un algèbre de Boole Dans tout algèbre de Boole, chaque élément x possède un seul complément x Généralités : Un algèbre de Boole général, noté est muni d'une Relation d'ordre notée ; le plus petit majorant de deux éléments x et y est noté x v y (c'est la borne supérieure) Leur plus grand minorant x y et on considère le plus grand élément de S soit sup(b) = I , et le plus petit élément inf(b) = 0. Le complément de x est noté x , et l'opération qui associe x à x s'appelle : La Complémentation. I est le plus grand élément de l'algèbre. [...]

[...] Les autres propriétés étant des conséquences de ces dernières. Exercice : Montrer que dans tout algèbre de Boole, on a : x , y B : x = y v = étapes : Il faut démontrer les 2 implications : si x = y alors ( x v ( x = 0 = v ( x v ( x v v ( y v = v y ) ( y v I = ( x v ( y v = y v ( y inf y = y y sup y = 0 si ( x v ( x = 0 v ( x = 0 ? [...]

[...] (donc tous ces éléments ont au moins un élément) Exemple e : Dans le diagramme de Hasse du cube : A est aussi un treillis complémenté car : 6 sup(A) = 30 inf(A) = 15 = 10 = 1 v 15 = 30 donc 2 = v 10 = 30 donc 3 = v 6 = 30 donc 5 = 6 Page NEUVIEME PARTIE - CALCUL BOOLEEN Dans l'exemple a : A n'est pas un treillis complémenté car b (par exemple) n'a pas de complément , - a b , - b c , - b d , - a f , - b f , - b g , - b h e f g h a b c d Ici, b n'a pas de complément. Exercice : On a ( D75, ) représentant l'ensemble des divisions de 75. Donner le diagramme de Hasse correspondant ; Est-ce un treillis, est-il complémenté ? D75 = { } 75 = 3 x 25 = 3 x 52 3a x 5b avec a et b On a donc : 2 x 3 = 6 diviseurs div75 = { } Quel est l'élément supérieur de l'ensemble sup(D75) = 75 ? [...]

[...] borne inf Tout treillis fini possède un plus grand et un plus petit élément . Les ensembles totalement ordonnés (c'est à dire, les ensembles munis d'un ordre total) sont des treillis. [Si une chaîne = obligatoirement un treillis] Conclusion : A n'est pas un treillis car sup(b , inexistant et inf(d , aussi. Exemple b : Soient A = { a , b , c , d , e , f } Et son diagramme de Hasse : f , a b , a c , a d , a e , a f , a pas de sup . [...]

[...] Il est isomorphe à Bn et son diagramme de Hasse est un n-cube. [...]