Algèbre de boole

50 %
50 %
Information about Algèbre de boole
Education

Published on March 2, 2014

Author: linuxscout

Source: slideshare.net

Description

Circuits logiques
rappel sur l'algèbre de BOOLE

Module: Architecture des ordinateurs 1ère MI S2 Circuits Logiques ‫الدارات النطقية‬ Taha Zerrouki Taha.zerrouki@gmail.com 1

Module: Architecture des ordinateurs 1ère MI S2 Circuits Logiques ‫الدارات النطقية‬ Taha Zerrouki Taha.zerrouki@gmail.com 2

Plan • Algèbre de Boole • Portes Logiques 3

Algèbre de Boole 4

L'algèbre de Boole • L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques, de la logique et de l'électronique qui s'intéresse aux opérations et aux fonctions sur les variables logiques. 5

Boole • Elle fut initiée en 1854 par le mathématicien britannique George Boole 6

1. Introduction • Les machines numériques sont constituées d’un ensemble de circuits électroniques. • Chaque circuit fournit une fonction logique bien déterminée ( addition, comparaison ,….). A Circuit F(A,B) B La fonction F(A,B) peut être : la somme de A et B , ou le résultat de la comparaison de A et B ou une autre fonction 7

• Pour concevoir et réaliser ce circuit on doit avoir un modèle mathématique de la fonction réalisée par ce circuit . • Ce modèle doit prendre en considération le système binaire. • Le modèle mathématique utilisé est celui de Boole. 8

3.3. Fonction logique • C’est une fonction qui relie N variables logiques avec un ensemble d’opérateurs logiques de base. • Dans l’Algèbre de Boole il existe trois opérateurs de base : NON , ET , OU. • La valeur d’une fonction logique est égale à 1 ou 0 selon les valeurs des variables logiques. • Si une fonction logique possède N variables logiques  2n combinaisons  la fonction possède 2n valeurs. • Les 2n combinaisons sont représentées dans une table qui s’appelle table de vérité ( TV ). 9

Fonction logique V1 V2 V3 V4 V5 ... F(V1,V2,…..Vn) Vrai Faut 10

Exemple d’une fonction logique F ( A, B, C ) = A.B.C + A.B.C + A.B.C + A.B.C La fonction possède 3 variables  23 combinaisons F C B A 0 0 0 1 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 0 0 1 1 1 Une table de vérité 0 1 1 1 11

Priorité des opérateurs • Pour évaluer une expression logique : () NON ET OU ‫أولوية العوامل‬ 12

F(A, B, C) = (A . B) . ( C + B) + A.B.C si on veut calculer F(0,1,1) alors : F(0,1,1) = (0.1)(1 + 1) + 0.1.1 F(0,1,1) = (0 ) (1 ) + 0.0.1 F(0,1,1) = 1.1 + 0.0.1 F(0,1,1) = 1 + 0 F(0,1,1) = 1 13

Priorité des opérateurs F(A, B, C) = (A . B) . ( C + B) + A.B.C Calculer F(0,1,1) 14

Priorité des opérateurs F(A, B, C) = (A . B) . ( C + B) + A.B.C si on veut calculer F(0,1,1) alors : F(0,1,1) = (0.1)(1 + 1) + 0.1.1 F(0,1,1) = (0 ) (1 ) + 0.0.1 F(0,1,1) = 1.1 + 0.0.1 F(0,1,1) = 1 + 0 F(0,1,1) = 1 15

Table de vérité • Tracer la table de vérité de F(A,B,C) F(A, B, C) = (A . B) . ( C + B) + A.B.C 16

Solution •Pour trouver la table de vérité , il faut trouver la valeur de la fonction F pour chaque combinaisons des trois variables A, B , C •3 variables  2 3 = 8 combinaisons F(A, B, C) = (A . B) . ( C + B) + A.B.C F C B A 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 F(1,1,0) = ( 1. 1) .(0 + 1) + 1 . 1 .0 = 0 0 0 1 1 F(1,1,1) = ( 1. 1) .(1 + 1) + 1 . 1 .1 = 0 0 1 1 1 F(0,0,0) = ( 0. 0) .(0 + 0) + 0 . 0 .0 = 0 F(0,0,1) = ( 0. 0) .(1 + 0) + 0 . 0 .1 = 1 F(0,1,0) = ( 0. 1) .(0 + 1) + 0 . 1 .0 = 1 F(0,1,1) = ( 0. 1) .(1 + 1) + 0 . 1 .1 = 1 F(1,0,0) = ( 1. 0) .(0 + 0) + 1 . 0 .0 = 0 F(1,0,1) = ( 1. 0) .(1 + 0) + 1 . 0 .1 = 1 17

4.5 Lois fondamentales de l’Algèbre de Boole •L’opérateur NON A= A A+ A = 1 A. A = 0 18

•L’opérateur ET ( A.B ).C = A.( B.C ) = A.B.C Associativité A.B = B. A Commutativité A. A = A A.1 = A Idempotence Elément neutre A.0 = 0 Elément absorbant 19

• L’opérateur OU ( A + B) + C = A + ( B + C ) = A + B + C A+ B = B + A A+ A = A Associativité Commutativité Idempotence A+ 0 = A A+ 1= 1 Elément neutre Elément absorbant 20

•Distributivité A . ( B + C ) = ( A . B ) + ( A . C ) Distributivité du ET sur le OU A + ( B . C ) = (A + B).(A + C) Distributivité du OU sur le ET •Autres relations utiles A + ( A.B) = A A. ( A + B) = A (A + B) . (A + B) = A A + A.B= A + B 21

5. Dualité de l’algèbre de Boole • Toute expression logique reste vrais si on remplace le ET par le OU , le OU par le ET , le 1 par 0 , le 0 par 1. • Exemple : A + 1= 1 → A.0 = 0 A + A = 1→ A.A = 0 ‫التقابل‬ 22

Théorème de DE-MORGANE 23

6. Théorème de DE-MORGANE •La somme logique complimentée de deux variables est égale au produit des compléments des deux variables. A+ B = A . B • Le produit logique complimenté de deux variables est égale au somme logique des compléments des deux variables. A.B = A + B 24

6.1 Généralisation du Théorème DEMORGANE à N variables A.B.C...... = A + B + C + .......... A + B + C + ........... = A.B.C...... ‫مجوم الجتام = مجووع الوجووع‬ ‫مجوم الوجووع = متام الوجووع‬ 25

Autres opérateurs logiques 26

OU exclusif ( XOR) F ( A, B) = A ⊕ B A ⊕ B = A.B + A.B 27

NAND ( NON ET ) F(A, B) = A . B F ( A, B ) = A ↑ B 28

NOR ( NON OU ) F(A, B) = A + B F ( A, B ) = A ↓ B 29

7.4 NAND et NOR sont des opérateurs universels • En utilisant les NAND et les NOR on peut exprimer n’importe qu’elle expression ( fonction ) logique. • Pour cela , Il suffit d’exprimer les opérateurs de base ( NON , ET , OU ) avec des NAND et des NOR. 30

7.4.1 Réalisation des opérateurs de base avec des NOR A = A+ A = A↓ A A + B = A + B = A ↓ B = (A ↓ B) ↓ (A ↓ B) A.B = A.B = A + B = A ↓ B = (A ↓ A) ↓ (B ↓ B) 31

Exercice • Exprimer le NON , ET , OU en utilisant des NAND ? 32

7.4.3 Propriétés des opérateurs NAND et NOR A↑ 0= 1 A↓ 0= A A↑ 1= A A↓ 1= 0 A↑ B = B↑ A A↓ B = B↓ A ( A ↑ B) ↑ C ≠ A ↑ ( B ↑ C ) ( A ↓ B) ↓ C ≠ A ↓ ( B ↓ C ) 33

Étude d’une fonction logique 34

Étude d’une fonction logique • • • • • Définition textuelle d’une fonction logique Les entrées et les sorties ‫دراسة دالة منطقية‬ Table de vérité ،‫ تعريف‬Formes algébriques ‫ الوتاخل والوخعرج‬Simplification: ،‫- متول الحقيقة‬ – Algébrique – Table de Karnaugh ،‫- شكل مبري‬ • Logigramme ،‫ تبسيط‬35 ‫- رسم الوخطط‬

1. Définition textuelle d’une fonction logique • Généralement la définition du fonctionnement d’un système est donnée sous un format textuelle . • Pour faire l’étude et la réalisation d’un tel système on doit avoir son modèle mathématique (fonction logique). • Donc il faut tirer ( déduire ) la fonction logique a partir de la description textuelle. 36

Exemple : définition textuelle du fonctionnement d’un système • Une serrure de sécurité s’ouvre en fonction de trois clés. Le fonctionnement de la serrure est définie comme suite : – La serrure est ouverte si au moins deux clés sont utilisées. – La serrure reste fermée dans les autres cas . Donner la schéma du circuit qui permet de contrôler l’ouverture de la serrure ? 37

Si on reprend l’exemple de la serrure : – Le système possède trois entrées : chaque entrée représente une clé. – On va correspondre à chaque clé une variable logique: clé 1  A , la clé 2  B , la clé 3  C • Si la clé 1 est utilisée alors la variable A=1 sinon A =0 • Si la clé 2 est utilisée alors la variable B=1 sinon B =0 • Si la clé 3 est utilisée alors la variable C=1 sinon C =0 – Le système possède une seule sortie qui correspond à l’état de la serrure ( ouverte ou fermé ). – On va correspondre une variable S pour designer la sortie : • S=1 si la serrure est ouverte , • S=0 si elle est fermée 38

S=F(A,B,C) F(A,B,C)= 1 si au mois deux clés sont introduites F(A,B,C)=0 si non . A B Circuit S=F(A,B,C) C Remarque : Il est important de préciser aussi le niveau logique avec lequel on travail ( logique positive ou négative ). 39

2. Table de vérité ( Rappel ) • Si une fonction logique possède N variables logiques  2n combinaisons  la fonction possède 2n valeurs. • Les 2n combinaisons sont représentées dans une table qui s’appelle table de vérité. 40

2. Table de vérité ( Exemple ) S C B A 0 0 0 0 A + B + C : max terme 0 1 0 0 A + B + C : max terme 0 0 1 0 A + B + C : max terme 1 1 1 0 A .B.C 0 0 0 1 A + B + C : max terme 1 1 0 1 A .B.C : min terme 1 0 1 1 1 1 1 1 A .B.C A .B.C : min terme : min terme : min terme 41

2.3 Extraction de la fonction logique à partir de la T.V • F = somme min termes F ( A, B, C ) = A . B . C + A . B . C + A . B . C + A . B . C • F = produit des max termes F(A, B, C) = ( A + B + C) (A + B + C)(A + B + C) (A + B + C) 42

3. Forme canonique d’une fonction logique • On appel forme canonique d’une fonction la forme ou chaque terme de la fonction comportent toutes les variables. • Exemple : F(A, B, C) = ABC + A CB + ABC 43

3.1 Première forme canonique • Première forme canonique (forme disjonctive) : somme de produits • C’est la somme des min termes. F ( A, B, C ) = A . B . C + A . B . C + A . B . C + A . B . C •Cette forme est la forme la plus utilisée. 44

3.2 Deuxième forme canonique • Deuxième forme canonique (conjonctive): produit de sommes • Le produit des max termes F(A, B, C) = ( A + B + C) (A + B + C)(A + B + C) (A + B + C) 45

• 1ère Forme  2ème forme 46

Remarque 1 • On peut toujours ramener n’importe qu’elle fonction logique à l’une des formes canoniques. • Cela revient à rajouter les variables manquants dans les termes qui ne contiennent pas toutes les variables ( les termes non canoniques ). • Cela est possible en utilisant les règles de l’algèbre de Boole : – Multiplier un terme avec une expression qui vaut 1 – Additionner à un terme avec une expression qui vaut 0 – Par la suite faire la distribution 47

Exemple : 1. F(A, B) = A + B = A (B + B) + B( A + A) = AB + A B + AB + AB = AB + A B + AB 2. F(A, B, C) = AB + C = AB(C + C) + C( A + A) = ABC + ABC + AC + AC = ABC + ABC + AC(B + B) + AC (B + B) = ABC + ABC + ABC + A BC + ABC + A BC = ABC + ABC + A BC + A B C + A B C 48

Remarque 2 • Il existe une autre représentation des formes canoniques d’une fonction , cette représentation est appelée forme numérique. • R : pour indiquer la forme disjonctive • P : pour indiquer la forme conjonctive. Exemple : si on prend une fonction avec 3 variables R( 2,4,6) = ∑ P(0,1,3,5,7) = (2,4,6) = R( 010,100,110) = ABC + A BC + ABC ∏ (0,1,3,5,7) = P(000,001,011,101,111) = (A + B + C)(A + B + C) (A + B + C ) (A + B + C ) (A + B + C) 49

Remarque 3 : déterminer F F C B FA 1 0 0 0 0 1 0 1 0 0 1 0 0 1 0 0 1 1 1 0 1 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 1 F = A.B.C + A.B.C + A.B.C + 50 .B.C A

Exercice 1 • Déterminer la première , la deuxième forme canonique et la fonction inverse à partir de la TV suivante ? Tracer le logigramme de la fonction ? F 0 1 1 0 B 0 1 0 1 A 0 0 1 1 51

Exercice 2 • Faire le même travail avec la T.V suivante : S C B A 0 0 0 0 1 1 0 0 1 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 52

Simplification des fonctions logiques 53

4. Simplification des fonctions logiques • L’objectif de la simplification des fonctions logiques est de : – réduire le nombre de termes dans une fonction – et de réduire le nombre de variables dans un terme 54

4. Simplification des fonctions logiques • Cela afin de réduire le nombre de portes logiques utilisées  réduire le coût du circuit • Plusieurs méthodes existent pour la simplification : – La Méthode algébrique – Les Méthodes graphiques : ( ex : table de karnaugh ) – Les méthodes programmables 55

5. Méthode algébrique • Le principe consiste à appliquer les règles de l’algèbre de Boole afin d’éliminer des variables ou des termes. • Mais il n’y a pas une démarche bien spécifique. • Voici quelques règles les plus utilisées : A.B+ A.B= B A + A.B= A A + A.B= A + B ( A + B) ( A + B) = A A . ( A + B) = A A . ( A + B) = A . B 56

5.1 Règles de simplification • Règles 1 : regrouper des termes à l’aide des règles précédentes • Exemple ABC + ABC + A BCD = AB (C + C) + A BCD = AB + A BCD = A ( B + B (CD)) = A ( B + CD) = AB + ACD 57

• Règles 2 : Rajouter un terme déjà existant à une expression • Exemple : A B C + ABC + A BC + ABC = ABC + ABC + ABC + A BC + ABC + ABC = BC + AC + AB 58

• Règles 3 : il est possible de supprimer un terme superflu ( un terme en plus ), c’est-àdire déjà inclus dans la réunion des autres termes. Exemple 1 : F(A, B, C) = A B + BC + AC = AB + BC + AC ( B + B) = AB + BC + ACB + A BC = AB ( 1 + C) + BC (1 + A) = AB + BC 59

Exemple 2 : il existe aussi la forme conjonctive du terme superflu F(A, B, C) = (A + B) . (B + C) . (A + C) = (A + B) . (B + C) . (A + C + B.B) = (A + B) . (B + C) . (A + C + B) .(A + C + B) = (A + B) . (A + C + B) . (B + C) .(A + C + B) = (A + B) . (B + C) 60

• Règles 4 : il est préférable de simplifier la forme canonique ayant le nombre de termes minimum. • Exemple : F ( A, B, C ) = R ( 2,3,4,5,6,7) F(A, B, C) = R( 0,1) = A . B . C + A . B . C = A . B (C + C) = A.B= A + B F(A, B, C) = F(A, B, C) = A + B = A + B 61

Exercice Démontrer la proposition suivante : A.B + B.C + A.C + A.B.C + A.B.C + A.B.C = A + B + C Donner la forme simplifiée de la fonction suivante : F ( A, B, C , D) = ABCD + A BCD + ABC D + ABC D + ABCD 62

Simplification par la table de Karnaugh 63

Les termes adjacents •Examinons l’expression suivante : A.B+ A.B AB + A B = A( B + B ) = A •Ces termes sont dites adjacents. ‫متجاورة‬ ‫حدود‬ 64

Exemple de termes adjacents Ces termes sont adjacents A.B + A.B = B A.B.C + A.B.C = A.C A.B.C.D + A.B.C.D = A.B.D Ces termes ne sont pas adjacents A.B + A.B A.B.C + A.B.C A.B.C.D + A.B.C.D 65

Table de karnaugh •La méthode de Karnaugh se base sur la règle précédente. • Méthode graphique pour detecter tous les termes adjacents 66

A B 1 AB C 10 0 11 01 00 0 0 1 1 Tableau à 2 variables Tableaux à 3 variables 67

Tableau à 4 variables AB CD 10 11 01 00 00 01 11 10 68

Tableau à 5 variables AB CD 10 11 01 AB CD 10 00 11 01 00 00 01 01 11 11 10 U=0 00 10 U= 1 69

TV => Karnaugh S C B A 0 0 0 0 0 1 0 0 0 0 1 0 1 1 1 0 0 0 0 1 1 1 0 1 1 0 1 1 1 1 1 1 AB C 10 11 01 00 0 1 1 1 1 1 70

Exemple 1 : 3 variables AB C 10 11 01 00 0 1 1 1 1 1 1 F ( A, B, C ) = C + AB 71

Exemple 2 : 4 variables AB CD 10 11 01 00 00 1 1 1 1 1 01 11 1 10 F ( A, B, C , D ) = C.D + A.B.C + A.B.C.D 72

Exemple 3 : 4 variables AB CD 10 11 01 1 1 00 1 1 01 1 11 1 1 00 1 10 F ( A, B, C , D) = A B + B D + BC D 73

Exemple 4 : 5 variables AB CD 10 11 01 AB CD 10 00 1 1 01 1 1 11 1 10 01 00 1 11 U=0 00 1 00 1 1 01 1 1 11 1 10 1 U= 1 F(A, B, C, D, U) = A B + A.B.D.U + A.C.D.U + A.B.D.U 74

Exercice Trouver la forme simplifiée des fonctions à partir des deux tableaux ? AB CD 10 AB C 10 11 01 1 1 1 1 1 00 1 11 01 1 00 1 0 1 00 01 1 11 1 1 1 75 1 10

Fonction non totalement définie ‫دالة تعريفها ناقص‬ 76

6.5 Cas d’une fonction non totalement définie • Examinons l’exemple suivant : Une serrure de sécurité s’ouvre en fonction de quatre clés A, B, C D. Le fonctionnement de la serrure est définie comme suite : S(A,B,C,D)= 1 si au moins deux clés sont utilisées S(A,B,C,D)= 0 sinon Les clés A et D ne peuvent pas être utilisées en même temps. •On remarque que si la clé A et D sont utilisées en même temps l’état du système n’est pas déterminé. •Ces cas sont appelés cas impossibles ou interdites  comment représenter ces cas dans la table de vérité ?. 77

S D C B A 0 0 0 0 0 0 1 0 0 0 •Les cas impossibles sont représentées 0 0 1 0 0 aussi par des X dans la table de karnaugh 1 1 1 0 0 0 0 0 1 0 1 1 0 1 0 1 0 1 1 0 1 1 1 1 0 0 0 0 0 1 X 1 0 0 1 1 0 1 0 1 X 1 1 0 1 1 0 0 1 1 X 1 0 1 1 1 0 1 1 1 X 1 1 78 1 1 •Pour les cas impossibles ou interdites il faut mettre un X dans la T.V . AB CD 10 11 01 00 00 1 X X 1 X X 1 01 1 1 1 1 11 10

• Il est possible d’utiliser les X dans des regroupements : – Soit les prendre comme étant des 1 – Ou les prendre comme étant des 0 • Il ne faut pas former des regroupement qui contient uniquement des X AB CD 10 11 01 00 00 1 X X X X 1 1 1 01 1 1 1 11 10 AB 79

AB CD 10 11 01 00 00 1 X X X X 1 1 1 01 1 1 1 11 10 AB + CD 80

AB CD 10 11 01 00 00 1 X X X X 1 1 1 1 01 1 1 11 10 AB + CD + BD 81

AB CD 10 11 01 00 00 1 X X X X 1 1 1 01 1 1 1 11 10 AB + CD + BD + AC 82

AB CD 10 11 01 00 00 1 X X X X 1 1 1 01 1 1 1 11 10 AB + CD + BD + AC + BC 83

Exercice 1 Trouver la fonction logique simplifiée à partir de la table suivante ? AB CD 10 11 01 X 1 1 X 00 00 1 01 1 X 1 11 X 1 X 10 84

Circuits de Base 85

Inverseur (NON) 86

Conjonction ET (AND) 87

Disjonction (OU) (OR) 88

Circuits combinés 89

7.3 NOR ( NON OU ) F(A, B) = A + B F ( A, B ) = A ↓ B 90

Non-OU (NAND) 91

7.2 NAND ( NON ET ) F(A, B) = A . B F ( A, B ) = A ↑ B 92

NON-ET (Nand) 93

OU exclusif (XOR) F ( A, B) = A ⊕ B A ⊕ B = A.B + A.B 94

OU exclusif (XOR) 95

Exercice 1 • Donner le logigramme des fonctions suivantes : F(A, B) = A.B + A.B F(A, B, C) = (A + B).(A + C).(B + C) F(A, B, C) = (A . B) . ( C + B) + A.B.C 96

Exercice 2 : Donner l’équation de F ? 97

Add a comment

Related presentations

Related pages

Algèbre de Boole (logique) — Wikipédia

L'algèbre de Boole, ou calcul booléen, est la partie des mathématiques qui s'intéresse à une approche algébrique de la logique, vue en termes de ...
Read more

Algèbre de Boole

21 Algèbre de Boole oerge Boole (1815-1864), mathématicien autodidacte anglais, a développé une algèbre permettant de manipuler les propositions ...
Read more

Álgebra de Boole - Wikipedia, la enciclopedia libre

Álgebra de Boole (también llamada álgebra booleana), en informática y matemática es una estructura algebraica que esquematiza las operaciones lógicas ...
Read more

OpenClassrooms - L'algèbre de Boole

Nous allons dans ce tuto étudier l'algèbre de boole. Derrière ce nom barbare se cache en fait quelque chose que tout programmeur, même débutant ...
Read more

Algèbre de Boole (structure) — Wikipédia

En mathématiques, une algèbre de Boole, ou parfois anneau de Boole, est une structure algébrique étudiée en particulier en logique mathématique.
Read more

Algèbre de Boole. Tableau de Karnaugh.

L'application construit le tableau de Karnaugh de la fonction booléenne et l'écrit sous forme normale disjonctive de la fonction. En outre l'application ...
Read more

Algèbre de Boole - CCM - Comment Ça Marche - Communauté ...

Qu'appelle-t-on algèbre de Boole? Un processeur est composé de transistors permettant de réaliser des fonctions sur des signaux numériques.
Read more

ALGEBRE DE BOOLE : 2# proprietés de base - YouTube

ALGEBRE DE BOOLE : 5# 1er forme canonique (disjonctife) en darija - Duration: 8:28. ENJOY STUDYING 2,829 views. 8:28 Table de Karnaugh - ...
Read more

Algebra de Boole - YouTube

Algebra Booleana YouTube - Duration: 10:33. profesorparticular09 190,687 ... Algebra de Boole Simplificação de Expressões Booleanas 1 ...
Read more

Excercices Avec Corriges Algebre de Boole

Architecture des ordinateurs Corrigé du TD 3 : Algèbre de Boole. Arnaud Giersch, Benoît Meister et Frédéric Vivien 1. Montrer comment l’opérateur ...
Read more