Université Larbi Tébessi -Tébessa Département MI
Logique mathématique Licence 2 - Informatique
Dimanche 08 Janvier 2023 Durée: 1 h 30 min (De 12:30 à 14:00)
Examen du Semestre 03
Questions de cours: (0.5 + 0.5 + 1 = 2 pts)
1. Qu’est ce qu’un Modèle (en logique des proposition)?
Un modèle d’une formule F est une valuation oú F est vrai.
2. Qu’est ce qu’un Modèle (en logique des Prédicat)?
On dit qu’une interprétation I est un modèle de F ssi I rend F satisfaisante(satisfiable).
3. Peut-on considérer L0 un cas particulier de L1 ? Justifier.
Le calcul propositionnel peut se voir comme un calcul des prédicats tant que :
l’ensemble des fonction est vide ;
l’ensemble des prédicats contient uniquement des prédicats 0-aires (ce sont les proposition) ;
les quantificateurs ne sont pas utilisées.
Exercice 1. ((3 × 0.5)+(2 × 0.5)+(5 × 0.5) + 1 = 6 Pts)
1. Réinsérer autant de parenthèses que possible dans chacune des expressions suivantes
(a) ¬p ∧ q ⇒ r
((¬(p) ∧ q) ⇒ r)
(b) (p ⇒ q) ∧ ¬(r ∨ p ⇒ q)
((p ⇒ q) ∧ ¬((r ∨ p) ⇒ q))
(c) p ∨ (¬q ⇒ p ∧ r)
(p ∨ (¬q ⇒ (p ∧ r)))
2. Supprimez les parenthèses inutiles dans chacune des expressions suivantes
(a) (¬(p ∧ (q ∧ r)) ⇒ (¬(p) ∨ ¬(r)))
¬(p ∧ q ∧ r) ⇒ ¬p ∨ ¬r
(b) ((¬(p ∧ (q ∨ r)) ⇒ ¬(p)) ∨ ¬(r))
(¬(p ∧ (q ∨ r)) ⇒ ¬p) ∨ ¬r
Page 1 / 5
3. dessiner les arbres syntaxique des 5 formules en haut.
∧ r
¬ q
Figure 1: 1.(a)
∧
⇒ ¬
p q ⇒
∨ q
r p
Figure 2: 1.(b)
∨
p ⇒
¬ ∧
q p r
Figure 3: 1.(c)
Page 2 / 5
⇒
¬ ∨
∧ ¬ ¬
p ∧ p r
q r
Figure 4: 2.(a)
∨
⇒ ¬
¬ ¬ r
∧ p
p ∨
q r
Figure 5: 2.(b)
4. Pour l’arbre syntaxique suivant, trouvez la formule logique propositionnelle qu’il représente.
¬ r
∨
p ∧
q ¬
p
¬(¬(p ∨ (q ∧ ¬p)) ⇒ r)
Exercice 2. (3 + 3 = 6 Pts)
Partie I
Aladdin trouve deux coffres A et B dans une grotte. Il sait que chacun d’eux soit contient un trésor, soit
un piège fatal.
Sur le coffre A est écrit : Au moins un de ces deux coffres contient un trésor .
Sur le coffre B est écrit : Dans A il y a un piège fatal (ne contient pas un trésor) .
Aladdin sait que : Soit les deux affirmations sont vraies, soit elles sont toutes les deux fausses.
1. Quel coffre doit-il ouvrir en étant sûr qu’il y trouvera un trésor ? Justifier.
Considérons un langage propositionnel où
Page 3 / 5
p : ”Le coffre A contient le trésor alors ¬p : ”Le coffre A contient un piège fatal”
et
q : Le coffres B contient le trésor .alors ¬q : ”Le coffre B contient un piège fatal”
Formalisation:
Au moins un de ces deux coffres contient un trésor
F ≡p∨q
Dans A il y a un piège fatal (ne contient pas un trésor)
G ≡ ¬p
Soit les deux affirmations sont vraies, soit elles sont toutes les deux fausses.
H≡F ⇔G
Ce que nous pouvons faire est de vérifier s’il existe une interprétation satisfaisant la formule H
la table de vérité
p q F G H
0 0 0 1 0
0 1 1 1 1
1 0 1 0 0
1 1 1 0 0
D’après la table de vérité La seule interprétation satisfaisant H est :
v(a) = F et v(b) = T
Ainsi Aladdin peut ouvrir le coffre B, étant sûr qu’il contient un trésor.
Partie II
en utilisant la résolution, Que peut-on dire sur la validité de l’argument suivant?
{(p ⇒ q), (r ⇒ ¬p), r} ¬q
F ≡ (p ⇒ q) ∧ (r ⇒ ¬p)landr ∧ ¬¬q
F ≡ (¬p ∨ q) ∧ (¬r ∨ ¬p)landr ∧ q ........FNC
C = {¬p ∨ q), (¬r ∨ ¬p), r, q}
N = {¬p}
C = {¬p ∨ q), (¬r ∨ ¬p), r, q, ¬p}
N = {¬p}
N ⊂ C alors{(p ⇒ q), (r ⇒ ¬p), r} 2 ¬q
Exercice 3. ((0.5 × 4 )+ (2 × 2) = Pts)
Soient f et h deux fonctions. Soient P et Q des prédicats et et soit a, b, c des constants.
on Définit une interprétation par :
Domaine : D = {1, 2, 3}
une fonction d’interprétation I:
– I(constantes) = {a 7→ 1, b 7→ 2, c 7→ 3}
– I(f ) = {f (1) 7→ 2, f (2) 7→ 3, f (3) 7→ 1}
– I(h) = {(x, y) 7→ min{x, y}} (min est la fonction minimale)
– I(P ) = {P (1) 7→ 1, P (2) 7→ 0, P (3) 7→ 1}
– I(Q) = {Q(1, 1) 7→ 0, Q(1, 2) 7→ 1, Q(1, 3) 7→ 0, Q(2, 1) 7→ 0, Q(2, 2) 7→ 0, Q(2, 2) 7→ 0, Q(3, 1) 7→
1, Q(3, 2) 7→ 0, Q(3, 3) 7→ 1, }
Quelle est la signification de chacune de ces formules dans cette interprétation ?
1. f (h(f (a), f (c))) = 2
Page 4 / 5
2. f (h(b, f (a)))= 3
3. Q(f (c), a)≡ 1
4. P (h(f (a), f (c)))≡ 1
5. ∀x, P (x)≡ 0
6. ∀x, ∃y, (P (x) ⇒ Q(x, y))≡ 1
Page 5 / 5