Complétude et fiabilité en logique propositionnelle
RÉSUMÉ
Ce cours aborde la relation entre la complétude et la fiabilité en logique propositionnelle. Bien que les techniques de déduction et la sémantique en logique propositionnelle aient été largement discutées, peu d’attention a été accordée à la relation entre ces deux aspects. La fiabilité se réfère à la propriété d’un système logique où, chaque fois qu’une expression G peut être déduite d’un ensemble d’expressions Γ, G est conséquemment une conséquence (sémantique) de Γ. D’autre part, la complétude se réfère à la propriété d’un système logique où, si G est une conséquence sémantique d’un ensemble d’expressions Γ, alors il existe une preuve formelle avec des prémisses Γ à partir de laquelle G peut être déduite. Il est démontré que la logique propositionnelle est fiable et complète, et une explication détaillée de chaque propriété est présentée. En particulier, il est montré comment la fiabilité découle de la constitution du système déductif de la logique propositionnelle, et comment la complétude est déduite de manière simple. Cette analyse est d’une grande importance pour comprendre le fonctionnement de la logique propositionnelle et l’appliquer efficacement dans divers domaines de la connaissance.
OBJECTIFS D’APPRENTISSAGE :
À la fin de ce cours, l’étudiant sera capable de :
- Distinguer entre la fiabilité et la complétude dans un système logique.
- Appliquer la table de vérité pour les axiomes de Łukasiewicz afin de démontrer la fiabilité de la logique propositionnelle.
- Expliquer comment le modus ponens peut être réécrit en utilisant la version sémantique du théorème de déduction.
- Comprendre que la fiabilité et la complétude sont liées et qu’elles peuvent être déduites l’une de l’autre.
- Analyser le concept de tautologie et sa relation avec les théorèmes en logique propositionnelle.
INDEX
COMPLÉTUDE ET FIABILITÉ EN LOGIQUE PROPOSITIONNELLE
LA LOGIQUE PROPOSITIONNELLE EST FIABLE
LA LOGIQUE PROPOSITIONNELLE EST COMPLÈTE
Complétude et fiabilité en logique propositionnelle
À ce stade, il est temps de parler de la complétude et de la fiabilité en logique propositionnelle. Il s’avère que jusqu’à présent, beaucoup a été dit sur les techniques de déduction et la sémantique de la logique propositionnelle, mais tout cela a été fait d’une manière qui les fait apparaître comme deux aspects totalement indépendants sans aucune relation entre eux. La réalité est tout à fait opposée.
FIABILITÉ : Un système logique est dit fiable lorsque, chaque fois qu’une expression G peut être déduite d’un ensemble d’expressions \Gamma, il en résulte que G est une conséquence (sémantique) de \Gamma. |
COMPLÉTUDE : D’autre part, un système est dit complet lorsque, si G est une conséquence sémantique d’un ensemble d’expressions \Gamma, alors il existe une preuve formelle avec des prémisses \Gamma à partir de laquelle G peut être déduite. |
En réexaminant ces idées, nous verrons que la complétude et la fiabilité sont satisfaites pour la logique propositionnelle.
La logique propositionnelle est fiable
Il est facile d’obtenir la fiabilité de la logique propositionnelle en observant la constitution de son système déductif. Si nous créons la table de vérité pour les axiomes de Łukasiewicz, nous verrons qu’ils ont une structure telle qu’ils donnent toujours comme valeur la vérité, c’est-à-dire :
| \models (\alpha \rightarrow (\beta \rightarrow \alpha)) |
| \models ((\alpha \rightarrow (\beta \rightarrow \gamma))\rightarrow ((\alpha \rightarrow \beta) \rightarrow (\alpha \rightarrow \gamma))) |
| \models ((\neg\beta \rightarrow \neg\alpha)\rightarrow(\alpha \rightarrow \beta)) |
De même, le modus ponens peut être réécrit sous la forme \{\alpha,(\alpha\rightarrow \beta)\}\models \beta., ce qui peut être obtenu en utilisant la version sémantique du théorème de déduction. En fait, par ce moyen, nous obtenons \{(\alpha\rightarrow \beta)\}\models (\alpha\rightarrow \beta),, puis \models ((\alpha\rightarrow \beta)\rightarrow (\alpha\rightarrow \beta)),, ce qui est évidemment une tautologie.
La logique propositionnelle est complète
La complétude de la logique propositionnelle nous dit que, si B est une conséquence sémantique de A, alors B est déduit de A. En d’autres termes : toutes les expressions vraies ont une démonstration. C’est ce que nous appelons la complétude. Cela peut être déduit d’une manière simple.
Cela peut être déduit d’une manière simple. Supposons que B ne puisse pas être déduit de A, ou plutôt \neg(A\vdash B), selon le théorème de déduction, cela équivaut à dire : \neg (\vdash A\rightarrow B) ; maintenant, si nous recourons à la fiabilité, cela conduit à \neg(\models A \rightarrow B), ce qui, selon la version sémantique du théorème de déduction, équivaut à \neg(A\models B). En résumé, nous obtenons :
\neg(A\vdash B) \Rightarrow \neg(A\models B)
Ce qui équivaut à dire
(A\models B) \Rightarrow (A\vdash B)
Cela signifie que, si A modélise B, alors B est déduit de A. Et si nous utilisons les théorèmes de déduction correspondants, nous pouvons obtenir
(\models A\rightarrow B) \Rightarrow (\vdash A \rightarrow B)
C’est-à-dire : si une expression est une tautologie, alors c’est un théorème ; et comme nous l’avons vu, les théorèmes sont le résultat d’une démonstration.