tite fractale

Algèbre de Boole

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 :

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 :

1.5. Remarques

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 :

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.




Christophe Gragnic, avec l’aimable et habituelle contribution de J.Calard, le 30/12/2016, 08h46'40".






Page générée le 27/05/2021, 09h53'27" (source).
historique de la page
historique global