Sémantique de la Logique Propositionnelle
RÉSUMÉ
Dans cette leçon, nous étudions la sémantique de la logique propositionnelle, en particulier l’affectation des valeurs de vérité à une expression et la manière dont elles se propagent d’une expression à une autre à travers les connecteurs logiques. La notion de tables de vérité est introduite, ainsi que les tables de vérité des connecteurs dérivés tels que la négation, la disjonction, la conjonction, l’implication, la double implication et la disjonction exclusive. De plus, la définition d’une affectation sur un ensemble d’expressions atomiques est présentée, et il est expliqué comment elle s’étend naturellement à toutes les expressions pouvant être construites à partir de cet ensemble. Enfin, les définitions des expressions valides, satisfaisables et insatisfaisables sont établies, et des exemples de tautologies et de contradictions sont présentés. Cependant, il est reconnu que le calcul des tables de vérité pour des expressions complexes peut être inefficace, d’où la mention de la recherche de méthodes alternatives pour résoudre les problèmes de validité ou de satisfaisabilité.
OBJECTIFS D’APPRENTISSAGE :
À la fin de cette leçon, l’étudiant sera capable de :
- Expliquer la sémantique de la logique propositionnelle
- Utiliser les tables de vérité pour représenter les affectations des valeurs de vérité des expressions en logique propositionnelle
- Modéliser une expression avec une affectation en logique propositionnelle
- Appliquer les règles sémantiques de la logique propositionnelle pour déterminer si une expression est une tautologie, une contradiction ou une contingence
INDEX
SUR LES AFFECTATIONS DES VALEURS DE VÉRITÉ
SÉMANTIQUE DES CONNECTEURS EN LOGIQUE PROPOSITIONNELLE
AFFECTATIONS EN LOGIQUE PROPOSITIONNELLE
MODÈLES EN LOGIQUE PROPOSITIONNELLE
UN PROBLÈME D’EFFICACITÉ DANS LA SÉMANTIQUE DE LA LOGIQUE PROPOSITIONNELLE
Sur les Affectations des Valeurs de Vérité
Nous avons précédemment examiné la syntaxe et les systèmes déductifs de la logique propositionnelle. Bien que cela nous ait permis d’examiner la manière dont on peut obtenir des expressions à partir d’autres, nous n’avons pas encore abordé l’affectation des valeurs de vérité. Comme nous avons déjà discuté de tout ce qu’il y a à dire sur les techniques de déduction en logique propositionnelle, nous allons maintenant commencer notre étude sur la sémantique de la logique propositionnelle, où nous examinerons comment les affectations des valeurs de vérité se propagent d’une expression à une autre.
Sémantique des Connecteurs en Logique Propositionnelle
La sémantique des connecteurs est introduite à travers les tables de vérité, car elles fournissent un moyen simple et ordonné de représenter toutes les affectations possibles d’une expression.
Table de Vérité de la Négation Conjointe
Nous commencerons tout d’abord par le connecteur le plus fondamental de tous, qui est la négation conjointe. Sa table de vérité est la suivante :
| \alpha | \beta | (\alpha\downarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 0 |
Les valeurs « 1 » et « 0 » correspondent à « Vrai » et « Faux », respectivement. Chaque ligne de la table de vérité est une affectation possible des variables (ou des expressions atomiques) qui composent l’expression (ou les expressions) à étudier. De même, chaque colonne contenant une expression formée par ces variables présente les résultats possibles de ces affectations. Ainsi, l’interprétation de cette table nous indique que \alpha\downarrow\beta est vrai seulement lorsque \alpha et \beta sont tous deux faux en même temps, et faux dans les autres cas. C’est pourquoi le connecteur \downarrow est appelé négation conjointe.
Tables de Vérité des Connecteurs Dérivés
À partir de la sémantique de la négation conjointe, il est possible de dériver celles des autres connecteurs via leurs définitions. Les voici :
| Négation : | \neg \alpha | := | (\alpha\downarrow\alpha) |
| Disjonction Inclusive : | (\alpha \vee \beta) | := | \neg(\alpha\downarrow\beta) |
| Conjonction : | (\alpha \wedge \beta) | := | \neg(\neg\alpha\vee \neg\beta) |
| Implication : | (\alpha \rightarrow \beta) | := | (\neg\alpha\vee \beta) |
| Double Implication : | (\alpha \leftrightarrow \beta) | := | ((\alpha\rightarrow \beta)\wedge(\beta \rightarrow \alpha)) |
| Disjonction Exclusive : | (\alpha \underline{\vee} \beta) | := | \neg(\alpha\leftrightarrow \beta) |
À partir de ces définitions, il est possible de calculer les tables de vérité des autres connecteurs :
Négation
| \alpha | \neg \alpha |
| 0 | 1 |
| 1 | 0 |
De là découle le fait que le connecteur de négation a la propriété d’inverser la valeur de vérité de l’expression à laquelle il est appliqué.
Disjonction Inclusive
| \alpha | \beta | (\alpha\vee\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 1 |
C’est pourquoi la disjonction inclusive (ou simplement « disjonction ») entre deux expressions est vraie si au moins l’une des expressions est vraie, et fausse lorsque les deux expressions sont fausses en même temps.
Conjonction
| \alpha | \beta | (\alpha\wedge\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
En conséquence, la conjonction entre deux expressions est vraie seulement si les deux expressions sont vraies en même temps, et fausse dans les autres cas. C’est pourquoi un nom approprié pour ce connecteur pourrait aussi être « affirmation conjointe ».
Implication
| \alpha | \beta | (\alpha\rightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 1 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
Ainsi, la table de vérité de l’implication résume la notion selon laquelle une expression vraie ne peut impliquer qu’une autre expression vraie, mais une expression fausse peut impliquer n’importe quoi.
Double Implication
| \alpha | \beta | (\alpha\leftrightarrow\beta) |
| 0 | 0 | 1 |
| 0 | 1 | 0 |
| 1 | 0 | 0 |
| 1 | 1 | 1 |
La double implication forme une expression vraie dès que les deux expressions qui la composent ont les mêmes valeurs de vérité, et fausse dans les autres cas.
Disjonction Exclusive
| \alpha | \beta | (\alpha\underline{\vee}\beta) |
| 0 | 0 | 0 |
| 0 | 1 | 1 |
| 1 | 0 | 1 |
| 1 | 1 | 0 |
La disjonction exclusive entre deux expressions est vraie lorsque l’une, et seulement l’une, des expressions est vraie, et fausse dans les autres cas.
Affectations en Logique Propositionnelle
Avec ce qui précède, nous avons une notion simple de ce qu’est une affectation; cependant, pour les développements futurs, nous aurons besoin de quelque chose de plus précis. Si S=\{A_1, A_2, \cdots, A_n\} est un ensemble d’expressions atomiques et \mathcal{F}(S) l’ensemble de toutes les expressions qui peuvent être construites à partir des expressions de S, alors nous avons la définition suivante :
DÉFINITION : Une affectation sur S est une fonction \mathcal{A}: S \longrightarrow \{0,1\}
En d’autres termes, une affectation sur S fournit une valeur de vérité à chaque expression atomique de S. Une affectation \mathcal{A} sur S s’étend naturellement à tous les éléments de \mathcal{F}(S). Si nous avons une expression F\in \mathcal{F}(S), alors une affectation \mathcal{A} sur S correspond à une seule ligne de la table de vérité de F et \mathcal{A}(F) est la valeur de vérité de F dans cette ligne.
Une affectation \mathcal{A} sur S peut également s’étendre à certaines expressions qui ne sont pas dans \mathcal{F}(S). Si F_0 est une expression qui ne fait pas partie de \mathcal{F}(S) et que S_0 est l’ensemble des sous-formules atomiques de F_0, alors si toutes les extensions de \mathcal{A} à S\cup S_0 ont la même valeur pour F_0, alors \mathcal{A}(F_0) est défini comme cette valeur.
EXEMPLE : Si A et B sont des expressions atomiques et que \mathcal{A} est une affectation sur \{A,B\} définie par \mathcal{A}(A)=1 et \mathcal{A}(B)=0, alors nous aurons :
\mathcal{A}(A\wedge B)=0 et \mathcal{A}(A\vee B)=1
Et même si une affectation sur une variable C n’a pas été établie, on peut dire que :
\mathcal{A}(A\wedge (C\vee \neg C))=1 et \mathcal{A}(B\vee (C\wedge \neg C))=0
Cela se produit avec les deux dernières expressions car, quelle que soit l’affectation de C, il se trouvera toujours que
\mathcal{A}(C\vee\neg C)=1 et \mathcal{A}(C\wedge\neg C)=0
Chose que nous pouvons vérifier rapidement en calculant leurs tables de vérité.
| C | \neg C | (C\wedge \neg C) | (C \vee \neg C) |
| 0 | 1 | 0 | 1 |
| 1 | 0 | 0 | 1 |
■ Fin de l’exemple
Modèles en Logique Propositionnelle
Considérons une affectation \mathcal{A} sur un ensemble d’expressions S. Si F\in S est telle que \mathcal{A}(F)=1, alors on dit que l’affectation \mathcal{A} modélise F, ou que l’expression F est soutenue par l’affectation \mathcal{A}, et on le représente par l’écriture suivante :
\mathcal{A}\models F.
Et, à partir de cela, les définitions suivantes sont établies :
DÉFINITION : On dit qu’une expression est valide lorsqu’elle est soutenue par toute affectation. Si F est valide, on écrit \models F . Les expressions valides sont également appelées tautologie.
EXEMPLE : L’expression (C\vee \neg C), que nous avons déjà vue, est une tautologie.
■ Fin de l’exemple
DÉFINITION : On dit qu’une expression est satisfaisable si elle est soutenue par une affectation. Les expressions satisfaisables qui ne sont pas des tautologies sont appelées contingences.
DÉFINITION : On dit qu’une expression est insatisfaisable si elle n’est soutenue par aucune affectation. Les expressions insatisfaisables sont appelées contradictions. Si F est une contradiction, on écrit \not\models F .
EXEMPLE : L’expression (C\wedge \neg C), que nous avons déjà vue, est une contradiction.
■ Fin de l’exemple
Exemples de Tautologies et de Contradictions
Supposons que nous voulions savoir si une expression est valide ou non. Ce que nous venons de poser est un problème de décision dans la Sémantique de la Logique Propositionnelle. Un problème de décision est tout problème qui, étant donné une certaine entrée, a pour résultat un « oui » ou un « non ». Si l’on nous donne une expression F et que l’on se demande si elle est valide ou non, alors nous sommes confrontés à un problème de décision que l’on appelle problème de validité. De même, si l’on se demande si elle est satisfaisable ou non, nous sommes confrontés à un problème de satisfaisabilité. En logique propositionnelle, les tables de vérité offrent une approche systématique pour résoudre ces problèmes de décision : si toutes les valeurs de vérité possibles de F sont « 1 », alors F est valide ; si seules certaines sont « 1 », alors elle est satisfaisable ; et enfin, si toutes sont « 0 », alors elle est insatisfaisable.
EXEMPLE : Considérons l’expression ((A\wedge (A \rightarrow B)) \rightarrow B). Pour déterminer si cette expression est valide, satisfaisable ou contradictoire, faisons sa table de vérité.
| A | B | (A\rightarrow B) | (A\wedge(A\rightarrow B)) | ((A\wedge(A\rightarrow B))\rightarrow B) |
| 0 | 0 | 1 | 0 | 1 |
| 0 | 1 | 1 | 0 | 1 |
| 1 | 0 | 0 | 0 | 1 |
| 1 | 1 | 1 | 1 | 1 |
Avec cela, nous voyons que ((A\wedge(A\rightarrow B))\rightarrow B) a une valeur de vérité « 1 » pour toutes les affectations possibles, donc l’expression est une tautologie.
■ Fin de l’exemple
EXEMPLE : Considérons maintenant l’expression (((A\rightarrow B)\rightarrow A)\wedge \neg A). Le calcul de la table de vérité nous donne ce qui suit :
| A | B | (A\rightarrow B) | ((A\rightarrow B)\rightarrow A) | \neg A | (((A\rightarrow B)\rightarrow A)\wedge \neg A) |
| 0 | 0 | 1 | 0 | 1 | 0 |
| 0 | 1 | 1 | 0 | 1 | 0 |
| 1 | 0 | 0 | 1 | 0 | 0 |
| 1 | 1 | 1 | 1 | 0 | 0 |
Donc, le résultat est une contradiction.
■ Fin de l’exemple
Un Problème d’Efficacité dans la Sémantique de la Logique Propositionnelle
En théorie, nous pouvons déterminer si une expression est valide, contingente ou insatisfaisable simplement en calculant sa table de vérité, ce qui n’est pas particulièrement difficile ; malheureusement, la facilité d’exécution se fait au détriment de l’efficacité. Si nous avons une expression F composée de n expressions atomiques, alors nous devrons calculer une table de vérité avec 2^n lignes ; ainsi, par exemple, si F est composée de 23 expressions atomiques, alors sa table de vérité aura 8.388.608 lignes à calculer. En procédant de cette manière, bien que mécanique et facile à réaliser, le calcul devient rapidement impraticable à mesure que la complexité des expressions augmente. Pour cette raison, l’un de nos objectifs futurs sera de trouver un moyen de résoudre les problèmes de validité ou de satisfaisabilité sans avoir besoin de calculer des tables de vérité. La recherche de telles méthodes est l’un des problèmes centraux de toute logique.