Chapitre 2  Donner du sens aux formules

Définition 1 (Interprétation)   Une interprétation I de la signature (F,R) est donnée par

• un ensemble D non vide appelé domaine de l’interprétation;
• pour chaque symbole de fonction f∈F_n d’arité n, une fonction f_I n-aire sur D (c’est-à-dire que f_I∈ Dⁿ→ D, pour chaque x₁,…,x_n∈ D, on a f_I(x₁,…,x_n)∈D);
• pour chaque symbole de relation R∈R_n d’arité n, une relation n-aire R_I sur D (c’est-à-dire que R_I ⊆ Dⁿ est un ensemble de n-uplets (v₁,…,v_n) de valeurs dansD qui correspondent à tous les cas pour lesquels on considère, dans cette interprétation, que la relation R est vraie).

Exemple 1   Par exemple, les langages de programmation ont une notion primitive d’entiers relatifs mais pas de nombres rationnels. On peut se donner une signature pour manipuler des rationnels qui contiendra des constantes 0, 1 et -1, une opération binaire de construction frac, des opérations binaires + et * et un symbole de prédicat binaire pour l’égalité.

On peut proposer une interprétation de cette signature. Il faut décider comment on va représenter un rationnel, on choisit de le faire en prenant un couple (p,q)∈ℤ×ℕ∖{0} formé d’un entier relatif en numérateur et d’un entier naturel non nul en dénominateur. Le domaine de l’interprétation est donc D =^def  ℤ×ℕ∖{0}. D’autres choix sont possibles comme d’imposer que la fraction soit réduite (pas de diviseur commun du dénominateur et du numérateur), ou encore avoir un entier relatif en dénominateur.

On pourra définir alors l’interprétation de chacun des symboles de notre signature :

0ℚ   def =    (0,1) 1ℚ   def =    (1,1) -1ℚ   def =    (−1,1)

fracℚ((p1,q1),(p2,q2))   def =    (p1q2,q1p2) si   p2>0 fracℚ((p1,q1),(p2,q2))   def =    (0,1) si   p2=0 fracℚ((p1,q1),(p2,q2))   def =    (−p1q2,−q1p2) si   p2<0 +ℚ((p1,q1),(p2,q2))   def =    (p1q2+p2q1,q1q2) *ℚ((p1,q1),(p2,q2))   def =    (p1p2,q1q2) =ℚ((p1,q1),(p2,q2))   def =     (p1q2=q1p2)

Définition 2 (Environnement)   Soit I une interprétation de la signature (F,R) dont le domaine est D, un environnement est une application ρ qui associe une valeur du domaine D à chaque variable de X (c’est-à-dire ρ∈X→D).
Soit ρ un environnement, si x∈ X et d∈ D, on note ρ+{x↦d} l’environnement qui vaut d pour la variable x et ρ(y) pour toutes les variables y≠x.

Définition 3 (Valeur d’un terme et d’une formule dans une interprétation)   Soit ρ un environnement, ρ∈X→D.

• on définit la valeur val_I(ρ,t) d’un terme t∈ T(F,X) dans l’interprétation I et l’environnement ρ, c’est un élément du domaine D :

  valI(ρ,x)=ρ(x)      valI(ρ,f(t1,…,tn))=fI(valI(ρ,t1),…,valI(ρ,tn))

• on définit la valeur val_I(ρ,P) d’une formule P dans l’interprétation I et l’environnement ρ, c’est une valeur de vérité dans {V,F} :

  valI(ρ,⊥) = F    valI(ρ,⊤) = V    valI(ρ,R(t1,…,tn)) = si RI(valI(ρ,t1),…,valI(ρ,tn)) alors V sinon F  valI(ρ,¬ A) = si valI(ρ,A)=V alors F sinon V  valI(ρ, A∧ B) = si valI(ρ,A)=V alors valI(ρ,B) sinon F  valI(ρ, A∨ B) = si valI(ρ,A)=V alors V sinon valI(ρ,B)  valI(ρ, A⇒ B) = si valI(ρ,A)=V alors valI(ρ,B) sinon V  valI(ρ, ∀ x, A) = si pour tout d∈D, valI(ρ+{x↦d},A)=V alors V sinon F  valI(ρ, ∃ x, A) = si il existe d∈D tel que  valI(ρ+{x↦d},A)=V alors V sinon F

Proposition 1   Soit I une interprétation I et ρ un environnement.

• I,ρ⊭⊥
• I,ρ⊨⊤
• I,ρ⊨ R(t₁,…,t_n) si et seulement si (val_I(ρ,t₁),…,val_I(ρ,t_n)) appartient à l’interprétation de R
• I,ρ⊨¬ A si et seulement si I,ρ⊭A
• I,ρ⊨ A∧ B si et seulement si I,ρ⊨ A et I,ρ⊨ B
• I,ρ⊨ A∨ B si et seulement si I,ρ⊨ A ou I,ρ⊨ B
• I,ρ⊨ A⇒ B si et seulement si I,ρ⊭A ou I,ρ⊨ B
• I,ρ⊨ ∀ x, A si et seulement si pour tout d∈D, on a I,ρ+{x↦d}⊨ A
• I,ρ⊨ ∃ x, A si et seulement si il existe d∈D tel que I,ρ+{x↦d}⊨ A

Exemple 2   Les bases de données traitent généralement de problèmes sur des ensembles finis. On peut avoir un domaine qui soit un ensemble de personnes et vouloir représenter les relations de parenté (filiation et liens entre frères et soeurs).

On modélise une telle base de données en logique du premier ordre. On suppose que la signature est juste composée d’un ensemble de constantes pour représenter les individus, par exemple Alice, Bob, Charles, Denis, Eric, Fanny, Georges et Hélène et de deux symboles de relation binaire parent et fratrie ainsi qu’un symbole d’égalité binaire. La relation parent(x,y) exprime que x est le père ou la mère de y et fratrie(x,y) exprime que x et y sont dans la même fratrie.

Le modèle peut utiliser comme domaine l’ensemble des constantes

{Alice,Bob,Charles,Denis,Eric,Fanny,Georges,Hélène}

ou bien une autre représentation comme des entiers par exemple, ou des caractères.

On va prendre ici D =^def {A,B,C,D,E,F,G,H}. On interprète chaque constante par un élément de D. Il serait parfaitement légitime de choisir une interprétation qui associe le même élément du domaine à deux constantes différentes du langage (par exemple si un individu est connu sous deux identités différentes). Ici on choisit de représenter chaque constante du langage par un élément différent du domaine.

AliceI=A    BobI=B    CharlesI=C     DenisI=D EricI=E     FannyI=F    GeorgesI=G     HélèneI=H

On a ensuite le choix sur l’interprétation des relations, par exemple :

parentI ={(A,B),(G,B),(B,C),(B,H)} fratrieI ={(C,H),(H,C)} =I ={(A,A),(B,B),(C,C),(D,D),(E,E),(F,F),(G,G),(H,H)}

On s’attend à ce que cette interprétation satisfasse les propriétés suivantes :

• la relation de fratrie est symétrique;
• deux personnes sont dans la même fratrie si et seulement si ils ont un parent commun;
• une personne ne peut avoir plus de deux parents.

Exercice 1   Soient les formules suivantes sans variable libre. Sont-elles vraies si on les interprète dans ℕ, ℤ, ℚ avec les conventions usuelles pour l’interprétation des opérations et des relations.

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

On constate que des propriétés vraie ou fausses dans une interprétation ne le sont pas forcément dans une autre, même si les interprétations se correspondent sur les formules atomiques. Cela vient du fait que les quantifications ne vont pas faire référence aux mes ensembles sous-jacent. En mathématiques “usuelles” (qui s’appuient implicitement sur la théorie des ensembles) on distinguerait les formules en relativisant les quantificateurs. Par exemple ∀ x∈ℕ, ∃ y∈ℕ, y < x (qui est faux) versus ∀ x∈ℤ, ∃ y∈ℤ, y < x qui est vrai.

Proposition 2   La valeur d’un terme ne dépend que de la valeur de l’environnement sur les variables de ce terme et de l’interprétation des symboles de fonction et des constantes qui apparaissent dans ce terme.
La valeur de vérité d’une formule ne dépend que de la valeur de l’environnement sur les variables libres de cette formule et de l’interprétation des symboles de fonction, constantes et relations qui apparaissent dans la formule.

Preuve: La preuve se fait sans difficulté par récurrence sur la structure du terme puis de la formule. □

Proposition 3 (Vérité et substitution)   Soit une formule P qui contient une variable libre x et soit t un terme. On suppose que la formule substituée P[x← t] est définie (pas de capture). Soit ρ un environnement. Interpréter la formule dans laquelle on remplace x par t revient à interpréter la formule de base en complétant l’environnement avec pour valeur associée à la variable x, l’interprétation du terme t.

valI(ρ,P  [x← t]) = valI(ρ+{x↦valI(ρ,t)},P)

Preuve: La preuve se fait en montrant d’abord un résultat analogue pour les termes.

Soit u un terme, on a :

valI(ρ,u  [x← t]) = valI(ρ+{x↦valI(ρ,t)},u)

Ce premier résultat se montre par simple récurrence sur la structure du terme u, de la manière suivante :

• Si u est la variable x alors u [x← t]=t et la formule à montrer se réécrit en

  valI(ρ,t) = valI(ρ+{x↦valI(ρ,t)},x)=(ρ+{x↦valI(ρ,t)})(x)

  qui est vrai par définition de ρ+{x↦val_I(ρ,t)}.
• Si u est une variable y différente de x, alors y [x← t]=y et la formule à montrer se réécrit en

  valI(ρ,y) = valI(ρ+{x↦valI(ρ,t)},y)

  qui est vrai par définition de ρ+{x↦val_I(ρ,t)} (les deux expresssions sont égales à ρ(y)).
• Si u est une constante c alors c [x← t]=c et la formule à montrer se réécrit en

  valI(ρ,c) = valI(ρ+{x↦valI(ρ,t)},c)

  qui est vrai par définition de val_I (les deux expresssions sont égales à c).
• Si u est une expression f(u₁,…,u_n) alors f(u₁,…,u_n) [x← t]=f(u₁ [x← t],…,u_n [x← t]) et la formule à montrer se réécrit en

  valI(ρ,f(u1 [x← t],…,un [x← t])) = valI(ρ+{x↦valI(ρ,t)},f(u1,…,un))

  On a alors

  valI(ρ,f(u1 [x← t],…,un [x← t]))   =fI(valI(ρ,u1 [x← t]),…,valI(ρ,un [x← t])) def de valI =fI(valI(ρ+{x↦valI(ρ,t)},u1),…,valI(ρ+{x↦valI(ρ,t)},un)) hyp. de récurrence =valI(ρ+{x↦valI(ρ,t)},f(u1,…,un)) def de valI

On montre ensuite par récurrence sur la structure de la formule P que pour n’importe quel environnement ρ, on a

valI(ρ,P  [x← t]) = valI(ρ+{x↦valI(ρ,t)},P)

On ne montre ici que le cas des formules atomiques R(u₁,…,u_n) et le cas d’une formule quantifiée ∀ x, A.

• Le résultat établi pour les termes permet de montrer le cas des formules atomiques car

  valI(ρ,R(u1,…,un)[x← t])  = valI(ρ,R(u1 [x← t],…,un [x← t])) def de substitution = RI(valI(ρ,u1 [x← t]),…,valI(ρ,un [x← t])) def de valI = RI(valI(ρ+{x↦valI(ρ,t)},u1),…,valI(ρ+{x↦valI(ρ,t)},un)) prop. des termes = valI(ρ+{x↦valI(ρ,t)},R(u1,…,un)) def de valI

• Supposons que P est de la forme ∀ z,A et on suppose que z≠x (sinon la substitution est constante et le résultat immédiat) et que la substitution est bien définie à savoir la variable z n’est pas libre dans t. On a alors (∀ z,A)[x← t]=∀ z,(A[x← t]).

  Pour calculer la valeur d’une formule ∀ z,B dans un environnement ρ′ quelconque, on fixe un élement d∈ D et on regarde la valeur de la formule B dans l’environnement ρ′+{z↦d}.

  On se donne donc un environnement ρ et pour calculer val_I(ρ,∀ z,(A[x← t])) on se donne d∈ D et on calcule

  valI(ρ+{z↦d},A[x← t])     =  valI((ρ+{z↦d})+{x↦valI(ρ,t)},A) hypothèse de récurrence    =  valI((ρ+{x↦valI(ρ,t)})+{z↦d},A) car x≠z

  Donc pour tout d, val_I(ρ+{z↦d},A[x← t]) est vrai si et seulement si val_I((ρ+{x↦val_I(ρ,t)})+{z↦d},A) est vrai. On en déduit que val_I(ρ,∀ z,(A[x← t])) est vrai si et seulement si val_I(ρ+{x↦val_I(ρ,t)},∀ z,A) est vrai, qui est le résultat souhaité.

  Le même raisonnement permet de conclure dans le cas d’un quantificateur existentiel. La seule subtilité dans la preuve est que l’hypothèse de récurrence est appliquée à l’environnement ρ+{z↦d} au lieu de ρ et donc que la propriété que l’on cherche à montrer par récurrence sur la formule P doit bien inclure cette possibilité de faire varier l’environnement.

□

Définition 1 (Validité, satisfiabilité, modèle)   Soit A, une formule du calcul des prédicats sur une signature (F,R).

• La formule est dite valide (on dit aussi que c’est une tautologie) si sa valeur de vérité est vraie pour toute interprétation de la signature et tout environnement.
• La formule est dite satisfiable si sa valeur de vérité est vraie pour au moins une interprétation de la signature et un environnement. Une interprétation et un environnement qui rendent vraie la formule forment un modèle de la formule.
• La formule est dite insatisfiable (on dit aussi contradictoire) si sa valeur de vérité est fausse pour toute interprétation de la signature et tout environnement.

On étend ces notions à un ensemble E fini ou infini de formules:

• L’ensemble E est valide si pour toute interprétation I, tout environnement ρ et toute formule P∈E on a val_I(ρ,P)=V (toutes les formules sont vraies dans toutes les interprétations).
• L’ensemble E est satisfiable s’il existe une interprétation I et un environnement ρ tels que pour toute formule P∈E on a val_I(ρ,P)=V (il existe une interprétation qui rend vraies toutes les formules de E).
• L’ensemble E est insatisfiable si pour toute interprétation I et tout environnement ρ, il existe une formule P∈E telle que val_I(ρ,P)=F (il n’existe pas d’interprétation qui rende vraies toutes les formules ou de manière équivalente, toute interprétation rend fausse au moins une formule de E).

Proposition 1 (Lien entre validité et satisfiabilité)   La formule A est valide si et seulement si ¬ A est insatisfiable.

Preuve: La formule A est valide si et seulement si la formule A est vraie dans toute interprétation de la signature et tout environnement. Ceci est équivalent à dire que la formule ¬ A est fausse dans toute interprétation de la signature et tout environnement, ce qui est la définition de insatisfiable. □

Exercice 2   Dire si les formules suivantes sont valides, satisfiables, insatisfiables :

• (∃ x,¬ P(x)) ⇒ ¬ ∀ x,P(x)
• (∃ x,¬ P(x)) ⇒ ∃ x,¬ Q(x)
• (∃ x,¬ P(x)) ∧ ∀ x,P(x)

Proposition 2   

• Une formule A avec un variable libre x est valide si et seulement si la formule ∀ x, A est valide.
• Une formule A avec un variable libre x est satisfiable si et seulement si la formule ∃ x, A est satisfiable.
• Une formule A avec un variable libre x est insatisfiable si et seulement si la formule ∃ x, A est insatisfiable.

Définition 2 (Remplacement d’une variable propositionnelle par une formule, P[X← Q])   Soit P et Q des formules et X une variable propositionnelle, le remplacement de X par Q dans P est une formule notée P[X← Q] qui est définie de manière récursive sur la structure de P.

• Si P est une formule atomique alors si P est la variable propositionnelle X alors P[X← Q]=Q sinon P[X← Q]=P
• Si P est de la forme ¬ A alors P[X← Q]=¬(A[X← Q])
• Si P est de la forme A∘ B avec ∘ l’une des connecteurs propositionnels alors P[X← Q]=(A[X← Q])∘ (B[X← Q])
• Si P est de la forme ∀ x,A (resp. ∃ x,A) avec la variable x qui n’est pas libre dans la formule Q, alors P[X← Q]=∀ x, (A[X← Q]) (resp. P[X← Q]=∃ x, (A[X← Q]))

Proposition 3   Soit P et Q des formules et X une variable propositionnelle, si P est une formule valide (resp. insatisfiable) alors il en est de même de la formule obtenue en remplaçant X par Q dans P.

Preuve: Nous allons faire la preuve dans le cas de la validité. Le résultat découle du fait que dans une interprétation I et un environnement ρ quelconques, la valeur de P[X← Q] est égale à la valeur de P dans un environnement dans lequel la variable X a pour interprétation la valeur de Q. Ce résultat s’obtient facilement par récurrence sur la structure de P.

Maintenant si une formule est valide, elle est vraie tout le temps donc en particulier si on fixe une valeur pour une de ses variables (ici X). □

Exemple 1   Soit une signature avec une constante c et un symbole de prédicat unaire Q et un symbole d’égalité binaire.

Soit A la formule P(c)⇒∃ x,P(x) alors A[P(z)← z=z] est défini comme la formule :

(c=c)⇒∃ x,x=x

Définition 3 (Remplacement d’un symbole de prédicat par une formule, P[R(x₁,…,x_n)← Q])   Soit P et Q des formules, R un symbole de prédicat d’arité n et x₁,…,x_n, n variables d’objet. Le remplacement de R par Q paramétré par x₁,…,x_n dans P est une formule notée P[R(x₁,…,x_n)← Q] qui est définie de manière récursive sur la structure de P.

• Si P est une formule atomique alors si P est de la forme R(t₁,…,t_n) on a P[R(x₁,…,x_n)← Q]=Q[x₁← t₁,…,x_n← t_n] sinon P[R(x₁,…,x_n)← Q]=P
• Si P est de la forme ¬ A alors P[R(x₁,…,x_n)← Q]=¬(A[R(x₁,…,x_n)← Q])
• Si P est de la forme A∘ B avec ∘ l’une des connecteurs propositionnels alors P[R(x₁,…,x_n)← Q]=(A[R(x₁,…,x_n)← Q])∘ (B[R(x₁,…,x_n)← Q])
• Si P est de la forme ∀ x,A (resp. ∃ x,A) avec la variable x qui n’est pas libre dans la formule Q, alors P[R(x₁,…,x_n)← Q]=∀ x, (A[R(x₁,…,x_n)← Q]) (resp. P[R(x₁,…,x_n)← Q]=∃ x, (A[R(x₁,…,x_n)← Q]))

Proposition 4   Soit une formule P qui est construite sur une signature qui comporte un symbole de relation n-aire R. Soit une formule Q et n variables x₁,…,x_n.

Si P est valide (resp. insatisfiable) alors il en est de même de la formule P[R(x₁,…,x_n)← Q].

Preuve: On se donne une interprétation quelconque I pour les symboles de la formule P[R(x₁,…,x_n)← Q] et un environnement ρ pour les variables libres. On doit montrer que dans cette interprétation la formule P[R(x₁,…,x_n)← P] est vraie (resp. fausse).

Tous les symboles et les variables qui apparaissent dans P apparaissent aussi dans P[R(x₁,…,x_n)← P] à l’exception peut-être de R. On construit une interprétation I′ qui est définie comme I pour tous les symboles sauf dans le cas de R pour lequel on pose R_I′(d₁,…,d_n) est vrai si et seulement si val_I(ρ+{x₁↦ d₁,…,x_n↦ d_n},Q) est vrai.

Pour n’importe quel environnement ρ, on a

valI′(ρ,P)=valI(ρ,P[R(x1,…,xn)← Q])

(cette propriété se montre par récurrence sur la structure de la formule P).

Si P est valide, on a val_I′(ρ,P) est vrai. On en déduit que val_I(ρ,P[R(x₁,…,x_n)← Q]) est vrai et comme cela vaut pour toutes les interprétations I, on en déduit la validité de la formule P[R(x₁,…,x_n)← Q]. □

Définition 1 (Conséquence logique, équivalence)   Si E est un ensemble de formules et A une formule, on dit que A est conséquence logique de E et on note E⊨ A si toute interprétation I et environnement ρ qui rendent vraies les formules de E rendent aussi vraie la formule A. C’est-à-dire que si I,ρ⊨ B pour toutes les formules B∈E (noté I,ρ⊨ E) alors I,ρ⊨ A
On dit que A et B sont des formules équivalentes et on écrit A≡ B si A⊨ B et B ⊨ A. C’est-à-dire que I,ρ⊨ A si et seulement si I,ρ⊨ B.

Proposition 1   Si E est un ensemble de formules et A une formule, on a E⊨ A si et seulement si pour toute interprétation

Proposition 2   Pour toute formule P et ensemble de formules E, on a les propriétés suivantes:

• Pour toutes formules A₁,…,A_n, A₁,…,A_n ⊨ P si et seulement si A₁∧… ∧ A_n ⇒ P est valide
• si E est un ensemble insatisfiable de formules alors pour toute formule P, on a E ⊨ P
• E est un ensemble insatisfiable de formules si et seulement si E ⊨ ⊥
• E ⊨ P si et seulement si l’ensemble de formules E∪ {¬ P} est insatisfiable.
• E,P ⊨ Q si et seulement si E⊨ P ⇒ Q

Preuve: On traite ici le cas de formules closes pour ne pas avoir à introduire d’environnement mais la preuve est identique s’il y a des variables en introduisant l’environnement ρ en plus de l’interprétation I.

• A₁,…,A_n ⊨ P si et seulement si toute interprétation qui rend vraies toutes les formules A₁,…,A_n rend vraie P. On considère une interprétation I quelconque. Si I rend vraies toutes les formules A₁,…,A_n alors elle rend vraie P et donc aussi A₁∧… ∧ A_n ⇒ P. Si I rend faux une des formules A₁,…,A_n alors elle rend faux A₁∧… ∧ A_n et donc elle rend vraie A₁∧… ∧ A_n ⇒ P. On a donc montré que quelle que soit l’interprétation, la formule A₁∧… ∧ A_n ⇒ P était vraie et donc cette formule est valide.
  Réciproquement si A₁∧… ∧ A_n ⇒ P est valide et si I est une interprétation qui rend vraies toutes les formules A₁,…,A_n, alors I rend vraie P.
• Si E est un ensemble insatisfiable de formule, alors l’ensemble des interprétations qui rendent vraie les formules de E est vide. Et donc n’importe quelle interprétation dans cet ensemble rend vraie la formule P. Par définition, E ⊨ P est alors vérifié.
• Etant donnée la question précédente, il suffit de montrer que si E ⊨ ⊥ alors E est insatisfiable. Supposons que E soit satisfiable, il y aurait alors une interprétation qui rend vraie les formules de E, mais alors cette interprétation devrait rendre vrai la formule ⊥ ce qui est contraire à la éfinition de ⊥.
• Supposons que E ⊨ P et montrons que toute interprétation I rend fausse l’une des formules de E∪{¬ P}. Soit I rend fausse l’une des formules de E et donc a fortiori une des formules de E∪{¬ P}, soit I rend vraies toutes les formules de E et donc aussi P et donc I rend fausse la formule ¬ P.
  Réciproquement si E∪{¬ P} est insatisfiable, soit I une interprétation qui rend vraies toutes les formules de E, elle rend fausse la formule ¬ P (sinon E∪{¬ P} serait satisfiable) et donc elle rend vraie la formule P et donc E ⊨ P.
• Soit une interprétation I.
  • Si E,P ⊨ Q et I⊨ E,
    • si I⊨ P alors I⊨ E,P donc I⊨ Q et donc I⊨ P⇒ Q d’où le résultat
    • si I⊭P alors P est faux dans l’interprétation I donc P⇒ Q est vrai et donc I⊨ P⇒ Q
    on en conclut que E ⊨ P ⇒ Q
  • En sens inverse, si E ⊨ P ⇒ Q et I⊨ E,P. On a I⊨ E donc I⊨ P⇒ Q et I⊨ P. On en déduit que I⊨ Q et donc E,P ⊨ Q.

□

Proposition 3   Soit P une formule, E un ensemble de formules tel que E⊨ P.

• si x est une variable d’objet et t un terme alors E[x← t]⊨ P[x← t]
• siR un symbole de prédicat n-aire, x₁,…,x_n n variables et Q une formule alors E[R(x₁,…,x_n)← Q]⊨ P[R(x₁,…,x_n)← Q]

Preuve: La preuve suit les lignes des preuves de préservation de la validité par substitution en utilisant le fait que pour n’importe quelle formule P, interprétation I et environnement ρ, on a (proposition 3

valI(ρ,P  [x← t]) = valI(ρ+{x↦valI(ρ,t)},P)

et (d’après la preuve de la proposition 3)

valI(ρ,P[R(x1,…,xn)← Q])=valI′(ρ,P)

avec I′ définie comme I pour tous les symboles sauf R pour lequel on pose R_I′(d₁,…,d_n) est vrai si et seulement si val_I(ρ+{x₁↦ d₁,…,x_n↦ d_n},Q) est vrai. □

Proposition 4   Soit E un ensemble de formules, A₁,A₂,B₁ et B₂ des formules. On suppose que E,A₁⊨ B₁ et E,A₂⊨ B₂, on a alors

• E,¬ B₁⊨ ¬ A₁
• E,A₁∧ A₂⊨ B₁∧ B₂
• E,A₁∨ A₂⊨ B₁∨ B₂
• E,B₁⇒ A₂⊨ A₁⇒ B₂
• si de plus la variable x n’apparait pas libre dans E, alors E,∀ x,A₁⊨ ∀ x,B₁ et E,∃ x,A₁⊨ ∃ x,B₁

Preuve: La preuve se fait très facilement en utilisant la définition de ⊨. On fera attention à la négation et l’implication qui “changent le sens” de la relation. Au niveau des quanticateurs, la condition que la variable x n’est pas libre dans l’ensemble E est essentielle, comme le montre l’exemple suivant avec deux prédicats P(x) et Q(x). On a P(x), P(x)⇒ Q(x)⊨ Q(x) qui est trivialement vrai. Si maintenant on pouvait appliquer la règle avec E =^def {P(x)}, A₁ =^def  P(x)⇒ Q(x) et B₁ =^def  Q(x), on en déduirait P(x), (∀ x,P(x)⇒ Q(x))⊨ ∀ x,Q(x). Il suffit de prendre un modèle avec deux éléments {0,1} avec P(0) et Q(0) vrai, P(1) et Q(1) faux. On a bien (pour x↦ 0), P(x) et ∀ x,P(x)⇒ Q(x) qui sont vrais mais ∀ x,Q(x) est faux. □

Exercice 3   Donner des formules équivalentes pour ⊥⇒ P, ⊤⇒ P, P⇒ ⊤

Définition 2 (Forme normale de négation)   Une formule est dite en forme normale de négation si elle ne contient que les connecteurs logiques ∧,∨, les quantificateurs ∀,∃ et que le symbole de négation n’apparait que devant une formule atomique R(t₁,…,t_n).

Proposition 5   On se place dans un langage avec deux symboles de prédicat unaire H et G et un symbole de prédicat binaire R. Les équivalences suivantes sont vérifiées :

• On peut permuter deux quantificateurs de même nature :
  ∀ x, ∀ y,R(x,y)≡ ∀ y, ∀ x,R(x,y)    ∃ x, ∃ y,R(x,y)≡ ∃ y, ∃ x,R(x,y)
• Du fait des liens entre quantification universelle et conjonction d’une part, quantification existentielle et disjonction d’autre part, on peut réarranger l’enchainement de ces connecteurs :
  ∀ x, (G(x) ∧ H(x)) ≡ (∀ x, G(x)) ∧ (∀ x, H(x))      ∃ x, (G(x) ∨ H(x)) ≡ (∃ x, G(x)) ∨ (∃ x, H(x))
• On peut éliminer un quantificateur sur la variable x si x n’est pas libre dans la formule. Si x∉VL(A) alors ∀ x, A ≡ ∃ x,A≡ A.
• On peut “sortir” d’un quantificateur sur la variable x, une sous-formule dans laquelle la variable n’est pas libre. Si x∉VL(A) alors ∀ x,(A ∧ G(x)) ≡ A ∧ ∀ x,G(x)     ∀ x,(A ∨ G(x)) ≡ A ∨ ∀ x,G(x)     ∃ x,(A ∧ G(x)) ≡ A ∧ ∃ x,G(x)     ∃ x,(A ∨ G(x)) ≡ A ∨ ∃ x,G(x)

Exercice 4   En utilisant les équivalences précédentes, montrer les équivalences suivantes :

• si x∉VL(A) alors ∀ x,(A ⇒ H(x)) ≡ A ⇒ ∀ x, H(x)     ∃ x,(A ⇒ H(x)) ≡ A ⇒ ∃ x, H(x)
• si x∉VL(A) alors ∀ x,(G(x) ⇒ A) ≡ (∃ x, G(x)) ⇒ A     ∃ x,(G(x) ⇒ A) ≡ (∀ x, G(x)) ⇒ A

Une application de la dernière équivalence est le principe dit du “buveur” : dans un bar quelconque, il existe une personne telle que si cette personne boit alors tout le monde boit. Il suffit de prendre pour G(x) la formule x boit et pour A la formule ∀ x, x boit

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

• ∀ x, ∃ y,R(x,y) ≢∃ y,∀ x, R(x,y)
• ∀ x, (G(x)∨ H(x)) ≢(∀ x,G(x)) ∨ (∀ x,H(x))
• ∃ x, (G(x)∧ H(x)) ≢(∃ x,G(x)) ∧ (∃ x,H(x))