1 C C C Chapitr hapitr hapitr hapitre e e e 2 2 2 2 A A A Algèbre de Boole lgèb

1 C C C Chapitr hapitr hapitr hapitre e e e 2 2 2 2 A A A Algèbre de Boole lgèbre de Boole lgèbre de Boole lgèbre de Boole et et et et C C C Circuits ircuits ircuits ircuits L L L Logiques ogiques ogiques ogiques Sommaire II.1 – INTRODUCTION ...................................................................................................................................................................................... 2 II.2 – DEFINITION DE L’ALGEBRE DE BOOLE. ....................................................................................................................................................... 2 II.3 – THEOREMES ET PROPRIETES ...................................................................................................................................................................... 2 II.3.1 Principe de dualité ....................................................................................................................................................................... 2 II.3.2 Théorèmes Fondamentaux .......................................................................................................................................................... 3 II.4 – CONCEPTS FONDAMENTAUX ..................................................................................................................................................................... 3 II.4.1 Variables booléennes ................................................................................................................................................................... 3 II.4.2 Fonctions booléenne .................................................................................................................................................................... 3 II.4.3 Opérateurs booléens ou fonctions de base .................................................................................................................................. 3 II.4.4 Système logique complet (S.L.C) .................................................................................................................................................. 3 II.4.5 Système logique complet minimisé .............................................................................................................................................. 3 II.4.6 Expressions booléennes ............................................................................................................................................................... 4 II.5 – FONCTIONS BOOLEENNES ......................................................................................................................................................................... 4 II.5.1 Manipulations algébriques .......................................................................................................................................................... 4 II.5.2 Représentation par la table de vérité ........................................................................................................................................... 4 II.5.3 Représentation par la forme algébrique ...................................................................................................................................... 5 II.5.4 Passage de la forme algébrique à la table de vérité .................................................................................................................... 5 II.5.5 Passage de la table de vérité à la forme algébrique .................................................................................................................... 5 II.5.6 Fonctions booléennes à une variable ........................................................................................................................................... 6 II.5.7 Fonctions booléennes à deux variables ........................................................................................................................................ 6 II.5.8 Fonctions booléennes à n variables ............................................................................................................................................. 6 II.5.9 Les fonctions booléennes particulières......................................................................................................................................... 6 II.5.10 Représentation schématiques des fonctions logiques ................................................................................................................ 7 II.6 – FORMES CANONIQUES ............................................................................................................................................................................. 7 II.6.1 Mintermes et Maxtermes ............................................................................................................................................................ 7 II.6.2 Conversions entre formes canoniques ......................................................................................................................................... 8 II.7 – SIMPLIFICATIONS DES FONCTIONS BOOLEENNES ............................................................................................................................................. 9 II.7.1 La méthode algébrique ................................................................................................................................................................ 9 II.7.2 Méthode de simplification de Karnaugh ...................................................................................................................................... 9 Support de cours établi par Lhadi BOUZIDI Année universitaire 2013-2014 Semestre II 2 II.1 – Introduction Un processeur est composé de transistors permettant de réaliser des fonctions sur des signaux numériques. Ces transistors, assemblés entre eux forment des composants permettant de réaliser des fonctions très simples. A partir de ces composants il est possible de créer des circuits réalisant des opérations plus complexes. L'algèbre de Boole (du nom du mathématicien anglais Georges Boole 1915 - 1864) est un moyen permettant de concevoir de tel circuit. C’est une théorie mathématique proposant de traduire des signaux électriques (à deux états) en expressions mathématiques. Pour cela, on définit chaque signal élémentaire par des variables logiques et leur traitement par des fonctions logiques. Des méthodes (table de vérité) permettent de définir les opérations que l'on désire réaliser, et de transcrire le résultat en une expression algébrique. Grâce à des règles appelées lois de composition, ces expressions peuvent être simplifiées. Cela va permettre de représenter grâce à des symboles un circuit logique (logigramme), c'est-à-dire un circuit qui schématise l'agencement des composants de base (au niveau logique) sans se préoccuper de la réalisation au moyen de transistors (niveau physique). Figure 1 - Algèbre de Boole II.2 – Définition de l’Algèbre de BOOLE. On appelle algèbre de Boole tout ensemble E muni de deux lois de composition interne « • » et «  » et d’une application involutive f (f 2 = Id) de E dans lui-même, notée f : a →  (   = ). Cet ensemble respecte les propriétés suivantes : • Chacune des deux lois est associative et commutative, • Chacune des deux lois est distributive par rapport à l’autre, • La loi « • » admet un élément neutre unique noté e1 : ∀x∈E, x• e1 = x • La loi «  » admet un élément neutre noté e0 : ∀x∈E, xe0 = x • Tout élément de E est idempotent pour chacune des deux lois : ∀x∈E, x • x = x et xx = x • Axiomes de complémentarité : ∀x∈E, x • ̅ = e0 et ∀x∈E, x̅ = e1 Exemples d’algèbres de Boole : • L’ensemble P(E) des parties d’un ensemble E, muni des opérateurs intersection ∩ , union ∪, et l’application involutive complémentaire dans E définie comme suit : f(A)= CE(A) avec A∈ P(E). • L’ensemble des propositions (leurs valeurs {V,F}) muni des connecteurs logiques ¬ (l’application involutive négation) , ∧ (ET logique), ∨ (OU logique). • L’algèbre des circuits électriques est une algèbre de Boole : L’ensemble E est composé des éléments 0 et 1. Il est muni des lois « . » et « + » et de l’application complémentaire f : a → . Concrètement, on peut utiliser des montages d’interrupteurs en série ou en parallèle pour réaliser l’équivalent des deux lois de composition « . » et « + ». Pour vérifier que les exemples ci-dessus sont réellement des algèbre de Boole, il suffit de vérifier les axiomes présentés dans la page précédente en substituant les lois du nouvel ensemble aux lois « • », «  » et à l’application f : a → . II.3 – Théorèmes et propriétés II.3.1 Principe de dualité Le principe de dualité permet de retrouver des propriétés à partir de propriétés déjà existantes en se servant d’une caractéristique dont dispose les formules issues de l’algèbre de Boole. En effet, partant d’une formule (axiome ou théorème) déjà établi, on peut retrouver une autre formule (axiome ou théorème) rien qu’en remplaçant dans la première formule la loi « + » par « . » ou inversement et l’élément neutre « 1 » par « 0 » ou inversement. Exemple : Tous les propriétés relatives à la loi « . » sont déductibles de celles de la loi « + » en se servant du principe de dualité : Propriété Loi "+" Idempotence x + x = x Commutativité x + y = y + x Associativité x + y + z = x + (y + z) = (x + y) + z Elément neutre x + 0 = x Distributivité x + (y . z) = (x + y) . (x + z) Complémentarité 1 = + x x Algèbre de Boole La conception de circuits électroniques numériques Les mémoires Les circuits de calcul Les microprocesseurs Etc… Utilisée pour Comme Théorie mathématique Un ensemble Deux lois de composition interne Une application involutive Un ensemble d’axiomes Un ensemble de théorème 3 Loi "+" Loi "." x + x = x x . x = x x + y = y + x x . y = y . x x + y + z = x + (y + z) = (x + y) + z x . y . z = x . (y . z) = (x . y) . z x + 0 = x x . 1 = x x + (y . z) = (x + y) . (x + z) x . (y + z) = (x . y) + (x . z) 1 = + x x 0 . = x x Tableau 1 - Propriétés de l’algèbre de Boole et principe de dualité II.3.2 Théorèmes Fondamentaux Les théorèmes qui suivent sont les plus utilisés dans le calcul des fonctions logiques. Tous peuvent être déduits des axiomes de l’algèbre de Boole. Inhibition y x y x x + = + ) ( y x y x x . ) .( = + Absorption x + 1 = 1 x . 0 = 0 x + (x . y) = x x . (x + y) = x DeMorgan y x y x . = + y x y x + = . x x = Tableau 2 : Théorème fondamentaux de l’algèbre de Boole Démonstration du théorème de l’inhibition : y x y x x + = + ) ( y x y x y x x x y x x + = + = + + = + ) .( 1 ) ).( ( ) ( Démonstration du théorème de l’absorption : x + (x . y) = x x + (x . y) = (x . 1) + (x . y) = x . (1 + y) = x Démonstration du théorème de l’absorption : x + 1 = 1 x + 1 = x + (x + x ) = (x + x) + x = x + x = 1 II.4 – Concepts fondamentaux II.4.1 Variables booléennes On désigne par variable booléenne un être mathématique qui représente une valeur dans l’ensemble {0,1}. Elle est identifiée par un nom composé de caractères alphanumériques (le premier est toujours alphabétique). Concrètement, elle représente un signal électrique dans un système électronique. II.4.2 Fonctions booléenne Une fonction booléenne est une relation d’un ensemble de départ Vn et d’un ensemble d’arrivée V. avec Vn = produit cartésien de V par V n fois et V={0,1}. En général, les fonctions booléennes sont des fonctions à plusieurs variables (x1,x2, ...,xn). : 0,1  → 0,1 , , … , ) →, , … , ) Exemple : f1(x1, x2, x3) = (x1+x2) .    II.4.3 Opérateurs booléens ou fonctions de base On désigne par opérateur booléen, la fonction de base associée soit à la loi de composition interne « + » ou « . » ou à l’application involutive « négation ». Nous verrons que d’autres opérateurs sont utilisés (NAND, NOR, XOR). uploads/s3/ chapitre-ii.pdf

Tags
Administrationfonction variables table forme f(x y)
Documents similaires
  • 461
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager