Université Sorbonne Paris-Nord L1 informatique
Logique pour l’informatique - Partiel 2
Durée 3h - barême donné à titre indicatif
Exercice 1 (4 points - extrait du partiel 2023) :
On considère les deux connecteurs logiques définis pas les tables de vérités suivantes :
X Y X •Y X □Y
0 0 0 1
0 1 1 1
1 0 0 0
1 1 0 0
Question 1 (2 points) – Montrer que le système {•} n’est pas complet.
Question 2 (2 points) – Le système {•, □} est-il complet ? Si oui, est-il minimal ?
Exercice 2 (4 points) :
On définit par induction sur les formules du calcul des prédicats les fonctions suivantes :
1. le nombre de connecteurs cn(F )
— cn(R(t1 . . . tn )) = 0 pour tout R, t1 . . . tn
— cn(¬F ) = cn(F ) + 1
— cn(F ⋆ G) = cn(F ) + cn(G) + 1 pour ⋆ ∈ {∧, ∨, ⇒}
— cn(∀xF ) = cn(F )
— cn(∃xF ) = cn(F )
2. le nombre de quantificateurs qt(F )
— qt(R(t1 . . . tn )) = 0 pour tout R, t1 . . . tn
— qt(¬F ) = qt(F )
— (F ⋆ G) = qt(F ) + qt(G) pour ⋆ ∈ {∧, ∨, ⇒}
— qt(∀xF ) = qt(F ) + 1
— qt(∃xF ) = qt(F ) + 1
3. la longueur lg(F )
— lg(R(t1 . . . tn )) = 1 pour tout R, t1 . . . tn
— lg(¬F ) = lg(F ) + 1
— (F ⋆ G) = lg(F ) + lg(G) + 1 pour ⋆ ∈ {∧, ∨, ⇒}
— lg(∀xF ) = lg(F ) + 1
— lg(∃xF ) = lg(F ) + 1
Question 1 – (1 point) Soit F = ∀x(R(x) ⇒ ∃y(S(x, y) ∧ R(y))). Calculer cn(F ), qt(F ), et lg(F ).
Question 2 – (1 point) Donner une formule F telle que cn(F ) = 1, qt(F ) = 1, et lg(F ) = 3.
Question 3 – (2 points) Pour tout F , montrer que cn(F ) + qt(F ) < lg(F ).
page 1
Université Sorbonne Paris-Nord L1 informatique
Exercice 3 (4 points) :
Formaliser les énoncés suivants en calcul des prédicats. Préciser à chaque fois la signification des prédicats
que vous utilisez.
1. Jean n’a pas perdu un seul cheveu.
2. Tout le monde est furieux dès que quelqu’un fait du bruit.
3. Qui veut noyer son chien l’accuse de la rage.
4. Chaque étudiant, s’il fait un stage, doit le faire valider par tous les professeurs.
Exercice 4 (4 points) :
Question 1 (2 points) – Pour chaque formule ci-dessous, dire quelle propriété vue en cours est représentée par la
formule.
1. ∀x∀y(R(x, y) ⇒ R(y, x))
2. ∀x∀y((A(x) ∧ A(y)) ⇒ ∃z(A(z) ∧ (R(x, z) ∧ R(y, z))))
3. ∀x∀y((R(x, y) ∧ (R(y, x))) ⇒ x = y)
4. ∃z((∀x(A(x) ⇒ R(x, z))) ∧ ∀y((∀x(A(x) ⇒ R(x, y))) ⇒ R(z, y)))
Question 2 (1 point) – Donner une interprétation dans laquelle toutes les formules sont vraies (une seule in-
terprétation pour les 4 formules).
Question 3 (1 point) – Donner une interprétation dans laquelle toutes les formules sont fausses (une seule
interprétation pour les 4 formules).
Exercice 5 (4 points) :
On rappelle les règles de la déduction naturelle.
Γ ⊢dn F Γ ⊢dn G Γ ⊢dn F ∧ G Γ ⊢dn F ∧ G
ax ∧-i ∧-eg ∧-ed
Γ, F ⊢dn F Γ ⊢dn F ∧ G Γ ⊢dn F Γ ⊢dn G
Γ ⊢dn F Γ ⊢dn G Γ ⊢dn F ∨ G Γ, F ⊢dn H Γ, G ⊢dn H
∨-ig ∨-id ∨-e
Γ ⊢dn F ∨ G Γ ⊢dn F ∨ G Γ ⊢dn H
Γ, F ⊢dn G Γ ⊢dn F ⇒ G Γ ⊢dn F
⇒-i ⇒-e
Γ ⊢dn F ⇒ G Γ ⊢dn G
Γ, F ⊢dn G Γ, F ⊢dn ¬G Γ ⊢dn F Γ ⊢dn ¬F Γ ⊢dn ¬¬F
¬-i ¬-e raa
Γ ⊢dn ¬F Γ ⊢dn G Γ ⊢dn F
Γ ⊢dn ∀xF Γ ⊢dn F Γ ⊢dn ∃yF Γ, F ⊢dn G Γ ⊢dn F {t/x}
∀-e ∀-i ∃-e ∃-i
Γ ⊢dn F {t/x} Γ ⊢dn ∀yF Γ ⊢dn G Γ ⊢dn ∃xF
pour tout terme t, y ∈
/ VL(Γ) et y ∈
/ VL(G). On pourra utiliser si besoin les règles suivantes.
Γ ⊢dn F
aff tex
Γ, G ⊢dn F ⊢dn F ∨ ¬F
Question 1 (2 points) – Écrire la preuve en déduction naturelle de (X ⇒ ¬Y ), (Y ∨ Z) ⊢dn (X ⇒ Z).
Question 2 (2 points) – Écrire la preuve en déduction naturelle de ∃x¬P(x) ⊢dn ¬(∀yP(y)).
page 2
