1. Construction

1.1. Introduction

Dans ce chapitre, une variable (mathématique) booléenne prendra soit la valeur 0 soit la valeur 1. On note $E=\left\{0;1\right\}$.

Les variables seront souvent notées en minuscule, et les nombres 0 et 1 pourront être utilisés dans les calculs.

Aucune approche théorique sur les algèbres ne sera faite ici. Pour plus de détail, consulter ces articles Wikipedia :

• Algèbre de Boole et logique, ce qui nous occupe ici,
• Structure des algèbres de Boole, un point de vue plus général, au niveau de la structure,
• Algèbres en général. Celle de Boole est en fait sur $\mathbb Z / 2 \mathbb Z$.

1.2. Opérations

Addition    Multiplication   Complémentation

 + | 0 1       . | 0 1           a | ā
---+-----     ---+-----         ---+---
 0 | 0 1       0 | 0 0           0 | 1
 1 | 1 1       1 | 0 1           1 | 0

1.3. Propriétés

Ce sont les mêmes que celles de la disjonction, de la conjonction et de la négation (voir le chapitre sur le calcul des propositions).

Elles confèrent à $E$ une structure d’algèbre de Boole.

1.4. Exemples de calculs

Sachant que $a=1$, $b=0$ et $c=1$, calculer :

• $a+b$
• $a.b$ (ou $ab$)
• $a \overline b$
• $\overline a \overline b$
• $\overline a b + \overline c$

1.5. Remarques

• $\overline a \overline b$ ne signifie pas la même chose que $\overline {ab}$.

2. Simplifications

Soit $F$ une fonction booléenne à plusieurs variables, comme par exemple celle définie par :

$$ F(a,b,c) = a + ab \overline c + \overline a \overline b c + abc + \overline a bc$$

Le but est de donner une expression plus simple de $F$.

2.1. Méthode analytique ou algébrique

On utilise les propriétés énoncées ci-dessus, mais c’est assez difficile.

$$\begin{aligned} F(a,b,c) &= a + ab \overline c + \overline a \overline b c + abc + \overline a bc \\\\ &= a \left(1 + b \overline c + bc \right) + \overline a \left( \overline b c + bc \right) \\\\ &= a + \overline a \left( c \left( \overline b + b \right) \right) \\\\ &= a + \overline a c \\\\ &= a + c \\\\ \end{aligned}$$

On retrouve ici des concepts comme :

• la factorisation
  • puisque . se développe par rapport à +,
  • mais aussi + par rapport à -,
• 1 est neutre pour . et absorbant pour + (idem pour $\mathcal V$ avec la conjonction et la disjonction),
• 0 est absorbant pour . et neutre pour + (idem pour $\mathcal F$…),
• $a . \overline a = 0$ et $a + \overline a = 1$,
• …

2.2. Méthode graphique

2.2.1. Code Gray

Le code Gray est un système binaire ou le passage d’un nombre au suivant se fait en ne changeant qu’un seul chiffre. C’est celui que nous allons utiliser dans les tableaux ci-dessous. Il ne faut donc pas respecter l’ordre utilisé dans les tables de vérité !

Exercice : Compter jusqu’à 16.

2.2.2. Tableaux de Karnaugh

Prononcer « Karno ».

Voir la feuille.