Upload
hadien
View
220
Download
2
Embed Size (px)
Citation preview
RRéévisionsvisionsLogique combinatoireLogique combinatoire
lundi 22 flundi 22 féévrier 2010vrier 2010
Fonctions logiques de base
Georges BOOLE
Algèbre de Boole : relations particulières
Algèbre de Boole : théorème de DE MORGAN
Algèbre de Boole : Recherche d’équation
Algèbre de Boole : création d’un logigramme
Algèbre de Boole : Tableau de Karnaugh
OU
ET
NON-OU (NOR)
NON-ET (NAND)
NOR Exclusif
OU Exclusif
Fonctions logiques de baseFonctions logiques de base
�� Fonction ETFonction ET
Se1 e2
&e1
e2S
0
0
0
0
1
11
1
• Pour que la sortie S soit à 0 :Il suffit qu’au moins une entrée soit à 0 �
• Pour que la sortie S soit à 1 :Il faut que les entrées e1 ET e2 soient à 1 �
•Equation booléenne:
1
0
0
0
S = e1 . e2
Diapo suiv
Fonctions logiques de baseFonctions logiques de base
�� Fonction ETFonction ET
Se1 e2
&e1
e2S
0
0
0
0
1
11
1
• Pour que la sortie S soit à 0 :Il suffit qu’au moins une entrée soit à 0 �
• Pour que la sortie S soit à 1 :Il faut que les entrées e1 ET e2 soient à 1 � 1
0
0
0
S = e1 . e2•Equation booléenne:
� Menu
Fonctions logiques de baseFonctions logiques de base
�� Fonction NONFonction NON--ET (NAND)ET (NAND)
Se1 e2
0
0
0
0
1
11
1
• Pour que la sortie S soit à 0 :
Il suffit qu’au moins une entrée soit à 0 �
• Pour que la sortie S soit à 1 :
Il faut que les entrées e1 ET e2 soient à 1 �
•Equation booléenne:
0
1
1
1
S = e1 . e2
&e1
e2 S&e1
e2 S
S = e1 + e2
1
0
0
0
Diapo suiv
Fonctions logiques de baseFonctions logiques de base
�� Fonction NONFonction NON--ET (NAND)ET (NAND)
Se1 e2
0
0
0
0
1
11
1
• Pour que la sortie S soit à 0 :
Il suffit qu’au moins une entrée soit à 0 �
• Pour que la sortie S soit à 1 :
Il faut que les entrées e1 ET e2 soient à 1 �
•Equation booléenne:
0
1
1
1
S = e1 . e2
&e1
e2 S&e1
e2 S
S = e1 + e2� Menu
Fonctions logiques de baseFonctions logiques de base
�� Fonction OUFonction OU
Se1 e2
0
0
0
0
1
11
1
• Pour que la sortie S soit à 0 :Il suffit qu’au moins une entrée soit à 0 �
• Pour que la sortie S soit à 1 :Il suffit qu’au moins une entrée soit à 1 �
•Equation booléenne:
1
0
1
1
S = e1 + e2
>1e1
e2S
Diapo suiv
Fonctions logiques de baseFonctions logiques de base
�� Fonction OUFonction OU
Se1 e2
0
0
0
0
1
11
1
• Pour que la sortie S soit à 0 :Il suffit qu’au moins une entrée soit à 0 �
• Pour que la sortie S soit à 1 :Il suffit qu’au moins une entrée soit à 1 �
•Equation booléenne:
1
0
1
1
S = e1 + e2
>1e1
e2S
� Menu
Fonctions logiques de baseFonctions logiques de base
�� Fonction NONFonction NON--OU (NOR)OU (NOR)
Se1 e2
0
0
0
0
1
11
1• Pour que la sortie S soit à 0 :
Il suffit qu’au moins une entrée soit à 1
• Pour que la sortie S soit à 1 :
Il faut que les entrées e1 ET e2 soient à 0 �
•Equation booléenne:
0
1
0
0
S = e1 + e2
S = e1 . e2
1
0
1
1
>1e1
e2S>1
e1
e2S
Diapo suiv
Fonctions logiques de baseFonctions logiques de base
�� Fonction NONFonction NON--OU (NOR)OU (NOR)
Se1 e2
0
0
0
0
1
11
1• Pour que la sortie S soit à 0 :
Il suffit qu’au moins une entrée soit à 1
• Pour que la sortie S soit à 1 :
Il faut que les entrées e1 ET e2 soient à 0 �
•Equation booléenne:
0
1
0
0
S = e1 + e2
S = e1 . e2
>1e1
e2S>1
e1
e2S
� Menu
Fonctions logique de baseFonctions logique de base
�� Fonction OU ExclusifFonction OU Exclusif =1e1
e2S
• Pour que la sortie soit à 0 :
Il faut que e1 OU e2 soit à 1 mais pas les 2
• Pour que la sortie soit à 1 :
Il faut que les entrées soient au même niveau logique
S = e1 + e2
Se1 e2
0
0
0
0
1
11
1 1
1
0
0
S = e1.e2 + e1.e2
Intérêt :
Diapo suiv
Fonctions logique de baseFonctions logique de base
�� Fonction OU ExclusifFonction OU Exclusif =1e1
e2S
• Pour que la sortie soit à 0 :
Il faut que e1 OU e2 soit à 1 mais pas les 2
• Pour que la sortie soit à 1 :
Il faut que les entrées soient au même niveau logique
S = e1 + e2
Se1 e2
0
0
0
0
1
11
1 1
1
0
0
S = e1.e2 + e1.e2
Intérêt : Détecter l’inégalité entre e1 et e2
Diapo suiv
Fonctions logique de baseFonctions logique de base
�� Fonction OU Fonction OU ExclusifExclusif =1e1
e2S
• Pour que la sortie soit à 0 :
Il faut que e1 OU e2 soit à 1 mais pas les 2
• Pour que la sortie soit à 1 :
Il faut que les entrées soient au même niveau logique
S = e1 + e2
Se1 e2
0
0
0
0
1
11
1 1
1
0
0
S = e1.e2 + e1.e2
Intérêt : Détecter l’inégalité entre e1 et e2
� Menu
Fonctions logique de baseFonctions logique de base
�� Fonction NOR ExclusifFonction NOR Exclusif
• Pour que la sortie soit à 1 :
Il faut que e1 OU e2 soit à 1 mais pas les 2
• Pour que la sortie soit à 0 :
Il faut que les entrées soient au même niveau logique
S = e1 + e2
Se1 e2
0
0
0
0
1
11
1 0
0
1
1
S = e1.e2 + e1.e2
Intérêt :
=1e1
e2S
NOR Exclusif = OU Exclusif
1
1
0
0
S = e1.e2 + e1.e2
Diapo suiv
Fonctions logique de baseFonctions logique de base
�� Fonction NOR ExclusifFonction NOR Exclusif
• Pour que la sortie soit à 1 :
Il faut que e1 OU e2 soit à 1 mais pas les 2
• Pour que la sortie soit à 0 :
Il faut que les entrées soient au même niveau logique
S = e1 + e2
Se1 e2
0
0
0
0
1
11
1 0
0
1
1
S = e1.e2 + e1.e2
Intérêt : Détecter l’identité entre e1 et e2
=1e1
e2S
NOR Exclusif = OU Exclusif
1
1
0
0
S = e1.e2 + e1.e2
� Menu
�� Il dIl déécrit un systcrit un systèème algme algéébrique qui sera plus brique qui sera plus tard connu sous le nom dtard connu sous le nom d’’algalgèèbre boolbre boolééenne. enne. Dans ce systDans ce systèème, les propositions logiques sont me, les propositions logiques sont indiquindiquéées par des symboles et peuvent être es par des symboles et peuvent être exexéécutcutéées par des opes par des opéérateurs mathrateurs mathéématiques matiques abstraits qui correspondent aux lois de la abstraits qui correspondent aux lois de la
logique.logique.
�
�� Boole, GeorgeBoole, George (1815(1815--1864), 1864), mathmathéématicien et logicien maticien et logicien anglais.anglais.
AlgAlgèèbre logiquebre logique
�� Relations particuliRelations particulièèresres
a . b = b . a
a + b = b + a
a + ( b + c ) = ( a + b ) + c = b + ( a + c )
a ( b + c ) = a . b + a . c
a . 0 = 0
a . a = a
a . 1 = a
a . a = 0
a + 0 = a
a + a = a
a + 1 = 1
a + a = 1
� Menu
AlgAlgèèbre logiquebre logique
�� ThThééororèème de de Morganme de de Morgan
a . b = a + b
a + b = a . b
Application principale : Transformation d’une somme en produit et inversement
� Menu
AlgAlgèèbre logiquebre logique
�� Exemple dExemple d’’application : application : Recherche d’équation
&
a
b >1c & S
b.ca + b.c
= c.(a + b.c)
Simplification : S = a.c + b.c.c
S = a.c + b.c
S = c (a + b) S = c (a + b)
� Menu
AlgAlgèèbre logiquebre logique
�� Exemple dExemple d’’application : application : création d’un logigramme
Equation logique de départ : S = ( a + b.c ).d
&a + b.c
dS>1b.c
a
&c
b
a
d
Règle de construction : Toujours partir de la sortie, rechercherl’opérateur logique qui sépare l’équation
� Menu
AlgAlgèèbre logiquebre logique
�� Tableau de Tableau de KarnaughKarnaugh : :
1111000011
1100000011
0011111100
1100111100
1111001100
0000001100
1111110000
1100110000
0011000000
0000000000
SSaabbccdd
Etude d’un exemple :définition d’une équation àpartir d’une table de vérité
� Menu
AlgAlgèèbre logiquebre logique
�� Tableau de Tableau de KarnaughKarnaugh : :
1 – Construire le tableau
1111000011
1100000011
0011111100
1100111100
1111001100
0000001100
1111110000
1100110000
0011000000
0000000000
SSaabbccdd
1010
1111
0101
0000
1010111101010000
d.c
b.a
11
1 1
1 1
0 0
0 0
� Menu
AlgAlgèèbre logiquebre logique
�� Tableau de Tableau de KarnaughKarnaugh : :
2 – Compléter le tableau
1111000011
1100000011
0011111100
1100111100
1111001100
0000001100
1111110000
1100110000
0011000000
0000000000
SSaabbccdd
1010
1111
0101
0000
1010111101010000
d.c
b.a
Ajouter des 1 ou 0 afin de pouvoir réaliser des regroupements maximums
1
1
1 1 1
1
11
1 1
1 1
0 0
0 0
� Menu
AlgAlgèèbre logiquebre logique
�� Tableau de Tableau de KarnaughKarnaugh : :
3 – Regrouper les cases (groupe de 2n)
1111000011
1100000011
0011111100
1100111100
1111001100
0000001100
1111110000
1100110000
0011000000
0000000000
SSaabbccdd
1010
1111
0101
0000
1010111101010000
d.c
b.a
1
1
1 1 1
1
11
1 1
1 1
0 0
0 0
� Menu
AlgAlgèèbre logiquebre logique
�� Tableau de Tableau de KarnaughKarnaugh : :
4 – Etablir l’équation finale
1111000011
1100000011
0011111100
1100111100
1111001100
0000001100
1111110000
1100110000
0011000000
0000000000
SSaabbccdd
1010
1111
0101
0000
1010111101010000
d.c
b.a
S = c.b + d + a.b + a.b.c Recommencer
1
1
1 1 1
1
11
1
11 1
0 0
0 0
� Menu
AlgAlgèèbre logiquebre logique
�� Tableau de Tableau de KarnaughKarnaugh : : Etude d’un exemple :définition d’une équation à partir d’une équation logique
1 – Construire le tableau
1010
1111
0101
0000
1010111101010000
a.b
c.d
S = a.b.c + a.b.c + a.b.c + a.b.d
1 1
11 1 1
� Menu
AlgAlgèèbre logiquebre logique
�� Tableau de Tableau de KarnaughKarnaugh : :
2 - Regrouper
1010
1111
0101
0000
1010111101010000
a.b
c.d
S = a.b.c + a.b.c + a.b.c + a.b.d
1 1
11 1 1
� Menu
AlgAlgèèbre logiquebre logique
�� Tableau de Tableau de KarnaughKarnaugh : :
3 – Définir l’équation finale
1010
1111
0101
0000
1010111101010000
a.b
c.d
S = a.b.c + a.b.c + a.b.c + a.b.d
1 1
11 1 1 S = a.b + a.c S = a.(b + c)
Recommencer
� Menu