Previous Up
Eléments de logique pour l’informatique 2020–21                   http://www.lri.fr/~paulin/Logique

Annexe A  Correction des exercices

A.1  Exercices du chapitre 1

Exercice 1
  1. ∀ x y, ami(self,x)∧ ami(x,y)⇒ ami(self,y)
  2. ∀ x, joue(self,x)⇒ ami(self,x)
  3. ¬ ∃ x, joue(self,x) ∧ ami(self,x) ou de manière équivalente ∀ x, ¬ joue(self,x) ∨ ¬ ami(self,x)
  4. ∃ x y, joue(self,x) ∧ joue(self,y)∧ ¬(x=y) sans la mention de x≠y la formule est vraie dès qu’il existe une personne avec qui je joue.
  5. ∀ x, ∃ y, ami(x,y)
Exercice 2

∀ x y, pair(x)∧ pair(y)⇒ pair(x+y)

Exercice 3
Exercice 4

La formule parenthésée est (∀ x, (P ⇒ Q)) ⇒ ((¬ Q) ⇒ (¬ (∃ x, P))) et sous forme d’arbre :

Exercice 5

Les formules parenthésées sont (P ⇒ (Q ⇒ R)) ⇒ ((P ∧ Q) ⇒ R) et (P ⇒ Q) ⇒ ((¬ Q) ⇒ (¬ P)) et sous forme d’arbre

Exercice 6
Exercice 7

La seule variable libre de la formule : ∀ b, b > 0 ⇒ ∃ q, ∃ r, a = b × q + r ∧ r < b est a.

Exercice 8
  1. La formule ((P ⇒ Q) ⇒ P) ⇒ P est valide. En effet soit P est vrai et elle est vraie. Soit P est faux, mais alors P ⇒ Q est vrai et donc (P ⇒ Q) ⇒ P est faux et donc ((P ⇒ Q) ⇒ P) ⇒ P est vrai. Dans toutes les interprétations possibles, la formule est vraie. Donc elle est valide.
  2. La formule (¬ P ⇒ P) ⇒ P est valide. En effet soit P est vrai et elle est vraie. Soit P est faux, mais alors ¬ P est vrai et donc ¬ P ⇒ P est faux et donc (¬ P ⇒ P) ⇒ P est vrai. Dans toutes les interprétations possibles, la formule est vraie. Donc elle est valide.
Exercice 9

On peut faire une table de vérité de cette dernière formule en fonction des valeurs de P1 et P2 et chercher dans quels cas elle est vraie.

On peut aussi raisonner directement.

Comme A2 est de la forme A1 ∨ B, si A1 est vrai alors A2 est vrai et donc la troisième formule est fausse. Donc A1 est faux et A2 est vrai et on a P2 ∧ ¬ P1 donc il faut ouvrir la deuxième porte.

Exercice 10

La formule (∀ x, P(x)) ⇒ ∃ x, P(x) est vraie quelle que soit l’interprétation de P. En effet si on se donne une interprétation I sur une domaine D, qui rend vraie ∀ x, P(x). L’interprétation de P est vraie pour toutes les valeurs dans le domaine D. Comme le domaine est non vide, on peut choisir d∈ D. L’interprétation de P est vraie pour d et donc ∃ x, P(x) est vraie dans cette interprétation.

La formule ¬(∀ x, P(x)) ⇒ ∃ x, ¬ P(x) est vraie quelle que soit l’interprétation de P. En effet si on se donne une interprétation I sur une domaine D, qui rend vraie ¬(∀ x, P(x)). Cette interprétation rend faux ∀ x, P(x) ce qui veut dire qu’il existe d∈ D pour lequel l’interprétation P est fausse et donc l’interprétation de ∃ x, ¬ P(x) est vraie.

Exercice 11

t ≤ u  =def  ∃ n, n+t=u.

Exercice 12

Il est nécessaire en plus du prédicat pos(i,j,k) qui exprime que le chiffre k est sur la case (i,j) de disposer du prédicat d’égalité pour pouvoir dire qu’un chiffre apparait au plus une fois.

  1. Un seul chiffre k par case (i,j): ∀ i j k, pos(i,j,k) ⇒ ∀ l, ¬ l=k⇒ ¬ pos(i,j,l)
  2. Chaque chiffre k apparaît sur chaque ligne i au moins dans une colonne j: ∀ i k, ∃ j, pos(i,j,k)
  3. Chaque chiffre k apparaît au plus une fois sur chaque ligne i (s’il est dans la colonne j, il n’est pas dans une autre colonne) : ∀ i j1 j2 k, pos(i,j1,k)∧ pos(i,j2,k)⇒ j1=j2
  4. Le cas des colonnes est analogue à celui des lignes. On traite ici la notion de carré. Si on veut éviter de traiter chaque valeur de ligne et de colonne individuellement, on peut introduire un symbole de fonction tiers unaire qui, étant donné une ligne ou une colonne, va nous dire dans quel tiers du tableau elle se trouve (premier, deuxième ou troisième). On peut ainsi tester si deux positions (i1,j1) et(i2,j2) seront dans le même carré si et seulement si les indices de ligne sont dans le même tiers du tableau et de même pour les indices de colonnes.

    Pour représenter le fait que chaque chiffre k apparaît au plus une fois dans chaque carré on utilisera la formule :

    ∀ i1 i2 j1 j2 k, tiers(i1)=tiers(i2)∧ tiers(j1)=tiers(j2)
          ⇒ pos(i1,j1,k)∧  pos(i2,j2,k)
          ⇒ i1=i2∧ j1=j2

    On peut aussi représenter le fait que chaque chiffre apparaitra au moins une fois dans chaque carré de la manière suivante :

    ∀ i1 j1 k, ∃ i2 j2, tiers(i1)=tiers(i2)∧ tiers(j1)=tiers(j2)∧ pos(i2,j2,k)

    Les deux formules sont redondantes dès lors qu’il y a 9 valeurs et 9 cases puisqu’on a écrit qu’il y avait au moins une valeur par case et qu’il ne pouvait pas y avoir deux fois la même valeur, donc chaque valeur va apparaître au moins une fois (une application injective (resp. surjective) d’un ensemble fini dans un ensemble de même cardinal est bijective.

  5. reste à exprimer dans la logique le fait qu’on a 9 valeurs possibles pour les lignes, les colonnes et les chiffres dans les cases. Cela se fait en ajoutant 9 constantes :1,…,9. AInsi qu’un axiome qui dot que l’univers est formé uniquement de ces 9 éléments ∀ x,x=1∨ …∨ x=9 auquel il faut ajouter les 36 axiomes qui disent que les constantes sont différentes deux à deux ¬1=2,¬1=3,…,¬1=9,¬2=3,…, ¬8=9.

    Il faudra aussi ajouter les 9 axiomes qui permettent de raisonner sur la fonction tiers à savoir tiers(1)=1,tiers(2)=1,tiers(3)=1,…,,tiers(9)=3.

Exercice 13
nbsymb(p)=0     si p atomique 
nbsymb(¬ A)=1+ nbsymb(A) 
nbsymb(∀ x, A)= 1+nbsymb(A) 
nbsymb(∃ x, A)= 1+nbsymb(A) 
       
   
nbsymb(A∧ B)=1+ nbsymb(A)+nbsymb(B) 
nbsymb(A∨ B)=1+ nbsymb(A)+nbsymb(B) 
nbsymb(A⇒ B)=1+ nbsymb(A)+nbsymb(B)
Exercice 14
prof(p)=0     si p atomique 
prof(¬ A)=1+ prof(A) 
prof(∀ x, A)= 1+prof(A) 
prof(∃ x, A)= 1+prof(A) 
       
   
prof(A∧ B)=1+ max(prof(A),prof(B)) 
prof(A∨ B)=1+ max(prof(A),prof(B)) 
prof(A⇒ B)=1+ max(prof(A),prof(B)) 
Exercice 15
Exercice 16

On considère ici des termes qui ne contiennent pas de variable

Exercice 17

La théorie de l’égalité contient les axiomes pour la reflexivité, la symétrie et la transitivité ainsi que des axiomes pour les symboles de fonctions et les prédicats d’arité au moins 1. Dans le cas de la signature qui est donnée, il y aura donc deux axiomes

  1. ∀ x1 x2 y1 y2, x1=x2∧ y1=y2 ⇒ g(x1,y1)=g(x2,y2)
  2. ∀ x1 x2 y1 y2, x1=x2∧ y1=y2 ⇒ Q(x1,y1)⇒ Q(x2,y2)

On veut montrer que la formule t=u ⇒ v[x← t]=v[x← u] est valide : On se place dans une interprétation qui rend vraie la formule t=u (et les axiomes de l’égalité).

On commence par montrer par récurrence sur la structure du terme v que la formule v[x← t]=v[x← u] est également vraie.

On montre ensuite par récurrence sur la formule P que pour tous les termes t et u et toute interprétation qui rend vraie t=u, on a P[x← t]⇒ P[x← u] est vraie quelque soit l’environnement pour les valeurs des variables libres de P[x← t].

Exercice 1
 ℕℤℚ
∀ x, ∃ y, x < yVVV 
∀ x, ∃ y, y < xFVV  
∀ x y, x < y ⇒ x+1 ≤ yVVF 
∀ x y z, x ≤ y ⇒ x× z ≤ y × zVFF 
Exercice 2

A.2  Exercices du chapitre 2

Exercice 1

Dans chacune des interprétations (qui fixent le domaine et sur ce domaine le sens des symboles ≤, < et ×), chaque formule a une valeur de vérité V ou F qu’il convient de justifier.

  1. ∀ x, ∃ y, x < y
  2. ∀ x, ∃ y, y < x
  3. ∀ x y, x < y ⇒ x+1 ≤ y
  4. ∀ x y z, x ≤ y ⇒ x× z ≤ y × z
Exercice 2
Exercice 3

On a ⊥⇒ P≡⊤, ⊤⇒ P≡ P, P⇒ ⊤≡⊤. On peut justifier par des tables de vérité ou bien utiliser A⇒ B≡ ¬ A∨ B et utiliser les lois connues pour les connecteurs ⊥, ⊤ et ∨.

Exercice 4

On suppose que x∉VL(A).

Exercice 5

Trouver des interprétations qui justifient les résultats suivants :

Exercice 6

Le langage contient n constantes {c1;…;cn}. On note I,ρ⊨ A lorsque la formule A est vraie dans l’interprétation I et l’environnement ρ, c’est-à-dire lorsque valI(ρ, A)=V. On s’intéresse aux interprétations dans lesquelles le symbole d’égalité est interprété par l’égalité dans le domaine. C’est-à-dire que I,ρ⊨ t=u si et seulement si valI(ρ,t)=valI(ρ,u)

  1. Le cardinal du domaine d’une interprétation qui rend vraie la formule ∀ x, x=c1∨… ∨ x=cn est inférieur ou égal à n. En effet la formule dit que tout élément du domaine est égal à l’interprétation d’une des constantes ci ce qui fait qu’il y a au plus n valeurs possibles. Par contre rien n’empêche deux constantes différentes d’être interprétées par la même valeur dans le domaine, donc on peut avoir strictement moins de n éléments.

    Pour justifier le résultat plus formellement, on se donne une interprétation I sur un domaine D et on appelle C l’ensemble des interprétations des constantes {c1;…;cn}, à savoir C={valI(ci)|1≤ i≤ n}. On a C ⊆ D et |C|≤ n. On va montrer que D=C. Soit donc d∈ D. Comme I⊨ ∀ x, x=c1∨… ∨ x=cn on a I,{x↦ d} ⊨ x=c1∨… ∨ x=cn et donc comme une disjonction est vraie lorsque l’une des parties est vraie, il existe i tel que I,{x↦ d} ⊨ x=ci et donc d=valI({x↦ d},x)=valI({x↦ d},ci) et donc d∈ C.

    Les deux ensembles étant égaux ont même cardinal qui est inférieur à n.

  2. Montrons que (∀ x, x=c1∨… ∨ x=cn), (P(c1) ∧ … ∧ P(cn)) ⊨ ∀ x, P(x)

    On se donne une interprétation I de l’égalité et telle que I⊨ ∀ x y, x=y ⇒ (P(x)⇒ P(y)), I⊨ ∀ x, x=c1∨… ∨ x=cn et I⊨ P(c1) ∧ … ∧ P(cn). Soit d∈ D. On a I,{x↦ d} ⊨ x=c1∨… ∨ x=cn donc il exists i tel que I,{x↦ d} ⊨ x=c1, on a aussi I,{x↦ d}⊨ P(ci) on en déduit que I,{x↦ d}⊨ P(x) et donc I⊨ ∀ x,P(x).

    On pourrait faire le même raisonnement pour l’existentielle. On peut aussi réutiliser le résultat précédent. On peut remplacer P(x) par ¬ P(x) en utilisant la propriété 3 de remplacement d’un symbole de prédicat par une formule paramétrée. On a donc (∀ x, x=c1∨… ∨ x=cn), (¬ P(c1) ∧ … ∧ ¬ P(cn)) ⊨ ∀ x, ¬ P(x)

    On utilise ensuite le fait que pour tout ensemble de formule E et deux formules A et B, E,A⊨ B est équivalent à E,¬ B⊨ ¬ A (on peut utiliser le fait que E,A⊨ B est équivalent à E⊨ A ⇒ B et la propriété de contraposée A ⇒ B≡¬ B⇒¬ A ).

Exercice 7
Exercice 8

Soit la formule ∀ x y, (P(x)∧ Q(y) ∧ (¬ P(a) ∨ ¬ Q(a))). Le langage des termes ne contient que la constante a, celui des prédicats contient les deux symboles P et Q.

Exercice 9

A.3  Exercices du chapitre 3

Exercice 1
  1. La fonction clauseset prend pour argument un ensemble d’instances de prédicats associés à des booléens et renvoie une formule de la logique correspondant à la clause associée.
    clauseset(s) =
    si s=∅  alors ⊥
    sinon 
    soit (p,b)∈ s,s′=s\ (p,b), A=si b alors p sinon ¬ p
    dans si s′=∅ alors A sinon A∨clauseset(s′)
Exercice 2

A  =def  (∃ x, ∀ y, R(x,y)) ⇒ (∀ y, ∃ x, R(x,y)).

A.4  Exercices du chapitre 4

Exercice 1
  1. N(x,є)=? N(є,y)

    Solution : {x← є;z← є}

  2. N(N(x,y),є) =? N(є,y)

    Pas de solution : on simplifie en utilisant (7) qui amène l’équation N(x,y)=?є qui échoue (règle 6).

  3. N(x,є) =? x

    Pas de solution : échec règle (3) après avoir appliqué la règle (5) pour retourner l’équation.

Exercice 4

Il suffit de résoudre le problème : {t1=? t2;t2=? t3 … tn−1=? tn}

On peut se ramener à une seule équation : F(t1,t2,…,tn−1)=F(t2,t3, …,tn)

Exercice 3
  1. (plus(x,0)=x)=? (plus(0,y)=y)

    Solution {x← 0;y← 0}

  2. (plus(x,0)=x)=? y ≠ z

    Pas de solution car un littéral positif ne peut être égal à un littéral négatif.

  3. (plus(x,0)=x)=? (y=plus(y,0))

    Pas de solution : le problème se décompose en plus(x,0)=? y; x =? plus(y,0) qui se simplifie par les règles (5) puis (4),on obtient {y← plus(x,0)}(x =? plus(plus(x,0),0)) qui conduit à un échec suivant la règle (3).

Exercice 5
Exercice 7

Pour prouver (∃ x,¬ P(x)), (∀ x,(P(x) ∨ Q(x)))⊨ ∃ x, Q(x) en utilisant la résolution, on procède aux étapes suivantes :

  1. Mise en forme clausale
    C1
     
    def
    =
     
    		  ¬ P(a)
     C2
     
    def
    =
     
    		  P(x) ∨ Q(x)
    C3
     
    def
    =
     
    		  ¬ Q(y)
           
  2. Résolution :
    [y]a 
    [x]a C1         C2
     Q(a)
    		         C3
     ⊥
  3. Conclusion : ¬ A est insatisfiable donc A est valide.
Previous Up