1 12/09/06

Créé le 08/09/05 10:05

TD combinatoire
 Tableaux de Karnaugh

Des pb ont amenés à resoudre les TK suivants :

1
ab ab
cd 00 01 11 10 cd 00 01 11 10
00 1 0 0 1 00 0 1 0 0
01 0 1 0 0 01 0 1 1 0
11 1 1 0 0 11 1 1 0 0
10 1 1 0 1 10 1 1 0 1

ab ab
cd 00 01 11 10 cd 00 01 11 10
00 1 ∅ 0 1 00 0 ∅ 0 0
01 ∅ 1 1 1 01 ∅ 0 1 1
11 1 1 0 0 11 0 0 1 1
10 1 1 0 1 10 0 0 0 0

ab
cd 00 01 11 10
00 1 1 0 0
01 0 1 1 1
11 1 1 1 1
10 0 1 0 0

abc
de 000 001 011 010 110 111 101 100
00 0 1 0 0 0 1 1 0
01 0 0 1 0 0 1 0 0
11 1 0 1 0 0 1 0 1
10 0 1 0 0 0 1 1 0

2 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 2 parmi 5 entrelacé
I) Présentation
Un chariot filoguidé est équipé d’un lecteur de code à barres capable de lire le code « 2 parmi
5 entrelacé » permettant d’identifier les produits transportés.
Chaque produit est identifié par un nombre de quatre chiffres C3, C2, C 1, C 0.
C3C2 C1C0

Le code utilise 5 bits (2 d’entre eux valent 1 et les 3 autres valent 0) pour coder un chiffre
décimal.
Les chiffres de rang impair(C3, C1) sont codés sur les barres noires.
Les chiffres de rang pair (C2, C 0) sont codés sur les espaces entre les barres noires
Les 1 sont codés par les barres ou les espaces « larges »
Les 0 sont codés par les barres ou les espaces « étroits »

Chaque chiffre de 0 à 9 est codé sur 4 bits: a, b, c, d de poids respectif :1, 2, 4, 7. Le code est
complété par un bit de centrale de parité e de poids O
Rappel
N10=1.a+ 2.b+3.c+4.d +0.e
e prend les valeurs 0 ou 1 afin que chaque nombre exprimé (en fonction de a, b, c, d, e)
comporte toujours et uniquement 2 bits à 1

1)Déterminer les codes des chiffres de 0 à 9 en complétant le tableau.

Conseil:
• compléter le tableau (colonnes a, b, c, d ) pour les chiffres 1 à 9
• en déduire le code du chiffre 0
• et enfin compléter la colonne e
2)Déterminer le nombre correspondant au produit transporté du code barre dessiné ci-dessus.

3)Le calculateur de la machine traduit chaque chiffre de ce code à barres en un nombre

binaire naturel (donc ordonné) codé sur les quatre bits S3, S2, S1, S0 . Le poids du bit Si
vaut 2i
Compléter la table de vérité des sorties Si en fonction des entrées a, b, c, d, e.

4)Determiner avec un tableau de Karnaugh 5 entrées, l'eqt de sorties S1.

3 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 2 parmi 5 entrelacé (doc réponse)
1) et 3)
Poids 1 2 4 7 0 Binaire naturel
Bits a b c d e S3 S2 S1 S0
0
1
2
3
4
5
6
7
8
9

2)

4)

abc

de

4 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 DISTRIBUTEUR DE BOISSONS
II)Etude

Le distributeur de boissons doit remplir les fonctions suivantes:

• E : distribution d'eau
• M : distribution de sirop de menthe.
• C : distribution de sirop de citron.
• R : restitution de jeton.

Il est commandé par 4 capteurs :

• 3 boutons poussoirs
e (eau), m (menthe), c (citron),
• un detecteur de jeton p.

Le fonctionnement doit se faire de la manière suivante :

• rien n’est gratuit
• on ne fournit pas de sirop sans demande d’eau
• on ne fournit pas d'eau seule.
• on ne peut pas mélanger menthe et citron.
• en cas de paiment on rend la piéce d'une demande érronée.

1)Donner la table de vérité traduisant le fonctionnement de la machine.

2)Donner les tableaux de karnaugh des fonctions
3)Donner les fonctions sous forme canonique
4)Etablir les diagrammes logiques avec des portes OUI , NON , OU , ET

SIMPLIFICATIONS

m.o.p.(o+p)+p.(o+m.p)

a.b.c.d+a.b.(c+d)=S
Simplifier sous forme somme de produit logique selon une méthode au choix

S= a.b.c.d +a.b.c.d + a.b.c.d + a.b.c.d + a.b.c.d + a.b.c.d + a.b.c.d méthode au choix

f(a,b,c,d)=(a.b.c + d + b).b + (d + a) + b.(c + a)

a)développer l'expression
b)simplifier

5 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
1) Soit la fonction :

• simplifiez l'équation (je vous conseille un tableau de Karnaugh)

• tracez le schéma de f, à l'aide de portes logiques.

2) soit la fonction

• trouvez (équation la plus simple possible)

• tracez le schéma de f uniquement à l'aide de portes NOR
• tracez le schéma de f uniquement à l'aide de portes NAND

I)Simplifier les équations suivantes :

L1 = a + b + a.b avec les propriétés de l’algèbre de boole
L2 = a.b.c + a.b.c + a.b.c + a.b.c + a.b.c méthode au choix.
L3 = a.b.c.d + a + b + c + d + a.b.c.d + a.b.c.d + a.b.c.d + a.b.c.d + a.b.c.d
le plus efficacement possible

S= a.b.c +a.b.c+a.b.c+a.b.c avec 2 méthodes

Exercice 4
Construire les tables de vérité (entrées A, B et C) correspondant aux
expressions booléennes suivantes:
X=(A +B).(B+C)
Y=A +AB+ABC
Z=(A +A).(B+B).(C+C)

Exercice 5
Écrire l’équation logique ou booléenne réalisée par le circuit logique de la
figure 5.

Exercice 6
Reprendre le même énoncé que l’exercice 5 avec le circuit de
la figure 6.

Exercice 7
Proposer un circuit logique avec des portes OU, ET, NON,
NAND permettant de représenter l’équation logique:
S=A.B+C.D+E.F

Exercice 8
Reprendre le même énoncé que l’exercice 7 avec des
portes OU, ET et_NON pour l’équation logique:
S = A.(B + C) + D.E

Exercice 9
Écrire les équations logiques non simplifiées correspondant aux tableaux de
Karnaugh de la figure 9. Réduire et simplifier ces équations.

Exercice 10
Reprendre le même énoncé que l’exercice 9 à partir de la figure 10.
6 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
Exercice 11
Réduire et simplifier les expressions booléennes suivantes:
Y=A.B+A.B+A.B
Z = A.B.C + A.B.C + B.C.D
S=(A+B).(A+C).(B+C)
T = A.B.C.D + A.B.C.D + A.B.C.D + A.B.C.D

Exercice 12
En utilisant le théorème de Morgan simplifier les expressions de la figure 12.

Exercice 13
Connaissant les signaux d’entrée a et b, tracer la forme de l’onde de sortie S du circuit de la figure 13.
Refaire la question si a disparaît. Même question si b disparaît.

Exercice 14
Reprendre l’énoncé de l’exercice 13 avec une porte
NAND ou NON ET.

Monte-Charge

Un monte-charge doit permettre le levage de

masses m comprises entre 20 et 80 kg. Pour
cela, il comporte une plate-forme reposant sur
des ressorts. Selon l'importance des charges à
soulever, trois contacts réglables sont établis.
Les conditions de fonctionnement sont les
suivantes :

m>5 a=1
m>20 b=1
m>80 c=1

1. À vide, le monte-charge peut fonctionner. Aucun des contacts n'est activé.

2. Pour des charges comprises entre 5 et 20 kg, le monte-charge ne peut fonctionner.
3. Pour les charges comprises entre 20 et 80 kg, le monte-charge peut fonctionner.
4. Pour des charges supérieures à 80 kg, le monte-charge ne peut fonctionner.

Questions
1. Déterminer la table de vérité de la variable logique S qui vaut 1 quand le fonctionnement
du monte-charge est autorisé.
2. En déduire l’équation de S que l’on simplifiera.
3. A partir de la table de vérité, déterminer l’expression de S . En déduire une nouvelle
manière d’obtenir l’expression de S.
4. Représenter le schéma à contacts de S.
5. Représenter le logigramme de S.

7 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 COMMANDE DE PHARES DE VOITURE

I)Présentation

Une automobile comprend 4 paires de phares qui sont:

• V veilleuses
• C feux de croisement
• R feux de route
• A phares antibrouillard
Ces phares sont commandés par une série de 4 interrupteurs: v, r, c, a.

On impose le fonctionnement suivant:

• Tout interrupteur allume nécessairement les veilleuses.
• On ne peut avoir allumé simultanément deux paires de phares (en plus des
veilleuses).
• Les antibrouillards sont prioritaires sur les feux de route.
• Les feux de croisement sont prioritaires sur les feux de route et les antibrouillards.

Les fonctions logiques V, C, R, A seront actives au niveau 1.

II)Etude

1. Mettre en place la table de vérité des fonctions logiques V, C, R, A en fonction des

commandes v, c, r, a.
2. Donner les tableaux de Karnaugh des fonctions logiques.
3. Ecrire les équations de V, C, R, A sous forme canonique.
4. Donner le diagramme logique de chaque fonction V, C, R, A.
5. Donner le schéma de câblage électrique du système. (schéma relais)

12 V 0V

8 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 POLICE D’ASSURANCE

I)Présentation.
Les conditions de délivrance d'une police d'assurance précisent que cette police ne
peut être souscrite que par les personnes remplissant au moins l'une des conditions suivantes :
•avoir souscrit à la police n°19, être de sexe masculin et marié ;
•avoir souscrit à la police n°19, être marié et âgé de moins de 25 ans ;
•n'avoir pas souscrit à la police n°19, être mariée et de sexe féminin ;
•être de sexe masculin et âgé de moins de 25 ans ;
•être marié et âgé de plus de 25 ans.

II)Etude
La lecture de ces conditions donne l'impression d'une surabondance d'informations.
Afin de simplifier les condition d’attribution d’une assurance procéder comme suit:
1. Parametrer très rigoureusement chaque condition
2. Ecrire l’équation
3. Simplifier par une méthode au choix
4. Dites quels sont les conditions minimales à remplir pour être assuré.
5. Tracer le logigramme de la fonction

Robot ramasseur et lanceur de balles

Un robot peut ramasser jusqu’à 7 balles dans son magasin, avant d’entamer une phase de tir.
7 capteurs Ci donnent une information présence-absence devant la position que peuvent
occuper chacune des 7 balles.

Il peut donc y avoir entre O et 7 balles dans le magasin.

Combien faut-il réserver de bits, au minimum, dans la mémoire du calculateur qui gère le
robot, pour stocker l’information « nombre de balle(s) présente(s) dans le magasin »? Vous
prendrez soin de justifier votre réponse en étant claire et concis.
9 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 ROUE CODEUSE
I)Présentation

Une roue codeuse permet de réaliser le

transcodage décimal-binaire. Elle est
composée d'une roue graduée de 0 à 9 et
d'un disque comportant des zones
conductrices. 5 balais (1 commun et 4
pour les bits d,c,b,et a) sont en contact
avec le disque.

Méthode de transcodage décimal /

binaire
On peut exprimer un chiffre décimal
N(10) en un nombre binaire de 4 bits a, b,
c, d
N(10)=d.23 + c.22 + b.21 + a.20
Exemple:
N(10)=7 donne en binaire : 0.23 + 1.22 + 1.21 + 1.20 soit: d=0, c=1, b=1, a=1 donc
7 s'écrit en binaire: 0111

II)Etude
On cherche à déterminer quels sont les secteurs conducteurs du disque de la roue codeuse qui
permettent le contact entre les balais a, b, c, d d'une part et le commun d'autre part lorsque le
bit correspondant est à 1. Pour cela on demande:
1) Pour obtenir dix codes (eqt booléennes), représentant les chiffres de 0 à 9, toutes les
combinaisons de a, b, c, d ne sont pas utilisées, il est donc possible pour simplifier les
relations d'utiliser une table de décodage qui fonctionne comme suit:
• Construire un tableau de Karnaugh ayant pour entrées les variables d, c, b, a et inscrire
dans chaque case la valeur decimale (de 0 à 9) correspondant à l'etat des variables.
• Les cases vides correspondent à des combinaisons inutilisées qui peuvent donc prendre la
valeur ∅.
• Pour effectuer la simplification on opère les regroupements des cases adjacentes par 2, 4,
8, ou 16, afin que chaque regroupement soit le plus grand possible et n' inclut qu'un seul
chiffre decimal
2) Donner les 10 équations simplifiées de chaque valeur décimale (de 0 à 9) en fonction des
variables binaires.

3) Sur le dessin de la roue codeuse du I) colorier les secteurs qui devront être conducteurs.
4)Etablir pour les N(10) =7;8;9, les diagrammes logiques avec des portes OUI , NON , OU ,
ET

10 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 Additionneur 4 bits
On souhaite réaliser une "additionneuse" de deux chiffres decimaux (A10 et B10) dont le
résultat (R10) sera affiché sur 2 afficheurs 7 segments.(On Chiffre A10
étudiera ici que l'addition dont le resultat n'exedera pas 1510 (decimal)

inclus). additionneur R10=A10+B10

Chiffre B10
On a donc le schéma globale suivant: (decimal)
Soit le schema plus complet
a0
c0 b0 a0
a0 a Circuit
c0
a1 d Circuit de c1 d'affichage f0 g0 b0
des unité d0
Chiffre A10 Roue d codage de
a2 c2 (100) e0
c0
i s0
(decimal) codeuse A 1 mot (S) e0 d
f0 0
a3 t s1 de 4 bits c3 g0 Chiffre des unités
i s (0 à
2 1111) à 2 a1
b0 o a1
mots (C d0 b1
n s3 Circuit
b1 et D) de 4 d1 c1 f1 g0 b1
Chiffre B10 Roue n d'affichage
bits (0 à des d1
(decimal) codeuse B b2 e d2 e1 e1 c1
1001) dizaines d1
b3 u
d3 (101) f1
r g1 Chiffre des dizaines

Interessons-nous au module d’addition.

Le schéma ci-contre représentele principe de l’addition de 2
entiers positifs à 4 bits

1. Completer resultat et retenue pour cet exemple :

22 21 20

A 1 0 1
B 0 1 1
Si
Ri

2. completer la table de verité d’un

additionneur donné pour chaque bit ai bi ri- si ri
1
de rang i
3. Determiner et simplifier l’equation 0 0 0
de si=f(ai,bi,ri-1) 0 0 1
4. Determiner et simplifier l’equation 0 1 0
de ri=f(ai,bi,ri-1) 0 1 1
1 0 0
1 0 1
1 1 0
1 1 1

5. Determiner le logigramme d’un module additionneur de ai

si
rang i bi
Module de
rang i
ri
ri-1

11 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 Contrôle de pieces
Mise en situation
Lors de la fabrication d’une pièce, on est amené à vérifier si la cote fabriquée (la dimension)
est bien égale à la cote demandée. En effet lors de la fabrication, il est impossible d’obtenir
une cote absolument égale à la cote demandée, ceci à cause de divers imprécisions.
On est donc amené à définir un intervalle de tolérance afin que la pièce fabriquée convienne
au mécanisme dans lequel elle doit s’insérer. Par exemple, C = 40 ± 0,02 signifie que, si la
dimension de la cote obtenue est comprise entre 39,98 et 40,02 , alors la pièce sera considérée
comme bonne. Dans tout autre cas, la pièce sera considérée comme mauvaise.
On désire vérifier les cotes extérieures de l’embout avant d’un vérin. Pour gagner en rapidité,
on réalise le montage de contrôle représenté par le dessin ci-dessous. On considère comme
négligeable l’erreur due à la lecture.
Description du système
Ce mécanisme est composé de deux leviers munis chacun de deux capteurs à contact qui
recueillent l’information : « inclinaison du levier ». Par exemple, le capteur « a » informe que
la cote verticale de l’embase est trop faible, à contrario, le capteur « b » informe que la cote
verticale de l’embase est trop grande.

Fonctionnement
• Lorsque les deux cotes sont à l’intérieur des intervalles de tolérance, aucun des capteurs
« a, b, c, d » n’est actionné. Le voyant vert (V) s’allume.
• Lorsque l’une ou les deux cotes sont trop fortes, le voyant bleu (B) s’allume. La pièce doit
être réusinée.
• Lorsque l’une des deux cotes est trop faible, le voyant rouge (R) s’allume. La pièce est
mise au rebut..
Etude (Réponses sur copie)
1. Donner la table de vérité du système de contrôle des pièces.
2. Donner le tableau de Karnaugh de chacun des voyants.
3. En regroupant sur les "1", Donner la plus simple équation logique de fonctionnement
de chacun des voyants.
4. Tracer le logigramme matérialisant les équations précédemment définies.
5. Tracer le schema à contacts electrique du systeme.

12 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 Transcodeur et afficheur 7 segments
On affectera un indice 2 ou 10 pour signifier la base d'un chiffre

I)Position du probleme
On souhaite réaliser une "additionneuse" de deux chiffres decimaux (A10 et B10) dont le
résultat (R10) sera affiché sur 2 afficheurs 7 Chiffre A10
segments.(On étudiera ici que l'addition dont le (decimal)

resultat n'exedera pas 1510 inclus). additionneur R10=A10+B10

On a donc le schéma globale suivant: Chiffre B10
(decimal)

Soit le schema plus complet

a0
c0 b0 a0
a0 a Circuit
Circuit de c1 c0
d d'affichage f0 b0
a1 des unité d0 g0
Chiffre A10 Roue d codage de
a2 c2 (100) e0
c0
(decimal) codeuse A i s0 1 mot (S)
f0
e0
d0
a3 t s1 de 4 bits c3 g0 Chiffre des unités
i s (0 à
2 1111) à 2 a1
o a0
b0 mots (C d0 b1
n s3 Circuit
b1 et D) de 4 d1 c1 f0 g0 b0
Chiffre B10 Roue n d'affichage
bits (0 à des d1
(decimal) codeuse B b2 e d2 e1 e0 c0
u 1001) dizaines d0
b3 d3 (101) f1
r g1 Chiffre des dizaines

Deja traité en TD

II)Afficheur 7 segment
On souhaite réaliser le cablage du circuit a0
d'affichage d'un chiffre decimal correspondant a0
b0
à la valeur binaire naturelle du nombre C2.Le c0 Circuit
c0 f0 g0 b0
nombre C2 entrant est donc compris entre 010 et c1 d'affichage
des unité d0
910 ou.00002 et 10012 c2 e0 e0 c0
(100) d0
c3 f0 Chiffre des unités
Affichages possibles: g0

1 Completer la table de verité uniquement pour la variable de sortie "ao" (ao=0 donc
éteint et ao=1 donc allumé). Les autres segments ne seront pas traités.

13 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 décimal Unités en binaire a b c d e f g
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
12 1 1 0 0
13 1 1 0 1
14 1 1 1 0
15 1 1 1 1

2 Donner le tableau de karnaugh qui donnera l'eqt de "ao"

3 Simplifier sur les "1" le TK
4 Donner l'eqt qui regit l'état de "ao"
5 Donner le schéma de cablage avec des portes logiques

III)Circuit de codage
Le résultat de l'addition est un nombre de 4 bits compris entre 010 et 1510. Le probleme est que
le decimal ne permet pas d'écrire de chiffres superieur à 9.
l'affichage d'un resultat en base 10 nécessitera deux variables (donc 2 afficheurs 7 segments).
Il faut donc integrer dans le montage un circuit qui se chargera de transformer un nombre
binaire (S) de 4 bits (de 00002 à 11112 ou de 010 à 1510) en deux nombre binaires (C et D) de 4
bits (de 00002 à 10012 ou 010 à 910). Ces 2 nombres correspondent bien sur au unités et au
dizaines

14 12/09/06
Créé le 08/09/05 10:05
TD combinatoire
 Résultat S D (dizaines) C (unités)

s3 s2 s1 s0 d3 d2 d1 d0 c3 c2 c1 c0
0 0 0 0 0
1 0 0 0 1
2 0 0 1 0
3 0 0 1 1
4 0 1 0 0
5 0 1 0 1
6 0 1 1 0
7 0 1 1 1
8 1 0 0 0
9 1 0 0 1
10 1 0 1 0
11 1 0 1 1
12 1 1 0 0
13 1 1 0 1
14 1 1 1 0
15 1 1 1 1

1. Completer la table de verité

2. Donner le tableau de karnaugh qui donnera l'eqt de "c1"
3. Simplifier le TK
4. Donner l'eqt qui regit l'état de "c1"
5. Donner le schéma de cablage avec des portes logiques de "c1"

15 12/09/06
Créé le 08/09/05 10:05
TD combinatoire