Département d’Informatique
Logique Mathématique
Série n°01
Exercice 01
1°) Soit P désignant la proposition «l’enfant sait lire» et R désignant la proposition «l’enfant sait
écrire ». Donner la traduction dans le langage courant des propositions suivantes :
(1) P R ; (2) P ( R) ; (3) (R → P) ; (4) ( P) ( R) ; (5) ( P) ( R)
2°) Même question avec P la proposition «l’homme est mortel» et R désignant la proposition
« l’homme est éternel » et les propositions :
(1) (P R) ; (2) ( P) ( R) ; (3) (P R) ; (4) P ( R) ; (5) (P → ( R))
Exercice 02: Traduire les énoncés suivants dans le langage propositionnel
• Si tu échoues à tes examens, tu ne partiras pas en vacances.
• Si une fonction est dérivable, elle est continue.
• Si un naturel est impair, il n’est pas divisible par 2.
• Si je ne peins pas mon portail en fer, il va rouiller.
• On partira en pique-nique à condition qu’il fasse beau.
• Si les hirondelles se rassemblent, elles commencent leur migration.
Exercice 03 : Supprimer les parenthèses superflues :
• (( P) Q) → R
• Q (P → R)
• P →((Q R) → (Q R))
• (P→ Q) (P →( R))
Exercice 04 : Montrer que les formules suivantes sont des tautologies :
• (P Q) (P→Q) (Q→P)
• (P→ Q) ( PQ)
• (PQ) ( P→Q)
Exercice 05
Soit les faits suivants :
• Si Hicham vient on joue aux cartes.
• Si Hicham et Khaled viennent, il y a des disputes.
• Si on ne joue pas aux cartes, il n’y a pas de dispute.
• Hicham ne vient pas
1) Représenter en calcul propositionnel les quatre faits.
2) Peut-on déduire de ces quatre faits qu’il n’y aura pas de dispute ?
Exercice 06
Trois collègues, Ali, Badis et Djamel déjeunent ensemble chaque jour ouvrable. Les affirmations
suivantes sont vraies : 1. Si Ali commande un dessert, Badis en commande un aussi. 2. Chaque
jour, soit Badis, soit Djamel, mais pas les deux, commandent un dessert. 3. Ali ou Djamel, ou les
deux, commandent chaque jour un dessert. 4. Si Djamel commande un dessert, Ali fait de même.
Questions
1. Exprimer les données du problème comme des formules propositionnelles
2. Que peut on en déduire sur qui commande un dessert ?
3. Pouvait-on arriver à la même conclusion en supprimant l'une des quatre affirmations?
Exercice 07 :
A peine sorti de l’USDB, Youcef Oboulo se rue sur les annonces d’emploi, persuadé que la qualité
de la formation reçu dans cette université sera immédiatement reconnue par les entreprises les
plus prestigieuses. Effectivement, en réponse à l’une de ces 5687 candidatures spontanées, le
responsable du service des ressources humaines de la World Compagnie Inc., le convoque pour
un entretien décisif. Remonté à bloc, Youcef Oboulo, se précipite vers le premier train en
partance pour Alger, où il est convoqué. En chemin, il fait le raisonnement suivant :
1) En cas de grève, le train sera en retard ou annulé.
2) Ne pas réussir l’audition et manquer le rendez-vous sont les deux causes les plus sures de
ne pas être embaucher.
3) Réussir à l’entretien est synonyme d’embauche.
4) Qui dit train en retard dit rendez-vous manqué.
5) Une chose est sur, je ne raterai pas l’audition.
(C) Donc, seule une grève peut empêcher mon embauche.
Angoissé à l’idée d’avoir son avenir suspendu aux décisions des organisations syndicales, Youcef
Oboulo tente d’écarter ses idées noires en traduisant en logique des propositions son
raisonnement. Saurez- vous l’aider ?
Exercice 08:
Vous êtes perdu dans le désert. Vous arrivez à une bifurcation. Chacune des 2 pistes est gardée
par un sphinx que vous pouvez interroger. Les pistes peuvent soit conduire à une oasis, soit se
perdre dans un désert profond.(au mieux elles conduisent toutes à un oasis, au pire elles se
perdent toutes les deux).
A : le sphinx de droite vous répond : “ une au moins des 2 pistes conduit à une oasis ”
B : le sphinx de gauche vous répond : “ La piste de droite se perd dans le désert ”
C : vous savez que les 2 sphinx disent tous les deux la vérité ou bien mentent tous les deux ”
On note OD la proposition :"Il y a une oasis au bout de la route de droite ” et OG la proposition :
"il y a une oasis au bout de la route de gauche”
1. Exprimer par une formule logique chacune des affirmations A et B et la connaissance C.
2. Résoudre cette énigme
Exercice 09:
Un crime horrible a été commis au département informatique : les PC de la salle d’informatique
qui faisaient l'an dernier encore de l'Université un musée, ont été remplacés par des ordinateurs
flambants neufs !Le détective chargé de cette difficile enquête, est arrivé à isoler trois suspects.
Voici le résumé de leur dépositions :
(TA) Anass : Billel est coupable et Karim n’a rien à voir là dedans..
(TB) Billel : Si Anass a fait le coup alors Karim aussi.
(TK) Karim : Je suis innocent, mais l’un des deux autres au moins est coupable.
1. Traduisez l’énoncé précédent en calcul propositionnel.
2. Les témoignages sont-ils compatibles ?
3. En supposant que tous sont innocents, lequel aurait produit un faux serment ?
4. En supposant que le témoignage de chacun des suspects est vrai qui est innocent, qui est
coupable ?
5. En supposant que l’innocent a dit la vérité et que le coupable a menti, qui est innocent et qui
est coupable ?
Exercice 10 : Lesquelles des propositions suivantes sont valides ?
• ╞ (╞ et ╞ )
• ╞ (╞ ou ╞ )
• ╞ → (si ╞ alors ╞ )
• ╞ (╞ si et seulement si ╞ )
• ( ), → ╞
• Si , ╞ alors , ╞
• Si , ╞ alors , ╞
Exercice 11 :
- On définit le connecteur de Sheffer noté | (barre de Sheffer) par : 𝑝 | 𝑞 = (𝑝 ∧ 𝑞)
a. Donner la table de vérité de la formule 𝑝 | 𝑞
b. Donner la table de vérité de la formule ((𝑝 | 𝑞 ) | (𝑝 | 𝑞 ))
c. Exprimer les connecteurs usuels en utilisant la barre de Sheffer, et rien qu'elle.
Exercice 12 :
Mettre chacune des formules suivantes sous forme normale conjonctive et sous forme normale
disjonctive.
• P (S ((Q R) → P))
• ((( P → Q) → R) →S)
• (P (P → Q)) → Q)
• (P Q) ( P → Q)
• (p → (q → r)) → (r ∨ p)
• ((q ∨ r) → p) ∧ ( q → (p ∧ r))