Formalismes linguistiques – Logique du premier ordre © 2005-2006 R.

Marlet
1

Cours de formalismes linguistiques

Master 1 — 2005-2006

Logique du premier ordre

Application en linguistique

Renaud Marlet

LaBRI / INRIA
[Link]
màj : 07/02/2006
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
2

Objectif

●
Se donner un langage formel pour exprimer la
sémantique, ici sous un aspect logique
– pouvoir représenter des faits / des états du monde
– pouvoir juger vrais ou faux des énoncés relatifs à cette
connaissance du monde
●
N.B. On ne juge pas ici si le monde « réel » est fidèlement
représenté ; ce monde peut être « imaginaire »
●
On se contente de juger la véracité de certains énoncés par
rapport à une connaissance donnée (arbitraire) du monde
●
(Savoir associer à une phrase en langue naturelle
sa ou ses sémantiques logiques, quand il y en a)
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
3

Au programme
●
Vocabulaire
– briques de base d'une représentation sémantique
●
Modèle
– sens effectivement donné à un vocabulaire
●
Langage du premier ordre
– énoncé → formule logique basée sur le vocabulaire
– véracité d'une phrase par rapport à un/des modèle(s)
●
Lambda-calcul
– construction compositionnelle d'une formule logique
associée à une phrase en langue naturelle
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
4

Rappel mathématique

Relation R sur un ensemble E

R = ensemble d'éléments choisis dans E × E
Exemples pour E = {0,1}
R = {(1,1)}, R = {(0,0),(0,1),(1,1)}, ...
Notation (pour tout x et y  E)
x R y ssi (x,y)  R [ on note aussi R(x,y) ]
Plus généralement (relation d'arité n):
R = ensemble d'éléments choisis dans E1 × ... × En
Notation : R(x1, ..., xn), R(x), R(x,y,z)
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
5

Vocabulaire
d'après « Computational Semantics »
(Burchart, Walter, Koller, Kohlhase, Blackburn, Bos)

Vocabulaire (termes/briques de base)

– constantes
●
ex. Marie, Jean, Anne, Pierre
– prédicats (relations)
●
ex. aime, violoniste, gastronome
●
exemple d'usage : aime(Pierre,Marie)
– arité = nombre d'arguments d'un prédicat
●
ex. arité de aime = 2
●
ex. arité de violoniste et de gastronome = 1
Notation :
({Marie, Jean, Anne, Pierre}, {aime/2, violoniste/1, gastronome/1})
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
6

Vue d'ensemble (1)

Lexique Vocabulaire
syntaxique sémantique

Phrases
Phrases
/ formules
grammaticales
utilisant le
utilisant le
vocabulaire
lexique
sémantique
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
7

Usage des symboles

●
Le sens du vocabulaire est arbitraire
– Il est juste constitué de symboles
●
On pourrait (!)
– dire que le symbole Pierre désigne Marie Curie
– dire que le symbole Marie désigne Pierre Curie
– dire que le symbole aime désigne l'action de réveiller
– et écrire aime(Pierre, Marie) pour signifier que Marie
Curie réveille son mari
●
Mais on ne le fera pas : on utilisera toujours les
symboles de façon « suggestive »
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
8

Modèle (intuition)

☛ Un modèle donne un sens à un vocabulaire

Intuitivement, un modèle est :
– une situation, une connaissance supposée de l'état du
monde
– exprimable à l'aide des symboles d'un vocabulaire
Un modèle est constitué par :
– un ensemble ayant pour éléments les « véritables »
entités dont on veut parler
– une correspondance entre les symboles du vocabulaire
et les entités / des faits concernant ces entités
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
9

Vue d'ensemble (2)

Lexique Vocabulaire interprétation

Entités
syntaxique sémantique

construction Modèle construction

Phrases
Phrases
/ formules Faits
grammaticales
utilisant le concernant
utilisant le satisfaction
vocabulaire les entités
lexique
sémantique
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
10

Modèle (définition formelle)

Un modèle M est défini par M = (D, F) tel que :

– D est un domaine
[c'est l'ensemble des entités dont on veut parler]
– F est une fonction d'interprétation
[c'est la correspondance entre symboles et entités/faits]
● Si c est une constante, F(c) ∈ D
●
Si p est un prédicat d'arité n, F(p) est une relation d'arité n
dans D
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
11

Exemple de modèle

Domaine D = {d1,d2,d3,d4}
Fonction d'interprétation F définie par :
● F(Marie) = d1
● F(Anne) = d2
● F(Jean) = d3
● F(Pierre) = d4
● F(violoniste) = {d1,d3} → Marie et Jean sont violonistes
● F(gastronome) = {d2,d4} → Anne et Pierre sont gastronomes
● F(aime) = {(d4,d2),(d3,d1)} → Pierre aime Anne, Jean aime Marie
(mais Anne n'aime pas Pierre,
Anne n'aime pas Jean, ...)
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
12
Exercice :
Donnez une description en français
● D = {d1,d2,d3,d4}
● F2(Marie) = d2
● F2(Anne) = d1
● F2(Jean) = d4
● F2(Pierre) = d3
● F2(violoniste) = {d1,d2,d4}
● F2(gastronome) = {d3}
● F2(aime) = {(d4,d1)}
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
13
Exercice :
Donnez une description en français
● D = {d1,d2,d3,d4}
● F2(Marie) = d2
● F2(Anne) = d1
● F2(Jean) = d4
● F2(Pierre) = d3
● F2(violoniste) = {d1,d2,d4}
● F2(gastronome) = {d3}
● F2(aime) = {(d4,d1)}
→ Il y a quatre entités : Anne, Marie, Pierre, Jean. Anne,
Marie et Jean sont violonistes. Pierre est gastronome.
Jean aime Anne. Et rien d'autre.
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
14

Remarques

– Une entité peut avoir plusieurs noms, c.-à-d. être

associée à plusieurs constantes du vocabulaire
● D = {d1}
● F(Marie) = d1
● F(Anne) = d1
– Des entités peuvent ne pas être nommées, c.-à-d. ne
pas être associées à une constante du vocabulaire
● D = {d1,d2,d3,d4}
● F(Marie) = d1
● F(Anne) = d2
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
15

Modèle exact

Définition : un modèle M = (D, F) est exact ssi

chaque entité de D correspond à une et une
seule constante du vocabulaire
Exemple :
constantes : Marie, Anne, Jean, Pierre
domaine : D = {d1,d2,d3,d4}
fonction d'interprétation : F(Marie) = d1
F(Anne) = d2
F(Jean) = d3
F(Pierre) = d4
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
16

Modèle inexact

Définition : un modèle M = (D, F) est inexact ssi il

n'est pas exact
– à une entité peut correspondre plusieurs constantes
● D = {d1}
● F(Marie) = d1
● F(Anne) = d1
– certaines entités peuvent ne pas être nommées
● D = {d1,d2,d3,d4}
● F(Marie) = d1
● F(Anne) = d2
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
17

Modèle inexact

Un modèle est inexact ssi il n'est pas exact : [rappel]

– à une entité peut correspondre plusieurs constantes
– certaines entités peuvent ne pas être nommées
Attention !
– Un modèle inexact n'est pas faux, incohérent, ambigu...
– C'est juste un modèle avec lequel c'est peu pratique de
travailler (en particulier si D est infini)
– Mais pour la plupart des problèmes, on utilise des
modèles exacts, plus faciles à représenter et presque
aussi « puissants » [cf. modèles de Herbrand]
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
18

Plan

On a vu :
– vocabulaire : briques de base
– modèle : sens donné à un vocabulaire

On va voir :
– construction de phrases qui utilisent ce vocabulaire
→ langage du premier ordre : formule logique
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
19

Langages du premier ordre :

ingrédients
– les symboles d'un vocabulaire (aussi appelés
symboles non logiques)
– un ensemble (infini) de variables : x, y, z, w, ...
– les quantificateurs
● ∀ (universel) et ∃ (existentiel)
– les connecteurs booléens
● ¬ (négation), ⇒ (implication), ∧ (conjonction), ∨ disjonction
– les parenthèses « ( » et « ) »
Ce qui distingue un langage du premier ordre d'un
autre : le choix du vocabulaire
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
20

Langages du premier ordre :

définitions (1)
Terme (du premier ordre) :
– Un terme est une constante ou une variable
Exemples :
– Pierre, Marie, x, y
Non-exemples :
– aime, violoniste

Exercice :
– Donnez d'autres exemples et non-exemples
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
21

Langages du premier ordre :

définitions (2)
Formule atomique :
– Si R est un symbole de relation d'arité n et t1, ..., tn
sont des termes, alors R(t1, ..., tn) est une formule
atomique
Exemples :
– violoniste(Pierre), aime(x,Marie)
Non-exemples :
– x, violoniste, gastronome(Jean,aime)

Exercice : Donnez d'autres exemples et non-exemples

Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
22

Langages du premier ordre :

définitions (3)
Formule bien formée (ou complexe) :
[en anglais : well-formed formula (wff)]
●
Une formule atomique est une formule bien formée
● Si  et  sont des formules bien formées alors ¬ , ( ⇒ ),
( ∧ ) et ( ∨ ) sont des formules bien formées
● Si  est une formule bien formée et x est une variable, alors
∀x  et ∃x  sont des formules bien formées
●
Rien d'autre n'est une formule bien formée [mais en pratique,
précédence des opérateurs pour éviter les parenthèses inutiles]

Ex. : violoniste(Jean), ∀x (violoniste(x) ⇒ aime(Marie,x))

Non-exemples : ¬Jean, gastronome(Pierre∧Jean), ∃Marie
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
23

Langages du premier ordre :

définitions (4)
Littéral
– formule atomique ou négation d'un formule atomique
Exemples
– violoniste(Pierre), ¬gastronome(Jean)
Non-exemples
– Pierre, ¬gastronome, violoniste(Pierre ∨ Jean)

Exercice :
– Donnez d'autres exemples et non-exemples
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
24

Interprétation linguistique (1) :

cas de figure courants
● ∀x P(x)
– Pour tout x, P(x)
– Tout est P
● ∀x gastronome(x)
●
Tout le monde, toute chose est gastronome
● ∀x ¬P(x) [ = ¬ ∃x P(x) ]
– Pour tout x, non P(x)
– Aucun x n'est tel que P(x)
– Il n'existe aucun x « de type P »
● ∀x ¬violoniste(x)
●
Personne, rien n'est violoniste
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
25

Interprétation linguistique (2) :

cas de figure courants
● ∀x (P(x) ⇒ Q(x))
– Pour tout x, si P(x) alors Q(x)
– Tous les x tels que P(x) sont tels que Q(x)
– Tout x « de type P » est « de type Q »
● ∀x (violoniste(x) ⇒ gastronome(x))
●
Tout violoniste est gastronome [= Tous les violonistes sont gastronomes]
● ∀x (P(x) ⇒ ¬Q(x))
– Pour tout x, si P(x) alors non Q(x)
– Aucun x tel que P(x) n'est tel que Q(x)
– Aucun x « de type P » n'est « de type Q »
● ∀x (violoniste(x) ⇒ ¬gastronome(x))
●
Aucun violoniste n'est gastronome
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
26

Interprétation linguistique (3) :

cas de figure courants
● ∃x P(x)
– Il existe un x tel que P(x)
– Il y a (au moins) un x « de type P »
● ∃x gastronome(x)
●
Il y a un(e) gastronome
● ∃x ¬P(x) [ = ¬ ∀x P(x) ]
– Il existe un x tel que non P(x)
– (Au moins) un x n'est pas « de type P »
● ∃x ¬violoniste(x)
●
Quelqu'un, quelque chose n'est pas violoniste
●
On ne peut pas dire que tout le monde est violoniste
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
27

Interprétation linguistique (4) :

cas de figure courants
● ∃x (P(x) ∧ Q(x)) [= ∃x (Q(x) ∧ P(x))]
– Il existe un x tel que P(x) et Q(x)
– Il existe un x à la fois « de type P et Q »
– Il existe un x « de type P » qui est aussi « de type Q »
● ∃x (violoniste(x) ∧ gastronome(x))
●
Il y a un violoniste gastronome [= il y a un gastronome violoniste]

● ∃x (P(x) ∧ ¬Q(x))
– Il existe un x tel que P(x) et non Q(x)
– Il existe un x « de type P » qui n'est pas « de type Q »
● ∃x (violoniste(x) ∧ ¬gastronome(x))
●
Il y a un violoniste qui n'est pas gastronome
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
28

Interprétation linguistique (5) :

cas de figure courants
Noter la différence entre quantificateurs :
– ∀x (P(x) ⇒ Q(x))
●
Tout x « de type P » est « de type Q »
– ∀x (P(x) ⇒ ¬Q(x))
●
Aucun x « de type P » n'est « de type Q »
– ∃x (P(x) ∧ Q(x))
●
Il existe un x « de type P » qui est aussi « de type Q »
– ∃x (P(x) ∧ ¬Q(x))
●
Il existe un x « de type P » qui n'est pas « de type Q »
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
29

Double interprétation de certaines

formes linguistiques
Un violoniste est gastronome
– ...
– ...
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
30

Double interprétation de certaines

formes linguistiques
Un violoniste est gastronome
– Un fait concernant un individu :
●
Il y a un violoniste qui est (aussi) gastronome
– Une règle générale :
●
Tout violoniste est gastronome
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
31

Double interprétation de certaines

formes linguistiques
Un violoniste est gastronome
– Un fait concernant un individu :
●
Il y a un violoniste qui est (aussi) gastronome
– Une règle générale :
●
Tout violoniste est gastronome

Un train peut en cacher un autre

– ...
Un chien aboie dans le lointain
– ...
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
32

Double interprétation de certaines

formes linguistiques
Un violoniste est gastronome
– Un fait concernant un individu :
●
Il y a un violoniste qui est (aussi) gastronome
– Une règle générale :
●
Tout violoniste est gastronome

Un train peut en cacher un autre

– cas = règle : tout train peut cacher tout autre train
Un chien aboie dans le lointain
– cas = individu : il y a un chien qui aboie dans le lointain
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
33

Exercice
Écrivez les formules bien formées
– Pierre est gastronome
●
...
– Marie aime un gastronome
●
...
– Marie aime un(e) gastronome mais elle n'aime pas Pierre
●
...
– Marie aime un(e) gastronome mais ce n'est pas Pierre
●
...
– Tous les gastronomes que Marie aime, Anne les aime aussi
●
...
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
34

Exercice
Écrivez les formules bien formées
– Pierre est gastronome
●
gastronome(Pierre)
– Marie aime un gastronome
● ∃x (gastronome(x) ∧ aime(Marie,x))
– Marie aime un(e) gastronome mais elle n'aime pas Pierre
● ∃x (gastronome(x) ∧ aime(Marie,x)) ∧ ¬aime(Marie,Pierre)
– Marie aime un(e) gastronome mais ce n'est pas Pierre
●
Ce n'est pas exprimable dans le langage :
● ∃x (gastronome(x) ∧ aime(Marie,x) ∧ x ≠ Pierre [pas dans le langage]

– Tous les gastronomes que Marie aime, Anne les aime aussi
● ∀x (gastronome(x) ∧ aime(Marie,x) ⇒ aime(Anne,x))
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
35

Exercice
Écrivez les formules bien formées
– Il existe quelqu'un qui s'appelle Marie
●
...
– Si Jean est gastronome, alors Pierre est violoniste
●
...
– Il y a un(e) violoniste qui aime un(e) gastronome
●
...
– Un violoniste aime tous les gastronomes
●
...
– Tous les violonistes gastronomes sont égoïstes
●
...
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
36

Exercice
Écrivez les formules bien formées
– Il existe quelqu'un qui s'appelle Marie
● Ce n'est pas exprimable dans le langage : ∃x x = Marie, ∃Marie
– Si Jean est gastronome, alors Pierre est violoniste
● gastronome(Jean) ⇒ violoniste(Pierre)
– Il y a un(e) violoniste qui aime un(e) gastronome
● ∃x ∃y (violoniste(x) ∧ gastronome(y) ∧ aime(x,y))
– Un violoniste aime tous les gastronomes
● ∃x (violoniste(x) ∧ ∀y (gastronome(y) ⇒ aime(x,y))) [un : individu]
● ∀x (violoniste(x) ⇒ ∀y (gastronome(y) ⇒ aime(x,y))) [un : règle]
– Tous les violonistes gastronomes sont égoïstes
● ∀x (violoniste(x) ∧ gastronome(x) ⇒ aime(x,x))
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
37

Exercice
Paraphrasez les formules logiques
– ∃x ∃y (violoniste(x) ∧ gastronome(y) ∧ aime(x,y))
●
...
– ∃y ∃x (violoniste(x) ∧ gastronome(y) ∧ aime(x,y))
● ...
– ∃x (violoniste(x) ∧ ∃y (gastronome(y) ∧ aime(x,y)))
●
...
– ∃x (violoniste(x) ∧ ∀y (gastronome(y) ⇒ ¬aime(x,y))
●
...
– ∀y (gastronome(y) ⇒ ∃x (violoniste(x) ∧ ¬aime(x,y))
●
...
– ∀y ∃x (gastronome(y) ⇒ (violoniste(x) ∧ ¬aime(x,y))
●
...
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
38

Exercice
Paraphrasez les formules logiques
– ∃x ∃y (violoniste(x) ∧ gastronome(y) ∧ aime(x,y))
– ∃y ∃x (violoniste(x) ∧ gastronome(y) ∧ aime(x,y))
– ∃x (violoniste(x) ∧ ∃y (gastronome(y) ∧ aime(x,y)))
●
Un violoniste aime un gastronome
– ∃x (violoniste(x) ∧ ∀y (gastronome(y) ⇒ ¬aime(x,y))
●
Il existe un violoniste qui n'est aimé par aucun gastronome
– ∀y (gastronome(y) ⇒ ∃x (violoniste(x) ∧ ¬aime(x,y))
●
Tout gastronome a un violoniste qu'il n'aime pas
●
Tout gastronome n'aime pas un violoniste
– ∀y ∃x (gastronome(y) ⇒ (violoniste(x) ∧ ¬aime(x,y))
●
Tout gastronome a un violoniste qu'il n'aime pas
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
39

Plan

On a vu :
– vocabulaire : briques de base
– modèle : sens donné à un vocabulaire
– langage du 1er ordre : phrases utilisant le vocabulaire

On va voir :
– valeur de vérité associée à ces phrases
→ notion de formule logique satisfaite
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
40

Variables libres, variables liées

Variable liée
Exemple : ∃x (violoniste(x) ∧ gastronome(x))

Exemple : ∀x (gastronome(x) ⇒ ∃y aime(x,y))

Variable libre
Exemple : ∃x (gastronome(y) ∧ violoniste(x))
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
41

Variables libres, variables liées :

Analogie dans la langue
Variable liée : phrase autonome/indépendante (self-contained)
● Exemple : ∃x (violoniste(x) ∧ gastronome(x))

Il existe un(e) violoniste gastronome

● Exemple : ∀x (gastronome(x) ⇒ ∃y aime(x,y))

Tout gastronome est aimé (de quelqu'un)

Variable libre : référent à trouver dans le contexte
● Exemple : ∃x (gastronome(y) ∧ violoniste(x))

Il/elle est gastronome et il y a un(e) violoniste

Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
42

Variable libre

Définition formelle (par induction) :

– Toute occurrence de variable est libre dans une
formule atomique
– Si une occurrence de variable est libre dans  ou
dans , alors cette occurrence est libre dans ¬,
( ⇒ ), ( ∧ ) et ( ∨ )
– Si une occurrence d'une variable x est libre dans ,
alors elle est libre dans ∀y  et dans ∃y  pour
toute variable y différente de x
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
43

Variable liée

Définition formelle (par induction) :

– Aucune occurrence de variable n'est liée dans une
formule atomique
– Si une occurrence de variable est liée dans  ou
dans , alors cette occurrence est liée dans ¬,
( ⇒ ), ( ∧ ), ( ∨ ), ∀x  et ∃x  pour
toute variable x
– Si une occurrence d'une variable x est libre dans ,
alors elle est liée dans ∀x  et dans ∃x 
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
44

Notion de satisfaction

●
On ne peut pas donner une définition « dans
l'absolu » de ce qui est vrai ou pas
●
On va dire ce qui est vrai dans un modèle
→ relation entre une phrase et un modèle (c.-à-d. une
connaissance de l'état du monde)
●
On va définir une relation de satisfaction entre
– une formule (≈ une phrase) 
– un modèle M = (D,F)
– une affectation de valeurs aux variables g
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
45

Affectation de (valeurs aux) variables

– Définition : une affectation de variables (ou affectation

de valeurs aux variables) est une application g de
l'ensemble des variables dans D
Ex. D = {d1,d2,d3,d4}
g(x) = d1 ; g(y) = d2 ; g(z) = d1 ; g(w) = d4 ; ...

– Soient x une variable et g une affectation de variables.

Une x-variante de g est une affectation de variables g'
telle que pour toute variable y ≠ x, g'(y) = g(y)
Ex. g'(x) = d1 ; g'(y) = d3 ; g'(z) = d1 ; g'(w) = d4 ; ...
g' est une y-variante de g (et réciproquement) mais
g' n'est pas une x-variante de g (et réciproquement)
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
46

Interprétation : définition

Soient M = (D,F) un modèle, g une affectation de

variables dans M et  un terme.
L'interprétation de  par rapport à M et g, notée
IgF(), est définie par :
– IgF() = F() si  est une constante
– IgF() = g() si  est une variable
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
47

Interprétation : exemple

– Modèle : M = (D,F)
– Domaine : D = {d1,d2,d3,d4}
– Fonction d'interprétation : F(violoniste) = {d1,d3}
F(Marie) = d1 F(Jean) = d3 F(gastronome) = {d2,d4}
F(Anne) = d2 F(Pierre) = d4 F(aime) = {(d4,d2),(d3,d1)}
– Affectation de variables :
g(x) = d1 ; g(y) = d3 ; g(z) = d1 ; g(w) = d4 ; ...
– Interprétation :
IgF(Marie) = F(Marie) = d1 IgF(Anne) = F(Anne) = d2
IgF(x) = g(x) = d1 IgF(y) = g(y) = d3
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
48

Satisfaction : définition
Soient M = (D,F) un modèle et g une affectation de variables dans M.
La relation de satisfaction « M, g ∣=  » ( est satisfaite dans M
par rapport à l'affectation de variables g) est définie par :

M, g ∣= R(1,...,n) ssi (IgF(1),...,IgF(n)) ∈ F(R)

M, g ∣= ¬ ssi non M, g ∣= 
M, g ∣=  ∧  ssi M, g ∣=  et M, g ∣= 
M, g ∣=  ∨  ssi M, g ∣=  ou M, g ∣= 
M, g ∣=  ⇒  ssi non M, g ∣=  ou M, g ∣= 
M, g ∣= ∃x  ssi non M, g' ∣=  pour une x-variante g' de g
M, g ∣= ∀x  ssi non M, g' ∣=  pour toute x-variante g' de g

Si M, g ∣=  n'est pas vrai, on note M, g ∣≠ 

Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
49

Satisfaction : exemples

M = (D,F) D = {d1,d2}
F(Marie) = d1 F(Jean) = d2 F(violoniste) = {d2} F(aime) = {(d1,d2)}
g(x) = d1 ; g(y) = d2 ; g(z) = d1 ; g(w) = d1 ; ...

On a :
M, g ∣= violoniste(Jean) mais M, g ∣≠ violoniste(Marie)
M, g ∣= violoniste(y) mais M, g ∣≠ violoniste(x)
M, g ∣= violoniste(x) ∨ aime(z,Jean)
M, g ∣= ∃y aime(y,Jean) mais M, g ∣≠ ∃y aime(Jean,y)
M, g ∣= ∀x aime(Marie,x) mais M, g ∣≠ ∀x aime(x,Jean)
M, g ∣= ∀x violoniste(x) ⇒ aime(Marie,x)
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
50

Valeur de vérité dans un modèle :

définition

Définition :
– Une phrase  est vraie dans le modèle M ssi pour
toute affectation de variables g, on a : M, g ∣= 

Notation :
– Si  est vraie dans le modèle M, on note M ∣= 
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
51

Valeur de vérité dans un modèle :

exemples
M = (D,F) D = {d1,d2}
F(Marie) = d1 F(Jean) = d2 F(violoniste) = {d2} F(aime) = {(d1,d2)}
g(x) = d1 ; g(y) = d2 ; g(z) = d1 ; g(w) = d1 ; ...
g'(x) = d1 ; g'(y) = d2 ; g'(z) = d2 ; g'(w) = d1 ; ...
On a :
M ∣= violoniste(Jean) mais M ∣≠ violoniste(z)
M ∣≠ violoniste(x) ∨ aime(z,Jean)
M ∣= ∃x aime(x,Jean) mais M ∣≠ ∃x aime(Jean,x)
M ∣= ∃y aime(y,Jean) mais M ∣≠ ∃y aime(Jean,y)
M ∣= ∀x aime(Marie,x) mais M ∣≠ ∀x aime(x,Jean)
Peu importe l'affectation de variables pour déterminer si  est vraie →
pas de variables libres dans  ou relation vraie pour toute valeur
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
52

Formule valide

Intuition :
– Une formule est valide ssi elle est vrai quelle que soit la
réalité du monde
Définition :
– Une formule  est valide ssi elle est vraie dans tous les
modèles
Exemples :
. ∣= (∀x violoniste(x) ⇒ aime(Marie,x)) ∧ violoniste(Jean) ⇒ aime(Marie,Jean)
. ∣≠ (∀x violoniste(x) ⇒ aime(Marie,x)) ∧ ¬violoniste(Jean) ⇒ ¬aime(Marie,Jean)
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
53

Plan

On a vu :
– vocabulaire : briques de base
– modèle : sens donné à un vocabulaire
– langage du 1er ordre : phrases utilisant le vocabulaire
– valeur de vérité des phrases : formule satisfaite

On va voir (très succinctement et superficiellement) :

– lien avec la langue
→ lambda-calcul
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
54

Lambda-Calcul
Intuition (1)
Plusieurs écritures pour une même réalité :
– f:ℝℝ
x  x+3 f(5) = 8
– fonction f(x) = x+3
– f = fonction x  x+3
Notations :
– f = x . x+3
– f x = f(x)
– Ex. f 5 = (x . x+3) 5 → 5+3 → 8
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
55

Lambda-Calcul
Intuition (2)
Plusieurs écritures pour une même réalité :
– f:ℝ×ℝℝ
(x,y)  x+3−y f(5,2) = 6
– f = fonction (x,y)  x+3−y
Alternative
– f = fonction x  (fonction y  x+3−y)
– f = x .(y.(x+3−y))
– f 5 = (x.(y.(x+3−y))) 5 → y.(5+3−y)
– (f 5) 2 → (y.(5+3−y)) 2 → 5+3−2 → 6
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
56

Lambda-termes

L'ensemble des -termes est défini inductivement

de la manière suivante :

– Atomes : toutes les variables et les constantes sont

des -termes

– Application : si A et B sont des -termes, alors (A B)

est un -terme

– Abstraction : si A est un -terme et x est une variable,

alors x.A est un -terme
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
57

Lambda-termes
et langage du premier ordre

Exemples d'abstraction de constantes :

– violoniste(Pierre) ← ([Link](x)) Pierre
– aime(Jean,Marie) ← (x.[Link](x,y)) Jean Marie

Exemples d'abstraction de prédicats

– (P.∃x (P x)) violoniste
→ ∃x violoniste(x)
– (P.Q.(∀x (P x) ⇒ (Q x))) violoniste gastronome
→ ∀x violoniste(x) ⇒ gastronome(x)
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
58

Sémantique de Montague
(intuition)
Sémantique compositionnelle :
– À chaque mot, on associe un (ou des) -terme(s), qui
représente(nt) sa sémantique
– On considère une analyse syntaxique de la phrase (en
constituants)
– On construit un -terme isomorphe à l'arbre d'analyse
syntaxique :
● Toute feuille (mot) est remplacée par le -terme associé
● Tout autre noeud est une -application
– La sémantique est le résultat de l'évaluation du -terme
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
59

Sémantique de Montague
(exemple simple)
● un = P.Q.(∃x (P x) ∧ (Q x)) P
● violoniste = x.(violoniste(x) SN SV
● aime = y.[Link](x,y) Det N V SN
un violoniste aime Marie
● Marie = Marie
● ((un violoniste) (aime Marie))
→ ((P.Q.(∃x (P x) ∧ (Q x))) x.(violoniste(x)) (aime Marie)
→ (Q.(∃x violoniste(x) ∧ (Q x)) ((y.[Link](x,y)) Marie)
→ (Q.∃x violoniste(x) ∧ (Q x)) ([Link](x,Marie))
→ ∃x violoniste(x) ∧ aime(x,Marie)
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
60

Vue d'ensemble

Lexique Vocabulaire interprétation

Entités
syntaxique sémantique
Modèle
-termes construction

Phrases
Phrases
/ formules Faits
grammaticales
utilisant le concernant
utilisant le satisfaction
vocabulaire les entités
lexique
sémantique
Formalismes linguistiques – Logique du premier ordre © 2005-2006 R. Marlet
61

À retenir

●
Notion de modèle :
– donne du sens à un vocabulaire
– décrit une connaissance (hypothétique) du monde
●
Langage du premier ordre / formule logique
– interprétation(s) linguistique(s)
●
Satisfaction d'une formule logique
– définit ce qui est vrai dans un modèle
●
Lien formel avec la langue
– -calcul, sémantique compositionnelle (Montague)