Logique des propositions

LOGIQUE

INFORMATIQUE

OLFA MOUELHI

MOHAMED HENY SELMI

ECOL E SUPÉRIEURE PR IVÉE D 'INGÉNIERIE ET DE TECHNOL OGIES

olfa.mouelhi@esprit.tn

medheny.selmi@esprit.tn

ORGANISATION DU

MODULE

Enseignement

• Cours/TD 80%

• TP sur machine 20%

Langage support PROLOG

Évaluations

• Evaluation (TD noté) 20%

• TP noté en fin de module 20%

• Examen final 60%

Olfa MOUELHI - Mohamed Heny SELMI

INTRODUCTION

PLAN DU COURS

Logique formelle (Bases théoriques )

• Calcul propositionnel

• Calcul des prédicats

Le langage PROLOG

Olfa MOUELHI - Mohamed Heny SELMI

DOMAINES D’APPLICATION

Intelligence Artificielle : une nouvelle façon de programmer

Systèmes Experts, Systèmes d’Aides à la Décision

Programmation des Jeux

Techniques de Représentation de Connaissances

Traduction formelle et Interprétation des langages naturel

Olfa MOUELHI - Mohamed Heny SELMI

EN TP, VOUS

APPRENDREZ À ...

Utiliser PROLOG

Résoudre automatiquement des énigmes logiques exprimées en

langage naturel

Olfa MOUELHI - Mohamed Heny SELMI

1. LOGIQUE DES PROPOSITIONS

(LOGIQUE D’ORDRE 0)

2. LOGIQUE DES PREDICATS

(LOGIQUE D’ORDRE 1)

3. PROGRAMMATION LOGIQUE

PROLOG

1. LOGIQUE DES PROPOSITIONS

(LOGIQUE D’ORDRE 0)

2. LOGIQUE DES PREDICATS

(LOGIQUE D’ORDRE 1)

3. PROGRAMMATION LOGIQUE

PROLOG

QU’EST-CE QU’UNE PROPOSITION ?

Une connaissance qui est vraie ou fausse!

Exemple :

- il pleut p1

- il fait beau p2

- après le repas, je tonds la pelouse p3

- Il y a un bon film à la télévision ce soir p4

Chacun de ces énoncés est représenté par une proposition.

On nomme chaque proposition élémentaire.

Olfa MOUELHI - Mohamed Heny SELMI

Construire de nouvelles propositions à partir de

celles qui existent en ajoutant des connecteurs :

-Il pleut et il y a un bon film à la télévision ce soir:

-Je ne tonds pas la pelouse après le repas:

-Il pleut si et seulement si il ne fait pas beau:

p1 ^ p4

¬p3

p1 ¬p2

Olfa MOUELHI - Mohamed Heny SELMI

DÉFINITION

Etude scientifique des conditions de vérités de proposition.

Manière basique et simple de raisonner.

Enchainement cohérent d’idées.

Olfa MOUELHI - Mohamed Heny SELMI

OBJECTIFS

Comment écrire les formules ?

• Aspects syntaxiques

Comment déterminer la valeur de vérité d’une formule ?

• Aspects sémantiques

Comment démontrer de nouveaux résultats ?

• Aspects déductifs

modéliser

interpréter

Raisonner

Olfa MOUELHI - Mohamed Heny SELMI

SYNTAXE DU LANGAGE

Vocabulaire

• un ensemble de variables propositionnelles(atomes)

{ p, q, r, … } énoncés élémentaires

• un ensemble de connecteurs

{ , , , , }

• Ensemble de délimiteurs

{(,)}

Formules bien formée (fbf)

• p est une fbf

• (H) est une formule si H est une fbf

• (H K), (H K), (H K) et (H K) sont des fbf si H et K sont

des fbf

Olfa MOUELHI - Mohamed Heny SELMI

PRIORITÉ DES CONNECTEURS

ET PARENTHÈSES

On utilise les parenthèses pour éviter les ambigüités de lecture.

Priorité décroissante des connecteurs dans l’ordre:

Quand il y’a un seul connecteur l’association se fait de gauche à droite

Exemples:

1) P Q R (P (( Q) (R)))

2) P Q R (P (Q R ))

3) P QR S (((P Q)R) S)

Olfa MOUELHI - Mohamed Heny SELMI

SÉMANTIQUE D’UNE FORMULE

Logique bi-valuée

• fausse (F)

• vraie (V)

Notion d’interprétation

• donner une valeur de vérité à une variable

• Pour n atomes 2n interprétations

1,,)( OouFVp

Olfa MOUELHI - Mohamed Heny SELMI

TABLES DE VÉRITÉ :

OPÉRATEURS

V

F F F

F V

F V

V V

V V

F V

V F

F V

p p

F

V

F V

F

V

F V

F

V

F V

F

V

F V

F

V

Olfa MOUELHI - Mohamed Heny SELMI

FORMULES

PARTICULIÈRES

Tautologie (valide) : formule toujours vraie

• Toutes les interprétations ne contiennent que des V

• exemple : p p

p ( p) (p p)

F

V

V

F

V

V

F V

V V

F V

F

V

toutes les interprétations

sont évaluées à VRAIE

Olfa MOUELHI - Mohamed Heny SELMI

)()(: qpqpA

p q ¬ p ¬ q p q ¬ ( p q ) (¬ p ¬ q) A

F F

F V

V F

V V

V

V

F

F

V

F

V

F

F F

F V

F V

F

V

F V

V

V

F

F V

V V

F V

F

V

V F

F

V V

V

V F

F V

F V

F

V

V

V

V

V F

Calcul propositionnel

est-elle valide?

Olfa MOUELHI - Mohamed Heny SELMI

VALIDE, INVALIDE, INCONSISTANTE,

CONSISTANTE ???

F V

V

V

V

V

F

F

F

F

F V

V F

V

F

V

V

F

F

V

F

F V V F

VALIDE INCONSISTANTE

CONSISTANTE INVALIDE INVALIDE

et

CONSISTANTE

V

V

F

F

Olfa MOUELHI - Mohamed Heny SELMI

FORMULES ÉQUIVALENTES

Formules tautologiquement équivalentes

• les tables de vérité sont les mêmes

• Condition nécessaire et suffisante :

(A) (B) est une tautologie

)()(, BA

Calcul propositionnel

A B V V

V V

F F

V V

F F

F F

F F

EQUIVALENTES

A B V V

V F

F F

V V

F F

F F

F F

EQUIVALENTES

AB V

V

V

V

V

V

V

EQUIVALENTES

Olfa MOUELHI - Mohamed Heny SELMI

FORMULES

ÉQUIVALENTES UTILES

AA= V (loi du tiers exclu)

A A=F

((AB) A) B (modus ponens)

((A B) B) A (modus tollens)

(A B) (B A) (contraposition)

A A (double négation)

A B A B

A B (A B) (B A)

AA AA A (idempotence)

Olfa MOUELHI - Mohamed Heny SELMI

Lois de Morgan :

(AB) A B

(AB) A B

FORMULES

PARTICULIÈRES

Olfa MOUELHI - Mohamed Heny SELMI

EXERCICE

D’APPLICATION :

Développer la négation en appliquant les lois de Morgan:

Olfa MOUELHI - Mohamed Heny SELMI

FORMES NORMALES

But:

avoir une représentation uniforme des formules du calcul

propositionnel

limiter le nombre de connecteurs différents utilisés

FORMES NORMALES

FN CONJONCTIVES

FN DISJONCTIVES

(, ¬) (, ¬) Olfa MOUELHI - Mohamed Heny SELMI

FORMES NORMALES

Une formule F est dite sous Forme Normale Disjonctive ssi F est une disjonction de conjonctions de variables propositionnelles et de leurs négations

Toute formule du calcul propositionnel est tautologiquement équivalente à une formule sous forme normale disjonctive

Une formule F est dite sous Forme Normale Conjonctive ssi F est une conjonction de disjonctions de variables propositionnelles et de leurs négations

Toute formule du calcul propositionnel est tautologiquement équivalente à une formule sous forme normale conjonctive

Olfa MOUELHI - Mohamed Heny SELMI

ALGORITHME DE

NORMALISATION

Début

Elimination des connecteurs et

Remplacer A B par A B

A B par (A B) (B A)

Application des lois de Morgan

Remplacer (AB) par A B

(AB) par A B

Elimination des doubles négations A par A

Application des règles de distributivité

A (B C) par (A B) (AC)

(A B) C par (AC) (BC)

Fin

Olfa MOUELHI - Mohamed Heny SELMI

ASPECTS

DÉDUCTIFS

NOTION DE CONSÉQUENCE LOGIQUE

NOTION DE RAISONNEMENT

CONSÉQUENCE

LOGIQUE / SÉMANTIQUE

F1, F2 ,…, Fn n formules bien formées : hypothèses

G une formule bien formée : conclusion

? Peut on déduire G à partir des hypothèses F1, F2 ,…, Fn

G est une conséquence logique de F1, F2 ,…, Fn ssi

(F1 … Fn) G est une tautologie

OU G est une conséquence logique de F1, F2 ,…, Fn ssi

(F1 … Fn) G est inconsistante

Notion de réfutation : démonstration par l’absurde

Olfa MOUELHI - Mohamed Heny SELMI

EXERCICE

D’APPLICATION:

Considérons les arguments suivants:

« Si Didier est l’auteur de ce bruit, il est stupide ou

dépourvu de principes. Didier n’est ni stupide ni dépourvu de

principes. Donc Didier n’est pas l’auteur de ce bruit. »

Olfa MOUELHI - Mohamed Heny SELMI

H1 : « Si Didier est l’auteur de ce bruit, il est stupide ou dépourvu de

principes »

(D → (S ∨ P))

H2 : « Didier n’est pas stupide »

￢S

H3 : « Didier n’est pas dépourvu de principes » ￢P

C : « Didier n’est pas l’auteur de ce bruit »

￢D

D : « Didier est l’auteur de ce bruit »

S : « Didier est stupide » P : « Didier est dépourvu de principes »

Olfa MOUELHI - Mohamed Heny SELMI

La table de vérité nous permet de vérifier aisément l’assertion:

Vérifier si ?

C est une conséquence logique de H1, H2 et H3

Olfa MOUELHI - Mohamed Heny SELMI