INFZ21, logiques du raisonnement valide

Généralités

Dans le chapitre précédent, nous nous sommes intéressés aux propositions comme éléments de base de notre langage. Nous allons, dans ce chapitre, enrichir notre analyse de ces propositions en introduisant une nouvelle structure, celle de prédicat.

Un prédicat formalise une notion appelée en grammaire structure « sujet-prédicat ».

Ainsi, considérons la proposition : « Tout homme est mortel ». La structure « est mortel » est un prédicat et « homme » est le sujet du prédicat.

Le calcul des prédicats permet de s'intéresser à des énoncés relatifs à un ensemble d'objets, comme « Tout homme est mortel » ou à certains éléments de ces ensembles, comme « il existe des hommes mauvais ». Les notions de « quel que soit » et de « il existe » sont fondamentales en calcul des prédicats.

Notons enfin que le calcul des prédicats est aussi appelé logique du premier ordre.

Limitation de la logique des propositions

Prenons le problème suivant :

Tout homme est mortel.
Socrate est un homme.
Donc, Socrate est mortel.

Nous avons déjà traduit des énoncés en logique des propositions. Supposons la traduction suivante :

• Tout homme est mortel est traduit par la proposition a ;
• Socrate est un homme est traduit par la proposition b ;
• Donc, Socrate est mortel est traduit par la proposition c.

Le problème s'écrit alors, en logique des propositions, a ∧ b → c. Cette traduction est correcte. Mais elle est de piètre qualité. En effet, il n'échappera à personne que le raisonnement de départ était valide, mais que sa traduction ne l'est pas (bien qu'elle soit satisfiable).

Légitimité de la logique des prédicats

Définition 2.1 -Prédicat- Un prédicat est une propriété ou relation qui porte sur un ou plusieurs éléments d'un domaine D. C'est une fonction de D dans { T,F}.

Le problème précédent peut être traduit de manière adéquate en logique des prédicats :

Hypothèse 1 : Quelque soit x appartenant au domaine D, si x est un homme, alors x est mortel (∀x(H(x) → M(x))) ;

Hypothèse 2 : Socrate a la propriété d'être un homme (H(Socrate)) ;

Conclusion : Socrate à la propriété d'être mortel (M(Socrate)).

Dans cet exemple, nous avons utilisé deux prédicats (H etM), une constante (Socrate), une variable (x) et le quantificateur universel (∀). Comme nous le verrons plus tard, ce raisonnement, ainsi formalisé en logique des prédicats, sera valide.

Alors que le calcul propositionnel s'appuyait seulement sur des atomes et des connecteurs, le calcul des prédicats s'appuie sur six classes de symboles :

• les variables : on les note en général x,y,z… ;
• les symboles de constantes : ils sont notés a,b,c… ;
• les symboles de fonction : les symboles de fonctions d'arité n > 0 sont notés f,g… ;
• les symboles de prédicats : les prédicats, d'arité positive ou nulle, sont notés p,q… (un prédicat d'arité nulle est équivalent à un atome du calcul propositionnel) ;

• les connecteurs : les connecteurs sont ceux du calcul propositionnel ;
• les quantificateurs : les quantificateurs (ou quanters) sont ∀ et ∃.

Définition 2.2 -Terme- Un terme est défini récursivement par :

• une variable est un terme ;
• un symbole de constante est un terme ;
• si f est un symbole de fonction d'arité n et si t₁,_t2… ,t_n sont des termes, alors f(t₁,t_2… ,t_n) est un terme ;

Tout terme est obtenu par l'application des règles précédentes un nombre fini de fois.

Exemple

• Par exemple, Socrate, x, y, Carré(x), Plus(x,y), Plus(x,Carré(y)), peuvent être des termes. Ici Carré est une fonction d'arité 1 qui renvoie le carré de sont argument et Plus est une fonction d'arité 2 qui renvoie la somme de ses deux arguments.

La définition des formules(3) en calcul des prédicats est très proche de la définition des formules en calcul propositionnel. Nous commençons par définir les atomes :

Définition 2.3 -Atome- Si p est un symbole de prédicat d'arité n et que t₁,t_2… ,t_n sont des termes, alors p(t₁,t_2… ,t_n) est un atome, ou formule atomique.

Définition 2.4 -Formule- Une formule est définie récursivement par :

• toute formule atomique est une formule.
• si A et B sont des formules, alors (A → B), (A ↔ B), (A∧B) et (A∨B) sont des formules ;
• si A est une formule, alors (￢A) est une formule.

• si A est une formule et si x est une variable quelconque alors (∀xA) est une formule, on dit que A est la porté du quantificateur ∀x ;
• si A est une formule et si x est une variable quelconque alors (∃xA) est une formule, on dit que A est la porté du quantificateur ∃x ;

Toute formule est obtenue par l'application des règles précédentes un nombre fini de fois.

Exemple

• Par exemple, ∀x Inf(x,Plus(x,x)) ou encore ∀x (H(x) → M(x)) sont des formules.

Parenthèsage

De la même manière qu'en logique des propositions, nous accepterons les formules dont le parenthèsage est partiellement ou complètement implicite. Pour cela, les connecteurs et les quantificateurs sont traditionnellement classés de la façon suivante (par priorité décroissante des connecteurs et quantificateurs) : ∀, ∃, ￢, ∧, ∨, →, ↔. Dans le cas où deux connecteurs ont même priorité, et en l'absence de parenthèse, l'associativité se fait de gauche à droite. Ainsi, ￢∀x A∨B doit se lire ((￢(∀x A)) ∨ B).

Dans exercices qui suivent, on posera que x, y, z sont des variables, que a, b, c sont des constantes, que f, g, h sont des fonctions et que p, q, r sont des prédicats.

Termes

Dites si les « écritures » suivantes correspondent à des termes :

1. y
2. c
3. x ∨ a
4. f(x)
5. f(x,a)
6. f(a ∧ b)
7. f(y(a),b)
8. g(h(x),f(x,y),c)
9. f(f(f(f(x))))

Formules atomiques

Dites si les « écritures » suivantes correspondent à des formules atomiques :

1. p
2. p(a)
3. p(x)
4. p(a ∨ b)
5. q(x,y,b)
6. r(f(x))
7. q(g(f(a)),b)
8. p(b) ∨ q(a)

Formules

Dites si les « formules » suivantes sont des formules bien formées :

1. a ∨ b
2. p
3. p ∨ r
4. ∀x p(x)
5. ∀x ∨ q(y)
6. ∃x p(x) ∨ q(y)
7. q(x,y,b) → p(x) ∨ p(a) ∧ r
8. ∀b q(x,y,b) → p(x) ∨ p(a) ∧ r
9. ∃y q(x,y,b) → p(x) ∨ p(a) ∧ r
10. ∀z∀x (∃y q(x,y,b) → p(z) ∨ p(a) ∧ r)

Considérons la formule élémentaire ∀xp(x,y) où p est un symbole de prédicat à deux variables. L'occurrence de la variable x dans p(x,y) est placée dans la portée du quantificateur ∀. Une telle occurrence de variable est dite liée.

Définition 2.5 -Variables liées- L'ensemble des variables liées d'une formule A, noté B(A), se définit de façon inductive par :

• si A est un atome, B(A) =  ;
• si A est de la forme (B → C), (B ↔ C), (B ∧ C), (B ∨ C), alors B(A) = B(B) ∪ B(C) ;
• si A est de la forme (￢B) alors B(A) = B(B) ;
• si A est de la forme (∀x B) ou (∃x B), alors B(A) = {x} ∪ B(B).

Définition 2.6 -Variable libre- L'ensemble des variables libres d'une formule A, noté F(A), se définit de façon inductive par :

• si A est un atome, F(A) est égal à l'ensemble des variables apparaissant dans A ;
• si A est de la forme (B → C), (B ↔ C), (B ∧ C), (B ∨ C), alors F(A) = F(B) ∪ F(C) ;
• si A est de la forme (￢B) alors F(A) = F(B) ;
• si A est de la forme (∀x B) ou (∃x B), alors F(A) = F(B) − {x}.

Définition 2.7 -Formule close- Une formule A telle que F(A) = est dite close, fermée ou est encore appelée énoncé.

Dans les formules suivantes, dites si les variables utilisées sont des variables libres ou des variables liées.

• - p(x) ∨ q(y)
• - ∀xp(x) ∨ q(y)
• - ∀xp(x) ∨ q(y,z)
• - ∃z(∀xp(x,z) ∨ q(y,z))
• - ∃z(p(x,z) ∨ ∃yq(y,z))
• - ∀xp(x) ∨ q(x)
• - p(x,y) ∨ p(y,x) ∧ p(x,x) → p(x,y)
• - ∀x∀y(p(x,y) ∨ p(y,x)) ∧ p(x,x) → p(x,y)
• - ∀x∀y(p(x,y) ∨ p(y,x)) ∧ p(x,x) → ∃x∀yp(x,y)
• - ∀x∀y(p(x,y) ∨ p(y,x)) ∧ ∀xp(x,x) → ∃x∀yp(x,y)

Nous allons rencontrer rapidement une difficulté concernant les variables libres. Il est en effet possible d'interpréter une variable libre de deux façons dans une formule.

Si un théorème est démontré à partir d'une hypothèse A(x) où x est pris dans le sens conditionnel, c'est-à-dire où x est contraint à prendre ses valeurs dans un sous-ensemble des valeurs possibles, alors le théorème ne s'applique que pour le même x. En revanche, un théorème démontré à partir de A(x) où x est pris au sens de la généralité est valable pour tout x. Il faut bien prendre garde à ce type de phénomènes, source de sophismes logiques. Il est clair que nombre de problèmes proviennent de l'emploi de variables libres.

Si nous nous contraignions à n'utiliser que des variables liées, l'ambiguïté disparaîtrait sur-le-champ.

On peut toujours ramener une formule non close à une formule close via les deux notions qui suivent.

Définition 2.8 -Clôture universelle- On appelle clôture universelle de la formule A la formule liée ∀x₁ ∀x₂ … ∀x_q où x₁,x_2… ,x_q sont les variables libres apparaissant dans A.

Définition 2.9 -Clôture existentielle- On appelle clôture existentielle de la formule A la formule liée ∃x₁ ∃x₂ … ∃x_q où x₁,x_2… ,x_q sont les variables libres apparaissant dans A.

Comme en calcul propositionnel, nous allons nous efforcer de construire un modèle permettant de dégager une interprétation sémantique de nos formules.

Cependant, en calcul des prédicats, il n'est pas possible d'appliquer une méthode des tables de vérité directement dérivée du calcul propositionnel, en raison des domaines de valeur des variables de chacun des prédicats. En fait, pour une formule atomique p(x_1… ,x_n), nous allons avoir besoin d'une fonction (appelée fonction d'interprétation) chargée de donner un sens au symbole p, et donc de calculer sa valeur de vérité selon la valeur des x_1… ,x_n.

Définition 2.10 -Interprétation- Une interprétation d'une formule F est caractérisée par la donnée d'un ensemble de définition D non vide, appelé le domaine de l'interprétation et d'une fonction d'interprétation I qui associe :

• à chaque symbole de constante de F, un élément de D ;
• à chaque symbole de fonction f d'arité n de F, le graphe d'une fonction de Dⁿ → D définissant f ;
• à chaque symbole de prédicat p d'arité n de F, le graphe d'une fonction de Dⁿ → { T, F} définissant p.

Définition 2.11 -Interprétation des termes- Soit une formule F et I une interprétation de cette formule. On peut étendre l'interprétation I aux termes de F :

• à chaque symbole de constante, on associe sa valeur selon I ;
• à chaque variable, on associe la variable elle-même ;
• à chaque terme f(t_1… ,t_n), on associe le terme f′(t′_1… ,t′_n) où t′_1… ,t′_n sont les interprétations des t_1… ,t_n et f′ est l'interprétation de f.

Définition 2.12 -Interprétation des formules- Elle est définie par :

• si F est un atome p(t_1… ,t_n), I(F) est la fonction p′(t′_1… ,t′_n) où p′ est l'interprétation de p et où chaque t′_i est l'interprétation de t_i ;
• si F est de la forme (￢G), (G → H), (G ↔ H), (G∧H), (G∨H), I(F) est définie par les mêmes lois fonctionnelles que celles définies pour le calcul propositionnel ;
• si F est de la forme ∀xG(x,y_1… ,y_n), pour tout n- uplet (a_1… ,a_n) ∈ Di, I(F)(a_1… ,a_n) = T si pour toute valeur a ∈ D, I(G)(a,a_1… ,a_n) = T, I(F)(a_1… ,a_n) = F sinon ;
• si F est de la forme ∃xG(x,y1… ,yn), pour tout n- uplet (a1… ,an) ∈ Di, I(F)(a_1… ,a_n) = T s'il existe une valeur a ∈ D, I(G)(a,a_1… ,a_n) = T, I(F)(a_1… ,a_n) = F sinon.

Définition 2.13 -Formule valide- Une formule F est dite valide ssi, pour toute interprétation I, on a I(F) = T.

Définition 2.14 -Formule satisfiable- Une formule A sera dite satisfiable, ou sémantiquement consistante, s'il existe une interprétation I telle que I(A) = T. L'interprétation est alors un modèle de A.

Définition 2.15 -Formules invalides- Une formule invalide est fausse dans au moins une interprétation.

Définition 2.16 -Formule insatisfiable- Une formule insatisfiable, ou sémantiquement inconsistante, ou encore antitautologie, est une formule fausse dans toute interprétation.

Définition 2.17 -Formules contingentes- Une formule contingente est vraie dans certaines interprétations et fausse dans d'autres.

Définition 2.18 -Conséquence logique- Soit une formule B et une famille de n formules A_i ; On dit que B est conséquence des Ai si pour toute interprétation I telle que ∀A_i, I(A_i) = T, on a aussi I(B) = T. On note alors A₁,A_2… ,A_n |= B.

Exemple

Soit la formule A = p(y) ∨ ∀x(p(x) → q) où p est défini sur le domaine D = {1,2}. Nous allons essayer de montrer que cette formule n'est pas valide. Pour cela nous allons construire la table de vérité de A. Tout d'abord nous devons considérer les quatre 

interprétations possibles pour p (table 2.1). Nous pouvons ensuite nous lancer dans la construction de la table de vérité de A (table 2.2) en prenant en compte les différentes interprétations possibles de p et de q et les différentes valeurs possibles de y.

Détaillons le calcul des deux premières lignes par exemple. L'interprétation de p utilisé est I₁ et on suppose que l'interprétation de q est T. L'interprétation de p(x) → q est une fonction d'une variable x et est toujours égale à T d'après l'interprétation I₁. On en déduit que la formule close ∀x(p(x) → q) s'interprète par la fonction constante T.

L'interprétation de p(y) est une fonction d'une variable y constante égale à T (d'après I₁). On en déduit que sous I₁, l'interprétation de la formule A est la fonction d'une variable constante et égale à T. D'où les deux premières lignes.

On déduit du contenu de la table que la formule n'est pas valide puisqu'il existe un domaine et une interprétation I (tel que I(p) = I₂(p) et I_q = F) pour lesquels l'interprétation de A n'est pas la fonction constante T. 

Problème des domaines infinis

Vérifier la validité d'une formule dans le cas où les domaines de ses variables sont finis ne pose aucun problème, du moins d'ordre théorique. Il suffit de construire, comme en calcul propositionnel, une table de vérité.

En revanche si un ou plusieurs des domaines sont infinis, le problème est tout autre.

On ne peut plus construire de table de vérité et l'on est forcé de tenir des raisonnements d'ordre général pour démontrer la validité d'une formule (pour démontrer qu'elle n'est pas valide, il suffit bien sûr d'exhiber un cas où elle est fausse).

Cette particularité rend la théorie des modèles du calcul des prédicats beaucoup plus délicate à manipuler que la théorie des modèles du calcul propositionnel.

Traduire les énoncés suivants dans le langage de la logique des prédicats :

1. Tout est relatif.
2. Il n'est point de petites affaires.
3. Si on aime la vie, on craint la mort.
4. Un sot trouve toujours un plus sot qui l'admire.
5. Bien mal acquis ne profite jamais.
6. Chaque âge a ses plaisirs, son esprit et ses mœurs.
7. Il y a un remède à tout, hors la mort.
8. Ce qui vient du diable retourne au diable.

Soit la formule suivante : F = ∀x∃yp(x,y) → ∃yp(yy)

• Dans les interprétations suivantes, dites si la formule F est vraie ou fausse :

1. D = {Hommes} et p(x,y) signifie x est le père de y.
2. D = {Hommes} et p(x,y) signifie y est le père de x.
3. D = R et p : R × R → { T,F} tel que p(x,y) :« x 6= y »
4. D = {} et p : D × D → { T,F} tel que p(,) = T
5. D = {} et p : D × D → { T,F} tel que p(,) = F

• Que peut-on dire, en terme de validité et de consistance, au sujet de la formule F ?
• Que pensez-vous de la formule suivante : ∀xA(x) → ∃yA(y)

Définition 2.19 -Formules équivalentes- Deux formules sont équivalentes quand elles ont même valeur dans toute interprétation (notation : A ≡ B).

Propriété 2.1 -Formules équivalentes- Soit A(x) et B(x) deux formules atomiques bien formées.

• Les formules équivalentes de la logique des propositions demeurent équivalentes en logique des prédicats.

• ∀xA(x) ∧ ∀xB(x) ≡ ∀x(A(x) ∧ B(x))
• ∃xA(x) ∨ ∃xB(x) ≡ ∃x(A(x) ∨ B(x))
• ￢(∀xA(x)) ≡ ∃x￢A(x)
• ￢(∃xA(x)) ≡ ∀x￢A(x)

Remarque :

• ⋆ ∀xA(x) ∨ ∀xB(x) 6≡ ∀x(A(x) ∨ B(x)) ⋆
• ⋆ ∃xA(x) ∧ ∃xB(x) 6≡ ∃x(A(x) ∧ B(x)) ⋆

La principale différence syntaxique entre calcul propositionnel et calcul des prédicats est la présence de quantificateurs à l'intérieur des formules. L'idée à la base de cette section est de construire une formule équivalente dans laquelle les quantificateurs seront rejetés en tête de la formule.

Définition 2.20 -Matrice- Une matrice est une formule du calcul des prédicats ne contenant aucun quantificateur.

Définition 2.21 -Forme prénexe- Une forme prénexe est une formule du calcul des prédicats de la forme Q₁x₁ …Q_nx_nM, où Q désigne ∃ ou ∀ et M est une matrice.

Théorème 2.1 -Forme prénexe équivalente- Toute formule admet une forme prénexe équivalente.

Algorithme de construction - À partir d'une formule quelconque, voici comment construire la forme prénexe associée.

1. Supprimer les connecteurs d'équivalence et d'implication.
2. Renommer certaines variables liées de manière à n'avoir plus de variable quantifiée deux fois.
3. Supprimer les quantificateurs inutiles (dont la variable quantifiée n'apparaît pas dans leur portée)s'il y en a.
4. Transférer toutes les occurrences de la négation devant les atomes en utilisant les règles de réécriture vues pour la logique des propositions et les règles supplémentaires suivantes :
   • ￢∀xA ∃x￢A ;
   • ￢∃xA ∀x￢A.
5. faire passer les quantificateurs en tête en utilisant les règles de réécriture suivantes (et en utilisant l'associativité, la commutativité ou le renommage de variable si nécessaire) :
   • (∀xA ∧ B) ∀x(A ∧ B) si B ne contient pas x ;
   • (∃xA ∧ B) ∃x(A ∧ B) si B ne contient pas x ;
   • (∀xA ∨ B) ∀x(A ∨ B) si B ne contient pas x ;
   • (∃xA ∨ B) ∃x(A ∨ B) si B ne contient pas x.

Exemple

Nous allons construire la forme prénexe équivalente à la formule : ∀xp(x) ∧ ∃yq(y) → ∃y(p(y) ∧ q(y))

1. ￢(∀xp(x) ∧ ∃yq(y)) ∨ ∃y(p(y) ∧ q(y)) par suppression de → ;
2. ￢(∀xp(x) ∧ ∃yq(y)) ∨ ∃z(p(z) ∧ q(z)) par renommage des variables ;
3. (∃x￢p(x) ∨ ∀y￢q(y)) ∨ ∃z(p(z) ∧ q(z)) par transfert de la négation ;
4. ∃x∀y∃z(￢p(x) ∨ ￢q(y) ∨ (p(z) ∧ q(z))) par déplacement des quantificateurs.

Expliquez les deux inégalités de la remarque de la section 2.3.1Formules équivalentes : trouvez des exemples qui l'illustrent.

En utilisant le prédicat mieux_vaut(x,y) (lire x vaut mieux que y) traduire les énoncés suivants dans le langage de la logique des prédicats :

1. Mieux vaut une médaille de bronze qu'aucune médaille ;
2. Rien n'est mieux qu'une médaille d'or ;
3. Une médaille d'argent est préférable à une médaille de bronze.

Traduire les raisonnements suivants dans le langage de la logique des prédicats :

1. Tous les politiciens parlent à la radio.
   Parmi les gens qui parlent à la radio, certains sont des menteurs.
   Donc, quelques politiciens sont menteurs.
2. Seuls les oiseaux ont des plumes.
   Aucun mammifère n'est un oiseau.
   Donc, tout mammifère est dépourvu de plumes.
3. Toutes les médailles d'or sont remportées par quelqu'un.
   Tous ceux qui ont gagné des médailles d'or sont des champions.
   Les gens fatigués ne gagnent pas de médailles d'or.
   Il existe des médailles d'or.
   Il y a donc des champions qui ne sont pas fatigués.

Mettre sous forme prénexe les formules suivantes :

1. ∀xA(x) → ∃yA(y)
2. ￢∀x(A(x) ∨ B(x)) → ∃xA(x)
3. ∀x∃yP(x,y) → ∃yP(yy)
4. ∀x(P(x) ∧ Q(x) → ∃y(S(xy) ∧ ∀zR(zyx)))