Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

TDI1C, TRI1A, TRI1B 2010/2011 Module : Notions de mathématiques appliquées à l’

TDI1C, TRI1A, TRI1B 2010/2011 Module : Notions de mathématiques appliquées à l’Informatique. Chapitre : Algèbre de BOOLE Présentation George Boole est le père fondateur de la logique moderne. L'algèbre de Boole est une algèbre permettant de traduire des signaux (tout ou rien) en expressions mathématiques en remplaçant chaque signal élémentaire par des variables logiques et leur traitement par des fonctions logiques. L'algèbre de Boole nous permettra de résoudre des équations logiques afin de réaliser des fonctions sur des signaux numériques. Ces fonctions seront appelées fonctions combinatoires et l'étude de la logique combinatoire nous conduira à réaliser des codeurs, des transcodeurs et même des circuits arithmétiques. Une fois assemblées, ces fonctions combinatoires simples donneront naissances à des circuits réalisant des opérations très complexes utilisées dans l'élaboration des processeurs, DSP, ASIC, FPGA... L'étude des propriétés de l'algèbre de Boole nous amène à considérer les notions de variable binaire, variable logique et fonction logique. Après avoir défini le système binaire, la fonction logique à une variable (OUI, NON), la fonction logique à deux ou n variables (OU, ET) nous abordons le concept de logique combinatoire. Avec l'algèbre de Boole comme outil mathématique nous étudions les principales combinaisons logiques souvent utilisées à des fins techniques. Les différentes fonctions logiques de base sont décritent sous cinq formes : une représentation logique : symbole logique une représentation arithmétique : table de vérité une représentation algébrique ou cononique : équation de l'algèbre de boole une représentation électrique : schéma développé à contacts Formatrice : Imane BOUROUS TDI1C, TRI1A, TRI1B 2010/2011 Sommaire Sommaire ............................................................................................................... 2 Introduction ............................................................................................................ 3 Généralités et Définitions ....................................................................................... 3 Fonction de base : ET, OU, OU exclusif ................................................................... 4 Logique combinatoire .......................................................................................... 4 Fonction NON ou "NO" ......................................................................................... 4 Fonction OU ou "OR" ........................................................................................... 5 Fonction ET ou "AND" .......................................................................................... 5 Fonction OU EXCLUSIF ou "XOR" ......................................................................... 6 Résumé des propriétés : ........................................................................................ 6 Théorème de MORGAN ........................................................................................... 7 Complément d'une somme logique ..................................................................... 7 Complément d'une somme logique ..................................................................... 7 FONCTIONS LOGIQUES ........................................................................................... 7 Table de vérité .................................................................................................... 7 Formes canoniques d'une fonction logique ........................................................ 8 Équivalence entre la table de vérité et forme canonique Table de vérité: .......... 8 Simplification des fonctions logiques - Tableau de KARNAUGH ........................... 9 Résolution d’un problème ...................................................................................... 9 Formatrice : Imane BOUROUS TDI1C, TRI1A, TRI1B 2010/2011 Introduction De nombreux dispositifs électroniques, électromécanique, (mécanique, électrique, pneumatique, etc....) fonctionnement en TOUT ou RIEN. Ceci sous-entend qu’ils peuvent prendre 2 états. Exemple : • arrêt marche • ouvert fermé • enclenché déclenché • avant arrière • vrai faux • conduction blocage Pour ces raisons, il est beaucoup plus avantageux d'employer un système mathématique n'utilisant que 2 valeurs numériques (exemple O ou 1) pour étudier les conditions de fonctionnement de ces dispositifs : C'est le système BINAIRE L'ensemble des règles mathématiques qui pourront être utilisées avec des variables ne pouvant prendre que 2 valeurs possibles représente : "L'ALGÈBRE DE BOOLE" Généralités et Définitions Variable logique ou variable binaire La variable logique est une grandeur qui peut prendre 2 valeurs qui sont repérées habituellement 0 ou 1. Cette variable binaire se note par une lettre comme en algèbre. Exemple : a b x Physiquement, cette variable peut correspondre à l’un des dispositifs cités ci-dessus dont les 2 états représentent les 2 valeurs possibles que peut prendre cette variable. D'une façon générale, ces 2 états sont repérés H et L et on attribue à l'état H (high) la valeur 1 à l'état L (1ow) la valeur 0 On trouvera parfois cette notation du zéro : Ø pour éviter la confusion avec la lettre O. La variable binaire est aussi appelée variable booléenne. Formatrice : Imane BOUROUS TDI1C, TRI1A, TRI1B 2010/2011 Fonction de base : ET, OU, OU exclusif Une fonction logique est le résultat de la combinaison (logique combinatoire) d'une ou plusieurs variables logiques reliées entre elles par des opérations mathématiques BOOLEENNES bien définies : la valeur résultante de cette fonction dépend de la valeur des variables logiques, mais de toute façon cette résultante ne peut être que O ou 1. Une fonction logique possède donc une ou des variables logiques d'entrée et une variable logique de sortie. Cette fonction logique se note par une lettre comme en algèbre. Logique combinatoire La logique combinatoire, à l'aide de fonctions logiques, permet la construction d'un système combinatoire. Un système est dit combinatoire quand il est de type boucle ouverte, c'est à dire qu'aucune des sorties n'est bouclée en tant qu'entrée. A chaque combinaison d'entrée correspond une seule sortie. Les systèmes combinatoires sont les plus simples et peuvent se représenter par une table de vérité indiquant pour chaque état d'entrée quel est l'état de sortie correspondant. Fonction NON ou "NO" La fonction NON est obtenue avec une seule variable. Table de vérité La valeur de la fonction est toujours la valeur inverse (complémentaire) de celle de la variable. Nous l'écrivons : X = /a et nous lisons : X égale a barre. Cette fonction est aussi appelée : Fonction Inversion, Fonction complémentation. Nous disons également que a est la valeur complémentaire de a et x la valeur complémentaire de x. Symbolisation Formatrice : Imane BOUROUS TDI1C, TRI1A, TRI1B 2010/2011 Fonction OU ou "OR" On obtient la fonction OU avec un minimum de deux variables. Elle correspond à V7 du tableau des 16 fonctions à 2 variables. Table de vérité La fonction X prend la valeur 1 quand l'une ou l'autre ou les 2 variables sont à 1. Nous l'écrivons : X = a + b ==> addition ou somme logique Nous lirons X égale a ou b. Propriétés particulières : a + 1 = 1 a + 0 = a a + a = a a + a = 1 Symbolisation Fonction ET ou "AND" Cette fonction est obtenue avec au moins deux variables. Elle correspond à V1 du tableau des 16 fonctions à 2 variables. Table de vérité La fonction X prend la valeur 1 quand l'une et l'autre variables sont à 1. Formatrice : Imane BOUROUS TDI1C, TRI1A, TRI1B 2010/2011 Nous l'écrivons : X = a . b ==> produit logique Nous lirons X égale a et b. Propriétés particulières a . 1 = a a . 0 = 0 a . a = a a . a = 0 Symbolisation Fonction OU EXCLUSIF ou "XOR" Le OU EXCLUSIF est une fonction obtenue avec un minimum de deux variables. Table de vérité Considération 1 : La fonction X prend une valeur égale à 1 quand l'une OU l'autre des variables, à l'EXCLUSION des 2 à la fois, prennent une valeur égale à 1. Nous l'écrivons : X = a b. Nous lirons : X égale a XOR b ; X égale a OU EXCLUSIF b. Expression du Ou exclusif Propriétés particulières : a 1 = a a 0 = a a a = 0 a a = 1 Résumé des propriétés : P1 : Involution : Formatrice : Imane BOUROUS TDI1C, TRI1A, TRI1B 2010/2011 P2 : Idempotence : P3 : Commutativité : P4 : Associativité : P5 : Complémentarité : P6 : Elément neutre : P7 : Distributivité : P8 : Absorption : Théorème de MORGAN Complément d'une somme logique Complétons le tableau suivant et comparons les valeurs des fonctions Y1 et Y2. Conclusion Complément d'une somme logique De la même manière on peut prouver que FONCTIONS LOGIQUES Table de vérité La relation entrée-sortie d'un système logique peut être mise sous forme d'un tableau que l'on nomme table de vérité. Une table de vérité comporte 2 lignes où n est les nombre de variable d'entrées. Elle comporte toutes les combinaisons possibles de variables. Soit un système logique à deux variables A et B. Formatrice : Imane BOUROUS TDI1C, TRI1A, TRI1B 2010/2011 A B SYSTEME LOGIQUE Y Formes canoniques d'une fonction logique Première forme canonique (Forme Disjonctive) Elle correspond à une somme des produits logiques. Si chacun des produits contient toutes les variables d'entrée sous une forme directe ou complémentée, alors la forme est appelée « première forme canonique » ou « forme canonique disjonctive ».Chacun des produits est alors appelé minterme. Exemple : Deuxième forme canonique (Forme Conjonctive) Elle fait référence à un produit de sommes logiques. Si chacune des sommes contient toutes les variables d'entrée sous une forme directe ou complémentée, alors la forme est appelée « deuxième forme canonique » ou « forme canonique conjonctive ». Chacune des sommes est alors appelée maxterme. Exemple: Équivalence entre la table de vérité et forme canonique Table de vérité: A B C Y 0 0 0 1 0 0 1 1 0 1 0 0 0 1 1 1 1 0 0 0 1 0 1 1 1 1 0 0 1 1 1 0 Pour écrire l'équation de Y en fonction des 3 variables il faut dire : Y=1 si A=0 ET B=0 ET C=0 OU A=0 ET B=0 ET C=1 OU A=0 ET B=1 ET C=1 OU A=1 ET B=0 ET C=1 Ce qui donne une écriture "algébrique" en notant : La variable par sa lettre si elle vaut 1 (ex : uploads/Philosophie/ cours-alg.pdf