16/12/2010
Algèbre de Boole
EPSTA
• • • • •
Chapitre 2 Algèbre de BOOLE
Introduction Les variables et fonctions logiques La table de vérité Les opérateurs de base et les portes logiques Les lois et les propriétés de l’algèbre de Boole – Propriétés – Théorème de Morgan
• La définition d’une fonction logique • Les formes canoniques d’une fonction logique
A.KHELASSI
[email protected]
– 1ère Forme Normale – 2ème Forme Normale
• Simplification des fonctions logiques – Méthode algébrique – par table de Karnaugh
16/12/2010 17:52
Introduction
2
Introduction
• Définit en 1847 par Georges Boole (1815-1864), physicien Anglais • Algèbre applicable au raisonnement logique qui traite des fonctions à variables binaires (deux valeurs). • Ne s'applique pas aux systèmes à plus de deux états d'équilibre. • Permet d'étudier les circuits logiques (un système logique sert à modifier des signaux). 16/12/2010 17:52
Archi1 EPSTA 2010-2011
Archi1 EPSTA 2010-2011
• L ’algèbre de Boole permet de manipuler des valeurs logiques • Une valeur logique n’a que deux états possible: Vraie(1) ou Fausse(0). • Plusieurs valeurs logiques peuvent être combinées pour donner un résultat qui est lui aussi une valeur logique
3
16/12/2010 17:52
Archi1 EPSTA 2010-2011
4
Introduction
Fonctions logique
• Les machines numériques sont constituées d’un ensemble de circuits électroniques. • Chaque circuit fournit génère une valeur logique (1ou 0) en fonction des valeurs introduite. • Ce circuit peut représenter par une fonction le modèle mathématique.
• Résultat de la combinaison (logique combinatoire) d'une ou plusieurs variables logiques reliées entre elles par des opérations logique de base : • la valeur résultante (O ou 1 ) de cette fonction dépend de la valeur des variables logiques. Une fonction logique possède 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. Exemple F = (A et B) ou C et (non D)
A
1 ou 0
Circuit
B 16/12/2010 17:52
Archi1 EPSTA 2010-2011
5
16/12/2010 17:52
Archi1 EPSTA 2010-2011
6
1
16/12/2010
Table de vérité
Fonctions logique (La table de vérité) • Les fonctions logiques peuvent être représentées par des Tables de vérités • La table de vérité permet la connaissance de la sortie (d ’un circuit logique) en fonction des diverses combinaisons des valeurs des entrées • Le nombre de colonnes est le nombre total d'entrées et de sorties • Le nombre de lignes est 2N sachant que "N" est le nombre d’entrées, • Exemple: Une fonction de 3 entrées et 1 sortie se représente par une table de 4 colonnes et 8 lignes 16/12/2010 17:52
Archi1 EPSTA 2010-2011
7
Les opérateurs de base et les portes logiques
A
B
C
F(A,B,C)
0
0
0
0
0
0
1
1
0
1
0
1
0
1
1
1
1
0
0
0
1
0
1
0
A
S(A)
1
1
0
0
1
0
1
1
1
0
0
0
16/12/2010 17:52
•3 Variables logique A,B,C •4 Colonnes et 8=23 lignes
Une variable logique 2 ligne
Archi1 EPSTA 2010-2011
8
Les opérateurs de base et les portes logiques
• Opérateur unaire (un seule variable)
• Opérateurs binaire
La négation • Non A
16/12/2010 17:52
F ( A) A
Archi1 EPSTA 2010-2011
ET / AND F(A,B)=A*B =AB=A.B
9
16/12/2010 17:52
Les opérateurs de base et les portes logiques
Archi1 EPSTA 2010-2011
10
Exemple • Un circuit électrique • 4 interrupteurs A,B,C,D (variables d’entrée ) • Une lompe L et un moteur M (variables Sortie)
Le OU, OR F(A,B)=A+B
L(A,B)= A+B M(C,D)=C.D
16/12/2010 17:52
Archi1 EPSTA 2010-2011
11
16/12/2010 17:52
Archi1 EPSTA 2010-2011
12
2
16/12/2010
Exemple de Schéma d’un circuit logique ( Logigramme)
Autre fonctions A
A B
B
Porte NAND
A B
A
B
16/12/2010 17:52
A B Porte NOR
A B Porte XOR
Archi1 EPSTA 2010-2011
13
16/12/2010 17:52
Les lois, propriétés et fondamentales de l’algèbre de Boole
Archi1 EPSTA 2010-2011
14
Théorème de Morgane
•Et d’une manière générale A.B.C...... A B C .......... A B C ........... A.B.C......
16/12/2010 17:52
Archi1 EPSTA 2010-2011
15
Étapes de conception et de réalisation d’un circuit numérique
•
Pour faire l’étude et la réalisation d’un circuit il faut suivre les étapes suivantes : 1. 2. 3. 4. 5. 6. 7.
Archi1 EPSTA 2010-2011
Archi1 EPSTA 2010-2011
16
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).
Il faut bien comprendre le fonctionnement du système. Il faut définir les variables d’entrée. Il faut définir les variables de sortie. Etablir la table de vérité. Ecrire les équations algébriques des sorties ( à partir de la table de vérité ). Effectuer des simplifications ( algébrique ou par Karnaugh). Faire le schéma avec un minimum de portes logiques.
16/12/2010 17:52
16/12/2010 17:52
• Donc il faut tirer ( déduire ) la fonction logique a partir de la description textuelle.
17
16/12/2010 17:52
Archi1 EPSTA 2010-2011
18
3
16/12/2010
Exemple : définition textuelle du fonctionnement d’un système
– 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
• Une serrure de sécurité s’ouvre en fonction de trois clés. Le fonctionnement de la serrure est définie comme suite :
• 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
– La serrure est ouverte si au moins deux clés sont utilisées. – La serrure reste fermée dans les autres cas .
– 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
Donner la fonction logique ou le schéma du circuit qui permet de contrôler l’ouverture de la serrure ? 16/12/2010 17:52
Archi1 EPSTA 2010-2011
19
16/12/2010 17:52
Archi1 EPSTA 2010-2011
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 .
Table de vérité ( Exemple )
A B
20
S=F(A,B,C) Circuit
C
A
B
C
F
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
A B C : max terme A B C : max terme A B C : max terme
16/12/2010 17:52
Archi1 EPSTA 2010-2011
21
Extraction de la fonction logique à partir de la T.V
16/12/2010 17:52
A .B.C
: min terme
A B C : max terme A .B.C
: min terme
A .B.C A .B.C
: min terme : min terme
Archi1 EPSTA 2010-2011
22
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.
• F = somme min termes
• Exemple :
F ( A, B, C) A . B . C A . B . C A . B . C A . B . C
F(A,B, C) ABC ACB ABC • F = produit des max termes
Il existent plusieurs formes canoniques : les plus utilisées sont la première et la deuxième forme .
F(A,B, C) ( A B C) (A B C)(A B C) (A B C)
16/12/2010 17:52
Archi1 EPSTA 2010-2011
23
16/12/2010 17:52
Archi1 EPSTA 2010-2011
24
4
16/12/2010
1 Première forme canonique
3.2 Deuxième forme canonique • Deuxième forme canonique (conjonctive): produit de sommes • Le produit des max termes • Conjonction de disjonctions • Exemple :
• Première forme canonique (forme disjonctive) : somme de produits • C’est la somme des min termes. • Une disjonction de conjonctions. • Exemple :
F(A,B, C) ( A B C) (A B C)(A B C) (A B C)
F ( A, B, C ) A . B . C A . B . C A . B . C A . B . C
La première et la deuxième forme canonique sont équivalentes .
•Cette forme est la forme la plus utilisée. 16/12/2010 17:52
Archi1 EPSTA 2010-2011
25
16/12/2010 17:52
Archi1 EPSTA 2010-2011
Formes normal de Shannon
26
Les formes canoniques
• 1ère forme
• 1ère forme disjonctive f ( x1 , x2 , x3 ) x1 x2 x3 f (0,0,0) x1 x2 x3 f (0,0,1) x1 x2 x3 f (0,1,0) x1 x2 x3 f (0,1,1)
F(x1,.., xi,.., xn) xi. f ( x1..,1i,...xn) xi f (x1..,0i,...xn)
x1 x2 x3 f (1,0,0) x1 x2 x3 f (1,0,1) x1 x2 x3 f (1,1,0) x1 x2 x3 f (1,1,1)
•
2ème
•
forme F(x1,..xi,.., xn) [ xi. f ( x1..0i...xn)].[xi f (x1...1i...xn)]
2ème
forme conjonctive
f ( x1, x2 , x3 ) x1 x2 x3 f (1,1,1) x1 x2 x3 f (1,1,0) x1 x2 x3 f (1,0,1) x1 x2 x3 f (1,0,0)
x1 x2 x3 f (0,1,1) x1 x2 x3 f (0,1,0) x1 x2 x3 f (0,0,1) x1 x2 x3 f (0,0,0)
16/12/2010 17:52
Archi1 EPSTA 2010-2011
27
Remarque 2
Archi1 EPSTA 2010-2011
28
Remarque 3 : déterminer F
• 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) (2,4,6) R( 010,100,110) ABC A BC ABC P(0,1,3,5,7) (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) 16/12/2010 17:52
16/12/2010 17:52
Archi1 EPSTA 2010-2011
29
A
B
C
F
F
0
0
0
0
1
0
0
1
0
1
0
1
0
0
1
0
1
1
1
0
1
0
0
0
1
1
0
1
1
0
1
1
0
1
0
1
1
1
1
0
F A.B.C A.B.C A.B.C A.B.C 16/12/2010 17:52
Archi1 EPSTA 2010-2011
30
5
16/12/2010
Exercice • Déterminer la première , la deuxième forme canonique et la fonction inverse à partir de la TV suivante ?
A 0 0 1 1
B 0 1 0 1
F 0 1 1 0
F
1 0 0 1 2ère FC
Solution A B : max terme A.B :
Simplification des fonctions logiques
min terme
A.B : min terme A B : max terme 1ème FC
F(A, B) (A B).(A B) (A.B) (A.B) 1ère FC
2ème FC
F(A, B) (A . B) (A . B) (A B).(A B) 16/12/2010 17:52
Archi1 EPSTA 2010-2011
31
Simplification algébrique
Pour quoi la simplification?
• 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 :
• 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 • Cela afin de réduire le nombre de portes logiques utilisées réduire le coût du circuit
A.B A.B B A A.B A
• Plusieurs méthodes existent pour la simplification : – La Méthode algébrique – Les Méthodes graphiques : (table de karnaugh )
( A B) ( A B) A A . ( A B) A
A A.B A B
A . (A B) A . B 16/12/2010 17:52
Archi1 EPSTA 2010-2011
33
Rappel
16/12/2010 17:52
Archi1 EPSTA 2010-2011
34
Règles pour la simplification algébrique • Règles 1 : regrouper des termes à l’aide des règles précédentes • Exemple 1
ABC ABC A BCD AB (C C) A BCD AB A BCD A ( B B (CD)) A ( B CD) AB ACD 16/12/2010 17:52
Archi1 EPSTA 2010-2011
35
16/12/2010 17:52
Archi1 EPSTA 2010-2011
Distributivité A A.B A B
Distributivité
36
6
16/12/2010
• Règles 3 : il est possible de supprimer un terme
• Règles 2 : Rajouter un terme déjà existant à une expression
superflu ( un terme en plus ), c’est-à-dire déjà inclus dans la réunion des autres termes.
• Exemple :
• Exemple 1 : 1
A B C ABC A BC ABC
F(A, B, C) A B BC AC AB BC AC ( B B)
ABC ABC ABC A BC ABC ABC BC AC AB
AB BC ACB A BC 1
1
Distributivité
AB ( 1 C) BC (1 A) AB BC
Rappel
A+A=A
A A 1 16/12/2010 17:52
Archi1 EPSTA 2010-2011
37
Exemple 2 : il existe aussi la forme conjonctive du terme superflu
16/12/2010 17:52
Archi1 EPSTA 2010-2011
38
• Règles 4 : il est préférable de simplifier la forme canonique ayant le nombre de termes minimum.
F(A, B, C) (A B) . (B C) . (A C)
• Exemple :
0
(A B) . (B C) . (A C B.B)
Distributivité
(A B) . (B C) . (A C B) .(A C B)
F ( A, B, C ) R(2,3,4,5,6,7)
(A B) . (A C B) . (B C) .(A C B)
F(A, B, C) R( 0,1) A . B . C A . B . C
(A B) . (B C)
commutativité
MIN <2n/2 1
A . B (C C) A.B A B
Rappel
A . ( A B) A
16/12/2010 17:52
Distributivité Morgan
F(A, B, C) F(A, B, C) A B A B
Archi1 EPSTA 2010-2011
39
16/12/2010 17:52
Archi1 EPSTA 2010-2011
40
Les termes adjacents •Examinons l’expression suivante :
A.B A.B
Simplification graphique (la table de Karnaugh)
•Les deux termes possèdent les même variables. La seule différence est l’état de la variable B qui change. •Si on applique les règles de simplification on obtient :
AB AB A( B B) A •Ces termes sont dites adjacents. 16/12/2010 17:52
Archi1 EPSTA 2010-2011
41
16/12/2010 17:52
Archi1 EPSTA 2010-2011
42
7
16/12/2010
La table de karnaugh
Exemple de termes adjacents Ces termes sont adjacents
•La méthode de Karnaugh se base sur la règle précédente.
A.B A.B B
• La méthode consiste a mettre en évidence par une méthode graphique (un tableaux ) tous les termes qui sont adjacents (qui ne différent que par l’état d’une seule variable).
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
•La méthode peut s’appliquer aux fonctions logiques de 2,3,4,5 et 6 variables.
A.B A.B
•Un tableau de Karnaugh comportent 2n cases ( N est le nombre de variables ).
A.B.C A.B.C A.B.C.D A.B.C.D 16/12/2010 17:52
Archi1 EPSTA 2010-2011
43
16/12/2010 17:52
Archi1 EPSTA 2010-2011
44
Tableau à 4 variables A
AB
AB
B
0
C
1
00
01
11
CD
10
00
0
0
00
1
1
01
01
11
10
11
Tableau à 2 variables
16/12/2010 17:52
Tableaux à 3 variables
Archi1 EPSTA 2010-2011
10
45
16/12/2010 17:52
AB
AB
00
01
11
10
CD
00
00
01
01
11
11
10
10
U=0 16/12/2010 17:52
AB
00
46
Dans un tableau de karnaugh , chaque case possède un certain nombre de cases adjacentes.
Tableau à 5 variables
CD
Archi1 EPSTA 2010-2011
01
11
10
C
AB
00
01
11
10
CD
00
0
00
1
01
01
11
10
11 Les trois cases bleues sont des cases adjacentes à la case rouge
10
U= 1 Archi1 EPSTA 2010-2011
47
16/12/2010 17:52
Archi1 EPSTA 2010-2011
48
8
16/12/2010
Exemple :
Passage de la table de vérité à la table de Karnaugh
•Pour chaque combinaisons qui représente un min terme lui correspond une case dans le tableau qui doit être mise à 1 . •Pour chaque combinaisons qui représente un max terme lui correspond une case dans le tableau qui doit être mise à 0 . • Lorsque on remplis le tableau , on doit soit prendre les min terme ou les max terme
16/12/2010 17:52
Archi1 EPSTA 2010-2011
49
A
B
C
S
0
0
0
0
0
0
1
0
0
1
0
0
0
1
1
1
1
0
0
0
1
0
1
1
1
1
0
1
1
1
1
1
AB C
00
01
1
16/12/2010 17:52
1
1
1
Archi1 EPSTA 2010-2011
50
AB
• Si la fonction logique est donnée sous la première forme canonique ( disjonctive), alors sa représentation est directe : pour chaque terme lui correspond une seule case qui doit être mise à 1. • Si la fonction logique est donnée sous la deuxième forme canonique ( conjonctive), alors sa représentation est directe : pour chaque terme lui correspond une seule case qui doit être mise à 0 .
C
F1(A,B, C) (1,2,5,7)
00 0 1
51
01
11
10
1
1
10
1 1
AB C
F2(A,B, C) (0,2,3,6)
0
00
01
11
0
0
0
1
Archi1 EPSTA 2010-2011
10
1
Exemple
Passage de la forme canonique à la table de Karnaugh
16/12/2010 17:52
11
0
16/12/2010 17:52
0
Archi1 EPSTA 2010-2011
52
•Puisque il existent encore des cases qui sont en dehors d’un regroupement on refait la même procédure : former des regroupements.
Méthode de simplification (Exemple : 3 variables ) •L’idée de base est d’essayer de regrouper (faire des regroupements ) les cases adjacentes qui comportent des 1 ( rassembler les termes adjacents ).
•Une case peut appartenir à plusieurs regroupements
•Essayer de faire des regroupements avec le maximum de cases ( 16,8,4 ou 2 ) •Dans notre exemple on peut faire uniquement des regroupements de 2 cases . AB C
00
01
0 1
16/12/2010 17:52
01
0
AB C
ABC ABC AB
00
11
10
1
1
1
ABC ABC AB
1
11
10
1 1
1
1
ABC ABC AC
1
Archi1 EPSTA 2010-2011
53
16/12/2010 17:52
Archi1 EPSTA 2010-2011
54
9
16/12/2010
Donc , en résumé pour simplifier une fonction par la table de karnaugh il faut suivre les étapes suivantes :
•On s’arrête lorsque il y a plus de 1 en dehors des regroupements •La fonction final est égale à la réunion ( somme ) des termes après simplification.
1. Remplir le tableau à partir de la table de vérité ou à partir de la forme canonique. 2. Faire des regroupements : des regroupements de 16,8,4,2,1 cases ( Les même termes peuvent participer à plusieurs regroupements ) . 3. Dans un regroupement :
AB C
00
01
0
11
10
ABC ABC AB
1
1
1
1
1
ABC ABC AC
ABC ABC BC
5. L’expression logique finale est la réunion ( la somme ) des groupements après simplification et élimination des variables qui changent d’état.
F ( A, B, C ) AB AC BC 16/12/2010 17:52
Archi1 EPSTA 2010-2011
Qui contient un seule terme on peut pas éliminer de variables. Qui contient deux termes on peut éliminer une variable ( celle qui change d’état ). Qui contient 4 termes on peut éliminer 2 variables. Qui contient 8 termes on peut éliminer 3 variables. Qui contient 16 termes on peut éliminer 4 variables.
55
16/12/2010 17:52
Exemple 1 : 3 variables
Archi1 EPSTA 2010-2011
56
Exemple 2 : 4 variables AB CD
AB C
00
01
0
11
1
1
1
1
1
00
01
11
10
00
10
01
1
1 1
1
1
1
11
F ( A, B, C, D) C.D A.B.C A.B.C.D
10
1
F ( A, B, C ) C AB 16/12/2010 17:52
Archi1 EPSTA 2010-2011
57
16/12/2010 17:52
AB
AB
00
CD
00
11
10
1
00
1
01
1
1 11
11
1 10
1
1
AB
00
1 1
F ( A, B, C, D) AB B D BCD
10
01
1
01
58
Exemple 4 : 5 variables
Exemple 3 : 4 variables
CD
Archi1 EPSTA 2010-2011
01
1 1
11
10
CD
00
01
11
10
00
1
1
01
1
1
1
11
1
1
10
1
U=0
1 U= 1
F(A,B, C, D, U) A B A.B.D.U A.C.D.U A.B.D.U 16/12/2010 17:52
Archi1 EPSTA 2010-2011
59
16/12/2010 17:52
Archi1 EPSTA 2010-2011
60
10
