Ce cours parle:
- des opérations de base de l'algèbre de Boole en utilisant leurs différentes propriétés;
- du fonctionnement des portes logiques;
- de l'application de l'ensemble de théorèmes de l'algèbre de Boole;
- de la simplification des fonctions logiques par les méthodes algébriques et graphique;
- des exercices d'application
Pré-requis :
- Mathématique (Algèbre Linéaire).
- Électricité de base.

Algèbre de Boole — Résumé du cours

I. Introduction

L'algèbre de Boole opère sur des $\textit{variables logiques}$ ne prenant que deux valeurs :
$0$ (Faux) et $1$ (Vrai), à l'aide d'$\textit{opérateurs logiques}$ pour réaliser des
$\textit{fonctions logiques}$.

II. Opérations logiques

Opérations principales

$\textit{NON (NOT)}$ : $\overline{A}$ — inverse la variable. Table : $0 \to 1$, $1 \to 0$.

$\textit{ET (AND)}$: $A \cdot B = 1$ si et seulement si $A = 1$ ET $B = 1$.

$\textit{OU (OR)}$ : $A + B = 1$ si au moins une des entrées vaut $1$.

Opérations secondaires

$\textit{NAND}$ : $\overline{A \cdot B}$ — complément du ET.

$\textit{NOR}$ : $\overline{A + B}$ — complément du OU.

$\textit{XOR (OU exclusif)}$ : $A \oplus B = \bar{A}B + A\bar{B}$ — vaut $1$ si et seulement si
$A \neq B$.

III. Théorème de De Morgan

$$\overline{\prod_{i=1}^{n} A_i} = \sum_{i=1}^{n} \bar{A}_i
\qquad \text{et} $$
$$\overline{\sum_{i=1}^{n} A_i} = \prod_{i=1}^{n} \bar{A}_i.$$
Le complément d'un produit est la somme des compléments ; le complément d'une somme
est le produit des compléments. Ces théorèmes permettent de transformer ET en OU et
vice-versa.

IV. Propriétés des opérateurs AND et OR

Associativité : $A + (B+C) = (A+B)+C$, $\quad A(BC) = (AB)C$

Commutativité : $A+B = B+A$, $\quad AB = BA$

Distributivité : $A(B+C) = AB + AC$, $\quad A + BC = (A+B)(A+C)$

Élément neutre : $A + 0 = A$, $\quad A \cdot 1 = A$

Complémentarité : $A + \bar{A} = 1$, $\quad A \cdot \bar{A} = 0$

Involution : $\bar{\bar{A}} = A$

Invariance : $A + 1 = 1$, $\quad A \cdot 0 = 0$

Idempotence : $A + A = A$, $\quad A \cdot A = A$

Identités remarquables :
$$A + AB = A, \qquad A(A+B) = A, $$ $$(A+\bar{B})B = AB.$$

Propriétés NAND et NOR

NAND et NOR sont \textit{commutatifs} mais \textbf{pas associatifs} :
$\overline{(AB)C} \neq \overline{A(BC)}$.

V. Universalité de NAND et NOR

Toute opération logique peut être réalisée uniquement avec des portes NAND (ou
uniquement NOR) :

NOT par NAND : $\overline{A \cdot A} = \bar{A}$

AND par NAND : $\overline{\overline{AB}} = AB$

OR par NAND : $\overline{\bar{A} \cdot \bar{B}} = A + B$

VI. Fonctions logiques

Une fonction logique $F$ de $N$ variables ne prend que les valeurs $0$ ou $1$. Elle peut
être représentée de quatre manières :

$\textit{Expression algébrique}$ : somme/produit de variables logiques,
ex. $F = BCD + ACD + \bar{B}C\bar{D}$.

$\textit{Table de vérité}$ : tableau à $N+1$ colonnes et $2^N$ lignes listant toutes les
combinaisons des entrées avec la valeur de $F$.

$\textit{Tableau de Karnaugh}$ : représentation graphique en $2^N$ cases adjacentes telle
que deux cases voisines ne diffèrent que d'un seul bit (code Gray). Pour $N$ variables,
le tableau comporte $2^N$ cases.

$\textit{Logigramme}$ : schéma de portes logiques réalisant la fonction.

VII. Formes canoniques

1ère forme canonique (somme de min-termes) : somme de tous
les produits fondamentaux pour lesquels $F = 1$.
Ex. : $F(A,B,C) = AB\bar{C} + A\bar{B}C + ABC$

2ème forme canonique (produit de max-termes) : produit de
toutes les sommes fondamentales pour lesquelles $F = 0$.
Ex. : $F(A,B,C) =$ $ (A+B+C)(A+\bar{B}+C)(A+\bar{B}+\bar{C})$ $(A+B+\bar{C})$

Méthode de calcul : on développe chaque terme en multipliant par la somme des
variables manquantes et de leurs compléments, puis on simplifie.

VIII. Simplification des fonctions logiques

Simplification algébrique

On applique les propriétés de l'algèbre de Boole pour réduire le nombre de termes.
Cette méthode ne garantit pas d'aboutir à la forme minimale.

Exemple :
$F =$ $\bar{A}B\bar{C} + A\bar{B}C + AB\bar{C} + \bar{A}\bar{B}C +$ $\, \bar{A}BC + A\bar{B}\bar{C}
=$ $\, \bar{B}C + \bar{A}B + A\bar{C}$

Simplification par tableau de Karnaugh

Règles de regroupement :
On regroupe les cases adjacentes/symétriques contenant des $1$, en groupes de
$2^p$ cases ($p \geq 0$). Chaque groupe doit être aussi grand que possible. Tout $1$
doit appartenir à au moins un groupe. Une même case peut appartenir à plusieurs groupes.
Chaque groupement élimine $p$ variables.

Chaque groupement maximal est un $\textit{impliquant premier}$. Un impliquant premier
contenant au moins un $1$ ne figurant dans aucun autre impliquant premier est dit essentiel. La forme minimale s'obtient en retenant d'abord tous les impliquants
premiers essentiels, puis les autres nécessaires à couvrir tous les $1$.

Fonctions incomplètement définies

Certaines combinaisons sont impossibles : on note $\emptyset$ (ou $\phi$) la valeur
indifférente. Lors du regroupement, on peut inclure les $\emptyset$ pour agrandir les
groupes, mais on n'est pas obligé de les couvrir tous.

Exemple : $F(A,B,C,D) = \bar{C}D + C\bar{D}$

---

Pour plus de détails, consulter le PDF ci-joint.

---