Remerciez-le!

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

EST SAFI – Mme O. IKHOUANE Dept GI 1ère Année CHAPITRE 2 FONCTIONS LOGIQUES Dan

EST SAFI – Mme O. IKHOUANE Dept GI 1ère Année CHAPITRE 2 FONCTIONS LOGIQUES Dans les automatismes logiques, que l'on soit en combinatoire ou en séquentiel, on prend en compte, on traite et on donne des ordres sous forme binaire (0 ou 1). Les variables logiques qui permettent de traiter ces informations peuvent s'organiser sous forme de fonctions. L’Algèbre de Boole1 définit un cadre mathématique d’étude de ces variables et fonctions. Elle permet de traduire des signaux binaires en expressions mathématiques. L’Algèbre de Boole et les fonctions logiques forment donc le support théorique des circuits combinatoires et séquentiels. 1 – ALGÈBRE DE BOOLE 1.1 – Définition Considérons un ensemble d'éléments (a,b,c, ...) associé à :  deux lois de composition interne notées respectivement : o « + » appelée addition, o « . » appelée produit,  une opération unaire notée « » (lire « barre ») et appelée complémentation. Formellement, cet ensemble et ces 3 opérations constituent une Algèbre de Boole si et seulement si les postulats suivants sont satisfaits. P1 Les opérations sont commutatives :  a b b a     a . b b . a  P2 Chacune des opérations est distributive sur l'autre :      c b a c b a c b a              c . b . a c . b . a c . b . a   P3 Postulat des éléments neutres :  Il existe un élément neutre pour l’addition noté 0 tel que a a 0 0 a      Il existe un élément neutre pour le produit noté 1 tel que a a . 1 1 . a   P4 A chaque élément a est associé un élément a tel que :  1 a a    0 a . a  P5 Postulat d’Idempotence  a a a    a a . a  P6 Postulat d’involution 1 Georges BOOLE (1815-1864) : mathématicien et philosophe anglais. Il publia en 1854 un essai sur les raisonnements logiques portant sur les propositions auxquelles les seules réponses possibles sont oui ou non. L’ensemble des opérations découlant de ces propositions forment uns structure mathématique, donc une algèbre, dénommée « Algèbre de Boole ». 2  a a  P7 Postulat de distributivité entre opérations    c . a b . a c b . a        c . b a c a . b a     1.2 – Théorèmes Une Algèbre de Boole vérifie les théorèmes ci-dessous. T1 : Théorème d’absorption  1 1 a    0 0 . a  T2 : Théorème de De Morgan  b . a b a   et par extension z ...... c . b . a z .... c b a       b a b . a   et par extension z .... c b a z ...... c . b . a      1.3 – Identités remarquables2  a ab a    b a b . a a     Redondance : x b ax ab x b ax     1.4 – Variable booléenne Une variable booléenne est une entité qui prend ses valeurs dans l’ensemble {0, 1}. Par exemple un bouton peut être actionné (1) ou non actionné (0), un moteur peut tourner (1) ou être arrêté (0). Une variable binaire peut représenter n’importe quel dispositif binaire (contact, interrupteur, lampe, électrovanne, vérin, etc.). Convention de nommage des synonymes des « 0 » et « 1 » : ces deux valeurs peuvent être nommées de différentes façons.  Niveau logique « 1 » : Vrai, Fermé, Marche, Haut, Allumé, Oui ;  Niveau logique « 0 » : Faux, Ouvert, Arrêt, Bas, Éteint, Non. Les trois opérations élémentaires s’appliquent sur toute variable booléenne, ce qui signifie que ces opérations sont également binaires. Lorsqu’une opération élémentaire concerne plusieurs variables booléennes, on obtient une fonction booléenne. 2 – FONCTIONS LOGIQUES BOOLÉENNES On appelle fonction logique à n variables F(a,b,c,d,...,n) une application de [0,1]n dans [0,1], ce que l’on note mathématiquement par :     1 , 0 1 , 0 F n   Cela signifie encore que F prend sa valeur dans l’ensemble {0, 1}. Pour visualiser une fonction booléenne, on utilise sa table de vérité. La table de vérité est composée de 2 parties :  la partie gauche donne l’ensemble des 2n combinaisons des variables a, b, c, …, n ;  la partie droite donne la valeur 0 ou 1 de la fonction pour chacune des combinaisons. Exemple : 2 Qu’on peut démontrer à partir des postulats et théorèmes précédents 3 a b c F 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 0 1 1 0 0 1 1 1 1 2.1 – Fonctions booléennes élémentaires Ce sont les trois opérations élémentaires utilisées par l’Algèbre de Boole. 2.1.1 – Fonction ET Elle utilise l’opérateur « . ». Sa table de vérité est donnée ci-dessous. b a F1 0 0 0 0 1 0 1 0 0 1 1 1 L’appellation ET s’explique facilement. F1 ne vaut en effet 1 que si les variables a et b valent 1 simultanément. On écrit : b . a F 1  2.1.2 – Fonction OU Elle utilise l’opérateur « + ». Sa table de vérité est donnée ci-dessous. b a F2 0 0 0 0 1 1 1 0 1 1 1 1 L’appellation OU s’explique facilement. F2 vaut en effet 1 si l’une ou les deux variables a et b valent 1. On écrit :   b . a a b . a b b . a ab b . a b . a F2         soit encore : b a F2   2.1.3 – Fonction NON Elle utilise l’opérateur « ». Sa table de vérité est donnée ci-dessous. x F3 0 1 1 0 On écrit : x F3  4 2.2 – Fonctions booléennes complémentaires Les 3 fonctions ci-dessous complètent les 3 premières et permettent avec celles-ci d’élaborer toutes les fonctions booléennes complexes. 2.2.1 – Fonction OU exclusif Sa table de vérité est donnée ci-dessous. b a F4 0 0 0 0 1 1 1 0 1 1 1 0 Par rapport au Ou simple, le Ou exclusif exclut le fait que la fonction puisse valoir 1 lorsque les 2 variables valent 1. On écrit : b a b . a b . a F4     2.2.2 – Fonction NON ET (NAND) C’est le complément de la fonction ET. Sa table de vérité est donnée ci-dessous. b a F5 0 0 1 0 1 1 1 0 1 1 1 0 On écrit : b a b . a F5    2.2.3 – Fonction NON OU (NOR) C’est le complément de la fonction ET. Sa table de vérité est donnée ci-dessous. b a F6 0 0 1 0 1 0 1 0 0 1 1 0 On écrit : b . a b a F 6    2.3 – Fonctions booléennes à n variables Hormis la fonction NON, toutes les fonctions précédentes peuvent être étendues à n variables. Les fonctions à n variables sont également définies par leur table de vérité. Définition 1 : monôme booléen On appelle monôme booléen un produit de plusieurs variables booléennes complémentées ou non. Exemples : c ab , z xy w , a , etc. 5 Définition 2 : polynôme booléen On appelle polynôme booléen la somme booléenne de plusieurs monômes booléens. On démontre que toute fonction booléenne peut se mettre sous forme polynomiale. Exemple :   bc c ab b a c , b , a f    Définition 3 : forme canonique d’une fonction booléenne Lorsqu’une fonction booléenne de n variables s’écrit sous la forme d’un polynôme booléen composé uniquement de monômes complets, c'est-à-dire contenant les n variables soit sous forme directe soit sous forme complémentée, on dit que la fonction booléenne est écrite sous forme canonique. Exemple :    abc bc a c ab c b a c , b , a f     est écrite sous forme canonique puisque les 4 monômes qui la composent sont complets.  Inversement   bc c ab b a c , b , a f    n’est pas sous forme canonique. La forme canonique d’une fonction booléenne est issue directement de sa table de vérité. Remarque 1 : les monômes complets sont aussi appelés « minterms ». Toute fonction booléenne de n variables comporte 2n minterms qui sont décrits sur la partie gauche de la table de vérité. Remarque 2 uploads/s3/ chap-2-gi-fonctions-logiques-gi.pdf