Expressions et fonctions booléennes

L'algèbre booléenne est une algèbre de la logique. Il traite des variables qui peuvent avoir deux valeurs discrètes, 0 (False) et 1 (True); et les opérations qui ont une signification logique. La première méthode de manipulation de la logique symbolique a été inventée par George Boole et est par la suite devenue connue sous le nom d'algèbre booléenne.

L'algèbre booléenne est maintenant devenue un outil indispensable en informatique pour sa large applicabilité dans la théorie de la commutation, la construction de circuits électroniques de base et la conception d'ordinateurs numériques.

Fonctions booléennes

A Boolean functionest un type spécial de fonction mathématique $ f: X ^ n \ rightarrow X $ de degré n, où $ X = \ lbrace {0, 1} \ rbrace $ est un domaine booléen et n est un entier non négatif. Il décrit la manière de dériver une sortie booléenne à partir d'entrées booléennes.

Example- Soit, $ F (A, B) = A'B '$. Ceci est une fonction de degré 2 de l'ensemble des paires ordonnées de variables booléennes à l'ensemble $ \ lbrace {0, 1} \ rbrace $ où $ F (0, 0) = 1, F (0, 1) = 0, F (1, 0) = 0 $ et $ F (1, 1) = 0 $

Expressions booléennes

A Boolean expressionproduit toujours une valeur booléenne. Une expression booléenne est composée d'une combinaison des constantes booléennes (Vrai ou Faux), des variables booléennes et des connecteurs logiques. Chaque expression booléenne représente une fonction booléenne.

Example - $ AB'C $ est une expression booléenne.

Identités booléennes

Loi du double complément

$ \ sim (\ sim A) = A $

Loi complémentaire

$ A + \ sim A = 1 $ (formulaire OR)

$ A. \ sim A = 0 $ (Forme AND)

Loi idempotente

$ A + A = A $ (formulaire OU)

$ A. A = A $ (forme ET)

Loi d'identité

$ A + 0 = A $ (formulaire OU)

$ A. 1 = A $ (formulaire ET)

Loi de dominance

$ A + 1 = 1 $ (formulaire OR)

$ A. 0 = 0 $ (formulaire ET)

Loi commutative

$ A + B = B + A $ (formulaire OU)

$ A. B = B. A $ (formulaire ET)

Loi associative

$ A + (B + C) = (A + B) + C $ (formulaire OR)

$ A. (B. C) = (A. B). C $ (formulaire ET)

Loi d'absorption

$ A. (A + B) = A $

$ A + (A. B) = A $

Loi de simplification

$ A. (\ sim A + B) = A. B $

$ A + (\ sim A. B) = A + B $

Loi distributive

$ A + (B. C) = (A + B). (A + C) $

$ A. (B + C) = (A. B) + (A. C) $

Loi de De-Morgan

$ \ sim (A. B) = \ sim A + \ sim B $

$ \ sim (A + B) = \ sim A. \ sim B $

Formes canoniques

Pour une expression booléenne, il existe deux types de formes canoniques -

• Formulaire de la somme des minterms (SOM)
• Le produit de la forme maxterms (POM)

Le formulaire Somme des minterms (SOM) ou Somme des produits (SOP)

Un minterme est un produit de toutes les variables prises sous leur forme directe ou complétée. Toute fonction booléenne peut être exprimée comme une somme de ses 1 minutes et l'inverse de la fonction peut être exprimée comme une somme de ses 0 minutes. Par conséquent,

F (liste des variables) = ∑ (liste des indices à 1 minute)

et

F '(liste des variables) = ∑ (liste des indices à 0 minute)

UNE	B	C	Terme	Minterm
0	0	0	x'y'z '	m 0
0	0	1	x'y'z	m 1
0	1	0	x'yz '	m 2
0	1	1	x'yz	m 3
1	0	0	xy'z '	m 4
1	0	1	xy'z	m 5
1	1	0	xyz '	m 6
1	1	1	xyz	m 7

Example

Soit, $ F (x, y, z) = x 'y' z '+ xy' z + xyz '+ xyz $

Ou, $ F (x, y, z) = m_0 + m_5 + m_6 + m_7 $

Par conséquent,

$ F (x, y, z) = \ somme (0, 5, 6, 7) $

Nous allons maintenant trouver le complément de $ F (x, y, z) $

$ F '(x, y, z) = x' yz + x 'y' z + x 'yz' + xy 'z' $

Ou, $ F '(x, y, z) = m_3 + m_1 + m_2 + m_4 $

Par conséquent,

$ F '(x, y, z) = \ somme (3, 1, 2, 4) = \ somme (1, 2, 3, 4) $

Formulaire Produit de Maxterms (POM) ou Produit de sommes (POS)

Un maxterm est l'addition de toutes les variables prises sous leur forme directe ou complétée. Toute fonction booléenne peut être exprimée comme un produit de ses 0-maxterms et l'inverse de la fonction peut être exprimée comme un produit de ses 1-maxterms. Par conséquent,

F (liste de variables) = $ \ pi $ (liste d'indices 0-maxterm).

et

F '(liste des variables) = $ \ pi $ (liste des indices 1-maxterm).

UNE	B	C	Terme	Maxterm
0	0	0	x + y + z	M 0
0	0	1	x + y + z '	M 1
0	1	0	x + y '+ z	M 2
0	1	1	x + y '+ z'	M 3
1	0	0	x '+ y + z	M 4
1	0	1	x '+ y + z'	M 5
1	1	0	x '+ y' + z	M 6
1	1	1	x '+ y' + z '	M 7

Exemple

Soit $ F (x, y, z) = (x + y + z). (x + y + z '). (x + y '+ z). (x '+ y + z) $

Ou, $ F (x, y, z) = M_0. M_1. M_2. M_4 $

Par conséquent,

$ F (x, y, z) = \ pi (0, 1, 2, 4) $

$ F '' (x, y, z) = (x + y '+ z'). (x '+ y + z'). (x '+ y' + z). (x '+ y' + z ') $

Ou, $ F (x, y, z) = M_3. M_5. M_6. M_7 $

Par conséquent,

$ F '(x, y, z) = \ pi (3, 5, 6, 7) $

Des portes logiques

Les fonctions booléennes sont implémentées à l'aide de portes logiques. Voici les portes logiques -

PAS de porte

Une porte NOT inverse une entrée de bit unique en un seul bit de sortie.

UNE	~ A
0	1
1	0

ET Porte

Une porte ET est une porte logique qui donne une sortie haute uniquement si toutes ses entrées sont hautes, sinon elle donne une sortie basse. Un point (.) Est utilisé pour afficher l'opération ET.

UNE	B	UN B
0	0	0
0	1	0
1	0	0
1	1	1

OU Porte

Une porte OU est une porte logique qui donne une sortie élevée si au moins une des entrées est haute. Un signe plus (+) est utilisé pour montrer l'opération OR.

UNE	B	A + B
0	0	0
0	1	1
1	0	1
1	1	1

Porte NAND

Une porte NAND est une porte logique qui donne une sortie basse uniquement si toutes ses entrées sont hautes, sinon elle donne une sortie élevée.

UNE	B	~ (AB)
0	0	1
0	1	1
1	0	1
1	1	0

Porte NOR

Une porte NOR est une porte logique qui donne une sortie élevée si les deux entrées sont basses, sinon elle donne une sortie faible.

UNE	B	~ (A + B)
0	0	1
0	1	0
1	0	0
1	1	0

Porte XOR (OU exclusif)

Une porte XOR est une porte logique qui donne une sortie élevée si les entrées sont différentes, sinon elle donne une sortie faible.

UNE	B	A⊕B
0	0	0
0	1	1
1	0	1
1	1	0

Porte X-NOR (NOR exclusif)

Une porte EX-NOR est une porte logique qui donne une sortie élevée si les entrées sont identiques, sinon elle donne une sortie faible.

UNE	B	UN X-NOR B
0	0	1
0	1	0
1	0	0
1	1	1