Logique propositionnelle et logique du premier ordre
La logique propositionnelle et la logique du premier ordre sont les systèmes formels fondamentaux de la logique classique, suffisamment expressifs pour formaliser la plupart des raisonnements ordinaires et mathématiques.
Definition
La logique propositionnelle étudie l'inférence entre des phrases entières combinées par des connecteurs vérifonctionnels ; la logique du premier ordre l'étend avec des quantificateurs portant sur un domaine d'individus et avec des prédicats et des relations, tout en maintenant la quantification restreinte aux individus plutôt qu'aux propriétés.
Scope
Ce sujet couvre la syntaxe, la sémantique et la théorie de la preuve du calcul propositionnel classique (connecteurs vérifonctionnels) et de la logique des prédicats du premier ordre (quantificateurs, variables et relations). Il inclut les résultats métathéoriques centraux — les théorèmes de correction, de complétude, de compacité et de Löwenheim-Skolem — ainsi que la signification philosophique de la logique du premier ordre en tant que cadre canonique pour la formalisation des arguments et pour les fondements des mathématiques.
Core questions
- Quelle est la portée expressive de la logique du premier ordre, et qu'est-ce qui ne peut pas y être exprimé ?
- Pourquoi la logique du premier ordre est-elle souvent considérée comme la logique privilégiée pour la formalisation ?
- Que nous apprennent la complétude et la compacité sur la relation entre la syntaxe et la sémantique ?
- Quels sont les coûts et les avantages philosophiques du passage au second ordre ?
Key concepts
- connecteurs vérifonctionnels
- quantificateurs et variables
- satisfaction et modèles
- complétude et compacité
- théorèmes de Löwenheim-Skolem
- logique du premier ordre vs. logique du second ordre
Key theories
- Complétude de la logique du premier ordre
- Le théorème de complétude de Gödel établit que toute conséquence sémantique du premier ordre est prouvable dans un système déductif standard, de sorte que la dérivabilité et la validité en théorie des modèles coïncident pour la logique du premier ordre.
- Orthodoxie du premier ordre
- Quine défend la restriction de la logique canonique au premier ordre, arguant qu'elle est complète, ontologiquement perspicace et exempte des engagements ensemblistes et de l'incomplétude de la logique du second ordre.
History
La Begriffsschrift de Frege en 1879 a introduit la notation quantificateur-variable et le premier système de logique des prédicats, anticipé indépendamment par Peirce. La métathéorie a été établie au début du XXe siècle avec le théorème de complétude de Gödel (1929) et les résultats de compacité et de Löwenheim-Skolem, après quoi Quine et d'autres ont promu la logique du premier ordre comme cadre logique canonique.
Debates
- La logique du premier ordre est-elle la bonne logique canonique ?
- La question de savoir si la logique devrait être limitée au premier ordre, compte tenu de sa complétude et de sa clarté ontologique, ou étendue à la logique du second ordre pour une plus grande puissance expressive au prix de la complétude et d'engagements mathématiques plus lourds.
Key figures
- Gottlob Frege
- Kurt Godel
- W. V. O. Quine
- Charles Sanders Peirce
- Herbert Enderton
Related topics
Seminal works
- frege1879
- quine1986
Frequently asked questions
- Quelle est la différence entre la logique du premier ordre et la logique du second ordre ?
- La logique du premier ordre ne quantifie que sur des objets individuels dans un domaine. La logique du second ordre permet également la quantification sur les propriétés, les relations et les fonctions de ces objets. La logique du second ordre est beaucoup plus expressive mais manque d'un système de preuve complet et implique des engagements mathématiques plus forts, c'est pourquoi de nombreux philosophes traitent la logique du premier ordre comme canonique.