Logique combinatoire

Logique combinatoireLogique combinatoire

M. M. DelebecqueDelebecque

Algèbre logiqueAlgèbre logique Boole, GeorgeBoole, George (1815-1864), (1815-1864),

mathématicien et logicien anglais.mathématicien et logicien anglais. Il décrit un système algébrique qui Il décrit un système algébrique qui

sera plus tard connu sous le nom sera plus tard connu sous le nom d’algèbre booléenned’algèbre booléenne. Dans ce . Dans ce système, les propositions logiques système, les propositions logiques sont indiquées par des symboles sont indiquées par des symboles et peuvent être exécutées par des et peuvent être exécutées par des opérateurs mathématiques opérateurs mathématiques abstraits qui correspondent aux abstraits qui correspondent aux lois de la logique. lois de la logique.

Niveaux logiquesNiveaux logiques

Les états ou niveaux logiques sont caractérisés par des valeurs de tensions dont les limites sont précisées dans les documents constructeurs.

État 0 : niveau bas, absence de tension (low level, L)

État 1 : niveau haut, présence de tension (high level, H)

Fonctions logiques de baseFonctions logiques de base

Fonction OUI Fonction OUI (identité)(identité)

1e

Se

S

1

0

Fonction NON Fonction NON

(inverseur)(inverseur)

1e

Se

S

1

0

S= e

0

1

1

0

S= e

Fonctions logiques de baseFonctions logiques de base

Fonction ET (AND)Fonction ET (AND) &e1

e2

Se1 e2

S

0

0

0

0

1

11

1• Pour que la sortie soit à 0 :Il suffit qu’une entrée soit à 0

• Pour que la sortie soit à 1 :Il faut que e1 ET e2 soient à 1

1

0

0

0

S = e1 . e2

Fonctions logiques de baseFonctions logiques de base

Fonction OU (OR)Fonction OU (OR) >1

e1

e2

Se1 e2

S

0

0

0

0

1

11

1• Pour que la sortie soit à 0 :

Il suffit qu’une entrée e1 OU e2 soit à 1

• Pour que la sortie soit à 1 :

Il faut que toutes les entréessoient à 0

1

1

1

0

S = e1 + e2

Fonctions logiques de baseFonctions logiques de base

Fonction ET-NON (NAND)Fonction ET-NON (NAND) &e1

e2

Se1 e2

S

0

0

0

0

1

11

1• Pour que la sortie soit à 1 :Il suffit qu’une entrée soit à 0

• Pour que la sortie soit à 0 :Il faut que e1 ET e2 soient à 1

0

1

1

1

S = e1 . e2

Fonctions logique de baseFonctions logique de base

Fonction OU-NON (NOR)Fonction OU-NON (NOR) >1

e1

e2

Se1 e2

S

0

0

0

0

1

11

1• Pour que la sortie soit à 1 :

Il suffit qu’une entrée e1 OU e2 soit à 1

• Pour que la sortie soit à 0 :

Il faut que toutes les entréessoient à 0

0

0

0

1

S = e1 + e2

Fonctions logique de baseFonctions logique de base

Fonction OU Exclusif (XOR)Fonction OU Exclusif (XOR) =1

e1

e2

Se1 e2

S

0

0

0

0

1

11

1• Pour que la sortie soit à 0 :

Il faut que e1 OU e2 soit à 1Mais pas les 2

• Pour que la sortie soit à 1 :

Il faut que les entréessoient au même niveau logique

1

1

0

S = e1 + e2

0

S = e1.e2 + e1.e2

Fonctions logique de baseFonctions logique de base

Fonction « ET Exclusif »Fonction « ET Exclusif » =1

e1

e2

Se1 e2

S

0

0

0

0

1

11

1• Pour que la sortie soit à 1 :

Il faut que e1 OU e2 soit à 1Mais pas les 2

• Pour que la sortie soit à 0 :

Il faut que les entréessoient au même niveau logique

0

0

1

S = e1 + e2

1

S = e1.e2 + e1.e2

Algèbre logiqueAlgèbre logique

RelationsRelations

Commutativité => a . b =

=> a + b =

Associativité => a + ( b + c ) =

Distributivité => a ( b + c ) =

a + ( b . c ) =

b . a

b + a

( a + b ) + c

( a . b ) + ( a . c)

( a + b ) . ( a + c )

Algèbre logiqueAlgèbre logique

Relations Relations (répondre par a, 0 ou 1)(répondre par a, 0 ou 1)

a . 0 =

a . a =

a . 1 =

a . a =

a + 0 =

a + a =

a + 1 =

a + a =

Algèbre logiqueAlgèbre logique

Relations Relations

a . 0 = 0

a . a = a

a . 1 = a

a . a = 0

a + 0 = a

a + a = a

a + 1 = 1

a + a = 1

Algèbre logiqueAlgèbre logique

Théorème de De MorganThéorème de De Morgan

a . b = a + b

a + b = a . b

Application principale : Transformation d’une somme en produit et inversement

Algèbre logiqueAlgèbre logique

Exemple d’application : Exemple d’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)

Algèbre logiqueAlgèbre logique

Exemple d’application : Exemple d’application : création d’un logigramme

Equation logique de départ :S = ( a + b.c ).d

Règle de construction : Toujours partir de la sortie, rechercherl’opérateur logique qui sépare l’équation

Algèbre logiqueAlgèbre logique

Exemple d’application : Exemple d’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

ET à 3 entréesS = E1 . E2 . E3

E1 E2 E3 S0 0 0 00 0 1 00 1 0 00 1 1 01 0 0 01 0 1 01 1 0 01 1 1 1

OU à 3 entrées

S = E1 + E2 + E3

E1 E2 E3 S0 0 0 00 0 1 10 1 0 10 1 1 11 0 0 11 0 1 11 1 0 11 1 1 1

E1 E2 E3 S0 0 0 10 0 1 10 1 0 10 1 1 11 0 0 11 0 1 11 1 0 11 1 1 0

NAND à 3 entréesS = E1 . E2 . E3

NOR à 3 entrées

S = E1 + E2 + E3

E1 E2 E3 S0 0 0 10 0 1 00 1 0 00 1 1 01 0 0 01 0 1 01 1 0 01 1 1 0