Logique des propositions

La logique des propositions est un langage formel

constitué d’une syntaxe et d’une sémantique.
La syntaxe décrit l’ensemble des formules qui
appartiennent au langage.
La sémantique permet de donner un sens aux
formules du langage.

Introduction à la linguistique - Logique – p.1/63

 Logique des propositions - syntaxe

Le vocabulaire de la logique des propositions est

constitué :
d’atomes, ou propositions que l’on désignera par les
lettres minuscules de l’alphabet a, b, c, d, . . . , z
de connecteurs logiques (¬, ∨, ∧, →, ↔),
de parenthèses

Introduction à la linguistique - Logique – p.2/63

 Logique des propositions - syntaxe

Les règles de formation des formules de la logique des

proposition sont :

Tout atome est une formule

si E1 et E2 sont des formules alors
¬E1 est une formule
E1 ∨ E2 est une formule
E1 ∧ E2 est une formule
E1 → E2 est une formule
E1 ↔ E2 est une formule
si E est une formule alors (E) est une formule.
rien d’autre n’est une formule.

Introduction à la linguistique - Logique – p.3/63

 Logique des propositions - syntaxe

On définit un ordre de précédence entre les connecteur :

¬ > ∧ > ∨ >→>↔

Exemples de formules :
a
a∨b
¬a ∨ b ≡ (¬a) ∨ b
a∨b∧c ≡ a ∨ (b ∧ c)
a ∨ b → c ∧ d ≡ (a ∨ b) → (c ∧ d)

Introduction à la linguistique - Logique – p.4/63

 Logique des propositions - syntaxe

L’ensemble des formules peut être généré à l’aide de la

grammaire hors-contexte G = hΣ, {F }, P, F i où :
Σ = {a, b, . . . , z, (, ), ¬, ∧, ∨, →, ↔}


 F → a|b| . . . |z
F → ¬F





 F →F ∨F


P = F →F ∧F
′ ′
F → F → F








 F →F ↔F
F → (F )


Introduction à la linguistique - Logique – p.5/63

 Logique des propositions - syntaxe

Le même langage peut être généré par la grammaire non

ambiguë G′ = hΣ, {F, G, H, I, J, K}, P, F i où :
Σ = {a, b, . . . , z, (, ), ¬, ∧, ∨, →, ↔}


 F →F ↔G | G
G → G ′ →′ H | H





 H →H ∨I | I


P = I →I ∧J | J
J → ¬J | K








 K → (F )
K → a|b| . . . |z


Introduction à la linguistique - Logique – p.6/63

 Logique des propositions - syntaxe

G et G′ sont faiblement équivalentes :

Elles reconnaissent le même langage.
Mais peuvent associer des arbres différents à un
même mot.

Introduction à la linguistique - Logique – p.7/63

 Logique des propositions - syntaxe

G G′
F

F F
H
HH HH
 H
F ∨ F ¬ F I
HH
HH   H
¬ F b F ∨ F I ∨ J

J ¬ J
a a b
K K

a b

Introduction à la linguistique - Logique – p.8/63

 Logique des propositions - sémantique

La sémantique consiste à donner un sens aux différents

éléments du langage :
on donne à chaque atome une valeur de vérité :
vrai (v) ou faux (f )
on associe à chaque connecteur une table de vérité.
La valeur d’une formule peut être calculée à partir des
valeurs de vérité des atomes, grâce aux tables de vérité
des connecteurs.

Introduction à la linguistique - Logique – p.9/63

 Logique des propositions

La table de vérité d’un connecteur unaire ◦1 permet de

calculer la valeur de ◦1 F étant donné la valeur de F .
La table de vérité d’un connecteur binaire ◦2 permet de
calculer la valeur de F1 ◦2 F2 étant donné les valeurs de
F1 et F2 .

F1 F2 F1 ∨ F2 F1 ∧ F2 ¬F1 F1 → F2 F1 ↔ F2
v v v v f v v
v f v f f f f
f v v f v v f
f f f f v v v

Introduction à la linguistique - Logique – p.10/63

 Logique des propositions - sémantique

Les tables de vérité des connecteurs sont toujours les

mêmes.
Les valeurs de atomes peuvent changer, elles sont
déterminées par une fonction d’évaluation.
On appelle fonction d’évaluation d’un ensemble d’atomes
A, une fonction V de A dans {v, f }.
Pour évaluer une formule F , il faut définir une fonction
d’évaluation des atomes qui figurent dans F .
On dit que V satisfait F si l’évaluation de F étant donné V
est égale à v.

Introduction à la linguistique - Logique – p.11/63

 Logique des propositions

V = {(a, v), (b, f ), (c, v)} ne satisfait pas a ∨ b ∧ ¬c

E(f )
HH
 H
 H
 H
 H
E(v) ∧ E(f )
HH H
 H
 H ¬ E(v)
E(v) ∨ E(f )
c(v)
a(v) b(f )

Introduction à la linguistique - Logique – p.12/63

 Logique des propositions

V = {(a, v), (b, f ), (c, f )} satisfait a ∨ b ∧ ¬c

E(v)
HH
 H
 H
 H
 H
E(v) ∧ E(v)
HH H
 H
 H ¬ E(f )
E(v) ∨ E(f )
c(f )
a(v) b(f )

Introduction à la linguistique - Logique – p.13/63

 Logique des prédicats

En logique des prédicats, les éléments de base du

langage ne sont plus des propositions mais des prédicats.

la mer est bleue

sujet prédicat

Un prédicat peut être vu comme une fonction

propositionnelle bleu(x) qui prend la valeur v lorsque x est
la mer et f lorsque x est le soleil.
Le prédicat aimer prend deux arguments : l’être aimant et
l’être ou la chose aimée.
On appellé arité d’un prédicat, le nombre d’argument qu’il
requiert.

Introduction à la linguistique - Logique – p.14/63

 Logique des prédicats

Le vocabulaire de la logique des prédicats est constitué

de cinq classes de symboles :
les constantes (a, b, c, d . . .)
les variables (w, x, y . . .)
les symboles de prédicats d’arité positive ou nulle
(A, B . . .)
les connecteurs logiques
les quantificateurs (∀, ∃)
∀ est appelé le quantificateur universel
∃ est appelé le quantificateur existentiel

Introduction à la linguistique - Logique – p.15/63

 Logique des prédicats

Un terme est :
une variable
ou une constante
Si t1 . . . tn sont des termes et si A est un prédicat d’arité
n, alors A(t1 , . . . , tn ) est un atome ou formule atomique.

Introduction à la linguistique - Logique – p.16/63

 Logique des prédicats

une formule est définie récursivement :

tout atome est une formule
si ϕ et ψ sont des formules, alors : ϕ ∨ ψ, ϕ ∧ ψ,
ϕ → ψ, ϕ ↔ ψ sont des formules.
si ϕ est une formule alors ¬ϕ est un formule.
si ϕ est une formule et si x est une variable, alors ∀xϕ
et ∃xϕ sont des formules. ϕ est appelé la portée du
quantificateur ∀x et ∃x.
toute formule est obtenue par l’application des règles
précédentes un nombre fini de fois.

Introduction à la linguistique - Logique – p.17/63

 Logique des prédicats - syntaxe

On définit un ordre de précédence entre les connecteur :

∀, ∃ > ¬ > ∧ > ∨ > → > ↔

Exemples de formules :
∀xA(x) ≡ ∀x(A(x))
∀x∃yB(y) ∨ H(a) ≡ ∀x(∃y(B(y))) ∨ H(a)
¬∀xH(x) → P (x) ≡ ¬(∀x(H(x))) → P (x)

Introduction à la linguistique - Logique – p.18/63

 Logique des prédicats

Dans la formule ∀xJ(x, y), x est dans la portée du

quantificateur universel. Elle est dite liée, la variable y est
libre.
L’ensemble des variables liées d’une formule ϕ (noté
B(ϕ)) se définit de la façon suivante :
si ϕ est un atome, B(ϕ) = ∅
si ϕ est de la forme χ ∨ ψ, χ ∧ ψ, χ → ψ, χ ↔ ψ alors
B(ϕ) = B(χ) ∪ B(ψ).
si ϕ est de la forme ¬ψ alors B(ϕ) = B(ψ)
si ϕ est de la forme ∀xψ ou ∃xψ alors
B(ϕ) = {x} ∪ B(ψ)

Introduction à la linguistique - Logique – p.19/63

 Logique des prédicats

L’ensemble des variables libres d’une formule ϕ (noté

F(ϕ)) se définit de la façon suivante :
si ϕ est un atome, F(ϕ) est égal à l’ensemble des
variables apparaissant dans ϕ
si ϕ est de la forme χ ∨ ψ, χ ∧ ψ, χ → ψ, χ ↔ ψ alors
F(ϕ) = F(χ) ∪ F(ψ).
si ϕ est de la forme ¬ψ alors F(ϕ) = F(ψ)
si ϕ est de la forme ∀xψ ou ∃xψ alors
F(ϕ) = F(ψ) − {x}
Une formule ϕ telle que F(ϕ) = ∅ est dite close ou fermée.

Introduction à la linguistique - Logique – p.20/63

 Domaine de discours, interprétation, modèle

Pour évaluer la formule ∀xH(x) il faut connaître

l’ensemble des valeurs que peut prendre la variable x.
Cet ensemble est appelé le domaine de discours, noté D
L’évaluation d’une formule ϕ nécessite la spécification
d’un domaine de discours D et d’une fonction
d’interprétation I qui associe :
à chaque symbole de constante un élément de D
à chaque symbole de prédicat P d’arité n, la définition
d’une fonction de Dn → {v, f } définissant P .
Un domaine de discours et une fonction d’interprétation
constituent un modèle.

Introduction à la linguistique - Logique – p.21/63

 Assignation

Pour évaluer une formule comportant des variables, il est

nécessaire de donner à ces dernières des valeurs dans
D.
On appelle assignation, une fonction qui associe à toute
variable une valeur dans D.
Etant donné l’assignation g, on note g[y ← d] l’assignation
g ′ qui associe la valeur d à la variable y et associe les
mêmes valeurs que g à toutes les autres variables.

Introduction à la linguistique - Logique – p.22/63

 Evaluation d’une formule

L’évaluation d’une formule nécessite la spécification de :

Un modèle M
Une fonction d’assignation g

Introduction à la linguistique - Logique – p.23/63

 Interprétation de termes

Si t est un terme, on définit la fonction d’interprétation,

étant donné un modèle M = hD, Ii et une assignation g,
de la manière suivante :

I(t) si t est une constante
[[t]]hM,gi =
g(t) si t est une variable

Introduction à la linguistique - Logique – p.24/63

 Evaluation

VhM,gi (P (t1 , . . . , tn )) = v ssi

h[[t1 ]]hM,gi , . . . , [[tn ]]hM,gi i ∈ [[P ]]hM,gi
VhM,gi (¬ϕ) = v ssi VhM,gi (ϕ) = f
VhM,gi (ϕ ∨ ψ) = v ssi VhM,gi (ϕ) = v ou VhM,gi (ψ) = v
VhM,gi (ϕ ∧ ψ) = v ssi VhM,gi (ϕ) = v et VhM,gi (ψ) = v
VhM,gi (ϕ → ψ) = v ssi VhM,gi (ϕ) = f ou VhM,gi (ψ) = v
VhM,gi (ϕ ↔ ψ) = v ssi VhM,gi (ϕ) = VhM,gi (ψ)
VhM,gi (∀xϕ) = v ssi pour tout d ∈ D, VhM,g[x←d]i (ϕ) = v
VhM,gi (∃xϕ) = v s’il existe au moins un d ∈ D tel que
VhM,g[x←d]i (ϕ) = v

Introduction à la linguistique - Logique – p.25/63