Logique des propositions/Substitution

Début de la boite de navigation du chapitre

fin de la boite de navigation du chapitre

Notion de substitution

Définition

Définition

Étant données deux formules A et B, substituer dans la formule A la formule B à l'atome 'a' consiste à remplacer dans la formule A chaque occurrence de 'a' par la formule B. On note cette nouvelle formule '$A[a/B]$'

Mise en pratique

Début de l'exemple

Exemple

Soit la formule $a\to (b\to \lnot a)$.

On substitue à l'atome $a$ la formule $(b\land \lnot c)$ c'est-à-dire qu'on remplace chaque $a$ par cette formule, ce qui va donner :

$(b\land \lnot c)\to (b\to \lnot (b\land \lnot c))$

Fin de l'exemple

Notion de schéma

Définition

Définition

Un schéma désigne n’importe quelle formule obtenue par substitution à partir d'une formule originelle

Mise en pratique

Début de l'exemple

Exemple

Soit la formule $\lnot (a\land \lnot a)$.

$\lnot (A\land \lnot A)$ désigne n’importe quelle formule obtenue à partir de $\lnot (a\land \lnot a)$ par substitution telle que :

• $\lnot (b\land \lnot b)$.
• $\lnot ((a\lor b)\land \lnot (a\lor b))$.
• ...

On parle alors de schéma.

Fin de l'exemple

Propriété 1

Si on opère une substitution dans une formule valide alors on obtient une formule valide => Les substitutions conservent la validité.

Propriété 2

Si un schéma est obtenu à partir d'une formule valide alors il est valide.

Début de l'exemple

Exemple

$(a\leftrightarrow b)\leftrightarrow ((a\to b)\land (b\to a))$ est valide.

On opère les substitutions $a/(a\lor b)$ et $b/(c\land d)$.

$((a\lor b)\leftrightarrow (c\land d))\leftrightarrow (((a\lor b)\to (c\land d))\land ((c\land d)\to (a\lor b)))$ est valide.

Fin de l'exemple

Conclusion

Il est important de constater que ce qui fait la validité ou non d'une formule, ce n’est pas la valeur de vérité qu'on distribue aux atomes, ou même l'agencement des atomes les uns par rapport aux autres, mais la construction de la formule : son schéma.