Université de Yaoundé I Faculté des Sciences
The University of Yaounde I Faculty of Sciences
Département d’Informatique
INF1222 : Fiche de TD N˚3
22 mai 2023
Etienne Kouokam
E XERCICE 1 [Lié ? Libre ? Formule ?]
Analyser les formules suivantes (dire si ce sont des formules, donner arbres, occurrences libres, occurrences
liées, identifier la portée de chaque quantificateur) :
1.1 (∀x)((D1(x) ∨ D2(x, y)) ⇒ ((∃y)(C(y) ∧ D3(x, y)) ∧ E(u, y, x))).
1.2 (∀x)(D1(x) ∨ D2(x, y) ⇒ ((∃y)(C(y) ∧ D3(x, y)) ∧ E(u, y, x))).
1.3 (∀x)(D1(x) ∨ (D2(x, y) ⇒ ((∃y)(C(y) ∧ D3(x, y)) ∧ E(u, y, x)))).
1.4 (∃x)(∃y)(x 6= y ∧ (∀w)(((w = x ∨ w = y) ∨ w = u) ⇒ (∀z)¬D3(z, w) ∧ D2(x, u)).
1.5 (∃x)(∃y)(x 6= y ∧ (∀w)(((w = x ∨ w = y) ∨ w = u) ⇒ (∀z)(¬D3(z, w) ∧ D2(x, u)))).
E XERCICE 2 [Traduction en logique des prédicats]
Traduire les phrases suivantes en LP1 (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 les différentes formules possibles.
2.1 Jean suit un cours.
2.2 Un logicien a été champion du monde de cyclisme.
2.3 Un entier naturel est pair ou impair.
2.4 Un enseignant-chercheur a toujours un nouveau sujet à étudier.
2.5 Dans un triangle isocèle une médiane est également hauteur.
2.6 Seulement les hommes sont méchants.
2.7 Il existe un homme qui aime toutes les femmes.
2.8 Chaque personne aime quelqu’un et personne n’aime tout le monde, ou bien quelqu’un aime tout le monde
et quelqu’un n’aime personne.
2.9 Il y a des gens que l’on peut rouler tout le temps et quelquefois on peut rouler tout le monde, mais on ne
peut pas rouler tout le monde à chaque fois.
2.10 Une conjecture est un théorème qui ne peut être démontré par aucun mathématicien. Il existe des mathé-
maticiens qui ne démontrent pas tous les théorèmes. Si un mathématicien démontre une conjecture alors
il se trompe. Si quelqu’un démontre un théorème sans se tromper, alors ce n’est pas une conjecture.
2.11 Il existe des PC non connectés en réseau. Dans les grandes entreprises, tous les PC sont connectés au réseau
interne. Il existe dans chaque grande entreprise au moins un PC connecté au réseau interne et relié à
Internet.
2.12 Toute personne possédant un PC et un modem peut utiliser Internet. Il existe des personnes connectées en
réseau, qui ne peuvent pas utiliser Internet. Nul ne possède de modem s’il ne possède pas de PC. Tout
utilisateur d’Internet est soit connecté à un réseau, soit possesseur d’un PC. Il n’est pas possible d’utiliser
Internet sans posséder de PC.
1
E XERCICE 3 [Traductions et interprétations]
Tout en expliquant, donner le nombres de lectures différentes pour les phrases suivantes :
3.1 trois déménageurs ont soulevé trois pianos.
3.2 mettre huit gouttes de médicaments dans trois cuillérées d’eau.
3.3 Chaque professeur a donné un livre à chaque étudiant.
3.4 Chaque professeur a donné un livre à un étudiant.
3.5 Un professeur a donné un livre à un étudiant.
3.6 Je n’ai pas donné quelque chose à quelqu’un.
3.7 Marie n’a rien raconté à quelqu’un.
3.8 Marie n’a raconté quelque chose à personne.
3.9 Jean croit que quelqu’un le persécute.
3.10 Jean croit qu’un professeur a donné un livre à chaque étudiant.
E XERCICE 4 [Résolution]
4.1 Montrer, en utilisant la méthode des tableaux puis la résolution, que C est conséquence logique des hypo-
thèses, dans chacun des cas suivants :
(H1) ∃z∀x∀y(F (x, y) ⇒ G(z, x)) (H1) (∃xF (x) ⇒ ∃xG(x))
(H2) ∀x∀y∃z(¬F (y, z) ⇒ E(x)) (H2) ∀x(G(x) ⇒ ∃yH(x, y))
(H3) ∃z¬E(z) (H3) ∀x∀y(H(x, y) ⇒ A(x))
(C) ∃xG(x, x) (C) ∃x(F (x) ⇒ A(x))
4.2 Démontrez la validité des raisonnements suivants à l’aide du principe de résolution.
(H1) ∀x∀y(M (x, x, x) ∨ B(x)) (H1) ∀x∀y(D(x, y) ⇒ A(x, x))
(H2) ∀x∀y∃z((M (x, y, z) ∧ N (x, y)) ⇒ P (y, x)) (H2) (∀xA(x, x) ⇒ ∀x∀yB(x, y))
(H3) ∃x∀y∀z∀t(¬P (y, x) ∧ (M (y, z, t) ∨ A(x, z)))
(H3) ∀x∀y∀z(C(x, z) ⇒ (A(x, y)∨D(y, z)∨E(z, z)))
(H4) ∀x∀y(M (x, x, x) ⇒ N (x, y))
(H5) ∀x∀y(M (x, x, y) ⇒ ¬A(x, y)) (H4) ∀x∃y(C(x, y) ∧ ¬E(y, y))
(C) ∃xB(x) (C) ∃xB(x, x)
E XERCICE 5 [Interprétation et Résolution]
Démontrez la validité des raisonnements suivants à l’aide du principe de résolution.
5.1 H1 : Tout homme est un primate
H2 : Les dauphins ne sont pas des primates
H3 : Il y a des dauphins qui sont intelligents
Par conséquent, on peut ne pas être un homme et être intelligent
5.2 H1 : Toutes les personnes qui entrent en voiture dans la faculté doivent avoir une carte ou être accompa-
gnées par un membre du personnel.
H2 : Certains étudiants entrent en voiture dans la faculté sans être accompagnés de personnes qui ne sont
pas des étudiants.
H3 : Aucun étudiant n’a de carte.
Donc, certains étudiants sont membres du personnel.
Bon courage ! ! !