Histoire de l'algèbre booléenne, théorèmes et postulats, exemples

Il Algèbre de Boole o L'algèbre de Boole est la notation algébrique utilisée pour le traitement des variables binaires. Couvre les études de toute variable qui n'a que 2 résultats possibles, complémentaires et exclusifs. Par exemple, les variables dont la seule possibilité est vraie ou fausse, correcte ou incorrecte, sur ou hors.

L'algèbre booléenne constitue la base de l'électronique numérique, ce qui le rend assez présent dans la contemporanéité. Il est régi par le concept de portes logiques, où les opérations connues dans l'algèbre traditionnelle sont remarquablement affectées.

Source: Pexels.com

[TOC]

Histoire

L'algèbre booléenne a été introduite en 1854 par le mathématicien anglais George Boole (1815 - 1864), qui était un érudit auto-apparié de l'époque. Sa préoccupation est née d'un différend existant entre Augustus de Morgan et William Hamilton, sur les paramètres qui définissent ce système logique.

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

L'intention de George Boole était de définir, à travers les propriétés de l'algèbre, les expressions de la logique propositionnelle nécessaire pour faire face aux variables binaires.

En 1854, les sections les plus importantes de l'algèbre booléenne sont publiées dans le livre "Une enquête sur les lois de la pensée sur les théories mathématiques de la logique et de la probabilité est fondée ».

Ce titre curieux serait résumé plus tard comme "Les lois de la pensée "(" les lois de la pensée "). Le titre a sauté à la gloire en raison de l'attention immédiate qu'il avait de la communauté mathématique de l'époque.

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

Structure

Les valeurs élémentaires de 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 de 3:

- Et opération de conjonction. Représenté par un point ( . ). Synonyme du produit.

- Ou opération de disjonction. Représenté par une croix (+) .Synonyme de la somme.

- Aucune opération ou dénomination. Représenté par le préfixe pas (pas a). Il est également connu sous le nom de complément.

Si dans un ensemble, 2 lois de composition interne dénotent comme un produit et une somme est définie ( .  + ), on dit que la liste (un . + ) C'est une algèbre booléenne si et seulement si cette liste répond à l'état d'être un réticulum distributif.

Il peut vous servir: Nombres rationnels: propriétés, exemples et opérations

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

. est distributif par rapport à la somme +                   pour . (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 de Univers ou vide.

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 des circuits simplicité pour optimiser les processus, est le résultat de l'application et de la pratique correctes de l'algèbre booléenne.

De l'élaboration des tableaux électriques, à travers la transmission des données, jusqu'à atteindre la programmation dans différentes langues, nous pouvons fréquemment trouver l'algèbre de Boole dans tous les types d'applications numériques.

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

Postule

Il y a des théorèmes qui régissent les lois sur la logique structurelle de l'algèbre booléenne. De la même manière, ils sont publiés pour connaître les résultats possibles dans différentes combinaisons de variables binaires, selon l'opération réalisée.

Sum (+)

L'opérateur Ou 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

1 . 0 = 0

1 . 1 = 1

Opposé (pas)

L'opérateur Pas 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

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

Théorèmes

Règle et unité zéro

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

0 + a = a

1 + a = 1

0 . A = 0

1 . A = a

Pouvoirs égaux ou idemployance

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

Peut vous servir: Congruence: figures congruentes, critères, exemples, exercices

A + a = a

POUR . A = a

Complémentation

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

A + pas a = 1

POUR . Pas a = 0

Involution ou double déni

Tout le double déni sera considéré comme la variable naturelle.

Pas (pas a) = a

Commutatif

A + b = b + a; L'été de la somme.

POUR . B = b . POUR ; Commutivité des produits.

Associatif

A + (b + c) = (a + b) + c = a + b + c; Somme d'associativité.

POUR . (B . C) = (a . B) . C = a . B . C; Association de produits.

Distributif

A + (B . C) = (a + b) . (A + c); Distribuer la somme en ce qui concerne le produit.

POUR . (B + c) = (a . B) + (a + c); Distributivité des produits par rapport à la somme.

Lois d'absorption

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

POUR . (A + b) = a

POUR . (Pas a + b) = a . B

Pas un (a + b) = pas un . B

(A + B) . (A + pas b) = a

A + A . B = a

A + pas un . B = a + b

Pas un + a . B = pas a + b

POUR . 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 ( + . ).

NOTE . B) = pas a + pas b

Pas (a + b) = pas un . Pas b

A + b = pas (pas a + pas b)

POUR . B = pas (pas un . Pas b)

Dualité

Tous les postulats et les théorèmes ont le pouvoir de la dualité. Cela implique qu'en échangeant les variables et les opérations, la proposition résultante est vérifiée. C'est-à-dire lors de l'échange de 0 pour 1 et et et vice versa; Une expression est créée qui sera également complètement valable.

Par exemple, si vous prenez le postulat

1 . 0 = 0

Et la dualité est appliquée

0 + 1 = 1

Un autre postulat parfaitement valide est obtenu.

Carte de Karnaugh

La carte de Karnaugh est un diagramme utilisé dans l'algèbre booléenne pour simplifier les fonctions logiques. Il se compose d'un arrangement à deux dimensions similaire aux tableaux de vérité de la logique propositionnelle. Les données sur les tables réelles peuvent être directement incorporées sur la carte Karnaugh.

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

Proposé en 1953 par Maurice Karnaugh, il a été établi comme un outil fixe dans le domaine de Boole.

Exemples

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

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

Pas (ab + a + b) . Pas (a + pas b)

Pas [a (b + 1) + b] . Pas (a + pas b); En tenant compte du facteur commun.

Peut vous servir: calcul des approches à l'aide de différentiels

Pas [a (1) + b] . Pas (a + pas b); Par théorème a + 1 = 1.

Pas (a + b) . Pas (a + pas b); Par théorème a . 1 = A

( NOTE . Pas b) . [ NOTE . Pas (pas b)];

Par théorème de Morgan Not (a + b) = pas un . Pas b

( NOTE . Pas b) .  ( NOTE . B); Par théorème de double déni pas (pas a) = a

NOTE . Pas b . NOTE . B; Groupe algébrique.

NOTE . NOTE . Pas b . B; Commutivité des produits à . B = b . POUR

NOTE . Pas b . B; Par théorème a . A = a

NOTE . 0; Par théorème a . Pas a = 0

0; Par théorème a . 0 = 0

POUR . B . C + pas a + a . Pas b . C

POUR . C . (B + pas b) + pas a; Factorisé (un . C) avec un facteur commun.

POUR . C . (1) + pas a; Par théorème a + pas a = 1

POUR . C + pas a; Par le théorème de la règle zéro et l'unité 1 . A = a

Pas un + c ; Par la loi de Morgan à + pas un . 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 pas (pas a) = a par involution.

Simplifier la fonction logique

NOTE . Pas b . Pas c + pas un . Pas b . C + pas un . Pas c avant son expression minimale

NOTE . Pas b . (Pas c + c) + pas un . Pas c; Factorisé (pas un . Pas b) avec un facteur commun

NOTE . Pas b . (1) + pas un . Pas c; Par théorème a + pas a = 1

(NOTE . Pas b) + (pas un . Pas c);  Par le théorème de la règle zéro et l'unité 1 . A = a

Pas un (pas b + pas c); N'empotitude pas un facteur commun

NOTE . Pas (b . C); Par les lois de Morgan Not (un . B) = pas a + pas b

Pas [a + (b . C)] Par les lois de Morgan Not (un . 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 jusqu'à son expression minimale

( POUR . Pas b .  C + A . Pas b . B . D + pas un . Pas b) . C

( POUR . Pas b . C + A . 0 . D + pas un . Pas b) . C; Par théorème a . Pas a = 0

( POUR . Pas b . C + 0 + pas un . Pas b) . C; Par théorème a . 0 = 0

( POUR . Pas b . C + pas un . Pas b) . C; Par théorème a + 0 = a

POUR . Pas b . C . C + pas un . Pas b . C; Par distribution du produit par rapport à la somme

POUR . Pas b . C + pas un . Pas b . C; Par théorème a . A = a

Pas b . C (a + pas a) ; Factorisé (pas b . C) avec un facteur commun

Pas b . C (1); Par théorème a + pas a = 1

Pas b . C; Par le théorème de la règle zéro et l'unité 1 . A = a

Les références

1. L'algèbre booléenne et ses applications J. Eldon Whitesitt. Continental Reditorial Company, 1980.
2. Mathématiques et ingénierie en informatique. Christopher J. Van wyk. Institut des sciences informatiques et de la technologie. Bureau national des normes. Washington, D. C. 20234
3. Mathématiques pour l'informatique. Eric Lehman. Google Inc.
   F Thomson Leighton Department of Mathematics and the Computer Science and AI Laboratory, Massachussetts Institute of Technology; Akamai Technologies.
4. Éléments de l'analyse abstraite. Mícheál o'searcoïd doctorat. Département des mathématiques. University College Dublin, Beldfield, Dublind.
5.  Introduction à la logique et à la méthodologie des sciences déductives. Alfred Tarski, New York Oxford. Oxford University Press.