Remerciez-le!

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

Cours de mathématiques Formation continue — ADSIO Feuille 1 : Algèbre de Boole

Cours de mathématiques Formation continue — ADSIO Feuille 1 : Algèbre de Boole Exercice 1 Démontrer les propriétés suivantes en utilisant les règles du calcul booléen : 1) (a + b).(a + b) = b 2) a + b.a = 1 3) a.b + a + b = 0 4) (a ⇒b) = a + a.b puis (a ⇒b) = a + b 5) (a ⇒b) = a.b 6) (a ⇒b) = (b ⇒a) (raisonnement par contraposée) 7) a = (a ⇒0) (raisonnement par l’absurde) 8) (a ⇔b) = (a ⇒b).(b ⇒a) 9) (a ⇒(b + c)) = ((a.b) ⇒c) 10) (a + b).(a + c) = a + b.c 11) a.b.c + a.b.c + a.b.c + a.b.c = a Exercice 2 1) On peut réaliser des portes logiques avec le démineur de Windows. Montrer que la porte suivante correspond à la porte OU (on note 1 s’il y a une mine) 2) Montrer que la porte suivante correspond à ET 3) Montrer que la porte suivante correspond à XOR Exercice 3 Simpliﬁer le circuit logique présenté dans le cours. Exercice 4 1) On considère un ensemble E muni d’une structure d’algèbre de Boole. Soit S l’expression S = a.b.c + a.b.c + a.b.c. Montrer, par un calcul direct que S = a.c + a.b.c puis que S = a.c + b.c. 2) Un immeuble comprend six logements dont les surfaces ﬁgurent dans le tableau ci-dessous : Logement 1 2 3 4 5 6 Superﬁcie 55 105 112 228 247 253 Les logements 1 et 3 appartiennent à Monsieur A, les logements 2 et 4 appartiennent à Madame B, les 5 et 6 appartiennent à Monsieur C. Chacun détient à l’assemblée des copropriétaires un nombre de voix égal à la superﬁcie totale de ses logements, exprimée en m2. Ainsi, Monsieur A dispose de : 55 + 112 = 167 voix. Une proposition concernant le remplacement de la chaudière est mise au vote à l’assemblée. Pour être adoptée, elle doit recueillir la majorité des voix, soit 501 voix. Si A vote « pour », son vote favorable est désigné par a. S’il vote « contre », ou s’il s’abstient, son vote est désigné par a. De même pour B et C. a) Quelle situation de vote traduit le produit booléen a.b.c ? b) Écrire l’expression booléenne qui exprime la condition V pour que la proposition soit adoptée. c) En utilisant les résultats de la question 1), écrire cette condition sous forme simpliﬁée, puis la traduire par une phrase explicative. Exercice 5 (Registre à décalage à rétroaction linéraire) 1) On considère la suite de bits (Sn)n≥1 déﬁnie par Sn+2 = Sn+1 ⊕Sn, n ≥1, initialisée par la graine S = (S1, S2). a) On suppose que S = (1, 0). Trouver les prochains bits de la suite. Vériﬁer que la suite est pério- dique et déterminer la période. b) Même question avec les graines S = (0, 1) puis S = (1, 1). 2) On considère la suite de bits (Sn)n≥1 déﬁnie par Sn+4 = Sn+2 ⊕Sn, n ≥1, initialisée par la graine S = (S1, S2, S3, S4). a) On suppose que S = (1, 1, 0, 1). Trouver les prochains bits de la suite. Vériﬁer que la suite est périodique et déterminer la période. b) Même question avec les graines S = (1, 0, 1, 0) puis S = (0, 1, 1, 1). c) Montrer que pour toute condition initiale, une telle suite est périodique de période (au plus) 6, i.e. que pour tout n ≥1, Sn+6 = Sn. 3) On considère maintenant la suite Sn+4 = Sn+1 ⊕Sn, n ≥1, initialisée par S = (S1, S2, S3, S4). a) Étudier la suite initialisée à S = (1, 0, 1, 1). Trouver la longueur du cycle de ce générateur. b) Montrer que pour toute condition initiale, une telle suite est périodique de période (au plus) 15. Exercice 6 (Chiﬀre de Vernam) On considère un message M que l’on veut chiﬀrer, à l’aide d’une clé secrète K (uniquement connue par l’émetteur et le destinataire). On suppose que M et K sont codés en binaires et sont de même longueur. Le message chiﬀré est obtenu par C = M ⊕K. 1) Calculer C pour M = 0101010110 et K = 1100010101. 2) Montrer que l’on reconstitue M à l’aide de la formule M = C ⊕K. 3) Montrer comment un attaquant peut trouver K à l’aide d’un seul message M et de sa version chiﬀrée C. Remarque : c’est pour cela qu’il faut changer de clé secrète à chaque utilisation. Exercice 7 A) Soit f la fonction booléenne de quatre variables booléennes a, b, c, d déﬁnie par : f(a, b, c, d) = ab + bcd + abcd + abc + abcd. Si d prend la valeur 1, on note g la fonction de trois variables déﬁnie par : g(a, b, c) = f(a, b, c, 1). 1) Expliciter g(a, b, c). 2) Simpliﬁer la fonction g. 3) Déterminer la fonction g, complémentaire de la fonction g. B) Dans une entreprise, les personnes pouvant bénéﬁcier de l’attribution d’une prime sont les suivantes : • Toute personne de plus de 40 ans, ayant plus de 10 ans d’ancienneté. • Toute personne de plus de 10 ans d’ancienneté ayant suivi un stage de formation dans les cinq dernières années, et gagnant moins de 1500 e par mois. • Toute personne de moins de 40 ans, qui n’a pas suivi de stage de formation dans les cinq dernières années, mais ayant plus de 10 ans d’ancienneté et gagnant moins de 1500 e par mois. • Toute personne de moins de 40 ans, ayant moins de 10 ans d’ancienneté mais qui a suivi un stage de formation dans les cinq dernières années. • Toute personne de plus de 40 ans, de moins de 10 ans d’ancienneté qui a suivi un stage de formation dans les cinq dernières années bien qu’elle gagne plus de 1500 e par mois. On note a, b, c et d les quatre variables booléennes caractérisant respectivement les propriétés « être une personne de plus de 40 ans », « avoir plus de 10 ans d’ancienneté », « avoir suivi un stage de formation dans les cinq dernières années » et « gagner moins de 1500 e par mois ». 1) a) Quelle situation traduit le produit booléen abcd ? b) Exprimer à l’aide d’une fonction booléenne les conditions caractérisant l’attribution de la prime. 2) Parmi les personnes gagnant moins de 1500 e par mois : a) Monsieur H a plus de 10 ans d’ancienneté. Peut-il obtenir la prime ? b) Même question pour Madame F qui a plus de 40 ans et moins de 10 ans d’ancienneté. c) Quelles sont les catégories d’employés qui auront la prime ? Exercice 8 La société Jurabois exploite des coupes constituées exclusivement de feuillus et de résineux. Elle désire simpliﬁer le règlement que ses salariés doivent appliquer pour la coupe du bois. Actuellement le règlement dit qu’un arbre est à abattre dans les quatre cas suivants : • si c’est un résineux au tronc droit mesurant plus de 20 m de hauteur ; • si c’est un feuillu de 50 ans ou plus ; • s’il a moins de 50 ans et mesure plus de 20 m de hauteur ; • s’il est tordu. Pour un arbre quelconque, on déﬁnit les variables booléennes suivantes par : a = 1 si l’arbre est un résineux ; b = 1 si l’arbre a moins de 50 ans ; c = 1 si l’arbre mesure plus de 20 m de hauteur ; d = 1 si l’arbre est tordu. 1) Écrire la fonction booléenne f(a, b, c, d), qui traduit le règlement actuel d’abattage d’un arbre. Grâce à une bonne gestion des forêts que la société exploite, il n’y a maintenant plus d’arbres tordus. 2) Montrer que le nouveau règlement d’abattage se traduit par la fonction g(a, b, c) = a.c + a.b + b.c. 3) Simpliﬁer au maximum cette fonction. 4) Écrire la nouvelle régie d’abattage d’un arbre sous la forme la plus simple possible. Exercice 9 Un règlement administratif concerne les trois catégories d’individus suivantes : • les hommes de moins de 50 ans ; • les non-salariés ayant 50 ou plus de 50 ans ; • les femmes qui sont soit salariées, soit non salariées et qui ont moins de 50 ans. On déﬁnit quatre variables booléennes h, a, s, r. Ainsi x désignant un individu quelconque, h = 1 si x est un homme ; a = 1 si x est âgé de 50 ou plus de 50 ans ; s = 1 si x est salarié ; r = 1 si x est concerné par le règlement. 1) Quels sont les individus x pour lesquels on a h.a = 1 ? 2) Montrer que la catégorie de personnes concernées par ce règlement est donnée par la fonction booléenne r = h.a + s.a + h.(s + s.a). 3) Montrer que r peut se uploads/S4/ algebre-de-boole-exercice-corrige.pdf