J. Jayez – LC du premier ordree 1/ 20Cours Introduction à la logique classiqueLogique classique du premier ordreJacques Jayez, ENS-LSH, L2C22008-2009, semestre 1J. Jayez – LC du premier ordree 2/ 20SyntaxeSyntaxe I◮ Par rapport à la logique propositionnelle, la logiquedu premier ordre offre la possibilité de désigner desindividus et de quantifier sur eux.◮ On conserve les opérateurs à une place (la néga-tion) ou à deux places (disjonction, conjonction,implication).◮ On ajoute des termes, qui permettent de désigner desindividus.◮ On ajoute également deux quantificateurs∃ et ∀.J. Jayez – LC du premier ordree 3/ 20SyntaxeSyntaxe II◮ Les termes sont des variables (x, y, x ), des constantes (c ) et desi ifonctions (f(t ...t )), où les t sont des termes.1 n i◮ Ex. : x, x +2 (la fonction +2 appliquée à x), 3 (un constante),3+2 (la fonction +2 appliquée à la constante 3).◮ ∃ affirme l’existence d’au moins un individu qui vérifie unecertain relation, par ex.,∃x(x ∈N&x > 5) = il existe au moinsun individu qui un entier naturel supérieur à 5.◮ ∀ affirme que tous les individus vérifient une certaine relation,par ex.,∀x(x ∈N⇒ x ≥ 0) = pour tous les individus x, si x estun entier x est supérieur ou égal à 0.J. Jayez – LC du premier ordree 4/ 20SyntaxeSyntaxe III◮ On se donne un vocabulaire (plus riche que celui dela logique propositionnelle).◮ Le vocabulaire V comprend un ensemble infini dé-nombrable de variables, un ensemble de constantes,un ensemble de ...
◮ Par rapport à la logique propositionnelle, la logique du premier ordre offre la possibilité de désigner des individus et de quantifier sur eux. ◮ On conserve les opérateurs à une place (la néga-tion) ou à deux places (disjonction, conjonction, implication). ◮ On ajoute des termes , qui permettent de désigner des individus. ◮ On ajoute également deux quantificateurs ∃ et ∀ .
J. Jayez – LC du premier ordree 3/ 20
Syntaxe
Syntaxe II
◮ Les termes sont des variables ( x , y , x i ), des constantes ( c i ) et des fonctions ( f ( t 1 t n ) ), où les t i sont des termes. ◮ Ex. : x , x + 2 (la fonction + 2 appliquée à x ), 3 (un constante), 3 + 2 (la fonction + 2 appliquée à la constante 3). ◮ ∃ affirme l’existence d’au moins un individu qui vérifie une certain relation, par ex., ∃ x ( x ∈ N & x > 5 ) = il existe au moins un individu qui un entier naturel supérieur à 5. ◮ ∀ affirme que tous les individus vérifient une certaine relation, par ex., ∀ x ( x ∈ N ⇒ x ≥ 0 ) = pour tous les individus x , si x est un entier x est supérieur ou égal à 0.
J. Jayez – LC du premier ordree
Syntaxe
Syntaxe III
4/ 20
◮ On se donne un vocabulaire (plus riche que celui de la logique propositionnelle). ◮ Le vocabulaire V comprend un ensemble infini dé-nombrable de variables, un ensemble de constantes, un ensemble de symboles de fonction et de relations ( R n , etc.), ainsi que le symbole de l’égalité ‘=’.
Une formule atomique est n’importe quelle expression de forme t 1 = t 2 , où t 1 et t 2 sont des termes, ou de forme R ( t 1 t n ) où R est un symbole de relation (à n places) et les t i sont des termes. Ex. : P ( x ) , R ( x c i ) , R ( c j f ( x y )) sont des formules atomiques.
On appelle terme soit une variable, soit un symbole de constante, soit une forme f ( t 1 t n ) , où f est une fn à n places et les t i sont des termes.
◮ On définit les termes (qui dénotent des individus). ◮ Ensuite, on crée les formules atomiques, les briques élémentaires qui correspondent aux propositions.
On appelle formule n’importe quelle expression A qui obéit à une des conditions suivantes. a. A est une formule atomique b. A = ¬ B , et B est une formule. c. A = B ∨ C , ou A = B & C , ou A = B ⇒ C et B et C sont des formules. d. A = ∃ xB et x est une variable et B une formule. e. A = ∀ xB et x est une variable et B une formule.
◮ Finalement, on rajoute les quantificateurs.
J. Jayez – LC du premier ordree 7/ 20
Sémantique
Sémantique I
◮ En gros, une variable est dite liée quand elle est dans le champ d’un quantificateur, sinon elle est libre . ◮ En fait, la situation est plus compliquée parce que ce sont les occurrences de variable qui sont libres ou liées, pas les variables elles-mêmes. ◮ Lorsqu’on dit qu’une variable est libre, cela signifie qu’elle a au moins une occurrence libre dans une formule. ◮ ∃ x ( P ( x y )) & ∀ z ( P ′ ( z x )) : première occurrence de x liée, seconde occurrence libre, y libre, z liée.
J. Jayez – LC du premier ordree 8/ 20
Sémantique
Sémantique II
◮ Les constantes, les (occurrences de) variables liées, et, plus généralement, les termes sans variables libres ont une interprétation fixe (un individu particulier). ◮ Les (occurrences de) variables libres ont une inter-prétation qui dépend de ce qu’on appelle une fonction d’assignation (ou assignation ). ◮ Un exemple jouet. Un langage L avec une seule relation R à deux places, une fonction f à un place, deux variables x et y , et une constante c 1 .
J. Jayez – LC du premier ordree 9/ 20 Sémantique
Sémantique III
◮ On se donne un domaine de deux individus D = { a b } et une interprétation I qui fixe l’interprétation de R , f et c . ◮ I ( R ) = {h a b i} , I ( f ) = {h a b i h b b i} , I ( c 1 ) = b . ◮ On a deux variables et deux individus, on aura donc 4 assignations possibles.
g 1 g 2 g 3 g 4 g 1 ( x ) = a g 2 ( x ) = a g 3 ( x ) = b g 4 ( x ) = b g 1 ( y ) = a g 2 ( y ) = b g 3 ( y ) = a g 4 ( y ) = b
J. Jayez – LC du premier ordree 10/ 20
Sémantique
Sémantique IV
◮ Appelons M (modèle) le couple D I . ◮ M g | = A signifie que M satisfait φ modulo l’assigna-tion g . ◮ Ex. : M g 2 | = R ( x y ) , M g 4 | = f ( x ) = y , M g 2 | = f ( x ) = c 1 , etc. ◮ Sens de M g 3 | = ∃ x ( R ( x c 1 )) ?
J. Jayez – LC du premier ordree 11/ 20
Sémantique
Sémantique V
◮ Deux interprétations possibles a priori ◮ On remplace x par g 3 ( x ) et on regarde si R ( g 3 ( x ) c 1 ) est vrai, c.a.d. si h b b i ∈ I ( R ) . ◮ On regarde s’il existe un individu qui, substitué à x , vérifie R ( x c 1 ) . ◮ C’est la première interprétation qui est la bonne, parce qu’elle permet de distinguer entre M g 3 | = ∃ x ( R ( x c 1 )) (vrai) et M g 3 | = R ( x c 1 ) (faux).