Matrices booléennes : somme et produit booléens

Une matrice booléenne est une matrice dont tous les coefficients valent 0 ou 1 (faux ou vrai). On la combine avec la somme booléenne, case par case avec la règle 1 + 1 = 1, et avec le produit booléen, ligne par colonne avec les opérations « ou » et « et ». Le produit ordinaire compte des liaisons, le produit booléen dit seulement si une liaison existe. Ce chapitre définit ces deux opérations, les applique aux droits d'accès et aux jointures, et fait le lien avec les graphes.

Le calcul booléen, rappel

En algèbre de Boole, les valeurs sont 0 (faux) et 1 (vrai). La somme booléenne ⊕ est le « ou », le produit booléen ⊗ est le « et » :

La seule différence avec le calcul ordinaire est 1 ⊕ 1 = 1 : « vrai ou vrai » reste vrai. Le reste du calcul booléen (lois de De Morgan, simplifications) est dans le cours de logique et d'algèbre de Boole. Les manuels écrivent aussi + et ×, ou ∨ et ∧, en précisant que le calcul est booléen ; ce cours utilise ⊕ et ⊗, comme le cours de graphes.

La somme booléenne de deux matrices

A = [ 1  0  1 ]      B = [ 0  1  1 ]      A ⊕ B = [ 1  1  1 ]
    [ 0  0  1 ]          [ 0  0  0 ]              [ 0  0  1 ]
    [ 1  0  0 ]          [ 1  1  0 ]              [ 1  1  0 ]

Les cases (1, 3) et (3, 1) valent 1 dans les deux matrices : la somme booléenne y vaut 1, pas 2. La somme booléenne sert à réunir deux informations : si A dit qui a accès à quoi par un premier moyen et B par un second, A ⊕ B dit qui a accès à quoi par l'un ou l'autre.

Le produit booléen de deux matrices

Avec les matrices A et B ci-dessus, la case (1, 2) de A ⊗ B est la ligne 1 de A, (1, 0, 1), « fois » la colonne 2 de B, (1, 0, 1) : pour k = 1, a₁₁ = 1 et b₁₂ = 1, la case vaut donc 1. En faisant de même pour toutes les cases :

A ⊗ B = [ 1  1  1 ]        alors que     A × B = [ 1  2  1 ]
        [ 1  1  0 ]                              [ 1  1  0 ]
        [ 0  1  1 ]                              [ 0  1  1 ]

Le produit ordinaire A × B a un 2 en case (1, 2) : il y a deux valeurs de k qui conviennent (k = 1 et k = 3). Le produit booléen ne garde que l'information « il en existe au moins un ».

Comme le produit ordinaire, le produit booléen n'est pas commutatif : ici, B ⊗ A = [ 1 0 1 ; 0 0 0 ; 1 0 1 ], très différent de A ⊗ B. La ligne 2 de B est nulle, donc la ligne 2 de B ⊗ A l'est aussi.

Une application : les droits effectifs dans Active Directory

Chez Sorbier Logistique, les droits sur les partages du serveur de fichiers sont donnés à des groupes, jamais directement aux comptes (principe AGDLP, et calcul des droits effectifs). Pour savoir à quels partages un salarié accède, il faut combiner deux informations : ses groupes, et les partages de chaque groupe. On ne s'intéresse ici qu'à l'existence d'un accès (lecture ou modification), pas à son niveau.

La matrice U dit qui est membre de quel groupe (lignes : Hélène Garnier, Julie Lefèvre, Karim Morel, Sofiane Benali ; colonnes : GG_Direction, GG_Comptables, GG_Resp_Comptable, GG_Commerciaux). La matrice G dit quel groupe accède à quel partage (lignes : les mêmes groupes ; colonnes : les partages Compta, Paie, Commercial, Direction). Karim Morel, responsable comptable, est membre de GG_Resp_Comptable et, comme les comptables, de GG_Comptables (c'est le cas étudié dans le cours Windows Server avec les stratégies de mot de passe affinées).

         Dir Cpt Resp Com                  Compta Paie Comm Dir
U = [ 1   0   0   0 ]  Hélène       G = [   1     1    1    1 ]  GG_Direction
    [ 0   1   0   0 ]  Julie            [   1     0    0    0 ]  GG_Comptables
    [ 0   1   1   0 ]  Karim            [   1     1    0    0 ]  GG_Resp_Comptable
    [ 0   0   0   1 ]  Sofiane          [   0     0    1    0 ]  GG_Commerciaux

Un salarié accède à un partage s'il existe un groupe dont il est membre et qui accède à ce partage : c'est exactement la définition du produit booléen. Les droits effectifs sont donc U ⊗ G :

                Compta Paie Comm Dir
U ⊗ G = [   1     1    1    1 ]  Hélène
        [   1     0    0    0 ]  Julie
        [   1     1    0    0 ]  Karim
        [   0     0    1    0 ]  Sofiane

Le produit ordinaire U × G donne la même matrice, sauf en ligne Karim, colonne Compta, où il vaut 2 : Karim accède à Compta par deux groupes. Le produit booléen dit « il y accède », le produit ordinaire « par combien de chemins ». Les deux informations sont utiles à l'administrateur : un accès obtenu par deux groupes ne disparaît pas si l'on retire Karim d'un seul d'entre eux, ce qu'il faut savoir avant de croire qu'on lui a retiré un droit.

Une autre application : une jointure SQL

Dans la base parc du cours SQL, la table poste dit quel employé utilise quel poste, et la table installation quel logiciel est installé sur quel poste. Pour quatre employés, cinq postes et quatre logiciels, cela donne deux matrices booléennes : E (employés × postes) et P (postes × logiciels).

       PC1 PC3 PC4 PC7 PC15               M365  LO  Sage  Odoo
E = [ 1   0   0   0   0 ]  Julie      P = [  1    0    1     0 ]  PC-0001
    [ 0   1   0   0   0 ]  Karim          [  1    0    1     1 ]  PC-0003
    [ 0   0   1   0   1 ]  Sofiane        [  1    0    0     1 ]  PC-0004
    [ 0   0   0   1   0 ]  Nadia          [  0    1    0     1 ]  PC-0007
                                          [  1    0    0     1 ]  PC-0015

E ⊗ P dit quels logiciels chaque employé a sous la main, sur au moins un de ses postes :

                M365  LO  Sage  Odoo
E ⊗ P = [  1    0    1     0 ]  Julie
        [  1    0    1     1 ]  Karim
        [  1    0    0     1 ]  Sofiane
        [  0    1    0     1 ]  Nadia

Sofiane a deux postes, qui portent tous les deux Microsoft 365 et Odoo : dans E × P, sa ligne vaut (2, 0, 0, 2). C'est la différence entre une jointure avec et sans DISTINCT : la requête qui joint employe, poste, installation et logiciel renvoie deux fois le couple (Benali, Odoo), un par poste ; avec SELECT DISTINCT, elle ne le renvoie qu'une fois. Le produit booléen, c'est une jointure suivie d'un DISTINCT ; le produit ordinaire, c'est une jointure suivie d'un COUNT(*) par couple. Les jointures elles-mêmes sont expliquées dans le chapitre Jointures SQL.

Les puissances booléennes et les graphes

Pour une matrice booléenne carrée M, la puissance booléenne M^[p] est le produit booléen de p matrices égales à M. Si M est la matrice d'adjacence d'un graphe orienté, M^[p] a un 1 en case (i, j) s'il existe au moins un chemin de longueur p de i vers j, alors que la puissance ordinaire Mᵖ en donne le nombre (chapitre 4).

Exemple : un paquet logiciel A dépend des paquets B et C, qui dépendent tous les deux du paquet D. Dans l'ordre A, B, C, D :

M = [ 0  1  1  0 ]      M² = [ 0  0  0  2 ]      M^[2] = [ 0  0  0  1 ]
    [ 0  0  0  1 ]           [ 0  0  0  0 ]              [ 0  0  0  0 ]
    [ 0  0  0  1 ]           [ 0  0  0  0 ]              [ 0  0  0  0 ]
    [ 0  0  0  0 ]           [ 0  0  0  0 ]              [ 0  0  0  0 ]

M² compte deux chemins de longueur 2 de A vers D (par B et par C) ; M^[2] dit seulement que A dépend indirectement de D. La somme booléenne M ⊕ M^[2] ⊕ … ⊕ M^[n], où n est le nombre de sommets, signale tous les couples reliés par un chemin, quelle que soit sa longueur : c'est la fermeture transitive du graphe. Ici, M^[3] est nulle et

M ⊕ M^[2] = [ 0  1  1  1 ]
            [ 0  0  0  1 ]
            [ 0  0  0  1 ]
            [ 0  0  0  0 ]

Installer A impose d'installer B, C et D ; installer B ou C impose D. C'est le calcul que fait un gestionnaire de paquets comme apt. La fermeture transitive, sa lecture et l'algorithme de Roy-Warshall, plus rapide, sont détaillés dans le cours de graphes : puissances booléennes et fermeture transitive.

En Python

Le produit booléen s'écrit comme le produit ordinaire (chapitre 8), avec or et and à la place de + et *. La fonction any de Python renvoie True dès qu'un élément est vrai, ce qui traduit directement « il existe un k » :

def somme_booleenne(A, B):
    return [[1 if A[i][j] or B[i][j] else 0 for j in range(len(A[0]))]
            for i in range(len(A))]


def produit_booleen(A, B):
    p = len(B)
    return [[1 if any(A[i][k] and B[k][j] for k in range(p)) else 0
             for j in range(len(B[0]))]
            for i in range(len(A))]


U = [[1, 0, 0, 0], [0, 1, 0, 0], [0, 1, 1, 0], [0, 0, 0, 1]]
G = [[1, 1, 1, 1], [1, 0, 0, 0], [1, 1, 0, 0], [0, 0, 1, 0]]
print(produit_booleen(U, G))

[[1, 1, 1, 1], [1, 0, 0, 0], [1, 1, 0, 0], [0, 0, 1, 0]]

Exercices