Introduction à la logique Cours #2: GPA-140 Hiver 2005

Introduction à la logique

Cours #2: GPA-140Hiver 2005

2

Introduction aux fonctions logiques

Systèmes binaires¤ Deux états fondamentaux et distincts;¤ Vrai/Faux, Marche/Arrêt, Oui/Non.

Par convention:¤ Un état est représenté par « 1 »;¤ L’autre est représenté par « 0 ».

3

La logique Booléenne

En 1847, George Boole invente une algèbre pour traiter les variables binaires.¤ Il écrira « The Mathematical

Analysis of Logic », Cambridge,

Il définit 3 opérateurs de base, ainsi qu’une foule de règles et de postulats.

4

Types de représentation

Les fonctions logiques peuvent être représentées de plusieurs façons:¤ Tables de vérités¤ Diagrammes échelle (Ladder)¤ Équations logiques

5


Tables de vérités¤ Tables qui énumèrent toutes les

combinaisons possibles d'entrées, et les sorties correspondantes.

¤ Le nombre de colonnes est la sommes du nombre d'entrée et de sortie

¤ Pour "N" entrées, le nombre de lignes est 2N

Exemple:3 entrées et 1 sorties4 colonnes et 8 lignes

6


Tables de vérités3 entrées et 1 sorties4 colonnes et 8 lignes

Chaque ligne est une équation logique

7


Diagrammes échelle (Ladder)

8


Équations logiques¤ Reposent sur 3 opérateurs de base:

ET, OU, NON

Toutes les équations logiques sont formées de ces 3 opérateurs

9

Fonction logique NON

En anglais: NOTReprésentation:

¤ F = A ou F = /A

Entrée Sortie

A F

0 1

1 0

Table de vérité

A F

Symbole graphique

10

Fonction logique ET

En anglais: ANDReprésentation:

¤ F = A * B ou A • B ou AB

Entrée Sortie

F

1

Table de vérité

AB

0 0

1

1

11

0

0

0

0

0

AF

Symbole graphique

B

11

Fonction logique OU

En anglais: ORReprésentation:

¤ F = A + B

Entrée Sortie

F

1

Table de vérité

AB

0 0

1

1

11

0

1

1

0

0

AF

Symbole graphique

B

12

Fonction logique NON-ET

En anglais: NANDReprésentation:

¤ F = A * B

Entrée Sortie

F

0

Table de vérité

AB

0 0

1

1

11

0

1

1

1

0

AF

Symbole graphique

B

13

Fonction logique NON-OU

En anglais: NORReprésentation:

¤ F = A + B

Entrée Sortie

F

0

Table de vérité

AB

0 0

1

1

11

0

0

0

1

0

AF

Symbole graphique

B

14

Fonction OU-EXCLUSIF

En anglais: XORReprésentation:

¤ F = A B

Entrée Sortie

F

0

Table de vérité

AB

0 0

1

1

11

0

1

1

0

0

AF

Symbole graphique

B

/B*A

B*/A

/B*A+B*/A

15

Fonction NON OU-EXCLUSIF

En anglais: XNORReprésentation:

¤ F = A B

Entrée Sortie

F

1

Table de vérité

AB

0 0

1

1

11

0

0

0

1

0

AF

Symbole graphique

B

/B*/A

B*A

/B*/A+B*A

16

Fonctions à 2 variables

Il existe 16 fonctions logiques possibles avec 2 variables.¤ Deux variables permettent 4 combinaisons

(22) 00, 01, 10, 11

¤ Ces 4 combinaisons donnent 16 fonctions (24)

F0, F1, … F15

17


16 fonctions logiques avec 2 variables.

A F0

0 0

0 0

B

0

1

1

1

0

1

0

0

F1

1

0

0

0

F2

0

1

0

0

F3

1

1

0

0

F4

0

0

1

0

F5

1

0

1

0

F6

0

1

1

0

F7

1

1

1

0

A F8

0 0

0 0

B

0

1

1

1

0

1

0

1

F9

1

0

0

1

F10

0

1

0

1

F11

1

1

0

1

F12

0

0

1

1

F13

1

0

1

1

F14

0

1

1

1

F15

1

1

1

1

18


A F0

0 0

0 0

B

0

1

1

1

0

1

0

0

F1

1

0

0

0

F2

0

1

0

0

F3

1

1

0

0

F4

0

0

1

0

F5

1

0

1

0

F6

0

1

1

0

F7

1

1

1

0

A F8

0 0

0 0

B

0

1

1

1

0

1

0

1

F9

1

0

0

1

F10

0

1

0

1

F11

1

1

0

1

F12

0

0

1

1

F13

1

0

1

1

F14

0

1

1

1

F15

1

1

1

1

19


Il existe 256 fonctions logiques possibles avec 3 variables.¤ Trois variables permettent 8 combinaisons

(23) 000, 001, 010, 011, 100, 101, 110, 111

¤ Ces 8 combinaisons donnent 256 fonctions (28)

F0, F1, … F255

¤ Pas très convivial !

20

Fonctions logiques utilisant des interrupteurs

En électronique, on représente les fonctions logiques avec des diagrammes d'échelle.

En automatisation, on utilise des interrupteurs et des relais pour représenter les fonctions logiques.

21


Interrupteur normalement fermé

V

A

Lampe

Lampe A

22

Fonction logique ET

Utilise deux interrupteurs normalement ouvert en série.

V

A

Lampe

B

Lampe A B

23

Fonction logique OU

Utilise deux interrupteurs normalement ouvert en parallèle.

V

A

Lampe

B

Lampe A B

24


Utilise deux interrupteurs normalement fermés en parallèle.

V

A

Lampe

B

Lampe AB A B

25


Utilise deux interrupteurs normalement fermés en série.

V

A

Lampe

B

Lampe A B A B

26


Utilise deux interrupteurs à deux contacts

V

A

Lampe

A B

B

LampeABABAB

27

Fonction NON OU-EXCLUSIFUtilise deux interrupteurs à deux contacts

V

A

Lampe

A B

B

Lampe A B A B AB

28

Fonctions logiques utilisant des relaisEn automatisation, on utilise les relais

pour réaliser des fonctions logiques.Le relais est une composante

électromécanique.

AA A

Contactnormalement

ouvert

Bobine Contactnormalement

fermé

29


Relais avec un contact normalement fermé

V

b

B

V++

LampeB

Bobine d'entrée Diagramme en échelle (Ladder)

30

Fonction logique ET

2 relais avec des contacts N.O. en série.

V

c

C

V++

LampeC

Bobines d'entrée Diagramme en échelle (Ladder)

V

d

D

D

31

Fonction logique OU

2 relais avec des contacts N.O. en parallèle.

V

e

E

V++

Lampe

E


V

f

F

F

32


2 relais avec des contacts N.F. en parallèle.

i

I

V++

Lampe

I


j

J

J

V

V

33


2 relais avec des contacts N.F. en série.

V

g

G

V++

LampeG


V

h

H

H

34


Lampe = K L = /K.L + K./L

V

k

K

V++

Lampe

K


V

l

L

K

L

L

35

Fonction NON OU-EXCLUSIF

Lampe = M N = M.N + /M./N

V

m

M

V++

Lampe

M


V

n

N

M

N

N

36

Règles, postulats et théorèmes¤ Utiles pour la simplification des équations

logiques !

L’algèbre Booléenne

37

Fermeture:¤ Si A et B sont des variables Booléennes,

alors A+B, A*B sont aussi des variables Booléennes.

Commutativité¤ A + B = B + A¤ A * B = B * A

L’algèbre BooléenneRègles, postulats et théorèmes

38

Associativité¤ A + (B + C) = (A + B) + C¤ A * (B * C) = (A * B) * C

Distributivité¤ ET/OU: A(B + C) = AB + AC¤ OU/ET: A+(B*C) = (A+B)*(A+C)


39


Idempotence¤ A + A = A¤ A * A = A

Complémentarité¤ A + A = 1¤ A * A = 0

Règles, postulats et théorèmes

40


Identités remarquables¤ 1 + A = 1 et 1 * A = A¤ 0 + A = A et 0 * A = 0

Distributivité interne¤ A + (B + C) = (A + B) + (A + C)¤ A * (B * C) = (A * B) * (A * C)

Règles, postulats et théorèmes

41

L’algèbre BooléenneRègles et postulats

42


43


44

Table de vérité versusdiagramme échelle

Pour une table de vérité donnée, nous pouvons trouver l’équation logique et le diagramme échelle correspondant

Il faut utiliser l’algèbre de Boole pour simplifier.

45

Exemple

Trouver l’équation de S.

0

C

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

B A S

Entrées Sortie

0

0

1

1

1

1

0

0

46

Exemple

Solution:¤ On construit l’équation de

S en écrivant tous les termes donnant S=1.

¤ Ainsi, S = 1: si C=0 et B=1 et A=0; ou si C=0 et B=1 et A=1; ou si C=1 et B=0 et A=1; ou si C=1 et B=1 et A=0.

0

C

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

B A S

Entrées Sortie

0

0

1

1

1

1

0

0

47

Exemple

Solution pour S=1. si C=0 et B=1 et A=0; ou si C=0 et B=1 et A=1; ou si C=1 et B=0 et A=1; ou si C=1 et B=1 et A=0.

On peut donc écrire:¤ S = /C.B./A + /C.B.A +

C./B.A + C.B./A

0

C

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

B A S

Entrées Sortie

0

0

1

1

1

1

0

0

48

Exemple

S = /C.B./A + /C.B.A + C./B.A + C.B./AOn peut simplifier:

¤ S = /C.B.(/A+A) + C./B.A + C.B./A

¤ S = /C.B.(1) + C./B.A + C.B./A

¤ S = /C.B + C./B.A + C.B./A

¤ S = /C.B + C.(A B) "ou-exclusif"

49

Exemple

S = /C.B./A + /C.B.A + C./B.A + C.B./AOn peut simplifier:

¤ S = /C.B./A + C.B./A + /C.B.A + C./B.A

¤ S = B./A.(/C+C) + /C.B.A + C./B.A

¤ S = B./A.(1) + /C.B.A + C./B.A

¤ S = B./A + /C.B.A + C./B.A¤ S = B./A + A.(C B) "ou-exclusif"

50

Exemple

Inspection visuelle ?

0

C

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

B A S

Entrées Sortie

0

0

1

1

1

1

0

0

S = /C.B + C./B.A + C.B./AS = /C.B + C.(A B)

S = B./A + /C.B.A + C./B.AS = B./A + A.(C B)

51

Si nous utilisions des relais...S = /C.B + C./B.A + C.B./A = C.(/B.A + B./A) + /C.B

52

La simplification des équations

La simplification est essentielle.¤ On veut avoir le circuit le plus simple

possible...

La simplification peut être un processus long si le système est complexe.

Heureusement, il existe des techniques simples pour simplifier.

53

Méthodes de simplification

Il est possible d ’obtenir directement une équation sous sa forme simplifiée en utilisant une méthode de simplification graphique.

Méthodes de simplification graphique:¤ Tables de Karnaugh¤ Tables de Mahoney

54

Table de Karnaugh

Représentation de la table de vérité sous forme graphique.

Nombre de cases = nombre de lignes de la table de vérité.¤ Multiple de 2n (1, 2, 4, 8, 16, ...)

n = Nombre d ’entrées

55

Table de Karnaugh

Avec n = 2:¤ Entrées B et A¤ 4 cases

0 . 1 .

2 . 3 .

AB 0 1

0

1

56

Table de Karnaugh

Avec n = 3:¤ Entrées C, B et A¤ 8 cases

BA00 01 11 10

0

1

C

0 1 3 2

4 5 7 6

57

Table de Karnaugh

Avec n = 4:¤ Entrées D, C, B et A¤ 16 cases

BA00 01 11 10

00

01

11

10

DC

0 1 3 2

4 5 7 6

12 13 15 14

8 9 11 10

58

Exemple (Karnaugh)

0

C

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

B A S

Entrées Sortie

0

0

1

1

1

1

0

0

BA00 01 11 10

0

1

C

0 1 3 2

4 5 7 6

0

0

0

1

1

0

1

1

TABLE DE VÉRITÉ

TABLE DE KARNAUGH

59

Table de Karnaugh

À partir de la table, on simplifie en groupant les 1 adjacents.

Les 1 adjacents sont mis en évidence par l'ordre utilisé pour former la table

La taille d’un groupe est un multiple de 2k (1, 2, 4, 8, ...).

Le groupe est soit rectangulaire ou carré.

60

BA00 01 11 10

0

1

C

0 1 3 2

4 5 7 6

0

0

0

1

1

0

1

1

Exemple (Karnaugh)

Simplification: S = /C.B + B./A + C./B.A

/C.B.A+/C.B./A = /C.B

/C.B./A+C.B./A=B./AC./B.A

61

Table de Karnaugh

Former les plus gros groupes possibles.¤ Termes plus simples.

Un 1 peut faire partie de plusieurs groupes.

62

BA00 01 11 10

00

01

11

10

DC

0 1 3 2

4 5 7 6

12 13 15 14

8 9 11 10

Exemple (Karnaugh)

Les 1 des bords extrêmes sont adjacents.¤ La table se referme sur elle même.

1 10 1/C./A

/C.B

/D.C./B.A 0 01 0

0 00 0

1 10 1

63

Table de Mahoney

La table de Mahoney est semblable à celle de Karnaugh pour 2 variables

A

B

F0A B F0

0 0

0 1

1 0

1 1

A

B

64

Table de Mahoney

Pour 3 variables, la table est composée de celle pour 2 variables et de son miroir

A

B

F1 A

B

A A

C C

Charnière

65

C

0 1 5 4

2 3 7 6

C

B

B

AA AA

0

1

0

1

1

0

0

1

Exemple (Mahoney)

0

C

0

0

0

1

1

1

1

0

0

1

1

0

0

1

1

0

1

0

1

0

1

0

1

B A S

Entrées Sortie

0

0

1

1

1

1

0

0

TABLE DE VÉRITÉTABLE DE MAHONEY

66C

0 1 5 4

2 3 7 6

C

B

B

AA AA

0

1

0

1

1

0

0

1

Exemple (Mahoney)

Rappel: S = /C.B + B./A + C./B.A

/C.B.A+/C.B./A = /C.B /C.B./A+C.B./A=B./A

C./B.A

67

Exemples de table de Mahoney

Avec n = 3:¤ Entrées C, B et A¤ 8 cases

C

0 1 5 4

2 3 7 6

C

B

B

AA AA

68


Avec n = 4:¤ Entrées D, C, B et A¤ 16 cases

C

10 11 15 14

8 9 13 12

C

B

B

AA AA

0 1 5 4

2 3 7 6

B

BD

D

69


Avec n = 5:¤ Entrées E, D, C, B et A¤ 32 cases

E

10 11 15 14

8 9 13 12

C

B

B

AA AA

0 1 5 4

2 3 7 6

B

B

C

30 31 27 26

28 29 25 24

C

20 21 17 16

22 23 19 18

D

D

AA AA

E

C

70


Avec n = 6:¤ 64 cases

10 11 15 14

8 9 13 12

B

B

AA AA

0 1 5 4

2 3 7 6

B

B

30 31 27 26

28 29 25 24

20 21 17 16

22 23 19 18

D

D

AA AA

E

34 35 39 38

32 33 37 36

C

B

B

40 41 45 44

42 43 47 46

B

B

C

54 55 51 50

52 53 49 48

C

60 61 57 56

62 63 59 58

E

D

D

F

F

C

71

Les états indifférents (don’t care)

Ils sont représentés par des X

En sortie, ils correspondent à des combinaisons d’entrées pour lesquelles la sortie n’a pas été définie.¤ Ex.: Un réservoir ne peut être à la fois vide

et plein.

72

Contrôle de niveau d’un réservoir

M

Pompe 1

M

Pompe 2

h

b

s

Capteur de niveau hauth = 1 -> plein

Capteur de niveau basb = 0 -> vide Sélecteur de pompe

s = 0 -> Pompe 1s = 1 -> Pompe 2

73

Contrôle de niveau ...

Si réservoir plein: Aucune pompe en marche;

Si réservoir vide: Les 2 pompes en marche;

Si réservoir ni vide, ni plein: Faire fonctionner la pompe sélectionnée par le sélecteur « s ».

Documents

Introduction à la logique Cours #2: GPA-140 Hiver 2005