ch1_sys_logique.pdf

Le principal objectif de ce cours est de permettre ltudiant dacqurir des connaissances de base de llectronique numrique. Il permet

ltudiant de comprendre le fonctionnement de circuits logiques combinatoires et squentiels qui sont la base de larchitecture des

ordinateurs.

1

Descriptif et contenu Systmes binaires et algbre de Boole Portes: ET, OU inclusif/ exclusif , porte NON , NON ET et NON OU, Porte

Trois Etats Thormes de Morgan Rsum des identits boolennes de base Ecritures canoniques d'une fonction logique (Somme canonique de produits,

Produit canonique de sommes) Simplification de l'criture des fonctions logiques (Simplification algbrique,

Tableaux de Karnaugh)Tableaux de Karnaugh) Addition binaire (Demi additionneur, Additionneur, Addition en parallle,

Addition squentielle) Soustraction (Demi soustracteur, Additionneur-soustracteur, Comparaison) Contrle de parit Dcodage (Dcodeur DCB-dcimal) Multiplexage (Dmultiplexeur, Multiplexeur, Conversion parallle-srie) Encodage Unit arithmtique et logique Logique squentielle asynchrone et synchrone Bascules: RST ou RS Clock, JK, D et T Registres: mmorisation, dcalage Compteurs : asynchrones, synchrones

2

CHAPITRE I : CHAPITRE I :

Algbre Boolenne et simplification logique

3

INTRODUCTION : Lalgbre de Boole doit son nom au mathmaticien Anglais

Georges BOOLE (1815 1864). Cette algbre a t mise en place pour formaliser les rgles

de la logique des propositions. Elle a t publie en 1847. Lalgbre boolenne permet

d'utiliser des techniques algbriques pour traiter lesd'utiliser des techniques algbriques pour traiter lesexpressions deux valeurs de la logique des propositions.

Aujourd'hui, l'algbre de Boole trouve de nombreusesapplications en informatique et dans la conception descircuits lectroniques.

L'algbre de Boole des fonctions logiques permet demodliser des raisonnements logiques, en exprimant un tat en fonction de conditions.

4

Exemple :

Communication = metteur ET Rcepteur

Communication est VRAI Si metteur actif ETRcepteur actif (c'est une fonction logique dpendantdes variables metteur et Rcepteur)

INTRODUCTION :

des variables metteur et Rcepteur)

Dcrocher = ( Dcision de rpondre ET Sonnerie ) OUdcision d'appeler

Dcrocher est VRAI Si on entend la sonnerie ETque l'on dcide de rpondre OU si l'on dcided'appeler.

5

II. CONCEPTS DE BASE1. Prdicat

On appelle prdicat ou proposition logique une phrase , qui peut tre soit vraie, soit fausse.

Exemples :Exemples :

(P1) Il neige,

(P2) La temprature du four est suprieure 400

Par convention on notera vrai = 1 et faux = 0.

0 et 1 sont des notations facilitant la lisibilit mais nedsignant pas les rels 0 et 1 !

6

On appelle algbre de Boole, un quadruplet (B, NON ,ET ,OU ) compos d'un ensemble B = {0, 1} , d'unoprateur unaire NON B B appel complmentation,de deux oprateurs binaires ET ,OU BxB B appels

II. CONCEPTS DE BASE2. Dfinition

de deux oprateurs binaires ET ,OU BxB B appelsrespectivement multiplication logique et additionlogique.

Nous pouvons dfinir les oprateurs : NON, ET, OU

7

NON ou complmentation logique ( NOT a, ). Cet oprateur est dfini par la table de vrit suivante :

a NOT a

0


a

ET ou multiplication logique ( a AND b, a.b). Cet oprateur est dfini par la table de vrit suivante :

0

1

a b a.b

0 0

0 1

1 0

1 1 8

OU ou addition logique ( a OR b, a+b ). Cet oprateur est dfini par la table de vrit suivante :


a b a+ba b a+b

0 0

0 1

1 0

1 1

9

Une algbre de Boole vrifie les axiomes suivants :

II. CONCEPTS DE BASE3. Proprits de base

10

Une algbre de Boole vrifie les thormes suivants :

II. CONCEPTS DE BASE4. Thormes

11

OU exclusif ( a XOR b, ab), il correspond l'quation suivante :

ab =

II. CONCEPTS DE BASE5. Oprateurs ou fonction complmentaires

. .a b a b+

ab =

Cet oprateur est dfini par la table de vrit suivante :

. .a b a b+

a b ab

0 0

0 1

1 0

1 1

12

L'oprateur OU exclusif vrifie les proprits suivantes :


13

NON ET ou NAND ( a NANDb ), il correspond l'quation suivante :

a NANDb =



.a b


a b a NANDb

0 0

0 1

1 0

1 1

14

NON ET ou NANDRemarques :


15

NON OU ou NOR ( a NORb ), il correspond l'quation suivante :

a NORb =



a b+ Cet oprateur est dfini par la table de vrit suivante :

a b a NORb

0 0

0 1

1 0

1 1

16

NON OU ou NOR Remarques :


17

Implique (ab), il correspond l'quation suivante :ab =



a b+

a b ab

0 0

0 1

1 0

1 1

18

Equivalent ( ab ), il correspond l'quation suivante :ab =



. .a b a b a b aXORb+ = =

a b ab

0 0

0 1

1 0

1 1

19

Inhibe ( a|b), il correspond l'quation suivante : a|b =



a b+ Cet oprateur est dfini par la table de vrit suivante :

a b a|b

0 0

0 1

1 0

1 1

20

III. FONCTIONS BOOLENNES1. Dfinition

Soit une algbre de Boole constitue du quadruplet (B, NON ,ET ,OU ) o B est l'ensemble B = {0, 1}.

Soit Bn = {(a1 ,a2 ,...... ,an) ai B} avec Bn = 2n i

On appelle fonction boolenne de n variables, toute application de Bn dans B.

Exemple : f (x, y, z) = . ( )x z x y z+ +

21

III. FONCTIONS BOOLENNES2. Table de vrit

Une fonction boolenne de n variables est entirement dfinie par la liste de ses valeurs. On donne donc la valeur de la fonction pour chaque combinaison des n variables boolennes. On obtient ainsi la table de variables boolennes. On obtient ainsi la table de vrit de la fonction.

La table de vrit d'une fonction de n variables est compose de n + 1 colonnes et de 2n lignes.

2 variables ==> 3 colonnes et 4 lignes

3 variables ==> colonnes et lignes

4 variables ==> colonnes et lignes22

III. FONCTIONS BOOLENNES2. Table de vrit

Exemple :

La fonction f (x, y, z) = peut-tre dfinie par la table de vrit ci-dessous :

X y z f (x, y, z)X y z f (x, y, z)

23

III. FONCTIONS BOOLENNES3. Formes canoniques dune fonction boolenne

3.1 Fonction boolenne

Soit (B, NON ,ET ,OU ) une algbre de Boole.

Une fonction boolenne f de n variables boolennes Une fonction boolenne f de n variables boolennes Bn dans B est une application qui a tout n-uplet de B fait correspondre un lment B construit laide des oprations boolennes

Exemple :

f(a, b, c)=

g(a, b, c, d)=

a a b b c+ +abc ab dc b+ + +

24


3.2 Mintermes et maxtermes Un minterme de n variables est un produit comportant n facteurs,

chaque facteur correspondant une variable donne ou son complmentaire.

Un maxterme de n variables boolennes est une somme comportant n termes, chaque terme correspondant une variable

Un maxterme de n variables boolennes est une somme comportant n termes, chaque terme correspondant une variable donne ou son complmentaire.

Exemple : Soit a, b, c et d quatre variables boolennes. , et sont trois mintermes construit partir des variables

a, b, c et d. , et sont trois maxtermes construit partir

des variables a, b, c et d.Remarque : A partir de n variables boolennes on peut laborer 2n

mintermes et 2n maxtermes

abcd abcda bcd

a b c d+ + + a b c d+ + + a b c d+ + +

25


3.3 Forme canoniques disjonctive et conjonctive dune fonction boolenne

Soit f une fonction boolenne de Bn dans B.

Il est possible dcrire f de faon unique sous la forme dune somme de mintermes.

Cette somme est appele forme disjonctive : SDP de f . Cette somme est appele forme disjonctive : SDP de f .

De faon analogue, il est possible dcrire f sous la forme dun produit de maxtermes. Ce produit est appel forme conjonctive : PDS de f.

Exemple :

Considrons la fonction boolenne : =

On a :

26

a b

( , , )f a b c =ab .1 = .( )ab c c+

= abc abc+

(1 est un lment neutre de la multiplication)

(principe du tiers exclus)

(distributivit)

Une fonction tant, en gnrale, dfinie par sa table de vrit non partirons de la forme canonique disjonctive de la fonction boolenne pour en tablir une forme simplifie. On obtient ainsi un polynme contenant

IV. SIMPLIFICATION DES FONCTIONS BOOLENNES1. Dfinition

simplifie. On obtient ainsi un polynme contenant un minimum de variable.

1. Simplification par calcul En utilisant les axiomes et les thormes de l'algbre

de Boole, nous pouvons obtenir la forme simplifie d'une fonction boolenne. Cette mthode, utilisable dans des cas simples, est fastidieuse et hasardeuse.

27

2.1 Dfinition

Un tableau de Karnaugh est une table de vrit dans lequel chaque case reprsente un Minterme. Les cases du tableau sont ordonnes suivant un code binaire rflchi (le code GRAY (ci-dessous)) de tel sorte que

IV. SIMPLIFICATION DES FONCTIONS BOOLENNES2. Simplification par tableau de Karnaugh

un code binaire rflchi (le code GRAY (ci-dessous)) de tel sorte que pour passer d'une case une autre seule une variable change d'tat.

Exemple : Tableau de Karnaugh 4 variables

28

Exemple :


Exemple :Tableau de Karnaugh 4 variables

29

2.2 Mthodologie

a) Remplissage du tableau Ecrire 1 dans chaque case (Minterme) correspondant

une valeur vraie de la fonction boolenne.


une valeur vraie de la fonction boolenne. Ecrire 0 dans chaque case (Minterme)

correspondant une valeur fausse de la fonction boolenne. Ecrire X dans chaque case (Minterme)

correspondant une valeur non dfinie de la fonction boolenne.

30

2.2 Mthodologie

b) Regroupement

Regrouper les cases adjacentes contenant des 1 ou des X par puissances de 2 en formant les plus grands groupes possibles.


Vrifier que : Chaque case contenant un 1 appartient au moins un regroupement,

Chaque groupe est de taille maximale (1, 2, 4, 8, 16, ... 2n cases),

Aucune case contenant un 0 n'est incluse dans un regroupement.

Le terme correspondant chaque groupe est le produit des variables qui restent inchanges sur l'ensemble des cases constituant le regroupement. On appelle ce terme un impliquant premier

31

2.2 Mthodologie

c) Fonction boolenne simplifie

La fonction boolenne simplifie est la somme de tous les impliquants premiers.


Remarque :

La mthode de simplification par tableau de Karnaugh reste limite aux fonctions boolennes ne comportant pas plus de 5 6 variables.

32

Exemple 1 :Diagramme de Karnaugh dune SDP non standard

Soit la fonction dont la forme canonique disjonctive est gale

Nous pouvons tablir le tableau de Karnaugh suivant :


( , , ) . ( )f x y z x y x y z= + +( , , )f x y z xyz xyz xyz xyz xyz= + + + ++

D'o la forme simplifie de la fonction

33

( , , )f a b c xz y= +

Exemple 2 :Diagramme de Karnaugh dune PDS non standard

Soit la fonction PDS minimis g suivante

La combinaison des valeurs binaires sont :


( , , , ) ( ).( ).( )g A B C D C D A B D A B C= + + + + + La combinaison des valeurs binaires sont :

(x+x+0+0)(0+0+x+0)(1+0+0+x)

34

00 01 11 10

00 0 0

01 0

11 0

10 0 0

CDAB PDS standard ?

SDP standard ?SDP minimis ?

Applications

EXERCICE 1: Deux fonctions sont quivalentes si elles ont la mme forme

canonique ; dmontrer les quivalences suivantes :1 ( )( )2 ( )( )( ) ( )( )

T a b a c ac abT a b a c b c a b a c

+ + +

= + + + + +

EXERCICE 2:

Ecrire les tables de vrits des fonctions suivantes :

Montrer quelles permettent de comparer a et b

35

, ,ab ab ab ab+

V. SCHMATISATION DES OPRATEURS LOGIQUES1. Notation Franaise

36

V. SCHMATISATION DES OPRATEURS LOGIQUES2. Notation Amricaine

37

Documents

ch1_sys_logique.pdf