Algèbre booléen et programmation PHP

L'objectif est de vous présenter les bases de l'algèbre de Boole [1] et de lier ces notions à la programmation, spécialement avec PHP [2]

Algèbre de Boole : introduction

George Boole (nationalité anglaise) est un logicien, mathématicien et philosophe d’origine modeste et autodidacte. Dans les années 1844-1854, il a formulé les règle d’une algèbre binaire, n’acceptant que deux valeurs numériques, 0 et 1, avec les opérateurs logiques, OR, AND, et NOT correspondants. Le but de cette algèbre, qu’on appelle maintenant Algèbre de Boole était de proposer un formalisme qui pourrait servir de base au domaine de la logique mathématique. Malgré leur but théorique, les travaux de Boole ont trouvé de nombreuses applications très pratiques dans des domaines tels que la téléphonie. Et l’algèbre de Boole s’est surtout avérée de valeur inestimable en informatique, puisqu’elle propose des bases théoriques pour la conception de circuits à logique digitale dans les ordinateurs modernes.

L'algèbre de Boole [3], est une branche de la logique et de l’algèbre permettant de raisonner sur des variables propositionnelles dont les états sont binaires.

Par exemple, communément, si j’avance cette proposition : 2 + 2 = 4 et 2 + 2 = 5, je me retrouve devant une assertion dont la fausseté (la valeur 0) est validée socialement. En effet, deux plus deux vaut quatre et non cinq.

L’algèbre de Boole du nom de l’auteur permet de représenter les liens logiques binaires entre les données sous forme d’un formalisme mathématique.

Quel lien avec l’informatique ?

Ce formalisme est fort utile car il permet de formaliser l’organisation des influx électriques dans les circuits de l’ordinateur composés de transistors qui ne peuvent justement prendre que deux valeurs ou états : 0 (non passage de l’électricité dans le transistor) ou 1 (passage de l’électricité). Tout dans l’ordinateur se réduit à ses états binaires, dont peut toutefois émerger une complexité qui rejoint une logique compréhensible par l’homme : logique conditionnelle, calcul et arithmétique, traitement du langage verbal, etc. L’algèbre de Boole permet cette émergence.

Le formalisme booléen : permet à l’homme de communiquer avec la machine !

Essayons de raisonner sur l’implication d’une telle logique. Dans un système binaire dans lequel une donnée ne peut prendre que la valeur VRAI ou FAUX ou alors respectivement 1 et 0, il est logique que cela ne puisse se faire qu’en rapport à une deuxième donnée.

'Par référence à la théorie des ensembles on se retrouve devant un tel ensemble : B = {1, 0}'

Plusieurs combinaisons sont dès lors possibles entre la relation du premier élément et du second élément de cet ensemble :

Premier    Deuxième élément
élément    

1	   1
1	   0
0	   1
0	   0

Ces deux éléments peuvent ainsi (dans les mathématiques et même en programmation) prendre la forme de variables que l’on peut relier logiquement selon les trois types d’opérateurs suivants, qui permettant de relier ces deux données selon des cas de figure complémentaires.

Pour faire référence à la théorie des ensembles B est en quelque sorte un ensemble sur lequel on peut définir deux lois : ET et OU et une transformation appelée complémentaire, inversion ou contraire.

Premier type d’opération : la conjonction (la loi ET) par l’exemple

Par exemple, si l’on veut créer un programme en PHP qui définit une personne dans la classe sociale moyenne si elle un salaire annuel entre 12'000 et 24'000 EURO, cet opérateur sera d’une utilité certaine.

Dans ce programme, on utiliserait la relation logique suivante : a ET b : salaire > 12'000 EURO ET salaire < 24'000 EURO

Dans ce contexte opératif, cette relation est VRAIE si et seulement les deux données (a et b) sont VRAIES

En PHP cela donnerait :

< ?php

If (salaire > 12000 && salaire < 24000) {
Classe =  ″Classe moyenne″

}
?>

Cette loi est aussi notée

l’opérateur « . » :  a.b 
l’opérateur « ˄ » : a ˄ b
l’opérateur « & » ou « && » dans quelques langages de programmation (Perl, C, PHP...) : a & b
l’opérateur « AND » dans certains langages de programmation (Ada, Pascal, Python, PHP ...) : a AND b

Pour revenir à la logique, la table de vérité de la relation « ET » prend ainsi cette forme : Table de la loi ET

salaire > 12'000 EURO	salaire < 24'000 EURO	Valeur de la relation (classe moyenne ou pas)
1	                1                       1
1	                0                       0
1	                0                       0
0	                0                       0

Deuxième type d'opération logique : la disjonction

Dans ce contexte cette relation est fausse seulement et seulement SI une proposition a et une proposition b sont fausses, sinon elles sont vraies. Elle est donc complémentaire à la première loi.

Cette loi est aussi notée :

L’opérateur « + » : a + b
L’opérateur « ˅ » : a ˅  b
L’opérateur « | » ou « || » : a |  b
L’opérateur « OR » : a OR b

Prenons un exemple complémentaire au précédent :

a : quotient intellectuel < 40
b : quotient intellectuel > 150
L’idée est que si un sujet a un QI inférieur ou supérieur à 150 il a dès lors un score extrême, qu’il soit dans les scores très bas ou très haut.

En PHP cela donnerait :

< ?php

If (QI > 150 OR QI  < 40) {

$Quotient  =  ″Extrême″

}

?>

Voici la table de vérité de la loi « OU »

QI < 40  QI > 15    Valeur de la relation (QI extrême ou pas)

1         1         1
0         1         1
1         0         1
0         0         0

L’on peut dire que ce couple paraît conciliant puisque la soirée aura lieu dans le cas où la valeur de relation vaut 1.

Négation

Le contraire de "a" est VRAI si et seulement si a est FAUX.

L’opérateur est noté :

* non-a
* ā
* ¬(a) 
* ! 
* NOT

Le théorème De Morgan

Ce théorème établit deux vérité :

• ¬ (a + b) = ¬a . ¬b
• ¬ (a . b) = ¬a + ¬b

Cela montre bien les relations inextricables entre les trois lois : la loi de conjonction et complémentaire à la loi de conjonction.

De ces trois lois et du théorème de Morgan découlent toutes les autres lois

Le OU EXCLUSIF ou XOR, qui correspond à : (a + b) . ¬ (a.b)

Cela équivaut à dire que seulement un des deux doit être VRAI. Voici sa table de vérité :

A	B	A  XOR B

0	0	0
0	1	1
1	0	1
1	1	0

La loi d’équivalence qui est complémentaire à la première

Voici la loi : ¬ (a + b) + (a . b)

Cela équivaut à dire que les deux propositions doivent être VRAIES ou les deux propositions doivent être fausse:

A	B	A  <=> B

0	0	1
0	1	0
1	0	0
1	1	1

La loi d’implication qui équivaut à : ¬ a + b et est notée : a => b.

Elle indique que la proposition a est une condition étant suffisante pour la proposition b, tandis que la proposition b est une condition nécessaire pour la proposition a.

Par exemple si j’ai ces deux propositions :

A = «faire une omelette »

B = « casser des œufs»

Casser des œufs est une condition nécessaire pour faire une omelette, mais casser des œufs n’oblige pas la personne à faire des omelettes. Elle peut choisir par exemple de faire des œufs au plat.

Voici sa table de vérité :

A	B	A  => B
0	0	1
0	1	1
1	0	0
1	1	1

Propriétés

C’est ici que le terme « algèbre » prend toute sa dimension, car les relations logiques prennent quasiment les même propriétés que les calculs en arithmétique.

Prenons comme exemple ces trois propositions :

a = "J’aime aller à la piscine" b = "J’aimer aller au cinéma" c = "J’aime rencontrer mes amis"

L’Associativité

Comme avec les opérations habituelles, certaines parenthèses sont inutiles:

(a + b) + c = a + (b + c) = a + b + c (a.b).c = a.(b.c) = a.b.c

Imaginez vous les propositions précédents et remplacez les dans les énoncés ci-dessus et vous constaterez vous-même que les parenthèses sont inutiles.

Commutativité

Comme avec l’algèbre habituel l'ordre est sans importance :

• a + b = b + a
• a.b = b.a

Faites de même avec ces données.

Distributivité

Comme avec les opérations algébriques habituelles, il est possible de distribuer. Attention dans le cas de l’algèbre booléen le cas de figure est toutefois différent, puisque :

a + (b.c) = (a + b).(a + c)

Idempotence

a + a + a + [...] + a = a a.a.a.[...].a = a

En effet : « j’aime aller à la piscine » et « j’aime aller à la piscine » et « j’aime aller à la piscine » = « j’aime aller à la piscine » Élément neutre

a + 0 = a a.1 = a

Élément nul

0.a = 0 1 + a = 1

Absorption

a + a.b = a a.(a + b) = a

Complémentarité

• « J’aime aller à la piscine » = « je n’aime pas ne pas aller à la piscine  »

• « VRAI » SI J’aime aller à la piscine OU SI je n’aime pas aller à la piscine → c'est toujours le cas → vrai dans tous les cas → toujours VRAI, donc =1

• « VRAI » SI J’aime aller à la piscine ET J’aime aller à la piscine → impossible → faux dans tous les cas → toujours FAUX donc =0

Comme dans les opérations ordinaires la multiplication (ici la ET logique) est prioritaire par rapport à la somme (le OU logique) ; on peut, pour s'aider, placer des parenthèses dans les opérations.

Ces lois il est possible de les appliquer à plus de deux variables et de les intégrer dans la programmation

Prenons ces quatre propositions :

• A = je casse la coque des œufs
• B = je les bas
• C = je les fris dans une poêle
• D = je les mange

Etablissons la table de vérité de leur relation :

A (je casse la coque des œufs)	B (je les bas)	C (je fris les œufs dans une poêle)	D (je les mange)
          1	                       1	                        1	                 1	
          1	                       1	                        0	                 1	
          1	                       0	                        1	                 1	
          1	                       0	                        0	                 1	
          0	                       1	                        1	                 0	
          0	                       1	                        0	                 0	
          0	                       0	                        1	                 0	
          0	                       0	                        0	                 0

Pour pouvoir réduire et trouver la loi logique régit ces relations il s'agit de procéder ainsi :

Il s'agit premièrement de relever les relations qui ont un résultat vrai :

• a.b.c = 1
• a.b.¬c = 1
• a.¬b.c = 1
• a.¬b.¬c = 1

Puis de poser l'équation algébrique booléenne pour trouver la relation :

1. a.b.c + a.b. ¬c + a.¬b.c + a.¬b. ¬c =
2. a.(b.c + b. ¬c) + a (.¬b.c + .¬b. ¬c) =
3. a.(b. (c + ¬c) + a (¬b. (c + ¬c)) =
4. a.(b.1) + a (¬b. 1) =
5. a.(b.1 + ¬b. 1) =
6. a.(1.(b + ¬b) =
7. a.(1.1) = a

Comme vous voyez on a réduit la première proposition en une proposition bien plus courte (la septième qui équivaut à a).

Ainsi, nous pouvons appliquer cette équivalence dans le programme PHP suivant, pour simplifier les relations :

< ?php

$a = true;
$b = false;
$c = false;
$d = true

If ($a==true) {

$message  =  ″Bon appétit″

}

else {

$message = ″Si vous ne cassez pas les œufs, comment voulez-vous les manger ?″

}

?>

On voit donc ici l’utilité ne serait-ce que pour réduire des relations multiples, comme celles vues précédemment.

REFERENCE

Article Wikipédia sur Georges Boole : http://fr.wikipedia.org/wiki/George_Boole

--Pardiri 13 juin 2010 à 17:49 (CEST)