Remerciez-le!

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

Langage de la logique des prédicats: Introduction et motivation En logique prop

Langage de la logique des prédicats: Introduction et motivation En logique propositionnelle on se limite à des connecteurs propositionnels (connecteurs associant des propositions, et non des variables et des propositions). Ceci ne permet pas de rendre compte de raisonnements comme le suivant. TOUT être humain est mortel. OR Socrate est un être humain. DONC Socrate est mortel. Ce raisonnement repose sur une analyse plus fine des énoncés en termes d'énoncés génériques (`tout être humain est...') et énoncés singuliers (`Socrate est...'). Il utilise les notions d'objet et de propriété des objets. On écrit les propriétés d'objets sous la forme être-humain(Socrate). Socrate est l'objet, et être-humain est la propriété. C'est un énoncé singulier. Les énoncés génériques nécessitent l'emploi du quantificateur universel ∀. Ainsi, `` TOUT être humain est mortel '' peut être traduit comme ( x) (être-humain(x) -> ∀ mortel(x)) . Une notion plus générale que celle de propriété est celle de prédicat, qui permet d'exprimer une relation entre plusieurs objets, comme père(Jean,Pierre) ou plus_petit_que(3,7). Un prédicat a zéro, un, ou plusieurs arguments. Les variables propositionnelles peuvent être vus comme des prédicats à zéro arguments. La logique des prédicats est aussi appellée logique des prédicats du premier ordre, par oposition à la logique des prédicats de second ordre qui admettent la quantification non seulement sur des objets mais aussi sur des prédicats, ce qui leur permet de représenter la théorie des ensembles (la logique propositionnelle peut être vue comme logique des prédicats d'ordre zéro) Définition (alphabet). L'alphabet de la logique des prédicats est constitué de un ensemble dénombrable de symboles de prédicats à 0, 1, ou plusieurs arguments, notés p, q, r, ..., homme, mortel, père, ... un ensemble dénombrable de variables d'objets (ou variables d'individu), notées x, y, z, x1, x2, ... un ensemble dénombrable de fonctions à 0, 1, ou plusieurs arguments, notées f, g, ... , père-de, ... les quantificateurs , ∀∃ les connecteurs FALSE, ~, , , -> ∧∨ ainsi que les parenthèses de la logique propositionnelle Notation. Q dénote un quantificateur quelconque, c-à-d ∀ ou ∃. Les fonctions à 0 arguments sont appellées constantes et sont notés sans parenthèses ( a, b, ..., Socrate, ...). Même chose pour les prédicats à 0 arguments, qui ne sont rien d'autre que des variables propositionnelles. Définition (terme). L'ensemble des termes est le plus petit ensemble de mots construits sur l'alphabet de la logique des prédicats tel que toute variable est un terme f(t1,...,tn) est un terme si f est une fonction à n arguments et t1,...,tn sont des termes Définition (formule). Si p est un prédicat à n arguments et t1,...,tn sont des termes alors p(t1,...,tn) est une formule atomique. L'ensemble FOR des formules (ou formules bien formées) de la logique des prédicats est alors défini de la même manière qu'en logique propositionnelle, en rajoutant une clause pour les quantificateurs : (Q x A) est une formule si Q est un quantificateur, x une variable et A une formule Définition plus explicite des formules Définition. L'ensemble FOR des formules (ou formules bien formées) de la logique des prédicats est le plus petit ensemble de mots construits sur l'alphabet tel que si p est un prédicat à n arguments et t1,...,tn sont des termes alors p(t1,...,tn) est une formule (aussi appellé formule atomique) (Q x A) est une formule si A est une formule, Q un quantificateur et x une variable FALSE est une formule (~A) est une formule si A est une formule (A B), (A B), (A -> B) ∧ ∨ sont des formules si A et B sont des formules Langage de la logique des prédicats : exemples de traduction d'énoncés en formules `` Tout est relatif. '' x relatif(x) ∀ `` Une porte est ouverte ou fermée. '' x (porte(x) -> (ouvert(x) fermé(x)) ∀ ∨ `` Une porte est ou bien ouverte ou bien fermée. '' x ( porte(x) -> ((ouvert(x) fermé(x)) ~(ouvert(x) fermé(x)) ) ∀ ∨ ∧ ∧ `` Tout ce qui brille n'est pas or. '' ~ x (brille(x) -> or(x)) ∀ `` Il y a des peines, il y a des plaisirs, mais aucune peine n'est un plaisir. '' ( x peine(x)) ( x plaisir(x)) & x (peine(x) -> ~plaisir(x)) ∃ ∧∃ ∀ `` Tous les chemins mènent à Rome. '' x (chemin(x) -> mème-à(x,Rome)) ∀ `` Pour tout entier il existe un entier plus grand. '' x (entier(x) -> y (entier(y) plus-grand(y,x)) ) ∀ ∃ ∧ `` Il existe un plus grand entier. '' x (entier(x) y (entier(y) -> plus-grand(x,y)) ) ∃ ∧∀ Remarque sur les connecteurs primitifs Remarque. Notre présentation avec les connecteurs primitifs ∀ et ∃ peut être remplacée par une présentation avec seulement l'un des deux primitif : Si ∀ est primitif alors ∃ peut être défini en tant que abréviation : x A ∃ abrévie ~ x ~A ∀ .  Si ∃ est primitif alors ∀ peut être défini en tant que abréviation : x A ∀ abrévie ~ x ~A ∃ . Logique des prédicats : langage (suite) Définition (portée d'un quantificateur, variable libre). Dans les formules ( x A) ∀ et ( x A) ∃ , la formule A est appellé la portée du quantificateur. Une occurrence d'une variable est libre si elle n'est dans la portée d'aucun quantificateur. Sinon elle est liée. Exemples Dans ∀y ((p(x) x p(x)) q(y)) ∨∃ ∧ la première occurrence de x est libre, tandis que la deuxième occurrence est liée. L'occurrence de y est liée. Définition (formule fermée, formule ouverte). Une formule est fermée (ou close) si elle ne contient pas de variables libres. Sinon elle est ouverte. Exemples La formule A = y ((p(x) x p(x)) q(y)) ∀ ∨∃ ∧ est ouverte, car il y a une occurrence de variable libre. La formule x y ((p(x) x p(x)) q(y)) ∀∀ ∨∃ ∧ est fermée (c'est la fermeture universelle de A). La formule x y ((p(x) x p(x)) q(y)) ∃∀ ∨∃ ∧ est également fermée (c'est la fermeture existentielle de A). Définition (substitution de variables). Une substitution de variables est une application des variables dans les termes qui est l'identité presque partout. L'application d'une substitution à une expression E est le résultat du remplacement simultanée de toutes les occurrences libres des variables dans E par leur terme associé. Si E est une expression alors (E)s est appelé une instance de E. La composition de substitutions est la composition de fonctions. Notation. Soit {x1 , ... , xn} l'ensemble des variables tel que s(x) est différent de x . La substitution s est alors notée s = {x1\t1 , ... , xn\tn}. Remarque sur une définition plus explicite de la substitution Remarque. Une définition plus explicite est la suivante : une substitution de variables est un ensemble fini de couples associant à une variable un terme, notée s = {x1\t1 , ... , xn\tn} tel que xi = xj implique i = j. L'application de s à une formule A (notée (A)s) est le résultat du remplacement simultané dans A de toutes les occurrences libres de chaque xi par ti. Soient s1 et s2 deux substitutions, et soit s1 = {x1\t1 , ... , xn\tn}. Alors la composition de s1 et s2 est s1 o s2 = {x1\(t1)s , ... , xn\(tn)s} U s2 (où U denote l'union ensembliste). Exemples de substitutions (p(x) q(x,y)){x\z} ∨ = p(z) q(z,y) ∨ (p(x) q(x,y)){x\y} ∨ = p(y) q(y,y) ∨ ( x q(x,y)){x\z} ∀ = x q(x,y) ∀ (p(x) q(x,y)) ∨ {x\z,y\z} = p(z) q(z,z) ∨ (p(x) q(x,y)){x\f(x)} ∨ = p(f(x)) ∨ q(f(x),y) (p(x) q(x,y)) ∨ {x\y,y\a} = p(y) q(y,a) ∨ (p(x) q(x,y)) ∨ {x\y,y\x} = p(y) q(y,x) ∨ N.B. : les trois dernières substitutions sont particulières : dans {x\f(x)}, la variable substituée apparaît dans le terme, et n'est donc pas éliminé lors de l'application de la substitution ; dans {x\y,y\a} et {x\y,y\x}, la variable y apparaît et comme variable à substituer et dans le terme remplaçant x, et n'est donc également pas éliminé lors de l'application de la substitution. Ces deux cas de figure seront exclus dans la définition des unifieurs. Logique des prédicats : théorie des modèles Introduction et motivation Comme en logique propositionnelle, on fixe d'abord un ensemble de modèles (aussi appellés valuations ou interpretations). Ensuite, pour un modèle donné, on stipule des conditions de vérité permettant d'établir pour n'importe quelle formule A du langage si A est vraie ou fausse dans ce modèle. Pour donner un `sens' aux variables, constantes et fonctions du langage, il faut un domaine d'objets (ou domaine d'individu, ou univers de discours). À chaque variable et constante sera associé un élément du domaine. À chaque fonction sera associé une application dans le domaine. Ensuite, pour pouvoir donner un `sens' aux formules, il faut une fonction associant à chaque symbole de prédicat à n places l'ensemble des n-uplets d'éléments du domaine qui le rendent vrai. Finalement, l'interprétation d'une formule A se fait comme en logique propositionnelle : I(A) prend une valeur dans l'ensemble {0,1} (`vrai'/`faux'), où la quantification universelle x A ∀ est interprétée comme `pour toute interprétation uploads/Philosophie/ cours-de-logique-des-predicats.pdf