Karnaugh - De Morgandownload.paulk.fr/cours/si/Logique 3.pdfKarnaugh - De Morgan Page 1 Tableau de Karnaugh à 2 variables I TABLEAU DE KARNAUGH _Reprenons une expression vue au chapitre

Karnaugh - De Morgan

Page 1

Tableau de Karnaugh à 2 variablesI TABLEAU DE KARNAUGH

_Reprenons une expression vue au chapitre précédent

on avait Q = a b + b + a

Cette expression se simplifiait en Q = a + b mais la démonstration n'était pas évidente.

_ La méthode par tableau de Karnaugh va nous permettre d'utliser une méthodesystématique.

Le tableau de Karnaugh n'est qu'une table de vérité mais présentée d'une autremanière :

- il y a autant de cases dans un tableau de karnaugh qu'il y a de combinaisons soit

2 cases ( n étant le nombre de variables).

- en passant d'une case contigüe à une autre, c'est-à-dire en changeant de ligne oude colonne, on ne change qu'une variable à la fois.

A chaque ligne d'une table de vérité correspond une case du tableau de Karnaugh.

Le trait en face d'une ligne ou d'une colonne signifie que la variable vaut 1 dans cetteligne ou dans cette colonne.

a b

n

Table de vérité Tableau de Karnaugh

1) TABLEAU DE KARNAUGH A 2 VARIABLES

a b

0 0

0 1

1 0

1 1

a a

b

b

TD 3

_Reprenons notre expression Q = a b + b + a

_ on peut en établir la table de vérité et reporter celle-ci dans le tableau de Karnaugh( en s'aidant de la page précédente ).

_ on peut aussi remplir directement le tableau de Karnaugh à partir de l'équation, chaquecase du tableau représentant une combinaison " a b ".

_ l'équation la plus simple sera obtenue en faisant la somme des équations des groupementsde 1 tout en observant les règles suivantes :

* un groupement est constitué de"1" rassemblés par puissance de 2 et occupant des casescontigües

* chaque "1" doit être pris dans un groupement au moins* les groupements peuvent se recouper* l'équation du groupement est obtenue en éliminant les variables qui changent d'état

pour ne garder que celles qui ne changent pas.

_ reprenons notre exemple

équation du groupement : a

équation du groupement : b

a b

Q = a + b

Page 2


Tableau de Karnaugh à 2 variables

Q a

0 1

b

1 1

Q a

0 1

b

1 1

Q a

0 1

b

1 1

Q a

a b a b

a b

b

a b

a b

a b

a b

TD 3

a b L

0 0 0

0 1 1

1 0 1

1 1 1

Page 3


Exercice n° 1 et n° 2

exercice n° 1 :

_ lire les tableaux suivants en donnant pour chacun d'eux les valeurs des fonctionslogiques simplifiées.

_ pour D : trouver un autre groupement ? donner son équation . Conclusion ?

la solution de cet exercice à la page 19

vous venez de la page 19


exercice n° 2 :

_ reprendre les expressions suivantes du chapitre précédent et simplifier-les par KarnaughR = a + a . b

S = a + . b

T = a . (a + b)

_ comparer avec ce que l'on avait obtenu ..

a

A a

1 1

b 0 0

B a

1 0

b 1 0

C a

1 1

b 1 0

D a

1 1

b 1 1

TD 3

Page 4


Tableau de karnaugh à 3 variables



remarque : _ Dans un tableau de Karnaugh à 2 variables : Il y a 2 soit 4 cases

- 1 case est définie par la combinaison de 2 variables- 2 cases sont définies par la combinaison de 1 variable- 4 cases sont définies par la combinaison de 0 variable

_ Pour chaque variable, le choix de 0 ou de 1 représente la moitié des cas

_ Le tableau comprendra 2 cases soit 8 cases

_ le tableau à 2 variables est doublé :

- une fois pour c = 0

- une fois pour c = 1

2

3

a

1 0

b

1 0

L = a

a

0 1

b

0 1

L = a

a

0 0

b

1 1

L = b

a

1 1

b

0 0

L = b

a a

b

c = 1c = 0

TD 3

Page 5


Tableau de Karnaugh à 3 variables

_ Là encore, 0 ou 1 pour une variable correspond à la moitié des cas :

_ les deux parties de la région = 1 doivent se considérer comme jointivesATTENTION a

remarque :

exercice n° 3 :

_ Dans un tableau à 3 variables: il y a 2 cases soit 8 cases

- 1 case est définie par la combinaison de 3 variables- 2 cases sont définies par la combinaison de 2 variables- 4 cases sont définies par la combinaison de 1 variable- 8 cases sont définies par la combinaison de 0 variable

_ numéroter les 8 lignes de la table de vérité c, b, a et reporter ces numérosdans les 8 cases correspondantes du tableau.

3


b

c

a = 1

a

b

c

a = 0

a

b

c

b = 1

a

b

c

b = 0

a

b

c

c = 1

a

b

c

c = 0

a

TD 3

Page 6


Exercices n° 4 et n° 5




exercice n° 4 :

exercice n° 5 :

_ représenter par des tableaux les équations suivantes :

A = a . b . c D = a . bB = a . . c E = a . b + . . cC = . b . F = + .

_ lire l'équation représentée dans les tableaux suivants :

b a ba c a b c

G

0 0 1 1

b0 0 1 1

c

a K

1 0 0 1

b0 0 0 0

c

a

H

0 0 1 0

b0 0 1 0

c

a L

1 1 0 0

b0 0 1 0

c

a

I

0 0 1 1

b0 0 0 0

c

a M

1 1 0 0

b0 1 1 0

c

a

TD 3

Page 7


Exercices n° 6 - Tableau à 4 variables






exercice n° 6 : _ représenter par des tableaux de Karnaugh les tables de vérité :

_on peut :

- reporter lignepar ligne

- reporter les cas 1compléter par

des 0

- reporter les cas 0 d'abord s'ils sont moins nombreux et compléter par des 1.

_ la aussi, on doublele nombre

de cas par rapport à celui à

3 variables.

J

0 0 0 0

b0 1 0 0

c

a N

1 1 1 0

b0 1 1 0

c

a

a b c G H I J K

0 0 0 1 0 1 0 1

0 0 1 0 0 1 1 1

0 1 0 0 1 1 0 0

0 1 1 1 0 0 0 1

1 0 0 1 0 0 0 1

1 0 1 0 0 0 1 0

1 1 0 0 0 1 0 1

1 1 1 1 1 1 0 0

b

c

a

d=1

d=0

TD 3

Page 8


Tableau de karnaugh à 4 variables

_ les mêmes remarques pour lestableaux précédents peuvent s'appliquerau tableau à 4 variables.

_ les parties hachurées doivent êtreconsidérées comme jointives.

remarque :

Important :

_ Dans un tableau à 4 variables: il y a 2 cases soit 16 cases

- 1 case est définie par la combinaison de 4 variables- 2 cases sont définies par la combinaison de 3 variables- 4 cases sont définies par la combinaison de 2 variables- 8 cases sont définies par la combinaison de 1 variable- 16 cases sont définies par la combinaison de 0 variable

_ les appellations et l'ordre a, b, c, sont arbitraires. Seule compte la disposition desdifférentes variables.

4

a = 0 a = 0

b

c

a = 1

d

b=0

b=1

b=0

TD 3

Page 9

Exercice n° 7


Voici maintenant un exercice

_ écrire l'équation correspondant à chacun des tableaux :

exercice n° 7 : _ rechercher les groupements de 2, 4, 8 cases, les plus larges possibles.


A

0 0 1 1

b0 1 1 1

0 1 1 1

0 0 1 1

c

a

d

B

0 0 0 0

y1 1 0 0

1 1 0 0

1 1 0 0

z

w

x

C

1 1 1 0

c0 1 0 0

0 1 1 0

0 1 1 0

b

a

d

D

0 1 1 0

s0 1 1 1

1 0 0 1

0 0 0 0

h

p

m

E

0 0 1 0

c1 1 0 0

0 1 1 1

0 0 0 1

a

b

d

F

0 0 0 1

b1 1 1 1

0 1 0 0

1 0 0 1

c

a

d

TD 3

Page 11


Autres repérage des cases

Vous venez de la page 26

5) AUTRE REPERAGE DES CASES

OU

_ avec deux variables nous avions deux possibilités

a b

0 0

0 1

1 0

1 1

a

b

a

b 0 1

0

1

TD 3

Page 12



_ il en est de même avec 3 ou 4 variables :

_ à l'ordre 00, 01, 11, 10

_ un seul chiffre doit changerd'une colonne à la voisine

* 01 dans la colonne signifie :a = 0b = 1 soit .b

* la 8ème ligne de la table se lit :a b c

Attention :

a

1 1 1

* la 5ème ligne de la table se lit :a b c

_ Inversement, lecture du tableau :

a b c1 0 0 a

0 1 00 1 1 b ( c indifférent )

0 0 10 1 1 c ( b indifférent )

1 0 0

b c

a

a

Feuray

a b c

0 0 0

0 0 1

0 1 0

0 1 1

1 0 0

1 0 1

1 1 0

1 1 1

c

a

b

ab

c 00 01 11 10

0

1

ab

c 00 01 11 10

0 1 1

1 1 1

TD 3

ab

cd 00 01 11 10

00

01

11

10

_ ce repérage est particulièrement commode pour les tableaux à 4 variables( trés fréquent ).

_ Le mot désignant une ligne se liten deux syllabes de deux chiffreschacune, en prenant bien soin derespecter rigoureusement l'ordredes variables.

- comporte 2 cases- 1 case est définie par la combinaison de n variables

En résumé, un tableau de n variables

n

- 2 cases sont définies par la combinaison de (n-1) variables- 4 cases sont définies par la combinaison de (n-2) variables

- 2 cases sont définies par la combinaison de 1 variables

- 2 cases sont définies par la combinaison de 0 variable

n-1

n

Page 13



a b c d S

0 0 0 0

0 0 0 1 0001

0 0 1 0

0 0 1 1

0 1 0 0

0 1 0 1

0 1 1 0 0110

0 1 1 1

1 0 0 0

1 0 0 1

1 0 1 0

1 0 1 1 1011

1 1 0 0

1 1 0 1 1101

1 1 1 0

1 1 1 1 1111

a db c

a db c

a c db

a b dc

a b c d

TD 3

Page 14


Théorème de De Morgan

II THEOREME DE DE MORGAN

complément d'une somme produit des compléments

_ reprenons le tableau de Karnaugh suivant :

L = a + b

_ si au lieu de grouper les "1" on avait groupé les "0" on aurait obtenu (au lieu de L).Il suffit alors de prendre le complément de pour avoir L.

_ dans notre exemple ci-dessous

= . ( en groupant les "0" )

soit L = .

_ or on avait L = a + b --> a + b = .

que l'on écrit en complémentant chaque menbre : = .

" le de variables est égal audes variables "

_ prenons un autre exemple :

L = +

en groupant les "0" on aurait eu = a . b

soit L =

LL

L a b

a b

a b

a + b a b

a b

L

a . b

= . . .a + b + + x a b x... ...

1) ENONCE

L a

0 1

b

1 1

L a

1 1

b

1 0

TD 3

Page 15



d'où --> = +

" le de variables est égal audes variables "

a . b a b

complément d'un produit à la somme des compléments

= + + +a . b . . x a b x... ...

2) UTILISATION DE DE MORGAN

_ on utilise De Morgan quand il est plus facile de grouper les "0" que les "1".

_ or avec les relais, on ne sait pas cabler le complément d'une somme ou d'un produit.De Morgan permet de faire le cablage.

_ mais attention, il est souvent difficile, voire impossible de vérifier que les deuxexpressions sont identiques, si ce n'est par la simulation.

_ prenons comme exemple le tableau à quatre variables A :

_ en groupant les "1" on avait A = a.b + c

_ en groupant les "0"

on a = . + .

soit A = . + . = . . .

on aura donc a . b + c = ( a + c) . ( b + c )

_ ce qui ne semble pas évident à première vue

A a c b c

a c b c a c b c

A

0 0 1 1

b0 1 1 1

0 1 1 1

0 0 1 1

c

a

d

A

0 0

b0

0

0 0

c

a

d

TD 3

Page 16



RESUME

GENERALISATION

--> = . .DE MORGAN

--> = + +

a . ( b + c ) + b . . = ( + . ) . ( + c + a )

F = somme de produit

( b . + a . . d )

a + b + c a b c

a . b . c a b c

c a a b c b

d c

= somme de produit

( . + c . d + . d )

F = ( b + d ) . ( + ) . ( a + )

produit de somme

F

b d a

c d d

F

1 1

c1 1

1 1

b

a

d

F

0 0

c0 0

0 0 0 0

0 0

b

a

d

TD 3

1 F 1

bF 1

c

a

1 1

b1

c

a

Page 17


Exploitation des cas indifférents

III EXPLOITATION DES CAS INDIFFERENTS

Cas indifférents ou peu importants

Par exemple, soit un système à trois boutons de commande a, b, c la réalisation est tellequ'il soit impossible de ma noeuvrer a et b en même temps à l'état 1.

_ Cela exclut deux cas : il n'y a pas àrechercher ce que serait la valeur de S pources cas.

_ peu importe que ce soit 1 ou 0puisque cette éventualité ne peut pas seproduire.

---> cas exclus

_ Un signe distinctif Ø ou autre, est utilisé

_ Ces cas qui ne sont pas impérativement 0 ou 1 peuvent s'utiliser à volonté avec les 0 oules 1 voisins pour faire des regroupements plus larges.

. c + a . . c + a .

)

les 1 seuls avec les Ø

a b c b

a b c S

0 0 0 0

0 0 1 0

0 1 0 1

0 1 1 1

1 0 0 1

1 0 1 0

1 1 0 F

1 1 1 F

0 1 F 1

b0 0 F 1

c

a

TD 3TD 3

Page 18


Exercice n° 9 et n° 10

exercice n° 9 :

exercice n° 10 :

_ comparer l'équation en ne regroupant que les 1 à celle obtenue en utilisantles cas indifférents.

_ refaire le même exercice en groupant les "0"




S

1 1 1 F

b0 0 1 0

0 F F 0

F F 1 F

c

a

d

TD 3

T a

1

b

1

S a

1

b

1 1

R a

1

b

1

Page 19


Solutions des exercices n° 1 et n° 2


retourner à la page 3 pour un un deuxième exercice

correction exercice n° 1 :

A = 1 quand b = 0 --> A =

ou b = 0 --> C = +

ou b = 1 --> D = b + = 1

OU quand a = 0ou a = 1 --> D = a + = 1

b

a b

b

a

D est indépendant a et bon aurait pu faire ungroupement de 4

B = 1 quand a = 0 --> B =C = 1 quand a = 0

D = 1 quand b = 0

R = a + a . b S = a + . b

T = a . (a + b)

a

a


pour avancer dans le programme, aller à la page 4


R = a S = a + b

T = a

TD 3

F

1 1 1

b1 1

c

aE

1

b1 1

c

a

Page 20




aller à la page 6



retourner à la page 6 pour l'exercice n° 5


remarque:

D = a . b = a . b (c + )= a.b.c + a.b.

1 case dans c1 case dans C = .b. D = a.b A = a.b.c B = a. .c

E = a.b + . .c F = + .

cc

c a c b

a b a b c

c b a

0 0 0 1

0 0 1 2

0 1 0 3

0 1 1 4

1 0 0 5

1 0 1 6

1 1 0 7

1 1 1 8

1

b

1 1 1

c

a

1 2 6 5

b3 4 8 7

c

a

TD 3

G

0 0 1 1

b0 0 1 1

c

a

H

0 0 1 0

b0 0 1 0

c

a

I

0 0 1 1

b0 0 0 0

c

a

J

0 0 0 0

b0 1 0 0

c

a

Page 21


Solutions de l'exercice n° 5



_ l'écriture est plus simple quand on peut obtenir desregroupements de 2 ou 4 cases convenables.

_ tout le domaine c = 1

la boucle à cheval sur a et , etsur b et indique l'idifférence visà vis de ces variables.

_ dans c = 1 et dans a = 1sur b et : b indifférent

_ dans b = 0 et dans c = 1sur a et : indifférent

G = c

H = a . c

I = . c

ab

b

a

b

_ dans a = 1 , dans b = 1 et dans c = 0sur a et : indifférenta

J = a . b . c

TD 3

N

1 1 1 0

b

0 1 1 0

c

a

L

1 1 0 0

b

0 0 1 0

c

a

K

1 0 0 1

b

0 0 0 0

c

a

M

1 1 0 0

b

0 1 1 0

c

a

Page 22


suite correction exercice n° 5 :

_ dans b = 0 et dans a = 0c indifférent

_ dans b = 0 et dans c = 0a : indifférent

.

a . b . c

.

K = .

L = . + a . b . c

a b

b c

b c

b c

_ dans a = 1 et dans b = 1 et dans c = 0

a . b

.

a

_ l'utilisation du tableau, en recherchantles boucles les plus larges de 2 ou 4 cases,donne immédiatement l'écriture la plus simple

M = a . b + .

N = a + .

b c

b c

b c

retourner à la page 6 pour l'exercice n° 7

Solutions de l'exercice n° 5TD 3

J

0 0 0 0

c

1 1 0 0

b

a

I

1 0 1 1

c

1 0 1 0

b

a

G

1 1 0 0

c

0 0 1 1

b

a

Page 23


Solutions de l'exercice n° 6


G = . + b . c

H = . b . + a . b . c

H = b . ( . + a . c )

(pas de regroupement)

I = . + a . b + .

ou bien

I = . + a . b + .

(autre regroupement)

J = . c

b c

a c

a c

a b b c

a b a c

b


H

0 0 0 1

c

0 0 1 0

b

a

TD 3

D

0 1 1 0

s0 1 1 1

1 0 0 1

0 0 0 0

h

p

m

B

0 0 0 0

y1 1 0 0

1 1 0 0

1 1 0 0

z

w

x

A

0 0 1 1

b0 1 1 1

0 1 1 1

0 0 1 1

c

a

d

C

1 1 1 0

c0 1 0 0

0 1 1 0

0 1 1 0

b

a

d

K

1 1 0 0

c

1 0 0 1

b

a

Page 24




K = . + a . + .ca b c a

A = c + a . b B = . y + . xB = . ( x + y )

C = a. + a.d + a. + . . D = p. + .h.s + .m.sC = a . ( + + d ) + . . ou bien D = p. + h.s. + .m.s

retourner à la page 7



z zz

b c b c d m p pb c b c d m m p

TD 3

1

E

0 0 1 0

c1 1 0 0

0 1 1 1

0 0 0 1

a

b

d

F

0 0 0 1

b1 1 1 1

0 1 0 0

1 0 0 1

c

a

d

Page 25


Solutions des exercices n° 7


E = .c. + b.c.d + a. .d + a.b. . F = b. + a.b. + .c. + . .dou bien F = b. + a.b. + . .c + . .d

a d b c d d c a d a bd c a b a b

aller à la page 10

TD 3

correction exercice n° 9 : les 1 seuls avec les Ø

S = . . + a . c . + a . C . S = + a . c. . + a . b . ( + )

_ les cases Ø non employés sont assimilées à des 0

= . c + . c . = . b + . B( a + c ) . ( b + + d ) c . ( + )= + a . b

_ l'utilisation des Ø rend impossible la vérification des équations obtenues

b c d d b bb c d c d

S a b d S a cc a b c

aller à la page 18


correction exercice n° 10 : les 0 seuls avec les Ø

S

b0 0 0

0 0

c

a

d

S

b0 0 0

0 F 0

c

a

d

S

1 1 1

b1

1

c

a

d

S

1 1 1 F

b1

F

F F 1 F

c

a

d

Page 27


Solutions des exercices n° 9 et n° 10TD 3

Documents

Karnaugh - De Morgandownload.paulk.fr/cours/si/Logique 3.pdfKarnaugh - De Morgan Page 1 Tableau de Karnaugh à 2 variables I TABLEAU DE KARNAUGH _Reprenons une expression vue au chapitre