Algébre de Boole Exrecice Corrigé

CORRIGÉ - ELE1300 – Hiver 2015 - Examen intra 1/10
Question 1 – Algèbre de Boole (6 pts – 20 minutes)

Sachant que A, B et C sont des variables booléennes, soit le circuit suivant :
a) Exprimer les signaux M, N, O et P en fonction des entrées A,B et C sous forme

disjonctive (somme de produits) en utilisant exclusivement l’algèbre de Boole. La
forme disjonctive ne doit pas nécessairement être optimale.
M = AB
N = ... = AC
O = ... = AC + AB
P = ... = A + B
b) Utilisez la décomposition de Shannon autant de fois que nécessaire pour simplifier

l’expression suivante au maximum :
F = ( A ⊕ B ⊕ C ) + ABC
Pour A=0, F=1

Pour A=1, F = B ⊗ C + BC
On recommence avec G = B ⊗ C + BC
Pour B=0, F=1

Pour B=1, G = C + C = 1
Donc, F=1 en tout temps
c) En utilisant une technique de votre choix, démontrez que :

( A ⊕ B) + ( B ⊕ C ) + ( A ⊕ C ) = ( A + B + C )( A + B + C )
En développant le membre de droite, il vient :
( A + B + C )( A + B + C ) = AB + AC + BA + BC + CA + CB
En développant le membre de gauche de l’équation initiale, on obtient les mêmes

implicants (dans un ordre inversé)
Question 2 – Synthèse de circuits (12 pts – 40 minutes)

a) La fonction FX est spécifiée par sa table de vérité :
A B C D Fx
0 0 0 0 1
0 0 0 1 1
0 0 1 0 1
0 0 1 1 1
0 1 0 0 0
0 1 0 1 0
0 1 1 0 0
0 1 1 1 0
1 0 0 0 1
1 0 0 1 -
1 0 1 0 1
1 0 1 1 0
1 1 0 0 0
1 1 0 1 -
1 1 1 0 1
1 1 1 1 1
b) Donnez un maximum d’implicants premiers sous forme littérale et soulignez les

implicants premiers essentiels. Aidez-vous de la table de Karnaugh suivante.
AB/CD 00 01 11 10
00 1 1 1 1
01 0 0 0 0
11 0 - 1 1
10 1 - 0 1
A B, BC , B D , AC D , ABC , ABD , AC D
c) Donnez un maximum d’impliqués premiers sous forme littérale et soulignez les
impliqués premiers essentiels. Aidez-vous de la table de Karnaugh suivante.
AB/CD 00 01 11 10
00 1 1 1 1
01 0 0 0 0
11 0 - 1 1
10 1 - 0 1
A + B, B + C , A + B + D, A + C + D
Proposez une forme disjonctive optimale et dessinez le meilleur circuit pour l’implanter :
Forme disjonctive optimale : AB + B D + ABC
Avec 4 portes NAND
Coût du circuit : 3+3+4+4 = 14
d) Proposez une forme conjonctive optimale et dessinez le meilleur circuit pour

l’implanter :
Forme conjonctive optimale : ( A + B )( B + C )( A + B + D )

Avec 4 portes NOR
Coût du circuit : 3+3+4+4 = 14

e) Implantez le circuit en utilisant exclusivement des multiplexeurs 2 vers 1. Justifiez votre

démarche! Le multiplexeur directement connecté à la sortie doit utiliser l’entrée A
comme variable de sélection.
Question 3 – Décodeur (2 pts – 10 minutes)

Montrer comment on peut réaliser un décodeur 4 vers 16 en utilisant deux décodeurs 2
vers 4 et des portes logiques ET. Dessinez votre schéma et justifiez votre réponse. Vous
n’êtes pas obligé de dessiner tout le circuit mais illustrez au moins les sorties 0,1,5,11 et
12.
Un décodeur calcule tous les mintermes. En prenant le ET logique d’une sortie du

premier décodeur avec une sortie du second décodeur, on obtient le minterme de 4
variables désiré.
11 AB 11 CD
10 A/B 10 C/D
01 /AB 01 /CD
00 /A/B 00 /C/D
A C
B D
Par exemple, la sortie 5 (0101 en binaire) s’obtient en prenant le ET logique de /AB avec
/CD pour obtenir le minterme /AB/CD
Question 4 – Conception de circuits logiques (4 pts – 20 minutes)

Réalisez un circuit de coût minimal à 10 paires d’entrées (Ai, Bi), (0 ≤ i ≤ 9) dont la sortie
F est vraie si et seulement si chaque paire d’entrées (Ai, Bi) a une valeur différente de la
précédente (Ai-1, Bi-1) pour i allant de 1 à 9.
Remarque : chaque paire d’entrées peut prendre 4 valeurs différentes : 00, 01, 10 et 11.
Les successions suivantes sont valides et entrainent F=1:

00-01-10-11-00-01-10-11-00-01
00-01-00-01-00-01-00-01-00-01
Par contre, la succession suivante est invalide et entraine F=0:

00-01-00-00-10-01-10-01-00-01
Piste : commencez par concevoir un circuit avec seulement deux paires d’entrées
Deux paires sont différentes si au moins une de leurs variables est différente, soit :
On implante donc 9 circuits de ce type (i allant de 1 à 9). La fonction F sera vraie si

toutes les fonctions Di sont vraies. On utilise donc un ET logique des 9 sorties, ou, plus
efficacement (un ET de OU s’implante avec des NOR):
Question 5 - Quine-McCluskey (6 pts – 30 minutes)

Soit la table de vérité de la fonction logique F(A,B,C,D) :
A B C D F
0 0 0 0 1
0 0 0 1 -
0 0 1 0 0
0 0 1 1 0
0 1 0 0 1
0 1 0 1 -
0 1 1 0 1
0 1 1 1 -
1 0 0 0 0
1 0 0 1 1
1 0 1 0 1
1 0 1 1 1
1 1 0 0 0
1 1 0 1 0
1 1 1 0 1
1 1 1 1 0
1) Retranscrire les minterms de la fonction F sous forme binaire en soulignant les
minterms facultatifs — exemple : 1001 pour A B C D.
F(A,B,C,D) = 0000, 0001, 0100, 0101, 0110, 0111, 1001, 1010, 1011, 1110
2) Procéder par la méthode Quine-McCluskey pour simplifier la fonction F(A,B,C,D) et

identifier les impliquants premiers
v 0000 v 000X 0X0X
v 0001 v 0X00 01XX
v 0100 v 0X01
v 0101 X001
v 0110 v 010X
v 1001 v 01X0
v 1010 v 01X1
v 0111 v 011X
v 1011 X110
v 1110 10X1
101X
1X10
Impliquants premiers sous forme binaire :

X001 – X110 – 10X1 – 101X – 1X10 – 0X0X – 01XX X110
0 ; 0x01 ; 111x ; x1x1
3) Utiliser la table suivante pour identifier les impliquants essentiels de F(A,B,C,D)
0000 0100 0110 1001 1010 1011 1110
a 0X0X (*) *
b 01XX * *
c X001 *
d X110 * *
e 10X1 * *
f 101X * *
g 1X10 * *
Impliquants essentiels :
0X0X1000 ; 111x ; x1x
1
4) Les impliquants essentiels couvrent-ils l’ensemble des minterms ? Si oui, donner

l’expression disjonctive simplifiée de la fonction F(A,B,C,D). Autrement, utilisez la
méthode de Petrick pour trouver toutes les solutions de coût minimal et l’expression
disjonctive simplifiée de la fonction F(A,B,C,D) qui correspond pour chaque solution.
L’impliquant a couvre seulement les deux premiers mintermes. L’équation simplifiée de

Petrick devient :
(b+d)(c+e)(f+g)(e+f)(d+g) = a (b+d) (c+e) (e+f) (f+g) (d+g)
= a (b+d) (e+cf) (g+df) = (b+d) (g+df) (e+cf)
= a (bg+bdf+dg+df) (e+cf) = (bg+dg+df) (e+cf)
= a (beg + deg + def + cdf … et autres termes plus cher)
= abeg + adeg + adef + acdf

abeg est la solution la moins chère car c’est la seule qui utilise 01XX (une porte à deux
entrées)
La solution finale est donc : 0X0X + 01XX + 10X1 + 1X10, soit :
F = AC + AB + ABD + AC D
5) Confirmer votre résultat en utilisant une table de Karnaugh pour illustrer tous vos
impliquants premiers trouvés
AB/CD 00 01 11 10
00 1 1 0 0
01 1 1 1 1
11 0 0 0 1
10 0 1 1 1
Question 6 Bonus
Cette question est facultative. Toutefois, la réussir montrerait que vous maitrisez la
matière à un niveau supérieur à ce qui est normalement attendu de vous et nous
permettrait de le prendre en note à votre avantage.
Dans le circuit suivant, quel est le nombre minimal d’entrées qui doivent être vraies pour
que la sortie soit fausse? Justifiez votre réponse et proposez une solution :
8 entrées vraies suffisent. Une solution est illustrée ci-dessus.
Bon travail !

Algébre de Boole Exrecice Corrigé

Transféré par

Droits d'auteur :

Formats disponibles

Algébre de Boole Exrecice Corrigé

Transféré par

Informations du document

Description originale:

Copyright

Formats disponibles

Partager ce document

Partager ou intégrer le document

Options de partage

Avez-vous trouvé ce document utile ?

Ce contenu est-il inapproprié ?

Droits d'auteur :

Formats disponibles

Algébre de Boole Exrecice Corrigé

Transféré par

Droits d'auteur :

Formats disponibles

CORRIGÉ - ELE1300 – Hiver 2015 - Examen intra 1/10

Question 1 – Algèbre de Boole (6 pts – 20 minutes)

a) Exprimer les signaux M, N, O et P en fonction des entrées A,B et C sous forme

b) Utilisez la décomposition de Shannon autant de fois que nécessaire pour simplifier

Pour A=0, F=1

Pour B=0, F=1

Donc, F=1 en tout temps

c) En utilisant une technique de votre choix, démontrez que :

En développant le membre de droite, il vient :

En développant le membre de gauche de l’équation initiale, on obtient les mêmes

Question 2 – Synthèse de circuits (12 pts – 40 minutes)

b) Donnez un maximum d’implicants premiers sous forme littérale et soulignez les

Forme disjonctive optimale : AB + B D + ABC

Avec 4 portes NAND

Coût du circuit : 3+3+4+4 = 14

d) Proposez une forme conjonctive optimale et dessinez le meilleur circuit pour

Forme conjonctive optimale : ( A + B )( B + C )( A + B + D )

Coût du circuit : 3+3+4+4 = 14

e) Implantez le circuit en utilisant exclusivement des multiplexeurs 2 vers 1. Justifiez votre

Question 3 – Décodeur (2 pts – 10 minutes)

Un décodeur calcule tous les mintermes. En prenant le ET logique d’une sortie du

Question 4 – Conception de circuits logiques (4 pts – 20 minutes)

Les successions suivantes sont valides et entrainent F=1:

Par contre, la succession suivante est invalide et entraine F=0:

On implante donc 9 circuits de ce type (i allant de 1 à 9). La fonction F sera vraie si

Question 5 - Quine-McCluskey (6 pts – 30 minutes)

2) Procéder par la méthode Quine-McCluskey pour simplifier la fonction F(A,B,C,D) et

Impliquants premiers sous forme binaire :

3) Utiliser la table suivante pour identifier les impliquants essentiels de F(A,B,C,D)

0000 0100 0110 1001 1010 1011 1110

4) Les impliquants essentiels couvrent-ils l’ensemble des minterms ? Si oui, donner

L’impliquant a couvre seulement les deux premiers mintermes. L’équation simplifiée de

(b+d)(c+e)(f+g)(e+f)(d+g) = a (b+d) (c+e) (e+f) (f+g) (d+g)

= a (b+d) (e+cf) (g+df) = (b+d) (g+df) (e+cf)

= a (bg+bdf+dg+df) (e+cf) = (bg+dg+df) (e+cf)

= a (beg + deg + def + cdf … et autres termes plus cher)

= abeg + adeg + adef + acdf

La solution finale est donc : 0X0X + 01XX + 10X1 + 1X10, soit :

8 entrées vraies suffisent. Une solution est illustrée ci-dessus.

Vous aimerez peut-être aussi