Remerciez-le!

Remerciez @Admin pour avoir partagé cet document gratuitement, de la manière la plus simple, en partageant sur les réseaux sociaux.

Calcul des prédicats Le calcul des prédicats du premier ordre, ou calcul des re

Calcul des prédicats Le calcul des prédicats du premier ordre, ou calcul des relations, logique du premier ordre, logique quantificationnelle, ou tout simplement calcul des prédicats, est une formalisation du langage des mathématiques, proposée par Gottlob Frege, entre la fin du XIXe siècle et le début du XXe siècle. La logique du premier ordre comporte deux parties : la syntaxe définit le vocabulaire symbolique de base ainsi que les règles permettant de construire des énoncés complexes, la sémantique interprète ces énoncés comme exprimant des relations entre les éléments d'un domaine, également appelé modèle. Sur le plan syntaxique, les langages du premier ordre opposent deux grandes classes linguistiques : les constituants servant à identifier ou nommer des éléments du domaine : variables, symboles de constantes, termes ; les constituants servant à exprimer des propriétés ou des relations entre ces éléments : prédicats et formules. Un prédicat est une expression linguistique qui peut être reliée à un ou plusieurs éléments du domaine pour former une phrase. Par exemple, dans la phrase « Mars est une planète », l'expression « est une planète » est un prédicat qui est relié au nom (symbole de constante) « Mars » pour former une phrase. Et dans la phrase « Jupiter est plus grand que Mars », l'expression « est plus grand que » est un prédicat qui se relie aux deux noms, « Jupiter » et « Mars », pour former une phrase. En logique mathématique, lorsqu'un prédicat est lié à une expression, on dit qu'il exprime une propriété (telle que la propriété d'être une planète), et lorsqu'il est lié à deux ou plusieurs expressions, on dit qu'il exprime une relation (telle que la relation d'être plus grand). Ainsi on peut raisonner sur des énoncés comme « Tout est gentil » et « Il existe un tel que pour tout , est ami avec », ce qui exprimé symboliquement se traduit par la formule : et . Il convient de noter cependant que la logique du premier ordre ne contient aucune relation spécifique (comme telle relation d'ordre, d'inclusion ou d'égalité) ; en fait, il ne s'agit que d'étudier la façon dont on doit parler et raisonner avec les expressions du langage mathématique. Les traits caractéristiques de la logique du premier ordre sont : l'utilisation de variables comme , etc. pour dénoter des éléments du domaine d'interprétation ; l'utilisation de prédicats (ou relations) sur les éléments ; l'utilisation de connecteurs logiques (et, ou, implique etc.) ; l'utilisation de deux quantificateurs, l'un universel (« Quel que soit », « pour tout » noté ∀) et l'autre existentiel (« il existe au moins un … tel que », noté ∃). Le calcul des prédicats du premier ordre égalitaire adjoint au calcul des prédicats un symbole de relation, l'égalité, dont l'interprétation est l'affirmation que deux éléments sont les mêmes, et qui est axiomatisée en conséquence. Suivant le contexte, on peut parler simplement de calcul des prédicats pour le calcul des prédicats égalitaire. On parle de logique du premier ordre par opposition aux logiques d'ordre supérieur, où l'on peut aussi quantifier sur les prédicats ou les fonctions en plus des variables. En outre, cet article ne traite que de la logique du premier ordre classique, mais on notera qu'il existe aussi une logique du premier ordre intuitionniste. Introduction Histoire Syntaxe Définition Exemples Prédicats, formules closes, formules polies, variables libres, variables liées Sémantique Modèle Conditions de vérité Formule satisfaisable Formule valide Conséquence sémantique Système de déduction Propriétés Complétude Indécidabilité Compacité Expressivité Théorème de Löwenheim-Skolem Incomplétude Fragments décidables Variantes Notes et références Notes Références Annexes Articles connexes Bibliographie Alors que la logique propositionnelle traite des propositions déclaratives simples, la logique du premier ordre couvre en plus les prédicats et la quantification. Sommaire Introduction Un prédicat prend en entrée une ou plusieurs entités du domaine du discours et en sortie, il est soit Vrai, soit Faux. Considérons les deux phrases "Socrate est un philosophe" et "Platon est un philosophe". En logique propositionnelle, ces phrases sont considérées comme non liées et peuvent être désignées, par exemple, par des variables telles que p et q. Le prédicat "est un philosophe" apparaît dans les deux phrases, dont la structure commune est "a est un philosophe". La variable a est instanciée en tant que "Socrate" dans la première phrase, et est instanciée en tant que "Platon" dans la deuxième phrase. Alors que la logique du premier ordre permet l'utilisation de prédicats, tels que "est un philosophe" dans cet exemple, la logique propositionnelle ne le permet pas. Les relations entre les prédicats peuvent être énoncées à l'aide de connecteurs logiques. Considérons, par exemple, la formule du premier ordre "si a est un philosophe, alors a est un savant". Cette formule est un énoncé conditionnel dont l'hypothèse est " a est un philosophe " et la conclusion " a est un savant ". La vérité de cette formule dépend de l'objet désigné par a, et des interprétations des prédicats "est un philosophe" et "est un savant". Les quantificateurs peuvent être appliqués aux variables d'une formule. La variable a de la formule précédente peut être quantifiée universellement, par exemple avec la phrase du premier ordre "Pour tout a, si a est un philosophe, alors a est un savant". Le quantificateur universel "pour chaque" dans cette phrase exprime l'idée que l'affirmation "si a est un philosophe, alors a est un savant" est valable pour tous les choix de a. La négation de la phrase "Pour tout a, si a est un philosophe, alors a est un savant" est logiquement équivalente à la phrase "Il existe a tel que a est un philosophe et a n'est pas un savant". Le quantificateur existentiel "il existe" exprime l'idée que l'affirmation "a est un philosophe et a n'est pas un savant" est valable pour un certain choix de a. Les prédicats "est un philosophe" et "est un savant" prennent chacun une seule variable. En général, les prédicats peuvent prendre plusieurs variables. Dans la phrase du premier ordre "Socrate est le professeur de Platon", le prédicat "est le professeur de" prend deux variables. Emmanuel Kant croyait à tort que la logique de son temps, celle d’Aristote, était une science complète et définitivement achevée (préface de la seconde édition de la critique de la raison pure, 1787 ). Les logiciens du XIXe siècle se sont rendu compte que la théorie d’Aristote ne dit rien ou presque sur la logique des relations. Gottlob Frege et beaucoup d'autres ont comblé cette lacune en définissant le calcul des prédicats au premier ordre. Kurt Gödel a démontré en 1929 (dans sa thèse de doctorat) que le calcul des prédicats est complet, au sens où on peut donner un nombre fini de principes (axiomes logiques, schémas d'axiomes logiques et règles de déduction ) qui suffisent pour déduire de façon mécanique toutes les lois logiques (voir le théorème de complétude de Gödel). Il y a équivalence entre la présentation sémantique et la présentation syntaxique du calcul des prédicats. Tout énoncé universellement valide (c'est-à-dire vrai dans tout modèle du langage utilisé) est un théorème (c'est-à-dire qu'il peut être déduit d'un calcul, un système de règles logiques et d'axiomes, de façon équivalente un système à la Hilbert, la déduction naturelle, ou le calcul des séquents), et réciproquement. La logique du premier ordre est donc achevée au sens où le problème de la correction logique des démonstrations y est résolu. Elle continue cependant à faire l’objet d’importantes recherches : théorie des modèles, théorie de la démonstration, mécanisation du raisonnement… Histoire 1 2 3 Syntaxe Exemple d'une formule de la logique du premier ordre. Le schéma montre les quantificateurs, les occurrences des symboles de fonctions et des symboles de prédicats. Cette section donne une brève présentation de la syntaxe du langage formel du calcul des prédicats. On se donne pour alphabet : un ensemble de symboles appelés variables, toujours infini : , , , etc. ; un ensemble de symboles appelés constantes, éventuellement vide : , , , etc. ; un ensemble de symboles de fonctions : , , , etc. ; un ensemble de symboles de prédicats : , , , etc. Chaque symbole de fonction et chaque symbole de prédicat a une arité : il s'agit du nombre d'arguments ou d'objets auxquels il est appliqué. Par exemple, le prédicat pour « est bleu(e) » a une arité égale à 1 (on dit qu'il est unaire ou monadique), tandis que le prédicat pour « être amis » a une arité de deux (on dit qu'il est binaire ou dyadique). Les symboles (quel que soit) et (il existe), appelés quantificateurs. Les symboles (non), (et), (ou) et (implique), qui sont des connecteurs que possède aussi le calcul des propositions. Les symboles de ponctuation « ) » et « ( ». On pourrait se contenter d'un seul quantificateur et de deux connecteurs logiques et en définissant les autres connecteurs et quantificateur à partir de ceux-ci. Par exemple est défini comme . Les formules du calcul des prédicats du premier ordre sont définies par induction : si un symbole de uploads/Philosophie/ calcul-des-predicats.pdf