Logique Combinatoire - Cours

8/8/2019 Logique Combinatoire - Cours

1/30

- 1 -Logique CombinatoireCopyright F. Muller2002

Plan

n Les Systmes de Numration

n Fonctions et Circuits Logiques

n Simplification des Fonctions Logiques

n Les Diffrents Codes


2/30

- 2 -Copyright F. Muller2002

Fonctions et Circuits Logiques

n Dfinitionn Algbre de commutation ou algbre de Boole

n Fonction logiquen Circuits combinatoires SSI & MSI


3/30


Dfinitions

n

lment logiquen 2 lments logiques nots 0 et 1

n Le symbole 1 dsigne une action comme une lampesallume, la porte souvre

n Le symbole 0 indique gnralement labsence daction

n Variable logique ou boolenne Xn Une variable logique ou boolenne est une grandeur qui ne

peut prendre que 2 tats 0 ou 1

n Domaine de dfinition B2 = {0,1}

n Si X est une variable boolenne, on an X 0 si et seulement si X = 1n X 1 si et seulement si X = 0


4/30


DfinitionsOprateurs logiques lmentaires

X

Inversion (Inversion (NotNot) ou Compl) ou Complmentationmentation

OpOpration OU (OR) ou Unionration OU (OR) ou Union

OpOpration ET (AND) ou Intersectionration ET (AND) ou Intersection

B2 B2

Notation :

01

10

XX

YXou +YX

B2 x B2 B2

Notation :

111

101

110000

X+YYX

111

001

010000

X.YYX

XYouY.XouYX

B2 x B2 B2

Notation :


5/30


n Cas de 2 variables boolennes X et Y 2 domaines

DfinitionsDiagramme de Venn

n Les valeurs dune variable boolenne X peuvent trereprsentes par 2 rgions dun plan dlimites par unecourbe ferme.

X=0

X=1

n 3 variables boolennes 3 domaines

X=0

X=1

Y=0

Y=1

X=0

X=1

Y=0

Y=1

X.YX=0 Y=0

X + Y

X=1 Y=1


6/30






7/30


Lois fondamentales de lalgbre de Boole

n Lalgbre de commutation ou algbre de Boole est le systmealgbrique constitu de lensemble B2 et des oprations ET,OU, PAS.

1.A = A1+A = 10. A = 00+A = A

Identits remarquables

A+A = AA.A = A

Idempotence

A+A = 1A.A = 0

Complmentarit

A.(B+C) = A.B + A.CA+(B.C) = (A+B).(A+C) Diffrent algbre classique

Distributivit

A.(B.C) = (A.B).CA+(B+C) = (A+B)+CAssociativit

A.B = B.AA+B = B+A

Commutativit

A.B Variable logique dfinie par la table ETA+B Variable logique dfinie par la table OU

Fermeture

Axiomes delalgbre deboole


8/30


Thorme de De Morgan

n

Thorme 1n La ngation dun produit de variables est gale la somme

des ngations des variables

n Thorme 2n La ngation dune somme de variables est gale au produit

des ngations des variables

CBACBA ++=..

CBACBA ..=++


9/30






10/30

- 1 0 -Logique CombinatoireCopyright F. Muller2002

Dfinitions

n

Une fonction logique de n variables x1, , xn est uneapplication qui a toute combinaison de

n Une fonction logique ne peut prendre que 2 tats 0ou 1

n Le nombre de fonctions que lon peut crer avec nvariables est 22

npuisqu chacune des 2n

combinaisons de variables, on peut fairecorrespondre les valeurs 0 ou 1

22lmentunsn variable BBn


11/30


Fonction compltement dfinie

n Une fonction logique est compltement dfinie quandon connat sa valeur 0 ou 1 pour toutes lescombinaisons possibles des variables.

n Ces combinaisons sont au nombre de 2n pour nvariables

0010

1110

0001

1101

1

1

0

0

X

111

101

010

000

fZYExemple

n Soit une fonction de 3 variablesf(x,y,z)

n 23 = 8 combinaisons

n

Rpertorier les combinaisons danslordre croissant de 0 2n-1


12/30


Fonction incompltement dfinie

n

Une fonction logique est incompltement dfiniequand sa valeur est indiffrente ou non spcifie pourcertaines combinaisons de variables

n On note sa valeur par X ou

0010

X110

X001

1101

1

1

0

0

X

X11

101

010

X00

gZYExemple

n Soit une fonction de 3 variablesg(x,y,z)

n 23 = 8 combinaisonsdont 4 combinaisons indfinies


13/30


Formes Canoniques des Fct. LogiquesPremire Forme Canonique (1)

n Appel aussin Produels de Produitsn Forme canonique disjonctive

n Sexprime sous la forme dune somme de produits

n criture partir de la table de vritn Reprer dans la table de vrit les combinaisons x, y, z

pour lesquelles la fonctions vaut 1n Pour ces combinaisons, faire le produit des variables en

affectant le symbole aux variables dont ltat est 0. Onobtient les monmes de la fonction

n Faire la somme de tous les monmes


14/30



n Exemplen soit la fonction f tel que

n f = 1 si la majorit des variables sont 1n f = 0 sinon

0010

1110

0001

1101

1

1

00

X

111

101

010000

fZY

0010

1110

0001

1101

1

1

00

X

111

101

010000

fZY

Ralisation de la table de vrit 1) Recherche les cas o la fonction vaut 1

2) criture des monmes


15/30



n Remarquen Comment obtenir le complment de f ?

0010

1110

0001

1101

1

1

0

0

X

111

101

010

000

fZY

zyxzyxzyxzyxzyxf ........),,( +++=


16/30



n criture de la table de vrit partir de f canoniquen dresser la table de vrit n variablesn les combinaisons correspondantes un monmes de f seront

affectes ltat 1, les autres ltat 0n Exemple

zyxzyxzyxzyxf ......),,( ++=

0010

0110

00011101

1

1

0

0

X

111

001

010

100

fZY


17/30


Formes Canoniques des Fct. LogiquesDeuxime Forme Canonique (1)

n Appel aussin Produits de Produels

n Forme canonique conjonctive

n Sexprime sous la forme dun produit de sommes

n criture partir de la table de vritn Reprer les combinaisons pour lesquelles ltat de f est 0

n Pour ces combinaisons, faire la sommes des variables enaffectant le symbole aux variables dont ltat est 1

n

Faire le produit des sommes


18/30



n Exemple

0010

11100001

1101

1

1

0

0

X

111

101

010

000

fZY

1) Recherche les cas o la fonction vaut 0

zyx ++

zyx ++

zyx ++

zyx ++

2) criture des monmes


19/30



n criture de la table de vrit partir de fn Dresser la tablen Pour chaque terme somme de f, prendre la combinaison faisant

apparatren un 0 pour une variable directen un 1 pour une variable inverse note

n Affecter 0 f pour ces combinaisons, 1 f pour les autresn Exemple

)).().((),,( zyxzyxzyxzyxf ++++++=

1010

0110

10011101

1

1

0

0

X

111

001

010

100

fZY


20/30


Fonctions dune seule variable Boolenne

n On peut former 221

fonctions, soit 4 fonctionsn Ces fonctions sont appeles monodes

10101

11000

f3f2f1f0x

00 =f

13 =f

xf =1

xf =2

fonctions constantes

cest la variable elle-mme

cest le complment de la variable

not NON ou NOT


21/30


Fonctions de deux variables Boolennes

n On peut former 222

fonctions, soit 16 fonctions

101010101010101011

110011001100110001

111100001111000010

111111110000000000

f15f14f13f12f11f10f9f8f7f6f5f4f3f2f1f0yx

Fonction une seule variable

00 =f

115 =f

xf =3

xf =12

yf =5

yf =10

Oprateurs fondamentaux

yxf +=7

yxf .1 =

Autres fonctions

yxyxyxf =+= ..6

OU

ET

Fonction OU exclusif ou comparateurdingalit

yxyxyxf =+= ..9 Fonction Identique ou comparateurdidentit

yxyxf +== .8 Fonction NON OU ou NOR

yxyxf .14 =+= Fonction NON ET ou NAND


22/30

- 2 2 -Copyright F. Muller2002





23/30


Circuits SSI (Small Scale Integration)Portes Logiques lmentaires (1)

Porte NON, PAS ou Inverseur (NOT)Porte NON, PAS ou Inverseur (NOT)

lectricitlectricit +5v

0v

Lampe = X

X

Cas 1 X = 0

+5v

0v

Lampe = XX

Cas 2 X = 1

1

Symboles lectroniquesSymboles lectroniques

X X X X


24/30


Circuits SSI (Small Scale Integration)Portes Logiques lmentaires (2)

Porte ET (AND)Porte ET (AND)

Porte OU (OR)Porte OU (OR)

lectricitlectricit

+5v

0v

Lampe = X+Y

X

Y

lectricitlectricit

+5v

0v

Lampe = X.Y

X Y


X

Y

X.Y &X

Y

X.Y


1XY

X+YX

Y

X+Y


25/30


Circuits SSI (Small Scale Integration)Portes Logiques de Base (1)

Porte OU Exclusif (EXOR)Porte OU Exclusif (EXOR)

X

Y

X Y =1X

Y

X Y

Porte OU Exclusif ComplmentPorte OU Exclusif Complment(EXNOR)(EXNOR)

X

Y=1

X

Y

X YX Y

Porte NON ET (NAND)Porte NON ET (NAND)

X

Y &

X

Y

X.YX.Y

Porte NON OU (NOR)Porte NON OU (NOR)

X

Y

X+Y

1

X

Y

X+Y


26/30


Circuits SSI (Small Scale Integration)Portes Logiques de Base (2)

Circuits 3 tats (TRISTATE)Circuits 3 tats (TRISTATE)c

e s c = 0 alors s=haute impdance (z)c = 1 alors s=e

/c

e s c = 1 alors s=haute impdance (z)c = 0 alors s=e

c=0e s=z (haute impdance)

c=1e s=e

/c=1e s=e

/c=0e s= z (haute impdance)


27/30


Circuits SSI (Small Scale Integration)Exemples

NAND (7400) NOT (7404)

OR (7408) Buffer Tristate (74126)


28/30


Circuits MSI (Medium Scale Integration)Multiplexeur & Encodeur

MultiplexeurMultiplexeur

Adresses A,B,C, n fils

Entres E0,E1,E2,

2n fils

Sortie S1 fil

ExempleExemple

Multiplexeur 4 1

4 entres = 22

n=2 donc 2 fils dadresse A et B

1 sortie (toujours vrai)

EncodeurEncodeur

Entres E0,E1,,Em

n filsSortie S

m=2n fils ExemplesExemples

Encodeur 8 3 8 entres 3 sorties

Encodeur 10 4

1

10

S0

m-1

10

0

10

E1

1

00

S1

101

000010

SnE0Em-1


29/30


Circuits MSI (Medium Scale Integration)Demultiplexeur & Dcodeur

DemultiplexeurDemultiplexeur

Adresses A,B,C, n fils

Sorties S0,S1,S2,

2n fils

Entre E 1 fil

ExempleExempleDemultiplexeur 1 8

1 entre (toujours vrai)

8 sorties ou 23 sorties

n=3 donc 3 fils dadresse A,B et C

ExemplesExemples

Dcodeur 3 8 3 entres 8 sorties

Dcodeur 4 10

m-1

10

0

01

S0

1

00

E1

0

10

S1

111

010000

Sm-1E0En

DcodeurDcodeur

Sorties S0,S1,,Sm

n fils

m=2n fils

Entres E0,E1,,En


30/30


Circuits MSI (Medium Scale Integration)Exemples

Multiplexeur 4 vers 1 (74153) Additionneur 4 bits (7483)

Documents

Logique Combinatoire - Cours