Logique : IAP1 - contrôle continu - groupes 1 et 2
Mardi 16 mars 2010 - Sans documents - durée : 1h30
Les exercices sont indépendants.
1 Logique des propositions
Exercice 1
Prouver les séquents suivants en déduction naturelle :
Question 1
((A ⇒ B) ∧ ¬B) ` ¬A
Question 2
((A ∧ B) ⇒ C) ` (A ⇒ (B ⇒ C))
Exercice 2
On considère les propositions suivantes :
• Si Alice et Julie viennent à Paris, Zoé viendra aussi
• Si Julie vient à Paris, Alice aussi
• Julie ou Zoé, l’une des deux au moins, viendra à Paris.
Question 3
Formaliser ces 3 propositions en logique des propositions.
Question 4
Peut-on déduire de ces propositions que
• Alice viendra à Paris ?
• Julie viendra à Paris ?
• Zoé viendra à Paris ?
Pour chacune des questions, on donnera une preuve en déduction naturelle lorsque c’est possible.
Exercice 3
Soit F une formule propositionnelle construite à partir des seuls connecteurs ∧ et ∨ (et à partir
de variables propositionnelles). Soient p1 , . . . , pn ses variables propositionnelles.
Question 5
Montrer que si v est une interprétation telle que v(pi ) = 1 pour tout i ∈ {1, ..., n}, alors v(F ) = 1.
Exercice 4
Soient F et G deux formules sans variable propositionnelle commune.
Question 6
Montrer que si F ⇒ G est une tautologie, alors l’une au moins des formules ¬F et G est une
tautologie.
1
2 Logique des prédicats
Exercice 5
Considérons le langage du premier ordre L = {R, S, =, f, g, a} où
• R, S et = désignent deux symboles de relation binaire
• f et g désignent deux symboles de fonctions, f d’arité 1 et g d’arité 2
• a désigne un symbole de constante
Soit F la formule suivante,
∀y(∃z(R(y, g(z, a)) ∨ S(x, y))) ∧ ∃y(g(x, a) = y ⇒ ¬S(y, z))
Question 7
Souligner dans F les termes (on ne soulignera pas les sous-termes) et encadrer les formules
atomiques (utiliser si possible des couleurs différentes)
Question 8
Préciser dans F les variables libres et liées.
Question 9
Dans F renommer les variables de sorte que les variables libres n’aient plus aucune occurrence
liée et qu’aucune variable ne soit quantifiée plus d’une fois.
Exercice 6
On reprend le langage L de l’exercice précédent. Soit F la formule
∃y(∀z(R(x, w) ⇒ f (x) = y)) ∧ (z = g(x, y)) ∧ ∀z∃x(f (z) = g(x, x))
Pour chacun des termes suivants t, écrire F [x := t] (c’est-à-dire la substitution de t à la variable x
dans F ).
• t = g(w, a)
• t = g(f (y), y)
• t = g(x, y)
• t = g(x, z)
Exercice 7
Considérons deux personnes appelées Alice et Zola représentées par des constantes a et z, et le
roman Germinal représenté par la constante g. En utilisant les prédicats
• R(y) interprété par y est un roman
• H(x) interprété par x est un être humain
2
• E(x, y) interprété par x a écrit y
• L(x, y) interprété par x a lu y
et le prédicat =,
formaliser les énoncés suivants :
1. Alice a lu Germinal
2. Quelqu’un a lu Germinal
3. Tout le monde a lu Germinal
4. Tout le monde n’a pas lu Germinal
5. Quelqu’un n’a pas lu Germinal
6. Alice a lu un roman
7. Alice a lu exactement deux romans
8. Germinal a été écrit par Zola
9. Alice a lu tous les romans de Zola
10. Alice n’a pas lu tous les romans
11. Tout le monde a lu un roman de Zola
12. Tous les romans de Zola ont été lus
13. Tous ceux qui ont écrit un roman ont lu Germinal
14. Tous les romans n’ont pas été écrits par une même personne
15. Alice n’a lu que des romans de Zola
3
∆`A
(ax) ∆, A ` A (af f )
∆, B ` A
∆, A ` B ∆`A⇒B ∆`A
(⇒i ) (⇒e )
∆`A⇒B ∆`B
∆`A ∆`B ∆ ` A∧B
(∧i) (∧eg )
∆ ` A∧B ∆`A
∆ ` A∧B ∆`A
(∧ed ) (∨ig )
∆`B ∆ ` A∨B
∆`B
(∨id )
∆ ` A∨B
∆ ` A∨B ∆, A ` C ∆, B ` C
(∨e)
∆`C
∆, A ` ⊥ ∆ ` ¬A ∆`A
(¬i) (¬e)
∆ ` ¬A ∆`⊥
∆, ¬A ` ⊥
(⊥c )
∆`A
∆ ` A si x non libre dans ∆ ∆ ` ∀x A
(∀i) (∀e)
∆ ` ∀x A ∆ ` A[x := t]
∆ ` A[x := t]
(∃i)
∆ ` ∃x A
∆ ` ∃x A ∆, A ` C si x non libre dans ∆ et C
(∃e)
∆`C