Ce document contient plusieurs exercices de logique des prédicats. Les exercices portent sur la formalisation en logique des prédicats de phrases en langage naturel, ainsi que sur la vérification de la validité d'implications.
0 évaluation0% ont trouvé ce document utile (0 vote)
162 vues4 pages
Ce document contient plusieurs exercices de logique des prédicats. Les exercices portent sur la formalisation en logique des prédicats de phrases en langage naturel, ainsi que sur la vérification de la validité d'implications.
Ce document contient plusieurs exercices de logique des prédicats. Les exercices portent sur la formalisation en logique des prédicats de phrases en langage naturel, ainsi que sur la vérification de la validité d'implications.
Ce document contient plusieurs exercices de logique des prédicats. Les exercices portent sur la formalisation en logique des prédicats de phrases en langage naturel, ainsi que sur la vérification de la validité d'implications.
Téléchargez comme PDF, TXT ou lisez en ligne sur Scribd
Télécharger au format pdf ou txt
Vous êtes sur la page 1/ 4
Exercices Logique corrigés
Exercice 1 : En associant les énoncés élémentaires « Béchir est étudiant », « Kamel est étudiant »,
« Ridha est étudiant » aux propositions B, K, R, respectivement ; associer à chacun des
énoncés suivants la formule propositionnelle qui semble lui correspondre sémantiquement : 1) Exactement un seul parmi Béchir et Kamel est étudiant. (B ¬ K) ˅ (¬ B K) ou (B ¬ K) ou ¬ (B K) 2) Ni Béchir ni Ridha ne sont étudiants. ¬B¬R 3) Au moins l’un des trois n’est pas étudiant. (¬ B ˅ ¬ K ˅ ¬ R) ou ¬ (B K R) ou (¬ B K R) ˅ (B ¬ K R) ˅ (B K ¬ R) ˅ (¬ B ¬ K R) ˅ (¬ B K ¬ R) ˅ (B ¬ K ¬ R) ˅ (¬ B ¬ K ¬R)
4) Un seul parmi les trois n’est pas étudiant.
(¬ B K R) ˅ (B ¬ K R) ˅ (B K ¬ R) 5) Si Béchir est étudiant, Kamel l’est ; sinon Kamel ne l’est pas. B K ou (B K) (¬ B ¬ K) 6) Béchir est étudiant à condition que Ridha le soit. B R
Exercice 2 : Lesquelles parmi les implications suivantes sont vraies. Donner un contre exemple (deux prédicats P et Q) pour les implications qui ne sont pas vraies i. ( x (P(x) ˅ Q(x)) ) ( ( x P(x)) ˅ ( x Q(x)) ) ii. ( ( x P(x)) ˅ ( x Q(x)) ) ( x (P(x) ˅ Q(x)) ) iii. ( x (P(x) Q(x)) ) ( ( x P(x)) ( x Q(x)) ) iv. ( ( x P(x)) ( x Q(x)) ) ( x (P(x) Q(x)) )
i. Faux
Exemple 1 : On considère le domaine d’objet D = N (l’ensemble des entiers naturels), P(x) : x est un nombre pair, Q(x) : x est un nombre impair.
x (pair(x) ˅ impair(x)) est vrai mais
( x pair(x)) ˅ ( x impair(x)) est faux puisque ( x pair(x)) est faux et ( x impair(x)) est faux aussi
Exemple 2 : D est quelconque , P est quelconque et Q = P
ii. Vrai iii. Vrai iv. Faux Même exemples que i : ( x pair(x)) ( x impair(x)) est vrai puisque, par exemple, pair(2) impair(3) est vrai mais il n’existe pas un entier n qui est à la fois pair et impair (c.-à-d. pair(n) impair(n)) donc x (pair(x) impair(x)) est faux.
Exercice 3 : Soient les prédicats U(x) : x est un utilisateur, Co(x) : x est connecté, E(x) : x est un employé, Cl(x) : x est un client. Soit le domaine d’objets D : l’ensemble de toutes les personnes. On a enregistré des personnes comme utilisateurs d’un système informatique.
Formalisez en logique des prédicats les propriétés suivantes :
1. Il y’a des utilisateurs qui ne sont pas connectés
x U(x) ¬ Co(x)
2. Il y’a au moins un utilisateur qui est connecté
x U(x) Co(x)
3. Chaque utilisateur est soit connecté soit déconnecté.
x U(x) Co(x) ˅ ¬ Co(x)
4. Il y’a deux groupes d’utilisateurs : les employés et les clients
a. Dans le cas où il y’a seulement ces deux groupes x U(x) E(x) ˅ Cl(x)
b. Dans le cas où l’existence d’autres groupes n’est pas exclue
( x U(x) E(x)) ( x U(x) Cl(x))
4a. Il y’a seulement deux groupes d’utilisateurs : les employés et les clients x U(x) E(x) ˅ Cl(x)
4b. Il y’a seulement deux groupes d’utilisateurs qui sont disjoints : les employés et les clients x U(x) ( E(x) ¬ Cl(x)) ˅ ( ¬ E(x) Cl(x)) 2/4 x U(x) ¬ (E(x) Cl(x)) x U(x) (¬ E(x) Cl(x))
5. Il y’a au plus un utilisateur employé qui est connecté
( x U(x) E(x) ¬ Co(x) ) ˅
( x (U(x) E(x) Co(x) ( y . U(y) E(y) Co(y) x = y)))
ou bien ( x U(x) E(x) ¬ Co(x) ) ˅ ( ! x (U(x) E(x) Co(x)))
6. Tous les utilisateurs connectés sont des employés
x U(x) Co(x) E(x)
7. Les utilisateurs connectés sont soit tous des employés soit tous des clients ( x . U(x) Co(x) E(x)) ˅ ( x . U(x) Co(x) Cl(x))
7a. Les utilisateurs connectés sont tous des employés ou des clients ( x . U(x) Co(x) E(x) ˅ Cl(x)))
Exercice 4 : En supposant les prédicats Père(p,q), Mère(p,q) (signifie p est père (mère) de q) et Féminin(q) (signifie q est féminin) et les constantes Jamel, Kamel et Wafa, exprimez chacun des énoncés suivants en logiques des prédicats :
1- Wafa a une fille (peut être plusieurs, et peut être des fils aussi). x Féminin(x) Mère(Wafa, x)
2- Wafa a exactement une fille (mais peut aussi avoir des fils). x (Féminin(x) Mère(Wafa, x) ( y Féminin(y) Mère(Wafa, y) x = y))
3- Wafa a exactement un enfant, qui est une fille.
x (Féminin(x) Mère(Wafa, x) ( y Mère(Wafa, y) x = y)) ou bien ! x (Féminin(x) Mère(Wafa, x))
4- Wafa a au moins un enfant avec Jamel, et aucun avec personne d’autre.
x ( Mère(Wafa, x) Père(Jamel, x) ( y z Mère(Wafa, y) Père(z, y) z = Jamel))
4’ Wafa et Jamel on exactement un enfant ensemble.
x ( Mère(Wafa, x) Père(Jamel, x) 3/4 ( y Mère(Wafa, y) Père(z, y) x=y))
7- Wafa n’a pas des frères (elle peut avoir des sœurs) a. Même père et même mère :
m p x Mère (m, Wafa) Mère(m, x) Père(p, Wafa) Père(p, x)
Féminin(x)
b. Au moins un parent en commun :
x y (Mère (x, Wafa) Mère(x, y)) ˅ (Père(x, Wafa) Père(x, y)) Féminin(x)
8- Wafa a des enfants qui sont tous des garçons
( x Mère(Wafa, x)) y Mère(Wafa, y) ¬ Féminin (y)
9- Jamel n’a pas des cousins (ni cousins et ni cousines, notion de frères signifie au moins l’un des parents est en commun) ¬ ( x y z t (t ǂ x (Père(x, Jamel) ˅ Mère(x, Jamel)) (Père(y, x)) ˅ Mère(y, x)) (Père(t, z) ˅ Mère(t, z)) (Père(y, t) ˅ Mère(y, t))) )
Exercice 5: (sans correction)
Soient les prédicats J et G et les constante a et f définis de la manière suivante :
a : l’équipe d’Allemagne. f : l’équipe de France.
J (x; y) : x a joué un match contre y. G (x; y) : x a gagné contre y. Exprimer en logique du premier ordre, en utilisant les prédicats et les constantes définis ci- dessus, les assertions suivantes : 1. L’équipe de France a gagné un match et en a perdu un. 2. L’équipe de France et l’équipe d’Allemagne ont fait match nul. 3. Une équipe a gagné tous ses matchs. 4. Aucune équipe n’a perdu tous ses matchs. 5. L’équipe d’Allemagne a gagné tous ses matchs sauf un. 6. Tous ceux qui ont joué contre une équipe qui a gagné tous ses matchs, ont gagné au moins un match
