Corrigé du TD 3 : Algèbre de Boole

Architecture des ordinateurs Corrig du TD 3 Algbre de Boole Arnaud Giersch Benot Meister et Frdric Vivien 1 Montrer comment loprateur et peut tre obtenu partir des oprateurs ou et non De mme pour loprateur ou avec les oprateurs et et non Correction nona ou b non a et non b nonnon a ou non b a et b nona et b non a ou non b nonnon a et non b a ou b 2 On note respectivement les oprateurs ou et xor et non par et Montrer laide de tables de vrit que AB ABAB et que AB ABAB Correction Tables de vrits A B A B AB AB AB ABAB 1 1 0 0 0 0 0 0 1 0 0 1 1 0 1 1 0 1 1 0 1 1 0 1 0 0 1 1 0 0 0 0 A B A B AB AB AB ABAB 1 1 0 0 0 1 0 0 1 0 0 1 1 1 1 1 0 1 1 0 1 1 1 1 0 0 1 1 0 0 1 0 3 Montrer que A AB AB et que AAB AB Correction On utilise la distributivit de loprateur ou sur loprateur et et inversement A AB AAAB 1AB AB AAB AA AB 0 AB AB 4 Dterminer le complment de lexpression ABC Correction On utilise les lois de de Morgan loprateur et est prioritaire ABC ABC ABC ABAC 5 Montrer que les deux rgles dassociativit sont duales ie montrer qu partir de la rgle dassociativit de Correction A BC AB C A BC AB C ABC ABC A B et C sont des variables muettes Par changement de variable A A B B C C 0 on obtient la proprit dassociativit du ou A0 B C A B C 1

6 crire lexpression AB uniquement avec les oprateurs ou et et non Correction Daprs 2 AB ABAB AB ABAB AB ABAB 7 Montrer que la fonction nor forme un groupe logique complet Correction Pour cela on montre que la fonction nor permet dexprimer tous les oprateurs logiques non norAA A et nornorAAnorBB norAB AB AB ou nornorABnorAB norAB AB AB 8 Simplifier au maximum les expressions logiques suivantes a ABAB Correction ABAB AAB 1 B B b ABAB Correction ABAB ABB A0 A c AAB Correction AAB A 1AB A1B A 1 A d AAB Correction AAB A0AB A0 B A0 A e ABABC D Correction ABABC D ABABC D ABAB C D donc daprs lexercice 8d AB f ABC ABCADB Correction ABC ABCADB ABC ABCADB daprs lexercice 3 ABC ABCADB ABC ADB AAD BBC daprs lexercice 8c ABC ABCADB AB g ABBAB 2

Correction daprs lexercice 2 ABBAB ABABBAB ABABBAB ABAB daprs lexercice 8a B h AABAB Correction AABAB AAB AB daprs lexcercice 3 AABAB AB AB 1 9 Dmontrer que toute fonction trois variables FABC est gale FABC AF1BC AF0BC Correction A est une variable boolenne les deux valeurs quelle peut prendre sont 0 et 1 si A 0 0 F1BC 1 F0BC F0BC FABC si A 1 1 F1BC 0 F0BC F1BC FABC 10 Montrer que les lois de de Morgan stendent un nombre quelconque de variables Correction a A1 A2 An A1 A2 An avec n 2 La dmonstration se fait par rcurrence sur n le nombre de variables n 2 cest la loi de de Morgan basique n gt 2 on utilise lassociativit de et A1 A2 An A1 A2 An1An A1 A2 An1 An A1 A2 An1 An A1 A2 An1 An b A1 A2 An A1 A2 An avec n 2 Le raisonnement est similaire 11 Gnration et simplification dexpressions logiques Considrer la fonction dfinie par la table de vrit ci-dessous A B C FABC 0 0 0 0 0 0 1 1 0 1 0 1 0 1 1 0 1 0 0 1 1 0 1 1 1 1 0 1 1 1 1 0 3

a Gnrer une expression logique correspondante i sous forme de sommes de produits Correction ABC ABC ABC ABC ABC ii sous forme de produits de sommes Correction ABC ABC ABC ABCABCABC b Simplifier les deux expressions en utilisant les rgles de lalgbre de Boole Correction i ABC ABC ABC ABC ABC ABC AABC ABC C ABC BC AB AACBBC ACBBC ABBC BC AB BC ii ABCABCABC AAABAC BABBBC CACBCCABC AABAC ABAC BC BCABC AAABAACAABAACABCABCA ABABBACBABBACBBCBBCB AC ABC ACC ABC ACC BCC BCC ABC ABABC ABC AC BC BC AB1C C BC A1BC ABBC BC AB BC c Construire le diagramme de Karnaugh et dterminer une expression logique associe Correction Une table de Karnaugh se construit partir de lexpression logique sous forme de somme de produits Dans la somme de produits utilise chaque produit doit contenir toutes les variables de lexpression Par exemple on mettra une expression dpendant de A et B sous la forme dune somme de produits de A A B B Pour mettre lexpression sous la forme voulue la formule A AB B est trs utile ABC ABC ABC ABC ABC Chaque colonne de la table de Karnaugh doit diffrer de ses voisines dun et un seul littral Nous avons faire les plus grands morceaux possibles 4

faire le moins de morceaux possibles le nombre de 1 dans un morceau doit tre une puissance de 2 ne faire un nouveau morceau que sil permet de regrouper des 1 qui nont pas encore t regroups en se rappelant que la ligne du bas et la ligne du haut sont considres comme adjacentes et quil en est de mme pour la colonne la plus droite et la colonne la plus gauche A BC A A 0 1 1 1 0 1 0 1 BC BC BC BC Chaque morceau donne naissance un produit de variables Lorsquune variable et son inverse sont dans le mme morceau cette variable slimine parce que AA 1 BC ABBC 12 Considrer les fonctions logiques suivantes Pour chacune delles construire le diagramme de Karnaugh utiliser le diagramme pour simplifier les expressions a F1ABC ABC ABC ABC Correction La table de Karnaugh est prsente figure 1 A BC A 1 1 0 1 0 0 0 0 BC BC BC BC A FIG 1 Table de Karnaugh pour F1ABC A BC A 1 1 1 0 0 0 1 0 BC BC BC A BC FIG 2 Table de Karnaugh pour F2ABC Expression simplifie F1ABC ABAC b F2ABC ABC ABABC Correction La table de Karnaugh est prsente figure 2 Expression simplifie F2ABC AC BC c F3ABC ABABC BC ABC Correction F3ABC ABABC BC ABC ABC ABC ABC ABC ABC ABC La table de Karnaugh est prsente figure 3 Expression simplifie F3ABC BAC d F4ABCD BCDABDABCD 5

A BC A A 0 1 1 0 0 1 1 1 BC BC BC BC FIG 3 Table de Karnaugh pour F3ABC AB 0 0 1 1 0 0 1 1 CD AB AB 0 0 0 0 0 0 0 C D C D CD CD AB AB FIG 4 Table de Karnaugh pour F4ABCD Correction F4ABCD BCDABDABCD ABCDABCDABCDABCDABCD La table de Karnaugh est prsente figure 4 Expression simplifie F4ABCD BD e F5ABCD AABABC ABCD Correction F5ABCD ABCDABCDABCDABCDABCD ABCDABCDABCDABCDABCD ABCDABCDABCDABCDABCD La table de Karnaugh est prsente figure 5 Expression simplifie F5ABCD BAC AB 1 1 1 1 1 1 1 1 CD AB AB 1 1 0 1 1 1 AB 0 1 AB C D C D CD CD FIG 5 Table de Karnaugh pour F5ABCD AB 1 1 0 0 0 0 1 1 CD AB AB 0 0 0 1 1 1 1 C D C D CD CD AB AB FIG 6 Table de Karnaugh pour F6ABCD f F6ABCD ABDACDABCDABDBCDABCD Correction F6ABCD ABCDABCDABCDABCD ABCDABCDABCDABCDABCD ABCD 6

La table de Karnaugh est prsente figure 6 Expression simplifie F6ABCD ADABDBD 7