Vérité, modèles, conséquence

Interprétations

Donner une valeur aux variables

Une formule n'est ni vraie ni fausse dans l'absolu : $p \land q$ est vraie si $p$ et $q$ le sont. Une interprétation (ou valuation) $v$ donne à chaque variable propositionnelle une valeur : $1$ (vrai) ou $0$ (faux).

La valeur d'une formule se calcule de bas en haut, le long de son arbre, avec les tables des connecteurs.

Les tables des connecteurs

Une seule ligne surprend : $p \to q$ est vraie quand $p$ est fausse, quelle que soit $q$. L'implication ne dit rien de ce qui se passe quand sa condition n'est pas remplie. « S'il pleut, je prends mon parapluie » n'est pas démenti un jour de soleil, que je prenne mon parapluie ou non. La seule façon de la rendre fausse est d'avoir $p$ vraie et $q$ fausse.

La table de vérité d'une formule

Avec $n$ variables, il y a $2^n$ interprétations. La table de vérité d'une formule les passe toutes en revue.

Modèles, validité, satisfiabilité

Définitions

Une interprétation $v$ est un modèle de $A$ si $A$ est vraie dans $v$. On écrit $v \vDash A$. Dans l'exemple ci-dessus, $A$ a un seul modèle.

Une formule est :

• valide (une tautologie) si toute interprétation en est un modèle. On écrit $\vDash A$. Exemple : $p \lor \lnot p$.
• satisfiable si elle a au moins un modèle. Exemple : $p \land q$.
• insatisfiable (une contradiction) si elle n'a aucun modèle. Exemple : $p \land \lnot p$.

Toute formule valide est satisfiable. Une formule satisfiable peut être valide ou non. « Invalide » veut dire « pas valide », ce qui n'est pas « insatisfiable » : $p \land q$ est invalide et satisfiable.

La négation échange les rôles

• $A$ est valide si et seulement si $\lnot A$ est insatisfiable.
• $A$ est satisfiable si et seulement si $\lnot A$ n'est pas valide.

En effet, $v$ est un modèle de $A$ exactement quand $v$ n'est pas un modèle de $\lnot A$. Conséquence pratique : pour montrer que $A$ est valide, on peut chercher une interprétation qui la rend fausse. Si la recherche échoue, $A$ est valide.

Conséquence logique

Définition

Soit $\Sigma$ un ensemble de formules (des hypothèses) et $A$ une formule. $A$ est conséquence logique de $\Sigma$, et l'on écrit $\Sigma \vDash A$, si tout modèle de toutes les formules de $\Sigma$ est un modèle de $A$. Autrement dit : chaque fois que les hypothèses sont toutes vraies, la conclusion l'est aussi.

Quand $\Sigma$ est vide, on retrouve $\vDash A$ : $A$ est valide.

Trois propriétés, et leur démonstration

Les démonstrations suivent toutes le même chemin : revenir à la définition, et parler d'interprétations.

Propriété 1. $\Sigma \vDash A \land B$ si et seulement si $\Sigma \vDash A$ et $\Sigma \vDash B$.

Sens direct. Soit $v$ un modèle de $\Sigma$. Comme $\Sigma \vDash A \land B$, $v \vDash A \land B$, donc $v \vDash A$ et $v \vDash B$ par la table de $\land$. Ceci pour tout modèle $v$ de $\Sigma$ : $\Sigma \vDash A$ et $\Sigma \vDash B$.

Réciproque. Soit $v$ un modèle de $\Sigma$. Alors $v \vDash A$ et $v \vDash B$, donc $v \vDash A \land B$. Ainsi $\Sigma \vDash A \land B$.

Propriété 2. $\vDash A \to B$ si et seulement si $A \vDash B$.

Sens direct. Soit $v$ un modèle de $A$. Comme $A \to B$ est valide, $v \vDash A \to B$ ; avec $v \vDash A$, la table de $\to$ donne $v \vDash B$.

Réciproque. Soit $v$ une interprétation quelconque. Si $v \vDash A$, alors $v \vDash B$ par hypothèse, et $A \to B$ est vraie. Sinon $A$ est fausse dans $v$, et $A \to B$ est vraie. Dans les deux cas $v \vDash A \to B$ : elle est valide.

Plus généralement, $\Sigma \cup \{A\} \vDash B$ si et seulement si $\Sigma \vDash A \to B$ (même démonstration). On s'en sert pour faire passer une hypothèse de gauche à droite.

Propriété 3. $\Sigma \vDash A$ si et seulement si $\Sigma \cup \{\lnot A\}$ est insatisfiable.

$\Sigma \cup \{\lnot A\}$ a un modèle exactement quand il existe une interprétation qui rend $\Sigma$ vraie et $A$ fausse, c'est-à-dire quand $\Sigma \not\vDash A$.

C'est le principe du raisonnement par l'absurde, et le point de départ de la résolution (chapitre 5).

Équivalence

Définition

Deux formules $A$ et $B$ sont équivalentes, et l'on écrit $A \equiv B$, si elles ont les mêmes modèles : elles prennent la même valeur dans toute interprétation. Elles disent la même chose.

Propriété 4. $A \equiv B$ si et seulement si $\vDash A \leftrightarrow B$.

$A \leftrightarrow B$ est vraie dans $v$ exactement quand $A$ et $B$ y ont la même valeur. Elle est donc vraie dans toute interprétation exactement quand $A$ et $B$ ont partout la même valeur, c'est-à-dire quand $A \equiv B$.

C'est le lien annoncé au chapitre 1 : $\leftrightarrow$ est un connecteur, $\equiv$ une affirmation sur deux formules, et la seconde revient à dire que la première est valide. De même, $A \vDash B$ revient à dire que $A \to B$ est valide.

Les lois usuelles

Chacune se vérifie par une table de vérité.

Le remplacement

Si $B \equiv B'$ et que $B$ apparaît comme sous-formule dans $A$, remplacer $B$ par $B'$ dans $A$ donne une formule équivalente à $A$. C'est ce qui permet de calculer avec les lois, comme on simplifie une expression en algèbre.