Conséquence et Équivalence Sémantique

RÉSUMÉ
Dans cette leçon, nous étudierons la Conséquence et l’Équivalence Sémantique en logique propositionnelle, ce qui est une continuation naturelle de ce que nous avons vu précédemment. Nous apprendrons comment obtenir la notion de conséquence sémantique à partir des attributions de valeurs de vérité et comment cette idée se rapporte au théorème de déduction. De plus, nous verrons des exemples pratiques de l’utilisation des tables de vérité pour obtenir des propriétés utiles telles que l’Élimination de la Conjonction et l’Introduction de la Disjonction. Nous explorerons également la notion d’Équivalence Sémantique et verrons comment elle se rapporte aux propriétés que nous connaissons déjà. Enfin, nous montrerons comment l’utilisation de modèles et de techniques de déduction nous permet de simplifier l’étude des problèmes de conséquence et d’équivalence sémantique.

OBJECTIFS D’APPRENTISSAGE :
À la fin de cette leçon, l’étudiant sera capable de

Comprendre la notion de conséquence sémantique.
Comprendre les différentes interprétations du symbole ⊨.
Comprendre la démonstration du théorème de déduction dans sa version sémantique et son utilisation dans l’étude de la conséquence et de l’équivalence sémantique.
Comprendre la définition de l’équivalence sémantique et sa relation avec les valeurs de vérité.
Appliquer le théorème de déduction dans sa version sémantique pour transformer des problèmes de conséquence en problèmes de validité.
Appliquer les propriétés utiles dans l’utilisation des tables de vérité pour démontrer des équivalences sémantiques.
Appliquer les lois d’absorption, de distribution et de DeMorgan dans la simplification des expressions complexes.
Analyser la relation entre les modèles et les déductions dans l’étude de la logique propositionnelle.

TABLE DES MATIÈRES
ATTRIBUTIONS ET MODÈLES
LE THÉORÈME DE DÉDUCTION (VERSION SÉMANTIQUE)
UTILISATION DU THÉORÈME DE DÉDUCTION DANS L’ÉTUDE DE LA CONSÉQUENCE ET DE L’ÉQUIVALENCE SÉMANTIQUE
ÉQUIVALENCE SÉMANTIQUE ET PROPRIÉTÉS
SYNTHÈSE

L’étude de la Conséquence et de l’Équivalence Sémantique est la continuation naturelle de ce que nous avons fait lorsque nous avons examiné la sémantique de la logique propositionnelle. Nous examinerons maintenant la manière dont la notion de conséquence sémantique est obtenue à partir des attributions de valeurs de vérité, comment cela émerge naturellement une version sémantique du théorème de déduction. Des exemples pratiques de l’utilisation des tables de vérité pour obtenir certaines propriétés utiles seront présentés. Vous pouvez également voir tout cela sur la chaîne YouTube.

Attributions et modèles

Commençons par une définition qui est cruciale pour les développements que nous verrons dans cette entrée, celle de conséquence sémantique.

DÉFINITION : Une expression

G

est conséquence (sémantique) d’une autre expression

F

si pour chaque attribution

\mathcal{A}

il est vérifié que

$\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$

Cela est représenté en écrivant $F\models G$ et se lit « l’expression $F$ modèle l’expression $G$ » ou « $G$ est conséquence (sémantique) de $F$ . »

Avec cette définition en main, nous devons noter que le symbole $\models$ a en réalité plusieurs interprétations différentes selon le contexte :

$\mathcal{A} \models F$ signifie que $\mathcal{A}(F) = 1$ ; c’est-à-dire que « $\mathcal{A}$ modèle $F$ . »
$G \models F$ signifie que si une attribution quelconque modèle $G$ , alors elle modèle $F$ , et nous lisons cela comme « $F$ est conséquence de $G$ . »
$\models F$ signifie que $F$ est valable sous toute attribution ; c’est-à-dire que $F$ est une tautologie.

Ainsi, bien que le symbole $\models$ puisse avoir de nombreuses interprétations, le contexte n’est pas ambigu.

La notion de conséquence (sémantique) est proche de la notion « d’implication » que nous avons déjà examinée, dans le sens où, si $F\models G$ , alors $\models (F\rightarrow G)$ . En fait, cela est très similaire au théorème de déduction que nous avons vu dans les leçons précédentes.

Le Théorème de Déduction (Version Sémantique)

[voir]

THÉORÈME : Si

F

G

sont des expressions quelconques, alors il est vérifié que

$F\models G \Leftrightarrow \models (F\rightarrow G)$

Démonstration :

La démonstration de ce théorème est obtenue facilement en observant les tables de vérité

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

Si nous nous concentrons sur la signification de $F\models G$ , nous verrons que cela équivaut à dire que $\mathcal{A}\models F \Rightarrow \mathcal{A}\models G$ , ce qui est la même chose que de dire que $\mathcal{A}\not\models F \vee \mathcal{A}\models G$ . Maintenant, si nous notons que de plus $\mathcal{A}\not\models F$ est exactement la même chose que $\mathcal{A}\models \neg F$ , alors il est vérifié que $F\models G$ est équivalent à dire que $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ . Maintenant, si nous faisons une table de vérité pour $F \rightarrow G$ et que nous marquons en vert la région où il est vérifié que $\mathcal{A} \models \neg F \vee \mathcal{A}\models G$ , alors nous verrons ce qui suit :

$F$	$G$	$\neg F$	$(F\rightarrow G):=(\neg F \vee G)$
$0$	$0$	$1$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$0$	$0$
$1$	$1$	$0$	$1$

D’ici, nous avons que, lorsque $F\models G$ , il est toujours vérifié que $\models (F \rightarrow G)$ et vice versa, ce qui n’est rien d’autre que le théorème de déduction et son réciproque dans sa version sémantique.

Supposons que nous voulions savoir si une expression $G$ est conséquence d’une autre expression $F$ . Nous nous référerons à cela comme le problème de conséquence. En utilisant le théorème précédent, ce problème peut être transformé en un problème de validité, car « $G$ est conséquence de $F$ si et seulement si $(F\rightarrow G)$ est un théorème ».

Utilisation du théorème de déduction dans l’étude de la conséquence et de l’équivalence sémantique

À partir des tables de vérité, on peut inférer certaines propriétés qui rappellent celles que nous avons vues dans le passé.

EXEMPLE: Montrer en utilisant des tables de vérité que les propriétés suivantes sont valides

Élimination de la Conjonction :

(F\wedge G)\models F

Introduction de la Disjonction :

F\models (F\vee G)

Contradiction :

(F\wedge\neg F)\models G

Solution : En utilisant le théorème de déduction que nous venons de revoir, nous pouvons transformer le problème de conséquence en un problème de validité.

Pour résoudre l’Élimination de la Conjonction, nous pouvons réaliser la table de vérité suivante

$F$	$G$	$(F\wedge G)$	$((F\wedge G) \rightarrow F)$
$0$	$0$	$0$	$1$
$0$	$1$	$0$	$1$
$1$	$0$	$0$	$1$
$1$	$1$	$1$	$1$

Avec cela, nous avons démontré que $((F\wedge G)\rightarrow F)$ est une tautologie et, par conséquent, en suivant le réciproque du théorème de déduction, nous obtenons que $(F\wedge G) \models F$ .

L’Introduction de la Disjonction est résolue de manière analogue en construisant une table de vérité appropriée

$F$	$G$	$(F\vee G)$	$(F\rightarrow(F\vee G))$
$0$	$0$	$0$	$1$
$0$	$1$	$1$	$1$
$1$	$0$	$1$	$1$
$1$	$1$	$1$	$1$

Ici, nous observons que $(F\rightarrow (F\vee G))$ est une tautologie et, par conséquent, par le réciproque du théorème de déduction, il est vérifié que $F\models (F\vee G)$

Et enfin, la propriété de Contradiction est démontrée en utilisant la même méthode

$F$	$\neg F$	$(F\wedge \neg F)$	$G$	$((F\wedge \neg F)\rightarrow G)$
$0$	$1$	$0$	$0$	$1$
$0$	$1$	$0$	$1$	$1$
$1$	$0$	$0$	$0$	$1$
$1$	$0$	$0$	$1$	$1$

Avec cette table de vérité, nous avons démontré que $((F\wedge \neg F)\rightarrow G)$ est une tautologie et, par conséquent, par le réciproque du théorème de déduction, il est vérifié que $(F\wedge \neg F)\models G$ .

Équivalence Sémantique et Propriétés

[voir]

DÉFINITION : Si les deux se produisent en même temps,

F\models G

G\models F

, alors on dit que

F

G

sont semantiquement équivalents entre eux. Cela est représenté en écrivant

F\equiv G

Comme conséquence de cette définition, deux expressions sont sémantiquement équivalentes si et seulement si elles ont les mêmes valeurs de vérité

EXEMPLE : Il peut être montré en utilisant des tables de vérité que les équivalences sémantiques de symétrie sont valables.

(F\downarrow G) \equiv (G\downarrow F)

(F\vee G) \equiv (G\vee F)

(F\wedge G) \equiv (G\wedge F)

(F\leftrightarrow G) \equiv (G\leftrightarrow F)

(F\underline{\vee} G) \equiv (G\underline{\vee} F)

EXEMPLE : Si

F

est une expression quelconque,

\top

une tautologie et

\bot

une contradiction, alors en utilisant des tables de vérité, il est possible de prouver les équivalences sémantiques suivantes

(F\wedge \top) \equiv F

(F\vee \top) \equiv \top

(F\wedge \bot) \equiv \bot

(F\vee \bot) \equiv F

Ces équivalences sont connues sous le nom de lois d’absorption.

EXEMPLE : Dans la sémantique de la logique propositionnelle, les équivalences de distribution de la conjonction et de la disjonction sont également valables.

(F\wedge (G\vee H)) \equiv ((F\wedge G) \vee (F\wedge H))

(F\vee (G\wedge H)) \equiv ((F\vee G) \wedge (F\vee H))

EXEMPLE : Dans la sémantique de la logique propositionnelle, les Lois de DeMorgan sont également valables.

\neg(F\wedge G) \equiv (\neg F \vee \neg G)

\neg(F\vee G) \equiv (\neg F \wedge \neg G)

EXERCICE : Un bon exercice consiste à prouver en utilisant des tables de vérité que, en effet, les équivalences sémantiques des Lois d’Absorption, de Distributivité et les Lois de DeMorgan sont valables.

EXEMPLE : Démontrer en utilisant des équivalences sémantiques que l’équivalence suivante est vérifiée :

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E))\equiv ((A\wedge B)\vee(C\wedge D))$ .

Solution : Nous pouvons prouver cette équivalence en utilisant des tables de vérité, mais si nous faisons cela, nous devrons gérer une expression avec 5 variables propositionnelles, ce qui implique de faire une table de vérité avec

2^5 = 32

lignes, et il serait idéal d’éviter ce scénario. Pour y parvenir, nous utiliserons les équivalences que nous avons déjà montrées.

Tout d’abord, notons que $(E\vee \neg E)$ est une tautologie. Appelons cette tautologie $\top$ . Ensuite, en utilisant les lois d’absorption, nous aurons que

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((C\wedge D) \vee A) \wedge (C\wedge D) \vee B))$

En utilisant les lois de distribution, nous obtenons

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B)) \equiv ((C\wedge D) \vee (A\wedge B))$

Enfin, par symétrie

$((C\wedge D) \vee (A\wedge B)) \equiv ((A\wedge B) \vee (C\wedge D))$

Par conséquent, en suivant ces équivalences, nous avons l’équivalence

$((C\wedge D) \vee A) \wedge (C\wedge D) \vee B) \wedge (E \vee \neg E)) \equiv ((A\wedge B) \vee (C\wedge D))$

c’est ce que nous voulions démontrer.

Synthèse

Si nous observons le développement de cet dernier exemple, nous verrons que, à mesure que le nombre de variables augmente, la complexité de l’étude des problèmes de conséquence et d’équivalence sémantique croît de manière exponentielle si nous dépendons des tables de vérité. Cependant, nous avons vu que du développement de l’idée de modèle émerge quelque chose d’analogue aux techniques de déduction que nous avons déjà étudiées en détail. Cette relation entre les modèles et les déductions est ce que nous verrons bientôt, et la combinaison des deux sera ce qui nous épargnera finalement d’innombrables maux de tête dans l’étude de la logique.

Conséquence et équivalence sémantique