La logique en informatique : conditions, SQL, masques et bits

L'algèbre de Boole est partout dans le travail d'un informaticien : dans les conditions if et while d'un programme, dans les clauses WHERE d'une requête SQL, dans le calcul d'une adresse réseau (un ET logique bit à bit entre l'adresse IP et le masque) et dans les droits d'accès codés sur des bits. Ce chapitre fait le lien entre le cours de mathématiques et ces usages, avec des exemples en Python, en SQL et en réseau que tu retrouveras en SLAM comme en SISR.

Les opérateurs logiques des langages

Ces langages suivent tous la priorité du chapitre 1 : non, puis et, puis ou.

L'évaluation paresseuse (court-circuit). Les opérateurs and/&& et or/|| évaluent leur opérande de gauche d'abord, et ne calculent celui de droite que si c'est nécessaire. C'est l'application directe de deux règles de Boole : 0 · b = 0 (si la gauche d'un ET est fausse, le résultat est faux) et 1 + b = 1 (si la gauche d'un OU est vraie, le résultat est vrai). On s'en sert pour protéger un test :

# Si utilisateur vaut None, la partie droite n'est jamais évaluée : pas d'erreur.
if utilisateur is not None and utilisateur.actif:
    ouvrir_session(utilisateur)

L'ordre des deux conditions compte : inversées, elles provoqueraient une erreur quand utilisateur vaut None. Le ET logique est commutatif ; son évaluation dans un programme ne l'est pas.

Simplifier une condition avec De Morgan

Les conditions écrites « au fil de la pensée » sont souvent plus compliquées qu'il ne faut. Les lois de l'algèbre de Boole les rendent lisibles.

# Avant : une négation de toute la condition, difficile à lire
if not (age >= 18 and inscrit):
    refuser()

# Après De Morgan : non(a et b) = non a ou non b
if age < 18 or not inscrit:
    refuser()

Une boucle de recherche s'arrête quand on a trouvé ou qu'on est arrivé au bout. Elle continue donc tant que non(trouvé ou fin), c'est-à-dire tant que non trouvé et non fin :

i, trouve = 0, False
while not trouve and i < len(tickets):   # ≡ not (trouve or i >= len(tickets))
    if tickets[i]["statut"] == "urgent":
        trouve = True
    else:
        i += 1

D'autres simplifications fréquentes :

Conditions SQL : AND, OR, NOT et NULL

Dans une clause WHERE, la priorité NOT > AND > OR crée le piège classique déjà vu : WHERE statut = 'ouvert' OR statut = 'en cours' AND priorite = 'haute' se lit statut = 'ouvert' OR (statut = 'en cours' AND priorite = 'haute'). Mets toujours des parenthèses autour d'un OR combiné à un AND.

Les lois de De Morgan servent aussi en SQL : « les postes qui ne sont ni des portables ni des tablettes » s'écrit indifféremment

SELECT * FROM poste WHERE NOT (type_poste = 'portable' OR type_poste = 'tablette');
SELECT * FROM poste WHERE type_poste <> 'portable' AND type_poste <> 'tablette';
SELECT * FROM poste WHERE type_poste NOT IN ('portable', 'tablette');

SQL ajoute une troisième valeur de vérité, inconnu (UNKNOWN), produite par toute comparaison avec NULL. Un WHERE ne garde que les lignes où la condition est vraie : les lignes « inconnues » disparaissent, ce qui surprend souvent. NOT (inconnu) reste inconnu, vrai OR inconnu est vrai, faux AND inconnu est faux. Cette logique à trois valeurs et le piège de NOT IN avec un NULL sont détaillés dans le cours SQL : NULL et la logique à trois valeurs.

Les opérateurs bit à bit

Les opérateurs bit à bit appliquent une opération booléenne à chaque rang de bits de deux entiers, indépendamment des autres rangs.

Les usages des opérateurs bit à bit reposent sur trois règles de Boole, appliquées à chaque bit :

• x · 0 = 0 et x · 1 = x : un ET avec un masque garde les bits où le masque vaut 1 et éteint les autres ;
• x + 1 = 1 et x + 0 = x : un OU avec un masque allume les bits où le masque vaut 1 ;
• x ⊕ 1 = x̅ et x ⊕ 0 = x : un XOR avec un masque inverse les bits où le masque vaut 1.

Le masque de sous-réseau : un ET logique

Une adresse IPv4 compte 32 bits. Le masque de sous-réseau a ses premiers bits à 1 (la partie réseau) et les suivants à 0 (la partie hôte). L'adresse du réseau s'obtient par un ET bit à bit entre l'adresse IP et le masque : les bits de la partie réseau sont gardés, ceux de la partie hôte sont mis à 0.

Exemple : 192.168.10.37/27. Le préfixe /27 donne un masque de 27 bits à 1 : 255.255.255.224. Les trois premiers octets du masque valent 255 (tout est gardé) ; le travail se fait sur le dernier octet.

• Adresse du réseau : IP ET masque = 192.168.10.32.
• Adresse de diffusion (broadcast) : IP OU (complément du masque), tous les bits d'hôte à 1 = 192.168.10.63.
• Adresses utilisables : de 192.168.10.33 à 192.168.10.62, soit 2⁵ − 2 = 30 hôtes (5 bits d'hôte).

Deux machines sont dans le même réseau si et seulement si (IP₁ ET masque) = (IP₂ ET masque). C'est exactement le test que fait un poste avant d'envoyer un paquet : même réseau, envoi direct ; sinon, envoi à la passerelle.

import ipaddress

reseau = ipaddress.ip_interface("192.168.10.37/27").network
print(reseau, reseau.broadcast_address)   # 192.168.10.32/27 192.168.10.63

# Le même calcul à la main, avec le ET bit à bit
ip = int(ipaddress.ip_address("192.168.10.37"))
masque = int(ipaddress.ip_address("255.255.255.224"))
print(ipaddress.ip_address(ip & masque))   # 192.168.10.32

Le découpage en sous-réseaux est traité en détail dans le cours réseaux, et l'écriture d'une adresse ou d'un masque en binaire dans le cours d'arithmétique.

Les droits Unix : des bits et des masques

Sous Linux, les droits d'un fichier sont trois groupes de trois bits : lecture (r = 4), écriture (w = 2), exécution (x = 1), pour le propriétaire, le groupe et les autres. chmod 754 signifie 111 101 100 : rwx pour le propriétaire, r-x pour le groupe, r-- pour les autres.

• Tester un droit : un ET avec le bit voulu. Le groupe a-t-il l'écriture ? Le chiffre du groupe est 5 = 101, et 101 ET 010 = 000 : non.
• Le umask retire des droits par défaut. Un fichier est créé avec les droits 666 ET (non umask). Avec le umask 022 : 666 ET (non 022) = 644 (rw-r--r--). Pour un dossier, 777 ET (non 022) = 755.

Les droits Linux sont détaillés dans le cours administration Linux.

Les drapeaux : plusieurs booléens dans un entier

Une application peut ranger plusieurs droits dans un seul entier, chaque droit occupant un bit : LIRE = 1 (0001), ÉCRIRE = 2 (0010), SUPPRIMER = 4 (0100), ADMINISTRER = 8 (1000). On parle de drapeaux (flags) ou de masque de bits.

LIRE, ECRIRE, SUPPRIMER, ADMIN = 1, 2, 4, 8

droits = LIRE | ECRIRE        # 0011 : on allume deux bits (OU)
droits |= SUPPRIMER           # 0111 : on ajoute un droit (OU)
droits &= ~ECRIRE             # 0101 : on retire un droit (ET avec le complément)
print(droits)                 # 5
print(droits & SUPPRIMER != 0, droits & ECRIRE != 0)   # True False : on teste (ET)

C'est la technique des permissions Unix, des options de nombreuses fonctions système et des colonnes SET de MySQL.

Exercices

SELECT * FROM ticket WHERE priorite = 'haute' AND (statut = 'ouvert' OR statut = 'en attente');