Ensembles et relations d’ordre

John McCarthy, un des pères fondateurs de l’Intelligence Artificielle, a défini celle-ci comme étant : “La science et l’ingénierie de la création de machines intelligentes.”

L’acquisition et la représentation des connaissances est un aspect central dans le domaine de l’Intelligence Artificielle car une machine intelligente qui souhaite effectuer l’action appropriée à une situation ou tenir un raisonnement correct doit avant tout s’appuyer sur des informations représentant le monde de façon suffisamment précise. Cette difficulté à disposer d’une représentation correcte du monde est particulièrement importante lorsque l’on a affaire à un monde changeant ou à des informations provenant de sources multiples. La question est donc de savoir ce qu’un agent choisit de croire lorsque ses seules sources sont d’autres agents ou experts ? Lorsque les informations apportées par les agents sont cohérentes entre elles, il suffit de considérer l’union de ces informations comme étant la représentation du monde. Mais dans le cas où les agents possèdent des informations conflictuelles, cette solution n’est pas souhaitable car elle conduirait à une représentation incohérente du monde. Il sera donc nécessaire pour notre agent de transiger, de choisir, parmi les informations qui lui sont fournies celles qui lui permettent d’obtenir une représentation du monde qui soit cohérente.

Ensembles et relations d’ordre

Ensembles

De manière générale, on nomme ensemble une collection d’objets quelconques. Soient A et B deux ensembles, leur union, notée A ∪ B, est la collection des objets appartenant à A ou à B. Leur intersection, notée A ∩ B est la collection des objets appartenant à la fois à A et à B. Un multi-ensemble est un ensemble qui peut contenir plusieurs fois le même objet. On note ⊔ l’union de multi-ensembles et ⊓ leur intersection.

Relations, ordres et pré-ordres

Soit E un ensemble. Une relation binaire sur E est un sous-ensemble de E × E. Autrement dit, une relation binaire est un ensemble de couples (x, y) tels que x ∈ E et y ∈ E. On note xRy le fait qu’un couple (x, y) appartient à une relation R. On note x 6 Ry si (x, y) n’appartient pas à la relation R. P(E) représente l’ensemble des sous-ensembles de E.

Une relation R définie sur E × E peut vérifier les propriétés suivantes : réflexive si et seulement si ∀x ∈ E, xRx ; transitive si et seulement si ∀x ∈ E, ∀y ∈ E, ∀z ∈ E, si xRy et yRz, alors xRz ; symétrique si et seulement si ∀x ∈ E, ∀y ∈ E, si xRy alors yRx ; antisymétrique si et seulement si ∀x ∈ E, ∀y ∈ E, si xRy et yRx alors x = y ; totale si et seulement si ∀x ∈ E, ∀y ∈ E, xRy ou yRx ;

Une relation qui n’est pas totale est dite partielle et une relation qui n’est pas réflexive est dite irréflexive. Un ordre est une relation réflexive, transitive et symétrique. Un pré-ordre est une relation réflexive et transitive. Une relation d’équivalence est une relation réflexive, transitive et antisymétrique. Un ordre strict est une relation irréflexive et transitive.

Soit un pré-ordre ≤ défini sur E × E, on définit l’ordre strict < associé par x < y si et seulement si x ≤ y et y 6≤ x. On définit également une relation d’équivalence ∼ par x ∼ y si et seulement si x ≤ y et y ≤ x.

Logique propositionnelle

La langage de la logique propositionnelle est construit à partir d’un ensemble infini dénombrable de variables propositionnelles V (que nous noterons à l’aide de lettres minuscules), des constantes ⊤ (représentant le Vrai) et ⊥ (représentant le Faux), des connecteurs ¬,∨,∧,→,↔ ainsi que des symboles de ponctuation ( et ). L’ensemble des formules finies formées à partir de ces symboles est noté L.

Définition 1.2.1. L’ensemble des formules bien formées de L est le plus petit ensemble tel que :
– ⊥ et ⊤ sont des formules ;
– une variable propositionnelle est une formule ;
– si A et B sont des formules, alors ¬A, A ∨ B, A ∧ B, A → B, A ↔ B sont des formules.

Exemple 1.2.1. Par exemple, les formules suivantes sont des formules bien-formées de la logique propositionnelle :

F = {a,¬a ∨ b,(a ∧ b) → c}

Aspect sémantique

La sémantique permet de définir des règles d’interprétations pour les formules à partir de la valeur de vérité de chacune des propositions qui les composent.

Définition 1.2.2. On appelle interprétation toute application ω de V dans {0, 1} telle que ω(⊥) = 0 et ω(⊤) = 1. L’application ω est étendue aux formules de la façon suivante : ∀A, B ∈ L :
– ω(¬A) = 1 − ω(A)
– ω(A ∨ B) = max(ω(A), ω(B))
– ω(A ∧ B) = min(ω(A), ω(B))
– ω(A → B) = max(1 − ω(A), ω(B))
– ω(A ↔ B) = min(max(1 − ω(A), ω(B)), max(ω(A), 1 − ω(B)))

L’ensemble des interprétations sur un langage L est noté W. Une interprétation est souvent représentée sous la forme d’une table de vérité. Une interprétation ω satisfait une formule A, noté ω |= A , si et seulement si ω(A) = 1. Une interprétation ω satisfaisant une formule A est appelée modèle de A. L’ensemble des modèles de A est notée Mod(A). Par extension, on notera A |= B lorsque l’ensemble des modèles de A satisfont B, i.e. Mod(A) ⊆ Mod(B).

On dira d’une formule qu’elle est valide (ou qu’elle est une tautologie) si elle est vraie pour toute interprétation . Une formule fausse pour toute interprétation est dite insatisfaisable ou incohérente. On dit qu’une formule est satisfaisable ou cohérente s’il existe une interprétation qui la satisfait. Une interprétation qui satisfait une formule A (ou toutes les formules d’un ensemble de formules A) est appelée modèle de A (ou de A). À l’inverse, une interprétation qui ne satisfait pas une formule A (ou toutes les formules d’un ensemble de formules A) est appelée contre-modèle de A (ou de A).

Définition 1.2.3. La formule B est une conséquence logique ou conséquence valide de la formule A si ω(A) = 1 implique ω(B) = 1, on écrit alors A |= B. La formule B est une conséquence logique de l’ensemble de formules F, si ∀A ∈ F, ω(A) = 1 alors ω(B) = 1, on écrit F |= B

L’ensemble des conséquences logiques déductibles d’une formule A est noté Cons(A).

Définition 1.2.4. Soit F un ensemble de formules et G une formule, Cons(F) représente l’ensemble des conséquences de F. G ∈ Cons(F) si et seulement si F |= G. Si deux formules ont un même ensemble de conséquences, on dit alors qu’elles sont sémantiquement équivalentes.

Définition 1.2.5. Les formules A et B sont équivalentes si et seulement si A |= B et B |= A, on écrit alors A ≡ B. Une interprétation est représentée soit comme un ensemble de variables soit comme un vecteur dont les composantes correspondent aux valeurs de vérité des variables propositionnelles rangées selon un ordre lexicographique.

Aspect axiomatique

La logique propositionnelle peut être considérée comme un système formel. Un système formel est un ensemble de règles permettant en un nombre fini d’étapes et selon des règles explicites de déterminer si une proposition est un théorème. Un tel procédé s’appelle une démonstration . En logique propositionnelle, on définit un langage grâce à des règles d’écriture permettant d’effectuer de telles démonstrations. Le système formel de la logique propositionnelle est basé sur des axiomes – des propositions évidentes par ellesmême ne nécessitant pas de démonstrations – ainsi que sur deux règles de déductions : la substitution et le modus ponens.

Parmi les ensembles d’axiomes proposés, le système de Lukasiewicz [Luk64] est le plus succinct. Il est basé sur les trois axiomes suivants :
– A1 : A → (B → A)
– A2 : (A → (B → C)) → ((A → B) → (A → C))
– A3 : (¬A → ¬B) → (B → A)

Grâce à ces axiomes et aux règles suivantes, il est possible de démontrer si de nouvelles formules sont des théorèmes pour le système, on appelle cela une déduction. Pour pouvoir réaliser des déductions, deux règles sont définies : la règle de la substitution et le modus ponens. La règle de substitution autorise le remplacement d’une variable propositionnelle, partout où elle apparaît, par n’importe quelle formule bien-formée. Le modus ponens stipule que si de l’ensemble de formules G on peut déduire A et de l’ensemble de formules H on peut déduire A → B, alors de G et H on peut déduire B. On utilise le symbole ⊢ pour noter la relation de déduction ou d’inférence. Le symbole ⊢ n’est pas un nouveau symbole du langage mais appartient au métalangage.

Le rapport de stage ou le pfe est un document d’analyse, de synthèse et d’évaluation de votre apprentissage, c’est pour cela rapport-gratuit.com propose le téléchargement des modèles complet de projet de fin d’étude, rapport de stage, mémoire, pfe, thèse, pour connaître la méthodologie à avoir et savoir comment construire les parties d’un projet de fin d’étude.

Table des matières

Introduction
1 Préliminaires
1.1 Ensembles et relations d’ordre
1.1.1 Ensembles
1.1.2 Relations, ordres et pré-ordres
1.2 Logique propositionnelle
1.2.1 Aspect sémantique
1.2.2 Aspect axiomatique
1.2.3 Principales propriétés de la logique propositionnelle
1.2.4 Les méthodes énumératives et le problème SAT
1.2.5 La résolution
1.3 Logique des prédicats
1.3.1 Variables liées, variables libres et formules closes
1.3.2 Aspects sémantiques et syntaxiques
1.4 La logique possibiliste
1.4.1 Base de croyances et distribution de possibilité
2 La programmation logique
2.1 PROLOG
2.1.1 Les faits
2.1.2 Les règles
2.1.3 Les questions
2.1.4 Négation par échec
2.1.5 Les sémantiques de PROLOG
2.2 Programmes logiques
2.2.1 Programme logique basique
2.2.2 Dénomination des programmes logiques
2.3 Sémantique bien-fondée
2.3.1 Ensemble non-fondé
2.3.2 Modèle partiel bien-fondé
2.3.3 Modèle bien-fondé
2.4 Sémantique des modèles stables
2.4.1 Définition des modèles stables
2.4.2 Une définition alternative des modèles stables
2.4.3 Différentes utilisations de programme ASP
2.5 Langage ASP et solveurs
2.5.1 Langage ASP et instructions supplémentaires
2.6 Les préférences dans un programme logique
2.6.1 Théorie et définition
2.7 Solveurs ASP
2.7.1 Lparse
2.7.2 Smodels
2.7.3 Kernel Normal Form
2.7.4 CLASP
2.8 Genérer et tester
2.9 Programmation logique possibiliste
3 Changement de croyances
3.1 Révision
3.1.1 Changement de théories
3.1.2 Approche sémantique
3.1.3 Opérateurs de révision syntaxique
3.1.4 Révision itérée
3.2 Fusion de croyances
3.2.1 Flock et profil de croyances
3.2.2 La question des contraintes d’intégrité
3.2.3 Postulats
3.2.4 Arbitrage et majorité
3.2.5 Opérateurs
3.2.6 Fusion réversible
3.2.7 Fusion possibiliste
3.2.8 Fusion de bases de croyances exprimées en logique possibiliste
3.2.9 Résultat d’équivalence
4 Fusion par R-ensembles
4.1 Principes et définitions
4.1.1 Fusion pure par R-ensembles
4.1.2 Fusion avec contraintes
4.1.3 Réécriture des postulats de Konieczny-Pino Perez
4.2 Différents opérateurs de fusion syntaxique
4.2.1 Somme
4.2.2 Card
4.2.3 Max
4.2.4 GMax
4.3 Contrepartie sémantique
4.3.1 Contrepartie sémantique de l’opérateur Somme
4.3.2 Contrepartie sémantique de l’opérateur Card
4.3.3 Contrepartie sémantique de l’opérateur M ax
4.3.4 Contrepartie sémantique de l’opérateur GM ax
4.4 Généralisation de la Révision par R-ensembles
Conclusion

Lire le rapport complet

Télécharger aussi :

Laisser un commentaire

Votre adresse e-mail ne sera pas publiée. Les champs obligatoires sont indiqués avec *