03. Tables de Vérité

Sémantique de la logique propositionnelle

La sémantique d’un langage formel définit comment interpréter ses expressions et leur attribuer des valeurs de vérité. En logique propositionnelle, la sémantique est définie par les tables de vérité.

Interprétations

Une interprétation (ou assignation, ou valuation) est une fonction:

$$ v: \mathcal{P} \rightarrow {V, F} $$

qui assigne à chaque variable propositionnelle de l’ensemble $\mathcal{P}$ une valeur de vérité.

Notation: On écrit $v(p) = V$ pour indiquer que la variable $p$ est vraie sous l’interprétation $v$.

Pour $n$ variables propositionnelles, il existe exactement $2^n$ interprétations distinctes.

Extension aux formules composées

Étant donnée une interprétation $v$, on étend la fonction de valuation à toutes les formules bien formées par les règles suivantes:

$$ \begin{aligned} v(\neg \varphi) &= V \iff v(\varphi) = F \ v(\varphi \land \psi) &= V \iff v(\varphi) = V \text{ et } v(\psi) = V \ v(\varphi \lor \psi) &= V \iff v(\varphi) = V \text{ ou } v(\psi) = V \ v(\varphi \rightarrow \psi) &= V \iff v(\varphi) = F \text{ ou } v(\psi) = V \ v(\varphi \leftrightarrow \psi) &= V \iff v(\varphi) = v(\psi) \end{aligned} $$

Ces règles permettent de calculer la valeur de vérité de toute formule à partir d’une interprétation donnée.

Construction des tables de vérité

Méthode systématique

Pour construire la table de vérité d’une formule $\varphi$ contenant les variables $p_1, \dots, p_n$:

1. Énumérer toutes les $2^n$ interprétations possibles.
2. Évaluer les sous-formules en ordre de complexité croissante.
3. Calculer la valeur finale de $\varphi$ pour chaque ligne.

Exemple détaillé

Construisons la table de vérité de $(p \rightarrow q) \land (q \rightarrow r)$:

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

Ordre des lignes

Par convention, on ordonne les lignes en traitant les variables comme des chiffres binaires, de $VVV\dots V$ (tout vrai) à $FFF\dots F$ (tout faux), ou l’inverse.

Certains auteurs utilisent l’ordre inverse (commençant par $FFF$). L’important est la cohérence.

Classifications sémantiques

Tautologie

Une formule $\varphi$ est une tautologie si elle est vraie sous toute interprétation:

$$ \forall v: v(\varphi) = V $$

Notation: $\models \varphi$ (on lit “$\varphi$ est valide”)

Exemples de tautologies:

1. Loi du tiers exclu: $p \lor \neg p$

$$ \begin{array}{c|c|c} p & \neg p & p \lor \neg p \\ \hline V & F & V \\ F & V & V \end{array} $$

1. Modus ponens (forme propositionnelle): $((p \rightarrow q) \land p) \rightarrow q$

2. Loi de contraposition: $(p \rightarrow q) \leftrightarrow (\neg q \rightarrow \neg p)$

3. Loi d’absorption: $p \lor (p \land q) \leftrightarrow p$

Contradiction

Une formule $\varphi$ est une contradiction (ou antilogie) si elle est fausse sous toute interprétation:

$$ \forall v: v(\varphi) = F $$

Exemples:

1. Négation du tiers exclu: $\neg(p \lor \neg p)$
2. Contradiction simple: $p \land \neg p$

Propriété fondamentale: $\varphi$ est une contradiction si et seulement si $\neg\varphi$ est une tautologie.

Contingence

Une formule $\varphi$ est contingente si elle n’est ni une tautologie ni une contradiction:

$$ \exists v_1: v_1(\varphi) = V \quad \text{et} \quad \exists v_2: v_2(\varphi) = F $$

Exemple: $p \rightarrow q$ est contingente:

• $v(p) = F, v(q) = F \Rightarrow v(p \rightarrow q) = V$
• $v(p) = V, v(q) = F \Rightarrow v(p \rightarrow q) = F$

La plupart des formules rencontrées en pratique sont contingentes.

Satisfiabilité

Définition

Une formule $\varphi$ est satisfiable s’il existe au moins une interprétation $v$ telle que $v(\varphi) = V$.

$$ \exists v: v(\varphi) = V $$

Relations:

• Toute tautologie est satisfiable.
• Toute formule contingente est satisfiable.
• Seules les contradictions sont insatisfiables.

Modèle

Une interprétation $v$ qui satisfait $\varphi$ est appelée un modèle de $\varphi$:

$$ v \models \varphi \iff v(\varphi) = V $$

Problème SAT

Le problème de satisfiabilité (SAT) consiste à déterminer si une formule propositionnelle donnée est satisfiable.

Théorème (Cook-Levin, 1971): SAT est NP-complet.

Ce résultat est fondamental en théorie de la complexité: SAT est le premier problème démontré NP-complet. Tout problème dans NP peut être réduit à SAT en temps polynomial.

Conséquence logique

Définition

Une formule $\psi$ est une conséquence logique d’un ensemble de formules $\Gamma = {\varphi_1, \dots, \varphi_n}$ si toute interprétation qui satisfait toutes les formules de $\Gamma$ satisfait également $\psi$:

$$ \Gamma \models \psi \iff \forall v: (\forall \varphi \in \Gamma: v(\varphi) = V) \Rightarrow v(\psi) = V $$

Notation: On écrit $\varphi_1, \dots, \varphi_n \models \psi$

Théorème de déduction sémantique

$$ \Gamma, \varphi \models \psi \iff \Gamma \models (\varphi \rightarrow \psi) $$

Ce théorème établit un lien fondamental entre la conséquence logique et l’implication.

Vérification par table de vérité

Pour vérifier si $\varphi_1, \varphi_2 \models \psi$:

1. Construire la table de vérité avec toutes les variables.
2. Identifier les lignes où $\varphi_1 = V$ et $\varphi_2 = V$.
3. Vérifier que $\psi = V$ dans toutes ces lignes.

Exemple: Vérifier $p \rightarrow q, p \models q$

$$ \begin{array}{c|c|c|c} p & q & p \rightarrow q & \text{Conclusion} \\ \hline V & V & V & q = V \checkmark \\ V & F & F & \text{(non applicable)} \\ F & V & V & \text{(non applicable)} \\ F & F & V & \text{(non applicable)} \end{array} $$

La seule ligne où les deux prémisses sont vraies ($p = V$ et $p \rightarrow q = V$) est la première, et $q = V$. Donc $p \rightarrow q, p \models q$.

Équivalence logique

Définition

Deux formules $\varphi$ et $\psi$ sont logiquement équivalentes si elles ont la même valeur de vérité sous toute interprétation:

$$ \varphi \equiv \psi \iff \forall v: v(\varphi) = v(\psi) $$

Propriété: $\varphi \equiv \psi$ si et seulement si $\varphi \leftrightarrow \psi$ est une tautologie.

Exemples fondamentaux

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

Complexité et optimisations

Explosion combinatoire

Pour $n$ variables, une table de vérité a $2^n$ lignes. Cela devient rapidement impraticable:

Méthodes alternatives

Pour les formules avec beaucoup de variables, on utilise des méthodes plus efficaces:

1. Diagrammes de décision binaires (BDD): Représentation compacte des fonctions booléennes.
2. Solveurs SAT: Algorithmes comme DPLL et CDCL.
3. Propagation unitaire: Simplification incrémentale.
4. Arbres sémantiques: Exploration avec élagage.

Ces techniques sont au cœur des outils de vérification formelle modernes.