Université Constantine 2- Abdelhamid Mehri Janvier 2017
Faculté NTIC
Module : Logique Mathématique
Contrôle
EXERCICE-1 (5points)
Ali, Bachir et Cherif sont accusés d’espionnage. Ils font les déclarations suivantes :
• Ali : « Bachir est un espion mais Cherif ne l’est pas. »
• Bachir : « Si Ali est un espion alors Cherif aussi est un espion. »
• Cherif : « Je ne suis pas un espion mais au moins l’un des deux autres est un espion. »
1- Formuler les trois déclarations en logique propositionnelle.
2- Les trois déclarations sont-elles compatibles ? Justifier.
3- Parmi les trois déclarations, existe-t-il une déclaration conséquence d’une autre ?Justifier.
4- On suppose que les trois déclarations sont vraies, qui est l’espion ? Justifier.
5- On suppose que Ali, Bachir et Cherif ne sont pas des espions, qui a fait une fausse
déclaration ? Justifier.
6- On suppose qu’un espion ne dit jamais la vérité et qu’un innocent dit toujours la vérité,
qui est l’espion ?
EXERCICE-2 (8 points)
A- Soit la formule propositionnelle suivante : ϕ = ( (B→A)→B)
1- Donner l’arbre de décomposition de ϕ.
2- Déduire la notation polonaise de ϕ et la profondeur de ϕ .
3- Mettre ϕ sous FND sans utiliser la table de vérité.
B- Soit la suite des formules propositionnelles suivantes :
ϕ1 = A ( où A et B sont des variables propositionnelles)
ϕ2 = B
ϕ3 = (B→A)
ϕ4 = (ϕ3→ϕ2)
…
ϕn-1 = (ϕn-2→ϕn-3)
ϕn = (ϕn-1→ϕn-2)
1- Montrer que quelque soit n la formule ϕn n’est pas valide.
2- Etudier (en fonction de n) la satisfaisabilité de ϕn.
3- Etudier en fonction de n la compatibilité de Σ={ϕ1, ϕ2,.. ϕn}.
C- Démontrer par déduction le séquent suivant : B∧A | (B→A)
On pourra utiliser les règles d’inférence suivantes :
Σ , ϕ | ϕ1∧ϕ1 i Σ|ϕ1 Σ|ϕ2 ∧i Σ|ϕ1→ϕ2 Σ|ϕ1 MP
Σ |ϕ Σ| ϕ1∧ϕ2 Σ|ϕ2
Σ|ϕ1∧ϕ2 ∧e1 Σ|ϕ1∧ϕ2 ∧e2
Σ| ϕ1 Σ| ϕ2
QCM-1
Nom :……………………………….. Prénom :…………………… . Groupe :……..
A- Répondre par VRAI ou FAUX aux assertions suivantes :
NB. Réponse correcte : + 0,5 pt Réponse incorrecte : -0,5 pt Pas de Réponse : 0 pt
Assertions Réponses
1 Une proposition est une formule de la logique propositionnelle
2 B→(AvAvA) a 5 sous-formules
3 La notation polonaise de la formule A↔B→Cv D est ↔→ABvCD
4 ∀ϕ Complexité (ϕ) > Profondeur(ϕ)
5 Si ϕ= A ∧ C Alors ϕ[ AvB / A][CvD / C] =A v B ∧ (CvD)
6 ∀ϕ :formule propositionnelle ∀A,B :variables propositionnelles ϕ[ B/A][A/B] = ϕ
7 ({ϕ1,ϕ2,ϕ3,ϕ4} compatible) ⇔ ( ϕ1∧ϕ2∧ϕ3∧ϕ4 satisfaite)
8 ϕ1,ϕ2,ϕ3,ϕ4 | ϕ2v ϕ3
9 ϕ1=AvB est une FNC de ϕ2=BvA∧( C∧C)
10 ∀x (p(x) →f(x)≡ p(x)) est une formule de la logique du premier ordre
B- Formuler en logique du premier ordre les énoncés E1,E2,E3 en utilisant les prédicats
t(x) : x est un tiroir d(x,y) : x est dans y f(x) : x est une feuille
N.B. Réponse correcte :+1point Réponse incorrect :-0,5point Pas de réponse : 0 point
E1 : Dans chaque tiroir il y a au moins une feuille
E2 : Chaque feuille est dans un seul tiroir
E3 : Certains tiroirs sont vides
QCM-2
Nom :……………………………….. Prénom :…………………… . Groupe :……..
A- Répondre par VRAI ou FAUX aux assertions suivantes :
NB. Réponse correcte : + 0,5 pt Réponse incorrecte : -0,5 pt Pas de Réponse : 0 pt
Assertions Réponses
1 La notation polonaise de la formule AvB↔C→A est ↔→v A B C A
2 (B∨A)∨B a 5 sous-formules
3 Une proposition atomique est une formule de la logique propositionnelle
4 ∀ϕ Profondeur (ϕ) < Complexité(ϕ)
5 Si ϕ= A∧B Alors ϕ[AvB/A, CvD/B] =AvB∧(CvD)
6 ∀ϕ :formule propositionnelle ∀A,B :variables propositionnelles ϕ[ A/A][A/B] [B/A] = ϕ
7 ({ϕ1, ϕ2,ϕ3} compatible) ⇔ ( ϕ1∧ϕ2∧ϕ3 satisfaite)
8 ∃y (p(y) ≡ f(y) →f(y)) est une formule de la logique du premier ordre
9 ϕ1=A∧B est une FND de ϕ2=B∧Av ( C∧C)
10 ϕ1,ϕ2,ϕ3,ϕ4 | ϕ2vϕ3vϕ4
B- Formuler en logique du premier ordre les énoncés E1,E2,E3 en utilisant les prédicats
A(x) : x est un amphi d(x,y) : x est dans y E(x) : x est un étudiant
N.B. Réponse correcte :+1point Réponse incorrect :-0,5point Pas de réponse : 0 point
E1 : Dans chaque amphi il y a au moins un étudiant
E2 : Certains amphis sont vides
E3 : Chaque étudiant est dans un seul amphi
Corrigé Abrégé du Contrôle
QCM1
1 F
2 F
3 F
4 F E1 : ∀x( t(x) → ∃y( f(y)∧d(y,x) ))
5 V E2 : ∀x( f(x)→ ∃y (t(y)∧d(x,y)∧∀z ( t(z)∧z=y→d(x,z))))
6 F E3 : ∃x (t(x)∧∀yd(y,x))
7 V
8 V
9 F
10 F
QCM2
Exercice-1
1- Les VP A : Ali est un espion B : Bachir est un espion C : Cherif est un espion
Les formules : F1= B∧C F2= A→C F3=C∧(AvB)
2- La table de vérité
A B C F1 F2 F3
V1 0 0 0 0 1 0
V2 0 0 1 0 1 0
V3 0 1 0 1 1 1
V4 0 1 1 0 1 0
V5 1 0 0 0 0 1
V6 1 0 1 0 1 0
V7 1 1 0 1 0 1
V8 1 1 1 0 1 0
{F1,F2,F3}compatible car ∃v v=V3 tel que [F1]v= [F2]v= [F3]v= 1
3- F3 est conséquence de F1 car tous les modèles de F1 (V3 et V7) sont modèles de F3
4- D’après la table de vérité, quand F1,F2,F3 sont vraies on a :
V(A)=0 V(B)=1 V(C)=0 ⇒ Bachir espion
5- Ali,Bachir, Cherif ne sont pas espions ⇒ V(A)=V(B)=V(C)=0
⇒ [F1]v=0 [F2]v=1 [F3]v= 0⇒ Ali et Cherif ont fait de fausses déclarations
6- On cherche V/ V(A)= [F1]v V(B)= [F2]v V(C)= [F3]v
D’après la table de vérité V=V6 ⇒ Ali et Cherif espions
Exercice-2
A- 1-Arbre de décomposition ( (B→A)→B)
(B→A)→B
(B→A) B
B→A
B A
2- Notation polonaise : →→B A B Profondeur=4
3- FND= B∧B
B- Soit la suite des formules propositionnelles suivantes :
ϕ1 = A ( où A et B sont des variables propositionnelles)
ϕ2 = B
ϕ3 = (B→A)
ϕ4 = (ϕ3→ϕ2)
…
ϕn-1 = (ϕn-2→ϕn-3)
ϕn = (ϕn-1→ϕn-2)
1- ϕn n’est pas valide :
• n=1 ϕn=A non satisfaite pour V(A)=0
• n=2 ϕn=B non satisfaite pour V(B)=0
• n=3 ϕn= (B→A) non satisfaite pour V(A)=0 V(B)=0
• n>3 ϕn= B∧B (d’après A-3) antilogie
2- Satisfaisabilité de ϕn.
• n=1 ϕn=A satisfaite pour V(A)=1
• n=2 ϕn=B satisfaite pour V(B)=1
• n=3 ϕn= (B→A) satisfaite pour V(A)=0 V(B)=1
• n>3 ϕn= B∧B (d’après A-3) non satisfaite
3- Compatibilité de Σ={ϕ1, ϕ2,.. ϕn}.
• n=1 Σ={ϕ1 }compatible pour V(A)=1
• n=2 Σ={ϕ1, ϕ2 } compatible pour V(A)=1, V(B)=1
• n=3 Σ={ϕ1, ϕ2, ϕ3} non compatible
• n>3 Σ={ϕ1, ϕ2,.. ϕn} non compatible
C- Démonstration de: B∧A | (B→A)
1. B∧A B→A | B∧A Axiome
2. B∧A B→A | B ∧e1 (1)
3. B∧A B→A | B→A Axiome
4. B∧A B→A | A MP(3,2)
5. B∧A B→A | A ∧e2(1)
6. B∧A B→A | A ∧A ∧i (4,5)
7. B∧A | (B→A) i (6)
