M. Mahdi JEMMALI 1 Université de Monastir Niveau : Deuxième année LF, LA info I

M. Mahdi JEMMALI 1 Université de Monastir Niveau : Deuxième année LF, LA info Institut Supérieur d’Informatique Et de Mathématique de Monastir Enseignant : M. Mahdi JEMMALI Chapitre 3 : Logique des prédicats du premier ordre 1. Introduction Nous avons vu la logique propositionnelle (basée sur les propositions) qui nous a permis de mettre au point une première « théorie du raisonnement ». Il faut aller plus loin que le simple calcul des propositions. Définition : un prédicat est une formule logique qui dépend d'une variable libre. 2. Syntaxe du langage de prédicat 2.1. L’alphabet Le langage du calcul des prédicats est formé des symboles suivants : 1. Ensemble de symboles appelé séparateur : «)», «(» et «,». 2. Un ensemble de symboles appelé constante : les lettres minuscules de l’alphabet et leurs concaténations {a, b, c, . . .}; 3. Un ensemble de symboles appelé variable : les lettres majuscules et leurs concaténations {x, y, z, . . .} ; M. Mahdi JEMMALI 2 4. Un ensemble (dénombrable) de fonctions {f, g, h, . . .} ; 5. Un ensemble de symboles appelé prédicat comme les variables construites de lettres majuscules et leurs concaténations {P,Q, . . .} ; Lorsque on manipule un prédicat, on doit spécifier son nombre d’arguments appelé aussi Arité. Prédicat d’Arité fixe : L’Arité est un nombre entier >0. Lorsque l’Arité est fixé à 0, le prédicat est aussi appelé proposition. 6. Un ensemble de symboles appelé connecteur logique { ¬,∧∨→ ⇔,} 7. Deux symboles appelés quantificateurs : universel ∀ et existentiel ∃. 2.2. Termes Tout terme est engendré par application de deux lois suivantes : ƒ Les constantes et les variables sont des termes. ƒ Si f est un symbole de fonction d’arité n et si t1 . . . tn sont des termes, alors f(t1, . . . , tn) est un terme. 2.3. Atomes ou formules atomiques Les formules atomiques sont formées à partir de la règle suivante : Si P(_ , . . . ,_ ) est un symbole de prédicat d’arité n et si t1 . . . tn sont des termes, alors P(t1, . . . , tn) est une formule atomique. 2.4. Formule bien formée (FBF) M. Mahdi JEMMALI 3 Une formule en logique des prédicats se construit similairement à une formule en logique des propositions. En fait un prédicat va jouer un rôle analogue à une proposition. On doit en plus prendre en compte les quantifications : Les FBF serviront à exprimer des significations. 2.5. Quantificateurs Les différents connecteurs vus dans le chapitre précédant restent tout à fait d'actualité. Mais pour le calcul des prédicats, nous devons introduire deux nouveaux symboles : ce sont des quantificateurs. 2.5.1. Le quantificateur existentiel Ce quantificateur signifie : « il existe » ou plus précisément : « il existe au moins un » et est noté ∃. On peut écrire : ∃xP(x) Et on doit comprendre : « il existe au moins un x tel que P(x) soit vrai ». revient à considérer que P(a1) ∨· · · ∨P(an) est vrai, si {a1, . . . , an} est le domaine de x On peut écrire aussi : ∃!xP(x) M. Mahdi JEMMALI 4 Et on doit comprendre : « il existe un et un seul x tel que P(x) soit vrai ». 2.5.2. Le quantificateur universel Ce quantificateur signifie « quelque soit » et est noté ∀. On peut écrire : ∀xP(x) Et on doit comprendre : « quelque soit x, P(x) est vrai ». revient à considérer que P(a1)∧· · · ∧P(an) est vrai, si {a1, . . . , an} est le domaine de x 2.5.3. Quantificateurs imbriqués Notons que l’ordre des quantificateurs est important. En effet, « tout le monde aime quelqu’un » s’écrirait ∀x . (∃y. Aime(x, y)), qui n’a pas exactement le même sens que « il y a quelqu’un qui est aimé par tout le monde » qui s’écrirait ∃y . (∀x . Aime(x, y)). Liens entre ∀ et ∃ : On a les lois de Morgan pour les quantificateurs : Carré d’Aristote (1) L’introduction d’un quantificateur permet d’exprimer diverses propositions que nous appellerons quantifiées. Par exemple tout est éphémère, qui pourrait s’écrire ∀x E(x), mais aussi rien n’est éphémère, qu’on pourrait écrire ∀x ¬E(x). M. Mahdi JEMMALI 5 Dans la seconde formule, on constate que la variable y n’est pas quantifiée : un telle variable est dite libre. Une variable quantifiée est dite liée. Carré d’Aristote (2) On peut proposer maintenant une nouvelle version du carré d’Aristote, avec des phrases quantificationnelles dans lesquels on distingue une restriction et une portée : M. Mahdi JEMMALI 6 2.6. Variable libre et liée On dit qu'une occurrence d'une variable X dans une formule F est liée si un quantificateur porte sur cette occurrence, sinon cette occurrence est qualifiée de libre. 3. Règles d’inférence Une règle d’inférence est la représentation d’un procédé pour qu’à partir d’une ou plusieurs FBF dériver d’autres FBF. Exemples : M. Mahdi JEMMALI 7 1. La règle d’inférence appelée Modus Ponens, à partir de deux FBF respectivement de la forme G et (G→H), dérive la FBF H. 2. La règle d’inférence spécialisation universelle, à partir d’une FBF de la forme (∀X).G(X) et de n’importe quelle constante, soit : « a », dérive la FBF G(a) : toutes les occurrences de « X » dans G sont remplacées par « a ». 3. La règle d’inférence appelée Modus Tollens, à partir de deux FBF respectivement de la forme (¬H) et (G→H), dérive la FBF (¬G). Les FBF choisies initialement sont appelées axiomes. Les FBF obtenues par application des règles d’inférence sont appelées théorèmes. Une chaîne d’applications de règles d’inférence conduisant, depuis les axiomes, à un théorème, constitue une preuve du théorème. 4. Sémantique 4.1. Interprétation Une interprétation d'une FBF G est définie par les cinq étapes suivantes 1. Choix d'un domaine d'interprétation non vide D 2. Assignation à chaque constante de G d'un élément de D 3. Assignation à chaque proposition de G d'un élément de {V, F} (V : vrai, F : faux) 4. Assignation à chaque prédicat d'arité n (n≥1) d'une application de Dn dans {V, F} (V : vrai, F : faux) M. Mahdi JEMMALI 8 5. Assignation à chaque fonction d'arité n (n≥1) d'une application de Dn dans D. On dit alors qu'on a une interprétation de G sur D 4.2. Valeur selon une interprétation Soit une interprétation i de domaine D d'une fbf G : 1. Si G est une proposition alors la valeur qui lui est assignée par définition de i est appelée valeur de G selon i (ou dans i) 2. Si G est un littéral non propositionnel alors pour chaque choix de valeurs dans D pour les variables de G (s'il en existe) on obtiendra une valeur V ou F en suivant la définition de i. Cette valeur est dite valeur de G selon i pour le choix des valeurs de variables. 3. Si G est de la forme : (X)G', la valeur de G sera V, si la valeur de G' selon i pour toutes les valeurs de la variable (dans D) est V, sinon la valeur de G sera F 4. Si G est de la forme : (∃X) G', la valeur de G sera V si la valeur de G' selon i pour au moins une valeur de X (dans D) est V sinon la valeur de G sera F. Exemple : Valeur de Q(X, Y) dans I2 est V quand X = 1 et Y = 3 donc ∃Y Q(X, Y) est V selon I2 quand X=1 5. Si G est de la forme : (¬G') ou (G' ∧ G") ou (G' ∨ G") ou (G' → G") ou (G'↔ G"), les connecteurs gardent la même sémantique qu'en calcul propositionnel. On définira la valeur de G selon i (quand les valeurs G' et G" selon i seront définies) au moyen des tables de vérité. Remarques : 1. Il y a une infinité d'interprétations pour G 2. On ne peut pas interpréter une fbf contenant des variables libres 4.3. Théorèmes d'équivalence M. Mahdi JEMMALI 9 Soient A, B et C des formules bien formées : 1. Implication matérielle A → B ≅ ¬A ∨ B 2. Equivalence matérielle A ↔ B ≅ (A → B) ∧ (B → A) 3. Commutativité a) A ∨ B ≅ B ∨ A b) A ∧ B ≅ B ∧ A 4. Associativité a) (A ∨ B) ∨ C ≅ A ∨ (B ∨ C) b) (A ∧ B) ∧ C ≅ A ∧ (B ∧ C) 5. Distributivité a) A ∨ (B ∧ C) ≅ (A ∨ B) ∧ (A ∨ C) b) A ∧ (B ∨ C) ≅ (A ∧ B) ∨ (A ∧ C) 6. a) A ∨ V ≅ V b) A ∧ V ≅ A 7. a) A ∨ F ≅ A b) A ∧ F ≅ F 8. Complémentarité a) A ∨ ¬A ≅ V b) A ∧ ¬A ≅ F 9. uploads/Philosophie/ logique-mathematique-etudiants-predicat-ch3.pdf

Tags
Philosophieforme mahdi jemmali formule quantificateurs
Documents similaires
  • 28
  • 0
  • 0
Afficher les détails des licences
Licence et utilisation
Gratuit pour un usage personnel Attribution requise
Partager