04. Équivalences et Formes Normales

Algèbre booléenne

L’algèbre booléenne est la structure algébrique sous-jacente à la logique propositionnelle. Elle permet de manipuler les formules comme des expressions algébriques, en utilisant des lois qui préservent l’équivalence logique.

Structure algébrique

Une algèbre booléenne est un ensemble $B$ muni de:

• Deux opérations binaires: $\land$ (meet) et $\lor$ (join)
• Une opération unaire: $\neg$ (complément)
• Deux éléments distingués: $\bot$ (bottom/faux) et $\top$ (top/vrai)

satisfaisant les axiomes suivants.

Lois fondamentales

Lois d’identité

$$ \begin{aligned} p \land \top &\equiv p \ p \lor \bot &\equiv p \end{aligned} $$

L’élément $\top$ est neutre pour la conjonction, $\bot$ pour la disjonction.

Lois de domination

$$ \begin{aligned} p \land \bot &\equiv \bot \ p \lor \top &\equiv \top \end{aligned} $$

Toute conjonction avec $\bot$ est fausse; toute disjonction avec $\top$ est vraie.

Lois d’idempotence

$$ \begin{aligned} p \land p &\equiv p \ p \lor p &\equiv p \end{aligned} $$

Répéter un opérande n’a pas d’effet.

Lois de complémentarité

$$ \begin{aligned} p \land \neg p &\equiv \bot \ p \lor \neg p &\equiv \top \end{aligned} $$

La seconde est le principe du tiers exclu.

Lois de commutativité

$$ \begin{aligned} p \land q &\equiv q \land p \ p \lor q &\equiv q \lor p \end{aligned} $$

L’ordre des opérandes est interchangeable.

Lois d’associativité

$$ \begin{aligned} (p \land q) \land r &\equiv p \land (q \land r) \ (p \lor q) \lor r &\equiv p \lor (q \lor r) \end{aligned} $$

Le parenthésage n’affecte pas le résultat.

Lois de distributivité

$$ \begin{aligned} p \land (q \lor r) &\equiv (p \land q) \lor (p \land r) \ p \lor (q \land r) &\equiv (p \lor q) \land (p \lor r) \end{aligned} $$

La distributivité fonctionne dans les deux sens, contrairement à l’arithmétique ordinaire.

Lois d’absorption

$$ \begin{aligned} p \land (p \lor q) &\equiv p \ p \lor (p \land q) &\equiv p \end{aligned} $$

Ces lois sont utiles pour simplifier les formules.

Lois de De Morgan

$$ \begin{aligned} \neg(p \land q) &\equiv \neg p \lor \neg q \ \neg(p \lor q) &\equiv \neg p \land \neg q \end{aligned} $$

Ces lois permettent de “distribuer” la négation à travers les connecteurs, en échangeant $\land$ et $\lor$.

Généralisation:

$$ \begin{aligned} \neg(p_1 \land p_2 \land \dots \land p_n) &\equiv \neg p_1 \lor \neg p_2 \lor \dots \lor \neg p_n \ \neg(p_1 \lor p_2 \lor \dots \lor p_n) &\equiv \neg p_1 \land \neg p_2 \land \dots \land \neg p_n \end{aligned} $$

Double négation

$$ \neg\neg p \equiv p $$

En logique classique (mais pas en logique intuitionniste), la double négation s’élimine.

Équivalences pour l’implication

Définition matérielle

$$ p \rightarrow q \equiv \neg p \lor q $$

Cette équivalence est fondamentale pour transformer les implications.

Contraposition

$$ p \rightarrow q \equiv \neg q \rightarrow \neg p $$

Si “p implique q”, alors “non-q implique non-p”.

Exportation

$$ (p \land q) \rightarrow r \equiv p \rightarrow (q \rightarrow r) $$

Transitivité

$$ (p \rightarrow q) \land (q \rightarrow r) \models p \rightarrow r $$

Équivalences pour le biconditionnelle

$$ \begin{aligned} p \leftrightarrow q &\equiv (p \rightarrow q) \land (q \rightarrow p) \ p \leftrightarrow q &\equiv (p \land q) \lor (\neg p \land \neg q) \ p \leftrightarrow q &\equiv \neg(p \oplus q) \end{aligned} $$

où $\oplus$ est le XOR (ou exclusif).

Formes normales

Les formes normales sont des représentations canoniques des formules qui facilitent leur analyse et leur comparaison.

Littéraux

Un littéral est une variable propositionnelle ou sa négation:

• Littéral positif: $p$
• Littéral négatif: $\neg p$

Clauses

Une clause est une disjonction de littéraux:

$$ \ell_1 \lor \ell_2 \lor \dots \lor \ell_n $$

Une clause unitaire contient un seul littéral. La clause vide $\square$ (ou $\bot$) ne contient aucun littéral et est toujours fausse.

Termes

Un terme (ou cube) est une conjonction de littéraux:

$$ \ell_1 \land \ell_2 \land \dots \land \ell_n $$

Forme normale disjonctive (FND/DNF)

Définition

Une formule est en forme normale disjonctive si elle est une disjonction de termes:

$$ (l_{1,1} \land \dots \land l_{1,k_1}) \lor (l_{2,1} \land \dots \land l_{2,k_2}) \lor \dots \lor (l_{m,1} \land \dots \land l_{m,k_m}) $$

Algorithme de conversion

Pour convertir une formule $\varphi$ en FND:

1. Éliminer $\rightarrow$ et $\leftrightarrow$ en utilisant leurs définitions.
2. Pousser les négations vers l’intérieur (De Morgan, double négation).
3. Distribuer $\land$ sur $\lor$.

Exemple

Convertir $(p \rightarrow q) \land r$ en FND:

$$ \begin{aligned} (p \rightarrow q) \land r &\equiv (\neg p \lor q) \land r \ &\equiv (\neg p \land r) \lor (q \land r) \end{aligned} $$

FND complète

Une FND est complète si chaque terme contient exactement une occurrence de chaque variable (positive ou négative). Chaque terme d’une FND complète correspond à exactement une ligne de la table de vérité où la formule est vraie.

Exemple: Pour les variables $p, q$:

$$ (p \land q) \lor (p \land \neg q) \lor (\neg p \land q) $$

est une FND complète.

Forme normale conjonctive (FNC/CNF)

Définition

Une formule est en forme normale conjonctive si elle est une conjonction de clauses:

$$ (l_{1,1} \lor \dots \lor l_{1,k_1}) \land (l_{2,1} \lor \dots \lor l_{2,k_2}) \land \dots \land (l_{m,1} \lor \dots \lor l_{m,k_m}) $$

Algorithme de conversion

Similaire à FND, mais avec distribution de $\lor$ sur $\land$:

1. Éliminer $\rightarrow$ et $\leftrightarrow$.
2. Pousser les négations vers l’intérieur.
3. Distribuer $\lor$ sur $\land$.

Exemple

Convertir $\neg(p \land q) \rightarrow r$ en FNC:

$$ \begin{aligned} \neg(p \land q) \rightarrow r &\equiv \neg(\neg p \lor \neg q) \lor r \ &\equiv (p \land q) \lor r \ &\equiv (p \lor r) \land (q \lor r) \end{aligned} $$

Importance de la FNC

La FNC est fondamentale pour:

• Les solveurs SAT (algorithmes DPLL, CDCL)
• La résolution (méthode de preuve automatique)
• La programmation logique (clauses de Horn)

Conversion par table de vérité

De la table à la FND

Pour obtenir la FND d’une formule $\varphi$:

1. Construire la table de vérité de $\varphi$.
2. Pour chaque ligne où $\varphi = V$, créer un terme avec:
   • $p$ si $v(p) = V$
   • $\neg p$ si $v(p) = F$
3. Former la disjonction de tous ces termes.

De la table à la FNC

Pour obtenir la FNC:

1. Pour chaque ligne où $\varphi = F$, créer une clause avec:
   • $p$ si $v(p) = F$
   • $\neg p$ si $v(p) = V$
2. Former la conjonction de toutes ces clauses.

Exemple

Pour $p \rightarrow q$:

$$ \begin{array}{c|c|c} p & q & p \rightarrow q \ \hline V & V & V \ V & F & F \ F & V & V \ F & F & V \end{array} $$

FND: $(p \land q) \lor (\neg p \land q) \lor (\neg p \land \neg q)$

FNC: $\neg p \lor q$ (une seule ligne fausse)

Complétude fonctionnelle

Définition

Un ensemble de connecteurs est fonctionnellement complet s’il permet d’exprimer toute fonction booléenne.

Ensembles complets

Les ensembles suivants sont fonctionnellement complets:

1. ${\neg, \land}$
2. ${\neg, \lor}$
3. ${\neg, \rightarrow}$
4. ${NAND}$ seul
5. ${NOR}$ seul

Preuve pour {¬, ∧}

Toute formule peut être mise en FND. En FND, seuls $\neg$, $\land$, $\lor$ sont utilisés. Or:

$$ p \lor q \equiv \neg(\neg p \land \neg q) $$

Donc ${\neg, \land}$ suffit.

NAND est complet

$$ \begin{aligned} \neg p &\equiv p \uparrow p \ p \land q &\equiv (p \uparrow q) \uparrow (p \uparrow q) \ p \lor q &\equiv (p \uparrow p) \uparrow (q \uparrow q) \end{aligned} $$

où $p \uparrow q \equiv \neg(p \land q)$ est l’opérateur NAND.

Cette propriété est exploitée dans les circuits intégrés, où les portes NAND sont universelles.

Simplification de formules

Objectif

Trouver une formule équivalente avec:

• Moins de connecteurs
• Moins de littéraux
• Moins de niveaux de profondeur

Algorithme de Quine-McCluskey

Méthode systématique pour trouver la FND minimale:

1. Partir de la FND complète.
2. Identifier les implicants premiers: termes qui ne peuvent être simplifiés.
3. Construire la couverture minimale.

Cartes de Karnaugh

Représentation graphique pour formules avec 2-5 variables:

Pour $p \land q \lor p \land \neg q$:

      q=0  q=1
    +----+----+
p=1 | 1  | 1  |
    +----+----+
p=0 | 0  | 0  |
    +----+----+

Le rectangle de 1 se simplifie en: $p$

Dualité

Principe de dualité

Pour toute équivalence valide, en échangeant $\land \leftrightarrow \lor$ et $\top \leftrightarrow \bot$, on obtient une équivalence valide.

Exemple:

• Original: $p \land \top \equiv p$
• Dual: $p \lor \bot \equiv p$

Formule duale

La duale de $\varphi$, notée $\varphi^d$, s’obtient en échangeant $\land$ et $\lor$, $\top$ et $\bot$.

Théorème: $\neg\varphi \equiv (\neg\varphi_1, \dots, \neg\varphi_n)^d$ où $\varphi_1, \dots, \varphi_n$ sont les sous-formules atomiques de $\varphi$.