Cours Introduction à la logique classique - Logique classique du premier ordre

Jacques Jayez, Ens-Lsh, L2c2

Description

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 ...

Informations

• Publié par: Irda
• Nombre de lectures: 135
• Langue: Français

Extrait

J. Jayez – LC du premier ordree

Cours

1/ 20

Introduction à la logique classique

Logique classique du premier ordre

Jacques Jayez , ENS-LSH, L2C2

2008-2009, semestre 1

J. Jayez – LC du premier ordree 2/ 20

Syntaxe

Syntaxe I

◮ 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.

)2( JyaJ.L–zepudCmireorereedr205/ IVxetayn e S axntSy (1)

)3( Ve ynta /20 S ntax xe Sy –zCLaJey.Jree6rordemiedupr

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).