ML-Lecture_Chapter3_pt1

Introduction

• La logique propositionnelle est limitée aux opérations booléennes basiques.

• Ne peut pas exprimer des relations complexes ou des déclarations quantifiées.

• La logique des prédicats (logique du premier ordre) surmonte ces limitations en introduisant des variables et des quantités.

Logique de Prédicat

Concepts de Base

• Les prédicats incluent des relations au sein d'un domaine défini.

• Exemple classique : Tout homme est mortel. S'il est décrit qu'Alexandre est un homme, alors Alexandre est mortel.

• En logique propositionnelle, la formulation :

  • P : Tous les hommes sont mortels.

  • Q : Alexandre est un homme.

  • R : Alexandre est mortel.

• Validité du raisonnement mais insuffisante quelquefois :

  • Manque de distinction entre des déclarations singulières et générales.

Variables et Prédicats

Enrichissement de la logique des prédicats

• Introduit des constantes ou variables.

  • Exemples :

    • X (constant) représente un individu, comme Alexandre.

    • Propriétés et relations entre objets, tels que H(x) : x est humain.

• Les prédicats varient selon les propriétés d'un ou plusieurs objets.

  • M(x) : x est mortel

• Les quantificateurs sont également introduits, notés par ∀ (pour tous) et ∃ (il existe).

Syntaxe

• La langue des prédicats se définit par :

  • Ensemble de variables ou constantes E.

• Un prédicat P : E → {0, 1}, représentant une propriété ou relation.

• Exemples :

  • P(x) : x est un nombre premier ; pour P(7) vrai, mais P(8) faux.

  • R(x,y) : x est plus grand que y ; vérifié par exemple entre John et Mary.

Fonctions

• Relation entre un ensemble d'objets avec une sortie unique.

  • Exemples de fonctions : f(x), f(x,y).

• Prédications à un ou plusieurs arguments peuvent être représentées.

Quantificateurs

• Quantificateur universel (∀) : désigne que quelque chose est vrai pour tous les éléments d'un ensemble.

  • Exemple : "Tous les chiens aboient" traduit par ∀x (D(x) → B(x)) où D(x) signifie "x est un chien" et B(x) signifie "x aboie".

• Quantificateur existentiel (∃) : indique qu'il existe au moins un élément pour lequel la propriété est vraie.

  • Exemple : "Il existe un nombre premier plus grand que 100" traduit par ∃x (P(x) ∧ (x > 100)) où P(x) signifie "x est un nombre premier".

Négation des Quantificateurs

Propriétés de Négation

• La manière suivante relie la négation des quantificateurs :

  • ¬(∀x P(x)) ↔ ∃x (¬P(x))

  • ¬(∃x P(x)) ↔ ∀x (¬P(x))

Termes et Atomique

Concepts de Terme

• Un terme est obtenu en appliquant des règles sur des variables ou constantes.

  • Exemples : f(x,y) est un terme.

• Un atome est un prédicat appliqué à des termes.

  • Exemples : P(a,b) est un atome.

Formes Bien Formées (WFF)

• Une WFF est générée par :

  1. Un atome est une formule.

  2. Si F et G sont des WFF, alors (¬F), (F ∧ G), (F ∨ G), (F → G) sont des WFF.

Caractéristiques des Variables

Occurrences et Portée

• La portée d’un quantificateur est la formule à laquelle il s’applique.

  • Exemple : ∀x R(x, z), la portée de ∀x est R(x, z).

• Une variable est dite libre si elle n'est pas liée par un quantificateur.

Substitution de Variables

• La substitution d'une variable dans une WFF implique de remplacer toutes les occurrences libres de cette variable par un terme donné.

  • Exemple : substituer t pour x dans F produit un nouveau terme F[t/x].

Sémantique

• La signification d'une WFF dépend des valeurs des variables ainsi que de l'interprétation des fonctions et prédicats utilisés.

• Une interprétation dépend d'un domaine d'objets choisi.

• Exemple : pour G1: ∀x P(x), assigner des valeurs dans un ensemble permet d'évaluer la vérité de l’énoncé.

Représentation des Connaissances

Traduction des Énoncés en Logique de Prédicat

• Étapes pour traduire des énoncés naturels :

  1. Identifier les constantes, variables et prédicats.

  2. Déterminer les quantificateurs appropriés.

  3. Combiner prédicats et quantificateurs pour créer une WFF.

• Exemples :

  • "Tous les humains sont mortels" devient ∀x (H(x) → M(x)).