Ce TD propose des exercices corrigés sur l’algèbre de Boole et les diagrammes ou tableaux de Karnaugh.
Exercice 1
La société K-Gaz décide de recruter en interne des collaborateurs pour sa filiale.
Pour chaque employé, on définit les variables booléennes suivantes :
- a=1 s’il a plus de 5 ans d’ancienneté dans l’entreprise
- b=1 s’il possède un BTS-IG
- c=1 s’il parle couramment l’anglais
La direction des ressources humaines décide que pourront postuler les employés :
- qui satisfont aux trois conditions
- ou qui ont moins de 5 ans d’ancienneté mais qui maitrise l’anglais
- ou qui ne maitrisent pas l’anglais qui possèdent un BTS-IG
Voici les questions :
- Donner les critères RH en expression booléenne
- Représenter l’expression par un tableau de Karnaugh
- Le simplifier
- Retrouver le résultat par calcul à l’aide de retour arrière
- Conclure sur la version simplifiée
Question 1
Question 2
On marque un 1 à chaque fois qu’un élément de l’expression booléenne est vrai.
Question 3
Pour simplifier l’expression, on regarde dans le tableau les carrés de 4 éléments ou les rectangles de deux éléments (pas forcement connexe) dont un littérale au plus change entre ligne et colonne.
Par exemple, le rectangle vert, seul le littérale b change, donc äc ne change pas (ä en considérant la ligne et c en considérant les deux colonnes). Dans le carré rouge, en colonne, seul b change (a change dans les lignes, et c change en colonne).
On en déduit l’expression simplifié.
Question 4
La technique du retour arrière consiste à revenir peu à peu sur les résultats en fonction du manque d’élément calculatoire. Par exemple, après factoriser par b, on aura ac+C_barre. Au vue de la formule, il est évident qu’il faudrait ac+äc+c_barre pour que cette expression soit égale à 1.
Ainsi, à chaque fois qu’il manque un élément calculatoire pour arriver à sa finalité, il est possible de transformer les lignes de calcul précédente en ajoutant des éléments déjà existant ou en multipliant par 1 comme par exemple b+b_barre pour atteindre ses fins.
Voici le raisonnement final :
Question 5
En en déduit que la RH accepte les postulants qui possède un BTS-IG ou qui a moins de 5 ans d’ancienneté mais maitrisant l’anglais.
Exercice 2
Le responsable du parc informatique d’une entreprise envisage l’acquisition de nouveaux ordinateurs. Pour s’équiper, ce responsable s’adresse à une entreprise de vente de matériel informatique qui propose des configurations prédéfinies (ordinateur et périphériques).
On définit les critères :
a : la configuration comprend un graveur de DVD;
b : la configuration comprend une imprimante;
c : la configuration comprend un scanner.
Les contraintes d’équipement excluent les configuration avec graveur de DVD mais sans scanner, ainsi que les configurations sans graveur et sans imprimante.
Voici les questions :
- Donner l’expression booléenne E traduisant les conditions d’exclusion
- Dresser la table de Karnaugh de E
- Traduire et dire si a(b_barre)c est accepté
- Déterminer une expression de F traduisant les conditions d’acceptation.
- Traduire la version simplifiée de F.
1- L’expression est E=a(c_barre)+ä(b_barre)
2- La table de Karnaugh de E est
3- l’expression signifie équipé d’un graveur DVD et d’un scanner mais sans imprimante. Elle n’est pas présente dans le Karnaugh de E donc elle est autorisée
4- Voici le Karnaugh de E
En vert c varie. En rouge b varie.
5- L’expression simplifié donne soit un graveur et un scanner; soit pas de graveur et une imprimante.
Exercice 3
Le directeur des ressources humaines (DRH) d’une mairie doit recruter une personne pour un travail concernant la circulation des voitures dans le centre-ville.
Pour faire son choix, le DRH met en place trois critères de sélection concernant les connaissances en informatique, l’expérience dans le domaine concerné et le suivi d’un stage de formation spécifique.
La personne recrutée devra:
- avoir des connaissances informatiques et de l’expérience dans le domaine concerné;
- ou ne pas avoir de connaissances informatiques, mais avoir suivi un stage de formation spécifique;
- ou ne pas avoir d’expérience dans le domaine concerné, mais avoir suivi un stage de formation spécifique.
On définit les trois variables booléennes a, b et c suivantes :
- a =1 si la personne possède des connaissances informatiques, a =0 sinon;
- b = 1 si la personne possède de l’expérience dans le domaine concerné, b = 0 sinon;
- c = 1 si la personne a suivi un stage de formation spécifique, c=0 sinon.
Voici les questions :
- Décrire la situation correspondant au produit a.b./c
- Définir l’expression booléenne E correspondant aux critères de sélection du DRH.
- Trouver une écriture simplifiée de l’expression booléenne E.
- Expliquer la version simplifiée.
1- a.b./c signifie que la personne possède des connaissances informatiques (a=1) et de l’expérience dans le domaine concerné (b=1), mais n’a pas suivi de stage spécifique de formation (c=0).
2- E = a.b + /a.c + b.c
3- Le tableau de Karnaugh et son modèle simplifié est le suivant
4- Cela signifie : La personne possède des connaissances informatiques (a=1) et de l’expérience dans le domaine concerné (b=1) OU a suivi un stage de formation spécifique (c=1).
