Tronc commun / Mathématiques / Logique et calcul booléen

Logique et calcul booléen

Module 4 de l'unité U21. La logique formelle = la grammaire des conditions if, des requêtes SQL et des circuits logiques.

1. Propositions et connecteurs

Proposition = énoncé auquel on attribue une valeur de vérité : vrai (1) ou faux (0).

Le « ou » de la logique est inclusif : P ∨ Q est vrai quand les deux le sont. C'est l'inverse du langage courant (« fromage ou dessert »). Le ou exclusif du langage courant correspond à ⊕, l'opérateur ^ en Python et en C.

2. Tables de vérité

Le point qui surprend toujours : une implication dont la prémisse est fausse est vraie. « S'il pleut, je prends mon parapluie » n'est pas mise en défaut par une journée sans pluie. La seule façon de rendre P ⇒ Q faux est d'avoir P vrai et Q faux.

Une formule vraie pour toutes les valeurs est une tautologie ; fausse pour toutes, une antilogie (ou contradiction).

3. Équivalences remarquables

Les lois de De Morgan sont d'un usage quotidien : pour inverser une condition composée, on inverse chaque terme et on échange les connecteurs.

// condition d'origine
if (estConnecte && aLesDroits) { ... }

// sa négation correcte
if (!estConnecte || !aLesDroits) { ... }

Attention à ne pas confondre la contraposée (équivalente) avec la réciproque Q ⇒ P, qui ne l'est pas.

4. Prédicats et quantificateurs

Prédicat P(x) = énoncé dépendant d'une variable. Pas de valeur de vérité tant que x n'est pas fixé ou quantifié.

Négation d'un quantificateur : on change le quantificateur et on nie le prédicat.

¬(∀x, P(x))  ≡  ∃x, ¬P(x)
¬(∃x, P(x))  ≡  ∀x, ¬P(x)

Nier « tous les serveurs sont à jour » ne donne pas « aucun serveur n'est à jour », mais « il existe au moins un serveur qui n'est pas à jour ».

L'ordre des quantificateurs change le sens : ∀x, ∃y et ∃y, ∀x ne disent pas la même chose. « Chaque utilisateur a un mot de passe » n'est pas « il existe un mot de passe commun à tous les utilisateurs ».

5. Algèbre de Boole

Algèbre de Boole = même structure que la logique propositionnelle, sur {0, 1}, en notation multiplicative.

Règles de calcul

6. Simplification et tableaux de Karnaugh

Simplifier = réduire le nombre de portes d'un circuit, ou la complexité d'une condition. Par le calcul :

F = a·b + a·b̄
  = a·(b + b̄)      (factorisation)
  = a·1             (complémentation)
  = a

Le tableau de Karnaugh automatise cette recherche : on place les valeurs de la fonction dans une grille où deux cases voisines ne diffèrent que d'une variable, puis on regroupe les 1 par paquets de 1, 2, 4 ou 8 cases.

Chaque regroupement élimine les variables qui changent de valeur à l'intérieur du paquet. Plus les paquets sont grands, plus l'expression est simple — et les regroupements peuvent traverser les bords du tableau.

7. Traduction en code

L'évaluation paresseuse (court-circuit) exploite directement les tables de vérité : dans A && B, si A est faux, B n'est jamais évalué ; dans A || B, si A est vrai, B non plus.

// l'ordre protège de l'erreur : sans court-circuit, user.nom planterait
if (user != null && user.nom.equals("admin")) { ... }

En SQL, attention à la logique ternaire : une comparaison avec NULL ne renvoie ni vrai ni faux mais inconnu. C'est pourquoi WHERE colonne = NULL ne retourne jamais rien, et qu'il faut écrire WHERE colonne IS NULL.