Langage de programmation - Mathématiques appliquées

Algèbre de Boole

L'algèbre de Boole est un aspect des mathématiques centré sur la logique inventé par le mathématicien britannique George Boole et publié dans un ouvrage intitulé «An Investigation of the Laws of Thought : On Which Are Founded the Mathematical Theories of Logic and Probabilities» (ISBN: 978-1-108-00153-3) en 1854. Les idées dernières l'algèbre de Boole sont le niveau le plus bas d'un ordinateur et est étroitement lié aux circuits électronique. En mathématiques appliquées, l'algèbre de Boole propose des principes simples :

Se base sur deux états possibles : vrai ou faux. Ainsi, les variables n'ont que deux états possible : vrai ou faux !
Il existe trois fonctions ou opérateurs de base : ET, OU et NON. Tous les autres fonctions se basent sur ses 3 fonctions.
Plusieurs valeurs peuvent être combiné afin de fournir une valeur logique
L'algèbre peut s'appliquer à une variable binaire (0 et 1)
Permet d'établir un circuit logiques

Ainsi, grâce à l'algèbre de Boole, on peut introduire une forme de raisonnement au mathématique allant être éventuellement appliqué à un programme informatique. De plus, elle permettra de donner un sens précis aux énoncés mathématiques afin de déterminer si une argumentation est valide.

On appel «booléenne» les états possibles, soit vrai ou faux, que peut avoir la valeur ou un énoncé.

Remarques

Par convention, en informatique et dans les ordinateurs, il a été établi que la valeur FAUX = 0 et que la valeur VRAI = 1.
Les variables booléenne sont très importantes dans les algorithmes de programmation car elles permettront la prise de décisions de l'ordinateur lors de l'exécution d'un programme.

Introduction

L'algèbre de Boole est une branche des mathématiques qui permet de représenter, de manipuler et de simplifier des expressions ne possédant généralement que deux états possibles. Ces états sont habituellement notés :

0 et 1

ou :

FAUX et VRAI

Contrairement à l'algèbre classique, qui manipule des nombres pouvant prendre une grande variété de valeurs, l'algèbre de Boole travaille principalement avec des valeurs binaires. Elle constitue ainsi le fondement mathématique de la logique numérique, des circuits électroniques, des instructions conditionnelles, des filtres, des moteurs de recherche, des bases de données et d'une grande partie de la programmation informatique.

Dans un programme, les expressions booléennes servent notamment à déterminer si une instruction doit être exécutée, si une boucle doit continuer, si une valeur satisfait une condition ou si un utilisateur possède une autorisation particulière. Dans un circuit numérique, elles décrivent le comportement des portes logiques et permettent de construire des composants comme les additionneurs, les comparateurs, les multiplexeurs, les registres et les processeurs.

L'algèbre de Boole fournit des opérations, des lois et des méthodes de transformation permettant d'étudier ces expressions. Grâce à elle, une condition complexe peut être simplifiée, une table de vérité peut être convertie en expression logique et un circuit peut être réduit afin d'utiliser moins de composants.

Origine de l'algèbre de Boole

L'algèbre de Boole porte le nom du mathématicien britannique George Boole, qui développa au XIX^e siècle une méthode algébrique permettant de représenter les raisonnements logiques.

Son objectif initial consistait à traduire certaines propositions logiques sous la forme d'expressions mathématiques. Les affirmations pouvaient alors être combinées, transformées et vérifiées à l'aide de règles comparables à celles de l'algèbre ordinaire.

L'importance de ces travaux dépassa progressivement le domaine de la logique. Lorsque les circuits électriques et électroniques commencèrent à être utilisés pour traiter des informations binaires, les opérations booléennes fournirent un modèle mathématique particulièrement adapté à leur description.

Définition générale

Une algèbre de Boole est une structure mathématique composée :

d'un ensemble de valeurs ;
de deux opérations binaires principales ;
d'une opération de complément ;
de deux éléments particuliers représentant généralement le minimum et le maximum logiques.

Dans sa forme la plus simple, l'ensemble des valeurs est :

B = {0,1}

Les opérations principales sont :

ET
OU
NON

Les valeurs particulières sont :

et :

Valeurs booléennes

Une valeur booléenne représente l'un de deux états opposés.

Valeur numérique	Valeur logique	Signification courante
0	FAUX	Condition non satisfaite
1	VRAI	Condition satisfaite

Les notations numériques et logiques sont généralement interchangeables dans les explications théoriques.

Ainsi :

0 = FAUX

et :

1 = VRAI

Interprétation des valeurs

Les valeurs booléennes peuvent représenter de nombreuses situations.

Valeur 0	Valeur 1
Faux	Vrai
Désactivé	Activé
Fermé	Ouvert
Absent	Présent
Échec	Succès
Non autorisé	Autorisé
Aucun signal	Signal
Bit désactivé	Bit activé

La signification exacte dépend du contexte dans lequel la valeur est utilisée.

Domaine booléen

Le domaine booléen classique contient exactement deux valeurs :

B = {0,1}

Une variable appartenant à ce domaine peut donc être définie par :

x ∈ B

Cela signifie que :

x = 0

ou :

x = 1

Aucune autre valeur n'est admise dans le modèle booléen classique.

Variable booléenne

Une variable booléenne est une variable pouvant prendre uniquement les valeurs :

VRAI

ou :

FAUX

Par exemple :

UtilisateurConnecté

peut valoir :

VRAI

lorsque l'utilisateur est authentifié, ou :

FAUX

dans le cas contraire.

Exemple de variables booléennes

EstMajeur
CompteActif
MotDePasseValide
FichierExiste
ConnexionDisponible
ErreurDétectée

Chacune de ces variables décrit un état pouvant être affirmé ou nié.

Constantes booléennes

Les constantes booléennes sont les deux valeurs fondamentales :

FAUX

et :

VRAI

Elles sont parfois écrites en lettres minuscules :

false
true

ou sous forme numérique :

0
1

La notation dépend du langage de programmation et du contexte mathématique.

Proposition logique

Une proposition logique est un énoncé auquel on peut attribuer une valeur de vérité.

Par exemple :

10 est supérieur à 5

est une proposition vraie.

En revanche :

10 est inférieur à 5

est une proposition fausse.

Expressions qui ne sont pas des propositions

Une question ou une instruction ne possède pas nécessairement une valeur de vérité.

Par exemple :

Quelle heure est-il ?

n'est pas une proposition logique.

De même :

Fermez la fenêtre.

est une instruction et non une proposition pouvant être classée directement comme vraie ou fausse.

Prédicat

Un prédicat est une expression contenant une ou plusieurs variables et dont la valeur de vérité dépend des valeurs fournies.

Par exemple :

x > 10

est un prédicat.

Pour :

x = 15

le prédicat est vrai.

Pour :

x = 4

le prédicat est faux.

Opérations fondamentales

L'algèbre de Boole utilise trois opérations fondamentales :

NON
ET
OU

L'opération NON agit sur une seule valeur.

Les opérations ET et OU combinent deux valeurs ou deux expressions.

Négation logique

L'opération NON inverse la valeur d'une expression.

Elle peut être notée :

NON A

¬A

Ā

Si :

A = VRAI

alors :

NON A = FAUX

Si :

A = FAUX

alors :

NON A = VRAI

Conjonction logique

L'opération ET produit la valeur vraie uniquement lorsque ses deux opérandes sont vraies.

Elle peut être notée :

A ET B

A ∧ B

A · B

La conjonction correspond à l'idée que plusieurs conditions doivent être satisfaites simultanément.

Exemple de conjonction

Considérons la condition :

UtilisateurConnecté ET CompteActif

L'accès est autorisé uniquement si :

UtilisateurConnecté = VRAI

et :

CompteActif = VRAI

Si l'une des deux conditions est fausse, la conjonction complète est fausse.

Disjonction logique

L'opération OU produit la valeur vraie lorsqu'au moins l'un de ses opérandes est vrai.

Elle peut être notée :

A OU B

A ∨ B

A + B

Le OU booléen classique est généralement inclusif : il reste vrai lorsque les deux opérandes sont vraies.

Exemple de disjonction

Considérons :

EstAdministrateur OU EstResponsable

La condition est vraie lorsqu'une personne est :

administratrice ;
responsable ;
ou les deux à la fois.

Tableau élémentaire des opérations

A	B	NON A	A ET B	A OU B
0	0	1	0	0
0	1	1	0	1
1	0	0	0	1
1	1	0	1	1

Ce tableau présente toutes les combinaisons possibles de deux variables booléennes.

Opérations dérivées

À partir des opérations fondamentales, plusieurs autres opérations peuvent être définies :

le OU exclusif ;
le NON-ET ;
le NON-OU ;
l'implication ;
l'équivalence logique.

Ces opérations peuvent toutes être exprimées à l'aide de combinaisons de :

NON
ET
OU

Ou exclusif

Le OU exclusif, généralement noté XOR, est vrai lorsque les deux valeurs sont différentes.

A XOR B

Il est faux lorsque les deux valeurs sont identiques.

A	B	A XOR B
0	0	0
0	1	1
1	0	1
1	1	0

Différence entre OU et XOR

Le OU inclusif accepte le cas où les deux opérandes sont vrais :

1 OU 1 = 1

Le OU exclusif refuse ce cas :

1 XOR 1 = 0

Le XOR exprime donc généralement l'idée suivante :

l'un ou l'autre, mais pas les deux

Opérateur NAND

L'opérateur NAND est la négation du ET.

A NAND B
=
NON(A ET B)

Il est faux uniquement lorsque les deux opérandes sont vrais.

A	B	A NAND B
0	0	1
0	1	1
1	0	1
1	1	0

Opérateur NOR

L'opérateur NOR est la négation du OU.

A NOR B
=
NON(A OU B)

Il est vrai uniquement lorsque les deux opérandes sont faux.

A	B	A NOR B
0	0	1
0	1	0
1	0	0
1	1	0

Implication logique

L'implication est généralement notée :

A → B

Elle signifie :

Si A est vrai, alors B doit être vrai.

Elle est fausse uniquement lorsque :

A = VRAI

et :

B = FAUX

Équivalence logique

L'équivalence logique est vraie lorsque les deux valeurs sont identiques.

Elle peut être notée :

A ↔ B

ou :

A XNOR B

A	B	A ↔ B
0	0	1
0	1	0
1	0	0
1	1	1

Expression booléenne

Une expression booléenne est une combinaison :

de variables booléennes ;
de constantes booléennes ;
d'opérateurs logiques ;
de parenthèses.

Par exemple :

(A ET B) OU NON C

Cette expression dépend de trois variables :

A
B
C

Évaluation d'une expression

Considérons :

(A ET B) OU NON C

avec :

A = VRAI
B = FAUX
C = FAUX

On calcule d'abord :

A ET B
=
VRAI ET FAUX
=
FAUX

Puis :

NON C
=
NON FAUX
=
VRAI

Finalement :

FAUX OU VRAI
=
VRAI

Fonction booléenne

Une fonction booléenne reçoit une ou plusieurs valeurs booléennes et retourne une valeur booléenne.

Par exemple :

F(A,B)
=
A ET NON B

La fonction possède deux paramètres et produit une sortie appartenant à :

{0,1}

Nombre de combinaisons d'entrées

Pour une fonction contenant :

variables booléennes, le nombre de combinaisons possibles est :

2ⁿ

Par exemple, avec trois variables :

A
B
C

on obtient :

2₃ = 8

combinaisons différentes.

Nombre de fonctions booléennes

Une fonction de n variables possède :

2_n

combinaisons d'entrées.

Pour chaque combinaison, la sortie peut être :

ou :

Le nombre total de fonctions booléennes distinctes de n variables est donc :

2^(2ⁿ)

Exemple avec une variable

Avec une seule variable :

il existe :

2^(2¹)
=
2²
=
4

fonctions booléennes différentes :

Toujours faux
A
NON A
Toujours vrai

Exemple avec deux variables

Avec deux variables :

A
B

le nombre de fonctions possibles est :

2^(2²)
=
2⁴
=
16

Ces fonctions comprennent notamment :

ET ;
OU ;
XOR ;
NAND ;
NOR ;
implication ;
équivalence ;
fonctions constantes.

Table de vérité

Une table de vérité présente le résultat d'une expression pour toutes les combinaisons possibles de ses variables.

Pour deux variables, la table comporte :

2² = 4

lignes.

Pour trois variables, elle comporte :

2³ = 8

lignes.

Pour quatre variables, elle comporte :

2⁴ = 16

lignes.

Exemple de table de vérité

Pour :

F(A,B)
=
A ET NON B

on obtient :

A	B	NON B	F(A,B)
0	0	1	0
0	1	0	0
1	0	1	1
1	1	0	0

La fonction est vraie uniquement lorsque :

A = 1

et :

B = 0

Équivalence des expressions

Deux expressions booléennes sont équivalentes lorsqu'elles donnent la même sortie pour toutes les combinaisons d'entrées.

Par exemple :

NON(A ET B)

est équivalent à :

NON A OU NON B

Cette identité est l'une des lois de De Morgan.

Vérification d'une équivalence

Une équivalence peut être vérifiée de deux manières principales :

en appliquant les lois de l'algèbre de Boole ;
en construisant une table de vérité.

Si les colonnes finales des deux expressions sont identiques, les expressions sont équivalentes.

Lois fondamentales

L'algèbre de Boole possède plusieurs lois permettant de transformer et de simplifier les expressions.

Parmi les principales lois, on trouve :

la commutativité ;
l'associativité ;
la distributivité ;
l'idempotence ;
la complémentarité ;
l'absorption ;
les identités ;
les lois de De Morgan.

Identités fondamentales

Quelques identités simples sont :

A ET 1 = A

A OU 0 = A

A ET 0 = 0

A OU 1 = 1

A ET A = A

A OU A = A

NON NON A = A

Complémentarité

Une variable combinée avec son complément satisfait :

A ET NON A = 0

et :

A OU NON A = 1

La première expression représente une contradiction.

La seconde représente une tautologie.

Tautologie

Une tautologie est une expression toujours vraie, quelles que soient les valeurs de ses variables.

Exemple :

A OU NON A

A	NON A	A OU NON A
0	1	1
1	0	1

Contradiction

Une contradiction est une expression toujours fausse.

Exemple :

A ET NON A

A	NON A	A ET NON A
0	1	0
1	0	0

Expression contingente

Une expression est contingente lorsqu'elle peut être vraie ou fausse selon les valeurs de ses variables.

Par exemple :

A ET B

est vraie dans certains cas et fausse dans d'autres.

La majorité des conditions rencontrées dans les programmes sont contingentes.

Différence avec l'algèbre ordinaire

L'algèbre de Boole possède des règles différentes de celles de l'arithmétique classique.

Par exemple :

1 + 1 = 1

lorsque le symbole `+` représente le OU logique.

De même :

A + A = A

selon la loi d'idempotence.

En algèbre ordinaire, on aurait plutôt :

A + A = 2A

Signification des symboles

Les symboles :

et :

ne représentent pas nécessairement l'addition et la multiplication numériques.

En algèbre de Boole :

A + B

représente souvent :

A OU B

et :

A · B

représente souvent :

A ET B

Priorité des opérations

Un ordre de priorité courant est :

Parenthèses
NON
ET
XOR
OU

Ainsi :

A OU B ET NON C

est généralement interprété comme :

A OU (B ET (NON C))

Il est recommandé d'utiliser des parenthèses afin d'éviter toute ambiguïté.

Simplification booléenne

La simplification booléenne consiste à remplacer une expression par une autre expression équivalente, mais plus courte ou plus facile à évaluer.

Par exemple :

A ET (A OU B)

se simplifie en :

Cette transformation correspond à la loi d'absorption.

Objectifs de la simplification

La simplification peut permettre :

de réduire le nombre d'opérations ;
d'améliorer la lisibilité d'une condition ;
de diminuer le nombre de portes logiques ;
de réduire la consommation électrique d'un circuit ;
d'accélérer certaines évaluations ;
de faciliter la vérification du comportement.

Algèbre de Boole et programmation

Dans les langages de programmation, les valeurs booléennes sont principalement utilisées dans les structures de contrôle.

Par exemple :

SI condition ALORS
instruction
FIN SI

L'instruction est exécutée uniquement lorsque :

condition = VRAI

Exemple de condition

SI âge >= 18 ET compteActif ALORS
AFFICHER
"Accès autorisé"
FIN SI

La condition est vraie uniquement lorsque la personne est majeure et que son compte est actif.

Conditions composées

Une condition composée combine plusieurs tests.

SI
   utilisateurConnecté
   ET
   (
      estAdministrateur
      OU
      estResponsable
   )
ALORS
   AutoriserModification
FIN SI

Cette expression exige que l'utilisateur soit connecté et possède au moins l'un des deux rôles autorisés.

Boucles

Les expressions booléennes contrôlent également les boucles.

TANT QUE
fichierNonTerminé
FAIRE

LireLigne

FIN TANT QUE

La boucle continue aussi longtemps que la condition reste vraie.

Comparaisons

Les opérateurs de comparaison produisent généralement une valeur booléenne.

Exemples :

x = y

x ≠ y

x < y

x ≤ y

x > y

x ≥ y

Chaque comparaison produit :

VRAI

ou :

FAUX

Exemple d'évaluation

Considérons :

x = 10
y = 20

Alors :

x < y

retourne :

VRAI

tandis que :

x = y

retourne :

FAUX

Type booléen dans les langages

De nombreux langages possèdent un type booléen explicite.

Langage	Type ou notation
Pascal	Boolean
Delphi	Boolean
C++	bool
C#	bool
Java	boolean
JavaScript	boolean
Python	bool
Visual Basic	Boolean
SQL	Variable selon le SGBD

Exemple en Pascal



Program ExempleBooleen;

 
var

  Age: Integer;

  CompteActif: Boolean;

  AccesAutorise: Boolean;

 
BEGIN

  Age := 25;

  CompteActif := True;

 
  AccesAutorise :=

    (Age >= 18) and CompteActif;

 
  if AccesAutorise then

    WriteLn('Accès autorisé')

  else

    WriteLn('Accès refusé');

END.

Exemple en Java


public final class ExempleBooleen {
 
    private ExempleBooleen() {
    }
 
    public static void main(String[] args) {
        int age = 25;
        boolean compteActif = true;
 
        boolean accesAutorise =
            age >= 18 && compteActif;
 
        if (accesAutorise) {
            System.out.println(
                "Accès autorisé"
            );
        } else {
            System.out.println(
                "Accès refusé"
            );
        }
    }
}

Exemple en C#



int age = 25;

bool compteActif = true;

 
bool accesAutorise =

    age >= 18 && compteActif;

 
if (accesAutorise)

{

    Console.WriteLine(

        "Accès autorisé"

    );

}

else

{

    Console.WriteLine(

        "Accès refusé"

    );

}

Exemple en Python



age = 25

compte_actif = True

 
acces_autorise = (

    age >= 18

    and compte_actif

)

 
if acces_autorise:

    print("Accès autorisé")

else:

    print("Accès refusé")

Évaluation en court-circuit

De nombreux langages utilisent une évaluation appelée court-circuit.

Dans l'expression :

A ET B

si :

A = FAUX

le résultat est déjà connu.

La valeur de :

n'a donc pas besoin d'être évaluée.

Court-circuit avec OU

Dans l'expression :

A OU B

si :

A = VRAI

le résultat est déjà vrai.

L'expression :

peut alors être ignorée.

Utilité du court-circuit

Le court-circuit permet :

de réduire le nombre d'opérations ;
d'éviter des calculs inutiles ;
de protéger certains accès ;
d'éviter des erreurs d'exécution.

Par exemple :

objet ≠ NUL
E
T objet.estValide()

La seconde condition n'est évaluée que si l'objet existe.

Valeur booléenne et entier

Dans certains langages anciens ou de bas niveau, les valeurs booléennes sont représentées par des entiers.

Une convention fréquente est :

0 = FAUX

et :

valeur différente de 0 = VRAI

Cependant, la représentation exacte de la valeur vraie peut varier.

Booléens en langage C

En langage C traditionnel, les conditions utilisent les règles suivantes :

est considéré comme faux.

Toute valeur non nulle est considérée comme vraie.

Par exemple :



if (5)

{

    /* Cette instruction est exécutée. */

}

Représentation binaire

Dans un ordinateur, les valeurs booléennes sont stockées à l'aide de bits ou de groupes de bits.

Un bit peut prendre les valeurs :

ou :

Cette correspondance naturelle explique pourquoi l'algèbre de Boole est fondamentale pour les systèmes numériques.

Logique et opérations bit à bit

Les opérations logiques doivent être distinguées des opérations bit à bit.

Une opération logique traite une valeur entière comme une condition globale.

Une opération bit à bit applique l'opération séparément à chaque position binaire.

Exemple d'opération bit à bit

Considérons :

1100

et :

1010

L'opération ET bit à bit donne :

1100
1010
----
1000

Chaque colonne est calculée indépendamment.

Masques de bits

Les masques de bits utilisent les opérations booléennes afin de sélectionner ou de modifier certains bits.

Par exemple :

valeur ET masque

permet de conserver uniquement les bits activés dans le masque.

valeur OU masque

permet d'activer certains bits.

valeur XOR masque

permet d'inverser certains bits.

Portes logiques

Une porte logique est un composant électronique réalisant une opération booléenne.

Les principales portes sont :

porte NON ;
porte ET ;
porte OU ;
porte XOR ;
porte NAND ;
porte NOR ;
porte XNOR.

Chaque porte reçoit une ou plusieurs entrées binaires et produit une sortie binaire.

Exemple de porte ET

Une porte ET possède généralement deux entrées :

A
B

et une sortie :

S = A ET B

La sortie est active uniquement lorsque les deux entrées sont actives.

Circuits combinatoires

Un circuit combinatoire produit une sortie dépendant uniquement de ses entrées actuelles.

Parmi les circuits combinatoires, on trouve :

les additionneurs ;
les comparateurs ;
les multiplexeurs ;
les démultiplexeurs ;
les encodeurs ;
les décodeurs.

Leur comportement peut être décrit à l'aide d'expressions booléennes.

Circuits séquentiels

Un circuit séquentiel possède également un état interne.

Sa sortie dépend :

des entrées actuelles ;
de l'état précédent.

Parmi ces circuits, on trouve :

les bascules ;
les registres ;
les compteurs ;
les mémoires ;
les machines à états.

Demi-additionneur

Un demi-additionneur additionne deux bits :

A
B

La somme est donnée par :

S = A XOR B

La retenue est donnée par :

R = A ET B

Cette structure montre le lien direct entre l'algèbre de Boole et l'arithmétique binaire.

Relation avec la théorie des ensembles

L'algèbre de Boole possède une correspondance avec les opérations sur les ensembles.

Algèbre de Boole	Théorie des ensembles
A ET B	Intersection
A OU B	Union
NON A	Complément
0	Ensemble vide
1	Ensemble universel

Les mêmes lois peuvent ainsi être interprétées dans les deux domaines.

Exemple avec les ensembles

Pour deux ensembles :

A
B

l'intersection :

A ∩ B

correspond à :

A ET B

L'union :

A ∪ B

correspond à :

A OU B

Le complément :

A^c

correspond à :

NON A

Relation avec la logique propositionnelle

L'algèbre de Boole et la logique propositionnelle manipulent des structures très proches.

Une variable booléenne peut représenter une proposition.

Les opérations :

ET
OU
NON

correspondent aux connecteurs logiques :

conjonction
disjonction
négation

Les identités booléennes permettent alors de transformer des raisonnements logiques.

Relation avec les circuits électriques

Un circuit simple comportant des interrupteurs peut être modélisé par l'algèbre de Boole.

Deux interrupteurs placés en série correspondent à :

Le courant passe uniquement si les deux interrupteurs sont fermés.

Deux interrupteurs placés en parallèle correspondent à :

Le courant passe si au moins l'un des interrupteurs est fermé.

Conditions dans les bases de données

Les requêtes de base de données utilisent fréquemment des expressions booléennes.

Exemple :



SELECT *

FROM Utilisateurs

WHERE Age >= 18

  AND CompteActif = 1;

La clause :



WHERE

conserve uniquement les lignes pour lesquelles la condition est vraie.

Logique ternaire de SQL

Dans SQL, la présence de :



NULL

introduit généralement une troisième valeur logique :

UNKNOWN

Les résultats possibles deviennent alors :

TRUE
FALSE
UNKNOWN

Cette logique n'est plus une algèbre de Boole classique à deux valeurs.

Filtres et moteurs de recherche

Les moteurs de recherche et les systèmes documentaires utilisent souvent des opérateurs booléens.

Par exemple :

Pascal ET compilateur

recherche les documents contenant les deux termes.

Pascal OU Delphi

recherche les documents contenant au moins l'un des termes.

Pascal NON Delphi

exclut certains résultats.

Contrôle d'accès

Les systèmes de sécurité utilisent des expressions booléennes pour déterminer les permissions.

Par exemple :

CompteActif ET ( EstAdministrateur OU PossèdePermissionÉcriture )

Cette condition autorise l'accès uniquement aux comptes actifs possédant les droits nécessaires.

Validation des données

L'algèbre de Boole est également utilisée pour valider les entrées.

NomNonVide
ET
AdresseCourrielValide
ET
MotDePasseSuffisammentLong

La validation complète réussit uniquement lorsque toutes les conditions requises sont vraies.

Automates et machines à états

Les transitions d'un automate sont souvent contrôlées par des conditions booléennes.

Par exemple :

SI
   BoutonAppuyé
   ET
   PorteFermée
ALORS

   État ← Démarrage

FIN SI

L'algèbre de Boole permet ainsi de décrire les règles de changement d'état.

Intelligence artificielle

Dans certains systèmes d'intelligence artificielle, les règles peuvent être exprimées sous forme logique.

SI
   TempératureÉlevée
   ET
   VentFaible
ALORS

   Risque ← Élevé

FIN SI

Les systèmes experts, les moteurs d'inférence et certains solveurs utilisent largement ce type de représentation.

Satisfaisabilité booléenne

Le problème de satisfaisabilité booléenne consiste à déterminer s'il existe une affectation des variables rendant une expression vraie.

Par exemple :

(A OU B)
ET
(NON A OU C)

On cherche des valeurs de :

A
B
C

pour lesquelles l'expression entière vaut vrai.

Ce problème est généralement appelé :

SAT

Formes normales

Les expressions booléennes peuvent être transformées sous certaines formes standardisées.

Les principales sont :

la forme normale disjonctive ;
la forme normale conjonctive ;
la forme canonique disjonctive ;
la forme canonique conjonctive.

Ces représentations sont utiles pour les solveurs, les circuits et les méthodes de simplification.

Forme normale disjonctive

Une forme normale disjonctive est une expression constituée d'un OU entre plusieurs termes reliés par des ET.

Exemple :

(A ET B)
OU
(NON A ET C)

Cette structure est également appelée :

somme de produits

Forme normale conjonctive

Une forme normale conjonctive est une expression constituée d'un ET entre plusieurs clauses reliées par des OU.

Exemple :

(A OU B)
ET
(NON A OU C)

Cette structure est également appelée :

produit de sommes

Méthodes de simplification

Plusieurs méthodes permettent de simplifier une fonction booléenne :

application directe des règles booléennes ;
utilisation d'une table de vérité ;
cartes de Karnaugh ;
méthode de Quine-McCluskey ;
diagrammes de décision binaires ;
solveurs logiques.

La méthode choisie dépend du nombre de variables et de la complexité de la fonction.

Cartes de Karnaugh

Les cartes de Karnaugh permettent de regrouper visuellement les valeurs identiques d'une table de vérité.

Elles sont particulièrement utiles pour simplifier des fonctions comportant un petit nombre de variables.

Les regroupements permettent d'éliminer les variables qui ne modifient pas le résultat.

Méthode de Quine-McCluskey

La méthode de Quine-McCluskey est une technique algorithmique de simplification.

Elle identifie :

les mintermes ;
les implicants premiers ;
les implicants premiers essentiels.

Contrairement aux cartes de Karnaugh, elle peut être automatisée plus facilement.

Diagrammes de décision binaires

Un diagramme de décision binaire représente une fonction logique sous la forme d'un graphe.

Chaque noeud teste une variable.

Chaque branche correspond généralement à :

ou :

Les feuilles indiquent le résultat final de la fonction.

Complétude fonctionnelle

Un ensemble d'opérateurs est dit fonctionnellement complet s'il permet de construire toutes les fonctions booléennes possibles.

Les ensembles suivants sont notamment complets :

{NON, ET}

{NON, OU}

{NAND}

{NOR}

Ainsi, toutes les fonctions booléennes peuvent être réalisées uniquement avec des portes NAND ou uniquement avec des portes NOR.

Algèbre booléenne abstraite

L'algèbre de Boole ne se limite pas aux valeurs numériques :

0
1

Elle peut être définie sur d'autres ensembles, à condition que les opérations respectent les lois booléennes.

Les ensembles de parties d'un ensemble constituent un exemple classique d'algèbre booléenne abstraite.

Algèbre des parties d'un ensemble

Pour un ensemble universel :

l'ensemble de toutes ses parties est noté :

P(U)

Les opérations booléennes correspondent alors à :

Intersection
Union
Complément

L'ensemble vide joue le rôle de :

et l'ensemble universel joue le rôle de :

Logique à plusieurs valeurs

Certaines applications ne se limitent pas à vrai et faux.

Elles peuvent ajouter des valeurs comme :

INCONNU
INDÉTERMINÉ
NON DÉFINI

Ces systèmes sont appelés logiques à plusieurs valeurs.

Ils ne correspondent plus exactement à l'algèbre booléenne classique, mais en constituent une extension.

Logique floue

La logique floue autorise des degrés de vérité compris entre :

et :

Par exemple :

0,8

peut représenter une affirmation largement vraie sans être absolument vraie.

La logique floue ne doit pas être confondue avec l'algèbre de Boole, dans laquelle seules deux valeurs sont permises.

Méthode générale d'analyse d'une expression

MODULE AnalyserExpressionBooléenne(Expression)

   Identifier les variables

   Identifier les opérateurs

   Déterminer leur priorité

   Ajouter des parenthèses
      si nécessaire

   Énumérer toutes les
      combinaisons d'entrées

   Évaluer chaque combinaison

   Construire la table
      de vérité

   Simplifier l'expression

   Vérifier l'équivalence

   RETOURNER résultat

Algorithme d'évaluation

MODULE EvaluerCondition(A,B,C)
   résultat ←
      (
         A ET B
      )
      OU
      NON C

   RETOURNER résultat

Exemple Java d'une fonction booléenne


public final class AlgebreBoole {
 
    private AlgebreBoole() {
    }
 
    public static boolean autoriserAcces(
        boolean utilisateurConnecte,
        boolean administrateur,
        boolean responsable
    ) {
        return utilisateurConnecte
            && (
                administrateur
                || responsable
            );
    }
 
    public static void main(String[] args) {
        boolean acces = autoriserAcces(
            true,
            false,
            true
        );
 
        System.out.println(
            "Accès autorisé : " + acces
        );
    }
}

Résultat du programme

Les valeurs fournies sont :

utilisateurConnecte = VRAI
administrateur = FAUX
responsable = VRAI

La sous-expression :

administrateur OU responsable

retourne :

VRAI

L'expression complète retourne donc :

VRAI ET VRAI
=
VRAI

Le programme affiche :

Accès autorisé : true

Tableau des principales notations

Opération	Notation textuelle	Notation mathématique	Notation fréquente en programmation
Négation	NON A	¬A ou Ā	!A ou not A
Conjonction	A ET B	A ∧ B ou A·B	A && B ou A and B
Disjonction	A OU B	A ∨ B ou A+B	A \|\| B ou A or B
Ou exclusif	A XOR B	A ⊕ B	A ^ B dans certains langages
Non-ET	A NAND B	A ↑ B	Généralement composé
Non-OU	A NOR B	A ↓ B	Généralement composé
Implication	A implique B	A → B	Généralement composé
Équivalence	A équivaut à B	A ↔ B	Comparaison d'égalité

Domaines d'application

L'algèbre de Boole est utilisée dans :

les langages de programmation ;
les circuits numériques ;
les processeurs ;
les systèmes embarqués ;
les bases de données ;
les moteurs de recherche ;
les systèmes de contrôle ;
les automates ;
les réseaux ;
la cryptographie ;
les compilateurs ;
la vérification formelle ;
les systèmes experts ;
l'intelligence artificielle ;
les tests logiciels ;
les contrôles d'accès ;
les filtres de données ;
les opérations sur les bits.

Avantages

L'algèbre de Boole présente plusieurs avantages :

elle fournit une représentation simple des décisions binaires ;
elle permet de décrire les conditions des programmes ;
elle constitue le fondement mathématique des circuits numériques ;
elle facilite la simplification des expressions logiques ;
elle permet de vérifier l'équivalence de deux conditions ;
elle facilite la conception de tables de vérité ;
elle permet de réduire le nombre de portes d'un circuit ;
elle possède des règles précises et reproductibles ;
elle s'applique à la logique, aux ensembles et aux bits ;
elle permet l'automatisation du raisonnement logique ;
elle intervient dans de nombreux domaines informatiques.

Limites et précautions

Plusieurs précautions doivent être prises lors de l'utilisation de l'algèbre de Boole :

il faut distinguer le OU inclusif du OU exclusif ;
les symboles peuvent varier selon les langages ;
les opérateurs logiques ne doivent pas être confondus avec les opérateurs bit à bit ;
la priorité des opérateurs peut varier ;
des parenthèses doivent être utilisées pour éviter les ambiguïtés ;
certaines expressions équivalentes ne possèdent pas la même lisibilité ;
l'évaluation en court-circuit peut modifier l'exécution des expressions ayant des effets secondaires ;
les valeurs booléennes ne sont pas toujours représentées par exactement un octet ;
certains langages considèrent les valeurs non nulles comme vraies ;
SQL utilise généralement une logique à trois valeurs en présence de NULL ;
les expressions comportant un grand nombre de variables produisent des tables de vérité très volumineuses ;
la simplification minimale d'une fonction complexe peut nécessiter des algorithmes spécialisés.

Remarque

L'algèbre de Boole constitue l'un des liens les plus importants entre les mathématiques et l'informatique. Ses deux valeurs fondamentales correspondent naturellement aux états binaires utilisés par les ordinateurs, tandis que ses opérations permettent de représenter les décisions, les conditions et les transformations logiques.

Dans un programme, elle détermine quand une instruction doit être exécutée ou lorsqu'une boucle doit se terminer. Dans un circuit, elle décrit le comportement des portes logiques et des composants numériques. Dans une base de données, elle contrôle les filtres et les critères de recherche. Dans les méthodes formelles, elle permet de vérifier la cohérence et la satisfaisabilité des expressions.

L'étude de l'algèbre de Boole prépare ainsi aux règles booléennes, aux tables de vérité, aux lois de De Morgan, aux formes normales, aux cartes de Karnaugh, aux opérations sur les bits, aux circuits logiques et aux techniques de simplification utilisées dans les logiciels et les systèmes numériques.

Dernière mise à jour : Dimanche, le 30 avril 2017