Logique pour l'Intelligence Artificielle
Cours complet expliqué depuis zéro
avec exemples de la vie réelle
Master 1 — Informatique
Partie 1 — Calcul des Propositions, connecteurs, FNC, résolution
propositions
Partie 2 — Logique du premier Variables, quantificateurs, substitution, clauses
ordre
Partie 3 — Logique non Défauts, exceptions, révision de croyances
monotone
Partie 4 — Résumé et astuces Points clés, erreurs fréquentes, méthodes
PARTIE 1 — Calcul des Propositions
1.1 C'est quoi une proposition ?
Une proposition est simplement une phrase qui est soit vraie (V), soit fausse (F). On ne peut
pas être les deux à la fois, et on ne peut pas ne pas savoir (en logique classique).
Exemples VRAIS (V) Exemples FAUX (F)
"2 + 2 = 4" "2 + 2 = 5"
"Le soleil se lève à l'est" "La lune est faite de fromage"
"Djibouti est en Afrique" "Le feu est froid"
"Il fait jour ou il fait nuit" "Je suis à deux endroits à la fois"
On note les propositions avec des lettres : P, Q, R, S... Par exemple :
P = 'Il pleut' Q = 'Je prends un parapluie' R = 'La route est mouillée'
1.2 Les 5 connecteurs logiques
On peut combiner des propositions avec des connecteurs. Il y en a 5 essentiels :
Symbol
Nom Se lit Vrai quand... Exemple réel
e
¬P NON 'non P' P est faux "Il ne pleut pas"
P∧Q ET 'P et Q' Les DEUX sont vrais "Il pleut ET il fait froid"
P∨Q OU 'P ou Q' Au moins UN est vrai "Café OU thé au petit déj"
IMPLIQU FAUX seulement si P vrai et
P→Q 'si P alors Q' "S'il pleut → parapluie"
E Q faux
P↔Q EQUIV. 'P ssi Q' Même valeur de vérité "Je sors ssi il fait beau"
Zoom sur l'implication (le connecteur le plus piégeux !)
L'implication P → Q se lit "Si P alors Q". Elle est fausse seulement quand P est vrai et Q est
faux. Pensez à une promesse :
Pluie (P) Parapluie (Q) P→Q Explication
V V V Il pleut, j'ai un parapluie → promesse tenue
V F F! Il pleut, je n'ai pas de parapluie → j'ai menti !
F V V Pas de pluie, j'ai quand même un parapluie → ok !
Pas de pluie, pas de parapluie → promesse non
F F V testée
RETENIR : P → Q est équivalent à ¬P ∨ Q (pas de P, ou Q)
1.3 La Forme Normale Conjonctive (FNC)
La FNC est une écriture standardisée d'une formule logique. On l'utilise pour préparer la
résolution. Une formule en FNC est une suite de clauses reliées par ET (∧), où chaque clause
est une suite de littéraux reliés par OU (∨).
FNC = (A ∨ B ∨ C) ∧ (D ∨ ¬E) ∧ (F) ∧ ...
Un littéral c'est une proposition (P) ou sa négation (¬P).
Algorithme en 3 étapes — toujours dans cet ordre :
Étape Éliminer les → Remplacer A → B par ¬A ∨ B
1
Étape Pousser les ¬ (De ¬(A ∧ B) → ¬A ∨ ¬B | ¬(A ∨ B) → ¬A ∧ ¬B | ¬¬A
2 Morgan) →A
Étape Distribuer ∨ sur ∧ A ∨ (B ∧ C) → (A ∨ B) ∧ (A ∨ C)
3
Exemple complet — transformer (P ∧ Q) → R :
(P ∧ Q) → R Formule de départ
¬(P ∧ Q) ∨ R Étape 1 : éliminer → (A → B devient ¬A ∨ B)
(¬P ∨ ¬Q) ∨ R Étape 2 : De Morgan sur ¬(P ∧ Q)
¬P ∨ ¬Q ∨ R Étape 3 : simplifier (déjà une disjonction)
Clause : {¬P, ¬Q, R} RÉSULTAT FNC — une seule clause !
1.4 La méthode de résolution
La résolution est une méthode pour prouver qu'une conclusion découle d'une base. On
utilise la réfutation : on suppose que la conclusion est fausse, et on montre que ça crée une
contradiction (clause vide ■).
Méthode : ajouter ¬(conclusion) à la base → dériver ■ → la conclusion est prouvée !
La règle de résolution : si on a une clause avec L et une autre avec ¬L, on peut les combiner en
supprimant L et ¬L :
(A ∨ L) et (¬L ∨ B) → résolvant : (A ∨ B) Si A ∨ B = vide (∅) alors on a ■ :
contradiction !
Exemple complet — prouver ¬A :
Base : {(A ∧ B) → C, C → D, D → E, ¬E, B}. On veut prouver ¬A.
Clause Contenu Explication
C1 ¬A ∨ ¬B ∨ C (A ∧ B) → C mis en FNC
C2 ¬C ∨ D C → D mis en FNC
C3 ¬D ∨ E D → E mis en FNC
C4 ¬E ¬E (fait)
C5 B B (fait)
C6 A Hypothèse : on suppose A vrai (réfutation)
--- --- ---
C7 = C3+C4 ¬D On résout C3 et C4 sur E
C8 = C2+C7 ¬C On résout C2 et C7 sur D
C9 = C1+C8 ¬A ∨ ¬B On résout C1 et C8 sur C
C10 = C9+C5 ¬A On résout C9 et C5 sur B
■ = C10+C6 CONTRADICTION ! On résout C10 et C6 sur A → ■
■ obtenu → B ∪ {A} est insatisfaisable → B implique ¬A ✓
PARTIE 2 — Logique du Premier Ordre (LPO)
2.1 Pourquoi aller au-delà du calcul propositionnel ?
Le calcul propositionnel parle de faits fixes. Mais si tu veux dire 'tout étudiant qui travaille
réussit', tu dois écrire une règle par personne. La LPO résout ce problème avec des variables et
des quantificateurs.
Calcul propositionnel Logique du premier ordre
EtudieAli → ReussitAli EtudieSara → ∀x (Etudie(x) → Reussit(x)) Une seule règle
ReussitSara EtudieKarim → ReussitKarim ... pour TOUT LE MONDE ! x est une variable qui
(une règle PAR personne !) représente n'importe qui.
1000 étudiants = 1000 règles 1000 étudiants = 1 règle ✓
2.2 Les éléments de la LPO
Élément Notation Signification
Variables x, y, z... Représentent des individus quelconques
Constantes Ali, Paris, 42... Des individus précis et nommés
Prédicats Etudie(x), Aime(x,y) Propriétés ou relations entre individus
Quantificateur ∀ ∀x P(x) 'Pour tout x, P(x) est vrai'
Quantificateur ∃ ∃x P(x) 'Il existe au moins un x tel que P(x)'
2.3 La substitution — comment appliquer une règle à un individu
Quand on a une règle générale avec une variable x, et qu'on veut l'appliquer à un individu précis
(Ali), on fait une substitution : on remplace x par Ali partout.
Règle : ∀x Etudie(x) → Reussit(x) Fait : Etudie(Ali) Substitution σ = {x ← Ali} Application :
Etudie(Ali) → Reussit(Ali) Conclusion : Reussit(Ali) ✓
2.4 Transformation en clauses (LPO)
Pour utiliser la résolution en LPO, on transforme les règles universelles en clauses. C'est comme
pour la FNC, mais on supprime aussi le ∀x (les variables restent implicitement universelles).
∀x (Etudie(x) ∧ IA(x) → Projet(x)) Règle de départ
∀x (¬Etudie(x) ∨ ¬IA(x) ∨ Projet(x)) Éliminer → et pousser ¬
Clause : {¬Etudie(x), ¬IA(x), Projet(x)} Supprimer ∀x → CLAUSE LPO
PARTIE 3 — Logique Non Monotone
3.1 Le problème avec la logique classique
En logique classique (propositions, LPO), si tu ajoutes de nouvelles informations, tu ne peux
jamais perdre de conclusions — tu ne peux qu'en gagner. Mais dans la vraie vie, c'est différent !
Logique MONOTONE (classique) Logique NON MONOTONE (vraie vie)
Tu sais que 2+2=4. Tu apprends que le ciel est Tu vois de la fièvre chez Amina. Tu conclus :
bleu. Tu sais toujours que 2+2=4. Les elle a une infection. Tu apprends qu'elle a eu
conclusions ne disparaissent jamais. un vaccin récent. Tu RÉVISES : ce n'est pas
une infection !
Plus d'infos → plus de conclusions (jamais Plus d'infos → parfois MOINS de
moins) conclusions
3.2 La règle par défaut
La logique non monotone utilise des règles par défaut (Reiter, 1980). Une règle par défaut dit :
'Normalement, si P est vrai, alors conclure Q — sauf si quelque chose l'interdit.'
Notation : Prémisse(x) : Conclusion(x) ■■■■■■■■■■■■■■■■■■■■■■■■■■■■■
Conclusion(x) Se lit : 'Si Prémisse(x) est vrai, et s'il est CONSISTANT de supposer
Conclusion(x), alors conclure Conclusion(x).'
La condition de consistance est la clé : le défaut s'applique seulement si ¬Conclusion n'est
pas dérivable de la base. Si quelque chose contredit la conclusion, le défaut est bloqué.
3.3 Exemple complet — le système médical
On a : • Défaut : Fièvre(x) : Infection(x) / Infection(x) [par défaut, fièvre → infection] • Règle :
VaccinRecent(x) → EffetSecondaire(x) • Règle : EffetSecondaire(x) → ¬Infection(x) • Fait :
Fièvre(Amina), VaccinRecent(Amina)
Étape 1 — sans Fièvre(Amina) est vrai. ¬Infection(Amina) n'est pas dérivable. → Le
VaccinRecent défaut s'applique → Infection(Amina) ✓
Étape 2 — avec VaccinRecent(Amina) → EffetSecondaire(Amina) → ¬Infection(Amina)
VaccinRecent Maintenant ¬Infection(Amina) EST dérivable ! → La condition de
consistance est violée → Le défaut est BLOQUÉ !
Conclusion On RETIRE Infection(Amina). La fièvre s'explique par le vaccin, pas une
infection. C'est exactement comme un médecin qui révise son diagnostic
!
3.4 Preuve formelle de non-monotonicité
Un raisonnement est non monotone si on peut avoir :
Base B1 ⊂ Base B2 mais Th(B1) ⊄ Th(B2) (Ajouter des infos peut faire disparaître des
conclusions !)
Dans notre exemple : • B1 = {Fièvre(Amina)} → Infection(Amina) est dans Th(B1) • B2 = B1 ∪
{VaccinRecent(Amina)} → Infection(Amina) n'est PLUS dans Th(B2) • B1 ⊂ B2 mais Th(B1) ⊄
Th(B2) → Non monotone !
PARTIE 4 — Résumé et Astuces pour les Examens
4.1 Tableau comparatif des 3 logiques
Critère Calcul prop. LPO Non monotone
Objets Propositions fixes Individus, relations Individus + défauts
Quantification Non Oui (∀, ∃) Oui
Monotonie Oui ✓ Oui ✓ NON ✗
Révision Non Non Oui
Outil principal FNC + résolution Clauses + substitution Défauts de Reiter
Usage typique Circuits, SAT IA classique, BD Systèmes experts
4.2 Erreurs fréquentes à éviter
✗ Oublier De Morgan ¬(A ∧ B) ≠ ¬A ∧ ¬B (FAUX !) ¬(A ∧ B) = ¬A ∨ ¬B (CORRECT !)
✗ Mal lire l'implication P → Q est FAUX seulement quand P=V et Q=F. Pas quand P=F —
dans ce cas c'est toujours VRAI !
✗ Oublier de spécifier σ Toujours écrire la substitution utilisée. Ex : σ = {x ← Ali} lors de
en LPO chaque étape.
✗ Mal vérifier la Le défaut est bloqué si ¬Conclusion est DÉRIVABLE. Pas juste si
consistance du défaut c'est possible — il faut que ça découle de la base.
✗ Confondre monotone Monotone : ajouter des infos ne retire jamais de conclusions. Non
et non monotone monotone : de nouvelles infos peuvent annuler des conclusions.
4.3 Mémo — formules essentielles à connaître par coeur
• A → B ≡ ¬A ∨ B
• ¬(A ∧ B) ≡ ¬A ∨ ¬B (De Morgan 1)
• ¬(A ∨ B) ≡ ¬A ∧ ¬B (De Morgan 2)
• A ∨ (B ∧ C) ≡ (A ∨ B) ∧ (A ∨ C) (distributivité)
• ¬∀x P(x) ≡ ∃x ¬P(x) (négation du ∀)
• ¬∃x P(x) ≡ ∀x ¬P(x) (négation du ∃)
• Réfutation : pour prouver φ, ajouter ¬φ et dériver ■
• Défaut bloqué si ¬Conclusion est dérivable de la base
Master 1 — Logique pour l'IA | Cours expliqué depuis zéro