Circuits numériques - Algèbre booléenne

Boolean Algebraest une algèbre, qui traite des nombres binaires et des variables binaires. Par conséquent, il est également appelé algèbre binaire ou algèbre logique. Un mathématicien, nommé George Boole avait développé cette algèbre en 1854. Les variables utilisées dans cette algèbre sont également appelées variables booléennes.

La plage de tensions correspondant à la logique «High» est représentée par «1» et la plage de tensions correspondant à la logique «Low» est représentée par «0».

Postulats et lois fondamentales de l'algèbre booléenne

Dans cette section, discutons des postulats booléens et des lois de base qui sont utilisées en algèbre booléenne. Ceux-ci sont utiles pour minimiser les fonctions booléennes.

Postulats booléens

Considérez les nombres binaires 0 et 1, la variable booléenne (x) et son complément (x '). La variable booléenne ou son complément est connu sous le nom deliteral. Les quatre possibleslogical OR les opérations parmi ces littéraux et nombres binaires sont indiquées ci-dessous.

x + 0 = x

x + 1 = 1

x + x = x

x + x '= 1

De même, les quatre possibles logical AND les opérations parmi ces littéraux et nombres binaires sont indiquées ci-dessous.

x.1 = x

x.0 = 0

xx = x

x.x '= 0

Ce sont les postulats booléens simples. Nous pouvons vérifier ces postulats facilement, en remplaçant la variable booléenne par «0» ou «1».

Note- Le complément de complément de toute variable booléenne est égal à la variable elle-même. c'est-à-dire (x ')' = x.

Lois de base de l'algèbre booléenne

Voici les trois lois de base de l'algèbre booléenne.

  • Loi commutative
  • Droit associatif
  • Loi distributive

Loi commutative

Si une opération logique de deux variables booléennes donne le même résultat quel que soit l'ordre de ces deux variables, alors cette opération logique est dite Commutative. Les opérations OR logiques et ET logiques de deux variables booléennes x et y sont indiquées ci-dessous

x + y = y + x

xy = yx

Le symbole «+» indique une opération OU logique. De même, le symbole «.» indique une opération ET logique et sa représentation est facultative. La loi commutative obéit aux opérations OU logiques et ET logiques.

Loi associative

Si une opération logique de deux variables booléennes quelconques est effectuée en premier, puis que la même opération est effectuée avec la variable restante donne le même résultat, alors cette opération logique est dite Associative. Les opérations OR logiques et ET logiques de trois variables booléennes x, y et z sont indiquées ci-dessous.

x + (y + z) = (x + y) + z

x. (yz) = (xy) .z

La loi associative obéit aux opérations OU logiques et ET logiques.

Loi distributive

Si une opération logique peut être distribuée à tous les termes présents dans la fonction booléenne, alors cette opération logique est dite Distributive. La distribution des opérations OR logiques et ET logiques de trois variables booléennes x, y et z est indiquée ci-dessous.

x. (y + z) = xy + xz

x + (yz) = (x + y). (x + z)

La loi distributive obéit aux opérations OU logiques et ET logiques.

Ce sont les lois de base de l'algèbre booléenne. Nous pouvons vérifier ces lois facilement, en remplaçant les variables booléennes par «0» ou «1».

Théorèmes de l'algèbre booléenne

Les deux théorèmes suivants sont utilisés en algèbre booléenne.

  • Théorème de dualité
  • Théorème de DeMorgan

Théorème de la dualité

Ce théorème stipule que le dualde la fonction booléenne est obtenue en interchangeant l'opérateur logique ET avec l'opérateur logique OU et les zéros avec des uns. Pour chaque fonction booléenne, il y aura une fonction Dual correspondante.

Faisons en deux groupes les équations booléennes (relations) dont nous avons parlé dans la section des postulats booléens et des lois de base. Le tableau suivant présente ces deux groupes.

Groupe 1 Groupe2
x + 0 = x x.1 = x
x + 1 = 1 x.0 = 0
x + x = x xx = x
x + x '= 1 x.x '= 0
x + y = y + x xy = yx
x + (y + z) = (x + y) + z x. (yz) = (xy) .z
x. (y + z) = xy + xz x + (yz) = (x + y). (x + z)

Dans chaque ligne, il y a deux équations booléennes et elles sont doubles l'une par rapport à l'autre. Nous pouvons vérifier toutes ces équations booléennes de Group1 et Group2 en utilisant le théorème de dualité.

Théorème de DeMorgan

Ce théorème est utile pour trouver le complement of Boolean function. Il déclare que le complément du OU logique d'au moins deux variables booléennes est égal au ET logique de chaque variable complémentée.

Le théorème de DeMorgan avec 2 variables booléennes x et y peut être représenté comme

(x + y) '= x'.y'

Le dual de la fonction booléenne ci-dessus est

(xy) '= x' + y '

Par conséquent, le complément du ET logique de deux variables booléennes est égal au OU logique de chaque variable complémentée. De même, nous pouvons également appliquer le théorème de DeMorgan pour plus de 2 variables booléennes.

Simplification des fonctions booléennes

Jusqu'à présent, nous avons discuté des postulats, des lois de base et des théorèmes de l'algèbre booléenne. Maintenant, simplifions certaines fonctions booléennes.

Exemple 1

Laissez-nous simplify la fonction booléenne, f = p'qr + pq'r + pqr '+ pqr

Nous pouvons simplifier cette fonction de deux manières.

Method 1

Étant donné la fonction booléenne, f = p'qr + pq'r + pqr '+ pqr.

Step 1- En premier et deuxième termes, r est commun et en troisième et quatrième termes, pq est commun. Alors, prenez les termes courants en utilisantDistributive law.

⇒ f = (p'q + pq ') r + pq (r' + r)

Step 2- Les termes présents dans la première parenthèse peuvent être simplifiés en fonctionnement Ex-OR. Les termes présents dans la deuxième parenthèse peuvent être simplifiés en «1» en utilisantBoolean postulate

⇒ f = (p ⊕q) r + pq (1)

Step 3- Le premier terme ne peut pas être simplifié davantage. Mais, le deuxième terme peut être simplifié en pq en utilisantBoolean postulate.

⇒ f = (p ⊕q) r + pq

Par conséquent, la fonction booléenne simplifiée est f = (p⊕q)r + pq

Method 2

Étant donné la fonction booléenne, f = p'qr + pq'r + pqr '+ pqr.

Step 1 - Utilisez le Boolean postulate, x + x = x. Cela signifie que l'opération OU logique avec n'importe quelle variable booléenne «n» fois sera égale à la même variable. Ainsi, nous pouvons écrire le dernier terme pqr encore deux fois.

⇒ f = p'qr + pq'r + pqr '+ pqr + pqr + pqr

Step 2 - Utiliser Distributive lawpour 1 er et 4 ème termes, 2 ème et 5 ème termes, 3 ème et 6 ème termes.

⇒ f = qr (p '+ p) + pr (q' + q) + pq (r '+ r)

Step 3 - Utiliser Boolean postulate, x + x '= 1 pour simplifier les termes présents dans chaque parenthèse.

⇒ f = qr (1) + pr (1) + pq (1)

Step 4 - Utiliser Boolean postulate, x.1 = x pour simplifier les trois termes ci-dessus.

⇒ f = qr + pr + pq

⇒ f = pq + qr + pr

Par conséquent, la fonction booléenne simplifiée est f = pq + qr + pr.

Nous avons donc obtenu deux fonctions booléennes différentes après avoir simplifié la fonction booléenne donnée dans chaque méthode. Fonctionnellement, ces deux fonctions booléennes sont identiques. Ainsi, en fonction de l'exigence, nous pouvons choisir l'une de ces deux fonctions booléennes.

Exemple 2

Trouvons le complement de la fonction booléenne, f = p'q + pq '.

Le complément de la fonction booléenne est f '= (p'q + pq') '.

Step 1 - Utilisez le théorème de DeMorgan, (x + y) '= x'.y'.

⇒ f '= (p'q)'. (Pq ')'

Step 2 - Utiliser le théorème de DeMorgan, (xy) '= x' + y '

⇒ f '= {(p') '+ q'}. {P '+ (q') '}

Step3 - Utilisez le postulat booléen, (x ')' = x.

⇒ f '= {p + q'}. {P '+ q}

⇒ f '= pp' + pq + p'q '+ qq'

Step 4 - Utilisez le postulat booléen, xx '= 0.

⇒ f = 0 + pq + p'q '+ 0

⇒ f = pq + p'q '

Par conséquent, la complement de la fonction booléenne, p'q + pq 'est pq + p’q’.