Institut de Mathématiques et L OGIQUE ET T ECHNIQUE DE P REUVE Année acad 20-21

de Sciences Physiques (IMSP) Fiche no2 d’exercices L3 Informatique

E XERCICE 1
1. Repondre par vrai ou faux aux assertions suivantes :
(a) Une formule A est prouvable par tableau s’il existe un tableau clos avec la racine {¬A}.
(b) Une formule A est prouvable par résolution si elle est conséquence logique de l’antilogie.
(c) Toute clause issue de la preuve par résolution d’une formule A est une conséquence
logique de A.
(d) Soit une formule A et E un ensemble de formules, s’il existe une preuve par résolution de
A à partir de E alors E |= A.
de f
2. On considère la formule A1 := (∃ x, ∀ y, R(x, y)) =⇒ (∀ y, ∃ x, R(x, y)).
(a) Donner la forme normale de négation de la formule ¬A1 .
(b) Donner la forme de skolem de la formule ¬A1 .
(c) Donner la forme clausale de ¬A1 .
(d) la formule ¬A1 est-elle satisfiable ? La formule A1 est-elle valide ?

E XERCICE 2 (P REUVE PAR R ÉSOLUTION )

de f
1. Soient F := ¬(p ∨ (q ∧ r)) =⇒ (¬q ∨ ¬r) une formule propositionnelle et l’ensemble Γ =
{¬p ∨ ¬q ∨ r, ¬p ∨ ¬q ∨ s, p, ¬s, q, t}.
(a) F admet-elle une preuve par résolution ? Si oui, la donner.
(b) Prouver par résolution l’ensemble Γ.
(c) Même question pour l’ensemble {p ∨ q, ¬p ∨ ¬q, p ∨ ¬q, ¬p ∨ q}.
de f
2. Soit A := ∃ x, ∀ y, (S(y) =⇒ R(x)) =⇒ (S(x) =⇒ R(y)). On veut prouver A par résolution
pour cela :
(a) Donner la représentation arborescente de A.
(b) Soit B la formule obtenue en écrivant la forme normale de négation de A. Justifier que B
est B = ∀ x, ∃ y, (¬S(y) ∨ R(x)) ∧ S(x) ∧ ¬R(y).
(c) Skolémiser la formule B obtenue à la question précédente.
(d) Écrire l’ensemble clausale de ¬A puis donner une preuve par résolution de ¬A.
3. Même questions pour
de f
A2 := (∃ x, P(x)) ⇒ ((∃ x, Q(x)) ⇒ ∃ x, (P(x) ∧ Q(x))).

4. En utilisant la résolution, montrer que {∃ x, ¬P(x), ∀ x, (P(x) ∨ Q(x))} |= ∃ x, Q(x).

E XERCICE 3
Soit la formule
∀ x, ∀ y, (P(x) ∧ Q(y) ∧ (¬P(a) ∨ ¬Q(a))).
Le langage des termes ne contient que la constante a, celui des prédicats contient les deux symboles
P et Q. On rappelle que ” le domaine de Herbrand d’un langage logique est l’ensemble des termes
clos formés à partir des symboles de fonctions du langage ” et ” la base de Herbrand est l’ensemble
des formules atomiques closes construites sur le langage”.
1. Quel est le domaine de Herbrand et la base de Herbrand associées ?
2. Donner toutes les interprétations de Herbrand possibles.
3. La formule est-elle satisfiable ?

$ GisG3 $ Page 1 sur 5

Exercice 4 Modélisation premier ordre (6 points)
On modélise de manière logique la situation sanitaire. Les objets utilisés représentent des personnes
ainsi que des jours.
Pour cela on introduit les prédicats suivants :
— contact(x, y, j) les personnes x et y ont été en contact le jour j
— symptome(x, j) la personne x présente des symptômes le jour j
— masque(x, j) la personne x porte un masque le jour j
— isole(x, d, f ) la personne x reste isolée du jour d au jour f inclus.
— teste-pos(x, j) la personne x est testée positive le jour j
— teste-neg(x, j) la personne x est testée négative le jour j
— contagieux(x, j) la personne x est contagieuse le jour j
On introduit également les symboles de fonction et de prédicats suivants sur les dates et les individus :
— Le symbole de prédicat unaire J tel que J(j) est vrai si j représente un jour.
— Le symbole de prédicat unaire I tel que I(x) est vrai si x représente un individu.
— une constante moi pour représenter la personne qui parle
— un ensemble de fonctions unaires +n pour n’importe quel entier n, l’opération +n ajoute n jours
à une date j. On pourra choisir n suivant les besoins, par exemple +1 représente le lendemain
ou +7 pour passer au même jour de la semaine suivante. On écrira de manière usuelle j+n au
lieu de +n(j) ;
— le symbole de prédicat binaire ≤ tel que j ≤ j 0 si le jour j est avant le jour j 0 ou bien le même
jour.
1. Traduire en français (ou en anglais) les formules suivantes :
(a) ∀x j, teste-neg(x, j) ⇒ ¬contagieux(x, j)
(b) ∀x, ∃j, ¬masque(x, j)
(c) ∃j, ∀x, ¬masque(x, j)
(d) ∀j, (∀x, ¬contact(moi, x, j)) ⇒ ¬masque(moi, j)
Correction :
(a) Toute personne qui est testée négative, n’est pas contagieuse le jour du test.
(b) Personne ne porte de masque tous les jours
(c) Il existe un jour où personne ne porte de masque
(d) Les jours où je n’ai de contact avec personne, je ne porte pas de masque.

Remarque : il était important de bien faire apparaı̂tre dans la formulation la notion de jour
qui apparaı̂t dans les prédicats. Par contre la variable j étant liée dans les formules, la phrase
associée doit conserver cet aspect générique du jour. Par exemple, on ne peut pas traduire la
formule 1c par “personne ne porte de masque le jour j”. En effet une telle formulation dépend
a priori du jour j ce qui n’est pas le cas de la formule initiale.
2. En utilisant uniquement les symboles donnés, exprimer comme des formules logiques les pro-
priétés suivantes :
(a) La même personne ne peut pas être testée positive et négative le même jour.
(b) Une personne isolée sur une période donnée n’a pas de contact sans masque durant cette
période.
(c) Toute personne testée positive reste isolée au moins 7 jours à partir du jour de test (par
exemple une personne détectée positive un mercredi devra restée isolée du mercredi du test
jusqu’au mercredi suivant inclus et pourra ressortir le jeudi). Elle reste également isolée au
delà des 7 jours tant qu’elle n’est pas deux jours sans symptôme.
Correction :

9
(a) ∀x j, teste-pos(x, j) ⇒ ¬teste-neg(x, j).
Remarque : Cette formule est équivalente à sa contraposée

teste-neg(x, j) ⇒ ¬teste-pos(x, j)

qui n’a donc pas besoin d’être ajoutée (même si cela reste correct). Par contre mettre une
équivalence et donc ajouter la condition ¬teste-neg(x, j) ⇒ teste-pos(x, j) est incorrect
car il est possible qu’une personne ne soit pas testée (ni positivement, ni négativement). De
même la réponse

∀x j, (teste-pos(x, j) ∧ ¬teste-neg(x, j)) ∨ (teste-neg(x, j) ∧ ¬teste-pos(x, j))

est incorrecte car implique que tout le monde est testé tous les jours. A fortiori la réponse
∀x j, teste-pos(x, j) ∨ teste-neg(x, j) est doublement incorrecte car suppose qu’un test a
lieu chaque jour et n’empêche pas que les deux soient vrais simultanément.
Certains ont voulu utiliser la formulation ∀x i j, teste-pos(x, i) ∧ teste-neg(x, j) ⇒ i = j,
en principe correcte, sauf que le langage ne contient pas a priori de prédicat pour l’égalité
(même si l’existence d’un ordre ≤ peut permettre de le définir sans trop de difficulté).

(b) ∀x j k, isole(x, j, k) ⇒ ∀y i, (j ≤ i ∧ i ≤ k) ⇒ contact(x, y, i) ⇒ masque(x, i).

Remarque :
Beaucoup de variantes possibles de la partie contact(x, y, i) ⇒ masque(x, i) qui peut s’écrire
¬contact(x, y, i) ∨ masque(x, i) ou encore ¬(contact(x, y, i) ∧ ¬masque(x, i)) qui est plus
proche de la formulation “pas de contact sans masque” mais qui a souvent été mal pa-
renthésé dans les copies.
L’utilisation de j+n à la place de la variable k est inutile et incorrect, en effet, dans ce cas
n doit être une variable de la logique et + devrait alors être une opération binaire alors que
l’énoncé précise que l’on a une infinité de fonction unaires à savoir +0, +1. . . +7. . .
Attention aux notations associées aux contraintes sur les variables. On doit écrire par
exemple ∀j k, j ≤ k ⇒ P (j, k) et pas ∀j k, j ≤ k, P (j, k) qui ne respecte pas la syntaxe
des formules et encore moins ∀j k, j ≤ k ∧ P (j, k) qui implique que ∀j k, j ≤ k qui est
évidemment en général faux.
(c) Cette question avait une partie facile, à savoir une personne testée positive doit restée
isolée 7 jours après le test. Cela se traduit par ∀x j, teste-pos(x, j) ⇒ isole(x, j, j+7). La
partie plus compliquée à traduire est “Elle reste également isolée au delà des 7 jours tant
qu’elle n’est pas deux jours sans symptôme.” Une partie de la solution est dans la formule
symptome(x, i) ⇒ isole(x, i, i+2) qui dit que si x a des symptômes le jour i, alors x reste
deux jours de plus isolé (et donc ne pourra sortir de l’isolement qu’après deux jours sans
symptôme).
La partie vraiment difficile est de bien capturer la relation entre le jour du test, et cette
isolement pour cause de symptômes. Si on quantifie pour tous les jours i on traduit une
autre propriété qui est que toute perssonne qui a des symptômes une journée reste isolée
deux jours (ce qui est pertinent sanitairement mais pas la question). Si on limite i à être
j+7 ou autre valeur fixée alors on ne capture pas le fait que la prolongation d’isolement peut
être arbitrairement longue tant que les symptômes perdurent.
La meilleure manière de traduire le fait que cette consigne s’applique en continuité d’un
isolement pour test positif est de dire que l’isolement jusqu’au jour i est prolongé de deux
jours tant qu’il y a des symptômes. Ce qui donne au final la formule :

∀x j, teste-pos(x, j) ⇒
isole(x, j, j+7) ∧ ∀i, (isole(x, j, i) ∧ symptome(x, i) ⇒ isole(x, i, i+2))

10
3. On construit des interprétations du langage précédent. Le domaine de ces interprétations sera
formé de l’ensemble des entiers naturels pour représenter les jours auquel on ajoute deux constantes
A, B pour représenter des individus.
L’interprétation de J (être un jour) est vraie pour les entiers et fausse pour les constantes A, B.
L’interprétation de I (être un individu) est vraie pour les constantes A, B et fausse pour les
entiers.
Pour n un entier, l’opération +n est interprétée comme la fonction qui au jour représenté par
l’entier j, associe le jour représenté par l’entier j + n. L’ordre ≤ est interprété comme l’ordre
usuel sur les entiers et est faux si l’un des objets à comparer est l’une des constantes A, B.
On va s’intéresser à des formules qui n’utilisent que les symboles de prédicats symptome et
contagieux. Pour représenter l’interprétation de ces symboles, on utilise un tableau dont les
lignes sont indexées par les individus A, B et les colonnes par les jours (des entiers). L’in-
terprétation du prédicat est vraie pour l’individu x et le jour j si et seulement si il y a une croix
sur la ligne x et la colonne j. L’interprétation est fausse pour tous les autres cas (en particulier
pour les couples d’élements du domaine qui n’apparaissent pas dans le tableau).
(a) Soit l’interprétation définie par les tableaux suivants :

symptome contagieux
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
A X X A X X X X X X X
B B X X X

Dans cette interprétation, A a des symptomes les jours 2 et 3, et est contagieux du jour 0
au jour 6. B n’a pas de symptômes mais est contagieux du jour 0 au jour 2.
Donner la valeur de vérité dans cette interprétation de la formule, justifier la réponse :

∀x j, symptome(x, j+2) ⇒ ∀k, (j ≤ k ∧ k ≤ j+4) ⇒ contagieux(x, k)

Correction : La formule est vraie dans cette interprétation.

Pour justifier ce résultat, il faut montrer que la formule

symptome(x, j+2) ⇒ ∀k, (j ≤ k ∧ k ≤ j+4) ⇒ contagieux(x, k)

est vraie pour tout environnement {x 7→ v, j 7→ n} dont pour toutes les valeurs de v et de
n dans le domaine.
— Si symptome(x, j+2) est faux dans cet environnement alors la formule est trivialement
vraie.
— Il reste donc à traiter les cas où symptome(x, j+2) est vraie. Cela n’arrive que si la valeur
de x est A et la valeur de j+2 est 2 ou 3. Comme l’opération +2 est interprétée comme
l’addition useulle, cela se produit dans deux cas, j 7→ 0 et j 7→ 1.
On doit donc vérifier que
— {x 7→ A, j 7→ 0} |= ∀k, (j ≤ k ∧ k ≤ j+4) ⇒ contagieux(x, k)
— {x 7→ A, j 7→ 1} |= ∀k, (j ≤ k ∧ k ≤ j+4) ⇒ contagieux(x, k)
Ce qui revient à montrer que contagieux(x, k) est vrai pour {x 7→ A, k 7→ n} avec
0 ≤ n ≤ 5 ce qui est bien vérifié.
Remarques :
— La formule exprime le fait que si on a des symptomes un jour j, alors on est contagieux
deux jours avant et deux jours après. Cela n’exclut pas que l’on puisse être contagieux
au delà de cette période (ce qui est le cas dans l’interprétation avec A qui est aussi
contagieux le jour 6 et B qui est contagieux sans avoir de symptôme). Il ne faut pas se
laisser influencer par l’interprétation dans le langage courant : “on est contagieux deux
jours avant et deux jours après les symptômes” sous-entend qu’on n’est pas contagieux
en dehors de cette période. Mais du point de vue logique la formule A ⇒ B n’est pas
équivalente à la formule dite “réciproque” ¬A ⇒ ¬B.

11
 — La question posée demandait la valeur de vérité de la formule dans l’interprétation. La
réponse attendue était donc soit vrai, soit faux. Une réponse “la formule est valide”
est incorrecte (on peut trouver des interprétations pour lesquelles elle est fausse), “la
formule est satisfiable” est correcte mais ne répond pas à la question. Une formule dans
une interprétation à une valeur de vérité et une seule. Une formule peut avoir différentes
valeurs si on se place dans différentes interprétations (et environnements). Dire qu’elle
est valide, c’est dire qu’elle est vraie dans toutes les interprétations.
(b) Proposer une interprétation des prédicats symptome et contagieux qui rende vraies simul-
tanément les trois formules suivantes, justifier la réponse :
— ∃x j, symptome(x, j+3) ∧ contagieux(x, j)
— ∃j, ∀x, I(x) ⇒ contagieux(x, j)
— ∀x, I(x) ⇒ ∃j, symptome(x, j)
Correction : Ce qui est demandé est une interprétation c’est-à-dire qu’il faut donner un
domaine et des interprétations de tous les symboles. Le plus simple est de repartir d’un
modèle comme celui utilisé à la question précédente. Il faut que la même interprétation
rende vraies les trois formules simultanément.
Ces trois formules correspondent aux propriétés suivantes
— il existe une personne qui est contagieuse un jour donné et a des symptome trois jours
après.
— il existe un jour où tous les individus sont contagieux
— tous les individus ont des symptomes au moins une journée
Une solution simple est de choisir une interprétation avec un seul individu A, il suffit que
cette personne soit contagieuse le jour 0 et ait des symptomes le jour 3. Les trois propriétés
sont alors vérifiées.
On peut aussi reprendre le modèle précédent avec deux individus et le compléter pour rendre
vraies les trois formules. Dans le modèle précédent, la première formule est vraie en choi-
sissant pour x l’individu A et pour le jour j, le jour 0. La deuxième formule est aussi vraie
dans cette interprétation, on peut choisir pour j les valeurs 0, 1 ou 2. Seule la troisième
formule est fausse dans ce modèle puisque B n’a jamais de symptôme. Il suffit d’ajouter un
jour où B a des symptomes. Cela ne remet pas en cause la valeur des autres formules.

symptome contagieux
0 1 2 3 4 5 6 7 0 1 2 3 4 5 6 7
A X X A X X X X X X X
B X B X X X

12