●

LOGIQUE ET IA PARTIE 2

– LOGIQUE DES PROPOSITIONS

– LOGIQUE DES PRÉDICATS

Mme Pidy Léonce

La logique des propositions

Aristote a défini ainsi le concept de proposition :

« tout discours n'est pas une
proposition, mais seulement le discours dans lequel
réside le vrai ou le faux, ce
qui n'arrive pas dans tous les cas : ainsi la prière
est un discours, mais elle n'est
ni vraie ni fausse »
La logique des propositions

●
La logique propositionnelle, également connue sous le
nom de logique des énoncés, est l'étude du raisonnement
formel basé sur l'utilisation de propositions.
●
Une proposition est une déclaration qui peut être vraie ou
fausse, mais pas les deux à la fois.
●
Cette branche de la logique est fondamentale dans de
nombreux domaines tels que la philosophie, l'informatique
et les mathématiques.
La logique des propositions

●
La syntaxe
L'alphabet de la logique des propositions

l'alphabet est constitué :

●
de connecteurs : ¬, ∧, ∨, →, ↔ qui se lisent respectivement non,
et, ou, implique et équivalent.
●
de délimiteurs : les parenthèses ( )
●
d'un ensemble infini dénombrable d'atomes appelés aussi
propositions ou variables propositionnelles
un atome en logique propositionnelle est une proposition élémentaire
sans structure interne, servant de brique de base pour construire des
formules composées à l'aide des connecteurs logiques. Sa vérité
dépend du modèle d'interprétation et non de sa structure logique.
●
des deux constantes propositionnelles V (vrai) et F (faux)

Mme Pidy Léonce

Les formules bien formées

Le langage est constitué de l' ensemble des Formules Bien

Formées (appelées aussi : FBFs ou Well Formed-Formula
WFF) ou expressions bien formées défini comme suit:
●
Base :
●
Induction :
●
Clôture : toutes les fbfs sont obtenues par application des
2 règles ci-dessus.
●
Ordre de priorité des connecteurs :
●
Quand il y a un seul connecteur, l'association se fait de
gauche à droite.
Exemples
●
A ∧ ¬B ∨ C → D ∧ E doit se lire
●
A → B → C correspond à

déterminer si les formules suivantes appartiennent à la logique des

propositions.
Soient A, B, C, D des fbfs
●
a) ((A ∨ (¬B)) ∧ (C ∨ D))
●
b) (A ∨ B) (∧ ∨ C)

Mme Pidy Léonce

La logique des propositions

●
La sémantique
Interprétation

Une interprétation du calcul propositionnel consiste à donner :

1. Domaine sémantique non vide D
2. Valuation des atomes dans D
3. Définition des connecteurs par des applications de D dans D pour ¬
et de D∗D dans D pour ∧, ∨, →, ↔.
Interprétation classique de la logique des propositions pour lequel D =
{V, F}
Tout atome est vrai ou faux mais pas les deux à la fois
●
Pour une fbf G composée de différents atomes : A1...An, une
interprétation de G est une assignation des valeurs de vérité à
A1...An. G comporte n atomes ==> 2n interprétations possibles
Interprétation

Une fbf G est vraie (respectivement fausse) dans une

interprétation i si la valeur de G est vraie (respectivement
fausse)
●
On écrit i[G] = V (respectivement i[G]= F)
●
Une interprétation qui rend vraie une formule est un
modèle de cette formule.
●
On dit qu'une interprétation i est un modèle d'une formule
F si la valeur de F selon l'interprétation i est vraie : i[F] = V
dans ce cas on note i |= F.
●
On dit que i est un modèle d'un ensemble de formules E si
i est modèle de tout élément de E
Théorèmes d'équivalence

●
Deux fbfs F et G sont équivalentes si et seulement si les
valeurs de vérité de F et de G sont les mêmes dans toute
interprétation.
●
On peut démontrer que des formules sont équivalentes en
montrant qu'elles ont les mêmes valeurs dans toutes les
interprétations. Un moyen est donc de construire leur table
de vérité.
●
On peut utiliser les théorèmes d'équivalence pour
transformer une formule bien formée en une autre formule
bien formée qui lui est équivalente. Cela va permettre de
simplifier l'écriture de formules bien formées.

Mme Pidy Léonce

Théorèmes d'équivalence

Soient A, B et C des formules bien formées.

●
1. Implication matérielle
–
●
2 .Equivalence matérielle
–
●
3.Commutativité
–
●
4.Associativité
–
Théorèmes d'équivalence
Soient A, B et C des formules bien formées.
●
5.Distributivité
–
●
6.Lois de de Morgan
–
●
7.Complémentarité.
–
●
8.Identité
–
Théorèmes d'équivalence

●
9.Involution
–
●
10. éléments absorbants
–
●
11. éléments neutres
–
Exemple

1- Dresser la table de vérité des connecteurs logiques

2-Soit la formule G : (P → (Q ∨ (¬R)))
●
Soit i1 telle que: i1[P] = i1[R] = V i1[Q] = F
i1[G]= ?
●
Soit I2 telle que: i2[P] = i2[R] = F i2[Q] = V
i2[G]= ?
3- démontrer
– a) A ∨ ((¬A) ∧ B) ≅ A ∨ B
– b) A ∧ ((¬A) ∨ B) ≅ A ∧ B
Exemple

4- développer la négation en appliquant les lois de de

Morgan
●
a) (¬(A ∧ (B ∨ C)))
●
b) (¬((¬(A ∧ B)∨ (¬D)) ∧ E ∨ F))
La logique des propositions

●
Quelques notions classiques

Mme Pidy Léonce

Validité

●
Une fbf A est une tautologie (valide) si et seulement si elle
est vraie dans toute interprétation; on écrit alors : |= A

– ¬A ∨ A est une formule valide

●
Une fbf est invalide si et seulement si elle n'est pas valide

– A ∧ B et A ∨ B sont deux formules invalides il suffit

que A et B soient fausses
Insatisfaisabilité

●
Une fbf est inconsistante ou insatisfiable si et seulement
si elle est fausse dans toute interprétation
– ¬A ∧ A est une formule inconsistante
●
Une fbf A est consistante ou satisfiable
– si et seulement si elle n'est pas inconsistante
– si il existe une interprétation i telle que i[A] = V
– si elle admet un modèle
– A ∧ B et A ∨ B sont deux formules consistantes il suffit
que A et B soient vraies
Conséquence logique
●
A est une conséquence logique de E si et seulement si toutes
les interprétations qui rendent vraies toutes les formules de E
rendent vraie la formule A.
– On écrit alors E |= A
●
On dit qu'une formule C est une conséquence logique de H1..
Hn
– si et seulement si tout modèle de H1..Hn est un modèle de C
– si et seulement si H1 ∧ H2 ∧ ... ∧ Hn → C est valide
● Dans ce contexte les formule Hi sont les hypothèses et C est la
conclusion.
Complétude

●
Pour toute formule A si |= A alors |− A
●
Autrement dit : toutes les tautologies sont des théorèmes.
La logique des propositions

●
Représentation des connaissances
Représentation des connaissances

●
La représentation des connaissances en Intelligence
Artificielle consiste à faire une correspondance entre le
monde extérieur et un système symbolique manipulable
par un ordinateur.
●
La représentation des connaissances comporte un aspect
passif : il faut mémoriser.Par exemple, un livre ne connaît
pas l'information qu'il contient.
●
Mais aussi un côté actif : il faut inférer, manipuler ces
connaissances, effectuer un raisonnement.
Représentation des connaissances

Les ressemblances entre les connecteurs logiques et ceux de la

langue naturelle sont limitées.
●
Il mange ou il dort et il dort ou il mange semblent synonymes
●
Par contre, il a faim et il mange n'est pas semblable à il
mange et il a faim car le "et" a une connotation de causalité et
de temps.
●
La porte est ouverte ou la porte est fermée. Le "ou" du
français est parfois exclusif
●
La traduction est en général liée au contexte. Il peut aussi
exister plusieurs traductions possibles.
La conjonction

●
P ∧ Q peut se traduire :
–

Mme Pidy Léonce

La disjonction

●
P ∨ Q peut se traduire :
–
Le conditionnel

●
P → Q peut traduire :
–
L'équivalence

●
P ↔ Q peut se traduire :
–
Exemple

●
Jean et Pierre prirent le café et Gustave fit de même.
●
Jean prit le café, et Pierre ou Gustave aussi
●
Jean et Pierre ont dîné tous les deux, ou bien Jean et
Gustave prirent le café
●
Jean a dîné, ainsi que Gustave ou Pierre
●
Système de preuves par résolution
Le principe de résolution est une méthode automatique pour montrer
la validité d'une formule

Mme Pidy Léonce

Notion de clause

●
Une clause est une fbf qui a la forme d'une disjonction de
littéraux
●
Cas particulier : un littéral isolé est une clause.
●
Exemple de clauses :
– A ∨ B ∨ C ∨ ¬D
– ¬D
Clause résolvante

●
Si C1 et C2 sont 2 clauses et si L1 = ¬L2 et L1 est dans
C1 et L2 est dans C2
●
C est la disjonction des clauses restantes après
suppression des littéraux L1 et L2.
●
Elle est appelée clause résolvante et ou résolvant de C1 et
de C2.
●
L1 et L2 sont les littéraux résolus.
Exemples
●
Soient C1 et C2 les deux clauses suivantes :
– C1 : E1 ∨ E2
– C2 : ¬E2 ∨ E3
●
Le résolvant de C1 et de C2 est C :
●
Soient C1 et C2 les deux clauses suivantes :
– C1 : P
– C2 : ¬P
●
Le résolvant de C1 et de C2 est C :
●
La clause Faux est notée ¬ c'est la clause vide
●
Le résolvant C de deux clauses C1 et C2 est une conséquence
logique de C1 et de C2
Exemples

Trouver la clause résolvante dans les cas suivants :

●
a) C1 = ¬Q ∨ P C2 = R ∨ ¬P ∨ S
●
b) C1 = ¬Q ∨ P C2 = Q
●
c) C1 = ¬P ∨ ¬Q C2 = P ∨ S ∨ ¬R
●
d) C1 = P ∨ Q C2 = R ∨ P
Algorithme de résolution

●
On appelle déduction (ou résolution) d'une clause C à
partir d'un ensemble de clauses S= séquence finie R1,
R2,... Rn = C de clauses telle que chaque Ri est:
– soit une clause de S
– soit un résolvant de clauses le précédant
●
S = {R ∨ Q, ¬R, ¬Q ∨ P, ¬P ∨ R}
●
R1 = R ∨ Q
●
S'il existe une déduction de la clause vide à partir de S
alors S est insatisfiable

Mme Pidy Léonce

Algorithme de résolution

●
On appelle réfutation la déduction de la clause vide Ø à
partir de S. Montrer qu'une formule bien formée F est
valide :
– C'est équivalent à montrer que ¬F est inconsistante
– C'est aussi équivalent à monter que S ¬F insatisfiable
– C'est aussi équivalent à monter qu'il existe une
déduction de la clause vide Ø
Algorithme de résolution
●
Algorithme de résolution
●
Début
– Ecrire la négation de F ;
– Mettre F sous forme d'un ensemble de clauses ;
– Tant que la clause vide n'est pas rencontrée et qu'il existe des paires réductibles faire
●
Début
– Chercher des clauses résolvantes ;
– Ajouter ce résultat à la liste des clauses ;
– Fintantque ;
– Si on trouve la clause vide alors F est valide
– sinon F est invalide
– Finsi ;
●
Fin ;
●
NB : une clause peut être utilisée plusieurs fois et des clauses peuvent ne pas être
utilisées pour déduire la clause vide
Exemple

●
Soit S ¬F ={¬P ∨ ¬Q ∨ R, ¬R, P, ¬T ∨ Q, T}
– Montrons que cet ensemble est insatisfiable
●
S ¬F = {P ∨ Q, ¬Q ∨ T, ¬T ∨ R, ¬R, ¬P ∨ R, Q ∨ S, P
∨ S}
– Montrons que cet ensemble est insatisfiable
Les limites et ouverture vers la logique des prédicats

●
La logique des propositions est limitée dès que l'on veut
manipuler des propriétés générales un peu complexes, ou
des relations entre des objets,
●
on peut aussi avoir besoin de quantifier en exprimant
"Tous les hommes sont mortels". Rien ne nous permet de
faire cela en logique des propositions.
Les limites et ouverture vers la logique des prédicats

●
La logique des propositions est limitée dès que l'on veut manipuler des
propriétés générales un peu complexes, ou des relations entre des
objets,
●
on peut aussi avoir besoin de quantifier en exprimant "Tous les hommes
sont mortels". Rien ne nous permet de faire cela en logique des
propositions.
●
Si on a besoin d'exprimer des relations ou propriétés, des fonctions la
logique des propositions ne le permet pas.
●
Le prédicat est le concept qui pallie ce problème. Il exprime une
relation dans un contexte.
Les limites et ouverture vers la logique des prédicats

●
"Quelqu'un a chanté quelque chose "
●
on peut définir le prédicat : A_CHANTE avec deux
arguments ou termes : celui qui chante et ce qu'il chante
– A_CHANTE(MARIA_CALLAS,TRAVIATA)
●
"Le frère de Paul travaille avec le frère de Jacques"
●
peut se traduire par le prédicat TRAVAILLER avec deux
arguments et par le symbole de fonction frere
– TRAVAILLER(frere(paul),frere(jacques))

Mme Pidy Léonce

●
La logique des prédicats
L'alphabet
●
de connecteurs : ¬, ∧, ∨, →, ↔ qui se lisent respectivement non, et, ou, implique et
équivalent.
●
de délimiteurs : les parenthèses ( )
●
des deux constantes propositionelles V (vrai) et F (faux)
●
de constantes (minuscules de l'alphabet latin et les concaténations de telles lettres) C = {a, b,
c,...z, aa,...}
●
de variables (majuscules de l'alphabet latin, et les concaténations de telles lettres) V = {A, B,
Z, AA..}
●
de prédicats (majuscules P)
– L'arité d'un prédicat est le nombre d'argument du prédicat. C'est un nombre positif. Si le
prédicat est d'arité 0 il correspond à la notion de proposition de la logique des propositions
●
de fonctions (en minuscules: f, g sucesseur). Chaque symbole de fonction a une arité fixée.
– L'arité d'une fonction est le nombre d'argument de la fonction. C'est un nombre positif. Si
la fonction est d'arité 0, elle correspond à la notion de constante .
●
de quantificateurs
– ∃ prononcé "il existe" est le quantificateur existentiel
– ∀ prononcé "quel que soit" est le quantificateur universel
Les termes
●
Par définition, tout terme est engendré par application des deux
lois suivantes
– constantes et variables sont des termes
– si f est un symbole de fonction d'arité n (n>=1) et si t1..tn
sont des termes alors f(t1..tn) est un terme
●
Exemple :
– successeur(X) est un terme
– poids(b) est un terme
– successeur(poids(b)) est un terme
– P(X, bleu) n'est pas un terme
– poids(P(X)) n'est pas un terme
Les atomes
●
Par définition, tout atome est engendré par application des deux
lois suivantes
– Les propositions sont des atomes
– si P est un prédicat d'arité n (n >=1) et si t1..tn sont des
termes alors P(t1..tn) est un atome
●
Exemple :
– P(X, bleu) est un atome
– VIDE est un atome
– ENTRE(table,X, appui(fenetre)) est un atome
– successeur(X) n'est pas un atome
– appui(fenetre) n'est pas un atome
Les formules bien formées

●
Le langage est constitué de l'ensemble des Formules Bien
Formées (appelées aussi : FBFs ou Well Formed-Formula
WFF) ou expressions bien formées défini comme suit :
– Les atomes sont des fbfs
– si F et G sont des fbfs alors (¬G), (F ∧ G), (F ∨ G), (F →
G) et (F ↔ G) sont des fbfs
– si G est une fbf et X une variable alors ( ∃X)G et ( ∀X)G
sont des fbfs.
●
toutes les fbfs sont obtenues par application des 3 règles ci-
dessus.
●
Ordre de priorité des connecteurs :
Variable libre et liée

Champ ou portée d'un quantificateur = la fbf sur laquelle il

s'applique
●
∀X ∃Y (P(X, Y) ∧ ∃Z Q(X , Z))
– le champ de ∀X est
– le champ de ∃Y est
– le champ de ∃Z est
●
une occurrence de X est liée dans une fbf si elle est dans le
champ d'un quantificateur ∀ ou ∃ qui l'utilise ou si elle le suit.
sinon cette occurrence est dite libre
●
Une fbf sans variable libre est dite close ou fermée
Exemple

●
A = ∀X (∃Y P(X, Y) ∧ Q(X, Z)) ∧ R(X)
●
B = ∀X ((∃Y Q(X, Y)) ∧ P(X, Y, Z))
●
∀X ∃Y (P(X, Y) ∧ ∀Z R(X, Y, Z))
●
Déterminer les variables libres et liées

Mme Pidy Léonce

●
La sémantique
Théorèmes d'équivalence
Aux théorèmes cités précédemment on ajoute ceux-ci :
●
(∀X) G(X) = (∀Y) G(Y)
●
(∃X) G(X) = (∃Y) G(Y)
●
(¬((∃X) G(X))) = (∀X) (¬G(X))
●
(¬((∀X) G(X))) = (∃X) (¬G(X))
●
(∀X) (G(X) ∧ H(X)) = (∀X) G(X) ∧ (∀X) H(X)
●
(∃X) (G(X) ∨ H(X)) = (∃X) G(X) ∨ (∃X) H(X)
●
ATTENTION :
– (∀X) (G(X) ∨ H(X)) non équivalent à (∀X) G(X) ∨ (∀X) H(X)
– (∃X) (G(X) ∧ H(X)) non équivalent à (∃X) G(X) ∧ (∃X) H(X)
●
(∀X) F(X) ∨ (∀X) H(X) = (∀X) F(X) ∨ (∀Y) H(Y)
●
(∃X) F(X) ∧ (∃X) H(X) = (∃X) F(X) ∧ (∃Y) H(Y)
●
Représentation des Connaissances en
logique des prédicats
L'universelle affirmative

●
∀X (F(X) → G(X))
-
L'universelle négative

●
∀X (F(X) →¬G(X))
-
La particularité affirmative

●
∃X (F(X) ∧ G(X))
-
La particularité négative

●
∃X (F(X) ∧¬G(X))
-

Mme Pidy Léonce

Exemple

soit à traduire le groupes de phrases suivantes :

●
a) Marcus était un homme
●
b) Marcus était un pompéien
●
c) Tous les pompéiens étaient des romains
●
d) César était souverain
●
e) Tous les romains étaient fidèles à César, soit le haïssaient
●
f) Chacun est fidèle à quelqu'un
●
g) Marcus a essayé d'assassiner César