Université Kasdi Merbah Ouargla
Faculté NTIC - Département d’informatique et des TI
TD2 (Logique de prédicats)
Exercice 1 :
1. Traduisez les énoncés suivants en formules de la logique des prédicats (on donnera à chaque
fois l’interprétation des prédicats utilisés — par exemple A(x,y) = x aime y). En cas d’énoncé
ambigu, on proposera deux formules.
a. Jean est plus grand que Marie
b. Paul a vu Léa et elle ne l’a pas vu
c. Si Jean est un homme, alors il est mortel
d. Un chat est entré
e. Certains enfants ne sont pas malades
f. Tous les éléphants ont une trompe
g. Tous les hommes n’aiment pas Marie
h. Il y a une chanson qu’aucun enfant ne chante
i. Si tous les hommes aiment Marie, alors elle est contente
j. Tous les fermiers apprécient un ministre
2. Traduisez les quatre propositions du carré d’opposition en logique des prédicats. Dans chaque cas, il y a deux
possibilités de traduction, avec les deux quantificateurs.
3. Traduisez en logique des prédicats les propositions suivantes, et, en cas d’ambigüité, donnez toutes les traductions
correspondantes.
a. Bien que personne ne fasse de bruit, Jean n’arrive pas à se concentrer
b. Si personne ne fait de bruit, Jean répondra au moins à une question
c. Tout le monde a menti à quelqu’un dans sa vie
d. Tous les étudiants, sauf Jean, sont présents
e. Aucun enfant ne fait jamais aucune bêtise
f. Tout le monde a lu un livre de logique
Exercice 2 :
Soient les formules :
A : ∀ x (o(x) → o(s)) B : (∀ x o(x)) → o(s) C : o(s) → ∀ x o(s)
D : (∃ x o(x)) → o(s) E : ∃ x(o(x) → o(s)) F : o(s) → ∃ x o(x)
où o est un symbole de prédicat et s est une constante.
Soient I1 et I2 deux interprétations telles que :
– Dans les deux cas, l’univers (domaine) est l’ensemble des 10 salles de cours d’un bâtiment donné ;
– Dans les deux cas, l’interprétation de la constante s est la salle de cours N. 1.
– Dans les deux cas, l’interprétation du symbole de prédicat o est l’ensemble des salles de cours ouvertes ;
– Dans le cas de I1, la salle N. 1 est ouverte et toutes les autres sont fermées ;
– Dans le cas de I2, la salle N. 1 est fermée et toutes les autres sont ouvertes ;
1. Pour chacune des formules A - F, calculer sa valeur de vérité, d’abord par rapport à I1, puis par rapport à I2 ;
2. Pour chacune des formules A - F, dire si elle est valide ou pas. Justifiez vos réponse : si vous dites que la formule
n’est pas valide, donnez une interprétation où elle est fausse ; si vous dites qu’elle est valide, expliquez pourquoi
une interprétation la rendant fausse ne peut pas exister (en huit lignes au maximum).
Exercice 3 :
Soient les connaissances et les faits suivants :
X est le grand-père de Z si X est le père de Y et Y est le père de Z
X est le grand-père de Z si X est le père de Y et Y est la mère de Z
X est la sœur de Z si X est une fille et Y est le père de X et Y est le père de Z
Ali est le père de Omrane
Ali est le père de Meriem
Omrane est le père de Yahia
Omrane est le père de Younes
Aicha est la mère de Yahia
1) Exprimer ces connaissances et ces faits sous forme de clauses de Horn.
2) Comment exprimer les questions suivantes ?
a) Quelle est la sœur de Omrane ?
b) Ali est le grand-père de qui ?
Quelles sont les réponses à ces questions ? justifier vos réponses.
Exercice 4 :
1) Exprimer en logique des prédicats les phrases suivantes :
Amina a 50 ans
Ahmed a 25 ans
Amina est la mère de Ahmed
Toute personne a un age
Toute mère d’une personne est une personne
Une personne est l’ancêtre d’une autre personne si elle est parent d’une autre personne ou
bien si elle est l’ancêtre de l’ancêtre d’une autre personne
2) – mettre les formules obtenues précédemment sous forme de Clauses de Horn.
3) – Parmi ces clauses, quels sont les faits ?