Algèbre de Boole

Définitions

L'algèbre de boole que l'on doit au mathématicien Georges Boole est un ensemble de deux valeurs V (Vrai ⊤) et F (Faux ⊥) muni des opérations de négation représentée par le symbole ¬, de disjonction représentée par le symbole ∨ et de conjonction représentée par le symbole ∧.

En électronique numérique la valeur VRAI est représentée par le chiffre 1 et la valeur fausse par le chiffre 0. En logique positive, qui est la plus utilisée, la valeur 1 est représentée par un potentiel supérieur (+Vcc) à celui de la valeur 0 (masse). En logique négative, la valeur 1 correspond à un potentiel inférieur à celui de la valeur 0.

On définit une variable booléenne, représentée par une lettre de l'alphabet minuscule (a,b,...), un symbole qui peut prendre une des deux valeurs Vrai (1) ou Faux (0).

L'opération de négation

Elle est définie par l'opérateur ¬ suivi du nom de la variable (exemple : ¬a) ou bien, en électronique numérique, le nom de la variable surmonté d'une barre (exemple : a̅) et nommé opérateur NON (NOT en Anglais).

Expression

• S=¬a
• S=a̅

Symbole électronique

Table de vérité

a	S
0	1
1	0

L'opération de disjonction

Le résultat de l'opération est VRAI si et seulement si au moins une des opérandes est VRAI. Elle est définie par l'opérateur ∨ ou encore par l'opérateur OU (+) en électronique numérique (OR en Anglais).

Expression

• S=a ∨ b
• S=a + b

Symbole électronique

Table de vérité

a	b	S
0	0	0
0	1	1
1	0	1
1	1	1

L'opération de conjonction

Le résultat de l'opération est VRAI si et seulement si les deux opérandes sont VRAI. Elle est définie par l'opérateur ∧ ou encore par l'opérateur ET (.) en électronique numérique (AND en Anglais).

Expression

• S=a ∧ b
• S=a . b=ab (le point peut ne pas être précisé)

Symbole électronique

Table de vérité

a	b	S
0	0	0
0	1	0
1	0	0
1	1	1

Remarque : dans l'écriture des expressions booléennes l'opération de conjonction est prioitaire sur l'opération de disjonction.

Les fonctions ou opérations composées

La fonction OU-NON

Appelée également NON-OU (NOR en Anglais), c'est un opérateur OU suivi d'un opérateur NON.

Le résultat est FAUX si et seulement si au moins une des opérandes est VRAI.

Expression

• S=a ⊽ b
• S=a + b=a̅ . b̅

Symbole électronique

Table de vérité

a	b	S
0	0	1
0	1	0
1	0	0
1	1	0

La fonction ET-NON

Appelée également NON-ET (NAND en Anglais), c'est un opérateur ET suivi d'un opérateur NON.

Le résultat est FAUX si et seulement si les deux opérandes sont VRAI.

Expression

• S=a ⊼ b
• S=a . b=a̅ + b̅

Symbole électronique

Table de vérité

a	b	S
0	0	1
0	1	1
1	0	1
1	1	0

La fonction OU Exclusif

La fonction OU exclusif (XOR en Anglais) est représentée par le symbole ⊕.

On la définie également comme disjonction exclusive.

Le résultat est VRAI si et seulement si une seule des deux opérandes est VRAI.

Expression

• S=(¬a ∧b) ∨ (a ∧ ¬b)
• S=a ⊕ b=a̅ . b + a . b̅

Symbole électronique

Table de vérité

a	b	S
0	0	0
0	1	1
1	0	1
1	1	0

La fonction OU Exclusif-NON

La fonction OU exclusif-NON ou NON-OU exclusif (NXOR en Anglais) est représentée par le symbole ⊙. C'est la fonction OU exclusif suivi de l'opérateur NON.

Le résultat est VRAI si et seulement si les deux opérandes ont la même valeur.

Expression

• S=(¬a ∧ ¬b) ∨ (a ∧ b)
• S=a ⊕ b=a ⊙ b=a̅ . b̅ + a . b

Symbole électronique

Table de vérité

a	b	S
0	0	1
0	1	0
1	0	0
1	1	1

Propriétés

La dualité est le fait que dans une égalité on peut permuter les opérateurs OU et ET, l'égalité reste inchangée, exemple :
a.(b + c) = a.b + a.c ⇔ a + b.c = (a + b).(a + c)

Théorème de De Morgan

La loi de De Morgan est définie par les égalités :
$\overline{a_1.a_2.a_3.\; ...\; .a_n}=\overline{a_1}+\overline{a_2}+\overline{a_3}+\mathrm{...}+\overline{a_n}$
$\overline{a_1+a_2+a_3+\; ...\; +a_n}=\overline{a_1}.\overline{a_2}+\overline{a_3}.\mathrm{...}.\overline{a_n}$

Expressions de simplifications

• a + a.b = a + b
• a.(a + b) = a
• a + a̅.b = a
• a.(a̅ + b) = a.b

On peut utiliser ces expresssions ainsi que les propriétés pour simplifier une expression booléenne, comme par exemple :
S = a̅b + ab̅ + ab = a̅b + a(b + b̅) = a + a̅b = a + b

Jouons avec les fonctions logiques

Modélisation et simplification

Présentation

La fonction numérique qui caractérise la sortie d'un système est représentée par la table de vérité ou par son expression booléenne qui est souvent de la forme d'une disjonction de conjonctions des variables d'entrée. Par abus de langage, on parle de somme de produit ou chaque produit apparaît une seule fois, on dit que c'est une somme de minterms.

En affectant un poids binaire aux variables de façon à convertir les valeurs binaires des entrées en valeurs décimales, on peut définir cette fonction en énumérant la suite des valeurs décimales qui donne un résultat à 1.

L'expression déduite de la table de vérité peut souvent être simplifiée pour donner une expression encore plus réduite. La simplifcation booléenne peut être algébrique en utulisant les expressions de simplifications et propriétés, ou graphique en utilisant un tableau de Karnaugh. Mais il est également possible d'utiliser la méthode de Quine-Mc Cluskey suivi de la méthode de Petrick.

Simplification par tableau de Karnaugh

Un tableau de Karnaugh est un tableau à deux dimensions où les variables d'entrées sont réparties sur les lignes et les colonnes. Les valeurs binaires de ces variables utilisent le code binaire réfléchi ou binaire réfléchi ou code Gray. Ce qui fait que lorsque l'on se déplace suivant les directions des lignes ou des colonnes, une seule variable change d'état. Pour simplifier, on effectue des groupement de cellules contingües qui contiennent des 1. Grouper des cellules revient à simplifier en utilisant la propriété : a̅ + a = 1. Utiliser plusieurs fois la même cellule revient à ajouter plusieurs fois le même terme.

Pour grouper des cellules afin de simplifier, il faut respecter quelques règles :

• Le nombre de cellules par groupement est une puissance de 2
• Lorsque l'on se déplace à l'intérieur d'un groupement, une seule variable doit changer d'état
• Les cellules extrêmes du tableau sont considérées comme contigues.
• Les variables qui ne changent pas d'état sont reliées par l'opérateur ET pour donner un terme
• Les termes obtenus avec les groupements sont reliés par l'opérateur OU.

Premier exemple

Table de vérité

a	b	c	S
0	0	0	1
0	0	1	0
0	1	0	0
0	1	1	0
1	0	0	1
1	0	1	0
1	1	0	1
1	1	1	1

On peut ecrire cette fonction sous la forme S=f(0,4,6,7).

Tableau de karnaugh

Les variables qui ne changent pas d'état dans le groupement rouge sont b et c qui valent 0 pour ce groupement, la valeur du groupement est donc b̅c̅.
Les variables qui ne changent pas d'état dans le groupement bleu sont a et b qui valent 1 pour ce groupement, la valeur du groupement est donc ab.
La solution finale est donc : S=b̅c̅ + ab

• A partir de la table de vérité ou de la fonction, on obtient l'expression booléenne :
  S=a̅b̅c̅ + ab̅c̅ + abc̅ + abc
• On factorise pour faire apparaître les propriétés :
  S=(a+a̅)b̅c̅ + ab(c̅ + c)
• En utilisant la propriété a+a̅=1, on obtient
  S=b̅c̅ + ab

Deuxième exemple

Table de vérité

a	b	c	S
0	0	0	0
0	0	1	0
0	1	0	0
0	1	1	1
1	0	0	0
1	0	1	1
1	1	0	1
1	1	1	1

On peut ecrire cette fonction sous la forme S=f(3,5,6,7).

Tableau de karnaugh

Les variables qui ne changent pas d'état dans le groupement rouge sont b et c qui valent 1 pour ce groupement, la valeur du groupement est donc bc.
Les variables qui ne changent pas d'état dans le groupement bleu sont a et b qui valent 1 pour ce groupement, la valeur du groupement est donc ab.
Les variables qui ne changent pas d'état dans le groupement vert sont a et c qui valent 1 pour ce groupement, la valeur du groupement est donc ac.
La solution finale est donc : S=bc + ab + ac

• A partir de la table de vérité ou de la fonction, on obtient l'expression booléenne :
  S=a̅bc + ab̅c + abc̅ + abc
• On ajoute le terme abc deux fois pour factoriser ensuite
  S=a̅bc + abc + ab̅c + abc + abc̅ + abc
• On factorise pour faire apparaître les propriétés :
  S=(a+a̅)bc + a(b + b̅)c + ab(c̅ + c)
• En utilisant la propriété a+a̅=1, on obtient
  S=bc + ac + ab

Troisième exemple

Table de vérité

a	b	c	d	S
0	0	0	0	1
0	0	0	1	0
0	0	1	0	1
0	0	1	1	0
0	1	0	0	0
0	1	0	1	0
0	1	1	0	0
0	1	1	1	0
1	0	0	0	1
1	0	0	1	0
1	0	1	0	1
1	0	1	1	0
1	1	0	0	1
1	1	0	1	1
1	1	1	0	1
1	1	1	1	1

On peut ecrire cette fonction sous la forme S=f(0,2,8,10,12,13,14,15).

Tableau de karnaugh

Les variables qui ne changent pas d'état dans le groupement rouge sont a et b qui valent 1 pour ce groupement, la valeur du groupement est donc ab.
Les variables qui ne changent pas d'état dans le groupement bleu sont b et d qui valent 0 pour ce groupement, la valeur du groupement est donc b̅d̅.
La solution finale est donc : S=ab + b̅d̅

• A partir de la table de vérité ou de la fonction, on obtient l'expression booléenne :
  S=a̅b̅c̅d̅ + a̅b̅cd̅ + ab̅c̅d̅ + ab̅cd̅ + abc̅d̅ + abc̅d + abcd̅ + abcd
• On factorise pour faire apparaître les propriétés :
  S=(a̅c̅ + a̅c + ac̅ + ac )b̅d̅ + ab(c̅d̅ + c̅d + cd̅ + cd)
• On factorise pour faire apparaître les propriétés :
  S=(a̅ + a)(c̅ + c)b̅d̅ + ab(c̅ + c)(d̅ + d)
• En utilisant la propriété a+a̅=1, on obtient
  S=ab + b̅d̅

Quatrième exemple

Table de vérité

n	a	b	c	d	A	B	C	D	N
0	0	0	0	0	0	0	0	0	0
1	0	0	0	1	0	0	0	1	1
2	0	0	1	0	0	0	1	1	3
3	0	0	1	1	0	0	1	0	2
4	0	1	0	0	0	1	1	0	6
5	0	1	0	1	0	1	1	1	7
6	0	1	1	0	0	1	0	1	5
7	0	1	1	1	0	1	0	0	4
8	1	0	0	0	1	1	0	0	12
9	1	0	0	1	1	1	0	1	13
10	1	0	1	0	1	1	1	1	15
11	1	0	1	1	1	1	1	0	14
12	1	1	0	0	1	0	1	0	10
13	1	1	0	1	1	0	1	1	11
14	1	1	1	0	1	0	0	1	9
15	1	1	1	1	1	0	0	0	8

Tableau de Karnaugh

Sortie A Sortie précédente Sortie suivante

Solution :

A=a

Eléments de simplification :

A=	ab̅c̅d̅ + ab̅c̅d + ab̅cd̅ + ab̅cd + abc̅d̅ + abc̅d + abcd̅ + abcd
A=	a(b̅+b)(c̅+c)(d̅+d)
A=	a

Solution :

B=a̅b + ab̅

Eléments de simplification :

B=	a̅bc̅d̅ + a̅bc̅d + a̅bcd̅ + a̅bcd + ab̅c̅d̅ + ab̅c̅d + ab̅cd̅ + ab̅cd
B=	a̅b(c̅+c)(d̅+d) + ab̅(c̅+c)(d̅+d)
B=	a̅b + ab̅

Solution :

C=b̅c + bc̅

Eléments de simplification :

C=	a̅b̅cd̅ + a̅b̅cd + a̅bc̅d̅ + a̅bc̅d + ab̅cd̅ + ab̅cd + abc̅d̅ + abc̅d
C=	(a̅+a)b̅c(d̅+d) + (a̅+a)bc̅(d̅+d)
C=	b̅c + bc̅

Solution :

D=c̅d + cd̅

Eléments de simplification :

D=	a̅b̅c̅d + a̅b̅cd̅ + a̅bc̅d + a̅bcd̅ + ab̅c̅d + ab̅cd̅ + abc̅d + abcd̅
D=	(a̅+a)(b̅+b)c̅d + (a̅+a)(b̅+b)cd̅
D=	c̅d + cd̅

La relation qui relie N à n peut s'écrire :

$N=\frac{n\oplus 2n}{2}=\frac{n}{2}\oplus n$

Jouons avec les simplifications

Choisir le nombre de variables auto 3 4 puis demander une une fonction