ALGÈBRE BOOLÉENNE: HISTOIRE, THÉORÈMES ET POSTULATS, EXEMPLES - MATEMATIQUES - 2024

L' algèbre booléenne ou algèbre booléenne est la notation algébrique utilisée pour le traitement des variables binaires. Il couvre les études de toute variable qui n'a que 2 résultats possibles, complémentaires et mutuellement exclusifs. Par exemple, des variables dont la seule possibilité est vraie ou fausse, correcte ou incorrecte, activée ou désactivée sont à la base de l'étude de l'algèbre booléenne.

L'algèbre booléenne constitue la base de l'électronique numérique, ce qui la rend très présente aujourd'hui. Elle est régie par le concept de portes logiques, où les opérations connues en algèbre traditionnelle sont notablement affectées.

Source: pexels.com

L'histoire

L'algèbre booléenne a été introduite en 1854 par le mathématicien anglais George Boole (1815 - 1864), qui était un érudit autodidacte de l'époque. Son inquiétude découle d'un différend existant entre Augustus De Morgan et William Hamilton, au sujet des paramètres qui définissent ce système logique.

George Boole a soutenu que la définition des valeurs numériques 0 et 1 correspond, dans le domaine de la logique, respectivement à l'interprétation Nothing et Universe.

L'intention de George Boole était de définir, à travers les propriétés de l'algèbre, les expressions de logique propositionnelle nécessaires pour traiter les variables de type binaire.

En 1854, les sections les plus significatives de l'algèbre booléenne ont été publiées dans le livre "Une enquête sur les lois de la pensée sur lesquelles reposent les théories mathématiques de la logique et des probabilités."

Ce curieux titre sera résumé plus tard par «Les lois de la pensée» («Les lois de la pensée»). Le titre est devenu célèbre grâce à l'attention immédiate qu'il a reçue de la communauté mathématique de l'époque.

En 1948, Claude Shannon l'a appliqué à la conception de circuits de commutation électriques bistables. Cela a servi d'introduction à l'application de l'algèbre booléenne dans l'ensemble du schéma électronique-numérique.

Structure

Les valeurs élémentaires dans ce type d'algèbre sont 0 et 1, qui correspondent respectivement à FALSE et TRUE. Les opérations fondamentales de l'algèbre booléenne sont 3:

- Opération ET ou conjonction. Représenté par un point (.). Synonyme du produit.

- Opération OU ou disjonction. Représenté par une croix (+) Synonyme de la somme.

- PAS d'opération ou de négation. Représenté par le préfixe NOT (NOT A). Il est également appelé complément.

Si dans un ensemble A 2 les lois de composition interne sont définies, notées produit et somme (. +), On dit que le triple (A. +) est une algèbre booléenne si et seulement si ledit triple remplit la condition d'être un réseau distributif.

Pour définir un réseau distributif, les conditions de distribution doivent être remplies entre les opérations données:

. est distributif par rapport à la somme + a. (b + c) = (a. b) + (a. c)

+ est distributif par rapport au produit. a + (b. c) = (a + b). (a + c)

Les éléments qui composent l'ensemble A doivent être binaires, ayant ainsi des valeurs univers ou vides.

Applications

Son plus grand scénario d'application est la branche numérique, où elle sert à structurer les circuits qui composent les opérations logiques impliquées. L'art de la simplicité des circuits en faveur de l'optimisation des processus est le résultat de l'application correcte et de la pratique de l'algèbre booléenne.

De l'élaboration des panneaux électriques, en passant par la transmission de données, jusqu'à la programmation dans différents langages, on retrouve fréquemment l'algèbre booléenne dans toutes sortes d'applications numériques.

Les variables booléennes sont très courantes dans la structure de la programmation. Selon le langage de programmation utilisé, il y aura des opérations structurelles dans le code qui utilisent ces variables. Les conditions et arguments de chaque langage admettent des variables booléennes pour définir les processus.

Postulats

Il existe des théorèmes qui régissent les lois logiques structurelles de l'algèbre booléenne. De la même manière, il existe des postulats pour connaître les résultats possibles dans différentes combinaisons de variables binaires, en fonction de l'opération effectuée.

Somme (+)

L'opérateur OR dont l'élément logique est l'union (U) est défini pour les variables binaires comme suit:

0 + 0 = 0

0 + 1 = 1

1 + 0 = 1

1 + 1 = 1

Produit (.)

L'opérateur ET dont l'élément logique est l'intersection (∩) est défini pour les variables binaires comme suit:

0. 0 = 0

0. 1 = 0

une. 0 = 0

une. 1 = 1

En face (PAS)

L'opérateur NOT dont l'élément logique est le complément (X) 'est défini pour les variables binaires comme suit:

PAS 0 = 1

PAS 1 = 0

Beaucoup de postulats diffèrent de leurs homologues en algèbre conventionnelle. Cela est dû au domaine des variables. Par exemple, l'ajout d'éléments d'univers en algèbre booléenne (1 + 1) ne peut pas donner le résultat conventionnel de 2, car il n'appartient pas aux éléments de l'ensemble binaire.

Théorèmes

Règle du zéro et de l'unité

Toute opération simple qui implique un élément avec les variables binaires, est définie:

0 + A = A

1 + A = 1

0. A = 0

une. A = A

Pouvoirs égaux ou idempotence

Les opérations entre variables égales sont définies comme suit:

A + A = A

À. A = A

Complémentation

Toute opération entre une variable et son complément est définie comme:

A + PAS A = 1

À. PAS A = 0

Involution ou double négation

Toute double négation sera considérée comme la variable naturelle.

PAS (PAS A) = A

Commutatif

A + B = B + A; Commutativité de la somme.

À. B = B. À; Commutativité du produit.

Associatif

A + (B + C) = (A + B) + C = A + B + C; Associativité de la somme.

À. (B. C) = (A. B). C = A. B. C; Associativité des produits.

Distributif

A + (B. C) = (A + B). (A + C); Distributivité de la somme par rapport au produit.

À. (B + C) = (A. B) + (A + C); Distributivité du produit par rapport à la somme.

Lois d'absorption

Il existe de nombreuses lois d'absorption parmi plusieurs références, certaines des plus connues sont:

À. (A + B) = A

À. (PAS A + B) = A. B

PAS A (A + B) = PAS A. B

(A + B). (A + PAS B) = A

A + A. B = A

A + PAS A. B = A + B

PAS A + A. B = PAS A + B

À. B + A. PAS B = A

Théorème de Morgan

Ce sont des lois de transformation, qui gèrent des paires de variables qui interagissent entre les opérations définies de l'algèbre booléenne (+.).

PAS (A. B) = PAS A + PAS B

PAS (A + B) = PAS A. PAS B

A + B = PAS (PAS A + PAS B)

À. B = PAS (PAS A. PAS B)

Dualité

Tous les postulats et théorèmes possèdent la faculté de dualité. Cela implique qu'en échangeant les variables et les opérations, la proposition résultante est vérifiée. Autrement dit, lors de l'échange de 0 pour 1 et ET pour OU ou vice versa; une expression est créée qui sera également complètement valide.

Par exemple si le postulat est pris

une. 0 = 0

Et la dualité est appliquée

0 + 1 = 1

Un autre postulat parfaitement valable est obtenu.

Karnaugh: carte

La carte de Karnaugh est un diagramme utilisé en algèbre booléenne pour simplifier les fonctions logiques. Il consiste en un agencement bidimensionnel similaire aux tables de vérité de la logique propositionnelle. Les données des tables de vérité peuvent être directement capturées sur la carte de Karnaugh.

La carte de Karnaugh peut accueillir des processus jusqu'à 6 variables. Pour les fonctions avec un nombre de variables plus élevé, l'utilisation d'un logiciel est recommandée pour simplifier le processus.

Proposé en 1953 par Maurice Karnaugh, il s'est imposé comme un outil fixe dans le domaine de l'algèbre booléenne, car sa mise en œuvre synchronise le potentiel humain avec la nécessité de simplifier les expressions booléennes, aspect clé de la fluidité des processus numériques.

Exemples

L'algèbre booléenne est utilisée pour réduire les portes logiques dans un circuit, où la priorité est de ramener la complexité ou le niveau du circuit à son expression la plus basse possible. Cela est dû au retard de calcul que chaque porte suppose.

Dans l'exemple suivant, nous observerons la simplification d'une expression logique à son expression minimale, en utilisant les théorèmes et postulats de l'algèbre booléenne.

PAS (AB + A + B). PAS (A + PAS B)

NE PAS. PAS (A + PAS B); Factorisation A avec un facteur commun.

NE PAS. PAS (A + PAS B); Par le théorème A + 1 = 1.

PAS (A + B). PAS (A + PAS B); par le théorème A. 1 = A

(PAS A. PAS B).;

Par le théorème de Morgan NOT (A + B) = NOT A. PAS B

(PAS A. PAS B). (PAS A. B); Par théorème de double négation NOT (NOT A) = A

PAS A. PAS B. PAS A. B; Regroupement algébrique.

PAS A. PAS A. PAS B. B; Commutativité du produit A. B = B. À

PAS A. PAS B. B; Par le théorème A. A = A

PAS A. 0; Par le théorème A. PAS A = 0

0; Par le théorème A. 0 = 0

À. B. C + PAS A + A. PAS B. C

À. C. (B + NOT B) + NOT A; Affacturage (A. C) avec un facteur commun.

À. C. (1) + PAS A; Par théorème A + NOT A = 1

À. C + PAS A; Par règle du théorème zéro et de l'unité 1. A = A

PAS A + C; Selon la loi de Morgan A + NOT A. B = A + B

Pour cette solution, la loi de Morgan doit être étendue pour définir:

PAS (PAS A). C + PAS A = PAS A + C

Parce que NOT (NOT A) = A par involution.

Simplifiez la fonction logique

PAS A. PAS B. PAS C + PAS A. PAS B. C + PAS A. NOT C jusqu'à son expression minimale

PAS A. PAS B. (PAS C + C) + PAS A. PAS C; Factoring (NOT A. NOT B) avec facteur commun

PAS A. PAS B. (1) + PAS A. PAS C; Par théorème A + NOT A = 1

(PAS A. PAS B) + (PAS A. PAS C); Par règle du théorème zéro et de l'unité 1. A = A

PAS A (PAS B + PAS C); Factoriser NOT A avec un facteur commun

PAS A. PAS (B. C); Par les lois de Morgan NON (A. B) = PAS A + PAS B

PAS Par les lois de Morgan NON (A. B) = PAS A + PAS B

L'une des 4 options en gras représente une solution possible pour réduire le niveau du circuit

Simplifiez la fonction logique dans sa forme la plus simple

(A. PAS B. C + A. PAS B. B. D + PAS A. PAS B). C

(A. PAS B. C + A. 0. D + PAS A. PAS B). C; Par le théorème A. PAS A = 0

(A. PAS B. C + 0 + PAS A. PAS B). C; Par le théorème A. 0 = 0

(A. PAS B. C + PAS A. PAS B). C; Par théorème A + 0 = A

À. PAS B. C. C + PAS A. PAS B. C; Par distributivité du produit par rapport à la somme

À. PAS B. C + PAS A. PAS B. C; Par le théorème A. A = A

PAS B. C (A + PAS A) ; Factoring (PAS B.C) avec facteur commun

PAS B. C (1); Par théorème A + NOT A = 1

PAS B. C; Par règle du théorème zéro et de l'unité 1. A = A

Références

1. Algèbre booléenne et ses applications J. Eldon Whitesitt. Continental Publishing Company, 1980.
2. Mathématiques et ingénierie en informatique. Christopher J. Van Wyk. Institut d'informatique et de technologie. Bureau national des normes. Washington, DC 20234
3. Mathématiques pour l'informatique. Eric Lehman. Google Inc.

   F Thomson Leighton Département de mathématiques et Laboratoire d'informatique et d'intelligence artificielle, Massachussetts Institute of Technology; Technologies Akamai.

4. Éléments d'analyse abstraite. Mícheál O'Searcoid PhD. Département de mathématiques. Collège universitaire de Dublin, Beldfield, Dublind.
5. Introduction à la logique et à la méthodologie des sciences déductives. Alfred Tarski, New York Oxford. Presse de l'Université d'Oxford.