Algébre de Boole

$$\newcommand{\fonction}[5]{\begin{array}{ccccc} #1: & #2 & \longrightarrow & #3 \\ & #4 & \longmapsto & #5 \end{array}}$$

Définition.

DéfinitionUn Ensemble de Boole est un ensemble à deux élèments {Vrai,Faux} (aussi noté {1;0} ou {True,False}).
Remarque

L'ensemble de Boole a été inventée par George Boole (1815-1864) dans la cadre de la logique en mathématiques. Comme de nombreuses autres branches des mathématiques, l'algèbre de Boole à une grande importance en informatique.

Un conseil : si vous voulez faire de l'informatique à haut niveau vous devez faire des mathématiques !

Remarque

Selon les langages il existe un type pour des booléens (type Bool), en python True False existe par exemple mais pas en C où il faut utiliser en entier ou un char pour stocker un bool.

On peut se dire qu'un bool tient sur un bit mais on ne peut pas gérer un unique bit dans un ordinateur, la taille minimale utilisable est un byte (presque la même écriture que bit mais ce n'est pas la même chose) en général un byte est égal à un octet. En C attribuer un type pour un booléen entraîne une perte en mémoire (de 7 bits) et à une certaine époque cette perte n'était pas acceptable.

Les bons programmeurs peuvent réunir 8 bits dans un octet et donc ne pas perdre de place

En python un bool prend 28 bytes en mémoire comme un petit entier (pour le voir il faut utiliser import sys puis sis.getsizeof( ) ), le langage python n'est pas fait pour économiser de la mémoire !

Fonction booléenne

DéfinitionUne fonction booléenne est fonction de {Vrai,Faux}n dans {Vrai,Faux}.
Exemple

$$\fonction{non}{\{VRAI,FAUX\}}{\{VRAI,FAUX\}}{x}{\left \{\begin{array}{rcl} VRAI~~si~x = FAUX \\ FAUX~~si~x = VRAI \end{array} \right.}$$

La table de valeurs (appelé simplement table) associée est la suivante :
xnon(x)
01
10
Exemple

$$\fonction{et}{\{VRAI,FAUX\}²}{\{VRAI,FAUX\}}{x*y}{\left \{\begin{array}{rcl} VRAI~~si~x = y = VRAI \\ FAUX~~sinon \end{array} \right.}$$

La table de valeurs (appelé simplement table) associée est la suivante :
xyet(x,y)
000
010
100
111

A la place de et(x,y) on a l'habitude de noter x et y.

Exemple

$$\fonction{ou}{\{VRAI,FAUX\}²}{\{VRAI,FAUX\}}{x*y}{\left \{\begin{array}{rcl} FAUX~~si~x = y = FAUX \\ VRAI~~sinon \end{array} \right.}$$

La table associée est :
xyot(x,y)
000
011
101
111

A la place de ou(x,y) on a l'habitude de noter x ou y.

Proposition On peut exprimer toutes les fonctions booléennes uniquement à l'aide de et, ou et non.
Remarque

En exercice, nous allons voir qu'avec deux et même avec une unique fonction nous sommes capable d'écrire toutes les fonctions bolléennes !

Exemple

Le programme suivant permet de voir tous les cas pour n=3 mais il ne donne pas le résultat le plus simple !

xyzf(x,y,z)
000
001
010
011
100
101
110
111
x ou non(x)
Q.C.M.

a= VRAI et non(FAUX) et b=non(VRAI ou FAUX) alors :





Q.C.M.

a= non(VRAI) ou FAUX et b= non(non(VRAI)) alors :





Q.C.M.

La table de f(x,y) = (x ou y) et y est





Q.C.M.

La table suivante coorrespond à quelle fonction ?

xyzf(x,y,z)
0000
0010
0100
0111
1000
1011
1100
1111




Exercices.

  1. La fonction ou exclusif (xor en anglais) est définie par la table suivante :

    xyx xor y
    000
    011
    101
    110
    1. Exprimer en français courant le sens de la fonction xor.
    2. Exprimer xor à l'aide de non et, ou.

  2. On considére la fonction bolléennes unite(x,y,z) qui a trois variables x, y et z exprimées par 0 ou 1 associe le chiffre des unités de la somme en binaire de x de y et de z. Par exemple unite(1,0,1) donne 0 car 1 + 0 + 1 = 210 = 102. Ici 1 est le chiffre des "deuzaines" 0 celui des unités.

    1. Compléter la table de vérité (on peut cliquer sur les cellules de la derniére colonne pour passer de 0 à 1) :
      xyzunite(x,y,z)
      0000
      0010
      0100
      0110
      1000
      1010
      1100
      1110
    2. Exprimer unite à l'aide de xor.

  3. On considére la fonction bolléennes deuzaine(x,y,z) qui a trois variables x, y et z exprimées par 0 ou 1 associe le chiffre des deuzaines de la somme en binaire de x de y et de z. Par exemple deuzaine(1,0,1) donne 1 car 1 + 0 + 1 = 210 = 102. Ici 1 est le chiffre des "deuzaines" 0 celui des unités.

    1. Compléter la table de vérité (on peut cliquer sur les cellules de la derniére colonne pour passer de 0 à 1) :
      xyzdeuzaine(x,y,z)
      0000
      0010
      0100
      0110
      1000
      1010
      1100
      1110
    2. Exprimer deuzaine à l'aide de or et and.

  4. On souhaite exprimer toutes les fonctions booléennes avec seulement deux fonctions de bases :

    1. Exprimer la fonction et() à l'aide de la fonction non() et de la fonction ou().
    2. Reformuler la proposition du cours.

  5. L'exrcice introduit une fonction importante.

    1. Construire la table de f(x,y,z) = (non(x) et y) ou (x et z).
    2. La fonction s'appelle fonction multiplexeur (mux), compléter la phrase : "Si x est faux alors mux(x,y,z) est égal à ... sinon .........".

  6. La fonction de Sheffer est égale à S(x,y) = non(x et y).

    1. Construire sa table.
    2. Exprimer en francais la fonction de Sheffer.
    3. Construire la table de f(x)= S(x,x). f est égale à qu'elle autre fonction ?
    4. Construire la table de g(x,y) = S(S(x,x),S(y,y)). g est égale à quelle autre fonction ?
    5. Reformuler la fonction proposition de l'énnoncé.