Dans ce cours, nous allons nous intéresser à un type simple, les booléens qui ne possèdent que deux valeurs et qui sont donc codés que sur un seul bit:

  • FAUX: dont la syntaxe peut varier suivant les langages de programmation; 0 False, false ...
  • VRAI: codé en 0 True, true ...

Ces types sont extrêmement utilisés en informatique notamment pour l’exécution conditionnelle de code en fonction des conditions. La fameuse instruction if ... else.

Comme il n'existe que deux valeurs booléennes, les opérations ne sont pas les mêmes qu'avec les nombres.

l’algèbre de Boole

George Boole, né le 2 novembre 1815 à Lincoln (Royaume-Uni) et mort le 8 décembre 1864 à Ballintemple (Irlande), est un logicien, mathématicien et philosophe britannique.

Il est le créateur de la logique moderne, fondée sur une structure algébrique et sémantique, que l’on appelle algèbre de Boole en son honneur. Article Wikipedia sur George Boole

Algèbre de Boole

Dans le monde noir et blanc des idéaux, il y a une vérité absolue. C'est-à-dire que tout est vrai ou faux . Dans ce contexte philosophique, considérons les exemples suivants:

"Un plus un égale deux." Vrai ou faux?

C'est (sans doute) vrai!

"1 + 1 = 2 ET 2 + 2 = 4." Vrai ou faux?

C'est aussi vrai.

Mais qu'en est-il:

"1 + 1 = 3 OU Sydney est en Australie" Vrai ou faux?

C'est vrai! Bien que 1 + 1 = 3 ne soit pas vrai, le OU dans l’instruction a indiqué que, si l’une ou l’autre partie de l’instruction est vraie, l’instruction entière l’est également.

Considérons maintenant un exemple plus déconcertant

"2 + 2 = 4 OU 1 + 1 = 3 ET 1 - 3 = -1" Vrai ou faux?

La vérité ou la fausseté des déclarations dépend de l’ordre dans lequel vous évaluez la déclaration. Si vous évaluez d'abord "2 + 2 = 4 OU 1 + 1 = 3", la déclaration est fausse et sinon vraie. Comme en algèbre ordinaire, il est nécessaire de définir certaines règles pour régir l’ordre d'évaluation, afin d'éviter toute ambiguïté.

Avant de décider dans quel ordre évaluer les énoncés, nous faisons ce que la plupart des mathématiciens aiment faire: remplacer les phrases par des symboles. Soit x la vérité ou la fausseté de l’énoncé 2 + 2 = 4. Soit y la vérité ou la fausseté de l’énoncé 1 + 1 = 3. Soit z la vérité ou la fausseté de l’énoncé 1 - 3 = -1.

Ensuite, l’exemple ci-dessus peut être récrit de manière plus compacte:

x ou y et zx\ \textrm{ou}\ y\ \textrm{et}\ z

Pour aller encore plus loin, les mathématiciens remplacent également OR par + et AND par ×, l’énoncé devient:

x+y×zx + y \times z

Maintenant que l’ordre de priorité est clair. Nous évaluons (y ET z) en premier, puis OU avec le x. La déclaration "x + yz" est vraie ou symboliquement x+yz=1x + yz = 1 où le nombre 1 représente "vrai".

Il y a une bonne raison pour laquelle nous avons choisi le signe multiplicatif pour l’opération AND. Comme nous le verrons plus tard, nous pouvons établir des parallèles entre l’opération AND et la multiplication.

Notations

L’algèbre booléenne a des opérations (ET et OU) analogues à l’algèbre ordinaire que nous connaissons et aimons, on rencontre parfois d'autres écritures également.

Opération

Écriture symbolique

Écriture alternative

ET

OU

x

+

\wedge

\vee

Tables de vérités des fonctions booléennes AND OR et NOT

Pour donner tous les résultats possibles d'une opération booléenne, on utilise fréquemment une table de vérité qui donne la sortie de la fonction booléenne en fonction de la ou les entrées.

Nous allons dans un premier temps nous intéresser aux tables de vérité des trois fonctions logiques fondamentales:

  • le NON LOGIQUE
  • le ET LOGIQUE
  • le OU LOGIQUE

Fonction NON LOGIQUE: NOT

La fonction logique NOT n'a qu'un argument, on la note symboliquement avec un ', une barre supérieure ou encore ¬.

Elle renvoie l’inverse de son argument FAUX si l'argument est VRAI, et vice-versa.

x

not(x)

0

0

1

0

Notations

Opération

Écriture symbolique

Écriture alternative

NOT(x)

x' ou x\overline{x}

¬x\neg x

Fonction ET LOGIQUE: AND

La fonction ET LOGIQUE a deux arguments, elle renvoie VRAI si les deux arguments ont pour valeur VRAI.

a

b

a et b

0

0

1

1

0

1

0

1

0

0

0

1

On voit bien grâce à cette table pourquoi on a utilisé le signe x pour désigner la fonction ET LOGIQUE.

  • 0 x 0 = 0
  • 0 x 1 = 0
  • 1 x 0 = 0
  • 1 x 1 = 1

Fonction OU LOGIQUE: OR

La fonction OU LOGIQUE a deux arguments, elle renvoie VRAI si au moins un des deux arguments a pour valeur VRAI.

a

b

a ou b

0

0

1

1

0

1

0

1

0

1

1

1

On voit grâce à cette table que le signe + utilisé pour désigner la fonction OU LOGIQUE fonctionne à peu près comme le + de notre algèbre traditionnelle.

  • 0 + 0 = 0
  • 0 + 1 = 1
  • 1 + 0 = 1
  • 1 + 1 = 1

Tables de vérité composées

Les trois tables de vérité présentées ci-dessus sont les plus élémentaires et servent de blocs de construction pour les plus complexes.

Supposons que nous voulions construire une table de vérité pour xy + z (c.-à-d. x ET y OU z).

Remarquez que cette table implique trois variables (x, y et z), nous nous attendons donc à ce qu'elle soit plus grande que les précédentes.

Pour construire une table de vérité, nous écrivons d’abord toutes les combinaisons possibles des trois variables:

x 	y 	z
---------
0 	0 	0
0 	0 	1
0 	1 	0
0 	1 	1
1 	0 	0
1 	0 	1
1 	1 	0
1 	1 	1

Nous complétons ensuite le tableau à la main en calculant la valeur que chaque combinaison produira en utilisant l'expression xy + z.

x 	y 	z  | xy+z
-----------|-----
0 	0 	0  |  0
0 	0 	1  |  1
0 	1 	0  |  0
0 	1 	1  |  1
1 	0 	0  |  0
1 	0 	1  |  1
1 	1 	0  |  1
1 	1 	1  |  1

La procédure que nous suivons pour produire des tables de vérité est maintenant claire. Voici quelques exemples supplémentaires de tables de vérité.

Construire des tables de vérité

Construire les tables de vérité suivantes:

  • x + y + z
  • (x + yz)'
  • (x + yz ') w

Voici pouvez consulter la page d'exercices pour vous entraîner.

Lois de l'algèbre booléenne

En algèbre ordinaire, deux expressions peuvent être équivalentes, par exemple:

xz+yz=(x+y)zxz + yz = (x + y) z

La même chose peut être dite de l'algèbre booléenne. Construisons des tables de vérité pour:

xz+yzxz + yz et (x+y)z(x + y) z

x 	y 	z  | xz + yz
--------------------
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  |   0 
1 	1 	1  |   1 
x 	y 	z  | (x + y) z
----------------------
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  |   0 
1 	1 	1  |   1 

En comparant les deux tableaux, vous aurez remarqué que les résultats(c'est-à-dire la dernière colonne) des deux tableaux sont identiques!

Equivalence d'expressions booléennes

Nous disons que deux expressions booléennes sont équivalentes si la sortie de leurs tables de vérité est la même.

Nous listons quelques expressions équivalentes.

Loi de commutativité

x+y=y+xx+y=y+x x×y=y×xx\times y = y \times x

Loi d'associativité

x+(y+z)=(x+y)+zx + (y + z) = (x + y) + z x×(y×c)=(x×y)×cx \times (y \times c) = (x \times y) \times c

Loi de distributivité

(x+y)×(y+z)=(x×y)+(x×z)+(y×y)+(y×z)(x + y) \times (y + z) = (x \times y) + (x \times z) + (y \times y) + (y \times z) x×(y+z)=(x×y)+(x×z)x \times (y + z) = (x \times y) + (x \times z)

Simplification

Grâce à ces lois, nous pouvons simplifier les expressions booléennes comme nous le faisons en algèbre ordinaire. Voici quelques exemples:

(x+y)(x+z)=x(x+z)+y(x+z)=xx+xz+xy+yz=x+xz+xy+yz=x(1+z+y)+yz=x+yz{\begin{matrix}(x+y)(x+z)&=&x(x+z)+y(x+z)\\&=&xx+xz+xy+yz\\&=&x+xz+xy+yz\\&=&x(1+z+y)+yz\\&=&x+yz\end{matrix}}

Autre exemple:

(x+y)(x+y)=x(x+y)+y(x+y)=xx+xy+yx+yy=0+xy+yx+0=xy+yx{\begin{matrix}(x+y)(x'+y')&=&x(x'+y')+y(x'+y')\\&=&xx'+xy'+yx'+yy'\\&=&0+xy'+yx'+0\\&=&xy'+yx'\end{matrix}}

Lois de De Morgan

La négation de la conjonction de deux propositions est équivalente à la disjonction des négations des deux propositions, ce qui signifie que « non(A et B) » est équivalent à « (non A) ou (non B) ». Article Wikipedia

(x+y)=xy(x + y) '= x'y' (xy)=x+y(xy) '= x' + y '

Demorganlaws.svg
Par TeknadTravail personnel, CC BY-SA 4.0, Lien

Nous pouvons appliquer ces deux lois pour simplifier les équations:

Exprimer x en forme de somme de produits:

x=(ab+c)=(ab)c=(a+b)c=ac+bc{\begin{matrix}x&=&(ab'+c)'\\&=&(ab')'c'\\&=&(a'+b)c'\\&=&a'c'+bc'\end{matrix}}

Autre exemple:

x=(a+b+c)=(a+b)c=abc{\begin{matrix}x&=&(a+b+c)'\\&=&(a+b)'c'\\&=&a'b'c'\\\end{matrix}}

Une autre chose intéressante que nous avons apprise est que nous pouvons inverser la table de vérité de toute expression en remplaçant chacune de ses variables par leurs contraires, c'est-à-dire remplacer x par x 'et y' par y etc. Ce résultat n'aurait pas dû être une surprise pour tous, essayez quelques exemples vous-même.

Sources