Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

2007-2008 http ://www.cnam.fr/depts/maths CNAM - Paris MVA003 Corrig´ e du devo

2007-2008 http ://www.cnam.fr/depts/maths CNAM - Paris MVA003 Corrig´ e du devoir n◦6 Exercice 1 1◦) Il est possible de tirer la table de v´ erit´ e de F(a, b, c, d) ` a partir de son expression ab ∨bd ∨abc ∨abcd ∨acd On en d´ eduit la forme canonique disjonctive en sommant les 11 mintermes (les termes valant 1 de la table de v´ erit´ e). Cela nous donne : F(a, b, c, d) = ¯ a¯ b¯ cd ∨¯ a¯ bcd ∨¯ ab¯ c ¯ d ∨¯ ab¯ cd ∨a¯ b¯ cd ∨a¯ bc ¯ d ∨a¯ bcd ∨ab¯ c ¯ d ∨ab¯ cd ∨abc ¯ d ∨abcd 2◦) Le diagramme de Karnaugh On grise les cases correspondant aux mintermes de F (voir table de v´ erit´ e pr´ ec´ edente pour les mintermes) 3◦) On recherche les grosses cellules du diagramme : ac ad b¯ c ¯ bd ¯ cd ab a b c d F mintermes 0 0 0 0 0 0 0 0 1 1 ¯ a¯ b¯ cd 0 0 1 0 0 0 0 1 1 1 ¯ a¯ bcd 0 1 0 0 1 ¯ ab¯ c ¯ d 0 1 0 1 1 ¯ ab¯ cd 0 1 1 0 0 0 1 1 1 0 1 0 0 0 0 1 0 0 1 1 a¯ b¯ cd 1 0 1 0 1 a¯ bc ¯ d 1 0 1 1 1 a¯ bcd 1 1 0 0 1 ab¯ c ¯ d 1 1 0 1 1 ab¯ cd 1 1 1 0 1 abc ¯ d 1 1 1 1 1 abcd b ¯ b ¯ b ¯ c c ¯ d d ¯ d a ¯ a 4◦) Sur le diagramme : la case a¯ bc ¯ d est recouverte seulement par la grosse cellule ac, la case ¯ a¯ bcd est recouverte seulement par la grosse cellule ¯ bd, la case ¯ ab¯ c ¯ d est recouverte seulement par la grosse cellule b¯ c, donc il faut prendre ces trois grosses cellules. Mais ` a elles toutes seules, elles reconstituent le diagramme, donc la m´ ethode de Karnaugh s’arrˆ ete l` a et la formule simpliﬁ´ ee est : F(a, b, c, d) = ac ∨b¯ c ∨¯ bd. b ¯ b ¯ b ¯ c c ¯ d d ¯ d a ¯ a 5◦) Le diagramme du compl´ ement s’obtient en « prenant le n´ egatif » du diagramme de Karnaugh de la fonction : les cases noires sont blanchies, les cases blanches sont noircies. Ce qui donne pour G le diagramme ci-dessous : b ¯ b ¯ b ¯ c c ¯ d d ¯ d a ¯ a 6◦) Le diagramme de Karnaugh de G poss` ede quatre grosses cellules. Ce sont : ¯ b¯ c ¯ d ¯ a¯ b ¯ d ¯ ac ¯ d ¯ abc Suivant les grosses cellules que l’on utilise, nous avons 2 possibilit´ es de simpliﬁcation par la m´ ethode de Karnaugh. Diagamme 1 : Diagramme 2 : b ¯ b ¯ b ¯ c c ¯ d d ¯ d a ¯ a b ¯ b ¯ b ¯ c c ¯ d d ¯ d a ¯ a G = :::::::::::::: ¯ b¯ c ¯ d ∨¯ ac ¯ d ∨¯ abc G = :::::::::::::: ¯ b¯ c ¯ d ∨¯ a¯ b ¯ d ∨¯ acb Pour le premier diagramme de Karnaugh les grosses cel- lules suivantes sont indispensables pour recouvrir les cases gris´ ees : ¯ b¯ c ¯ d, ¯ ac ¯ d et ¯ abc. On prend le sup et ceci fournit la formule polynomiale minimale G = ¯ b¯ c ¯ d ∨¯ ac ¯ d ∨¯ abc Pour le second diagramme, nous op´ erons de la mˆ eme mani` ere avec les grosses cellules : ¯ b¯ c ¯ d, ¯ a¯ b ¯ d et ¯ acb. On prend le sup et ceci fournit la formule polynomiale mini- male G = ¯ b¯ c ¯ d ∨¯ a¯ b ¯ d ∨¯ acb Page 1 kalfaian@cnam.fr Exercice 2 1◦) f(a, b, c, d) = a¯ bc ¯ d ∨¯ a¯ bc ¯ d ∨abcd ∨¯ abcd ∨¯ ab¯ cd ∨a¯ b¯ c ¯ d ∨ab¯ c ¯ d ∨¯ ab¯ c ¯ d ∨¯ a¯ b¯ c ¯ d On d´ etermine les grosses cellules : ¯ c ¯ d ¯ b ¯ d bcd ¯ abd ¯ ab¯ c Il n’y a pas de grosse cellule ` a 8 cases, 2 grosses cellules de 4 cases et 3 grosses cellules de 2 cases. Pour recouvrir les cases gris´ ees, il y a deux possibilit´ es : La premi` ere consiste ` a utiliser les 2 cellules de 4 cases et les 2 cellules de 2 cases : ¯ c ¯ d, ¯ b ¯ d, bcd et ¯ abd. On prend le sup et ceci fournit la formule polynomiale minimale G = ¯ b ¯ d ∨¯ c ¯ d ∨¯ abd ∨bcd Pour la seconde on utilise les 2 cellules de 4 cases et les 2 cellules de 2 cases : ¯ c ¯ d, ¯ b ¯ d, bcd et ¯ ab¯ c. On prend le sup et ceci fournit la formule polynomiale minimale G = ¯ b ¯ d ∨¯ c ¯ d ∨¯ ab¯ c ∨bcd D’o` u on obtient les deux formes disjonctives minimales : ¯ b ¯ d ∨¯ c ¯ d ∨¯ abd ∨bcd ou alors : ¯ b ¯ d ∨¯ c ¯ d ∨¯ ab¯ c ∨bcd b ¯ b ¯ b ¯ c c ¯ d d ¯ d a ¯ a b ¯ b ¯ b ¯ c c ¯ d d ¯ d a ¯ a 2◦) Il y a 2 formules polynomiales minimales qui sont celles vues ci-dessus : f(a, b, c, d) = ¯ b ¯ d ∨¯ c ¯ d ∨¯ abd ∨bcd = ¯ b ¯ d ∨¯ c ¯ d ∨¯ ab¯ c ∨bcd A priori, il n’y en a pas une meilleure que l’autre car chacune d’elle fait intervenir le mˆ eme nombre de litt´ eraux et de monˆ omes. Exercice 3 a) p q p ∧q p ∨(p ∧q) ¬(p ∨(p ∧q)) V V V V F V F F V F F V F F V F F F F V Ceci n’est autre que la table de v´ erit´ e de ¬p ; donc on a : ¬(p ∨(p ∧q)) = ¬p p q p ∨q ¬(p ∨q) ¬p ¬p ∧q ¬(p ∨q) ∨(¬p ∧q) V V V F F F F V F V F F F F F V V F V V V F F F V V F V ie la table de v´ erit´ e de ¬p ; ie celle vue aussi pour ¬(p ∨(p ∧q)) D` es lors, les 2 formes propositionnelles propos´ ees sont synonymes et s’´ ecrivent simplement ¬p b) h(x, y, z) = (x ∨xy)(y ∨yz)(z ∨zx) Prenons chacune des 3 expressions : 1) (x ∨xy) peut s’´ ecrire ¬(p ∨(p ∧q)) avec p ↔x q ↔y On a vu que l’on avait ¬(p ∨(p ∧q)) = ¬p ; ici, ceci permet d’´ ecrire (x ∨(xy)) = ¯ x 2) (y ∨yz) peut s’´ ecrire ¬(p ∨(p ∧q)) avec p ↔y q ↔z d’o` u : (y ∨yz) = ¯ y 3) (z ∨zx) peut s’´ ecrire ¬(p ∨(p ∧q)) avec p ↔z q ↔x d’o` u : (z ∨zx) = ¯ z Ces 3 r´ esultats partiels permettent d’obtenir h(x, y, z) = ¯ x¯ y¯ z ****** Page 2 kalfaian@cnam.fr uploads/s3/ 07-08-devoir-correctionmva003-8-1.pdf