Université Sorbonne Paris-Nord L1 informatique
TD 7 – Calcul des prédicats, interprétation et déduction
naturelle
Exercice 1. Soit I l’interprétation de domaine D = {0, 1, 2} telle que I (P) = {0, 1}, I (Q) = {1, 2} et I (R) = ;.
Pour chacune des formules suivantes, calculer son interprétation.
1. ∃ xR( x)
2. ∀ x(P( x) ∨ Q( x))
3. ∀ x(P( x) ⇒ Q( x))
4. ∀ x(R( x) ⇒ Q( x))
Exercice 2. Soient les formules suivantes où u et z sont des constantes, f une fonction, et l’égalité toujours
interprétée comme {( x, x) | x ∈ D } quel que soit le domaine D .
1. ∀ x∃ y( y = f ( x, u))
2. ∃ y∀ x( y = f ( x, u))
3. ∃ x∀ y( y = f ( x, y))
4. ∃ x( x 6= z ∧ f ( x, x) = x)
Indiquer si les interprétations ci-dessous sont des modèles ou des contre-modèles de ces formules.
I 1 : D = {0, 1}, I 1 (z) = 0, I 1 (u) = 1, I 1 (f ) = ( x, y) 7→ x ∧ y
I 2 : D = N, I 2 (z) = 0, I 2 (u) = 1, I 2 (f ) = ( x, y) 7→ x + y
I 3 : D = 2 X pour X quelconque, I 3 (z) = ;, I 3 (u) = X , I 3 (f ) = ( x, y) 7→ x ∪ y
Exercice 3 (*). Le prédicat E( x) signifie que x a réussi son examen, et T( x, y) que x a téléphoné à y.
1. Formaliser les énoncés suivants en utilisant ces prédicats :
(a) Quelqu’un a raté l’examen et n’a été appelé par personne.
(b) Tous ceux qui ont réussi l’examen ont été appelés.
(c) Personne n’a appelé tous ceux qui ont réussi l’examen.
(d) Tous ceux qui ont appelé quelqu’un, ont appelé quelqu’un qui a réussi l’examen.
2. On considère l’interprétation I de domaine D = {Abdoulaye, Bourama, Céline, Dalia}, dans laquelle
seuls Bourama et Céline ont réussi l’examen, les garçons (Abdoulaye et Bourama) ont appelé les
filles, Dalia a appelé Bourama, Céline a appelé Dalia et ce sont les seuls appels.
(a) Définir formellement cette interprétation I .
(b) En s’aidant d’un schéma, interpréter chacune des formules ci-dessus dans I .
page 1
Université Sorbonne Paris-Nord L1 informatique
On rappelle les règles de la déduction naturelle.
Γ `dn F Γ `dn G Γ `dn F ∧ G Γ `dn F ∧ G
AX ∧- I ∧- EG ∧- ED
Γ, F `dn F Γ `dn F ∧ G Γ `dn F Γ `dn G
Γ `dn F Γ `dn G Γ `dn F ∨ G Γ, F `dn H Γ,G `dn H
∨- IG ∨- ID ∨- E
Γ `dn F ∨ G Γ `dn F ∨ G Γ `dn H
Γ, F `dn G Γ `dn F ⇒ G Γ `dn F
⇒- I ⇒- E
Γ `dn F ⇒ G Γ `dn G
Γ, F `dn G Γ, F `dn ¬G Γ `dn F Γ `dn ¬F Γ `dn ¬¬F
¬- I ¬- E RAA
Γ `dn ¬F Γ `dn G Γ `dn F
Γ `dn ∀ xF Γ `dn F Γ `dn ∃ yF Γ, F `dn G Γ `dn F {t/ x}
∀- E ∀- I ∃- E ∃- I
Γ `dn F {t/ x} Γ `dn ∀ yF Γ `dn G Γ `dn ∃ xF
pour tout terme t, y ∉ VL(Γ) et y ∉ VL(G )
Exercice 4. La dérivation suivante n’est pas correcte. Expliquer où est l’erreur.
AX
∃ xP( x), P( x) `dn P( x)
AX ∀- I
∃ xP( x) `dn ∃ xP( x) ∃ xP( x), P( x) `dn ∀ xP( x)
∃- E
∃ xP( x) `dn ∀ xP( x)
Donner une interprétation dans laquelle la formule (∃ xP( x)) ⇒(∀ xP( x)) n’est pas vérifiée.
Exercice 5. Prouver les séquents suivants en utilisant la déduction naturelle.
1. ∀ x(P( x) ∧ R( x)) ` (∀ xP( x)) ∧ (∀ xR( x))
2. ∃ x(P( x) ∨ R( x)) ` (∃ xP( x)) ∨ (∃ xR( x))
3. Si x ∉ VL(F ), alors ∀ xF ⇔ F
4. ∀ x∀ yP( x, y) ` ∀ y∀ xP( x, y)
5. ¬(∃ x¬P( x)) ` ∀ xP( x)
page 2