Langage de programmation - Mathématiques appliquées

Expressions booléennes

Une expression booléenne est une expression mathématique ou informatique dont l'évaluation produit une valeur appartenant au domaine booléen. Son résultat ne peut donc prendre que l'une des deux valeurs suivantes :

VRAI

ou :

FAUX

Dans une notation numérique, ces valeurs sont généralement représentées par :

et :

Les expressions booléennes sont construites à partir de variables, de constantes, de comparaisons, d'opérateurs logiques et de parenthèses. Elles permettent de représenter des conditions simples ou complexes, comme la validité d'une donnée, l'existence d'un fichier, l'autorisation d'un utilisateur ou l'état d'un appareil.

En programmation, les expressions booléennes contrôlent les instructions conditionnelles, les boucles, les validations, les filtres, les recherches et les règles de sécurité. En électronique numérique, elles décrivent le comportement des portes et des circuits logiques. En mathématiques, elles représentent des propositions et permettent d'étudier les équivalences, les tautologies, les contradictions et les fonctions booléennes.

Définition

Une expression booléenne est une combinaison de valeurs et d'opérations dont le résultat appartient à l'ensemble :

B = {0,1}

ou, de manière équivalente :

B = {FAUX,VRAI}

Par exemple :

A ET B

est une expression booléenne lorsque :

A ∈ B

et :

B ∈ B

Le résultat de l'expression appartient également à `B`.

Exemple élémentaire

Considérons :

A = VRAI
B = FAUX

L'expression :

A ET B

produit :

VRAI ET FAUX
=
FAUX

L'expression entière possède donc la valeur booléenne :

FAUX

Composants d'une expression booléenne

Une expression booléenne peut contenir :

des constantes booléennes ;
des variables booléennes ;
des prédicats ;
des comparaisons ;
des opérations logiques ;
des appels de fonctions booléennes ;
des parenthèses ;
des sous-expressions.

Par exemple :

CompteActif
ET
(
Âge >= 18
OU PossèdeAutorisation
)

contient une variable booléenne, une comparaison, trois opérandes et deux opérations logiques.

Constantes booléennes

Les constantes fondamentales sont :

FAUX

et :

VRAI

Elles peuvent également être notées :

et :

Une constante booléenne possède une valeur fixe et ne dépend d'aucune variable.

Expressions constantes

Une expression ne contenant que des constantes peut être évaluée immédiatement.

Par exemple :

VRAI ET FAUX

retourne :

FAUX

De même :

NON FAUX OU VRAI

retourne toujours :

VRAI

Variables booléennes

Une variable booléenne peut contenir :

VRAI

ou :

FAUX

Par exemple :

FichierExiste

peut être utilisée directement comme expression booléenne.

SI FichierExiste ALORS
OuvrirFichier
FIN SI

La variable représente déjà une condition complète.

Expressions atomiques

Une expression atomique est une expression ne contenant aucune sous-expression booléenne composée.

Les expressions suivantes sont atomiques :

VRAI

Âge >= 18

FichierExiste()

Elles peuvent ensuite être combinées pour former des expressions plus complexes.

Expressions composées

Une expression composée réunit plusieurs expressions atomiques ou composées à l'aide d'opérateurs logiques.

Par exemple :

EstMajeur
ET
CompteActif

est composée de deux expressions atomiques.

L'expression :

EstMajeur
ET
(
CompteActif
OU PossèdeAutorisationSpéciale
)

contient une sous-expression imbriquée.

Opérandes

Les valeurs ou expressions auxquelles un opérateur est appliqué sont appelées opérandes.

Dans :

A ET B

les opérandes sont :

et :

Dans :

NON A

l'unique opérande est :

Opérateurs unaires

Un opérateur unaire agit sur un seul opérande.

L'opérateur booléen unaire fondamental est :

NON

Par exemple :

NON EstConnecté

retourne vrai lorsque :

EstConnecté = FAUX

Opérateurs binaires

Un opérateur binaire combine deux opérandes.

Les principaux opérateurs binaires sont :

ET
OU
XOR
NAND
NOR
Implication
Équivalence

Par exemple :

A OU B

combine les valeurs de `A` et de `B`.

Négation

La négation inverse la valeur d'une expression.

NON VRAI = FAUX

NON FAUX = VRAI

Elle peut être notée :

NON A

¬A

Ā

ou, dans plusieurs langages :

Conjonction

La conjonction est vraie uniquement lorsque tous ses opérandes sont vrais.

A ET B

A	B	A ET B
0	0	0
0	1	0
1	0	0
1	1	1

Une conjonction représente généralement une accumulation de conditions obligatoires.

Disjonction

La disjonction inclusive est vraie lorsqu'au moins un opérande est vrai.

A OU B

A	B	A OU B
0	0	0
0	1	1
1	0	1
1	1	1

Une disjonction représente généralement plusieurs possibilités acceptables.

Ou exclusif

Le OU exclusif est vrai lorsque les deux opérandes sont différents.

A XOR B

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

Il exprime l'idée :

A ou B, mais pas les deux

Comparaisons

Une comparaison entre deux valeurs produit généralement un résultat booléen.

Les principales comparaisons sont :

=
≠
<
≤
>
≥

Par exemple :

Âge >= 18

retourne vrai lorsque la valeur de `Âge` est supérieure ou égale à 18.

Comparaison d'égalité

L'expression :

A = B

retourne vrai lorsque les deux valeurs sont égales.

Par exemple :

10 = 10

retourne :

VRAI

tandis que :

10 = 12

retourne :

FAUX

Comparaison d'inégalité

L'expression :

A ≠ B

retourne vrai lorsque les deux valeurs sont différentes.

10 ≠ 12

retourne :

VRAI

La notation utilisée en programmation peut être :

ou une autre forme définie par le langage.

Comparaisons numériques

Les comparaisons numériques permettent de construire des prédicats.

Température > 30

Solde <= 0

Position >= Minimum
ET
Position <= Maximum

Chaque comparaison produit une valeur booléenne pouvant être combinée avec d'autres conditions.

Comparaisons de chaînes

Les chaînes de caractères peuvent également être comparées.

Nom = "Sylvain"

Commande ≠ "QUITTER"

La comparaison peut dépendre :

de la casse ;
de la langue ;
de l'encodage ;
de l'ordre lexicographique ;
des règles de collation.

Comparaison de références

Dans certains langages, comparer deux objets peut signifier :

comparer leurs références ;
comparer leur contenu ;
appeler une méthode d'égalité ;
appliquer une surcharge d'opérateur.

Il faut donc connaître les règles du langage pour interpréter correctement :

ObjetA = ObjetB

Prédicats

Un prédicat est une expression ou une fonction produisant une valeur booléenne.

Exemples :

EstPair(Nombre)

EstVide(Chaîne)

Existe(Fichier)

PeutModifier(Utilisateur,Dossier)

Les prédicats permettent de nommer et de réutiliser des conditions.

Exemple de prédicat

MODULE EstPair(Nombre)

RETOURNER
Nombre MOD 2 = 0

L'expression :

Nombre MOD 2 = 0

produit une valeur booléenne.

L'appel :

EstPair(10)

retourne :

VRAI

Structure syntaxique

Une expression booléenne possède une structure déterminée par :

les opérateurs employés ;
leur priorité ;
leur associativité ;
les parenthèses ;
la grammaire du langage.

Par exemple :

A OU B ET C

est généralement structurée comme :

A OU (B ET C)

car ET est prioritaire sur OU.

Parenthèses

Les parenthèses imposent un regroupement explicite.

(A OU B) ET C

est différent de :

A OU (B ET C)

Même lorsque les parenthèses ne sont pas techniquement nécessaires, elles peuvent rendre l'intention plus claire.

Sous-expression

Une sous-expression est une partie d'une expression plus grande qui peut être évaluée séparément.

Dans :

A ET (B OU NON C)

les sous-expressions comprennent :

NON C

B OU NON C

et l'expression complète :

A ET (B OU NON C)

Arbre syntaxique

L'expression :

A ET (B OU NON C)

peut être représentée par l'arbre suivant :

          ET
         /  \
        A    OU
            / \
           B  NON
                \
                 C

Chaque feuille représente une valeur ou une variable.

Chaque noeud interne représente une opération.

Évaluation ascendante

L'arbre syntaxique peut être évalué en partant des feuilles.

Pour :

A = 1
B = 0
C = 0

on calcule d'abord :

NON C = 1

Puis :

B OU NON C
=
0 OU 1
=
1

Enfin :

A ET 1
=
1 ET 1
=
1

Affectation des variables

Une affectation de vérité associe une valeur à chaque variable d'une expression.

Pour :

F(A,B,C)

une affectation possible est :

A = 1
B = 0
C = 1

Chaque affectation produit une valeur déterminée pour `F`.

Nombre d'affectations

Une expression comportant :

variables distinctes possède :

2ⁿ

affectations possibles.

Avec deux variables :

2² = 4

Avec trois variables :

2³ = 8

Avec quatre variables :

2⁴ = 16

Table de vérité

Une table de vérité évalue une expression pour toutes les affectations possibles de ses variables.

Considérons :

F(A,B)
=
A ET NON B

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

La table décrit entièrement le comportement de la fonction.

Construction d'une table de vérité

Pour construire une table de vérité :

Identifier les variables distinctes
Calculer le nombre de lignes 2ⁿ
Énumérer toutes les affectations
Ajouter les colonnes intermédiaires
Évaluer chaque sous-expression
Calculer la colonne finale

Les colonnes intermédiaires réduisent les risques d'erreur.

Exemple à trois variables

Considérons :

F(A,B,C)
=
(A ET B) OU NON C

A	B	C	A ET B	NON C	F
0	0	0	0	1	1
0	0	1	0	0	0
0	1	0	0	1	1
0	1	1	0	0	0
1	0	0	0	1	1
1	0	1	0	0	0
1	1	0	1	1	1
1	1	1	1	0	1

Valeur d'une expression

Une expression booléenne ne possède pas nécessairement une valeur fixe.

Sa valeur peut dépendre :

des variables ;
des données entrées ;
de l'état du programme ;
du résultat d'un calcul ;
du retour d'une fonction ;
d'un événement externe.

Par exemple :

UtilisateurConnecté
ET
SessionValide

peut changer de valeur au cours de l'exécution.

Expression vraie

Une expression est vraie pour une affectation donnée lorsqu'elle retourne :

Par exemple :

A ET B

est vraie pour :

A = 1
B = 1

Elle est fausse pour les trois autres affectations.

Expression fausse

Une expression est fausse pour une affectation donnée lorsqu'elle retourne :

Cela ne signifie pas nécessairement que l'expression est une contradiction.

Une expression contingente peut être fausse pour certaines affectations et vraie pour d'autres.

Tautologie

Une tautologie est une expression vraie pour toutes les affectations possibles.

Exemple :

A OU NON A

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

Cette expression est toujours vraie.

Contradiction

Une contradiction est une expression fausse pour toutes les affectations.

Exemple :

A ET NON A

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

Cette expression ne peut jamais être satisfaite.

Contingence

Une expression est contingente lorsqu'elle est vraie pour certaines affectations et fausse pour d'autres.

Par exemple :

A OU B

est fausse lorsque :

A = 0
B = 0

et vraie dans les trois autres cas.

Satisfaisabilité

Une expression est satisfaisable s'il existe au moins une affectation pour laquelle elle est vraie.

Par exemple :

A ET B

est satisfaisable, car elle est vraie pour :

A = 1
B = 1

Une contradiction n'est pas satisfaisable.

Validité

Une expression est valide lorsqu'elle est vraie pour toutes les affectations.

Une expression valide est donc une tautologie.

Par exemple :

(A ET B) → A

est valide, car une conjonction vraie implique nécessairement que `A` est vrai.

Équivalence logique

Deux expressions sont logiquement équivalentes lorsqu'elles possèdent la même valeur pour toutes les affectations possibles.

On écrit :

F ≡ G

Par exemple :

NON(A ET B)

est équivalent à :

NON A OU NON B

Vérification par table de vérité

Considérons les deux expressions :

F = NON(A ET B)

G = NON A OU NON B

A	B	F	G
0	0	1	1
0	1	1	1
1	0	1	1
1	1	0	0

Les colonnes finales sont identiques.

Les expressions sont donc équivalentes.

Simplification

La simplification consiste à remplacer une expression par une expression équivalente plus courte ou plus facile à comprendre.

Par exemple :

A ET VRAI

se simplifie en :

De même :

A OU FAUX

se simplifie en :

Simplification par idempotence

Les lois d'idempotence donnent :

A ET A = A

et :

A OU A = A

Ainsi :

CompteActif ET CompteActif

peut être remplacé par :

CompteActif

Simplification par absorption

La loi d'absorption donne :

A OU (A ET B) = A

et :

A ET (A OU B) = A

Par exemple :

EstAdministrateur OU ( EstAdministrateur ET PossèdePermission )

se simplifie en :

EstAdministrateur

Simplification par complémentarité

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

A ET NON A = FAUX

et :

A OU NON A = VRAI

Ces lois permettent de détecter des expressions impossibles ou toujours vraies.

Lois de De Morgan

Les lois de De Morgan permettent de distribuer une négation sur une expression.

NON(A ET B)
=
NON A OU NON B

NON(A OU B)
=
NON A ET NON B

Elles sont particulièrement utiles pour transformer les conditions négatives.

Exemple de De Morgan

Considérons :

NON(
CompteActif
ET PossèdePermission
)

Cette expression est équivalente à :

NON CompteActif OU NON PossèdePermission

Le refus survient donc si le compte est inactif ou si la permission manque.

Forme normale disjonctive

Une expression est en forme normale disjonctive lorsqu'elle est constituée d'une disjonction de conjonctions.

Exemple :

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

Chaque groupe relié par ET est appelé un terme ou un produit logique.

L'ensemble est parfois appelé :

somme de produits

Forme normale conjonctive

Une expression est en forme normale conjonctive lorsqu'elle est constituée d'une conjonction de disjonctions.

Exemple :

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

Chaque groupe relié par OU est appelé une clause.

L'ensemble est parfois appelé :

produit de sommes

Littéral logique

Un littéral est une variable ou sa négation.

Les expressions suivantes sont des littéraux :

NON A

NON B

Les formes normales sont construites à partir de littéraux.

Minterme

Un minterme est une conjonction contenant chaque variable exactement une fois, directement ou sous forme niée.

Pour les variables :

A
B
C

un minterme possible est :

A ET NON B ET C

Il est vrai pour une seule affectation précise.

Maxterme

Un maxterme est une disjonction contenant chaque variable exactement une fois, directement ou sous forme niée.

Exemple :

A OU NON B OU C

Un maxterme est faux pour une seule affectation précise.

Forme canonique

Une forme canonique représente une fonction à l'aide de tous ses mintermes vrais ou de tous ses maxtermes faux.

La forme canonique disjonctive utilise les lignes où la fonction vaut :

La forme canonique conjonctive utilise les lignes où la fonction vaut :

Fonction booléenne

Une fonction booléenne de n variables est une application :

F : {0,1}ⁿ → {0,1}

Elle reçoit un vecteur de `n` valeurs booléennes et produit une seule valeur booléenne.

Par exemple :

F(A,B,C)
=
(A ET B) OU NON C

est une fonction de trois variables.

Nombre de fonctions booléennes

Avec n variables, il existe :

2ⁿ

affectations possibles.

Pour chacune de ces affectations, la sortie peut être `0` ou `1`.

Le nombre total de fonctions booléennes différentes est donc :

2^(2ⁿ)

Exemple avec deux variables

Pour deux variables :

A
B

il existe :

2² = 4

lignes dans la table de vérité.

Chaque ligne peut recevoir une sortie `0` ou `1`.

Le nombre de fonctions différentes est donc :

2⁴ = 16

Expression et fonction

Une même fonction booléenne peut être représentée par plusieurs expressions différentes.

Par exemple :

A ET (A OU B)

et :

représentent la même fonction.

L'expression est la représentation syntaxique.

La fonction est le comportement logique produit par cette expression.

Longueur d'une expression

La longueur d'une expression peut être mesurée par :

le nombre de variables ;
le nombre de littéraux ;
le nombre d'opérateurs ;
le nombre de parenthèses ;
la profondeur d'imbrication ;
le nombre de sous-expressions.

Ces mesures peuvent être utilisées pour estimer la complexité d'évaluation ou de simplification.

Profondeur d'une expression

La profondeur correspond au nombre maximal de niveaux imbriqués.

Par exemple :

A ET B

possède une faible profondeur.

L'expression :

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

possède une profondeur beaucoup plus grande.

Une profondeur excessive peut nuire à la lisibilité.

Évaluation récursive

Une expression peut être évaluée récursivement.

MODULE Évaluer(Expression)

   SI Expression est une constante ALORS
      RETOURNER sa valeur
   FIN SI

   SI Expression est une variable ALORS
      RETOURNER la valeur affectée
   FIN SI

   SI Expression est NON ALORS
      RETOURNER
         NON Évaluer(opérande)
   FIN SI

   SI Expression est ET ALORS
      RETOURNER
         Évaluer(gauche)
         ET
         Évaluer(droite)
   FIN SI

   SI Expression est OU ALORS
      RETOURNER
         Évaluer(gauche)
         OU
         Évaluer(droite)
   FIN SI

Cette méthode correspond à l'évaluation d'un arbre syntaxique.

Court-circuit

L'évaluation en court-circuit évite d'évaluer une sous-expression lorsque le résultat est déjà déterminé.

Pour :

A ET B

si :

A = FAUX

le résultat est forcément faux.

Il n'est pas nécessaire d'évaluer `B`.

Court-circuit du OU

Pour :

A OU B

si :

A = VRAI

le résultat est forcément vrai.

La sous-expression `B` peut être ignorée.

Exemple de protection

Objet ≠ NUL
ET
Objet.EstValide()

Si :

Objet = NUL

la seconde expression ne doit pas être évaluée.

Le court-circuit empêche alors un accès invalide à l'objet.

Effets secondaires

Une sous-expression peut contenir un appel modifiant l'état du programme.

Condition
ET
ModifierÉtat()

Si Condition est fausse, la fonction peut ne jamais être appelée.

Il est généralement préférable d'éviter les effets secondaires cachés dans les expressions booléennes.

Expression pure

Une expression est dite pure lorsque son évaluation ne modifie aucun état observable.

Par exemple :

Âge >= 18
ET
CompteActif

est généralement pure.

Une expression pure retourne toujours le même résultat pour les mêmes valeurs d'entrée.

Expression avec effet secondaire

L'expression suivante peut modifier une variable :

Compteur++ > 10

Son évaluation change la valeur de `Compteur`.

Lorsque ce type d'expression est combiné avec un court-circuit, le comportement peut devenir difficile à comprendre.

Expressions dans les conditions

Les structures conditionnelles utilisent une expression booléenne pour sélectionner un chemin d'exécution.

SI ExpressionBooléenne ALORS
BlocVrai
SINON
BlocFaux
FIN SI

Un seul des deux blocs est exécuté selon le résultat.

Exemple de condition simple

SI Âge >= 18 ALORS
AFFICHER "Personne majeure"
FIN SI

L'expression :

Âge >= 18

est évaluée avant l'exécution du bloc.

Exemple de condition composée

SI
   Âge >= 18
   ET CompteActif
   ET NON CompteSuspendu
ALORS

   AutoriserAccès

FIN SI

Les trois conditions doivent être vraies.

Expressions dans les boucles

Une boucle peut continuer tant qu'une expression demeure vraie.

TANT QUE
   Position < Taille
   ET NON Trouvé
FAIRE

   ExaminerÉlément
   Position ← Position + 1

FIN TANT QUE

La condition est réévaluée avant chaque nouvelle itération.

Boucle jusqu'à une condition

Certaines boucles se terminent lorsqu'une expression devient vraie.

RÉPÉTER
LireValeur
JUSQU'À
ValeurValide
FIN RÉPÉTER

La signification exacte dépend de la syntaxe du langage.

Expressions dans les filtres

Un filtre conserve uniquement les éléments satisfaisant une expression booléenne.

Âge >= 18
ET
CompteActif

Dans une collection, chaque élément est évalué séparément.

Seuls ceux pour lesquels l'expression retourne vrai sont conservés.

Exemple SQL



SELECT *

FROM Utilisateurs

WHERE Age >= 18

  AND CompteActif = 1

  AND CompteSuspendu = 0;

La clause WHERE contient une expression logique appliquée à chaque ligne.

Logique ternaire de SQL

En présence de NULL, SQL utilise généralement trois valeurs :

TRUE
FALSE
UNKNOWN

Une expression produisant `UNKNOWN` n'est pas traitée comme vraie par une clause WHERE.

Cela distingue SQL de l'algèbre de Boole classique à deux valeurs.

Expressions dans les assertions

Une assertion vérifie qu'une expression booléenne est vraie.

ASSERTION(
Indice >= 0
ET Indice < Taille
)

Si l'expression est fausse, le programme peut interrompre l'exécution ou signaler une erreur.

Préconditions

Une précondition est une expression devant être vraie avant l'exécution d'une opération.

Diviseur ≠ 0

Cette précondition doit être satisfaite avant une division.

Les préconditions décrivent les valeurs acceptables des paramètres.

Postconditions

Une postcondition est une expression devant être vraie après l'exécution d'une opération.

Par exemple, après un tri croissant :

TableauEstTrié(Tableau)

La postcondition décrit le résultat garanti par l'algorithme.

Invariants

Un invariant est une expression qui demeure vraie pendant une partie déterminée de l'exécution.

Un invariant de boucle peut être :

0 <= Position
ET
Position <= Taille

Il doit être vrai avant et après chaque itération.

Expressions de validation

Une validation combine plusieurs exigences.

NomNonVide
ET
CourrielValide
ET
MotDePasseAssezLong
ET
ConditionsAcceptées

Le formulaire est valide uniquement lorsque toutes les sous-expressions sont vraies.

Expressions d'autorisation

Une règle d'accès peut être représentée par :

UtilisateurAuthentifié
ET
CompteActif
ET
NON CompteSuspendu
ET
(
EstAdministrateur
OU PossèdePermissionÉcriture
)

Les parenthèses garantissent que les rôles possibles sont regroupés correctement.

Risque d'une expression mal groupée

Considérons :

CompteActif
ET EstAdministrateur
OU EstGestionnaire

Cette expression est généralement interprétée comme :

(
CompteActif
ET EstAdministrateur
)
OU EstGestionnaire

Un gestionnaire pourrait donc être autorisé même avec un compte inactif.

Expression correcte

Si le compte doit être actif pour tous les rôles, il faut écrire :

CompteActif
ET
(
EstAdministrateur
OU EstGestionnaire
)

La structure logique correspond alors à la règle métier.

Décomposition d'une expression

Une expression longue peut être divisée en variables intermédiaires.

CompteUtilisable ←
   CompteActif
   ET NON CompteSuspendu

RôleAutorisé ←
   EstAdministrateur
   OU EstGestionnaire

AccèsAutorisé ←
   UtilisateurAuthentifié
   ET CompteUtilisable
   ET RôleAutorisé

Cette forme facilite la lecture et les tests.

Nommer les sous-expressions

Un nom descriptif explique le rôle logique d'une sous-expression.

Par exemple :

EstMajeur ← Âge >= 18

PossèdeAccès ←
EstAdministrateur
OU PossèdePermission

La condition finale devient plus proche du langage naturel.

Expression positive

Une formulation positive est généralement plus facile à comprendre.

Préférer :

CompteActif

à :

NON CompteInactif

Préférer :

FichierExiste

à :

NON FichierAbsent

Double négation

Une double négation peut être simplifiée :

NON NON A = A

Dans un programme, une expression comme :

NON EstNonAutorisé

devrait généralement être reformulée en :

EstAutorisé

Comparaison explicite avec vrai

L'écriture :

SI CompteActif = VRAI ALORS

est souvent redondante.

On peut généralement écrire :

SI CompteActif ALORS

La variable constitue déjà une expression booléenne.

Comparaison explicite avec faux

Au lieu de :

SI CompteActif = FAUX ALORS

on peut écrire :

SI NON CompteActif ALORS

Cette forme exprime directement la négation.

Cas des booléens nullables

Une variable pouvant prendre les valeurs :

VRAI
FAUX
NUL

nécessite parfois une comparaison explicite.

Réponse = VRAI

est différent de :

Réponse ≠ FAUX

car la seconde expression peut traiter `NUL` différemment selon le langage.

Conversion implicite

Certains langages convertissent automatiquement d'autres types en valeurs logiques.

Ils peuvent considérer comme faux :

0
""
NUL
Tableau vide

selon leurs propres règles.

Ces conversions ne font pas partie de l'algèbre de Boole mathématique classique.

Valeurs vraies et fausses implicites

Dans les langages dynamiques, on parle souvent de valeurs :

truthy

et :

falsy

Une valeur truthy est interprétée comme vraie dans une condition.

Une valeur falsy est interprétée comme fausse.

Les règles exactes varient fortement selon les langages.

Chaîne « false »

La chaîne :

"false"

n'est pas nécessairement interprétée comme fausse.

Dans plusieurs langages, elle est considérée comme vraie parce qu'elle n'est pas vide.

Elle doit être analysée explicitement pour être convertie en booléen.

Expression bit à bit

Une expression bit à bit applique une opération à chaque position binaire.

Par exemple :

1100 ET 1010
=
1000

Cette opération produit une valeur numérique binaire.

Elle doit être distinguée de la conjonction logique portant sur deux conditions globales.

Transformation en booléen

Le résultat d'une opération bit à bit peut être transformé en expression booléenne.

(Permissions ET MasqueÉcriture) ≠ 0

L'opération ET bit à bit produit une valeur numérique.

La comparaison avec zéro produit ensuite une valeur booléenne.

Expression conditionnelle

Certains langages possèdent un opérateur conditionnel :

Condition
?
ValeurSiVrai
:
ValeurSiFaux

La condition est une expression booléenne.

L'expression conditionnelle complète peut toutefois retourner un autre type, comme un entier ou une chaîne.

Exemple conditionnel

Message ←
   CompteActif
   ?
   "Compte actif"
   :
   "Compte inactif"

L'expression `CompteActif` sélectionne l'une des deux chaînes.

Compilation d'une expression

Un compilateur analyse une expression en plusieurs étapes :

Analyse lexicale
Analyse syntaxique
Vérification des types
Construction de l'arbre syntaxique
Simplification éventuelle
Génération du code

La priorité des opérateurs est appliquée lors de l'analyse syntaxique.

Vérification de type

Un opérateur booléen exige normalement des opérandes compatibles.

Par exemple :

A ET B

nécessite généralement que `A` et `B` puissent être interprétés comme des valeurs logiques.

Un langage fortement typé peut refuser :

10 ET "Bonjour"

Repliement de constantes

Le compilateur peut calculer à l'avance les expressions constantes.

Par exemple :

VRAI ET FAUX

peut être remplacé pendant la compilation par :

FAUX

Cette optimisation est appelée repliement de constantes.

Élimination de code mort

Une condition connue comme toujours fausse peut rendre un bloc inaccessible.

SI FAUX ALORS
ExécuterFonction
FIN SI

Le compilateur peut supprimer ce code.

De même, une condition toujours vraie peut permettre de simplifier le flux d'exécution.

Expressions et circuits logiques

Chaque expression booléenne peut être représentée par un circuit composé de portes logiques.

Pour :

F =
(A ET B)
OU
NON C

le circuit contient :

une porte ET pour `A` et `B` ;
une porte NON pour `C` ;
une porte OU combinant les deux résultats.

Coût matériel

Dans un circuit, la complexité d'une expression peut être mesurée par :

le nombre de portes ;
le nombre d'entrées ;
la profondeur du circuit ;
le délai de propagation ;
la consommation électrique ;
la surface occupée.

La simplification booléenne peut réduire ces coûts.

Expression NAND

Toute expression booléenne peut être transformée pour utiliser uniquement l'opérateur NAND.

Par exemple :

NON A
=
A NAND A

et :

A ET B
=
NON(A NAND B)

Le NAND est donc fonctionnellement complet.

Expression NOR

L'opérateur NOR est également fonctionnellement complet.

NON A
=
A NOR A

et les autres opérations peuvent être construites à partir de combinaisons de NOR.

Cette propriété est importante dans la conception de circuits.

Diagramme de décision binaire

Une expression peut être représentée par un diagramme de décision binaire.

Chaque noeud teste une variable.

Chaque branche représente une valeur :

ou :

Les feuilles contiennent le résultat final.

Exemple conceptuel de décision

Pour :

A ET B

le diagramme teste d'abord `A`.

Si :

A = 0

le résultat est immédiatement `0`.

Si :

A = 1

le diagramme teste ensuite `B`.

Cette structure reflète le court-circuit.

Expressions dans les moteurs de recherche

Les moteurs de recherche peuvent accepter des expressions comme :

Pascal ET compilateur

Pascal OU Delphi

Pascal ET NON Delphi

Ces expressions servent à combiner des critères documentaires.

Expressions dans les règles métier

Une règle métier peut être traduite en expression logique.

Règle :

Un dossier est admissible lorsque
les deux parties ont demandé
la médiation et que le dossier
n'est pas fermé.

Expression :

DemandeMédiationDemandeur
ET
DemandeMédiationDéfendeur
ET
NON DossierFermé

Expressions dans les systèmes experts

Une règle peut prendre la forme :

SI
   TempératureÉlevée
   ET PressionFaible
ALORS
   RisqueÉlevé
FIN SI

La condition de la règle est une expression booléenne.

Le moteur d'inférence l'évalue à partir des faits disponibles.

Expressions dans les automates

Une transition d'état peut être déclenchée par :

BoutonAppuyé
ET
PorteFermée
ET
NON ArrêtUrgence

L'expression détermine si la transition est autorisée.

Expressions dans les graphes

Certaines propriétés de graphes sont booléennes :

EstConnexe(Graphe)

ExisteChemin(A,B)

EstBiparti(Graphe)

Ces expressions peuvent être combinées pour définir des conditions algorithmiques.

Expressions en théorie des ensembles

Une expression booléenne peut être interprétée par des opérations sur les ensembles.

Algèbre de Boole	Ensembles
A ET B	A ∩ B
A OU B	A ∪ B
NON A	Complément de A
FAUX	Ensemble vide
VRAI	Ensemble universel

Une expression logique correspond alors à une expression ensembliste.

Exemple ensembliste

L'expression :

A ET NON B

correspond à :

A ∩ B^c

Elle représente les éléments appartenant à `A`, mais pas à `B`.

Algorithme d'évaluation

MODULE ÉvaluerExpression(A,B,C)

   Partie1 ←
      A ET B

   Partie2 ←
      NON C

   Résultat ←
      Partie1 OU Partie2

   RETOURNER Résultat

Cette décomposition rend explicite l'ordre de calcul.

Algorithme de validation

MODULE ValiderUtilisateur(Âge,CompteActif,CompteSuspendu,CourrielVérifié)

   EstMajeur ←
      Âge >= 18

   CompteUtilisable ←
      CompteActif
      ET NON CompteSuspendu

   Résultat ←
      EstMajeur
      ET CompteUtilisable
      ET CourrielVérifié

   RETOURNER Résultat

Exemple en Pascal



Program ExpressionsBooleennes;

 
var

  Age: Integer;

  CompteActif: Boolean;

  CompteSuspendu: Boolean;

  CourrielVerifie: Boolean;

  AccesAutorise: Boolean;

 
BEGIN

  Age := 25;

  CompteActif := True;

  CompteSuspendu := False;

  CourrielVerifie := True;

 
  AccesAutorise :=

    (Age >= 18)

    and CompteActif

    and not CompteSuspendu

    and CourrielVerifie;

 
  if AccesAutorise then

    WriteLn('Accès autorisé')

  else

    WriteLn('Accès refusé');

END.

Analyse de l'exemple Pascal

L'expression contient :

une comparaison numérique ;
deux variables booléennes positives ;
une négation ;
plusieurs conjonctions.

La variable :

AccesAutorise

reçoit vrai uniquement si toutes les conditions sont satisfaites.

Exemple en Java


public final class ExpressionsBooleennes {
 
    private ExpressionsBooleennes() {
    }
 
    public static boolean autoriserAcces(
        int age,
        boolean compteActif,
        boolean compteSuspendu,
        boolean courrielVerifie,
        boolean administrateur
    ) {
        boolean estMajeur =
            age >= 18;
 
        boolean compteUtilisable =
            compteActif
            && !compteSuspendu;
 
        boolean conditionNormale =
            estMajeur
            && compteUtilisable
            && courrielVerifie;
 
        return administrateur
            || conditionNormale;
    }
 
    public static void main(String[] args) {
        boolean resultat = autoriserAcces(
            25,
            true,
            false,
            true,
            false
        );
 
        System.out.println(
            "Accès autorisé : "
            + resultat
        );
    }
}

Analyse de l'exemple Java

L'expression finale est :

Administrateur
OU
(
   EstMajeur
   ET CompteUtilisable
   ET CourrielVérifié
)

Un administrateur est autorisé directement.

Un autre utilisateur doit satisfaire toutes les conditions normales.

Cette règle doit être confirmée, car elle permettrait aussi à un administrateur dont le compte est suspendu d'être autorisé.

Variante plus sécuritaire

Si tous les utilisateurs doivent posséder un compte utilisable, il faut écrire :


return compteUtilisable
    && (
        administrateur
        || (
            estMajeur
            && courrielVerifie
        )
    );

La position des parenthèses modifie directement la règle d'autorisation.

Exemple en C



#include <stdbool.h>

 
bool autoriser_acces(

    int age,

    bool compte_actif,

    bool compte_suspendu,

    bool courriel_verifie

)

{

    return

        age >= 18

        && compte_actif

        && !compte_suspendu

        && courriel_verifie;

}

Exemple en C#



static bool AutoriserAcces(

    int age,

    bool compteActif,

    bool compteSuspendu,

    bool courrielVerifie)

{

    return age >= 18

        && compteActif

        && !compteSuspendu

        && courrielVerifie;

}

Exemple en Visual Basic



Function AutoriserAcces(

    Age As Integer,

    CompteActif As Boolean,

    CompteSuspendu As Boolean,

    CourrielVerifie As Boolean

) As Boolean

 
    Return

        Age >= 18 AndAlso

        CompteActif AndAlso

        Not CompteSuspendu AndAlso

        CourrielVerifie

 
End Function

Exemple en Python



def autoriser_acces(

    age,

    compte_actif,

    compte_suspendu,

    courriel_verifie,

):

    return (

        age >= 18

        and compte_actif

        and not compte_suspendu

        and courriel_verifie

    )

Exemple en JavaScript



def autoriser_acces(

    age,

    compte_actif,

    compte_suspendu,

    courriel_verifie,

):

    return (

        age >= 18

        and compte_actif

        and not compte_suspendu

        and courriel_verifie

    )

Génération d'une table de vérité

MODULE GénérerTableVérité(n)

   NombreLignes ← 2ⁿ

   POUR Ligne ← 0 JUSQU'À NombreLignes-1
      POUR Variable ← 0 JUSQU'À n-1
         Valeur[Variable] ←
            (
               Ligne
               DÉCALÉ À DROITE
               Variable
            )
            ET 1
      FIN POUR

      Résultat ← ÉvaluerExpression(Valeur)

      AFFICHER
         Valeur,
         Résultat

FIN POUR

Chaque numéro de ligne fournit une combinaison binaire différente.

Complexité d'une table de vérité

Une expression contenant `n` variables possède :

2ⁿ

affectations possibles.

Si son évaluation demande :

opérations, la génération complète de la table possède approximativement une complexité :

O(m × 2ⁿ)

La méthode devient rapidement coûteuse lorsque `n` augmente.

Explosion combinatoire

Avec :

n = 10

on obtient :

2¹⁰ = 1 024

lignes.

Avec :

n = 20

on obtient :

2²⁰ = 1 048 576

lignes.

Avec :

n = 30

on dépasse un milliard d'affectations.

Méthodes avancées

Pour éviter l'énumération complète, on peut utiliser :

la simplification algébrique ;
les cartes de Karnaugh ;
Quine-McCluskey ;
les diagrammes de décision binaires ;
les solveurs SAT ;
la propagation de contraintes ;
les formes normales ;
les méthodes symboliques.

Ces techniques représentent ou analysent les expressions plus efficacement dans certains cas.

Bonnes pratiques

Pour écrire des expressions booléennes lisibles et fiables, il est recommandé de :

utiliser des noms de variables exprimant une condition ;
préférer les formulations positives ;
employer des parenthèses explicites ;
éviter les doubles négations ;
décomposer les expressions longues ;
ne pas comparer inutilement un booléen avec `VRAI` ;
tenir compte du court-circuit ;
éviter les effets secondaires ;
distinguer la logique booléenne des opérations bit à bit ;
documenter la règle métier plutôt que la syntaxe ;
tester les combinaisons critiques ;
employer une énumération lorsque plus de deux états sont nécessaires.

Erreurs fréquentes

Les erreurs courantes comprennent :

confondre affectation et comparaison ;
oublier la priorité des opérateurs ;
omettre des parenthèses importantes ;
utiliser un OU au lieu d'un ET ;
confondre OU inclusif et XOR ;
nier seulement une variable au lieu de toute l'expression ;
comparer une chaîne `"false"` comme si elle était booléenne ;
confondre `FAUX`, `NUL` et `INCONNU` ;
utiliser un opérateur bit à bit à la place d'un opérateur logique ;
placer un effet secondaire dans une sous-expression court-circuitée ;
créer une condition toujours vraie ou toujours fausse ;
employer plusieurs booléens pouvant produire des états incohérents.

Tableau récapitulatif

Notion	Description
Expression booléenne	Expression retournant vrai ou faux
Expression atomique	Valeur ou test non composé
Expression composée	Combinaison de sous-expressions
Opérande	Valeur sur laquelle agit un opérateur
Négation	Inverse une valeur logique
Conjonction	Exige que toutes les conditions soient vraies
Disjonction	Exige qu'au moins une condition soit vraie
Prédicat	Fonction ou test retournant un booléen
Affectation de vérité	Valeurs attribuées aux variables
Tautologie	Expression toujours vraie
Contradiction	Expression toujours fausse
Contingence	Expression parfois vraie et parfois fausse
Satisfaisabilité	Existence d'au moins une affectation vraie
Équivalence	Même résultat pour toutes les affectations
Sous-expression	Partie évaluée d'une expression plus grande
Court-circuit	Arrêt anticipé de l'évaluation
Forme normale	Représentation logique standardisée

Avantages

Les expressions booléennes présentent plusieurs avantages :

elles représentent précisément les conditions et les décisions ;
elles peuvent être composées à partir de règles simples ;
elles s'intègrent directement aux structures de contrôle ;
elles permettent de formaliser les règles métier ;
elles peuvent être évaluées automatiquement ;
elles peuvent être simplifiées grâce aux lois booléennes ;
elles peuvent être représentées par des tables de vérité ;
elles décrivent directement des circuits numériques ;
elles facilitent la validation, le filtrage et le contrôle d'accès ;
elles servent de base à la logique formelle et aux solveurs SAT ;
elles permettent de vérifier l'équivalence de plusieurs formulations.

Limites et précautions

Les expressions booléennes possèdent certaines limites :

leur lisibilité diminue rapidement lorsqu'elles deviennent longues ;
une erreur de parenthèses peut modifier complètement leur sens ;
le nombre d'affectations augmente exponentiellement avec les variables ;
les conversions implicites varient selon les langages ;
le court-circuit peut empêcher certains appels d'être exécutés ;
les effets secondaires rendent l'évaluation difficile à prévoir ;
les valeurs nulles ou inconnues nécessitent parfois une logique à trois valeurs ;
une expression techniquement correcte peut ne pas correspondre à la règle métier ;
la simplification minimale peut être difficile pour les grandes fonctions ;
plusieurs expressions différentes peuvent représenter la même fonction ;
les opérations logiques et bit à bit ne sont pas interchangeables.

Remarque

Les expressions booléennes constituent le langage mathématique des décisions informatiques. Elles transforment des propriétés, des comparaisons et des états en une valeur unique indiquant si une condition est satisfaite. Cette valeur peut ensuite contrôler l'exécution d'une instruction, la poursuite d'une boucle, la sélection d'un enregistrement ou l'autorisation d'une opération.

Une expression simple peut se limiter à une variable ou à une comparaison. Une expression complexe peut contenir de nombreuses sous-expressions, des négations, des parenthèses et plusieurs niveaux de priorité. Sa compréhension exige alors une structure claire, des noms significatifs et une décomposition logique correspondant précisément à la règle représentée.

L'étude des expressions booléennes prépare aux tables de vérité, aux équivalences logiques, aux lois de De Morgan, aux formes normales, aux mintermes, aux maxtermes, aux méthodes de simplification et à la conception de circuits logiques. Elle constitue ainsi une étape essentielle dans l'apprentissage de l'algèbre de Boole et de son application aux langages de programmation.

Dernière mise à jour : Jeudi, le 16 juillet 2026