Précédent / Suivant / Table des matières

II. Eléments de logique du 1^er ordre

II-1. Prédicats

L’approche de la logique du 1^er ordre est moins “ naïve ” que celle des propositions. Cependant l’étudiant intéressé par une exposition axiomatique et approfondie dispose d’excellents ouvrages dont certains figurent dans la bibliographie proposée dans le cours « Mathématique pour l’informatique ».

 

Définitions 1 :
Une proposition logique peut être considérée comme un tout (atome) ou comme l'application d'une relation (d'une propriété) à un objet. Dans ce cas on dit que la proposition est analysée sous la forme prédicat/objet. Si p désigne un prédicat et x désigne un objet alors p(x) signifie l'application de la propriété p à l'objet x.
Les termes sont soit des constantes, qui désignent un objet particulier, soit des variables qui désignent un objet indéterminé, soit aussi des combinaisons de variables et de constantes à l'aide de symboles de fonctions

·       1 objet (1 argument) : on dit que le prédicat est unaire ou d'arité 1

·       2 objets (2 arguments) : on dit que le prédicat est binaire ou d'arité 2

·       3 objets (3 arguments) : on dit que le prédicat est ternaire ou d'arité 3

·       n objets (n arguments) : on dit que le prédicat est n-aire ou d'arité n

 

Remarque 1:
Une proposition atomique (non analysée) peut être considérée comme un prédicat d'arité 0.

 

Remarque 2:
Les variables d'un prédicat prennent leurs valeurs dans un univers U (non vide!) appelé univers du discours (ou plus simplement univers).
En assignant des valeurs prises dans U aux n variables d'un prédicat n-aire on lui associe l'une des deux valeurs de vérité Vrai ou Faux.
Si le prédicat p(x₁, x₂, …, x_n) est vrai pour tous les choix de valeurs v₁, v₂, …, v_n dans U que l'on assigne aux variables x₁, x₂, …, x_n on dit que p est valide dans l'univers U. S'il est vrai pour certains choix de valeurs v₁, v₂, …, v_n dans U on dit qu'il est satisfaisable. Si p n'est pas satisfaisable dans U on dit qu'il est non satisfaisable.

II-1. Quantificateurs

Certains prédicats concernent tous les objets (désignés par la variable x). Ceci se traduit par une quantification universelle de la variable x.

(x) p(x)   qui se lit “ quelque soit x,  p(x) ”. Le symbole  est appelé  quantificateur universel et se lit “ quelque soit ” ou “ pour tout ”. ou encore “ tous les ” , “ chaque ” , “ quelconque ” , “ aucun ” , “ nul ” etc.

Certains prédicats concernent au moins un objet (désignés par la variable x). Ceci se traduit par une quantification existentielle de la variable x.

(x) p(x)   qui se lit “ il existe au moins un x, p(x) ”. Le symbole  est appelé  quantificateur existentiel et se lit “ il existe au moins un” ou “ pour au moins un ”. ou encore “ parfois ” , “ plusieurs ” , “ d'aucun ” , “ presque tous ” , “ souvent ” etc.

 

Définitions 2 :
Toute variable quantifiée (par  ou ) est dite liée par le quantificateur. Dans la mesure où le nom (symbole) employé pour désigner une telle variable importe peu on dit que la variable est muette. Inversement une variable qui n'est pas liée par un quantificateur est dite libre.

 

Définitions 3 :
Une expression bien formée (ebf) ou plus simplement une expression (ou encore une formule) de la logique du 1^er ordre est définie (récursivement) par :
(1) - tout symbole d'atome est une ebf
(2) - Si p est un symbole de prédicat n-aire et si x₁, x₂, …, x_n sont des symboles d'objets alors
p(x₁, x₂, …, x_n) est une ebf.
(3) - Si A et B sont des ebf alors  (A) et (A → B) sont des ebf.
(4) - Si A est une ebf alors  (x) A  et  (x) A  sont des ebf.
(5) - Rien n'est une ebf hormis par (1), (2), (3) et (4).

 

II-1. Quantificateurs et connecteurs logiques

 

Axiomes  :

(A₁) - (x)(p → q)  (p → (x)q)  à condition que x ne figure pas dans p comme variable libre

(A₂) - (x) p(x)  p(y) où y est un symbole de variable ou de constante. A condition que (y) ne figure pas dans p.

 

Définitions 4 :
Interpréter une formule de la logique du 1^er degré dans un univers U c'est lui associer une valeur de vérité en assignant aux variables les valeurs prises dans U et en évaluant les valeurs de vérité des prédicats de la formule.

 

 

Propriétés 1 :

 (x) p(x)  p(u)  où u est un élément arbitraire de l'univers du discours

 p(u)  (x)p(x) où u est un élément arbitraire de l'univers du discours

 (x)p(x)  (x)p(x)

 (x)p(x)  (x)p(x)

 ((x)p(x)q)  (x)(p(x)q)

 ((x)p(x)q)  (x)(p(x)q)

 (x)p(x)(x)q(x)  (x)(p(x)q(x))

 (x)p(x)(x)q(x)  (x)(p(x)q(x))

 ((x)p(x)q)  (x)(p(x)q)

 ((x)p(x)q)  (x)(p(x)q)

 (x)(p(x)q(x))  (x)p(x)(x)q(x)

 (x)p(x)(x)q(x)   (x)(p(x)q(x))

Haut de page